离散数学：第2讲集合恒等式.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,集合,集合之间的关系,相等、子集、真子集,空集、全集,幂集、,n,元集、有限集,集合的运算,交,并,补,对称差,2,子集,(,),若,AB,且,BC,则,AC,证明,:A,B x(xAxB),x,xA,xB (AB),xC (BC),x(xAxC),即,AC.#,3,第,2,讲,集合恒等式,内容提要,集合恒等式与证明,对偶原理,容斥原理,4,集合恒等式,(,关于,与,),等幂律,(idempotent laws),A,A=A,A,A=A,交换律,(commutative laws),A,B=B,A,AB=B,A,5,集合恒等式,(,关于,与,、续,),结合律,(associative laws),(A,B),C=A,(B,C),(A,B),C=A,(B,C),分配律,(distributive laws),A,(B,C)=(A,B),(A,C),A,(B,C)=(A,B),(A,C),6,集合恒等式,(,关于,与,、续,),吸收律,(absorption laws),A,(A,B)=A,A,(A,B)=A,7,集合恒等式,(,关于,),双重否定律,(double complement law),A=,A,德,摩根律,(DeMorgan,s laws),(A,B)=,A,B,(A,B)=,A,B,8,集合恒等式,(,关于,与,E,),零律,(dominance laws),A,E=E,A,=,同一律,(identity laws),A,=A,A,E=,A,9,集合恒等式,(,关于,E),排中律,(excluded middle),A,A=E,矛盾律,(contradiction),A,A=,全补律,=E,E,=,10,集合恒等式,(,关于,-),补交转换律,(difference as intersection),A-B=A,B,11,集合恒等式,(,推广到多个集合,),分配律,德,摩根律,12,集合恒等式证明,(,方法,),逻辑演算法,:,利用逻辑等值式和推理规则,集合演算法利用集合恒等式和已知结论,13,逻辑演算法,(,格式,),题目,:A=B.,证明,:x,x,A,(?),x,B,A=B.#,题目,:AB.,证明,:x,x,A,(?),x,B,A,B.#,14,分配律,(,证明,),A,(B,C)=(A,B),(A,C),证明,:,x,x,A,(B,C),xA x,(B,C)(,定义,),xA (x,B,x,C)(,定义,),(xAx,B),(xAx,C)(,命题逻辑分配律,),(xA,B),(xA,C)(,定义,),x(A,B),(,A,C)(,定义,),A,(B,C)=(A,B),(A,C),15,补交转换律,(,证明,),A-B=A,B,证明,:,x,xA-B,xA xB,xA xB,xAB,A-B=A,B,.#,16,、,性质,(,证明,),A,B,A,证明,:,x,x,A,B,xA x,B,(,定义,),xA,(,命题逻辑化简,),A,B,A,A,A,B,证明,:,x,x,A,xA x,B,(,命题逻辑附加,),xA,B(,定义,),A,A,B,17,集合演算法,(,格式,1),题目,:A=B.,证明,:(),A,B,(,),A,B,A=B.#,题目,:AB.,证明,:,A,B(,或,A,B),=,(?),=A(,或,B),A,B.#,说明,:,分,=,成,与,说明,:,化,成,=(,需要证明,),A,B=A,AB,A,B=B,AB18,零律,(,证明,),A,=,证明,:,(),A,（,性质）,(,),(,性质,),A,(,性质,),A,（,性质）,A,=,19,吸收律,(,证明,),A,(A,B)=A,证明,:,(),A,A (,集合自反性,),A,B,A (,性质,),A,(A,B),A (,性质,),(,)A,A,(A,B)(,性质,),A,(A,B)=A,A,B,20,A,B=A,AB,x,x,A,x,A,B,x,B,A,B.#,A,B,A (,性质,),A A,A,B,A,A,B(,子集性质,),A,B=A,.#,21,集合演算法,(,格式,2),题目,:A=B.,证明,:,A,=,(?),=,B,A=B.题目,:AB.,证明,:,A,(?),B,A,B.#,22,德,摩根律的相对形式,A-(B,C)=(A-B),(A-C),A-(B,C)=(A-B),(A-C),证明,:A-(B,C),=A,(B,C)(,补交转换律,),=A,(,B,C)(,德,摩根律,),=(A,A)(,B,C)(,等幂律,),=(A,B,)(A,C)(,交换律,结合律,),=(A-B),(A-C)(,补交转换律,).#,23,对称差的性质,交换律,:AB=BA,结合律,:A(BC)=(AB)C,分配律,:A(BC)=(AB)(AC),A=A,AE=A,AA=,AA=E,24,对称差的性质,(,证明,2),结合律,:ABC)=(AB)C,证明思路：,分解成,“基本单位”,例如,:,1.A,BC,2.,A,BC,3.,A,B C,4.A,BC,A,B,C,ABC,1,2,3,4,25,对称差的性质,(,证明,2,、,续,1,),结合律,:A(BC)=(AB)C,证明,:,首先,A,B=(A-B)(B-A)(,定义,),=(AB)(BA)(,补交转换律,),=(AB)(AB)(,交换律,)(*),A,B,A,B,26,对称差的性质,(,证明,2,、,续,2,),其次,A,(BC),=(A(BC)(A(BC)(*),=(A(BC)(BC),(A(BC)(BC)(*),=(A(BC)(BC),(A(BC)(BC)德,摩根律,),27,对称差的性质,(,证明,2,、,续,3,),=(A(BC)(BC),(A(BC)(BC),=(A(BC)(BC),(A(BC)(BC)(,德,摩根律,),=(ABC)(ABC),(ABC)(ABC)(,分配律,),28,对称差的性质,(,证明,2,、,续,4,),同理,(AB)C,=(AB)C)(AB)C)(*),=(AB)(AB)C),(AB)(AB),C,)(*),=(AB)(AB)C),(AB)(AB),C,)(,德,摩根律,),29,对称差的性质,(,证明,2,、,续,5,),=(AB)(AB)C),(AB)(AB),C,),=(AB)(AB)C),(AB)(AB),C,)(,德,摩根律,),=(AB,C,)(AB,C,),(ABC)(ABC)(,分配律,),A(BC)=(AB)C.#,30,对称差的性质,(,讨论,),消去律,:,A,B=,A,C B=C,A=B,C B=AC C=AB,对称差与补,:(AB)=AB=AB,AB=AB,问题,:A,BC=,A,BC?,有些书中用,表示对称差,:,A,B=A,B,31,对称差的性质,(,证明,3),分配律,:A(BC)=(AB)(AC),证明,A(BC),=A(BC)(BC),=(ABC)(ABC),A,B,C,A(BC),32,对称差分配律,(,证明,3,、续,),(,续,)(AB)(AC),=(AB)(AC)(AB)(AC),=(AB)(AC)(AB)(AC),=(ABC)(ABC),A(BC)=(AB)(AC).#,33,对称差分配律,(,讨论,),A(BC)=(AB)(AC),A(BC)=(AB)(AC),A(BC)=(AB)(AC),A(BC)=(AB)(AC),?,?,?,34,对偶,(dual),原理,对偶式,(dual):,一个集合关系式,如果只含有,E,=,那么,同时把,与,互换,把,与,E,互换,把,与,互换,得到的式子称为原式的对偶式,.,对偶原理,:,对偶式同真假,.,或者说,集合恒等式的对偶式还是恒等式,.,35,对偶原理,(,举例,),分配律,A,(B,C)=(A,B),(A,C),A,(B,C)=(A,B),(A,C),排中律,A,A=E,矛盾律,A,A=,36,对偶原理,(,举例、续,),零律,A,E=,E,A,=,同一律,A,=A,A,E=A,37,对偶原理,(,举例、续,),A,B,A,A,B,A,A,E,A,38,容斥原理,(,principle of inclusion/exclusion,),容斥原理,(,或包含排斥原理,),|A,B|=|A|+|B|-|AB|,39,容斥原理,(,证明,),n=2,时的情况,:,|A,B|=|A|+|B|-|AB|,归纳证明,:,以,n=3,为例,:,|A,B C|=,|(A,B)C|=|AB|+|CAB)C|,=|A|+|B|-|AB|+|C|-|(AC)(BC)|,=|A|+|B|-|AB|+|C|,-(|AC|+|BC|-|(AC)(BC)|),=|A|+|B|+|C|-|AB|-|AC|-|BC|,+|ABC|,A,B,B,C,A,40,容斥原理,(,举例,),例,1:,在,1,到,10000,之间既不是某个整数的平方,也不是某个整数的立方的数有多少,?,解,:,设,E=x,N|1x10000,|E|=10000,A=x,E|x=k,2,kZ,|A|=100,B=x,E|x=k,3,kZ,|B|=21,则,|(A,B,)|=|E|-|A,B|,=,|E|-(,|A|+|B|AB|),=10000-100-21+4=9883,注意,AB=,x,E|x=k,6,kZ,|AB|=4.#,41,容斥原理,(,举例、续,),例,2:,在,24,名科技人员中,会说英,日,德,法语的人数分别为,13,5,10,和,9,其中同时会说英语,德语,或同时会说英语,法语,或同时会说德语,法语两种语言的人数均为,4.,会说日语的人既不会说法语也不会说德语,有两人会说英语,.,试求只会说一种语言的人数各为多少,?,又同时会说英,德,法语的人数有多少,?,解,:,设,E=x,|x,是,24,名科技人员之一,|E|=24,A=x,E|x,会说英语,B=x,E|x,会说日语,C=x,E|x会说德语,D=x,E|x,会说法语,42,容斥原理,(,举例、续,),解,(,续,):,设所求人数分别为,x,1,x,2,x,3,x,4,x(,如图,),A=x,E|x,会说英语,|A|=13,B=x,E|x,会说日语,|B|=5,C=x,E|x,会说德语,|C|=10,D=x,E|x,会说法语,|D|=9,首先,x,2,=|B|-|A,B|=,5-2=3,其次,对,A,C,D,用容斥原理,注意,|E|=24:,24-3=21=13+10+9-4-4-4+x=20+x,得,x=1,最后,x,1,=|A|-|A,B|,-3-3-1=13-2-7=4,同理,x,3,=10-3-3-1=3,x,4,=9-3-3-1=2.#,D,C,B,A,X,X,1,X,2,X,3,X,4,4-X,4-X,4-X,2,43,作业,P99 20-,