《复旦大学 赵一鸣 离散数学 二》由会员分享，可在线阅读，更多相关《复旦大学 赵一鸣 离散数学 二（28页珍藏版）》请在金锄头文库上搜索。
1、 每周一交作业，作业成绩占总成绩的 10%； 平时不定期的进行小测验，占总成绩的 20%； 期中考试成绩占总成绩的20%；期终考 试成绩占总成绩的50% AB=AC B=C cancellation law 。 Example:A=1,2,3,B=3,4,5,C=4,5, BC, But AB=AC=1,2,3,4,5 Example: A=1,2,3,B=3,4,5,C=3,BC, But AB=AC=3 A-B=A-C B=C cancellation law :symmetric difference The symmetric difference of A and B, write
2、AB, is the set of all elements that are in A or B, but are not in both A and B, i.e. AB=(AB)-(AB) 。 (AB)-(AB)=(A-B)(B-A) Theorem 1.4: if AB=AC, then B=C Distributive laws and De Morgans laws: B(A1A2An)=(BA1)(BA2)(BAn) B(A1A2An)=(BA1)(BA2)(BAn)Chapter 2 Relations Definition 2.1: An order pair (a,b) i
3、s 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
4、 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
5、A and B, denoted by AB, is the set of all ordered pairs ( a,b) where aA and bB. Hence AB=(a, b)| aA and bB Example: Let A=1,2, B=x,y,C=a,b,c. AB=(1,x),(1,y),(2,x),(2,y); BA=(x,1),(x,2),(y,1),(y,2); BAAB commutative laws AC=(1,a),(1,b),(1,c),(2,a),(2,b),(2,c) ; AA=(1,1),(1,2),(2,1),(2,2)。 A=A= Defini
6、tion 2.4: Let A1,A2,An be sets. The Cartesian product of A1,A2,An, denoted by A1A2An, is the set of all ordered n-tuples (a1,a2,an) where aiAi for i=1,2,n. Hence A1A2An=(a1,a2,an)|aiAi, i=1,2,n. Example:ABC=(1,x,a),(1,x,b),(1,x,c),(1,y,a), (1,y,b), (1,y,c),(2,x,a),(2,x,b),(2,x,c),(2,y,a),(2,y,b), (2
7、,y,c)。 If Ai=A for i=1,2,n, then A1A2An by An. Example：Let A represent the set of all students at an university, and let B represent the set of all course at the university. What is the Cartesian product of AB? The Cartesian product of AB consists of all the ordered pairs of the form (a,b), where a
8、is a student at the university and b is a course offered at the university. The set AB can be used to represent all possible enrollments of students in courses at the university students a,b,c, courses:x,y,z,w (a,y),(a,w),(b,x),(b,y),(b,w)，(c,w) R=(a,y),(a,w),(b,x),(b,y),(b,w) RAB, i.e. R is a subse
9、t of AB relation 2.2 Binary relations Definition 2.5: Let A and B be sets. A binary relation from A to B is a subset of AB. A relation on A is a relation from A to A. If (a,b)R, we say that a is related to b by R, we also write a R b. If (a,b)R , we say that a is not related to b by R, we also write
10、 a b. we say that empty set is an empty relation. Definition 2.6: Let R be a relation from A to B. The domain of R, denoted by Dom(R), is the set of elements in A that are related to some element in B. The range of R, denoted by Ran(R), is the set of elements in B that are related to some element in
11、 A. Dom RA,Ran RB。 Example: A=1,3,5,7,B=0,2,4,6, R=(a,b)|ab, where aA and bB Hence R=(1,2),(1,4),(1,6),(3,4),(3,6),(5,6) Dom R=1,3,5, Ran R=2,4,6 (3,4)R, Because 43, so (4,3)R Table R=(1,2),(1,4),(1,6),(3,4), (3,6),(5,6) A=1,2,3,4,R=(a,b)| 3|(a-b), where a and bA R=(1,1),(2,2),(3,3), (4,4),(1,4),(4,
12、1) Dom R=Ran R=A。 congruence mod 3 congruence mod r (a,b)| r|(a-b) where a and bZ, and rZ+ Definition 2.7：Let A1,A2,An be sets. An n-ary relation on these sets is a subset of A1A2An. 2.3 Properties of relations Definition 2.8: A relation R on a set A is reflexive if (a,a)R for all aA. A relation R o
13、n a set A is irreflexive if (a,a)R for every aA. A=1,2,3,4 R1=(1,1),(2,2),(3,3) ? R2=(1,1),(1,2),(2,2),(3,3),(4,4) ? Let A be a nonempty set. The empty relation AA is not reflexive since (a,a) for all aA. However is irreflexive Definition 2.9: A relation R on a set A is symmetric if whenever a R b,
14、then b R a. A relation R on a set A is asymmetric if whenever a R b, then ba. A relation R on a set A is antisymmetric if whenever a R b, then ba unless a=b. If R is antisymmetric, then a b or b a when ab. A=1,2,3,4 S1=(1,2),(2,1),(1,3),(3,1)? S2=(1,2),(2,1),(1,3)? S3=(1,2),(2,1),(3,3) ? A relation
15、is not symmetric, and is also not antisymmetric S4=(1,2),(1,3),(2,3) antisymmetric, asymmetric S5=(1,1),(1,2),(1,3),(2,3) antisymmetric, is not asymmetric S6=(1,1),(2,2) antisymmetric, symmetric, is not asymmetric A relation is symmetric, and is also antisymmetric Definition 2.10: A relation R on set A is transitive if whenever a R b and b R c, the
