离散数学课件-第4章.ppt

1 离散数学 Discrete Mathematics 汪荣贵贵 教授 合肥工业业大学软软件学院专专用课课件 2010.05 Chapter 4Chapter 4 Sets and Relations bBijk, 则 j=1; cBijk, 则 k=1;否 则为0。 如a,b,c,d 子集 B9 = B1001 =a,d a,c,d= B1011 = B11 【example】集合0，1，2的幂集合是什么？ Solution： 幂集合P(0,1,2)是0，1，2所有子集的集合。因此 P(0,1,2)=,0,1,2,0,1,0,2,1,2,0,1,2 注意：空集和0，1，2自身都是这个子集集合的成员。 【example】空集的幂集合是什么？集合的幂集合是什么？ Solution： 空集只有一个子集，这就是它自己。因此 P()= 集合有两个子集，即和集合自身。于是 P()=, & 集合的基本知识 集合的集合的基本概念及表示方法 集合间的关系 特殊集合 集合的运算 一.交运算 1. 定义：A、B是集合，由既属于A，也属于B的元素 构成的集合 ,称之为A与B的交集,记作AB。 例如A=1,2,3 B=2,3,4，则AB=2,3 集合的运算 谓词定义： AB=x|xAxB xAB xAxB 如果AB=，则称A与B不相交。 AB AB 2.性质 幂等律 对任何集合A，有AA=A。 交换律 对任何集合A、B，有AB=BA。 结合律 对任何集合A、B、C，有 (AB)C=A(BC)。 同一律 对任何集合A，有AE=A。 零律 对任何集合A，有A=。 AB AB=A。 下面只对性质进行证明。 Solution： AB=A x(xAB xA) x(xAB xA)(xA xAB) x(aABxA)(xAxAB) x(xAxB)xA) (xA(xAxB) x(xAxB)xA) (xA(xAxB) x(T(T ( xA xB) x( xA xB) x(xAxB) AB AB AB=A。 【example】集合1，3，5和1，2，3的交集是1，3， 即 1，3，51，2，3=1，3 【example】学校所有主修计算机科学的学生集合与所有主修数 学的学生的集合的交集，是所有即主修计算机科学又主修数 学的学生的集合。 二.并运算 1.定义：A、B是集合，由或属于A，或属于B的元 素构成的集合 ,称之为A与B的并集,记作AB。 例如 A=1,2,3 B=2,3,4 AB=1,2,3,4 谓词定义： AB =x|xAxB xAB xAxB B AB A 2.性质 幂等律 对任何集合A，有AA=A。 交换律 对任何集合A、B，有AB=BA。 结合律 对任何集合A、B、C，有 (AB)C=A(BC)。 同一律 对任何集合A，有A=A。 零律 对任何集合A，有AE =E 。 分配律 对任何集合A、B、C，有 A(BC) =(AB)(AC)。 A(BC) =(AB)(AC)。 吸收律 对任何集合A、B，有 A(AB)=A A(AB) =A。 证明: A(AB) = (AE)(AB) (同一) = A(EB) (分配) = AE=A (零律) (同一) AB AB=B。 【example】集合1，3，5和集合1，2，3的并集是集合1， 2，3，5， 即 1，3，51，2，3=1，2，3，5 【example】学校主修计算机科学的学生机和与主修数学的学生 集合的并集，是或主修数学、或主修计算机科学或同时主修 这两门课的学生的集合。 三. 差运算- (相对补集) 1.定义：A、B是集合，由属于A，而不属于B的元素构 成的集合 ,称之为A与B的差集,或B对A的相对补集， 记作A-B。 例如 A=1,2,3 B=2,3,4 A-B=1 谓词定义： A-B =x|xAxB xA-B xAxB AB A-B 2.性质 设A、B、C是任意集合，则 A-=A -A= A-A= A-BA AB A-B= (A-B)-C=(A-C)-(B-C) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) A(B-C)=(AB)-(AC) 注意：对- 是不可分配的，如A(A-B)=A 而(AA)-(AB)= 证明性质6 (A-B)-C=(A-C)-(B-C) proof：任取x(A-C)-(B-C) x(A-C)x(B-C) (xAxC)(xBxC) (xAxC) (xBxC) (xAxCxB)(xAxC xC) xAxCxB xAxBxC (xAxB)xC xA-BxCx(A-B)-C 所以 (A-B)-C=(A-C)-(B-C) 证明性质8 A-(BC)=(A-B)(A-C) Proof： 任取xA-(BC) xAx(BC) xA(xBxC) xA(xBxC) (xAxB)(xAxC ) xA-BxA-C x(A-B)(A-C) 所以 A-(BC)=(A-B)(A-C) 【example】集合1，3，5和1，2，3的差集是5； 即 1，3，5-1，2，3=5 这等同于1，2，3和1，3，5的差集是2。 【example】学校主修计算机科学的学生集合和主修数学的学生 集合的差集是学校主修计算机科学但不主修数学的学生集合。 四. 绝对补集 1.定义：A是集合,由不属于A的元素构成的集合, 称之为A的 绝对补集,记作A。 实际上 A=E-A。 例如，E=1,2,3,4 A=2,3,A=1,4 谓词定义： A =E-A=x|xEx A = x|x A xA xA AA E 2.性质 设A、B、C是任意集合，则 E= =E (A)=A AA= AA=E A-B=AB (AB)=AB (AB)=AB AB BA A=B 当且仅当AB=E且 AB= proof：任取x (AB) x (AB) xAB(xAxB) (xAxB)xAxB x AB (AB)=AB proof ： AB x(xAxB) x(xBxA)x(xBxA) BA proof： AB=EAB= x(xABxE) (PT=P) x(xABx) (PF=P) x(xABT)x(xABF) x(xAB(xAB) x(xAxB)(xAxB) x(xAxB)(xAxB) x(xAxB)(xBxA) x(xAxB)(xBxA) x(xAxB) A=B 【example】令A=a, e, I, o , u (全集为英文字母)。那么 A=b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, u, v, w, x, y, z 【example】令A为大于10的正整数的集合（全集为正整数集合） 。那么 A=1，2，3，4，5，6，7，8，9，10 五. 对称差 1.定义：A、B是集合,由属于A而不属于B，或者 属于B而不属于A的 元素构成的集合,称之为A 与B的对称差,记作AB。 例如 A=1,2,3 B=2,3,4 AB=1,4 谓词定义： AB=(A-B)(B-A) =x|(xAxB)(xBxA) AB=(AB)-(AB) AB AB 2.性质 交换律 对任何集合A、B，有AB=BA。 结合律 对任何集合A、B、C，有 (AB)C=A(BC)。 此式证明较繁，教材里有证明，这里从略。 同一律 对任何集合A，有A=A。 对任何集合A，有AA=。 对可分配 A(BC)=(AB)(AC) proof： (AB)(AC) = (AB)(AC)-(AB)(AC) = (A(BC)-(ABC) = A(BC)-(BC) (对-分配) = A(BC) 集合恒等式 一 定义：一组集合的并集是是包含那些至少是这组集合中一 个集合成员的元素的集合。 用记号 表示集合A1,A2,An 的并集。 六 扩扩展的并运算 【Example】令A=0,2,4,6,8，B=0,1,2,3,4，C=0,3,6,9。 ABC 是什么集合？ Solution： ABC包括那些至少属于A,B,C之一的元素。所以 ABC=0，1，2，3，4，6，8，9 七 扩展的交运算 一 定义：一组集合的交集是包含那些属于这组集合中所有成 员集合的元素的集合。 用记号 表示集合A1,A2,An的交集。 【example】令A=0,2,4,6,8，B=0,1,2,3,4，C=0,3,6,9 ABC是什么集合？ Solution： 集合ABC是包括那些属于全部三个集合的元素。因此 ABC=0 计算机表示集合的方式各种各样。 一种方法就是把集合的元素无序地存储起来。这 样的话，在做集合的并集交集或差集等运算时会浪 费事件。 现在介绍一种利用全集元素的一个任意排序 存放元素以表示集合的方法。 计计计计算机表示集合的方法算机表示集合的方法 具体的方法为： 假定全集U是有限的（而且大小合适，使U 得元素个数不超 过计算机能使用的内存量）。 首先为U的元素任意规定一个顺序，例如a1,a2,an. 于是可以用长度为n的位串表示U的子集A: 如果ai属于A,则位串中第i位是1： 如果ai不属于A，则位串中第i位是0. 【example】令U=1, 2, 3, 4, 5, 6, 7, 8, 9, 10,并且U的元素从 小到大排序，即ai=i。 表示U中所有奇数的子集、所有偶数的子集和不超过5的整数的 子集的位串是什么？ Solution： 表示U中所有奇数的子集即1，3，5，7，9的位串，其第1 、3、5、7、9位为1，其他位为0，即 10 1010 1010 （我们已把长度为10的位串分成长度为5的两段以便阅读，因 为长位串不易读）。类似地，U中所有偶数的子集即 2，4，6，8，10，由位串 01 0101 0101 表示。U中不超过5的所有整数的集合即1，2，3，4，5，由位 串 11 1110 0000 表示。 【example】我们已经知道集合1，3，5，7，9的位串（全集 为1，2，3，4，5，6，7，8，9，10）是 10 1010 1010 它的补集是什么？ Solution： 用0代替1，用1代替0，即可得到次集合的补集的位串 01 0101 0101 这对应着集合2，4，6，8，10。 注：要得到两个集合的并集和交集的位串，我们可以对表示着两 个集合的位串按位做布尔运算。 只要两个位串的第i字位有一个是1，则并集的位串的第i位是1 ，当两个字位都是0时为0.因此，并集的位串是两个集合位串的 按位或。 当两个位串的第i字位均为1时，交集的位串第i为位1，否则为 0.因此交集的位串是两个集合位串的按位与。 【exampl