Lecture Notes in Discrete Mathematics

lecture notes discrete mathematics and its applications and discrete mathematics for computer science lecture notes pdf free download
DanialOrton Profile Pic
DanialOrton,Hawaii,Professional
Published Date:09-07-2017
Your Website URL(Optional)
Comment
Lecture Notes in Discrete Mathematics Marcel B. Finan Arkansas Tech University c All Rights Reserved2Preface 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: m nanatu.edu 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. Marcel B. Finan May 2001 34 PREFACEContents 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 Quanti ers . . . . . . . . . . . . . . . . . . . . . 33 5 Arguments with Quanti ed 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 . . . . . . . . 79 Fundamentals of Set Theory 83 15 Basic De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 56 CONTENTS 20 Functions: De nitions 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 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215Fundamentals 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 simpli ed by the use of symbolic logic.  At the software level a knowledge of symbolic logic is helpful in the design of programs. 78 FUNDAMENTALS OF MATHEMATICAL LOGIC 1 Propositions and Related Concepts A proposition is any meaningful statement that is either true or false, but not both. We will use lowercase letters, such as p;q;r; ; to represent propositions. We will also use the notation p : 1 + 1 = 3 to de nep 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 1.1 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 1.2 Which of the following are propositions? Give the truth value of the propo- sitions. a. The di erence of two primes. b. 2 + 2 = 4: c. Washington D.C. 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 pq; is the proposition: p and q: This proposition is de ned to be true only when both p and q are true and it is false otherwise. 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 1.3 Let p : 5 9 q : 9 7: Construct the propositions pq and p_q: Solution. The conjunction of the propositions p and q is the proposition pq : 5 9 and 9 7: The disjunction of the propositions p and q is the proposition p_q : 5 9 or 9 7 Example 1.4 Consider the following propositions p : It is Friday q : It is raining: Construct the propositions pq and p_q:10 FUNDAMENTALS OF MATHEMATICAL LOGIC Solution. The conjunction of the propositions p and q is the proposition pq : 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. Next, we display the truth tables of pq 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 Letp andq be two propositions. The exclusive or ofp andq; denotedpq; is the proposition that is true when exactly one ofp andq is true and is false otherwise. The truth table of the exclusive `or' is displayed below p q pq T T F T F T F T T F F F Example 1.5 a. Construct a truth table for (pq)r: b. Construct a truth table for pp: Solution. a. p q r pq (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 F1 PROPOSITIONS AND RELATED CONCEPTS 11 b. p p p T F F F The nal operation on a proposition p that we discuss is the negation of p: The negation of p; denotedp; is the proposition not p: The truth table of p is displayed below p p T F F T Example 1.6 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  (pq)_r. Solution. p q r pq  (pq)  (pq)_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 1.7 Find the negation of the proposition p :5x 0: Solution. The negation of p is the propositionp :x 0 or x5 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 1.8 a. Construct the truth table of the proposition (pq)_(p_q): Determine if this proposition is a tautology. b. Show that p_p is a tautology. Solution. a. p q p q p_q pq (pq)_ (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 pq: Example 1.9 a. Show that (p_q)pq: b. Show that (pq)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) pq 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 T1 PROPOSITIONS AND RELATED CONCEPTS 13 b. p q p q pq  (pq) 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 1.10 a. Show that pqqp and p_qq_p: b. Show that (p_q)_rp_ (q_r) and (pq)rp (qr): c. Show that (pq)_r (p_r) (q_r) and (p_q)r (pr)_ (qr): Solution. a. p q pq qp T T T T T F F F F T F F F F F F p q p_q q_p T T T T T F T T F T T T F F F F b. p q r p_q q_r (p_q)_r p_ (q_r) T T T T T T T T T F T T T T T F T T T T T T F F T F T T F T T T T T T F T F T T T T F F T F T T T F F F F F F F14 FUNDAMENTALS OF MATHEMATICAL LOGIC p q r pq qr (pq)r p (qr) T T T T T T T T T F T F F F T F T F F F F T F F F F F F F T T F T F F F T F F F F F F F T F F F F F F F F F F F c. p q r pq p_r q_r (pq)_r (p_r) (q_r) T T T T T T T T T T F T T T T T T F T F T T T T T F F F T F F F F T T F T T T T F T F F F T F F F F T F T T T T F F F F F F F F p q r p_q pr qr (p_q)r (pr)_ (qr) T T T T T T T T T T F T F F F F T F T T T F T T T F F T F F F F F T T T F T T T F T F T F F F F F F T F F F F F F F F F F F F F Example 1.11 Show that (pq)6pq Solution. We will use truth tables to prove the claim.1 PROPOSITIONS AND RELATED CONCEPTS 15 p q p q pq  (pq) pq T T F F T F F T F F T F T =6 F F T T F F T =6 F F F T T F T T A compound proposition that has the value F for all possible values of the propositions in it is called a contradiction. Example 1.12 Show that the proposition pp is a contradiction. Solution. p p pp T F F F T F In propositional functions, the order of operations is that is performed rst. The operations_ and are executed in any order.16 FUNDAMENTALS OF MATHEMATICAL LOGIC Review Problems Problem 1.1 Indicate which of the following sentences are propositions. a. 1,024 is the smallest four-digit number that is perfect square. b. She is a mathematics major. 6 c. 128 = 2 6 d. x = 2 : Problem 1.2 Consider the propositions: p: Juan is a math major. q: Juan is a computer science major. Use symbolic connectives to represent the proposition \Juan is a math major but not a computer science major." Problem 1.3 In the following sentence is the word \or" used in its inclusive or exclusive sense? \A team wins the playo s if it wins two games in a row or a total of three games." Problem 1.4 Write the truth table for the proposition: (p_ (p_q)) (qr): Problem 1.5 Let t be a tautology. Show that p_tt: Problem 1.6 Let c be a contradiction. Show that p_cp: Problem 1.7 Show that (r_p) (r_ (pq)) (r_q)pq: Problem 1.8 Use De Morgan's laws to write the negation for the proposition: \This com- puter program has a logical error in the rst ten lines or it is being run with an incomplete data set."1 PROPOSITIONS AND RELATED CONCEPTS 17 Problem 1.9 Use De Morgan's laws to write the negation for the proposition: \The dollar is at an all-time high and the stock market is at a record low." Problem 1.10 Assumex2 IR: Use De Morgan's laws to write the negation for the proposition:0 x5: Problem 1.11 Show that the proposition s = (pq)_ (p_ (pq)) is a tautology. Problem 1.12 Show that the proposition s = (pq) (p_q) is a contradiction. Problem 1.13 a. Find simpler proposition forms that are logically equivalent to pp and p (pp): b. Is (pq)rp (qr)? Justify your answer. c. Is (pq)r (pr) (qr)? Justify your answer. Problem 1.14 Show the following: a. ptp, where t is a tautology. b. pcc, where c is a contradiction. c.tc andct: d. p_pp and ppp:18 FUNDAMENTALS OF MATHEMATICAL LOGIC 2 Conditional and Biconditional Propositions Let p and q be propositions. The implication pq is the proposition that is false only when p is true and q is false; otherwise it is true. p is called the hypothesis andq is called the conclusion. The connective is called the conditional connective. Example 2.1 Construct the truth table of the implication pq: Solution. The truth table is p q pq T T T T F F F T T F F T Example 2.2 Show that pqp_q. Solution. p q p pq p_q T T F T T T F F F F F T T T T F F T T T It follows from the previous example that the proposition p q is always true if the hypothesis p is false, regardless of the truth value of q: We say that pq is true by default or vacuously true. In terms of words the proposition pq also reads: (a) if p then q: (b) p implies q: (c) p is a sucient condition for q: (d) q is a necessary condition for p: (e) p only if q:2 CONDITIONAL AND BICONDITIONAL PROPOSITIONS 19 Example 2.3 Use the if-then form to rewrite the statement \I am on time for work if I catch the 8:05 bus." Solution. If I catch the 8:05 bus then I am on time for work In propositional functions that involve the connectives;;_; and the order of operations is that is performed rst and is performed last. Example 2.4 a. Show that (pq)pq: b. Find the negation of the statement \ If my car is in the repair shop, then I cannot go to class." Solution. a. We use De Morgan's laws as follows.  (pq)   (p_q)   (p)q  pq: b. \My car is in the repair shop and I can get to class." The converse of p q is the proposition q p: The opposite or in- verse of pq is the propositionpq: The contrapositive of pq is the propositionqp: Example 2.5 Find the converse, opposite, and the contrapositive of the implication: \ If today is Thursday, then I have a test today." Solution. The converse: If I have a test today then today is Thursday. The opposite: If today is not Thursday then I don't have a test today. The contrapositive: If I don't have a test today then today is not Thursday Example 2.6 Show that pqqp:20 FUNDAMENTALS OF MATHEMATICAL LOGIC Solution. We use De Morgan's laws as follows. pq  p_q   (pq)   (qp)  q_p  q_p  qp Example 2.7 Using truth tables show the following: a. pq6qp b. pq6pq Solution. a. It suces to show thatp_q6q_p: p q p q p_q q_p T T F F T T T F F T F =6 T F T T F T 6= F F F T T T T b. We will show thatp_q6p_q: p q p q p_q p_q T T F F T T T F F T F 6= T F T T F T 6= F F F T T T T Example 2.8 Show thatqppq Solution. We use De Morgan's laws as follows. qp  q_p   (qp)   (pq)  p_q  p_q  pq