Discrete Mathematics for Computer Science - UH

1 I. = . 1. ! |~ilHTerms Meaning SectionSets, Proof Templates, and Inductionx e A x is an element ofA f A x is not an element ofA x E A and P(x)} Set notation Natural numbers Integers Rationals Real numbers = B Sets A and B are equal C B A is a subset of B g B A is nota subset of B C B A is a proper subset of B 5 B A is nota proper subset of B a bimplies a b a if and only if b A union B A intersect B Generalized union of family of sets X Generalized intersection of family of sets X Xi Xm U ..UXn Xm n .. n Xn -B Elements of A not in B Elements not in A D B (A U B) -(A n B) (X) Power set of X x Y Product of X and Y A y Meet ofx and y v y Join ofx and y Complement of x Top Bottom Cardinality of A a,, + " -".

2 + a,, Meaning SectionFormal Logic"--p Not p p and q p or q q p implies q q p is equivalent to q X S logically implies X 3 AKP Conjecture about complexity (Vx)P(x) For all x, P(x) (3x)P(x) There exists an x such that P(x) (VxE V)P(x) For all X EV, P(x) (3x E V)P(x) There exists an x E V such that P(x) [i ..j] Array with elements Ail, .., A[j] Sheffer stroke Exclusive or , Pierce arrow (x, y) E R or xRy x is R-related to y The inverse of the relation R Composition of relations R and S + U Ri * URO R' =- m(modp) n -m = kp for some k E N Identity relation Less than or equal relation Greater than relation Greater than or equal relation [x] Equivalence class of x m divides n D.

3 S Equijoin of relations R and S is the World Wide Web site forBrooks/Cole and is your direct source to dozens ofonline you can find out aboutsupplements, demonstration software, and studentresources. You can also send email to many of ourauthors and preview new publicationsand exciting new the way the world learnsDiscrete Mathematicsfor Computer Sciencefo Copue ScienceGary HaggardBucknell UniversityJohn SchlipfUniversity of CincinnatiSue WhitesidesMcGill UniversityTHOrVIMSO3 NBROOGKS/COLE Australia Canada Mexico Singapore SpainUnited Kingdom United StatesTHOIMSO>NBROOKS/COLEP ublisher: Bob Pirtle Production Service: Hearthside Publishing Service.

4 Assistant Editor: Stacy Green Anne SeitzEditorial Assistant: Katherine Cook Text Designer: Roy NeuhausTechnology Project Manager: Earl Perry Copy Editor: Hearthside Publishing Service;Marketing Manager: Tom Ziolkowski Wesley MorrisonMarketing Assistant: Erin Mitchell Illustrator: Hearthside Publishing Service;Advertising Project Manager: Bryan Vann Jade MyersSigning Representative: Stephanie Shedlock Cover Designer: Roy R. NeuhausProject Manager, Editorial Production: Cover Image: DigitalVisionCheryll Linthicum Cover Printer: Phoenix Color CorpArt Director: Vernon Boes Compositor: ATLISP rint/Media Buyer: Doreen Suruki Printer: Phoenix Color CorpPermissions Editor: Chelsea JungetCOPYRIGHT 2006 Thomson Brooks/Cole, a part of Thomson Higher EducationThe Thomson Corporation.

5 Thomson, the Star logo, and 10 Davis DriveBrooks/Cole are trademarks used herein under license. Belmont, CA 94002-3098 ALL RIGHTS RESERVED. No part of this work covered USAby the copyright hereon may be reproduced or used in any Asiaform or by any means-graphic, electronic, or mechanical, Thomson Learningincluding photocopying, recording, taping, Web distribution, 5 Shenton Way #01-01information storage and retrieval systems, or in any other UIC Buildingmanner-without the written permission of the publisher. Singapore 068808 Australia/New ZealandPrinted in the United States of America Thomson Learning1 2 3 4 5 6 7 09 08 07 06 05 102 Dodds StreetSouthbank, Victoria 3006 AustraliaFor more information about our products, Canadacontact us at.

6 NelsonThomson Learning Academic Resource Center 1120 Birchmount Road1-800-423-0563 Toronto, Ontario MIK 5G4 CanadaFor permission to use material from this text orproduct, submit a request online at Europe/Middle East/ Thomson LearningAny additional questions about permissions can be High Holbom Housesubmitted by email to 50/51 Bedford RowLondon, WC1R 4 LRUnited KingdomLibrary of Congress Control Number: 2004113828 Latin AmericaThomson LearningISBN 0-534-49501-X Seneca, 53 Colonia Polanco . %11560 Mexico ! MexicoSpain/Portugal4 EcyO'- ParaninfoCalle Magallanes, 2528015 MadridSpainContentsCHAPTER 1 Sets, Proof Templates, and Basic Definitions Describing Sets Mathematically Set Membership Equality of Sets Finite and Infinite Sets Relations Between Sets Venn Diagrams Templates Exercises Operations on Sets Union and Intersection Set Difference, Complements.

7 And DeMorgan's Laws New Proof Templates Power Sets and Products Lattices and Boolean Algebras Exercises The Principle of Inclusion-Exclusion Finite Cardinality Principle of Inclusion-Exclusion for Two Sets Principle of Inclusion-Exclusion for Three Sets Principle of Inclusion-Exclusion for Finitely Many Sets Exercises 42viiviii Mathematical Induction A First Form of Induction A Template for Constructing Proofs by Induction Application: Fibonacci Numbers Application: Size of a Power Set Application: Geometric Series Program Correctness Pseudocode Conventions An Algorithm to Generate Perfect Squares Two Algorithms for Computing Square Roots Exercises Strong Form of Mathematical Induction Using the Strong Form of Mathematical Induction Application: Algorithm to Compute Powers Application: Finding Factorizations Application.

8 Binary Search Exercises Chapter Review Summary Starting to Review Review Questions Using Discrete Mathematics in Computer Science 87 CHAPTER 2 Formal Logic Introduction to Propositional Logic Formulas Expression Trees for Formulas Abbreviated Notation for Formulas Using Gates to Represent Formulas Exercises Truth and Logical Truth Tautologies 106 Contents Substitutions into Tautologies Logically Valid Inferences Combinatorial Networks Substituting Equivalent Subformulas Simplifying Negations Exercises Normal Forms Disjunctive Normal Form Application: DNF and Combinatorial Networks Conjunctive Normal Form Application: CNF and Combinatorial Networks Testing Satisfiability and Validity The Famous 'P Af r Conjecture Resolution Proofs: Automating Logic Exercises Predicates and Quantification Predicates Quantification Restricted Quantification Nested Quantifiers Negation and Quantification Quantification with Conjunction and Disjunction Application.

9 Loop Invariant Assertions Exercises Chapter Review Summary Starting to Review Review Questions Using Discrete Mathematics in Computer Science 151 CHAPTER 3 Relations Binary Relations n-ary Relations 162x Operations on Binary Relations Inverses Composition Exercises Special Types of Relations Reflexive and Irreflexive Relations Symmetric and Antisymmetric Relations Transitive Relations Reflexive, Symmetric, and Transitive Closures Application: Transitive Closures in Medicine and Engineering Exercises Equivalence Relations Partitions Comparing Equivalence Relations Exercises Ordering Relations Partial Orderings Linear Orderings Comparable Elements Optimal Elements in Orderings Application: Finding a Minimal Element Application: Embedding a Partial Order Exercises relational Databases.

10 An Introduction Storing Information in Relations relational algebra Exercises Chapter Review Summary Starting to Review Review Questions Using Discrete Mathematics in Computer Science 217 Contents xiCHAPTER 4 Functions Basic Definitions Functions as Rules Functions as Sets Recursively Defined Functions Graphs of Functions Equality of Functions Restrictions of Functions Partial Functions 1-1 and Onto Functions Increasing and Decreasing Functions Exercises Operations on Functions Composition of Functions Inverses of Functions Other Operations on Functions Sequences and Subsequences Exercises The Pigeon-Hole Principle k to 1 Functions Proofs of the Pigeon-Hole Principle Application: Decimal Expansion of Rational Numbers Application: Problems with Divisors and Schedules Application.