离散数学2nn.ppt

Exercise: P13 42 43 47 48 P126 17,37 P134 24, 26, P146 1,2,12, 21,31 P167 1,8,9,11 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 每周三交作业，作业成绩占总成绩的15%； 平时不定期的进行小测验，占总成绩的15%； 期中考试成绩占总成绩的20%；期终考试成绩占总成绩的50% zhym@fudan.edu.cn 张宓fudan.edu.cn BBS id:abchjsabc 软件楼103 杨侃 10302010007@fudan.edu.cn 程义婷 11302010050@fudan.edu.cn BBS id:chengyiting 刘雨阳fudan.edu.cn，软件楼405 liy@fudan.edu.cn 李弋 A∪B=A∪C ? B=C cancellation law ?。 Example:A={1,2,3},B={3,4,5},C={4,5}, B?C, But A∪B=A∪C={1,2,3,4,5} Example: A={1,2,3},B={3,4,5},C={3},B?C, But A∩B=A∩C={3} A-B=A-C ?B=C cancellation law :symmetric difference The symmetric difference of A and B, write A?B, is the set of all elements that are in A or B, but are not in both A and B, i.e. A?B=(A∪B)-(A∩B) 。 (A∪B)-(A∩B)=(A-B)∪(B-A) Theorem 1.4: if A?B=A?C, then B=C Distributive laws and De Morgan’s laws: B∩(A1∪A2∪…∪An)=(B∩A1)∪(B∩A2)∪…∪(B∩An) B∪(A1∩A2∩…∩An)=(B∪A1)∩(B∪A2)∩…∩(B∪An) Chapter 2 Relations Definition 2.1: An order pair (a,b) is a listing of the objects a and b in a prescribed order, with a appearing first and b appearing second. Two order pairs (a,b) and (c, d) are equal if only if a=c and b=d. {a,b}={b,a}， order pairs: (a,b)?(b,a) unless a=b. (a,a) Definition 2.2: The ordered n-tuple (a1,a2,…,an) is the ordered collection that has a1 as its first element, a2 as its second element,…, and an as its nth element.Two ordered n-tuples are equal is only if each corresponding pair of their elements ia equal, i.e. (a1,a2,…,an)=(b1,b2,…,bn) if only if ai=bi, for i=1,2,…,n. Definition 2.3: Let A and B be two sets. The Cartesian product of A and B, denoted by A×B, is the set of all ordered pairs ( a,b) where a?A and b?B. Hence A×B={(a, b)| a?A and b?B} Example: Let A={1,2}, B={x,y},C={a,b,c}. A×B={(1,x),(1,y),(2,x),(2,y)}; B×A={(x,1),(x,2),(y,1),(y,2)}; B×A?A×B commutative laws × A×C={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)}; A×A={(1,1),(1,2),(2,1),(2,2)}。 A×?=?×A=? Definition 2.4: Let A1,A2,…An be