WIXLIB

Lecture Notes in Discrete MathematicsMarcel B. FinanArkansas Tech Universityc All Rights Reserved

2

PrefaceThis book is designed for a one semester course in discrete mathematicsfor sophomore or junior level students. The text covers the mathematicalconcepts that students will encounter in many disciplines such as computerscience, engineering, Business, and the sciences.Besides reading the book, students are strongly encouraged to do all the exercises. Mathematics is a discipline in which working the problems is essentialto the understanding of the material contained in this book. Students arestrongly encouraged to keep up with the exercises and the sequel of conceptsas they are going along, for mathematics builds on itself.Instructors can request the solutions to the problems via email: mfinan@atu.eduFinally, I would like to take the opportunity to thank Professor Vadim Ponomarenko from San Diego State University for pointing out to me many errorsin the book and for his valuable suggestions.Marcel B. FinanMay 20013

4PREFACE

ContentsPreface3Fundamentals of Mathematical Logic1 Propositions and Related Concepts . . . . .2 Conditional and Biconditional Propositions3 Rules of Inferential Logic . . . . . . . . . . .4 Propositions and Quantifiers . . . . . . . . .5 Arguments with Quantified Premises . . . .6 Project I: Digital Logic Design . . . . . . .7 Project II: Number Systems . . . . . . . . .Fundamentals of Mathematical Proofs8 Methods of Direct Proof I . . . . . . . . . . . . . . . . . . . . . .9 More Methods of Proof . . . . . . . . . . . . . . . . . . . . . . .10 Methods of Indirect Proofs: Contradiction and Contraposition .11 Method of Proof by Induction . . . . . . . . . . . . . . . . . . .12 Project III: Elementary Number Theory and Mathematical Proofs13 Project IV: The Euclidean Algorithm . . . . . . . . . . . . . . .14 Project V: Induction and the Algebra of Matrices . . . . . . . .781824334145505353596467757779Fundamentals of Set Theory8315 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 8316 Properties of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 9217 Project VI: Boolean Algebra . . . . . . . . . . . . . . . . . . . . 100Relations and Functions10118 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . 10119 Partial Order Relations . . . . . . . . . . . . . . . . . . . . . . . 1135

6CONTENTS2021222324252627Functions: Definitions and Examples . . . .Bijective and Inverse Functions . . . . . . . .Recursion . . . . . . . . . . . . . . . . . . .Project VII: Applications to Relations . . . .Project VIII: Well-Ordered Sets and LatticesProject IX: The Pigeonhole Principle . . . .Project X: Countable Sets . . . . . . . . . .Project XI: Finite-State Automaton . . . . .119127133149152153154156Introduction to the Analysis of Algorithms15928 Time Complexity and O-Notation . . . . . . . . . . . . . . . . . 15929 Logarithmic and Exponential Complexities . . . . . . . . . . . . 16730 Θ- and Ω-Notations . . . . . . . . . . . . . . . . . . . . . . . . . 171Fundamentals of Counting and Probability Theory31 Elements of Counting . . . . . . . . . . . . . . . . . . . . . . .32 Basic Probability Terms and Rules . . . . . . . . . . . . . . . .33 Binomial Random Variables . . . . . . . . . . . . . . . . . . .175. 175. 182. 194Elements of Graph Theory20134 Graphs, Paths, and Circuits . . . . . . . . . . . . . . . . . . . . 20135 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

Fundamentals of MathematicalLogicLogic is commonly known as the science of reasoning. The emphasis herewill be on logic as a working tool. We will develop some of the symbolictechniques required for computer logic. Some of the reasons to study logicare the following: At the hardware level the design of ’logic’ circuits to implement instructions is greatly simplified by the use of symbolic logic. At the software level a knowledge of symbolic logic is helpful in thedesign of programs.7

8FUNDAMENTALS OF MATHEMATICAL LOGIC1 Propositions and Related ConceptsA proposition is any meaningful statement that is either true or false, butnot both. We will use lowercase letters, such as p, q, r, · · · , to representpropositions. We will also use the notationp:1 1 3to define p to be the proposition 1 1 3. The truth value of a propositionis true, denoted by T, if it is a true statement and false, denoted by F, if itis a false statement. Statements that are not propositions include questionsand commands.Example 1.1Which of the following are propositions? Give the truth value of the propositions.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 propositionExample 1.2Which of the following are propositions? Give the truth value of the propositions.a. The difference 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 CONCEPTS9d. Not a propositionNew propositions called compound propositions or propositional functions can be obtained from old ones by using symbolic connectives whichwe discuss next. The propositions that form a propositional function arecalled the propositional variables.Let p and q be propositions. The conjunction of p and q, denoted p q, isthe proposition: p and q. This proposition is defined to be true only whenboth p and q are true and it is false otherwise. The disjunction of p andq, denoted p q, is the proposition: p or q. The ’or’ is used in an inclusiveway. This proposition is false only when both p and q are false, otherwise itis true.Example 1.3Letp: 5 9q : 9 7.Construct the propositions p q and p q.Solution.The conjunction of the propositions p and q is the propositionp q : 5 9 and 9 7.The disjunction of the propositions p and q is the propositionp q : 5 9 or 9 7Example 1.4Consider the following propositionsp:q:It is FridayIt is raining.Construct the propositions p q and p q.

10FUNDAMENTALS OF MATHEMATICAL LOGICSolution.The conjunction of the propositions p and q is the propositionp q : It is Friday and it is raining.The disjunction of the propositions p and q is the propositionp q : It is Friday or It is rainingA truth table displays the relationships between the truth values of propositions. Next, we display the truth tables of p q and p q.pTTFFqTFTFp qTFFFpTTFFqTFTFp qTTTFLet 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 falseotherwise. The truth table of the exclusive ‘or’ is displayed belowpTTFFqTFTFp qFTTFExample 1.5a. Construct a truth table for (p q) r.b. Construct a truth table for p p.Solution.a.pTTTTFFFFqTTFFTTFFrTFTFTFTFp qFFTTTTFF(p q) rTFFTFTTF

1 PROPOSITIONS AND RELATED CONCEPTS11b.p p pT FF FThe 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. The truth table of p is displayed belowp pT FF TExample 1.6Consider 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.pTTTTFFFFqTTFFTTFFrTFTFTFTFp qTTFFFFFF (p q)FFTTTTTT[ (p q)] rTFTTTTTTExample 1.7Find the negation of the proposition p : 5 x 0.Solution.The negation of p is the proposition p : x 0 or x 5A compound proposition is called a tautology if it is always true, regardlessof the truth values of the basic propositions which comprise it.

12FUNDAMENTALS OF MATHEMATICAL LOGICExample 1.8a. Construct the truth table of the proposition (p q) ( p q). Determineif this proposition is a tautology.b. Show that p p is a tautology.Solution.a.pTTFF pFFTTqTFTF qFTFT p qFTTTp qTFFF(p q) ( p q)TTTTThus, the given proposition is a tautology.b.p pT FF Tp pTTAgain, this proposition is a tautologyTwo propositions are equivalent if they have exactly the same truth valuesunder all circumstances. We write p q.Example 1.9a. 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.pTTFFqTFTF pFFTT qFTFTp qTTTF (p q)FFFT p qFFFT

1 PROPOSITIONS AND RELATED CONCEPTS13b.pTTFFqTFTF pFFTT qFTFTp qTFFF (p q)FTTT p qFTTTc. pFTpTF ( p)TFExample 1.10a. Show that p q q p and p q q p.b. Show that (p q) r p (q r) and (p q) r p (q r).c. Show that (p q) r (p r) (q r) and (p q) r (p r) (q r).Solution.a.pTTFFqTFTFp qTFFFq pTFFFpTTFFqTFTFp qTTTFq pTTTFb.pTTTTFFFFqTTFFTTFFrTFTFTFTFp qTTTTTTFFq rTTTFTTTF(p q) rTTTTTTTFp (q r)TTTTTTTF

14FUNDAMENTALS OF MATHEMATICAL LOGICpTTTTFFFFqTTFFTTFFrTFTFTFTFp qTTFFFFFFq rTFFFTFFF(p q) rTFFFFFFFp (q r)TFFFFFFFc.pTTTTFFFFp TFTFp qTTTTTTFFp rTTTTTFTFp rTFTFFFFFq rTTTFTTTFq rTFFFTFFF(p q) rTTTFTFTF(p q) rTFTFTFFFExample 1.11Show that (p q) 6 p qSolution.We will use truth tables to prove the claim.(p r) (q r)TTTFTFTF(p r) (q r)TFTFTFFF

1 PROPOSITIONS AND RELATED CONCEPTSpTTFFqTFTF pFFTT qFTFTp qTFFF (p q)FT6 T6 T15 p qFFFTA compound proposition that has the value F for all possible values of thepropositions in it is called a contradiction.Example 1.12Show that the proposition p p is a contradiction.Solution.pTF pFTp pFFIn propositional functions, the order of operations is that is performedfirst. The operations and are executed in any order.

16FUNDAMENTALS OF MATHEMATICAL LOGICReview ProblemsProblem 1.1Indicate 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.c. 128 26d. x 26 .Problem 1.2Consider 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 majorbut not a computer science major.”Problem 1.3In the following sentence is the word “or” used in its inclusive or exclusivesense? “A team wins the playoffs if it wins two games in a row or a total ofthree games.”Problem 1.4Write the truth table for the proposition: (p ( p q)) (q r).Problem 1.5Let t be a tautology. Show that p t t.Problem 1.6Let c be a contradiction. Show that p c p.Problem 1.7Show that (r p) [( r (p q)) (r q)] p q.Problem 1.8Use De Morgan’s laws to write the negation for the proposition: “This computer program has a logical error in the first ten lines or it is being run withan incomplete data set.”

1 PROPOSITIONS AND RELATED CONCEPTS17Problem 1.9Use De Morgan’s laws to write the negation for the proposition: “The dollaris at an all-time high and the stock market is at a record low.”Problem 1.10Assume x IR. Use De Morgan’s laws to write the negation for the proposition:0 x 5.Problem 1.11Show that the proposition s (p q) ( p (p q)) is a tautology.Problem 1.12Show that the proposition s (p q) ( p q) is a contradiction.Problem 1.13a. Find simpler proposition forms that are logically equivalent to p p andp (p p).b. Is (p q) r p (q r)? Justify your answer.c. Is (p q) r (p r) (q r)? Justify your answer.Problem 1.14Show the following:a. p t p, where t is a tautology.b. p c c, where c is a contradiction.c. t c and c t.d. p p p and p p p.