离散概念和例题.docxVIP

PAGE24 / NUMPAGES24 集合 1.一个集合中的元素个数称为集合的基数。集合A的基数用|A|或card(A)表示 没有任何元素的集合称为空集合，简称为空集。 2.对于任意集合A，由A的所有不同子集为元素组成的集合称为集合A的幂集合（power set），简称为幂集，记作为P(A)或2A .如果|A|=n，则|P(A)|= 2n 3.对于任意集合A和全集U，由所有属于全集U但不属于集合A的元素组成的集合称为集合A的补集合（complement），简称为补集，记作为?A 对于集合A和B，证明A?B = (A–B) ? (B–A) 对于集合A、B和C，证明：如果A ? B = A ? C， 则B = C 关系 由两个元素x和y按照一定的次序排列成的二元组称为一个有序对或序偶，记作x, y 在一个序偶中，如果两个元素不相同，那么它们是不能交换次序的，称为序偶元素的有次序性，简称为有序性 由n个元素a1，a2，a3，…，an按照一定次序组成的n元组称为n元序???（ordered n-tuple），记为a1, a2, a3, …, an 对于集合A和B，以A中元素为第一元素，B中元素为第二元素组成序偶，所有这样的序偶组成的集合称为A和B的笛卡尔积（Cartesian product），记作A?B，形式化表示为 A?B = {x, y| x?A，y?B} 例2.2：设A={a}，B={b, c}，C=? ，D={1, 2}，列写出笛卡尔积A?B、B?A、A?C、C?A、A?(B?D)和(A?B)?D中的元素。 解：A?B ={a, b，a, c} B?A ={b, a, c, a} A?C= C?A = ? B?D ={b, 1, c, 1, b, 2, c, 2} A?(B?D) ={a, b, 1, a, c, 1, a, b, 2, a, c, 2} (A?B)?D = {a, b, 1, a, b, 2, a, c, 1, a，c, 2} 对于任意集合A、B、C和D，如果A?C且B?D，那么 A?B ? C?D。 如果一个集合的全体元素都是序偶，则称这个集合为一个二元关系，简称为关系，记作R。 对于某个二元关系R,若x, y?R，则称x与y以R相关，也常记为xRy,如果x，y?R，则称x与y不以R相关，记作x-R-y。 设|A|=n, |B|=m,A到B总共可能有多少个不同的二元关系 ？ |A?B|=m?n，集合|P(A?B)|=2 m?n次方,所以，从A到B的关系有2 m?n次方个 |A|=n, A上总共可能有多少个不同的二元关系 ？ |A?B|=n.n，集合|P(A?A)|=2 n.n次方所以，A上的关系有2 n?n次方个 空关系：对于任意集合A,空集 ?称为A 上的空关系 全关系：当R={x, y | x?A,y?A}, 即R=A2时，称R为A上的全关系，记为EA 恒等关系：设R是A上的二元关系，且满足R={x, x | x?A}，则称R是A上的恒等关系，记作IA 例2.7:对于A= {1, 2, 3}，试列写出A上的全域关系和恒等关系。 解: A上的全域关系为 EA={1, 1 , 1, 2, 1, 3, 2, 1, 2, 2, 2, 3, 3, 1, 3, 2, 3, 3}； A上的恒等关系为 IA={1, 1 , 2, 2，3, 3} 对于n个非空集合A1、A2、A3、…、An，称笛卡尔积A1?A2?A3?…?An的任意子集为依赖于A1?A2?A3?…?An的n元关系 对于集合A上的关系R，如果任意元素(所有元素)x?A，都有x, x?R，那么称集合A上的关系R具有自反性 如果任意元素(所有元素)x?A，都有x, x?R，那么称集合A上的关系R具有反自反性 设R为集合A上的关系，对于任意元素x?A和y?A，如果x, y?R，那么y, x?R，则称集合A上的关系R具有对称性 对于任意元素x?A和y?A，如果仅当x = y时，x, y?R且y, x?R，则称集合A上的关系R具有反对称性 自反性反自反性对称性反对称性传递性定义对于所有a?A都有 a,a?R对于所有a?A都有 a,a?R若a,b?R, 则有b,a?R若a,b?R并且b,a?R, 则有a=b若a,b?R并且b,c?R, 则有a,c?R集合IA?RR∩IA=?R=R-1R∩R-1?IAR2?R关 系 图图中每个结点都有环图中每个结点都无环任意两个不同的结点间(要么没有弧，要么有方向相反的一对弧)。任意两个结点间至多有一条弧若a到b有弧，b到c有弧，则a到c有弧关 系 矩 阵主对角线上全为1主对角线上全为0对称阵反对称阵(rij和rji不