Unformatted text preview:

Notes onDiscrete MathematicsMiguel A. LermaContentsIntroduction 5Chapter 1. Logic 61.1. Propositions 61.2. Quantifiers 101.3. Proofs 131.4.Mathematical Induction 18Chapter 2. The Language of Mathematics 212.1. Set Theory 212.2. Sequences and Strings 292.3. Relations 322.4. Functions 38Chapter 3. Algorithms 433.1. Algorithms 433.2. The Euclidean Algorithm 533.3. Modular Arithmetic, RSA Algorithm57Chapter 4. Counting 634.1. Basic Principles 634.2. Combinatorics 654.3. Generalized Permutations and Combinations 674.4. Binomial Coefficients 694.5. The Pigeonhole Principle714.6. Probability 72Chapter 5. Recurrence Relations 765.1.Recurrence Relations 76Chapter 6. Graph Theory 806.1. Graphs 806.2. Paths and Cycles 856.3. Representations of Graphs 916.4. Planar Graphs 943CONTENTS 4Chapter 7. Trees 977.1. Trees 977.2.Spanning Trees 1027.3. Binary Trees 1087.4. Decision Trees, Tree Isomorphisms 112Chapter 8. Boolean Algebras 1188.1. Combinatorial Circuits 1188.2. Boolean Functions, Applications 123Chapter 9. Automata, Grammars and Languages 1289.1. FiniteState Machines 1289.2. Languages and Grammars 1329.3. RegularLanguages 139Appendix A. 145A.1. Efficient Computation of Powers Modulo m 145A.2. Machinesand Languages 147IntroductionThese notes are intended to be a summary of the main ideas incourse CS 310: Mathematical Foundations of Computer Science. Imay keepworking on this document as the course goes on, so thesenotes will not be completely finished until the end of the quarter.The textbookfor this course is Richard Johnsonbaugh:Discrete Math-ematics, Fifth Edition, 2001, Prentice Hall. With few exceptions I willfollow the notation in the book.These notes contain some questions and “exercises” intended tostimulate the reader who wants to play a somehow active role whilestudying the subject. They are not homework nor need to be addressedat all if the reader does not wish to. I will recommend exercises andgive homework assignments separately.Finally, if you find any typos or errors, or you have any suggestions,please, do not hesitate to tell me.Miguel A. [email protected] UniversityWinter 20045CHAPTER 1Logic1.1. PropositionsA proposition is a declarative sentence that is either true or false(but not both). For instance, the following are propositions: “Parisis in France” (true), “London is in Denmark” (false), “2 < 4” (true),“4 = 7 (false)”. However the following are not propositions: “whatis your name?” (this is a question), “do your homework” (this is acommand), “this sentence is false” (neithertrue nor false), “x is aneven number” (it depends on what x represents), “Socrates” (it is noteven a sentence). The truth or falsehood of a proposition is called itstruth value.1.1.1. Connectives, Truth Tables. Connectives are used formaking compound propositions. The main ones are the following (pand q represent given propositions):Name Represented MeaningNegation p “not p”Conjunction p ∧ q “p and q”Disjunction p ∨ q “p or q (or both)”Exclusive Or p Y q “either p or q, but not both”Implication p → q “if p then q”Biconditional p ↔ q “p if and only if q”The truth value of a compound proposition depends only on thevalue of its components. Writing F for “false” and T for “true”, wecan summarize the meaning of the connectives in thefollowing way:61.1. PROPOSITIONS 7p q p p ∧ q p ∨ q p Y q p → q p ↔ qT T F T T F T TT F F F T T F FF T T F T T T FF F T F F F T TNote that ∨ represents a non-exclusive or, i.e., p ∨ q is true whenany of p, qis true and also when both are true. On the other hand Yrepresents an exclusive or, i.e., p Y q is true only when exactly one of pand qis true.1.1.2. Conditional Propositions. A proposition of the form “ifp then q” or “p implies q”, represented “p → q” is called a conditionalproposition. For instance: “if Johnis from Chicago then John is fromIllinois”. The proposition p is called hypothesis or antecedent, and theproposition q is the conclusion or consequent.Note that p → q is true always except when p is true and q is false.So, the following sentences are true: “if 2 < 4 then Paris is in France”(true → true),“if London is in Denmark then 2 < 4” (false → true),“if 4 = 7 then London is in Denmark” (false → false). However thefollowing one is false: “if 2 < 4 then London is in Denmark” (true →false).In might seem strange that “p →q” is considered true when p isfalse, regardless of the truth value of q. This will become clearer whenwe study predicates such as “if x is a multiple of 4 then x is a multipleof 2”. That implication is obviously true, although for the particularcase x = 3 it becomes “if 3 is a multiple of 4 then 3 is a multiple of 2”.The proposition p ↔q, read “p if and only if q”, is called bicon-ditional. It is true precisely whenp and q have the same truth value,i.e., they are both true or both false.1.1.3. Logical Equivalence. Note that the compound proposi-tions p → q and p ∨ q have the same truth values:p q p p ∨ q p → qT T F T TT F F F FF T T T TF F T T T1.1. PROPOSITIONS 8When two compound propositions have the same truth values nomatter what truth value their constituent propositions have, they arecalled logically equivalent. For instance p → q and p ∨ q are logicallyequivalent, and we write it:p → q ≡ p ∨qExample: De Morgan’s Laws for Logic. The following propositionsare logically equivalent:p ∨ q ≡ p ∧ qp ∧ q ≡ p ∨ qWe can check it by examining their truth tables:p q p q p ∨ q p ∨q p ∧q p ∧q p ∧q p ∨qT T F F T F F T F FT F F T T F F F T TF T T F T F F F T TF F T T F T T F T TExample: The following propositions are logically equivalent:p ↔ q ≡ (p → q) ∧ (q → p)Again, this can bechecked with the truth tables:p q p → q q → p (p → q) ∧ (q → p) p ↔ qT T T T T TT F F T F FF T T F F FF F T T T TExercise: Check the following logical equivalences:p → q ≡ p ∧qp → q ≡ q → pp ↔ q ≡ p Y q1.1.4. Converse, Contrapositive. The converse of a conditionalproposition p → q is the proposition q → p. As we have seen, the bi-conditional proposition is equivalent to the conjunction of a conditional1.1. PROPOSITIONS 9proposition an its converse.p ↔ q ≡ (p → q) ∧ (q → p)So, for instance, saying that “John is married if and only if he has aspouse” is the same as saying “if John is married then he


View Full Document

NU EECS 310 - Notes on Discrete Mathematics

Download Notes on Discrete Mathematics
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Notes on Discrete Mathematics and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Notes on Discrete Mathematics 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?