Title | Discrete Mathematics with Application-4th Edition by Susanna S. Epp |
---|---|
Author | Brian Mgabi |
Pages | 994 |
File Size | 88.4 MB |
File Type | |
Total Downloads | 81 |
Total Views | 564 |
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 ...
Accelerat ing t he world's research.
Discrete Mathematics with Application-4th Edition by Susanna S. Epp brian mgabi
Related papers
Download a PDF Pack of t he best relat ed papers
This page was intentionally left blank
List of Symbols Subject
Symbol
Meaning
Logic
∼p
not p
25
p and q
25
p∨q
p or q
25
p or q but not both p and q
28
P≡Q
P is logically equivalent to Q
30
p∧q
p ⊕ q or p XOR q p→q
if p then q
40
p if and only if q
45
∴
therefore
51
P(x)
predicate in x
P(x) ⇒ Q(x)
every element in the truth set for P(x) is in the truth set for Q(x)
p↔q
Number Theory and Applications
97 104
P(x) and Q(x) have identical truth sets
104
for all
101
there exists
103
NOT-gate
67
AND
AND-gate
67
OR
OR-gate
67
NAND
NAND-gate
75
NOR
NOR-gate
75
P(x) ⇔ Q(x)
∀
Applications of Logic
Page
∃
NOT
|
Sheffer stroke
74
↓
Peirce arrow
74
n2
number written in binary notation
78
n 10
number written in decimal notation
78
n 16
number written in hexadecimal notation
91
d divides n
170
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
d |n
d /| n
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
⌈x⌉
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
... n
and so forth
227
ak
the summation from k equals m to n of ak
230
ak
the product from k equals m to n of ak
223
n!
n factorial
237
a∈A
a is an element of A
k=m n
k=m
Set Theory
7
a is not an element of A
7
{a1 , a2 , . . . , an }
the set with elements a1 , a2 , . . . , an
7
R, R− , R+ , Rnonneg
the sets of all real numbers, negative real numbers, positive real numbers, and nonnegative real numbers
7, 8
Z, Z− , Z+ , Znonneg
the sets of all integers, negative integers, positive integers, and nonnegative integers
7, 8
Q, Q− , Q+ , Qnonneg
the sets of all rational numbers, negative rational numbers, positive rational numbers, and nonnegative rational numbers
7, 8
N
the set of natural numbers
8
A⊆B
A is a subset of B
9
A is not a subset of B
9
a∈ / A
{x ∈ D | P(x)}
A ⊆ B
A=B
A∪B
the set of all x in D for which P(x) is true
8
A equals B
339
A union B
341
A intersect B
341
B−A
the difference of B minus A
341
Ac
the complement of A
341
A∩B
(x, y)
ordered pair
(x 1 , x2 , . . . , xn )
ordered n-tuple
A×B
the Cartesian product of A and B the Cartesian product of A1 , A2 , . . . , An
347
∅
the empty set
361
the power set of A
346
A1 × A2 × · · · × An
P( A)
11 346 12
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
Counting and Probability
N (A)
the number of elements in set A
518
P( A)
the probability of a set A
518
P(n, r )
the number of r -permutations of a set of n elements
553
n
n choose r , the number of r -combinations of a set of n elements, the number of r -element subsets of a set of n elements
566
[xi1 , xi2 , . . . , xir ]
multiset of size r
584
the probability of A given B
612
r
P( A | B)
Functions
f: X → Y f (x) f
x →y
Relations
f is a function from X to Y
384
the value of f at x
384
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
x
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
b
Algorithm Efficiency
Page
x∼ =y
x is approximately equal to y
237
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
xRy
x is related to y by R
R
−1
m ≡ n (mod d) [a]
xy
the inverse relation of R
14 444
m is congruent to n modulo d
473
the equivalence class of a
465
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.
This page was intentionally left blank
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 suppressed 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.
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! Discrete Mathematics 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
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 [email protected].
Content Project Manager: Alison Eigel Zade Senior Art Director: Jill Ort
Library of Congress Control Number: 2010927831
Senior Print Buyer: Diane Gibbons
Student Edition: ISBN-13: 978-0-495-39132-6 ISBN-10: 0-495-39132-8
Right Acquisition Specialists: Timothy Sisler and Don Schlotman Production Service: Elm Street Publishing Services Photo Manager: Chris Althof, Bill Smith Group
Brooks/Cole 20 Channel Center Street Boston, MA 02210 USA
Cover Designer: Hanh Luu Cover Image: GettyImages.com (Collection: OJO Images, Photographer: Martin Barraud) Compositor: Integra Software Services Pvt. Ltd.
Cengage Learning is a leading provider of customized learning solutions with office locations around the globe, including Singapore, the United Kingdom, Australia, Mexico, Brazil, and Japan. Locate your local office at: international.cengage.com/region. Cengage Learning products are represented in Canada by Nelson Education, Ltd. For your course and learning solutions, visit www.cengage.com Purchase any of our products at your local college store or at our preferred online store www.cengagebrain.com.
Printed in Canada 1 2 3 4 5 6 7 14 13 12 11 10
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.
To Jayne and Ernest
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.
CONTENTS Chapter 1 Speaking Mathematically 1.1 Variables
1
1
Using Variables in Mathematical Discourse; Introduction to Universal, Existential, and Conditional Statements
1.2 The Language of Sets
6
The Set-Roster and Set-Builder Notations; Subsets; Cartesian Products
1.3 The Language of Relations and Functions
13
Definition of a Relation from One Set to Another; Arrow Diagram of a Relation; Definition of Function; Function Machines; Equality of Functions
Chapter 2 The Logic of Compound Statements
23
2.1 Logical Form and Logical Equivalence
23
Statements; Compound Statements; Truth Values; Evaluating the Truth of More General Compound Statements; Logical Equivalence; Tautologies and Contradictions; Summary of Logical Equivalences
2.2 Conditional Statements
39
Logical Equivalences Involving →; Representation of If-Then As Or; The Negation of a Conditional Statement; The Contrapositive of a Conditional Statement; The Converse and Inverse of a Conditional Statement; Only If and the Biconditional; Necessary and Sufficient Conditions; Remarks
2.3 Valid and Invalid Arguments
51
Modus Ponens and Modus Tollens; Additional Valid Argument Forms: Rules of Inference; Fallacies; Contradictions and Valid Arguments; Summary of Rules of Inference
2.4 Application: Digital Logic Circuits
64
Black Boxes and Gates; The Input/Output Table for a Circuit; The Boolean Expression Corresponding to a Circuit; The Circuit Corresponding to a Boolean Expression; Finding a Circuit That Corresponds to a Given Input/Output Table; Simplifying Combinational Circuits; NAND and NOR Gates
2.5 Application: Number Systems and Circuits for Addition
78
Binary Representation of Numbers; Binary Addition and Subtraction; Circuits for Computer Addition; Two’s Complements and the Computer Representation of vi
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.
Contents
vii
Negative Integers; 8-Bit Representation of a Number; Computer Addition with Negative Integers; Hexadecimal Notation
Chapter 3 The Logic of Quantified Statements
96
3.1 Predicates and Quantified Statements I
96
The Universal Quantifier: ∀; The Existential Quantifier: ∃; Formal Versus Informal Language; Universal Conditional Statements; Equivalent Forms of Universal and Existential Statements; Implicit Quantification; Tarski’s World
3.2 Predicates and Quantified Statements II
108
Negations of Quantified Statements; Negations of Universal Conditional Statements; The Relation among ∀, ∃, ∧, and ∨; Vacuous Truth of Universal Statements; Variants of Universal Conditional Statements; Necessary and Sufficient Conditions, Only If
3.3 Statements with Multiple Quantifiers
117
Translating from Informal to Formal Language; Ambiguous Language; Negations of Multiply-Quantified Statements; Order of Quantifiers; Formal Logical Notation; Prolog
3.4 Arguments with Quantified Statements
132
Universal Modus Ponens; Use of Universal Modus Ponens in a Proof; Universal Modus Tollens; Proving Validity of Arguments with Quantified Statements; Using Diagrams to Test for Validity; Creating Additional Forms of Argument; Remark on the Converse and Inverse Errors
Chapter 4 Elementary Number Theory and Methods of Proof
145
4.1 Direct Proof and Counterexample I: Introduction
146
Definitions; Proving Existential Statements; Disproving Universal Statements by Counterexample; Proving Universal Statements; Directions for Writing Proofs of Universal Statements; Variations among Proofs; Common Mistakes; Getting Proofs Started; Showing That an Existential Statement Is False; Conjecture, Proof, and Disproof
4.2 Direct Proof and Counterexample II: Rational Numbers
163
More on Generalizing from the Generic Particular; Proving Properties of Rational Numbers; Deriving New Mathematics from Old
4.3 Direct Proof and Counterexample III: Divisibility
170
Proving Properties of Divisibility; Counterexamples and Divisibility; The Unique Factorization of Integers Theorem
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 additiona...