離散數學第三章復習與總結第三章復習與總結基本概念計算方法基本概念集合：子集、冪集、集合的運算(交叉并補)性質：冪等律 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行;}}}計算方法等價關