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

1、大一上離散數(shù)學重要公式定理匯總2022-7-12 基本的等價公式基本的等價公式 對合律對合律 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 互補律互補律 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 等價公式等價公式( (前前1010個個) )與集合論的公式比較與集合論的公式比較： 對合律對合律 AAA AA A表示表示

3、A A的絕對補集的絕對補集 冪等律冪等律 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）公式中的命題變量元論公式中的命題變量元論怎樣指派，公式對應的真值恒為怎樣指派，公式對應的真值恒為T T。 永假（矛盾）式（永假（矛盾）式（Contradiction)Contradiction)公式中的命題變公式中的命題變量無論怎樣代入，公式對應的真值恒為量無論怎樣代入，公式對應的真值恒為F F。 可滿足公式（可滿足公式（Sat

5、isfactionSatisfaction）公式中的命題變量無公式中的命題變量無論怎樣代入，公式對應的真值總有一種情況為論怎樣代入，公式對應的真值總有一種情況為T T。一般命題公式（一般命題公式（ContingencyContingency）既不是永真公式也不既不是永真公式也不是永假公式。是永假公式。2022-7-173.重要的重言蘊含式重要的重言蘊含式(如教材第如教材第43頁所示頁所示) 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 蘊含的性質(zhì)蘊含的性質(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證明見書證明見書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 用分配律、冪等律等公式進行整理，使之成為所用分配律、冪等律等公式進行整理，使之成為所要求的形式。要求的形式。 normal form2022-7-111v主析取范式定義主析取范式定義 析取范式

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

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

11、題公式永真式永真式永真蘊涵式永真蘊涵式等價公式等價公式范式范式命題邏輯推理命題邏輯推理直接推理直接推理間接推理間接推理條件論證條件論證反證法反證法析取析取合取合取主析取主析取主合取主合取知識網(wǎng)絡：知識網(wǎng)絡：2022-7-114 如果是個不含客體變元x的謂詞公式，且不在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) 量詞轄域的擴充公式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)證明：設論域為a1,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)為了便于記憶，用圖形表示上面八個公式。2022-7-119第二章 小結(jié)集合的性質(zhì)集合的性質(zhì)冪等律冪等律 對任何集合A，有AA=A。交換律交換律 對任何集合A、B，有AB=BA。結(jié)合律結(jié)合律 對任何集合A、B、C，有 (AB)C=A(BC)。同一律同一律 對任

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

16、(AB)(AC)。 A(BC) =(AB)(AC) A(BC) =(AB)(AC)。吸收律吸收律 對任何集合對任何集合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ì)設設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)注意：注意：對對- - 是不可分配的，如是不可分配的，如A(A-B)=A A(A-B)=A 而而(AA)-(AB)=(AA)-(AB)=有關(guān)絕對補集的性質(zhì)有關(guān)絕對補集的性質(zhì)設設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 當且僅當當且僅當AB=EAB=E且且 AB= AB=有關(guān)對稱差的性質(zhì)有關(guān)對稱差的性質(zhì) 交換律交換律 對任何集合對任何集合A A、B B，有，有A A B=BB=B A A。 結(jié)合律結(jié)合律 對任何集合對任何集合A A、B B、C C，有，有 (A (A B)B) C=AC=A (B(B C)C)。教材里有證明。教材里有證明。 同一律同一律 對任何集合對任何集合A A，有，有A A =A=A。 對任何集合對

19、任何集合A A，有，有A A A A=。 對對 可分配可分配 A A(B(B C)=(AB)C)=(AB) (AC)(AC)一一. . 自反性自反性定義定義: :設設R R是集合是集合A A中的關(guān)系，如果對于任意中的關(guān)系，如果對于任意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ù)集合中, ,“ ”是自反關(guān)系，因是自反關(guān)系，因為，對任意實數(shù)為，對任意實數(shù)x x，有，有x x x. x. 關(guān)系的性質(zhì)關(guān)系的性質(zhì)從關(guān)系有向圖看自反性從關(guān)系有

20、向圖看自反性: :每個結(jié)點都有環(huán)。每個結(jié)點都有環(huán)。從關(guān)系矩陣看自反性：主對角線都為從關(guān)系矩陣看自反性：主對角線都為1 1。二二. .反自反性反自反性定義：定義：設設R R是集合是集合A A中的關(guān)系，如果對于任意的中的關(guān)系，如果對于任意的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)系有向圖看反自反性: :每個結(jié)點都無環(huán)。每個結(jié)點都無環(huán)。v 從關(guān)系矩陣看反自反性：主對角線都為從關(guān)系矩陣看反自反性：主對角線都為0 0。如如 實數(shù)的大于關(guān)系實數(shù)的大于關(guān)系，父

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

22、話，則有方向相反的兩條邊。兩條邊。v從關(guān)系矩陣看對稱性：以主對角線為對從關(guān)系矩陣看對稱性：以主對角線為對稱的矩陣。稱的矩陣。例例 鄰居關(guān)系和朋友關(guān)系是對稱關(guān)系。鄰居關(guān)系和朋友關(guān)系是對稱關(guān)系。四四. .反對稱性反對稱性定義定義: :設設R R為集合為集合A A中關(guān)系中關(guān)系, ,若對任何若對任何x, x, yA,yA,如果有如果有xRy,xRy,和和yRx,yRx,就有就有x=y,x=y,則稱則稱R R為為A A中反對稱關(guān)系中反對稱關(guān)系 。R R R是是A A上反對稱的上反對稱的 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)系圖看反對稱性：兩個不同的結(jié)點之間的關(guān)系圖看反對稱性：兩個不同的結(jié)點之間最多有一條邊。最多有一條邊。v 從關(guān)系矩陣看反對稱性：以主對角線為對稱的兩從關(guān)系矩陣看反對稱性：以主對角線為對稱的兩個元素中最多有一個個元素中最多有一個1 1。v另外對稱與反對稱不是完全對立的，有些關(guān)系它另外對稱與反對稱不是完全對立的，有些關(guān)系它既是對稱也是反對稱的，如空關(guān)系和恒等關(guān)系。既是對稱也是反對稱的，如空關(guān)系和恒等關(guān)系。五五. . 傳遞性傳遞性定義定義: :R R是是A A中關(guān)系，對任何中關(guān)系，對任何

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ù)集中的、，集合、，集合 、 是傳遞的。是傳遞的。v 從關(guān)系關(guān)系圖和關(guān)系矩陣中不易看清是否有傳從關(guān)系關(guān)系圖和關(guān)系矩陣中不易看清是否有傳遞性。必須直接根據(jù)傳遞的定義來檢查。遞性。必須直接根據(jù)傳遞的定義來檢查。v 檢查時要特別注意使得傳遞定義表達式的前件檢查時要特別注意使得傳遞定義表達式

25、的前件為為F F的時候此表達式為的時候此表達式為T T，即是傳遞的。，即是傳遞的。 即若即若RR與與RR有一個是有一個是F F時時( (即定義即定義的前件為假的前件為假) )，R R是傳遞的。是傳遞的。 本節(jié)要求：本節(jié)要求： 1.1.準確掌握這五個性質(zhì)的定義。準確掌握這五個性質(zhì)的定義。 2. 2.熟練掌握五個性質(zhì)的判斷和證明。熟練掌握五個性質(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上對稱的上對稱的x x y(xy(x A A y y A A xRy) xRy) yRx)y

26、Rx)R R是是A A上反對稱的上反對稱的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ì)表達式的前件為表達式的前件為F F時此表達式為時此表達式為T T，即，即R R是滿足此性質(zhì)的。是滿足此性質(zhì)的。 ( (自反和反自反性除外自反和反自反性除外) )自反性自反性反自反性反自反性對稱性對稱性傳遞

27、性傳遞性反對稱性反對稱性每個結(jié)點都有環(huán)每個結(jié)點都有環(huán) 主對角線全是主對角線全是1 1每個結(jié)點都無環(huán)每個結(jié)點都無環(huán) 主對角線全是主對角線全是0 0不同結(jié)點間如果有不同結(jié)點間如果有邊邊, ,則有方向相反則有方向相反的兩條邊的兩條邊. .是以對角線為對是以對角線為對稱的矩陣稱的矩陣不同結(jié)點間不同結(jié)點間, ,最多有最多有一條邊一條邊. .以主對角線為對稱以主對角線為對稱的位置不會同時為的位置不會同時為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是對稱的，當且僅當是對稱的，當且僅當 R RC C =R =R R R是反對稱的，當且僅當是反對稱的，當且僅當 RRRRC C I

31、 IA A。四四. .性質(zhì)性質(zhì)定理定理5.5. R R是是A A上關(guān)系，則上關(guān)系，則 R R是自反的，當且僅當是自反的，當且僅當 r(R)=R. r(R)=R. R R是對稱的，當且僅當是對稱的，當且僅當 s(R)=R. s(R)=R. R R是傳遞的，當且僅當是傳遞的，當且僅當 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是對稱的，則是對稱的，則r(R)r(R)和和t(R)t(R)也對稱。也對稱。 R R是傳遞的，則是傳遞的，則r(R)r(R)也傳遞。也傳遞。定理定理7 7：設設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) ) ，類似可證。，類似可證