Lecture Notes in Discrete Mathematics

1 Lecture Notes in Discrete MathematicsMarcel B. FinanArkansas Tech Universityc All Rights Reserved2 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 reading the book, students are strongly encouraged to do all the exer-cises. 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 can request the solutions to the problems via email: I would like to take the opportunity to thank Professor Vadim Pono-marenko from San Diego State University for pointing out to me many errorsin the book and for his valuable B.

2 FinanMay 200134 PREFACEC ontentsPreface3 Fundamentals of Mathematical Logic71 Propositions and Related Concepts ..82 Conditional and Biconditional Propositions .. 183 Rules of Inferential Logic .. 244 Propositions and Quantifiers .. 335 Arguments with Quantified Premises .. 416 Project I: Digital Logic Design .. 457 Project II: Number Systems .. 50 Fundamentals of Mathematical Proofs538 Methods of Direct Proof I .. 539 More Methods of Proof .. 5910 Methods of Indirect Proofs: Contradiction and Contraposition . 6411 Method of Proof by Induction .. 6712 Project III: Elementary Number Theory and Mathematical Proofs 7513 Project IV: The Euclidean Algorithm .. 7714 Project V: Induction and the Algebra of Matrices.

3 79 Fundamentals of Set Theory8315 Basic Definitions .. 8316 Properties of Sets .. 9217 Project VI: Boolean Algebra .. 100 Relations and Functions10118 Equivalence Relations .. 10119 Partial Order Relations .. 11356 CONTENTS20 Functions: Definitions and Examples .. 11921 Bijective and Inverse Functions .. 12722 Recursion .. 13323 Project VII: Applications to Relations .. 14924 Project VIII: Well-Ordered Sets and Lattices .. 15225 Project IX: The Pigeonhole Principle .. 15326 Project X: Countable Sets .. 15427 Project XI: Finite-State Automaton .. 156 Introduction to the Analysis of Algorithms15928 Time Complexity andO-Notation .. 15929 Logarithmic and Exponential Complexities .. 16730 - and -Notations.

4 171 Fundamentals of Counting and Probability Theory17531 Elements of Counting .. 17532 Basic Probability Terms and Rules .. 18233 Binomial Random Variables .. 194 Elements 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 in-structions is greatly simplified by the use of symbolic logic. At the software level a knowledge of symbolic logic is helpful in thedesign of OF MATHEMATICAL LOGIC1 Propositions and Related ConceptsApropositionis any meaningful statement that is either true or false, butnot both.

5 We will use lowercase letters, such asp,q,r, ,to representpropositions. We will also use the notationp: 1 + 1 = 3to definepto be the proposition 1 + 1 = valueof 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 of the following are propositions? Give the truth value of the 2 + 3 = Julius Caesar was president of the United What time is it?d. Be quiet ! 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 Not a propositionExample of the following are propositions? Give the truth value of the The difference of two 2 + 2 = Washington is the capital of New How are you?

6 Not a A proposition with truth value (T).c. A proposition with truth value (F).1 PROPOSITIONS AND RELATED CONCEPTS9d. Not a propositionNew propositions calledcompound propositionsorpropositional func-tionscan be obtained from old ones by usingsymbolic connectiveswhichwe discuss next. The propositions that form a propositional function arecalled thepropositional propositions. Theconjunctionofpandq,denotedp q,isthe proposition:p and proposition is defined to be true only whenbothpandqare true and it is false otherwise. Thedisjunctionofpandq,denotedp q,is the proposition:p or or is used in an inclusiveway. This proposition is false only when bothpandqare false, otherwise itis : 5<9q: 9< the propositionsp qandp conjunction of the propositionspandqis the propositionp q: 5<9 and 9< disjunction of the propositionspandqis the propositionp q: 5<9 or 9<7 Example the following propositionsp:It is Fridayq:It is the propositionsp qandp OF MATHEMATICAL conjunction of the propositionspandqis the propositionp q: It is Friday and it is disjunction of the propositionspandqis the propositionp q: It is Friday or It is rainingAtruth tabledisplays the relationships between the truth values of propo-sitions.

7 Next, we display the truth tables ofp qandp qTTTTFFFTFFFFpqp qTTTTFTFTTFFFL etpandqbe two propositions. Theexclusive orofpandq,denotedp q,is the proposition that is true when exactly one ofpandqis true and is falseotherwise. The truth table of the exclusive or is displayed belowpqp qTTFTFTFTTFFFE xample Construct a truth table for (p q) Construct a truth table forp q(p q) rTTTFTTTFFFTFTTFTFFTTFTTTFFTFTTFFTFTFFFF F1 PROPOSITIONS AND RELATED pTFFFThe final operation on a propositionpthat we discuss is negation ofp,denoted p,is the proposition truth table of pis displayed belowp pTFFTE xample the following propositions:p: Today is : 2 + 1 = : There is no pollution in New the truth table of [ (p q)] q (p q)[ (p q)] rTTTTFTTTFTFFTFTFTTTFFFTTFTTFTTFTFFTTFFT FTTFFFFTTE xample the negation of the propositionp: 5< x negation ofpis the proposition p.

8 X >0or x 5A compound proposition is called atautologyif it is always true, regardlessof the truth values of the basic propositions which comprise OF MATHEMATICAL LOGICE xample Construct the truth table of the proposition (p q) ( p q).Determineif this proposition is a Show thatp pis a p q p qp q(p q) ( p q)TTFFFTTTFFTTFTFTTFTFTFFTTTFTThus, the given proposition is a pp pTFTFTTA gain, this proposition is a tautologyTwo propositions areequivalentif they have exactly the same truth valuesunder all circumstances. We writep Show that (p q) p Show that (p q) p Show that ( p) and b. are known as DeMorgan s p qp q (p q) p qTTFFTFFTFFTTFFFTTFTFFFFTTFTT1 PROPOSITIONS AND RELATED p qp q (p q) p p ( p)TFTFTFE xample Show thatp q q pandp q q Show that (p q) r p (q r) and (p q) r p (q r).

9 C. Show that (p q) r (p r) (q r) and (p q) r (p r) (q r). qq pTTTTTFFFFTFFFFFFpqp qq qq r(p q) rp (q r)TTTTTTTTTFTTTTTFTTTTTTFFTFTTFTTTTTTFTF TTTTFFTFTTTFFFFFFF14 FUNDAMENTALS OF MATHEMATICAL LOGIC pqrp qq r(p q) rp (q r) qp rq r(p q) r(p r) (q r)TTTTTTTTTTFTTTTTTFTFTTTTTFFFTFFFFTTFTT TTFTFFFTFFFFTFTTTTFFFFFFFF pqrp qp rq r(p q) r(p r) (q r)TTTTTTTTTTFTFFFFTFTTTFTTTFFTFFFFFTTTFT TTFTFTFFFFFFTFFFFFFFFFFFFFE xample that (p q)6 p will use truth tables to prove the PROPOSITIONS AND RELATED CONCEPTS15pq p qp q (p q) p qTTFFTFFTFFTFT6=FFTTFFT6=FFFTTFTTA compound proposition that has the value F for all possible values of thepropositions in it is called that the propositionp pis a pp pTFFFTFIn propositional functions, the order of operations is that is performedfirst.

10 The operations and are executed in any OF MATHEMATICAL LOGICR eview ProblemsProblem which of the following sentences are 1,024 is the smallest four-digit number that is perfect She is a Mathematics 128 = the propositions:p: Juan is a math : Juan is a computer science symbolic connectives to represent the proposition Juan is a math majorbut not a computer science major. Problem 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 the truth table for the proposition: (p ( p q)) (q r).Problem a tautology. Show thatp t a contradiction. Show thatp c that (r p) [( r (p q)) (r q)] p De Morgan s laws to write the negation for the proposition: This com-puter program has a logical error in the first ten lines or it is being run withan incomplete data set.