《离散数学英文课件：DM_review》由会员分享，可在线阅读，更多相关《离散数学英文课件：DM_review（163页珍藏版）》请在金锄头文库上搜索。
1、Discrete Mathematics 1Hui GaoDISCRETE MATHEMATICSDr. Hui GMain Building (of Institute): West 304University of Electronic Science and Tech. of ChinaDiscrete Mathematics 2Hui GaoThe CourselTotally 72 (class hours) + 16 (lab hours) lGrading policy:l Attendance & Homework: 10%l Unexpected Quizzes(open-b
2、ook): 10%l Expected Middle Exam(open-book): 10%l Experimental Report: 10%l Final Exam(closed-book): 60%lExam concept: All in Chapter 1-5,8,9,10 Except 3.8,4.5,5.4,8.6Discrete Mathematics 3Hui Gao1.1 Proposition LogicGoals: l To introduce the basic terminology of propositional logic, including logica
3、l connectives; to show how to construct truth tables; l To illustrate the importance of logic with applications, and to motivate the study of logic through logic puzzles and system specifications.Discrete Mathematics 4Hui GaoSome Popular Logical OperatorsFormal NameNickname ParitySymbolNegation oper
4、atorNOTUnaryConjunction operatorANDBinary Disjunction operatorORBinary Exclusive-OR operatorXORBinary Implication operatorIMPLIESBinaryBiconditional operator IFFBinaryDiscrete Mathematics 5Hui GaoBoolean Operations SummarylWe have seen 1 unary operator and 5 binary operators. Their truth tables are
5、below.Discrete Mathematics 6Hui GaoA Simple ExerciseLet p = “It rained last night”, q = “The sprinklers came on last night,” r = “The lawn was wet this morning.”Translate each of the following into English:p = r p = r p q =“It didnt rain last night.”“The lawn was wet this morning, and it didnt rain
6、last night.”“Either the lawn wasnt wet this morning, or it rained last night, or the sprinklers came on last night.”Discrete Mathematics 7Hui GaoExample of the Converse, Inverse, ContrapositiveRaining tomorrow is a sufficient condition for my not going to town.Step 1: Assign propositional variables
7、to component propositionsp: It will rain tomorrowq: I will not go to townStep 2: Symbolize the assertion: p qStep 3: Symbolize the converse: q pStep 4: Convert the symbols back into wordsIf I dont go to town then it will rain tomorrowDiscrete Mathematics 8Hui GaoTranslating English SentencesTo remov
8、e the ambiguity“ You can access the Internet from campus “ You can access the Internet from campus only ifonly if you are a computer science major or you are not a you are a computer science major or you are not a freshman”freshman”Solution: Let Solution: Let a=“You can access the Internet from camp
9、us”a=“You can access the Internet from campus” c=“You are a computer science major” c=“You are a computer science major” f=“You are a freshman” f=“You are a freshman”The sentence can be represented by The sentence can be represented by a a c c f f ImpliesDiscrete Mathematics 9Hui GaoSystem Specifica
10、tionsWhether following specifications are consistent:“ The message is stored in the buffer or is retransmitted”“The message is not stored in the buffer”“If the message is stored in the buffer, then it is retransmitted”Solution: Let p denote “The message is stored in the buffer” q denote “The message
11、 is retransmitted”p p q q p pp p q qThey are consistent when p is false and q is true.Discrete Mathematics 10Hui GaoLogic PuzzlesTwo kinds of inhabitants:Two kinds of inhabitants:Knights:Knights: always tell the truth; always tell the truth; Knaves:Knaves: always lie. always lie.You encounter You en
12、counter 2 2 people people A A and and B B. . A A says:” says:”B is a B is a knightknight”, ”, B B says: “ says: “I and A are of opposite typesI and A are of opposite types”. ”. What are What are A A and and B B? ?SolutionSolution: Let : Let p denote “A is a knight” ;p denote “A is a knight” ;q denot
13、e “B is a knight”q denote “B is a knight” : consistent; X : inconsistent : consistent; X : inconsistentDiscrete Mathematics 11Hui Gao1.2 Propositional EquivalencelGoals: To show how propositional equivalences are established and to introduce the most important such equivalences.Discrete Mathematics
14、12Hui GaoDiscrete Mathematics 13Hui GaoDiscrete Mathematics 14Hui GaoLogical ProofsThere are two basic techniques for proving tautologies and logical equivalences:1)Build a truth table. Verify thatlast column is all TRUE for tautologyrelevant columns equal for equivalence2)Using Equivalence Laws on
15、page *, deriveTRUE starting from supposed tautologyDiscrete Mathematics 15Hui GaoEx. Prove that pq (p q).Proving Equivalence via Truth TablesFTTTTTTTTTFFFFFFFFTTDiscrete Mathematics 16Hui GaoLogical Non-Equivalencep qp qq p(p q) (q p)TTFFTFTFTFTTTTFTTFFTEx. p q and q p are not logically equivalent P
16、rove that.Discrete Mathematics 17Hui GaoTry to find a counter example Ex. Prove that pq (p q).Case 1: Try left side false, right side truelAssume p=F and q=F, then (p q) =F.Case 2: Try right side false, left side truelAssume (p q) F, then (p q) T, then p q T, then p=F and q=F, then pq =F.We have exh
17、austed all possibilities and not found a counterexample. Proving Equivalence via Abbreviated Truth TablesDiscrete Mathematics 18Hui GaoIdempotent LawAssociativity of OrDefinition of implicationUsing Logical EquivalencesRe-arrangingOriginal statementDeMorgans LawDiscrete Mathematics 19Hui Gao1.3 -1.4
18、 Predicate Logic lGoals: lTo introduce predicate logic, especially existential and universal quantification. Moreover, to explain how to translate between English sentences (or mathematical statements) and logical expressions.lTo explain how to work with nested quantifiers and makes clear that the o
19、rder of quantification matters.Discrete Mathematics 20Hui GaoQuantifierslExistential Quantifier“” reads “there exists”lUniversal Quantifier“” reads “for all”lOrder matters: y x R (x,y ) and x y R (x,y ) may not be logically equivalent.Discrete Mathematics 21Hui GaoDeMorgan Identitiesl“Not all true i
20、ff one is false.”lConjunctional version:(p1p2pn) (p1p2pn)lUniversal quantifier version: x P(x ) x P(x )l“Not one is true iff all are false.”lDisjunctional version:(p1p2pn) (p1p2pn)lExistential quantifier version: x P(x ) x P(x )Discrete Mathematics 22Hui GaoLogical EnglishLogical PuzzlesPrecise Engl
21、ish statements can be expressed in terms of logical constructs. In cases of English puzzles, this can be useful for solving.EG: Can there be a man that shaves exactly all the people that dont shave themselves.Let S(x,y) = “x shaves y”. Asking if following statement satisfiable: x y S(y,y ) S(x,y)Not
22、 satisfiable (trying plugging in y = x )1Discrete Mathematics 23Hui Gao1.5 Rules of InferencelGoals: lTo introduce the notion of a valid argument and rules of inference for propositional logic.To explain how to use rules of inference to build correct arguments in propositional calculus.lTo introduce
23、 rules of inference for predicate logic and how to use these rules of inference to build correct arguments in predicate logic. lTo show how rules of inference for propositional calculus and predicate calculus can be combined.Discrete Mathematics 24Hui GaoDiscrete Mathematics 25Hui GaoDiscrete Mathem
24、atics 26Hui GaoAn ExamplelShow that (x) (P(x) Q(x) (x) (Q(x) R(x) (x) (P(x) R(x)StepInference Rule(1)(x) (P(x) Q(x)P(2)P(y) Q(y)US, (1)(3)(x) (Q(x) R(x) P(4)Q(y) R(y)US, (3)(5)P(y) R(y) hypo. Syll. on (2), (4)(6)(x) (P(x) R(x)UG, (5)Discrete Mathematics 27Hui Gao1.6-1.7 Prove methods and StrategyGoa
25、ls: l To introduce the notion of proof and basic methods of proof, including direct proof, proof by contraposition, and proof by contradiction. l To learn important methods of proofs including proof by cases and existence proofs, To introduce key strategies for proving theorems, to understand the ro
26、les of conjectures and counterexamples, and to learn about some important open problems.Discrete Mathematics 28Hui GaoTen proof methods:6. Proof by cases7. Proof by contraposition8. Existence proofs9. Uniqueness proofs10. Counterexamples1. Direct proofs2. Indirect proofs3. Vacuous proofs4. Trivial p
27、roofs5. Proof by contradictionl Two proof strategies: l forward reasoning l backward reasoningDiscrete Mathematics 29Hui GaoDirect Proof ExamplelDefinition: An integer n is called odd iff n=2k+1 for some integer k; n is even iff n=2k for some k. lTheorem: (For all numbers n) If n is an odd integer,
28、then n2 is an odd integer.lProof: If n is odd, then n = 2k+1 for some integer k. Thus, n2 = (2k+1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1. Therefore n2 is of the form 2j + 1 (with j the integer 2k2 + 2k), thus n2 is odd. Discrete Mathematics 30Hui GaoIndirect Proof ExamplelTheorem: (For all integers n) I
29、f 3n+2 is odd, then n is odd.lProof: Suppose that the conclusion is false, i.e., that n is even. Then n=2k for some integer k. Then 3n+2 = 3(2k)+2 = 6k+2 = 2(3k+1). Thus 3n+2 is even, because it equals 2j for integer j = 3k+1. So 3n+2 is not odd. We have shown that (n is odd)(3n+2 is odd), thus its
30、contra-positive (3n+2 is odd) (n is odd) is also true. Discrete Mathematics 31Hui GaoVacuous Proof ExamplelTheorem: (For all n) If n is both odd and even, then n2 = n + n.lProof: The statement “n is both odd and even” is necessarily false, since no number can be both odd and even. So, the theorem is
31、 vacuously true. Discrete Mathematics 32Hui GaoTrivial Proof ExamplelTheorem: (For integers n) If n is the sum of two prime numbers, then either n is odd or n is even.lProof: Any integer n is either odd or even. So the conclusion of the implication is true regardless of the truth of the antecedent.
32、Thus the implication is true trivially. Discrete Mathematics 33Hui GaoProof by Contradiction ExamplelTheorem: is irrational.lProof: Assume 21/2 were rational. This means there are integers i,j with no common divisors such that 21/2 = i/j. Squaring both sides, 2 = i2/j2, so 2j2 = i2. So i2 is even; t
33、hus i is even. Let i=2k. So 2j2 = (2k)2 = 4k2. Dividing both sides by 2, j2 = 2k2. Thus j2 is even, so j is even. But then i and j have a common divisor, namely 2, so we have a contradiction. Discrete Mathematics 34Hui GaoProof by Contraposition ExampleProve: If x2 is even, x is evenlProof: if x is
34、not even, x is odd. Therefore x2 is odd. This is the contrapositive of the original assertion.Discrete Mathematics 35Hui GaoProof by Examples (Cases) lTheorem: x,yZ: x2+3y2 = 8.lProof: If |x|3 or |y|2 then x2+3y2 8. This leaves x20,1,4 and 3y20,3. The largest pair sum to 4+3 = 7 1), there is some na
35、tural number larger than all x, y, z such that it is not divisible by x or y or z.Proof: Construct xyz+1. we first assume xyz+1 can be evenly divided by x, i.e. (xyz+1)/x = yz + 1/x, where 1/x must be an integer. The only possible value for x must be 1. But this is in contradiction with the fact tha
36、t x, y, z 1. Therefore, xyz+1 cannot be divided by x, and similarly, by y or z.Discrete Mathematics 37Hui GaoCounterexampleslConjecture: integers n0, n2n+41 is prime.lHm, lets see if we can find any counter-examples: l121+41 = 41 (prime)l222+41 = 42+41 = 43 (prime)l323+41 = 93+41 = 47 (prime) Lookin
37、g good so far!lCan we conclude after showing that it checks out in, say, 20 or 30 cases, that the conjecture must be true?lNEVER!lOf course, 41241+41 is divisible by 41!Discrete Mathematics 38Hui Gao“Forwardized” version of ExamplelTheorem: a0,b0,ab: (a+b)/2 (ab)1/2.lProof. If Since ab, (ab)0. Thus,
38、 (ab)20, i.e., a22ab+b2 0. lAdding 4ab to both sides, a2+2ab+b2 4ab. Factoring the left side, we have (a+b)2 4ab, so (a+b)2/4 ab. lSince ab is positive, we can take the square root of both sides and get (a+b)/2 (ab)1/2. Discrete Mathematics 39Hui GaoBackward Reasoning ExamplelTheorem: a0,b0,ab: (a+b
39、)/2 (ab)1/2.lProof:lNotice it is not obvious how to go from the premises a0, b0, ab directly forward to the conclusion (a+b)/2 (ab)1/2.lSo, lets work backwards from the conclusion, (a+b)/2 (ab)1/2 !Discrete Mathematics 40Hui Gao2.1 Sets lGoals: To introduce the basic terminology of set theory.lSets
40、S, T, U Special sets N, Z, R.lSet notations a,b,., x|P(x)lSet relation operators xS, ST, ST, S=T, ST, ST. (These form propositions.)lFinite vs. infinite sets.lSet operations |S|, P(S), ST.Discrete Mathematics 41Hui Gao2.2: Set OperationslGoals: To express set operations using set builder notation an
41、d logical operators. To show how set identities are established and to introduce the most important such identities. lcomplement : A = x | x A lunion : A B = x | x A x B lintersection :A B = x | x A x B ldifference : A - B = x | x A x B lsymmetric difference:AB= x | xA xB Discrete Mathematics 42Hui
42、GaoSet IdentitieslIdentity: A = A = AUlDomination: AU = U, A = lIdempotent: AA = A = AAlDouble complement: lCommutative: AB = BA, AB = BAlAssociative: A(BC)=(AB)C , A(BC)=(AB)ClDistributive: ()=()() ()=()()lDeMorgans Law: Discrete Mathematics 43Hui GaoProving Set IdentitieslTo prove statements about
43、 sets, of the form E1 = E2 (where the Es are set expressions), here are three useful techniques:1. Prove E1 E2 and E2 E1 separately.2. Use set builder notation & logical equivalences.3. Use a membership table.Discrete Mathematics 44Hui Gao“Big U” notation: orGeneralized Unions & Intersections“Big Ar
44、ch” notation: or Generalized Inclusion/ExclusionDiscrete Mathematics 45Hui Gao2.3 FunctionslGoals: To introduce the concept of a function, the notion of one-to-one functions, onto functions, and the floor and ceiling functions.lNotations: f:AB, f(a), f(A).lTerms: image, preimage, domain, codomain, r
45、ange, one-to-one, onto, bijective, inverse, composition.lFunction unary operator f 1, binary operators , , etc., and . lThe RZ functions x and x.Discrete Mathematics 46Hui GaoProof of Misc. propertiesf(A B) f(A) f(B)?f(A B) = x : a (A B), f(a) = xChoose an arbitrary x f(A B), and show that it must a
46、lso be an element of f(A) f(B).So, a (A B) such that f(a) = x.If a A (it is), then f(a) = x f(A).If a B (it is), then f(a) = x f(B).x f(A), and x f(B), so x f(A) f(B).Discrete Mathematics 47Hui GaoProof of Misc. propertiesf-1(A B) = f-1(A) f-1(B) Choose an arbitrary x f-1(A) f-1(B), and show that it
47、 must also be an element of f-1(A B).If x f-1(A) (it is), then f(x) A.If x f-1(B) (it is), then f(x) B.so f(x) A B, and x f-1(A B). Proof: (1) f-1(A) f-1(B) f-1(A B) (2) f-1(A B) f-1(A) f-1(B) Trivial.Discrete Mathematics 48Hui Gao2.4: Sequences and SummationslGoals: To introduce terminology used fo
48、r sequences and summations and to introduce the concept of countability.lA sequence or series is just like an ordered n-tuple, except:lEach element has an associated index number.lA sequence or series may be infinite.lA string is a sequence of symbols from finite alphabet.lA summation is a compact n
49、otation for the sum of all terms in a (possibly infinite) series.Discrete Mathematics 49Hui GaoSummationslSum of a sequence from 0 to n :lSum of all the number in S :lDouble sum:lSum of first n numbers:lSum of first n kth powers:lGeometric sum:Discrete Mathematics 50Hui GaoCardinality and Countabili
50、tyCountable: 1.Finite, or2. -same cardinality as N: there is a bijection with the natural numbers.Lemmas: S is countable iflan onto function from another countable setlthere is a 1-to-1 function to another countable setEG: Z is countable because it is enumerated by the sequenceDiscrete Mathematics 5
51、1Hui Gao3.1: AlgorithmslGoals: To introduce the concept and basic properties of an algorithm.lCharacteristics of algorithms.lPseudocode.lExamples: Max algorithm, primality-testing, linear search & binary search algorithms. lIntuitively we see that binary search is much faster than linear search, but
52、 how do we analyze the efficiency of algorithms formally?Discrete Mathematics 52Hui Gao3.2: the Growth of functionslGoals: To introduce big-O and related big-Omega and big-Theta notation, and to show how to estimate the size of functions using this notation.Discrete Mathematics 53Hui GaoAsymptotical
53、 ComparinglComparing f(n) and g(n) as n approaches infinity,l If r = , thenr 0, including the case in which the limit is then f (g)r = c and 0 c k: 30n+8 cn.lLet c=31, k=8. Assume nk=8. Thencn = 31n = 30n + n 30n+8, so 30n+8 k: n2+1 cn2.lLet c=2, k=1. Assume nk=1. Then cn2 = 2n2 = n2+n2 n2+1, or n2+
54、11)l(n!)Factorial(With c a constant.)NP ProblemsDiscrete Mathematics 59Hui GaoComplexity analysis, cont.procedure max(a1, a2, , an: integers) v := a1t1 for i := 2 to nt2 if ai v then v := ait3 return vt4w.c.t.c.: Times for each execution of each line.Discrete Mathematics 60Hui Gao3.4-3.5: The Intege
55、rs and DivisionlGoals: To introduce some fundamental concepts from number theory, including the Division, Primality, Prime Factorization, GCD, LCM, Modular, and some useful Congruence theorems.Discrete Mathematics 61Hui GaoApplications of Congruence Hashing function. E.g. let k be your id. no. Assum
56、e we have m locations and hashing function: h(k) = k mod m h(064212848) = 064212848 mod 111=14 h(037149212) = 037149212 mod 111=65 Pseudorandom Numbers. Let modulus m, multiplier a, increment c, seed x0.xn+1=(axn+c) mod mDiscrete Mathematics 62Hui Gao3.6: Integers & AlgorithmslGoals: lTo cover repre
57、sentations of integers in different bases, including binary, octal, and hexadecimal representations,l twos complement notation for negative numbers in binary.land to introduce algorithms involving integers, including the Euclidean algorithm and algorithms for arithmetic.Discrete Mathematics 63Hui Ga
58、oTwos Complement RepresentationlIn binary, negative numbers can be conveniently represented using twos complement notation.lIn this scheme, a string of n bits can represent any integer i such that 2n1 i 2n1.lThe bit (msb) in the highest-order bit-position (n1) represents a coefficient multiplying 2n
59、1;lThe other positions i n-2.lBasis step: F3 =2 1; F4 =3 2lInductive hypothesis: lAssume Fn n-2 and Fn-1 n-3lRecursive step: Show true for new element Fn+1lFn+1=Fn + Fn-1 n-2+ n-3= n-3(+1) n-1lProven!Discrete Mathematics 75Hui Gao75Rules for Recursive AlgorithmslBase case - must have a way to end th
60、e recursionlRecursive call - must change at least one of the parameters and make progress towards the base caselexponentiation (x,y)lbase: if y is 0 then return 1lrecursive: else return (x*exponentiation(x,y-1)Discrete Mathematics 76Hui Gao5: CountinglUse basic counting rules to solve a variety of c
61、ounting problems.lthe product and sum rules, inclusionexclusionl Use the Pigeonhole Principle in enumeration and in proofslPermutations and Combinationsl a combination involves an unordered selection of objects from a set with no repetition allowed, while a permutation involves an ordered selection
62、of objects from a set with no repetition allowed. lGeneralized Permutations and CombinationslTo solve counting problems involving permutations and combinations with repetition allowed and permutations where objects may be indistinguishable.Discrete Mathematics 77Hui GaoIP Address Example lSome facts
63、 about the Internet Protocol, version 4:lValid computer addresses are in one of 3 types:lA class A IP address contains a 7-bit “netid” 17, and a 24-bit “hostid”lA class B address has a 14-bit netid and a 16-bit hostid.lA class C addr. Has 21-bit netid and an 8-bit hostid.lHostids that are all 0s or
64、all 1s are not allowed.lHow many valid computer addresses are there?ClassNetIDHostIDA7 bits24 bitsDiscrete Mathematics 78Hui GaoInclusion/Exclusion ExamplelSome hypothetical rules for passwords:lPasswords must be 2 characters long.lEach character must be a letter a-z, a digit 0-9, or one of the 10 p
65、unctuation characters !#$%&*().lEach password must contain at least 1 digit or punctuation character.Discrete Mathematics 79Hui GaoGeneralized Pigeonhole PrinciplelIf N objects are assigned to k places, then at least one place must be assigned at least N/k objects.lE.g., there are N=280 students in
66、this class. There are k=52 weeks in the year.lTherefore, there must be at least 1 week during which at least 280/52= 5.38=6 students in the class have a birthday.Discrete Mathematics 80Hui GaoPermutation ExamplelAn actress is depicted disabling a bomb by cutting wires to the trigger device. There ar
67、e 10 wires to the device. If she cuts exactly the right 3 wires, in exactly the right order, she will disable the bomb, otherwise it will explode! If the wires all look the same, what are her chances of survival?P(10,3) = 10!/(10-3)! 1098 = 720, so there is a 1 in 720 chance that shell survive!Discr
68、ete Mathematics 81Hui GaoCombination ExamplelHow many distinct 7-card hands can be drawn from a standard 52-card deck?lThe order of cards in a hand doesnt matter.lAnswer C(52,7) = P(52,7)/P(7,7)= 52515049484746 / 765432152171074746 = 133,784,560Discrete Mathematics 82Hui Gao8.1: Relations and Their
69、PropertieslGoals: To introduce the concept of a relation and basic properties of binary relations, including the reflexive, symmetric, antisymmetric, and transitive propertiesDiscrete Mathematics 83Hui GaoExamples:A: not reflexive; symmetric; antisymmetric; transitiveB: not reflexive; not symmetric;
70、 not antisymmetric; not transitiveC: not reflexive; not symmetric; antisymmetric; not transitiveD: not reflexive; not symmetric; antisymmetric; transitiveDiscrete Mathematics 84Hui GaoCombining Relations ExamplelLet A = 1, 2, 3 and B = 1, 2, 3, 4 R1 =(1, 1),(2, 2),(3, 3) R2 = (1, 1),(1, 2),(1, 3),(1
71、, 4) R1R2=(1, 1),(1, 2),(1, 3),(1, 4),(2, 2),(3, 3) R1 R2=(1, 1) R1 R2=(2, 2), (3, 3) R2 R1=(1, 2),(1, 3),(1, 4)Discrete Mathematics 85Hui GaoCombining Relationsl Example: Let D and S be relations on A = 1, 2, 3, 4: D = (a, b) | b = 5 - a, S = (a, b) | a b. D = (1, 4), (2, 3), (3, 2), (4, 1)S = (1,
72、2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)S D =l D maps an element a to the element (5 a), and afterwards S maps (5 a) to all elements larger than (5 a), resulting in S D = (a,b) | 5 ab.(2, 4),(2, 4), (3, 3),(3, 3), (3, 4),(3, 4), (4, 2),(4, 2), (4, 3),(4, 3), (4, 4)(4, 4)Discrete Mathematics 86Hui
73、Gao8.2 n-ary RelationslGoals: To introduce the concept of n-ary relations and show how these relations are used to represent data bases.Discrete Mathematics 87Hui GaolLet Rooms be the relation with attributes Place, Seats, BoardType, Computer R=(Fan17, 80, Chalk, Yes), (Lws21, 25, No, Yes), (Nek13,
74、50, Chalk, No), (Agr21, 90, No, Yes), R1 select =( R, BoardType, Chalk)R1=(Fan17,80, Chalk, Yes), (Nek13, 50, Chalk, No), R2 select =(R1, Computer, Yes)R2 = (Fan17,80, Chalk, Yes),Selection Operator ExampleDiscrete Mathematics 88Hui GaoProjection ExamplelLet Rooms be the relation with attributes Pla
75、ce, Seats, BoardType, Computer R=(Fan17, 80, Chalk, Yes), (Lws21, 25, No, Yes), (Nek13, 50, Chalk, No), (Agr21, 90, No, Yes), R1 = project (R, Place, Seats) will produce a relation limited to the place and number of seats.R1 =(Fan17, 80), (Lws21, 25), (Nek13, 50), (Agr21, 90), Discrete Mathematics 8
76、9Hui GaoJoin ExampleProf. CourseJohn CS202Brian CS340Kenny CS220Kemal CS215Course Class TimeCS215 FNR1326 11CS220 FNR2332 9CS340 Quig101 2CS202 LWS202 3What is the result of R1 joining R2?R1R2Discrete Mathematics 90Hui Gao8.3 Representing RelationslGoals: To show how relations can be represented usi
77、ng zeroone matrices and directed graphs.Discrete Mathematics 91Hui GaoZero-One Reflexive, SymmetriclTheorem: Let R be a binary relation on a set A and let M be its connection matrix. Thenl R is reflexive iff Mii = 1 for all i, irreflexive iff Mii = 0.l R is symmetric iff M is a symmetric matrix: M =
78、 MTl R is antisymetric if Mij = 0 or Mji = 0 for all ij.Reflexive:all 1s on diagonalIrreflexive:all 0s on diagonalSymmetric:all identicalacross diagonalAntisymmetric:all 1s are acrossfrom 0sany-thingany-thingany-thingany-thinganythingDiscrete Mathematics 92Hui GaoCombining Connection MatricesIf M1 i
79、s the connection matrix for R1 and M2 is the connection matrix for R2 thenDefinition: the join of two matrices M1, M2, denoted M1 M2 is the component wise boolean or of the two matrices. It is the connection matrix for R1 R2.Definition: the meet of two matrices M1, M2, denoted M1 M2 is the component
80、 wise boolean and of the two matrices. It is the connection matrix for R1R2.Discrete Mathematics 93Hui GaoThe CompositionThe boolean product of two connection matrices (M1)mn and (M2)np, denoted M1 M2 , is the connection matrix for the composition of R2 with R1, R2 o R1. M1 M2 Why? In order for ther
81、e to be a link in the composition then there must be a link in R1 and a link in R2 for some y!The Boolean product checkes all possible ys. If at least one such path exists, that is sufficient.Discrete Mathematics 94Hui GaoUsing Directed GraphslA directed graph or digraph G=(VG,EG) is a set VG of ver
82、tices (nodes) with a set EGVGVG of edges (links). Visually represented using dots for nodes, and arrows for edges. Notice that a relation R:AB can be represented as a graph GR=(VG=AB, EG=R).Matrix representation MR:Graph rep. GR:JoeFredMarkSusanMarySallyNode set VG(black dots)Edge set EG(blue arrows
83、)Discrete Mathematics 95Hui GaoDigraph Reflexive, SymmetriclIt is extremely easy to recognize the reflexive/irreflexive/ symmetric/antisymmetric properties by graph inspection.Reflexive:Every nodehas a self-loopIrreflexive:No nodelinks to itselfSymmetric:Every link isbidirectional Antisymmetric:No l
84、ink isbidirectional These are non-symmetric & non-antisymmetricThese are non-reflexive & non-irreflexiveDiscrete Mathematics 96Hui Gao8.4 Closures of RelationslGoals: To introduce the concept of the closure of a relation with respect to a property, and to develop algorithms for constructing transiti
85、ve closures.Discrete Mathematics 97Hui GaoExamplelLet R be a relation on the set 0, 1, 2, 3 containing the ordered pairs (0,1), (1,1), (1,2), (2,0), (2,2), and (3,0)lWhat is the reflexive closure of R?lWe add all pairs of edges (a,a) that do not already exist0132We add edges:(0,0), (3,3)Discrete Mat
86、hematics 98Hui GaoExamplelLet R be a relation on the set 0, 1, 2, 3 containing the ordered pairs (0,1), (1,1), (1,2), (2,0), (2,2), and (3,0)lWhat is the symmetric closure of R?lWe add all pairs of edges (a,b) where (b,a) existslWe make all “single” edges into anti-parallel pairs0132We add edges:(0,
87、2), (0,3)(1,0), (2,1)Discrete Mathematics 99Hui GaoTransitive closurelInformal definition: If there is a path from a to b, then there should be an edge from a to b in the transitive closurelIn order to find the transitive closure of a relation R, we add an edge from a to c, when there are edges from
88、 a to b and b to c. Repeat this step until no new edges are added to the relation.R = (1,2), (2,3), (3,4) (1,2) & (2,3) (1,3)(2,3) & (3,4) (2,4)(1,2) & (2,4) (1,4)1234Discrete Mathematics 100Hui GaoFinding the transitive closurelLet MR be the zero-one matrix of the relation R on a set with n element
89、s. Then the zero-one matrix of the transitive closure R* is:Nodes reachable with one application of the relationNodes reachable with two applications of the relationNodes reachable with n applications of the relationDiscrete Mathematics 101Hui Gao8.5 Equivalence RelationslGoals: To study equivalence
90、 relations and their equivalence classes.Discrete Mathematics 102Hui GaoEquivalence Relation ExampleslConsider relation R = (a,b) | len(a) = len(b) lwhere len(a) means the length of string alReflexivity: len(a) = len(a)lSymmetry: if len(a) = len(b), then len(b) = len(a)lTransitivity: if len(a) = len
91、(b) and len(b) = len(c), then len(a) = len(c)lThus, R is a equivalence relationDiscrete Mathematics 103Hui GaoEquivalence classeslConsider the relation R = (a,b) | a = b or a = -b lThus, every number is related to additive inverselThe equivalence class for an integer a:l7 = 7, -7 l0 = 0 la = a, -a l
92、There are an infinite number of equivalence classes formed by this equivalence relationDiscrete Mathematics 104Hui GaoExamples of partitionslWhich of the following are partitions of the set of integers?a)The set of even integers and the set of odd integersYes, its a valid partitionb)The set of posit
93、ive integers and the set of negative integersNo: 0 is in neither setc)The set of integers divisible by 3, the set of integers leaving a remainder of 1 when divided by 3, and the set of integers leaving a remaineder of 2 when divided by 3Yes, its a valid partitionDiscrete Mathematics 105Hui Gao9.1 Gr
94、aphs and Graph ModelsGoals: To introduce the notion of a graph and to show how to build graph modelsand to demonstrate the wide applicability of graph models.Discrete Mathematics 106Hui GaoSimple digraph Each person of the group is represented by a vertex. There is a directed edge from vertex a to v
95、ertex b when the person a influences the person b.egLindaBrianDeborahFredYvonneInfluence graphsDiscrete Mathematics 107Hui GaoSimple digraph Each statement is represented by a vertex, and there is an edge from a to b if the statement of b cannot be executed before the statement of a. egS1S2S4S5S3S6S
96、1: a:=0S2: b:=1S3: c:=a+1S4: d:=b+aS5: e:=d+1S6: e:=c+dPrecedence graphs Discrete Mathematics 108Hui Gao 9.2 Graph Terminology and Special Types of GraphsGoals: l To introduce some of the basic terminology of graph theory and some basic results about graphs. To describe some important families of gr
97、aphs such as: n-regular, complete graph Kn, cycle Cn, wheel Wn, n-cube Qnl To introduce the notion of a bipartite graph.Discrete Mathematics 109Hui Gao ExampleDiscrete Mathematics 110Hui GaoExample 4.deg(a)=2, deg+(a)=4deg(b)=2, deg+(b)=1deg(c)=3, deg+(c)=2deg(d)=2, deg+(d)=2deg(e)=3, deg+(e)=3deg(f
98、 )=0, deg+(f )=0abcedfDiscrete Mathematics 111Hui GaoExample 11. Is the graph G bipartite?agfecbdDiscrete Mathematics 112Hui GaoabcdefG1G2 Example 15.abcdfabcdeG1G2Discrete Mathematics 113Hui Gao9.3 Representing Graphs and Graph IsomorphismGoals: To show how to represent graphs and to study isomorph
99、ism of graphs.Discrete Mathematics 114Hui GaoExample 2. (digraph)abedcInitial vertexTerminal verticesab,c,d,ebb,dca,c,edeb,c,dDiscrete Mathematics 115Hui GaoExample 3. abcdabcdacbdExample 5. (Pseudograph) abcdabcdabcdDiscrete Mathematics 116Hui GaoShow that G and H are isomorphic.The function f with
100、 f(u1) = v1, f(u2) = v4, f(u3) = v3, and f(u4) = v2 is a one-to-one correspondence between V(G) and V(H).u1GHu3u2u4v2v4v1v3Sol. Example 8. Discrete Mathematics 117Hui GaoGraph Invariants under IsomorphismNecessary but not sufficient conditions for G1=(V1, E1) to be isomorphic to G2=(V2, E2):l|V1|=|V
101、2|, |E1|=|E2|.lThe number of vertices with degree n is the same in both graphs.lFor every proper subgraph g of one graph, there is a proper subgraph of the other graph that is isomorphic to g.Discrete Mathematics 118Hui Gao9.4: ConnectivityGoals: To introduce the notions of paths and circuits in gra
102、phs and to define connectivity of graphs.Discrete Mathematics 119Hui GaoFind the cut vertices and cut edges in the graph G. bacdehgfGcut vertices: b, c, e cut edges: a, b, c, e Sol:Example 8. Discrete Mathematics 120Hui GaoAre the directed graphs G and H strongly connected or weakly connected?eadbGc
103、Headbcstrongly connectedweakly connectedExample 9 Discrete Mathematics 121Hui GaoExample 14. How many paths of length 4 are there from a to d in the graph G?GabcdSol. The adjacency matrix of G (ordering as a, b, c, d) is 8Discrete Mathematics 122Hui Gao9.5: Euler & Hamilton PathsGoals: To develop ne
104、cessary and sufficient conditions for the existence of Euler circuits and paths, to give algorithms for constructing them, and to study Hamilton paths and circuits.Discrete Mathematics 123Hui GaoExample 1. Which of the following graphs have an Euler circuit or an Euler path? abG1cedabG2cedabG3cedEul
105、er circuit Euler pathnoneDiscrete Mathematics 124Hui Gaov1v2v3v5v4v6Step 1: find the 1st circuit C: v1, v2, v3, v4, v5, v1Step 2: H = G C , find subcircuitSC: v3, v5, v6, v3Step 3: C = C SC, H= G C =, stopC: v1, v2, v3, v5, v6, v3, v4, v5, v1SC embeddedAlgorithm for Constructing Euler CircuitsDiscre
106、te Mathematics 125Hui GaoHamilton Paths and CircuitsExample 1. Which of the following graphs have a Hamilton circuit or a Hamilton path? abG2cdHamilton circuit: G1 abG1cdeabG3decgfHamilton path: G1,G2 Discrete Mathematics 126Hui GaoTwo Theorems for Hamilton CircuitsThm. 3 (Diracs Thm.):If (but not o
107、nly if) G is a simple graph with n3 vertices such that the degree of every vertex in G is at least n/2, then G has a Hamilton circuit. Thm. 4 (Ores Thm.):If G is a simple graph with n3 vertices such that deg(u)+deg(v) n for every pair of nonadjacent vertices u and v, then G has a Hamilton circuit. D
108、iscrete Mathematics 127Hui Gao9.6: Shortest-Path ProblemsGoals: To present an algorithm for finding a shortest path in a weighted graph, and to discuss the traveling salesman problem.Discrete Mathematics 128Hui GaoExample 2. Use Dijkstras algorithm to find the length of a shortest path between a and
109、 z in the weighted graph. bdecaz6385421012bdecaz63854210120Sol. 0bdecaz63854210124(a)2(a) 0bdecaz63854210123(c)10(c)12(c)2(a) 0bdecaz63854210123(c)8(b)12(c)2(a) d0becaz63854210123(c)8(b) 14 (d)10(d)2(a)Discrete Mathematics 129Hui Gaod0becaz63854210123(c)8(b) 14(d)10(d)2(a) d0becaz63854210123(c)8(b)
110、13(e)10(d)2(a) 13(e)d0becaz63854210123(c)8(b)10(d)2(a) path: a, c, b, d, e, z length: 13 Discrete Mathematics 130Hui Gao9.7: Planar GraphsGoals: To introduce the concept of planarity of graphs and to develop tools to decide whether a graph is planar.Discrete Mathematics 131Hui GaoExample 3: Show tha
111、t K3,3 is nonplanar.Example 2: Is Q3 planar?Q3Q3 drawn with no crossings Q3 is planaradbcefSol.daebR2R1daebcfDiscrete Mathematics 132Hui GaoExample 4: Suppose that a connected planar graph has 20 vertices, each of degree 3. Into how many regions does a representation of this planar graph split the p
112、lane?Sol. v = 20, 2e = 320 = 60, e = 30 r = ev+2 = 3020+2 = 12Discrete Mathematics 133Hui GaoDiscrete Mathematics 134Hui Gao9.8: Graph ColoringGoals: To introduce the concept of the coloring of a graph and give applications of graph colorings.Discrete Mathematics 135Hui Gao21311Example 1: What are t
113、he chromatic numbers of the graphs G and H?32GgaHSol: G has a 3-cycle c(G)3 G has a 3-coloring c(G)3 c(G)=3 Sol: any 3-coloring for H(a,g) gives the same color to a and g c(H)3 4-coloring exists c(H)=4 Discrete Mathematics 136Hui Gao10.1 Introduction to TreesGoals: To introduce the concept of a tree
114、, to present basic terminology for trees, and to develop relationships among the number of vertices of different kinds and the number of edges in trees.Discrete Mathematics 137Hui GaoExample 3 full binary tree full 3-ary tree full 5-ary tree not full 3-ary tree Discrete Mathematics 138Hui Gao Proper
115、ties of TreesThm 2. A tree with n vertices has n1 edges.Thm 3. A full m-ary tree with i internal vertices contains n =mi 1 vertices.Cor. A full m-ary tree with n vertices contains (n1)/m internal vertices, and hence n (n1)/m = (m1)n1)/m leaves.Thm 5. There are at most mh leaves in an m-ary treeof he
116、ight h.Discrete Mathematics 139Hui GaoExample 11 Which of the rooted trees shown below are balanced? Sol. T1, T3Ex 28 How many vertices and how many leaves doesa complete m-ary tree of height h have? Discrete Mathematics 140Hui Gao10.2 Applications of TreesGoals: To introduce several applications of
117、 trees, including binary search trees, decision trees, prefix codesDiscrete Mathematics 141Hui GaoExample 1 Form a binary search tree for the words mathematics, physics, geography, zoology, meteorology, geology, psychology, and chemistry (using alphabetical order). Sol. Discrete Mathematics 142Hui G
118、aoExample 4 A decision tree that orders the elements of the list a, b, c.Sol. Discrete Mathematics 143Hui GaoExample 5 Use Huffman coding to encode the following symbols with the frequencies listed: A: 0.08, B: 0.10, C: 0.12, D: 0.15, E: 0.20, F: 0.35.What is the average number of bits used to encod
119、e a character?Discrete Mathematics 144Hui Gao10.3 Tree TraversalGoals: To introduce tree traversal algorithms and prefix and postfix notation.Discrete Mathematics 145Hui GaoExample 2. In which order does a preorder traversal visit the vertices in the ordered rooted tree T shown below?Sol: Discrete M
120、athematics 146Hui GaoExample 3. In which order does an inorder traversal visit the vertices in the ordered rooted tree T shown below?Sol: Discrete Mathematics 147Hui GaoExample 4. In which order does a postorder traversal visit the vertices in the ordered rooted tree T shown below?Sol: Discrete Math
121、ematics 148Hui GaoPreorder: a, b, d, h, e, i, j, c, f, g, kInorder: h, d, b, i, e, j, a, f, c, k, gPostorder: h, d, i, j, e, b, f, k, g, c, aDiscrete Mathematics 149Hui GaoProcedure preorder(T: ordered rooted tree)r := root of Tlist rfor each child c of r from left to rightbegin T(c) := subtree with
122、 c as its root preorder(T(c)end Algorithm 1 (Preorder Traversal) Discrete Mathematics 150Hui GaoProcedure inorder(T: ordered rooted tree)r := root of TIf r is a leaf then list relsebegin l := first child of r from left to right T(l) := subtree with l as its root inorder(T(l) list r for each child c
123、of r except for l from left to right T(c) := subtree with c as its root inorder(T(c)end Algorithm 2 (Inorder Traversal) Discrete Mathematics 151Hui GaoProcedure postorder(T: ordered rooted tree)r := root of Tfor each child c of r from left to rightbegin T(c) := subtree with c as its root postorder(T
124、(c)end list rAlgorithm 3 (Postorder Traversal) Discrete Mathematics 152Hui GaoSol. x y + 2 x 4 3 / +Example 6 What is the prefix form for (x+y)2)+(x4)/3)? Example 8 What is the postfix form of the expression (x+y)2)+(x4)/3)? Sol. + + x y 2 / x 4 3Discrete Mathematics 153Hui GaoExample 7 What is the
125、value of the prefix expression+ * 2 3 5 / 2 3 4? Sol. Discrete Mathematics 154Hui GaoExample 9 What is the value of the postfix expression7 2 3 * 4 9 3 / +? Sol. Discrete Mathematics 155Hui Gao10.4 Spanning TreesGoals: To introduce the concept of a spanning tree, to give algorithms for constructing
126、such trees, and to show how to solve problems using backtracking.Discrete Mathematics 156Hui GaoExample 3 Use depth-first search to find a spanning treefor the graph.Sol. (arbitrarily start with the vertex f) Discrete Mathematics 157Hui GaoProcedure DFS(G: connected graph with vertices v1, v2, , vn)
127、T := tree consisting only of the vertex v1visit(v1)procedure visit(v: vertex of G)for each vertex w adjacent to v and not yet in Tbegin add vertex w and edge v, w to T visit(w)endAlgorithm 1 (Depth-First Search) Discrete Mathematics 158Hui GaoSol. (arbitrarily start with the vertex e) Example 5 Use
128、breadth-first search to find a spanning treefor the graph.Discrete Mathematics 159Hui GaoProcedure BFS(G: connected graph with vertices v1, v2, , vn)T := tree consisting only of vertex v1L := empty listput v1 in the list L of unprocessed verticeswhile L is not emptybegin remove the first vertex v fr
129、om L for each neighbor w of v if w is not in L and not in T then begin add w to the end of the list L add w and edge v, w to T endendAlgorithm 2 (Breadth-First Search) Discrete Mathematics 160Hui GaoExample 6 (Graph Colorings) How can backtracking be used to decide whether the following graph can be
130、 colored using 3 colors?Sol.Discrete Mathematics 161Hui Gao10.5 Minimum Spanning TreesGoals: To study minimum spanning trees and produce algorithms for generating them.Discrete Mathematics 162Hui GaoExample 2 Use Prims algorithm to find a minimum spanning tree of G.Sol.Discrete Mathematics 163Hui GaoExample 3 Use Kruskalalgorithm to find a minimum spanning tree of G.Sol.
