西安交通大学离散复习重点.docx

1.个体与集合之间的关系称为属于关系。2.对于两个集合A，B，若A中的每个元素x都是B 的一个元素，则称A包含在B中（或者说B包含A ），记为AB。同时称A是B的子集（称B是A 的超集(superset)）。即AB x(xA xB) 。3. 集合与集合之间的关系有四种。列举如下 (1)B包含A， AB x(xA xB) ； (2)A包含B， BA x(xB xA)； (3)A等于B， A=B x(xB xA) ABBA ； (4)A与B互不包含， (AB)(BA) x(xAxB)y(yByA) 交、并、余运算的基本定理设X是全集，A，B，C是X的三个子集。则 (1)幂等律：A∩A=A， A∪A=A； (2)互补律：A∩A = ， A∪A =X；(2’)零壹律：A∩X=A，A∪X=X ； (全集是交的幺元,并的零元) (2”)零壹律：A∩ = ，A∪ =A； (空集是交的零元,并的幺元) (3)上界：A A∪B， B A∪B ；　 下界：A∩B A ， A∩B B ； (3’)上确界： A C B C A∪B C； (并集A∪B是同时包含A和B的集合中最小的一个) (3”)下确界：C A C B C A∩B； (交集A∩B是同时被A和B所包含的集合中最大的一个) (4)吸收律： A∩(A∪B) = A ， A∪(A∩B) = A； (5)交换律：A∩B= B∩A， A∪B= B∪A；(6)结合律：(A∩B) ∩C = A∩ (B∩C)， (A∪B) ∪C = A∪ (B∪C) ； (7)分配律：A∩(B ∪C) = (A∩B) ∪(A∩C) ，A∪(B ∩C) = (A∪B) ∩(A∪C) ； de Morgan律（也叫对偶律） 设A，B为两个集合。则 (1)( A∪B) = A∩B， (2)( A∩B) = A∪B。 差运算基本定理 　设X是全集，A，B，C是X的三个子集。则 (1)A\BA ； (2)ABA\B = ； (3)A\A = ； (4)X\A = A ；A\X = ； (5)A\ = A ；\A = ； (6)A∩(B\C)= (A∩B) \( A∩C) (交对差的分配律) ； (7)A\(B\C)=(A\B)∪(A∩C) ； (8)A\(B∪C) = (A\B) ∩(A\C) (相对补的de Morgan律)； (9) A\(B∩C) = (A\B)∪(A\C) (相对补的de Morgan律) 。环和运算基本定理 设X是全集，A，B，C是X的三个子集。则　　 (1)AB = (A∪B)\(A∩B) = (A∪B)∩(A∪B) ； (2)A = A （空集是环和的幺元）；　 AX = A ； (3)AA = （自己是自己（环和）的逆元）； AA= X ； (4)AB = AB ； (5)(AB) = AB = AB ； (6)交换律：AB = BA ； (7)结合律：A(BC) = (AB)C ； (8)分配律：A∩(BC) = (A∩B)(A∩C) (交对环和的)； (9)消去律：AB = AC B=C4. 叉积，笛卡尔积　 n个集合A1， A2， ，An的 n 维叉积定义为 =A1 × A2 × × An ={(a1, a2, , an): ai Ai(1i n)} ；　 n 维叉积A1 × A2 × × An的每个元素(a1, a2, , an)都称为一个n元组（n-tuple）；即，叉积是元组的集合； 　每个n元组(a1, a2, , an)的第i个位置上的元素ai称为该n元组的第i个分量（坐标或投影）；元组各分量的顺序不能改变；　 n 称为该叉积及其元组的维数；　 两个元组相等它们的维数相同且对应的分量相等。 即　　(a1, a2, , an)= (b1, b2, , bm) n=m(iN)(1i n)(ai = bi)；5. 叉积定义二： 二个集合A，B的(二维或二重)叉积定义为 A×B ={(a, b): a A bB} ；　其元素——二元组(a, b)通常称为序偶或偶对(ordered pair) ；　二元组(a, b)的第一分量上的元素a称为前者；第二分量上的元素b称为后者；　二重叉积的A B第一集合A称为前集；第二集合B称为后集。自反关系(reflexive relation)：当且仅当R满足　 自反性：(xX)(xRx) ；显然，对于自反关系R， (R) = (R) = X反自反关系(irreflexive relation)：当且仅当R满足　 反自反性：(x X)( ) 或(x X)(xRx) ；对称关系(symmetric relation)：当且仅当R满足　 对称性：(xX)