離散數(shù)學(楊圣洪版)-第3章-復(fù)習總結(jié)

離散數(shù)學第三章復(fù)習與總結(jié)第三章復(fù)習與總結(jié)基本概念計算方法基本概念集合：子集、冪集、集合的運算(交叉并補)性質(zhì)：冪等律 AA=A，AA=A結(jié)合律 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元組。笛卡爾積關(guān)系

將笛卡爾積中前后兩個元素之間存在某種關(guān)系的序偶檢出來,便得到一個關(guān)系?；靖拍铌P(guān)系矩陣、關(guān)系圖123abc基本概念關(guān)系復(fù)合

設(shè)F,G為二元關(guān)系,G對F的右復(fù)合記為FG,定義

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

乘法是合取，加法是析取，復(fù)合性質(zhì)：(1)結(jié)合律 (PR)S=P(RS)；(2)復(fù)合的逆 (PR)-1=R-1P-1；

(3)不滿足交換率；基本概念關(guān)系的性質(zhì)與分類

自反關(guān)系:xA<x,x>RIAR

反自反關(guān)系:xA<x,x>RIAR=

對稱關(guān)系:<x,y>R<y,x>RR=R-1

反對稱關(guān)系:<x,y>R,<y,x>Rx=y

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

傳遞關(guān)系:<x,y>R,<y,z>R<x,z>RR2R

自反:主對角線均為1反自反:主對角線均為0

對稱:M=MT。反對稱：MMT后只有主對角非0

傳遞:R2R即M2M基本概念等價關(guān)系

自反、對稱、可傳遞的關(guān)系稱為等價關(guān)系。等價類

彼此有等價關(guān)系的元素的集合,稱為等價類.

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

設(shè)RAA，R是等價關(guān)系，A0,A1,…,Ak是基于R得到的等價類，則稱集合{A0,A1,…,Ak}為A關(guān)于R的商集，記為A/R。

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

若A=A0A1…Ak,且不相交,則稱A的劃分。基本概念偏序關(guān)系

自反、反對稱、可傳遞的關(guān)系。廣義的“小于等于”關(guān)系，記為。全序(線序):

x,yA，x與y都可比。偏序集<A,>：<集合A、偏序關(guān)系>。如:A={,{1,2}}

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

<A,R1>

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

去掉箭頭;

去掉自旋箭頭;

去掉復(fù)合邊;蓋住:

xA,yA,x<y,

zA,使得x<z<y,則稱y蓋住x.{1,2}{1}{2}{1,2}{1}{2}基本概念最大元、最小元、極大元、極小元

設(shè)<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，設(shè)C為B的所有上界元的集合，若C中有最小元則該最小元稱為B的上確界abcgdfeh123574869第三章復(fù)習與總結(jié)基本概念計算方法笛卡爾積與復(fù)合的算法：乘法是合取，加法是析取，算法：性質(zhì)：(1)結(jié)合律 (PR)S=P(RS)(2)復(fù)合的逆 (PR)-1=R-1P-1MRS=MR

MS=[Cij]計算方法集合計數(shù)

|A1A2

…

|

=

|Ai|-|AiAj|

+|AiAjAk|

-

|AiAjAkAL|

….

+(-1)n-1|A1A2…An|例題在[1,300]整數(shù)中能被3或5或7整除的整數(shù)的個數(shù)。解：A3示能被3整除的數(shù),A5能被5整除,A7能被7整除.能被3整除的個數(shù)：|A3|=300/3=100能被5整除的個數(shù)：|A5|=300/5=60能被7整除的個數(shù)：|A7|=300/7=42能被3與5同時整除的個數(shù)：|A3A5|=300/15=20能被3與7同時整除的個數(shù)：|A3A7|=300/21=100/7=14能被5與7同時整除的個數(shù)：|A5A7|=300/35=60/7=8能被3、5、7同時整除的個數(shù)：|A3A5A7|=2能被3或被5或被7整除的個數(shù)：|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行;}}}計算方法等價關(guān)