# Discrete mathematics Functions

1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

S 50 R 51

1st Pass Pages

1019763_FM_VOL-I.qxp 9/17/07 4:22 PM Page viii

User

Zone de texte

This page was intentionally left blank

List of Symbols

Subject Symbol Meaning Page

Logic ∼p not p 25 p ∧ q p and q 25 p ∨ q p or q 25 p ⊕ q or p XOR q p or q but not both p and q 28 P ≡ Q P is logically equivalent to Q 30 p→ q if p then q 40 p q p if and only if q 45 ∴ therefore 51 P(x) predicate in x 97

P(x)⇒ Q(x) every element in the truth set for P(x) is in 104 the truth set for Q(x)

P(x)⇔ Q(x) P(x) and Q(x) have identical truth sets 104 ∀ for all 101 ∃ there exists 103

Applications of Logic NOT NOT-gate 67

AND AND-gate 67

OR OR-gate 67

NAND NAND-gate 75

NOR NOR-gate 75

| Sheffer stroke 74

↓ Peirce arrow 74 n2 number written in binary notation 78

n10 number written in decimal notation 78

n16 number written in hexadecimal notation 91

Number Theory and Applications

d | n d divides n 170 d |/ n d does not divide n 172 n div d the integer quotient of n divided by d 181

n mod d the integer remainder of n divided by d 181

�x� the floor of x 191 �x� the ceiling of x 191 |x | the absolute value of x 187 gcd(a, b) the greatest common divisor of a and b 220

x := e x is assigned the value e 214

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

Subject Symbol Meaning Page

Sequences . . . and so forth 227 n∑

k=m ak the summation from k equals m to n of ak 230

n∏ k=m

ak the product from k equals m to n of ak 223

n! n factorial 237 Set a ∈ A a is an element of A 7 Theory a /∈ A a is not an element of A 7

{a1, a2, . . . , an} the set with elements a1, a2, . . . , an 7 {x ∈ D | P(x)} the set of all x in D for which P(x) is true 8 R,R−,R+,Rnonneg the sets of all real numbers, negative real 7, 8

numbers, positive real numbers, and nonnegative real numbers

Z,Z−,Z+,Znonneg the sets of all integers, negative integers, 7, 8 positive integers, and nonnegative integers

Q,Q−,Q+,Qnonneg the sets of all rational numbers, negative 7, 8 rational numbers, positive rational numbers, and nonnegative rational numbers

N the set of natural numbers 8

A ⊆ B A is a subset of B 9 A �⊆ B A is not a subset of B 9 A = B A equals B 339 A ∪ B A union B 341 A ∩ B A intersect B 341 B − A the difference of B minus A 341 Ac the complement of A 341

(x, y) ordered pair 11

(x1, x2, . . . , xn) ordered n-tuple 346

A × B the Cartesian product of A and B 12 A1 × A2 × · · · × An the Cartesian product of A1, A2, . . . , An 347 ∅ the empty set 361 P(A) the power set of A 346

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

List of Symbols

Subject Symbol Meaning Page

Counting and N (A) the number of elements in set A 518 Probability P(A) the probability of a set A 518

P(n, r) the number of r -permutations of a set of 553 n elements(n

r

) n choose r , the number of r -combinations 566 of a set of n elements, the number of r -element subsets of a set of n elements

[xi1 , xi2 , . . . , xir ] multiset of size r 584 P(A | B) the probability of A given B 612

Functions f : X → Y f is a function from X to Y 384 f (x) the value of f at x 384

x f→y f sends x to y 384

f (A) the image of A 397

f −1(C) the inverse image of C 397

Ix the identity function on X 387

bx b raised to the power x 405, 406

expb(x) b raised to the power x 405, 406

logb(x) logarithm with base b of x 388

F−1 the inverse function of F 411

f ◦ g the composition of g and f 417 Algorithm x ∼= y x is approximately equal to y 237 Efficiency O( f (x)) big-O of f of x 727

�( f (x)) big-Omega of f of x 727

�( f (x)) big-Theta of f of x 727

Relations x R y x is related to y by R 14

R−1 the inverse relation of R 444

m ≡ n (mod d) m is congruent to n modulo d 473 [a] the equivalence class of a 465 x � y x is related to y by a partial order relation � 502

Continued on first page of back endpapers.

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

DISCRETE MATHEMATICS

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

DISCRETE MATHEMATICS WITH APPLICATIONS

FOURTH EDITION

SUSANNA S. EPP DePaul University

Australia · Brazil · Japan · Korea ·Mexico · Singapore · Spain · United Kingdom · United States

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

S 50 R 51

1st Pass Pages

1019763_FM_VOL-I.qxp 9/17/07 4:22 PM Page viii

User

Zone de texte

This page was intentionally left blank

52609_00_fm_pi-pxxvi.indd ii52609_00_fm_pi-pxxvi.indd ii 2/1/10 11:37:43 PM2/1/10 11:37:43 PM

This is an electronic version of the print textbook. Due to electronic rights

restrictions, some third party content may be suppressed. Editorial review has deemed that any suppres ed content does not materially

affect the overall learning experience. The publisher reserves the right to remove content from this title at any time if subsequent rights restrictions require it. For valuable information on pricing, previous editions, changes to current editions, and alternate formats, please visit www.cengage.com/highered to search by ISBN#, author, title, or keyword for materials in your areas of interest.

s

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

Cover Photo: The stones are discrete objects placed one on top of another like a chain of careful reasoning. A person who decides to build such a tower aspires to the heights and enjoys playing with a challenging problem. Choosing the stones takes both a scientific and an aesthetic sense. Getting them to balance requires patient effort and careful thought. And the tower that results is beautiful. A perfect metaphor for discrete mathematics!

DiscreteMathematics with Applications, Fourth Edition Susanna S. Epp

Publisher: Richard Stratton

Senior Sponsoring Editor: Molly Taylor

Associate Editor: Daniel Seibert

Editorial Assistant: Shaylin Walsh

Associate Media Editor: Andrew Coppola

Senior Marketing Manager: Jennifer Pursley Jones

Marketing Communications Manager: Mary Anne Payumo

Marketing Coordinator: Erica O’Connell

Content Project Manager: Alison Eigel Zade

Senior Art Director: Jill Ort

Senior Print Buyer: Diane Gibbons

Right Acquisition Specialists: Timothy Sisler and Don Schlotman

Production Service: Elm Street Publishing Services

Photo Manager: Chris Althof, Bill Smith Group

Cover Designer: Hanh Luu

Cover Image: GettyImages.com (Collection: OJO Images, Photographer: Martin Barraud)

Compositor: Integra Software Services Pvt. Ltd.

c© 2011, 2004, 1995 Brooks/Cole Cengage Learning ALL RIGHTS RESERVED. No part of this work covered by the copyright herein may be reproduced, transmitted, stored, or used in any form or by any means graphic, electronic, or mechanical, including but not limited to photocopying, recording, scanning, digitizing, taping, Web distribution, information networks, or information storage and retrieval systems, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without the prior written permission of the publisher.

For product information and technology assistance, contact us at Cengage Learning Customer & Sales Support, 1-800-354-9706.

For permission to use material from this text or product, submit all requests online at www.cengage.com/permissions.

Further permissions questions can be emailed to permissionrequest@cengage.com.

Library of Congress Control Number:…

## Leave a Reply

Want to join the discussion?Feel free to contribute!