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,, + " -". + 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.]

2 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. 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;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.

3 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. 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.

4 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: 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, 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.

5 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: 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.

6 Automating Logic Exercises Predicates and Quantification Predicates Quantification Restricted Quantification Nested Quantifiers Negation and Quantification Quantification with Conjunction and Disjunction Application: 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.

7 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.

8 Two Combinatorial Results Exercises Countable and Uncountable Sets Countably Infinite Sets Cantor's First Diagonal Argument Uncountable Sets and Cantor's Second Diagonal Argument Cardinalities of Power Sets Exercises 273xii Chapter Review Summary Starting to Review Review Questions Using Discrete Mathematics in Computer Science 280 CHAPTER 5 Analysis of Algorithms Comparing Growth Rates of Functions A Measure for Comparing Growth Rates Properties of Asymptotic Domination Polynomial Functions Exponential and Logarithmic Functions Exercises Complexity of Programs Counting Statements Two Algorithms Illustrating Selection An Algorithm Illustrating Repetition An Algorithm Illustrating Nested Repetition Time Complexity of an Algorithm Variants on the Definition of Complexity Exercises Uncomputability The Halting Problem Chapter Review Summary Starting to Review Review Questions Using Discrete Mathematics in Computer Science 323 Contents xiiiCHAPTER 6 Graph Theory Introduction to Graph Theory Definitions Subgraphs The Handshaking Problem Paths and Cycles Hamiltonian Cycles Graph Isomorphism Representation of Graphs Adjacency Matrix Adjacency Lists Exercises Connected Graphs The Relation CONN Depth First Search Complexity of Dfs Breadth First Search Finding Connected Components The K6nigsberg Bridge Problem Graph Tracing Exercises Trees Definition of Trees Characterization of Trees Spanning Trees Kruskal's Algorithm Correctness of Kruskal's Algorithm Kruskal's Algorithm for Weighted Graphs Correctness of Kruskal's Weighted Graph Algorithm 378xiv

9 Rooted Trees Binary Trees Binary Search Trees Tree Traversals Application: Decision Trees Exercises Directed Graphs Basic Definitions Directed Trails, Paths, Circuits, and Cycles Directed Graph Isomorphism Application: Scheduling a Meeting Facility WAITFOR Graphs Finding a Cycle in a Directed Graph Directed Cycle Detection Algorithm Correctness of Directed Cycle Detection Priority in Scheduling Algorithm for Topological Sort Correctness of Topological Sort Algorithm Connectivity in Directed Graphs Strongly Connected Directed Graphs Application: Designing One-Way Street Grids Eulerian Circuits in Directed Graphs Exercises Chapter Review Summary Starting to Review Review Questions Using Discrete Mathematics in Computer Science 416 CHAPTER 7 Counting and Combinatorics Traveling Salesperson's Problem 421 Contents Counting Principles The Multiplication Principle Addition Principle Set Decomposition Principle Counting the Complement Using the Pigeon-Hole Principle Application.

10 UNIX Logon Passwords Exercises Permutations and Combinations Permutations Linear Arrangements Circular Permutations Combinations Poker Hands Counting the Complement Decomposition into Subproblems Constructing the kth Permutation Exercises Counting with Repeated Objects Permutations with Repetitions Combinations with Repetitions Combinatorial Identities Binomial Coefficients Multinomials Pascal's Triangle Exercises Chapter Review Summary Starting to Review Review Questions Using Discrete Mathematics in Computer Science 472xvi ContentsCHAPTER 8 Discrete Probability Ideas of Chance in Computer Science Introductory Examples Basic Definitions Frequency Interpretation of Probability Introductory Example Reconsidered The Combinatorics of Uniform Probability Density Set Theory and the Probability of Events Exercises Cross Product Sample Spaces A Multiplication Principle The Cross Product of Sample Spaces Bernoulli Trial Processes Events of Cross Product Form Two Ways of Viewing Events Exercises Independent Events and Conditional Probability Independent Events Introduction to Conditional Probability Exploring Conditional Probability Using Bayes' Rule with the Theorem of Total Probability Exercises Discrete Random Variables Distributions of a Random Variable The Binomial Distribution The Hypergeometric Distribution Expectation of a Random Variable The Sum of Random Variables Exercises Variance, Standard Deviation.