离散数学(杨圣洪版)-第3章-复习总结

离散数学第三章复习与总结第三章复习与总结基本概念计算方法基本概念集合：子集、幂集、集合的运算(交叉并补)性质：幂等律 AA=A，AA=A结合律 ABC=A(BC)=(AB)CABC=A(BC)=(AB)C交换律 AB=BAAB=BA分配律 A(BC)=(AB)(AC)A(BC)=(AB)(AC)同一/零律 A=A A=排中/矛盾律 AA=EAA=吸收律(大吃小) A(BA)=A,A(BA)=A德摩律 (AB)=AB(AB)=AB双重否定 A=A

基本概念序偶

定义3.4.1将具有次序的两对象写在一块，称为序偶即有秩序的二个对象，记为<对象1，对象2>或<x,y>。三元组、n元组

定义3.4.3如果<x,y>是序偶，且<<x,y>,z>也是一个序偶，则称<x,y,z>为三元组。

定义3.4.4如果<x1,x2,…,xn-1>是n-1元组，而<<x1,x2,…,xn-1>,xn>是序偶，则称为<x1,x2,…,xn-1,xn>为n元组。笛卡尔积关系

将笛卡尔积中前后两个元素之间存在某种关系的序偶检出来,便得到一个关系。基本概念关系矩阵、关系图123abc基本概念关系复合

设F,G为二元关系,G对F的右复合记为FG,定义

FG={<x,y>|t(<x,t>F,<t,y>G)}

乘法是合取，加法是析取，复合性质：(1)结合律 (PR)S=P(RS)；(2)复合的逆 (PR)-1=R-1P-1；

(3)不满足交换率；基本概念关系的性质与分类

自反关系:xA<x,x>RIAR

反自反关系:xA<x,x>RIAR=

对称关系:<x,y>R<y,x>RR=R-1

反对称关系:<x,y>R,<y,x>Rx=y

<x,y>R且xy<y,x>RRR-1IA

传递关系:<x,y>R,<y,z>R<x,z>RR2R

自反:主对角线均为1反自反:主对角线均为0

对称:M=MT。反对称：MMT后只有主对角非0

传递:R2R即M2M基本概念等价关系

自反、对称、可传递的关系称为等价关系。等价类

彼此有等价关系的元素的集合,称为等价类.

如：{1、4、7}，{2、5、8}，{3、6}商集

设RAA，R是等价关系，A0,A1,…,Ak是基于R得到的等价类，则称集合{A0,A1,…,Ak}为A关于R的商集，记为A/R。

如：A={1、2、3、4、5、6、7、8}，R={<x,y>|x-y=3k}划分

若A=A0A1…Ak,且不相交,则称A的划分。基本概念偏序关系

自反、反对称、可传递的关系。广义的“小于等于”关系，记为。全序(线序):

x,yA，x与y都可比。偏序集<A,>：<集合A、偏序关系>。如:A={,{1,2}}

R1={<x,y>:xy,xA,yA},

<A,R1>

A={,{1},{2},{1,2}}R2={<x,y>:xy,xA,yA},<A,R2>哈斯图

去掉箭头;

去掉自旋箭头;

去掉复合边;盖住:

xA,yA,x<y,

zA,使得x<z<y,则称y盖住x.{1,2}{1}{2}{1,2}{1}{2}基本概念最大元、最小元、极大元、极小元

设<A,R>是偏序集，BA,y0B,若xB,均有<x,y0>R，则y0是B的最大元。

极大元:不存在x使<y0,x>R.上界、下界、上确界、下确界

在偏序集<A,R>中，BA，yA，若任意xB都有<x,y>R，则称y是B的上界。

在偏序集<A,R>中，BA，设C为B的所有上界元的集合，若C中有最小元则该最小元称为B的上确界abcgdfeh123574869第三章复习与总结基本概念计算方法笛卡尔积与复合的算法：乘法是合取，加法是析取，算法：性质：(1)结合律 (PR)S=P(RS)(2)复合的逆 (PR)-1=R-1P-1MRS=MR

MS=[Cij]计算方法集合计数

|A1A2

…

|

=

|Ai|-|AiAj|

+|AiAjAk|

-

|AiAjAkAL|

….

+(-1)n-1|A1A2…An|例题在[1,300]整数中能被3或5或7整除的整数的个数。解：A3示能被3整除的数,A5能被5整除,A7能被7整除.能被3整除的个数：|A3|=300/3=100能被5整除的个数：|A5|=300/5=60能被7整除的个数：|A7|=300/7=42能被3与5同时整除的个数：|A3A5|=300/15=20能被3与7同时整除的个数：|A3A7|=300/21=100/7=14能被5与7同时整除的个数：|A5A7|=300/35=60/7=8能被3、5、7同时整除的个数：|A3A5A7|=2能被3或被5或被7整除的个数：|A3A5A7|=|A3|+|A5|+|A7|-|A3A5|-|A3A7|-|A5A7|+|A3A5A7|=100+60+42-20-14-8+2=162计算方法闭包的计算：自反闭包：r(R)=RIA对称闭包：s(R)=RRT传递闭包：t(R)=RR2R3...Rn-1.任何两点最多n-1步

=MM2M3...Mn-1.t(R)=RR2R3...Rn-1.任何两点最多n-1步达=MM2M3...Mn-1.例A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}t(R)={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<a,a>,<a,c>,<b,b>,<b,d>,<c,b>,<d,a>,<d,c>,<a,b>,<a,d>,<b,a>,<b,c>,<b,b>,<c,a>,<c,c>,<d,b>,<d,d>}abcdt(R)=RR2R3...Rn-1.任何两点最多n-1步达=MM2M3...Mn-1.效率比较低！Warshall算法for(j=1;j<n;j++){//第1列到最后列for(i=1;i<n;i++{//第j列从第1行到最后行if(M(i,j)=1){第i行=第i行第j行;}}}计算方法等价关