离散数学课件(第3章).pptVIP

《离散数学》教案;第二篇：集合论;第二篇：集合论;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;;根据定理1，空集是任意集合的子集，即??A；对任意集合A，A?A。一般地说，任意集合A至少有两个子集，一个是空集?，另一个是它本身A。

推论空集是惟一的。

证明：设有两个空集?1和?2，由定理1有?1??2和?2??1，根据集合相等的定义知，?1=?2。

【定义】在一个具体问题中，如果所涉及的集合都是某个集合的子集，那么称这个集合为全集。记为E。

全集是相对的，不同的问题有不同的全集。即使是同一问题也可以取不同的全集。;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;第三章：集合与关系;【定义】设R是A上的二元关系，n为自然数，R的n次幂记为Rn，定义为：

⑴R0=IA

⑵Rn+1=Rn°R

由该定义可以看出，A上的任何二元关系的0次幂都相等，等于A上的恒等关系IA。由该定义还可???看出：

R1=R0°R=IA°R=R

R2=R1°R=R°R

R3=R2°R=(R°R)°R

……

因为复合运算满足结合律，所以R3又可以写成：

R3=R°R°R

同样的道理Rn也可以写成：Rn=

;例如,在【例3.6.1】中

R2=R°R=??1,2?,?2,2??

S2=S°S=??4,5?,?3,3?,?1,1??

R3=R°R°R=??1,2?,?2,2??

【定理】设A是具有n个元素的有限集，R是A上的二元关系，那么必存在自然数s和t，使得Rs=Rt，0≤s＜t≤2。

证明：R是A上的二元关系，对任何自然数k，由复合关系的定义知，Rk仍然是A上的二元关系，即Rk?A×A。另一方面，A上的二元关系仅有2种。列出R的各次幂R0，R1，R2，…，，共有2＋1个，必存在自然数s和t，使得Rs=Rt，0≤s＜t≤2。;【例】A=?1,2,3,4?，A上的二元关系R定义如下：

R=??1,2?,?2,1?,?2,3?,?3,4??

求二元关系R的各次幂，验证定理4.2.5。

解：|A|=4

R0=IA=??1,1?,?2,2?,?3,3?,?4,4??

R1=R=??1,2?,?2,1?,?2,3?,?3,4??

R2=R1°R=R°R=??1,1?,?1,3?,?2,2?,?2,4??

R3=R2°R=??1,2?,?2,1?,?2,3?,?1,4??

R4=R3°R=??1,1?,?1,3?,?2,2?,?2,4??=R2，

0≤2＜4≤216=2

R5=R4°R=R2°R=R3

R6=R5°R=R3°R=R4=R2

……

R2n=R2

R2n+1=R3,n=1,2,3,…;【定理】设R是A上的二元关系，m，n为自然数，那么

⑴Rm°Rn=Rm+n

⑵(Rm)n=Rmn

证明：⑴对任意给定的m?N，关于n进行归纳证明：