Lecture Notes in Discrete Mathematics

1 Lecture Notes in Discrete Mathematics Marcel B. Finan Arkansas Tech University All c Rights Reserved 2. Preface This book is designed for a one semester course in Discrete Mathematics for sophomore or junior level students. The text covers the mathematical concepts that students will encounter in many disciplines such as computer science, engineering, Business, and the sciences. Besides reading the book, students are strongly encouraged to do all the exer- cises. Mathematics is a discipline in which working the problems is essential to the understanding of the material contained in this book. Students are strongly encouraged to keep up with the exercises and the sequel of concepts as they are going along, for Mathematics builds on itself. Instructors can request the solutions to the problems via email: Finally, I would like to take the opportunity to thank Professor Vadim Pono- marenko from San Diego State University for pointing out to me many errors in the book and for his valuable suggestions.

2 Marcel B. Finan May 2001. 3. 4 PREFACE. Contents Preface 3. Fundamentals of Mathematical Logic 7. 1 Propositions and Related Concepts .. 8. 2 Conditional and Biconditional Propositions .. 18. 3 Rules of Inferential Logic .. 24. 4 Propositions and Quantifiers .. 33. 5 Arguments with Quantified Premises .. 41. 6 Project I: Digital Logic Design .. 45. 7 Project II: Number Systems .. 50. Fundamentals of Mathematical Proofs 53. 8 Methods of Direct Proof I .. 53. 9 More Methods of Proof .. 59. 10 Methods of Indirect Proofs: Contradiction and Contraposition . 64. 11 Method of Proof by Induction .. 67. 12 Project III: Elementary Number Theory and Mathematical Proofs 75. 13 Project IV: The Euclidean Algorithm .. 77. 14 Project V: Induction and the Algebra of Matrices.

3 79. Fundamentals of Set Theory 83. 15 Basic Definitions .. 83. 16 Properties of Sets .. 92. 17 Project VI: Boolean Algebra .. 100. Relations and Functions 101. 18 Equivalence Relations .. 101. 19 Partial Order Relations .. 113. 5. 6 CONTENTS. 20 Functions: Definitions and Examples .. 119. 21 Bijective and Inverse Functions .. 127. 22 Recursion .. 133. 23 Project VII: Applications to Relations .. 149. 24 Project VIII: Well-Ordered Sets and Lattices .. 152. 25 Project IX: The Pigeonhole Principle .. 153. 26 Project X: Countable Sets .. 154. 27 Project XI: Finite-State Automaton .. 156. Introduction to the Analysis of Algorithms 159. 28 Time Complexity and O-Notation .. 159. 29 Logarithmic and Exponential Complexities .. 167. 30 - and -Notations .. 171. Fundamentals of Counting and Probability Theory 175.

4 31 Elements of Counting .. 175. 32 Basic Probability Terms and Rules .. 182. 33 Binomial Random Variables .. 194. Elements of Graph Theory 201. 34 Graphs, Paths, and Circuits .. 201. 35 Trees .. 215. Fundamentals of Mathematical Logic Logic is commonly known as the science of reasoning. The emphasis here will be on logic as a working tool. We will develop some of the symbolic techniques required for computer logic. Some of the reasons to study logic are the following: At the hardware level the design of 'logic' circuits to implement in- structions is greatly simplified by the use of symbolic logic. At the software level a knowledge of symbolic logic is helpful in the design of programs. 7. 8 FUNDAMENTALS OF MATHEMATICAL LOGIC. 1 Propositions and Related Concepts A proposition is any meaningful statement that is either true or false, but not both.

5 We will use lowercase letters, such as p, q, r, , to represent propositions. We will also use the notation p:1+1=3. to define p to be the proposition 1 + 1 = 3. The truth value of a proposition is true, denoted by T, if it is a true statement and false, denoted by F, if it is a false statement. Statements that are not propositions include questions and commands. Example Which of the following are propositions? Give the truth value of the propo- sitions. a. 2 + 3 = 7. b. Julius Caesar was president of the United States. c. What time is it? d. Be quiet ! Solution. a. A proposition with truth value (F). b. A proposition with truth value (F). c. Not a proposition since no truth value can be assigned to this statement. d. Not a proposition Example Which of the following are propositions?

6 Give the truth value of the propo- sitions. a. The difference of two primes. b. 2 + 2 = 4. c. Washington is the capital of New York. d. How are you? Solution. a. Not a proposition. b. A proposition with truth value (T). c. A proposition with truth value (F). 1 PROPOSITIONS AND RELATED CONCEPTS 9. d. Not a proposition New propositions called compound propositions or propositional func- tions can be obtained from old ones by using symbolic connectives which we discuss next. The propositions that form a propositional function are called the propositional variables. Let p and q be propositions. The conjunction of p and q, denoted p q, is the proposition: p and q. This proposition is defined to be true only when both p and q are true and it is false otherwise.

7 The disjunction of p and q, denoted p q, is the proposition: p or q. The 'or' is used in an inclusive way. This proposition is false only when both p and q are false, otherwise it is true. Example Let p: 5<9. q : 9 < 7. Construct the propositions p q and p q. Solution. The conjunction of the propositions p and q is the proposition p q : 5 < 9 and 9 < 7. The disjunction of the propositions p and q is the proposition p q : 5 < 9 or 9 < 7. Example Consider the following propositions p: It is Friday q: It is raining. Construct the propositions p q and p q. 10 FUNDAMENTALS OF MATHEMATICAL LOGIC. Solution. The conjunction of the propositions p and q is the proposition p q : It is Friday and it is raining. The disjunction of the propositions p and q is the proposition p q : It is Friday or It is raining A truth table displays the relationships between the truth values of propo- sitions.

8 Next, we display the truth tables of p q and p q. p q p q p q p q T T T T T T. T F F T F T. F T F F T T. F F F F F F. Let p and q be two propositions. The exclusive or of p and q, denoted p q, is the proposition that is true when exactly one of p and q is true and is false otherwise. The truth table of the exclusive or' is displayed below p q p q T T F. T F T. F T T. F F F. Example a. Construct a truth table for (p q) r. b. Construct a truth table for p p. Solution. a. p q r p q (p q) r T T T F T. T T F F F. T F T T F. T F F T T. F T T T F. F T F T T. F F T F T. F F F F F. 1 PROPOSITIONS AND RELATED CONCEPTS 11. b. p p p T F. F F. The final operation on a proposition p that we discuss is the negation of p. The negation of p, denoted p, is the proposition not p.

9 The truth table of p is displayed below p p T F. F T. Example Consider the following propositions: p: Today is Thursday. q: 2 + 1 = 3. r: There is no pollution in New Jersey. Construct the truth table of [ (p q)] r. Solution. p q r p q (p q) [ (p q)] r T T T T F T. T T F T F F. T F T F T T. T F F F T T. F T T F T T. F T F F T T. F F T F T T. F F F F T T. Example Find the negation of the proposition p : 5 < x 0. Solution. The negation of p is the proposition p : x > 0 or x 5. A compound proposition is called a tautology if it is always true, regardless of the truth values of the basic propositions which comprise it. 12 FUNDAMENTALS OF MATHEMATICAL LOGIC. Example a. Construct the truth table of the proposition (p q) ( p q). Determine if this proposition is a tautology.

10 B. Show that p p is a tautology. Solution. a. p q p q p q p q (p q) ( p q). T T F F F T T. T F F T T F T. F T T F T F T. F F T T T F T. Thus, the given proposition is a tautology. b. p p p p T F T. F T T. Again, this proposition is a tautology Two propositions are equivalent if they have exactly the same truth values under all circumstances. We write p q. Example a. Show that (p q) p q. b. Show that (p q) p q. c. Show that ( p) p. a. and b. are known as DeMorgan's laws. Solution. a. p q p q p q (p q) p q T T F F T F F. T F F T T F F. F T T F T F F. F F T T F T T. 1 PROPOSITIONS AND RELATED CONCEPTS 13. b. p q p q p q (p q) p q T T F F T F F. T F F T F T T. F T T F F T T. F F T T F T T. c. p p ( p). T F T. F T F. Example a. Show that p q q p and p q q p. b.