離散數(shù)學(xué)重要公式定理匯總

1、大一上離散數(shù)學(xué)重要公式定理匯總2022-7-12 基本的等價(jià)公式基本的等價(jià)公式 對(duì)合律對(duì)合律 P PP P 冪等律冪等律 P PP PP PP PP PP P 結(jié)合律結(jié)合律 P P(QQR)R)( (P PQ)Q)R R P P(QQR)R)( (P PQ)Q)R R 交換律交換律 P PQQQQP PP PQQQQP P 分配律分配律 P P(QQR)R)( (P PQ)Q)(P PR) R) P P(QQR)R)( (P PQ)Q)(P PR)R) 吸收律吸收律 P P(P PQ)Q)P PP P(P PQ)Q)P P 德摩根定律德摩根定律 ( (P PQ)Q)P P Q Q ( (P P

2、Q)Q)P P QQFormula2022-7-13 同一律同一律 P PF FP PP PT TP P 零律零律 P PT TT PT PF FF F 互補(bǔ)律互補(bǔ)律 P P P PT T P P P PF F 附加：附加： P PQQP PQ Q P PQQQQP P P PQ Q ( (P PQ)Q)(Q(QP)P) P PQ Q ( ( P PQ)Q)(P(P Q) Q) P PQ Q ( (P PQ)Q)( ( P P Q )Q )Formula2022-7-14 等價(jià)公式等價(jià)公式( (前前1010個(gè)個(gè)) )與集合論的公式比較與集合論的公式比較： 對(duì)合律對(duì)合律 AAA AA A表示表示

3、A A的絕對(duì)補(bǔ)集的絕對(duì)補(bǔ)集 冪等律冪等律 A AA AA AA AA AA A 結(jié)合律結(jié)合律 A A(B BC)C)( (A AB)B)C C； A A(B BC)C)( (A AB)B)C C 交換律交換律 A AB BB BA AA AB BB BA A 分配律分配律 A A(B BC)C)( (A AB)B)(A AC) C) A A(B BC)C)( (A AB)B)(A AC)C) 吸收律吸收律 A A(A AB)B)A AA A(A AB)B)A A Formula2022-7-15德摩根定律德摩根定律 ( (A AB)B)A AB B ( (A AB)B)A AB B 同一律同一

4、律 A AA; AA; AE EA EA E表示全集表示全集 零律零律 A AE EE AE A 否定律否定律 A AA AE E A AA AFormula2022-7-16Definition永真永真( (重言重言) )式（式（TautologyTautology）公式中的命題變量元論公式中的命題變量元論怎樣指派，公式對(duì)應(yīng)的真值恒為怎樣指派，公式對(duì)應(yīng)的真值恒為T T。 永假（矛盾）式（永假（矛盾）式（Contradiction)Contradiction)公式中的命題變公式中的命題變量無(wú)論怎樣代入，公式對(duì)應(yīng)的真值恒為量無(wú)論怎樣代入，公式對(duì)應(yīng)的真值恒為F F。 可滿足公式（可滿足公式（Sat

5、isfactionSatisfaction）公式中的命題變量無(wú)公式中的命題變量無(wú)論怎樣代入，公式對(duì)應(yīng)的真值總有一種情況為論怎樣代入，公式對(duì)應(yīng)的真值總有一種情況為T T。一般命題公式（一般命題公式（ContingencyContingency）既不是永真公式也不既不是永真公式也不是永假公式。是永假公式。2022-7-173.重要的重言蘊(yùn)含式重要的重言蘊(yùn)含式(如教材第如教材第43頁(yè)所示頁(yè)所示) I1.PQP , I2. PQQ I3. PPQ I4. QPQ I5. PPQ I6. QPQ I7. (PQ)P I8. (PQ)Q I9. P,Q PQ I10. P(PQ)Q I11. P(PQ)Q

6、 I12. Q(PQ)P I13. (PQ)(QR)PR I14. (PQ)(PR)(QR)R I15. AB (AC)(BC) I16. AB (AC)(BC)Formula2022-7-18 蘊(yùn)含的性質(zhì)蘊(yùn)含的性質(zhì)* *若若A AB B且且A A為重言式，則為重言式，則B B必為重言式必為重言式* *若若A AB B且且B BC C，則，則A AC C (傳遞性傳遞性)* *若若A AB B且且A AC C，則，則A A(B B C C) * *若若A AB B且且C C B B，則，則(A AC C) B B證明見(jiàn)書證明見(jiàn)書P22P22Formula2022-7-19conjunction

7、一、全功能真值表一、全功能真值表PQ C1 C2 C3 C4 C5 C6 C7 C8TTTFTTFFTFTFTFTFFTFTFTTFFTTFFTFFTFFFTTFTPQC9C10 C11 C12 C13 C14 C15 C16TTTFTFTFTFTFTFFTFTTFFTTFTFFTFTFFFTTFTFTFPQccQP2022-7-1103.3.析取范式與合取范式的化法析取范式與合取范式的化法 化成限定性公式化成限定性公式。 公式公式E E16 16 P PQQP PQ Q 公式公式E E2121 P PQ Q ( (P PQ)Q)( ( P P Q) Q) 公式公式E E20 20 P PQ

8、Q ( (P PQ)Q)(Q(QP) P) 公式公式E E16 16 P PQ Q ( ( P PQ)Q)(P(P Q) Q) 將否定聯(lián)結(jié)詞移到命題變量的前面。將否定聯(lián)結(jié)詞移到命題變量的前面。 A(PA(P1 1,P,P2 2, ,P,Pn n) )A A* *( ( P P1 1, , P P2 2, , , P Pn n) ) ( (P PQ)Q)P P Q Q 、 ( (P PQ)Q)P P QQ 用分配律、冪等律等公式進(jìn)行整理，使之成為所用分配律、冪等律等公式進(jìn)行整理，使之成為所要求的形式。要求的形式。 normal form2022-7-111v主析取范式定義主析取范式定義 析取范式

9、析取范式 A A1 1AA2 2.A.An, n, , , 其中每個(gè)其中每個(gè)A Ai i (i=1,2.n) (i=1,2.n)都是小項(xiàng)，稱之為都是小項(xiàng)，稱之為主析取范式主析取范式。思考：主析取范式與析取范式的區(qū)別是什么？思考：主析取范式與析取范式的區(qū)別是什么？v主析取范式的寫法主析取范式的寫法 方法方法：列真值表列真值表 列出給定公式的真值表。列出給定公式的真值表。 找出真值表中每個(gè)找出真值表中每個(gè)“T”T”對(duì)應(yīng)的真值指派再對(duì)對(duì)應(yīng)的真值指派再對(duì)應(yīng)的小項(xiàng)。應(yīng)的小項(xiàng)。用用“”聯(lián)結(jié)上述小項(xiàng)，即可。聯(lián)結(jié)上述小項(xiàng)，即可。normal form2022-7-112v主合取范式定義主合取范式定義 合合取范

10、式取范式 A A1 1AA2 2. A. An, n, , , 其中每個(gè)其中每個(gè)A Ai i (i=1,2.n) (i=1,2.n)都是大項(xiàng)，稱之為都是大項(xiàng)，稱之為主合取范式。主合取范式。v主合取范式的寫法主合取范式的寫法 方法方法：列真值表列真值表 列出給定公式的真值表。列出給定公式的真值表。 找出真值表中每個(gè)找出真值表中每個(gè)“F”F”對(duì)應(yīng)的真值指派再對(duì)應(yīng)對(duì)應(yīng)的真值指派再對(duì)應(yīng)的大項(xiàng)。的大項(xiàng)。 用用“”聯(lián)結(jié)上述大項(xiàng)，即可。聯(lián)結(jié)上述大項(xiàng)，即可。normal form2022-7-113Brief Summary第一章第一章 小結(jié)小結(jié) 命題命題原子命題原子命題復(fù)合命題復(fù)合命題聯(lián)結(jié)詞聯(lián)結(jié)詞命題公式命

11、題公式永真式永真式永真蘊(yùn)涵式永真蘊(yùn)涵式等價(jià)公式等價(jià)公式范式范式命題邏輯推理命題邏輯推理直接推理直接推理間接推理間接推理?xiàng)l件論證條件論證反證法反證法析取析取合取合取主析取主析取主合取主合取知識(shí)網(wǎng)絡(luò)：知識(shí)網(wǎng)絡(luò)：2022-7-114 如果是個(gè)不含客體變?cè)獂的謂詞公式，且不在x和x的轄域內(nèi)，可以將放入x和x的轄域內(nèi)。即得如下公式： 1. xA(x)Bx(A(x)B) 2. xA(x)Bx(A(x)B) 3. xA(x)Bx(A(x)B) 4. xA(x)Bx(A(x)B) 5. BxA(x)x(BA(x) 6. BxA(x)x(BA(x) 7. xA(x)Bx(A(x)B) 8. xA(x)Bx(A(

12、x)B) 量詞轄域的擴(kuò)充公式2022-7-1151. x(A(x)B(x)xA(x)xB(x)2. x(A(x)B(x)xA(x)xB(x)3. x(A(x)B(x)xA(x)xB(x)4. xA(x)xB(x)x(A(x)B(x)證明：設(shè)論域?yàn)閍1,a2,.,an， x(A(x)B(x) (A(a1)B(a1)(A(a2)B(a2) (A(an)B(an) (A(a1)A(a2).A(an) (B(a1)B(a2).B(an) xA(x)xB(x) 量詞分配公式量詞分配公式2022-7-116 其它公式1. x(A(x)B(x)xA(x)xB(x) 2. xA(x)xB(x)x(A(x)B(

13、x) xA(x)xB(x)xA(x)xB(x) xA(x)xB(x)x(A(x)B(x)x(A(x)B(x) ： xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) x(A(x)B(x) x(A(x)B(x)2022-7-117量詞之間有如下公式：1. xyA(x,y)yxA(x,y)2. xyA(x,y)yxA(x,y)3. yxA(x,y)xyA(x,y)4. xyA(x,y)xyA(x,y)5. yxA(x,y)xyA(x,y)6. xyA(x,y)yxA(x,y)7. yxA(x,y)xyA(x,y)8. xyA(x,y)yxA(x,y)注意：下面式子不成立xyA(x,y

14、)yxA(x,y)2022-7-118 x x yA(x,y)yA(x,y) y y xA(x,y)xA(x,y) x x yA(x,y)yA(x,y) y y xA(x,y)xA(x,y) x x yA(x,y)yA(x,y) y y xA(x,y)xA(x,y) y y xA(x,y)xA(x,y) x x yA(x,y)yA(x,y)為了便于記憶，用圖形表示上面八個(gè)公式。2022-7-119第二章 小結(jié)集合的性質(zhì)集合的性質(zhì)冪等律冪等律 對(duì)任何集合A，有AA=A。交換律交換律 對(duì)任何集合A、B，有AB=BA。結(jié)合律結(jié)合律 對(duì)任何集合A、B、C，有 (AB)C=A(BC)。同一律同一律 對(duì)任

15、何集合A，有AE=A。零律零律 對(duì)任何集合A，有A=。 AB AB=A。交、并的性質(zhì)交、并的性質(zhì)冪等律冪等律 對(duì)任何集合對(duì)任何集合A A，有，有AA=AAA=A。交換律交換律 對(duì)任何集合對(duì)任何集合A A、B B，有，有AB=BAAB=BA。 結(jié)合律結(jié)合律 對(duì)任何集合對(duì)任何集合A A、B B、C C，有，有 (AB)C=A(BC) (AB)C=A(BC)。同一律同一律 對(duì)任何集合對(duì)任何集合A A，有，有A=AA=A。零律零律 對(duì)任何集合對(duì)任何集合A A，有，有AE =E AE =E 。分配律分配律 對(duì)任何集合對(duì)任何集合A A、B B、C C，有，有 A(BC) =(AB)(AC) A(BC) =

16、(AB)(AC)。 A(BC) =(AB)(AC) A(BC) =(AB)(AC)。吸收律吸收律 對(duì)任何集合對(duì)任何集合A A、B B，有，有 A(AB)=A A(AB) A(AB)=A A(AB) =A =A證明證明: : A(AB) A(AB) = (AE)(AB) ( = (AE)(AB) (同一同一) ) = A(EB) ( = A(EB) (分配分配) ) = AE=A ( = AE=A (零律零律) () (同一同一) ) A A B B AB=BAB=B差集的性質(zhì)差集的性質(zhì)設(shè)設(shè)A A、B B、C C是任意集合，則是任意集合，則 A-=A A-=A -A= -A= A-A= A-A=

17、 A-B A-B A A A A B B A-B= A-B= (A-B)-C=(A-C)-(B-C) (A-B)-C=(A-C)-(B-C) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) A A(B-(B-C)=(AB)-(AC)C)=(AB)-(AC)注意：注意：對(duì)對(duì)- - 是不可分配的，如是不可分配的，如A(A-B)=A A(A-B)=A 而而(AA)-(AB)=(AA)-(AB)=有關(guān)絕對(duì)補(bǔ)集的性質(zhì)有關(guān)絕對(duì)補(bǔ)集的性質(zhì)設(shè)設(shè)A A、B B、C C是任意集合，則是任意集合，則 E= E= =E =

18、E (A)=A(A)=A AA= AA= AA=E AA=E A-B=ABA-B=AB(AB)=AB (AB)=AB (AB)=AB (AB)=ABA A B B B B AA A=B A=B 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AB=EAB=E且且 AB= AB=有關(guān)對(duì)稱差的性質(zhì)有關(guān)對(duì)稱差的性質(zhì) 交換律交換律 對(duì)任何集合對(duì)任何集合A A、B B，有，有A A B=BB=B A A。 結(jié)合律結(jié)合律 對(duì)任何集合對(duì)任何集合A A、B B、C C，有，有 (A (A B)B) C=AC=A (B(B C)C)。教材里有證明。教材里有證明。 同一律同一律 對(duì)任何集合對(duì)任何集合A A，有，有A A =A=A。 對(duì)任何集合對(duì)

19、任何集合A A，有，有A A A A=。 對(duì)對(duì) 可分配可分配 A A(B(B C)=(AB)C)=(AB) (AC)(AC)一一. . 自反性自反性定義定義: :設(shè)設(shè)R R是集合是集合A A中的關(guān)系，如果對(duì)于任意中的關(guān)系，如果對(duì)于任意xAxA都都有有R (xRx)R (xRx)，則稱，則稱R R是是A A中自反關(guān)系。中自反關(guān)系。 即即 R R是是A A中自反的關(guān)系中自反的關(guān)系x(xx(x A AxRx)xRx)例如：例如：在實(shí)數(shù)集合中在實(shí)數(shù)集合中, ,“ ”是自反關(guān)系，因是自反關(guān)系，因?yàn)?，?duì)任意實(shí)數(shù)為，對(duì)任意實(shí)數(shù)x x，有，有x x x. x. 關(guān)系的性質(zhì)關(guān)系的性質(zhì)從關(guān)系有向圖看自反性從關(guān)系有

20、向圖看自反性: :每個(gè)結(jié)點(diǎn)都有環(huán)。每個(gè)結(jié)點(diǎn)都有環(huán)。從關(guān)系矩陣看自反性：主對(duì)角線都為從關(guān)系矩陣看自反性：主對(duì)角線都為1 1。二二. .反自反性反自反性定義：定義：設(shè)設(shè)R R是集合是集合A A中的關(guān)系，如果對(duì)于任意的中的關(guān)系，如果對(duì)于任意的xAxA都有都有 R R ，則稱，則稱R R為為A A中的反自反關(guān)系。中的反自反關(guān)系。 即即 R R是是A A中反自反的中反自反的x(xx(x A A R)R)v 從關(guān)系有向圖看反自反性從關(guān)系有向圖看反自反性: :每個(gè)結(jié)點(diǎn)都無(wú)環(huán)。每個(gè)結(jié)點(diǎn)都無(wú)環(huán)。v 從關(guān)系矩陣看反自反性：主對(duì)角線都為從關(guān)系矩陣看反自反性：主對(duì)角線都為0 0。如如 實(shí)數(shù)的大于關(guān)系實(shí)數(shù)的大于關(guān)系，父

21、子關(guān)系是反自反的。，父子關(guān)系是反自反的。注意：注意：一個(gè)不是自反的關(guān)系，不一定就是反自反一個(gè)不是自反的關(guān)系，不一定就是反自反 的。的。三三. .對(duì)稱性對(duì)稱性定義定義: :R R是集合是集合A A中關(guān)系中關(guān)系, ,若對(duì)任何若對(duì)任何x, x, yA,yA,如果有如果有xRy,xRy,必有必有yRx,yRx,則稱則稱R R為為A A中的對(duì)稱關(guān)系。中的對(duì)稱關(guān)系。 R R是是A A上對(duì)稱的上對(duì)稱的 x x y(xy(x A A y y A A xRy) xRy) yRx)yRx)v從關(guān)系有向圖看對(duì)稱性從關(guān)系有向圖看對(duì)稱性: :在兩個(gè)不同的結(jié)在兩個(gè)不同的結(jié)點(diǎn)之間，若有邊的話，則有方向相反的點(diǎn)之間，若有邊的

22、話，則有方向相反的兩條邊。兩條邊。v從關(guān)系矩陣看對(duì)稱性：以主對(duì)角線為對(duì)從關(guān)系矩陣看對(duì)稱性：以主對(duì)角線為對(duì)稱的矩陣。稱的矩陣。例例 鄰居關(guān)系和朋友關(guān)系是對(duì)稱關(guān)系。鄰居關(guān)系和朋友關(guān)系是對(duì)稱關(guān)系。四四. .反對(duì)稱性反對(duì)稱性定義定義: :設(shè)設(shè)R R為集合為集合A A中關(guān)系中關(guān)系, ,若對(duì)任何若對(duì)任何x, x, yA,yA,如果有如果有xRy,xRy,和和yRx,yRx,就有就有x=y,x=y,則稱則稱R R為為A A中反對(duì)稱關(guān)系中反對(duì)稱關(guān)系 。R R R是是A A上反對(duì)稱的上反對(duì)稱的 x x y(xy(x A A y y A A xRyxRy yRx)yRx) x=y)x=y) x x y(xy(x

23、A A y y A A x x y y xRy)xRy)y xy x) (P112) (P112)v 由由R R的關(guān)系圖看反對(duì)稱性：兩個(gè)不同的結(jié)點(diǎn)之間的關(guān)系圖看反對(duì)稱性：兩個(gè)不同的結(jié)點(diǎn)之間最多有一條邊。最多有一條邊。v 從關(guān)系矩陣看反對(duì)稱性：以主對(duì)角線為對(duì)稱的兩從關(guān)系矩陣看反對(duì)稱性：以主對(duì)角線為對(duì)稱的兩個(gè)元素中最多有一個(gè)個(gè)元素中最多有一個(gè)1 1。v另外對(duì)稱與反對(duì)稱不是完全對(duì)立的，有些關(guān)系它另外對(duì)稱與反對(duì)稱不是完全對(duì)立的，有些關(guān)系它既是對(duì)稱也是反對(duì)稱的，如空關(guān)系和恒等關(guān)系。既是對(duì)稱也是反對(duì)稱的，如空關(guān)系和恒等關(guān)系。五五. . 傳遞性傳遞性定義定義: :R R是是A A中關(guān)系，對(duì)任何中關(guān)系，對(duì)任何

24、x,x,y,zA,y,zA,如果有如果有xRy,xRy,和和yRz,yRz,就有就有xRz,xRz,則稱則稱R R為為A A中傳遞關(guān)系。中傳遞關(guān)系。 即即R R在在A A上傳遞上傳遞x x y y z(xz(x A A y y A A z z A A xRyxRy yRz)yRz)xRz)xRz)例例 實(shí)數(shù)集中的實(shí)數(shù)集中的、，集合、，集合 、 是傳遞的。是傳遞的。v 從關(guān)系關(guān)系圖和關(guān)系矩陣中不易看清是否有傳從關(guān)系關(guān)系圖和關(guān)系矩陣中不易看清是否有傳遞性。必須直接根據(jù)傳遞的定義來(lái)檢查。遞性。必須直接根據(jù)傳遞的定義來(lái)檢查。v 檢查時(shí)要特別注意使得傳遞定義表達(dá)式的前件檢查時(shí)要特別注意使得傳遞定義表達(dá)式

25、的前件為為F F的時(shí)候此表達(dá)式為的時(shí)候此表達(dá)式為T T，即是傳遞的。，即是傳遞的。 即若即若RR與與RR有一個(gè)是有一個(gè)是F F時(shí)時(shí)( (即定義即定義的前件為假的前件為假) )，R R是傳遞的。是傳遞的。 本節(jié)要求：本節(jié)要求： 1.1.準(zhǔn)確掌握這五個(gè)性質(zhì)的定義。準(zhǔn)確掌握這五個(gè)性質(zhì)的定義。 2. 2.熟練掌握五個(gè)性質(zhì)的判斷和證明。熟練掌握五個(gè)性質(zhì)的判斷和證明。R R是是A A中自反的中自反的x(xx(x A AxRx)xRx)R R是是A A中反自反的中反自反的x(xx(x A A R)R)R R是是A A上對(duì)稱的上對(duì)稱的x x y(xy(x A A y y A A xRy) xRy) yRx)y

26、Rx)R R是是A A上反對(duì)稱的上反對(duì)稱的x x y(xy(x A A y y A A xRyxRy yRx)yRx) x=y)x=y)x x y(xy(x A A y y A A x x y y xRy)xRy)y xy x) )R R在在A A上傳遞上傳遞x x y y z(xz(x A A y y A A z z A A xRyxRy yRz)yRz)xRz)xRz)v注意注意 性質(zhì)性質(zhì)表達(dá)式的前件為表達(dá)式的前件為F F時(shí)此表達(dá)式為時(shí)此表達(dá)式為T T，即，即R R是滿足此性質(zhì)的。是滿足此性質(zhì)的。 ( (自反和反自反性除外自反和反自反性除外) )自反性自反性反自反性反自反性對(duì)稱性對(duì)稱性傳遞

27、性傳遞性反對(duì)稱性反對(duì)稱性每個(gè)結(jié)點(diǎn)都有環(huán)每個(gè)結(jié)點(diǎn)都有環(huán) 主對(duì)角線全是主對(duì)角線全是1 1每個(gè)結(jié)點(diǎn)都無(wú)環(huán)每個(gè)結(jié)點(diǎn)都無(wú)環(huán) 主對(duì)角線全是主對(duì)角線全是0 0不同結(jié)點(diǎn)間如果有不同結(jié)點(diǎn)間如果有邊邊, ,則有方向相反則有方向相反的兩條邊的兩條邊. .是以對(duì)角線為對(duì)是以對(duì)角線為對(duì)稱的矩陣稱的矩陣不同結(jié)點(diǎn)間不同結(jié)點(diǎn)間, ,最多有最多有一條邊一條邊. .以主對(duì)角線為對(duì)稱以主對(duì)角線為對(duì)稱的位置不會(huì)同時(shí)為的位置不會(huì)同時(shí)為1 1如果有邊如果有邊, , ,則也有邊則也有邊. . 或前件為假或前件為假 如果如果a aij ij=1,=1,且且a ajk jk=1,=1,則則a aik ik=1=1性質(zhì)判定性質(zhì)判定 從關(guān)系的有向

28、圖從關(guān)系的有向圖 從關(guān)系的矩陣從關(guān)系的矩陣若若R R A AB SB S B BC C T T B BC C 則有則有)()()()()()(TRSRTSRTRSRTSR證明證明 任取任取R R (ST) (ST) b(bBb(bBRRST)ST)b(bBb(bBRR(ST)ST)）b(bBb(bBRRS)S) (bB (bBRRT)T)b(bBb(bBRRS)S) b(bBb(bBRRT)T)RR SRSR T T(R(R S)(RS)(R T)T)所以所以R R (ST)=(R (ST)=(R S) S)(R(R T)T) R是從A到B的關(guān)系，則 RR II RAB2. R2. RC C的

29、有向圖：是將的有向圖：是將R R的有向圖的所有邊的方向顛的有向圖的所有邊的方向顛倒一下即可。倒一下即可。3. R3. RC C的矩陣的矩陣 M =(M M =(MR R) )T T 即為即為R R矩陣的轉(zhuǎn)置。如矩陣的轉(zhuǎn)置。如 1 0 1 00 0 0 11 0 1 1MR=34 0 0 0 1 0 1 0 1 143 1 0 1=MRc三三. .性質(zhì)性質(zhì)令令R R、S S都是從都是從X X到到Y(jié) Y的關(guān)系，則的關(guān)系，則 1. (R1. (RC C) )C C = R= R 2. (RS) 2. (RS)C C = R = RC CSSC C 。 3. (RS) 3. (RS)C C = R =

30、 RC CSSC C 。 4. (R 4. (RS) S)C C = R = RC CS SC C 。5. R5. R S S R RC C S SC C 。6.(R)6.(R)C C=R=RC C7.7.令令R R是從是從X X到到Y(jié) Y的關(guān)系，的關(guān)系，S S是是Y Y到到 Z Z的關(guān)系，則的關(guān)系，則 (R (R S)S)C C= S= SC C R RC C 。 ( (注意注意RRC C S SC C ) )8. R8. R是是A A上關(guān)系，則上關(guān)系，則 R R是對(duì)稱的，當(dāng)且僅當(dāng)是對(duì)稱的，當(dāng)且僅當(dāng) R RC C =R =R R R是反對(duì)稱的，當(dāng)且僅當(dāng)是反對(duì)稱的，當(dāng)且僅當(dāng) RRRRC C I

31、 IA A。四四. .性質(zhì)性質(zhì)定理定理5.5. R R是是A A上關(guān)系，則上關(guān)系，則 R R是自反的，當(dāng)且僅當(dāng)是自反的，當(dāng)且僅當(dāng) r(R)=R. r(R)=R. R R是對(duì)稱的，當(dāng)且僅當(dāng)是對(duì)稱的，當(dāng)且僅當(dāng) s(R)=R. s(R)=R. R R是傳遞的，當(dāng)且僅當(dāng)是傳遞的，當(dāng)且僅當(dāng) t(R)=R. t(R)=R.定理定理6 6. . R R是是A A上關(guān)系，則上關(guān)系，則 R R是自反的，則是自反的，則s(R)s(R)和和t(R)t(R)也自反。也自反。 R R是對(duì)稱的，則是對(duì)稱的，則r(R)r(R)和和t(R)t(R)也對(duì)稱。也對(duì)稱。 R R是傳遞的，則是傳遞的，則r(R)r(R)也傳遞。也傳遞。定理定理7 7：設(shè)設(shè)R R1 1、R R2 2是是A A上關(guān)系，如果上關(guān)系，如果R R1 1 R R2 2 ，則，則 r(Rr(R1 1) ) r(Rr(R2 2) ) s(Rs(R1 1) ) s(Rs(R2 2) ) t(Rt(R1 1) ) t(Rt(R2 2) ) 證明證明 r(Rr(R1 1)=I)=IA ARR1 1 I IA ARR2 2= r(Rr(R2 2) ) ，類似可證。，類似可證