Question? Leave a message!

Lecture Notes on Discrete Mathematics

lecture notes discrete mathematics and its applications and discrete mathematics for computer science lecture notes pdf free download
ShawnPacinocal Profile Pic
ShawnPacinocal,United States,Researcher
Published Date:09-07-2017
Website URL
Notes on Discrete Mathematics Miguel A. LermaContents Introduction 5 Chapter 1. Logic, Proofs 6 1.1. Propositions 6 1.2. Predicates, Quantifiers 11 1.3. Proofs 13 Chapter 2. Sets, Functions, Relations 19 2.1. Set Theory 19 2.2. Functions 27 2.3. Relations 32 Chapter 3. Algorithms, Integers 38 3.1. Algorithms 38 3.2. The Euclidean Algorithm 48 3.3. Modular Arithmetic, RSA Algorithm 52 Chapter 4. Induction, Recurences 59 4.1. Sequences and Strings 59 4.2. Mathematical Induction 62 4.3. Recurrence Relations 65 Chapter 5. Counting 69 5.1. Basic Principles 69 5.2. Combinatorics 71 5.3. Generalized Permutations and Combinations 73 5.4. Binomial Coefficients 75 5.5. The Pigeonhole Principle 77 Chapter 6. Probability 78 6.1. Probability 78 Chapter 7. Graph Theory 82 7.1. Graphs 82 7.2. Representations of Graphs 88 7.3. Paths and Circuits 91 3CONTENTS 4 7.4. Planar Graphs 97 Chapter 8. Trees 100 8.1. Trees 100 8.2. Binary Trees 102 8.3. Decision Trees, Tree Isomorphisms 104 8.4. Tree Transversal 113 8.5. Spanning Trees 116 Chapter 9. Boolean Algebras 122 9.1. Combinatorial Circuits 122 9.2. Boolean Functions, Applications 127 Chapter 10. Automata, Grammars and Languages 133 10.1. Finite State Machines 133 10.2. Languages and Grammars 137 10.3. Language Recognition 144 Appendix A. 150 A.1. Efficient Computation of Powers Modulo m 150 A.2. Machines and Languages 152Introduction These notes are intended to be a summary of the main ideas in course CS 310: Mathematical Foundations of Computer Science. I may keep working on this document as the course goes on, so these notes will not be completely finished until the end of the quarter. The textbook for this course is Keneth H. Rosen: Discrete Mathe- matics and Its Applications, Fifth Edition, 2003, McGraw-Hill. With few exceptions I will follow the notation in the book. These notes contain some questions and “exercises” intended to stimulate the reader who wants to play a somehow active role while studyingthesubject. Theyarenothomeworknorneedtobeaddressed at all if the reader does not wish to. I will recommend exercises and give homework assignments separately. Finally, ifyoufindanytyposorerrors, oryouhaveanysuggestions, please, do not hesitate to let me know. Miguel A. Lerma Northwestern University Spring 2005 5CHAPTER 1 Logic, Proofs 1.1. Propositions A proposition is a declarative sentence that is either true or false (but not both). For instance, the following are propositions: “Paris is in France” (true), “London is in Denmark” (false), “2 4” (true), “4 = 7 (false)”. However the following are not propositions: “what is your name?” (this is a question), “do your homework” (this is a command), “this sentence is false” (neither true nor false), “x is an even number” (it depends on what x represents), “Socrates” (it is not even a sentence). The truth or falsehood of a proposition is called its truth value. 1.1.1. Connectives, Truth Tables. Connectives are used for making compound propositions. The main ones are the following (p and q represent given propositions): Name Represented Meaning Negation ¬p “not p” Conjunction p∧q “p and q” Disjunction p∨q “p or q (or both)” Exclusive Or p⊕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 the value of its components. Writing F for “false” and T for “true”, we can summarize the meaning of the connectives in the following way: 61.1. PROPOSITIONS 7 p q ¬p p∧q p∨q p⊕q p→q p↔q T T F T T F T T T F F F T T F F F T T F T T T F F F T F F F T T Note that ∨ represents a non-exclusive or, i.e., p∨q is true when any of p, q is true and also when both are true. On the other hand ⊕ represents an exclusive or, i.e., p⊕q is true only when exactly one of p and q is true. 1.1.2. Tautology, Contradiction, Contingency. 1. A proposition is said to be a tautology if its truth value is T forany assignment of truth values toits components. Example: The proposition p∨¬p is a tautology. 2. A proposition is said to be a contradiction if its truth value is F forany assignment of truth values toits components. Example: The proposition p∧¬p is a contradiction. 3. A proposition that is neither a tautology nor a contradiction is called a contingency. p ¬p p∨¬p p∧¬p T F T F T F T F F T T F F T T F 6 6 tautology contradiction 1.1.3. Conditional Propositions. A proposition of the form “if p then q” or “p implies q”, represented “p→q” is called a conditional proposition. For instance: “if John is from Chicago then John is from Illinois”. The proposition p is called hypothesis or antecedent, and the proposition 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),1.1. PROPOSITIONS 8 “if 4 = 7 then London is in Denmark” (false → false). However the following 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 is false, regardless of the truth value of q. This will become clearer when we study predicates such as “if x is a multiple of 4 then x is a multiple of 2”. That implication is obviously true, although for the particular case 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 when p and q have the same truth value, i.e., they are both true or both false. 1.1.4. Logical Equivalence. Note that the compound proposi- tions p→q and¬p∨q have the same truth values: p q ¬p ¬p∨q p→q T T F T T T F F F F F T T T T F F T T T When two compound propositions have the same truth values no matter what truth value their constituent propositions have, they are called logically equivalent. For instance p→q and ¬p∨q are logically equivalent, and we write it: p→q ≡ ¬p∨q Note that that two propositions A and B are logically equivalent precisely when A↔B is a tautology. Example: De Morgan’s Laws for Logic. The following propositions are logically equivalent: ¬(p∨q) ≡ ¬p∧¬q ¬(p∧q) ≡ ¬p∨¬q We can check it by examining their truth tables:1.1. PROPOSITIONS 9 p q ¬p ¬q p∨q ¬(p∨q) ¬p∧¬q p∧q ¬(p∧q) ¬p∨¬q T T F F T F F T F F T F F T T F F F T T F T T F T F F F T T F F T T F T T F T T Example: The following propositions are logically equivalent: p↔q ≡ (p→q)∧(q→p) Again, this can be checked with the truth tables: p q p→q q→p (p→q)∧(q→p) p↔q T T T T T T T F F T F F F T T F F F F F T T T T Exercise: Check the following logical equivalences: ¬(p→q) ≡ p∧¬q p→q ≡ ¬q→¬p ¬(p↔q) ≡ p⊕q 1.1.5. Converse,Contrapositive. Theconverse ofaconditional proposition p → q is the proposition q → p. As we have seen, the bi- conditionalpropositionisequivalenttotheconjunctionofaconditional proposition an its converse. p↔q ≡ (p→q)∧(q→p) So, for instance, saying that “John is married if and only if he has a spouse”isthesameassaying“ifJohnismarriedthenhehasaspouse” and “if he has a spouse then he is married”. Note that the converse is not equivalent to the given conditional proposition, for instance “if John is from Chicago then John is from Illinois” is true, but the converse “if John is from Illinois then John is from Chicago” may be false.1.1. PROPOSITIONS 10 The contrapositive of a conditional proposition p→q is the propo- sition ¬q → ¬p. They are logically equivalent. For instance the con- trapositive of “if John is from Chicago then John is from Illinois” is “if John is not from Illinois then John is not from Chicago”.1.2. PREDICATES, QUANTIFIERS 11 1.2. Predicates, Quantifiers 1.2.1. Predicates. Apredicate orpropositionalfunction isastate- ment containing variables. For instance “x+2 = 7”, “X is American”, “xy”, “p is a prime number” are predicates. The truth value of the predicatedependsonthevalueassignedtoitsvariables. Forinstanceif we replacex with 1 in the predicate “x+2 = 7” we obtain “1+2 = 7”, which is false, but if we replace it with 5 we get “5+2 = 7”, which is true. We represent a predicate by a letter followed by the variables enclosedbetweenparenthesis: P(x),Q(x,y), etc. An example forP(x) is a value of x for which P(x) is true. A counterexample is a value of x for which P(x) is false. So, 5 is an example for “x+2 = 7”, while 1 is a counterexample. Each variable in a predicate is assumed to belong to a universe (or domain) of discourse,forinstanceinthepredicate“nisanoddinteger” ’n’ represents an integer, so the universe of discourse of n is the set of all integers. In “X is American” we may assume that X is a human being, so in this case the universe of discourse is the set of all human 1 beings. 1.2.2. Quantifiers. Given a predicate P(x), the statement “for some x, P(x)” (or “there is some x such that p(x)”), represented “∃xP(x)”, has a definite truth value, so it is a proposition in the usual sense. For instance if P(x) is “x+2 = 7” with the integers as universe of discourse, then ∃xP(x) is true, since there is indeed an integer, namely 5, such that P(5) is a true statement. However, if Q(x) is “2x = 7” and the universe of discourse is still the integers, then∃xQ(x) is false. On the other hand,∃xQ(x) would be true if we extend the universe of discourse to the rational numbers. The symbol ∃ is called the existential quantifier. Analogously,thesentence“forallx,P(x)”—also“foranyx,P(x)”, “for every x, P(x)”, “for each x, P(x)”—, represented “∀xP(x)”, has a definite truth value. For instance, if P(x) is “x + 2 = 7” and the 1 Usually all variables occurring in predicates along a reasoning are supposed to belong to the same universe of discourse, but in some situations (as in the so called many-sorted logics) it is possible to use different kinds of variables to represent different types of objects belonging to different universes of discourse. For instance in the predicate “σ is a string of length n” the variable σ represents a string, while n represents a natural number, so the universe of discourse of σ is the set of all strings, while the universe of discourse of n is the set of natural numbers.1.2. PREDICATES, QUANTIFIERS 12 universe of discourse is the integers, then ∀xP(x) is false. However if 2 2 Q(x) represents “(x+1) = x +2x+1” then ∀xQ(x) is true. The symbol∀ is called the universal quantifier. Inpredicateswithmorethanonevariableitispossibletouseseveral quantifiers at the same time, for instance ∀x∀y∃zP(x,y,z), meaning “for all x and all y there is some z such that P(x,y,z)”. Notethatingeneraltheexistentialanduniversalquantifierscannot be swapped, i.e., in general ∀x∃yP(x,y) means something different from∃y∀xP(x,y). Forinstanceifxandy representhumanbeingsand P(x,y) represents “x is a friend of y”, then ∀x∃yP(x,y) means that everybody is a friend of someone, but ∃y∀xP(x,y) means that there is someone such that everybody is his or her friend. A predicate can be partially quantified, e.g. ∀x∃yP(x,y,z,t). The variablesquantified(xandyintheexample)arecalledbound variables, and the rest (z and t in the example) are called free variables. A partially quantified predicate is still a predicate, but depending on fewer variables. 1.2.3. Generalized De Morgan Laws for Logic. If∃xP(x) is false then there is no value of x for which P(x) is true, or in other words, P(x) is always false. Hence ¬∃xP(x) ≡ ∀x¬P(x). On the other hand, if ∀xP(x) is false then it is not true that for every x, P(x) holds, hence for some x, P(x) must be false. Thus: ¬∀xP(x) ≡ ∃x¬P(x). Thistworulescanbeappliedinsuccessivestepstofindthenegation of a more complex quantified statement, for instance: ¬∃x∀yp(x,y) ≡ ∀x¬∀yP(x,y) ≡ ∀x∃y¬P(x,y). Exercise:Writeformallythestatement“foreveryrealnumberthere is a greater real number”. Write the negation of that statement. Answer: The statement is: ∀x∃y(xy) (the universe of discourse istherealnumbers). Itsnegationis: ∃x∀y¬(xy),i.e.,∃x∀y(x 6 y). (Note that among real numbers x 6 y is equivalent to x ≥ y, but formally they are different predicates.)1.3. PROOFS 13 1.3. Proofs 1.3.1. Mathematical Systems, Proofs. A Mathematical Sys- tem consists of: 1. Axioms: propositions that are assumed true. 2. Definitions: used to create new concepts from old ones. 3. Undefinedterms: correspondingtotheprimitiveconceptsofthe system (for instance in set theory the term “set” is undefined). A theorem is a proposition that can be proved to be true. An argument that establishes the truth of a proposition is called a proof. Example: Prove that if x 2 and y 3 then x+y 5. Answer: Assuming x 2 and y 3 and adding the inequalities term by term we get: x+y 2+3 = 5. That is an example of direct proof. In a direct proof we assume the hypothesis together with axioms and other theorems previously proved and we derive the conclusion from them. An indirect proof or proof by contrapositive consists of proving the contrapositive of the desired implication, i.e., instead of proving p→q we prove ¬q→¬p. Example: Prove that if x+y 5 then x 2 or y 3. Answer: We must prove that x+y 5 → (x 2)∨(y 3). An indirectproofconsistsofproving¬((x 2)∨(y 3))→¬(x+y 5). Infact: ¬((x 2)∨(y 3))isthesameas(x≤ 2)∧(y≤ 3),soadding both inequalities we get x+y≤ 5, which is the same as¬(x+y 5). Proof by Contradiction. In a proof by contradiction or (Reductio ad Absurdum) we assume the hypotheses and the negation of the conclu- sion, and try to derive a contradiction, i.e., a proposition of the form r∧¬r. Example: Prove by contradiction that ifx+y 5 then eitherx 2 or y 3. Answer: We assume the hypothesis x+y 5. From here we must conclude that x 2 or y 3. Assume to the contrary that “x 2 or y 3” is false, so x≤ 2 and y ≤ 3. Adding those inequalities we get1.3. PROOFS 14 x≤ 2+3 = 5, which contradicts the hypothesis x+y 5. From here we conclude that the assumption “x≤ 2 and y ≤ 3” cannot be right, so “x 2 or y 3” must be true. Remark:Sometimesitisdifficulttodistinguishbetweenanindirect proof and a proof by contradiction. In an indirect proof we prove an implication of the form p → q by proving the contrapositive ¬q → ¬p. In an proof by contradiction we prove an statement s (which may or may not be an implication) by assuming ¬s and deriving a contradiction. In fact proofs by contradiction are more general than indirect proofs. √ Exercise: Prove by contradiction that 2 is not a rational number, √ i.e., there are no integers a,b such that 2 =a/b. √ √ Answer: Assume that 2 is rational, i.e., 2 =a/b, where a and b are integers and the fraction is written in least terms. Squaring both 2 2 2 2 sides we have 2 = a /b , hence 2b = a . Since the left hand side is 2 0 even, then a is even, but this implies that a itself is even, so a = 2a. 2 2 2 0 2 0 2 Hence: 2b = 4a , and simplifying: b = 2a . This implies that b 0 0 0 0 0 is even, so b is even: b = 2b. Consequently a/b = 2a/2b = a/b, contradicting the hypothesis that a/b was in least terms. 1.3.2. Arguments, Rules of Inference. An argument is a se- quence of propositions p ,p ,...,p called hypotheses (or premises) 1 2 n followed by a proposition q called conclusion. An argument is usually written: p 1 p 2 . . . p n ∴ q or p ,p ,...,p /∴ q 1 2 n The argument is called valid if q is true whenever p ,p ,...,p are 1 2 n true; otherwise it is called invalid.1.3. PROOFS 15 Rules of inference are certain simple arguments known to be valid and used to make a proof step by step. For instance the following argument is called modus ponens or rule of detachment: p→q p ∴ q In order to check whether it is valid we must examine the following truth table: p q p→q p q T T T T T T F F T F F T T F T F F T F F If we look now at the rows inwhichbothp→q andp are true(just the first row) we see that also q is true, so the argument is valid. Other rules of inference are the following: 1. Modus Ponens or Rule of Detachment: p→q p ∴ q 2. Modus Tollens: p→q ¬q ∴ ¬p 3. Addition: p ∴ p∨q 4. Simplification: p∧q ∴ p 5. Conjunction:1.3. PROOFS 16 p q ∴ p∧q 6. Hypothetical Syllogism: p→q q→r ∴ p→r 7. Disjunctive Syllogism: p∨q ¬p ∴ q 8. Resolution: p∨q ¬p∨r ∴ q∨r Arguments are usually written using three columns. Each row con- tains a label, a statement and the reason that justifies the introduction of that statement in the argument. That justification can be one of the following: 1. The statement is a premise. 2. Thestatementcanbederivedfromstatementsoccurringearlier in the argument by using a rule of inference. Example: Consider the following statements: “I take the bus or I walk. If I walk I get tired. I do not get tired. Therefore I take the bus.” We can formalize this by calling B = “I take the bus”, W = “I walk” and T = “I get tired”. The premises are B∨W, W →T and ¬T, and the conclusion is B. The argument can be described in the following steps: step statement reason 1) W →T Premise 2) ¬T Premise 3) ¬W 1,2, Modus Tollens 4) B∨W Premise 5) ∴B 4,3, Disjunctive Syllogism1.3. PROOFS 17 1.3.3. Rules of Inference for Quantified Statements. We state the rules for predicates with one variable, but they can be gener- alized to predicates with two or more variables. 1. Universal Instantiation. If∀xp(x) is true, then p(a) is true for each specific element a in the universe of discourse; i.e.: ∀xp(x) ∴ p(a) Forinstance,from∀x(x+1 = 1+x)wecanderive7+1 = 1+7. 2. Existential Instantiation. If∃xp(x)istrue, thenp(a)istruefor some specific element a in the universe of discourse; i.e.: ∃xp(x) ∴ p(a) The difference respect to the previous rule is the restriction in themeaningofa, whichnowrepresentssome(notany)element 2 of the universe of discourse. So, for instance, from ∃x(x = 2) (the universe of discourse is the real numbers) we derive the √ existence of some element, which we may represent ± 2, such √ 2 that (± 2) = 2. 3. Universal Generalization. If p(x) is proved to be true for a generic element in the universe of discourse, then ∀xp(x) is true; i.e.: p(x) ∴ ∀xp(x) By“generic”wemeananelementforwhichwedonotmakeany assumptionotherthanitsbelongingtotheuniverseofdiscourse. 2 2 So, for instance, we can prove ∀x(x+1) =x +2x+1 (say, for real numbers) by assuming that x is a generic real number 2 2 and using algebra to prove (x+1) =x +2x+1. 4. Existential Generalization. If p(a) is true for some specific ele- ment a in the universe of discourse, then ∃xp(x) is true; i.e.: p(a) ∴ ∃xp(x) For instance: from 7+1 = 8 we can derive ∃x(x+1 = 8). Example: Show that a counterexample can be used to disprove a universal statement, i.e., ifa is an element in the universe of discourse,1.3. PROOFS 18 then from ¬p(a) we can derive¬∀xp(x). Answer: The argument is as follows: step statement reason 1) ¬p(a) Premise 2) ∃x¬p(x) Existential Generalization 3) ¬∀xp(x) Negation of Universal StatementCHAPTER 2 Sets, Functions, Relations 2.1. Set Theory 2.1.1. Sets. A set is a collection of objects, called elements of the set. A set can be represented by listing its elements between braces: A =1,2,3,4,5. The symbol ∈ is used to express that an element is (or belongs to) a set, for instance 3∈A. Its negation is represented by 6∈, e.g. 76∈A. If the set is finite, its number of elements is represented A, e.g. if A =1,2,3,4,5 then A = 5. Some important sets are the following: 1 1. N =0,1,2,3,··· = the set of natural numbers. 2. Z =··· ,−3,−2,−1,0,1,2,3,··· = the set of integers. 3. Q = the set of rational numbers. 4. R = the set of real numbers. 5. C = the set of complex numbers. 2 Is S is one of those sets then we also use the following notations: + 1. S = set of positive elements in S, for instance + Z =1,2,3,··· = the set of positive integers. − 2. S = set of negative elements in S, for instance − Z =−1,−2,−3,··· = the set of negative integers. ∗ ∗ 3. S = set of elements in S excluding zero, for instanceR = the set of non zero real numbers. Set-builder notation. An alternative way to define a set, called set- builder notation, is by stating a property (predicate) P(x) verified by exactly its elements, for instance A = x ∈Z 1 ≤ x ≤ 5 = “set of 1 Note thatN includes zero—for some authorsN =1,2,3,···, without zero. 2 When working with strings we will use a similar notation with a different meaning—be careful not to confuse it. 192.1. SET THEORY 20 integers x such that 1 ≤ x ≤ 5”—i.e.: A = 1,2,3,4,5. In general: A =x∈U p(x), where U is the universe of discourse in which the predicate P(x) must be interpreted, or A =xP(x) if the universe of discourse for P(x) is implicitly understood. In set theory the term universal set isoftenusedinplaceof“universeofdiscourse”foragiven 3 predicate. Principle of Extension. Two sets are equal if and only if they have the same elements, i.e.: A =B ≡ ∀x(x∈A↔x∈B). Subset. We say that A is a subset of set B, or A is contained in B, and we represent it “A⊆ B”, if all elements of A are in B, e.g., if A =a,b,c and B =a,b,c,d,e then A⊆B. A is a proper subset of B, represented “A ⊂ B”, if A ⊆ B but A = 6 B, i.e., there is some element in B which is not in A. Empty Set. A set with no elements is called empty set (or null set, or void set), and is represented by ∅ or. Note that nothing prevents a set from possibly being an element of another set (which is not the same as being a subset). For instance if A = 1,a,3,t,1,2,3 and B = 3,t, then obviously B is an element of A, i.e., B ∈A. Power Set. The collection of all subsets of a set A is called the power set of A, and is representedP(A). For instance, if A =1,2,3, then P(A) =∅,1,2,3,1,2,1,3,2,3,A. n Exercise: Prove by induction that if A =n then P(A) = 2 . Multisets. Two ordinary sets are identical if they have the same elements, so for instance, a,a,b and a,b are the same set because they have exactly the same elements, namely a and b. However, in some applications it might be useful to allow repeated elements in a set. In that case we use multisets, which are mathematical entities similar to sets, but with possibly repeated elements. So, as multisets, a,a,b anda,b would be considered different, since in the first one the element a occurs twice and in the second one it occurs only once. 3 Properly speaking, the universe of discourse of set theory is the collection of all sets (which is not a set).