離散數(shù)學(xué)(第39講總復(fù)習(xí)一)

1、馮偉森馮偉森Email：2022年年5月月10日星期二日星期二2022-5-102022-5-10計算機學(xué)院計算機學(xué)院2 22022-5-102022-5-10計算機學(xué)院計算機學(xué)院3 3第一章第一章一、基本概念一、基本概念 命題、命題常元、命題變元、命題的解釋或命題、命題常元、命題變元、命題的解釋或賦值、賦值、原子命題原子命題( (簡單命題簡單命題) )、復(fù)合命題、否定、復(fù)合命題、否定聯(lián)結(jié)詞、合取、析取、可兼或、不可兼或、條聯(lián)結(jié)詞、合取、析取、可兼或、不可兼或、條件、雙條件件、雙條件、常值命題、命題變量、命題公式、常值命題、命題變量、命題公式、命題公式的解釋、真值表、永真公式命題公式的解釋、真

2、值表、永真公式( (重言式重言式) )、永假公式永假公式( (矛盾式，不可滿足公式矛盾式，不可滿足公式) )、可滿足公、可滿足公式、公式的等價、對偶（公）式、對偶原理、式、公式的等價、對偶（公）式、對偶原理、子句、短語、子句、短語、析取范式、合取范式、主析取析取范式、合取范式、主析?。ㄖ骱先。┓妒?、極小項、極大項（主合?。┓妒健O小項、極大項2022-5-102022-5-10計算機學(xué)院計算機學(xué)院4 4二、基本要求二、基本要求1 1、深刻理解五種常用聯(lián)結(jié)詞的涵義，并能準(zhǔn)確、深刻理解五種常用聯(lián)結(jié)詞的涵義，并能準(zhǔn)確地應(yīng)用它們地應(yīng)用它們將基本命題及復(fù)合命題符號化將基本命題及復(fù)合命題符號化。2 2、熟

3、練地寫出給定命題公式的真值表熟練地寫出給定命題公式的真值表3 3、牢記基本等價式的名稱及它們的內(nèi)容；、牢記基本等價式的名稱及它們的內(nèi)容；4 4、熟練地應(yīng)用基本等價式及置換規(guī)則進行等價、熟練地應(yīng)用基本等價式及置換規(guī)則進行等價 演算演算5 5、熟練掌握求主析?。ㄖ骱先。┓妒降姆椒ㄊ炀氄莆涨笾魑鋈。ㄖ骱先。┓妒降姆椒?022-5-102022-5-10計算機學(xué)院計算機學(xué)院5 56 6、理解并牢記、理解并牢記9 9類基本蘊涵關(guān)系式和蘊涵的基本類基本蘊涵關(guān)系式和蘊涵的基本性質(zhì)性質(zhì)7 7、牢記各條推理規(guī)則的內(nèi)容及名稱、牢記各條推理規(guī)則的內(nèi)容及名稱8 8、熟練掌握推理的各種方法（直接法、利用熟練掌握推理的各

4、種方法（直接法、利用CPCP規(guī)則、反證法）規(guī)則、反證法）2022-5-102022-5-10計算機學(xué)院計算機學(xué)院6 6第二章第二章一、基本概念一、基本概念 全總個體域（全論域）、全稱量詞、存在量詞、全總個體域（全論域）、全稱量詞、存在量詞、特性謂詞、指導(dǎo)（作用）變元、轄域（作用域）、約特性謂詞、指導(dǎo)（作用）變元、轄域（作用域）、約束變元、自由變元、約束變元的改名規(guī)則、自由變元束變元、自由變元、約束變元的改名規(guī)則、自由變元的代入規(guī)則、常量符號、變量符號、函數(shù)符號、謂詞的代入規(guī)則、常量符號、變量符號、函數(shù)符號、謂詞符號、謂詞公式、公式的解釋、永真公式符號、謂詞公式、公式的解釋、永真公式( (重言式

5、重言式) ) 、永假公式永假公式( (矛盾式，不可滿足公式）、可滿足公式、矛盾式，不可滿足公式）、可滿足公式、前束范式、母式、前束合取前束范式、母式、前束合取( (或析取或析取) )范式、范式、SkolemSkolem范范式、式、US(US(全稱指定規(guī)則全稱指定規(guī)則) )、ES(ES(存在指定規(guī)則存在指定規(guī)則) )、UG(UG(全全稱推廣規(guī)則稱推廣規(guī)則) )、EG(EG(存在推廣規(guī)則存在推廣規(guī)則) )2022-5-102022-5-10計算機學(xué)院計算機學(xué)院7 7二、基本要求二、基本要求 能準(zhǔn)確地將給定命題符號化能準(zhǔn)確地將給定命題符號化 深刻理解全稱量詞、存在量詞及量詞的轄域、深刻理解全稱量詞、

6、存在量詞及量詞的轄域、全總個體域的概念全總個體域的概念 能準(zhǔn)確理解約束變元能準(zhǔn)確理解約束變元( (量量) )和自由變元的概念和自由變元的概念 掌握約束變元的改名規(guī)則和自由變元的代入掌握約束變元的改名規(guī)則和自由變元的代入規(guī)則規(guī)則 能熟練地運用能熟練地運用USUS、ESES、UGUG、EGEG規(guī)則進行推理規(guī)則進行推理2022-5-102022-5-10計算機學(xué)院計算機學(xué)院8 8第三、四、五章第三、四、五章一、基本概念一、基本概念 冪集、笛卡爾集、冪集、笛卡爾集、關(guān)系、關(guān)系、n n元關(guān)系、空關(guān)元關(guān)系、空關(guān)系、二元關(guān)系、全關(guān)系、關(guān)系矩陣；關(guān)系的交、系、二元關(guān)系、全關(guān)系、關(guān)系矩陣；關(guān)系的交、并、補、差、

7、復(fù)合、冪、逆；并、補、差、復(fù)合、冪、逆；自反閉包、對稱自反閉包、對稱閉包、傳遞閉包閉包、傳遞閉包；等價關(guān)系、以；等價關(guān)系、以m m為模的同余為模的同余關(guān)系、等價類、生成元、偏序關(guān)系、偏序集、關(guān)系、等價類、生成元、偏序關(guān)系、偏序集、偏序集的哈斯圖、最大元偏序集的哈斯圖、最大元 、最小元、最小元 、極大元、極大元、極小元、上界、下界、最小上界、最大下界、極小元、上界、下界、最小上界、最大下界、全序關(guān)系、良序關(guān)系、良序集全序關(guān)系、良序關(guān)系、良序集2022-5-102022-5-10計算機學(xué)院計算機學(xué)院9 9二、基本要求二、基本要求1 1、熟練掌握關(guān)系的性質(zhì)和運算、熟練掌握關(guān)系的性質(zhì)和運算2 2、熟練

8、運用、熟練運用WarshallWarshall算法計算關(guān)系的傳遞閉包算法計算關(guān)系的傳遞閉包3 3、熟練掌握偏序關(guān)系的哈斯圖的畫法以及由哈斯熟練掌握偏序關(guān)系的哈斯圖的畫法以及由哈斯圖給出相應(yīng)的偏序關(guān)系圖給出相應(yīng)的偏序關(guān)系4 4、熟練掌握求偏序集中子集的最大元熟練掌握求偏序集中子集的最大元 、最小元、最小元 、極大元、極小元、上界、下界、最小上界、最極大元、極小元、上界、下界、最小上界、最大下界的方法大下界的方法5 5、熟練掌握利用關(guān)系的性質(zhì)和定義進行證明、熟練掌握利用關(guān)系的性質(zhì)和定義進行證明2022-5-102022-5-10計算機學(xué)院計算機學(xué)院1010第六章第六章一、基本概念一、基本概念 復(fù)合

9、函數(shù)、復(fù)合函數(shù)、單射單射 、滿射、雙射、置、滿射、雙射、置 換、換、單位單位( (恒等恒等) )置換、循環(huán)、置換、循環(huán)、逆函數(shù)逆函數(shù)二、基本要求二、基本要求1 1、熟練掌握判斷函數(shù)是否為單射、熟練掌握判斷函數(shù)是否為單射 、滿射、雙射、滿射、雙射的方法的方法2 2、熟練掌握、熟練掌握置換的復(fù)合運算和置換表示成循環(huán)置換的復(fù)合運算和置換表示成循環(huán)的積的積的方法的方法2022-5-102022-5-10計算機學(xué)院計算機學(xué)院1111求求G G(PQ)R(PQ)R的主合取范式和主析取范式。的主合取范式和主析取范式。解解：（公式轉(zhuǎn)換法）：（公式轉(zhuǎn)換法）G G(PQ)R(PQ)R( (PQ)RPQ)R（蘊涵）

10、（蘊涵）( (PQ(RPQ(RR)R) (PP)(PP)(QQ)R)QQ)R)（添加（添加R R、P P、Q Q）( (PQR)(PQR)(PQPQR)R)( (PPQR)(QR)(PQR)PQR)(P(PQR)(PQR) QR)(PQR) （分配律）（分配律）(PQR)(P(PQR)(PQR)(QR)(PQR)PQR)( (PQPQR)(R)(PPQR)QR)（結(jié)合律）（結(jié)合律）主合取范式主合取范式例例1 12022-5-102022-5-10計算機學(xué)院計算機學(xué)院1212G G(PQ)R(PQ)R( (PQ)R PQ)R （蘊涵）（蘊涵）( (PR)(QR)PR)(QR)( (P(P(QQ)

11、R)QQ)R)(PP)QR)PP)QR)( (PPQR)(QR)(PQR)PQR)( (PQR)(PQR) PQR)(PQR) （分配律）（分配律）( (PPQR)(QR)(PQR)(PQR)PQR)(PQR)主析取范式主析取范式2022-5-102022-5-10計算機學(xué)院計算機學(xué)院1313真值表技術(shù)法真值表技術(shù)法 1)1)、求公式的主合取范式、求公式的主合取范式P Q RP Q R(PQ) R(PQ) R0 0 00 0 0 0 00 0 10 0 1 1 1 0 1 00 1 0 0 00 1 10 1 1 1 11 0 01 0 0 0 01 0 11 0 1 0 01 1 01 1

12、0 0 01 1 11 1 1 1 1極大項極大項極大項極大項極大項極大項極大項極大項P PPP極大項極大項P2022-5-102022-5-10計算機學(xué)院計算機學(xué)院1414 將極大項全部進行合取后，可得到相應(yīng)的主將極大項全部進行合取后，可得到相應(yīng)的主合取范式：合取范式： G=G=（）=(PQR)(P=(PQR)(PQR)(QR)(PQR)PQR)( (PQPQR)(R)(PPQR)QR)2022-5-102022-5-10計算機學(xué)院計算機學(xué)院1515 2)2)、求公式的主析取范式、求公式的主析取范式P Q RP Q R(PQ(PQ）R R0 0 00 0 0 0 00 0 10 0 1 1

13、1 0 1 00 1 0 0 00 1 10 1 1 1 11 0 01 0 0 0 01 0 11 0 1 0 01 1 01 1 0 0 01 1 11 1 1 1 1P 極小項極小項極小項極小項極小項極小項PP2022-5-102022-5-10計算機學(xué)院計算機學(xué)院1616 將極小項全部進行析取后，可得到相應(yīng)的主析將極小項全部進行析取后，可得到相應(yīng)的主析取范式：取范式： G=G=（） = =（PP）（PP）（）2022-5-102022-5-10計算機學(xué)院計算機學(xué)院1717例例2 2 求證求證SRSR是前提是前提PQPQ，PRPR，QSQS的有效結(jié)論。的有效結(jié)論。( (構(gòu)構(gòu)造性二難推論造

14、性二難推論) ) 證：步驟證：步驟 公式公式 依據(jù)（注釋）依據(jù)（注釋） PQ PPQ P PQ TPQ T，E E1212 QS P QS P PS T, PS T, , , ,I,I6 6 SP TSP T，E E1414，E E1 1 PR P PR P SR TSR T，I I6 6 SR T SR T，E E1212，E E1 1 故故 PQPQ，PRPR，QS QS SRSR2022-5-102022-5-10計算機學(xué)院計算機學(xué)院1818例例3(CP3(CP規(guī)則規(guī)則) ) 證明證明RSRS可以從前提可以從前提 PP（QSQS），），RPRP，QQ推出推出 證：證： R PR P（附加

15、前提）（附加前提） RP PRP P P T P T，I I5 5 P P（QSQS） P P QS T QS T，I I3 3 Q P Q P S T S T，I I3 3 RS CP RS CP，2022-5-102022-5-10計算機學(xué)院計算機學(xué)院1919 證明：證明：RRQ Q，RSRS，SSQ Q，PQPQP P 證：證： （ P P） P P（假設(shè)前提）（假設(shè)前提） P TP T，E E1919 PQ P PQ P Q Q T, T, , , ,I,I3 3 S SQ PQ P S TS T，I I4 4 RS P RS P R T R T，I I5 5 R RQ PQ P Q

16、Q T T，I I3 3 Q QQ FQ F， 10 R RQ Q，RSRS，SSQ Q，PQPQP P例例4(4(反證法反證法) )2022-5-102022-5-10計算機學(xué)院計算機學(xué)院2020 若若n n是偶數(shù)，并且是偶數(shù)，并且n n大于大于5 5，則，則m m是奇數(shù)。是奇數(shù)。只有只有n n是偶數(shù)，是偶數(shù)，m m才大于才大于6 6。n n是大于是大于5 5，所以，所以，若若m m大于大于6 6，則，則m m是奇數(shù)。是奇數(shù)。解：設(shè)解：設(shè)p p：n n是偶數(shù)，是偶數(shù)，q: nq: n大于大于5,5, r: m r: m是奇數(shù)是奇數(shù), s: m, s: m大于大于6.6.前提前提: (p: (

17、pq) q) r,sr,sp,qp,q結(jié)論：結(jié)論：s sr r證明證明: q P q P s sq q 擴充法則擴充法則 （關(guān)鍵）（關(guān)鍵）例例5 52022-5-102022-5-10計算機學(xué)院計算機學(xué)院2121 sqsq 蘊涵式蘊涵式 spsp P P ( (spsp)()(sqsq) ) 合取合取 s(ps(pq q) ) 蘊涵式蘊涵式 (p(pq q)r P)r P sr sr 假言三段論假言三段論2022-5-102022-5-10計算機學(xué)院計算機學(xué)院2222例例6 6 所有的有理數(shù)都是實數(shù)；所有的無理數(shù)也是實數(shù)；虛所有的有理數(shù)都是實數(shù)；所有的無理數(shù)也是實數(shù)；虛數(shù)不是實數(shù)。因此，虛數(shù)既

18、不是有理數(shù)也不是無理數(shù)。數(shù)不是實數(shù)。因此，虛數(shù)既不是有理數(shù)也不是無理數(shù)。解：設(shè)解：設(shè)Q(x)Q(x)：x x是有理數(shù)；是有理數(shù)；R(x)R(x)：x x是實數(shù)；是實數(shù)； N(x)N(x)：x x是無是無理數(shù)；理數(shù)； C(x)C(x)：x x是虛數(shù)；是虛數(shù)； )()()()5()3()()()4()()()()3()1()()()2()()()()1()()()()()()()(),()()(),()()(xRxCxUS xRxNxRxNxUS xRxQxRxQxxNxQxCxxRxCxxRxNxxRxQx 2022-5-102022-5-10計算機學(xué)院計算機學(xué)院2323(11) )( (12)

19、(10)I (11)(8)(9) ) ()( (10) (9) 1088UGxNxQxCxTxNxQxCTxCxNxCxQITxCxNITxCxQETxCxRUSxRxC)()()()()()()()()()()7)(4()()()7)(2()()()8()6()()()7()5()()()6(33 2022-5-102022-5-10計算機學(xué)院計算機學(xué)院2424例例7 7 設(shè)設(shè)R R是集合是集合A A上的一個傳遞關(guān)系和自反關(guān)系，上的一個傳遞關(guān)系和自反關(guān)系，S S是是A A上的一個關(guān)系，使得對任意上的一個關(guān)系，使得對任意a,bAa,bA，SS當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)RR且且RR，試證，試證明明S S是

20、是A A上的一個等價關(guān)系。上的一個等價關(guān)系。證明：證明：1 1）對任意對任意aAaA，因，因R R是自反的，所以是自反的，所以RR。由由RR并且并且RR，有，有SS，即，即S S是是自反的。自反的。2 2）對任意對任意a,bAa,bA，若，若SS，則由已知條件有，則由已知條件有RR并且并且RR，即有，即有RR并且并且RR，所以，所以，SS，即，即S S是對稱的。是對稱的。2022-5-102022-5-10計算機學(xué)院計算機學(xué)院25253 3）對任意對任意a,b,cAa,b,cA，若，若SS，SS，則由已知條件有：則由已知條件有：RR并且并且RR和和RR并且并且RR。所以，由。所以，由RR并并且

21、且RR，有，有RR；由；由RR并且并且RR，有，有RR；由：；由：RR并且并且RR，有，有SS，即，即S S是傳遞的。是傳遞的。 由由1),2),3)1),2),3)知，知，S S是是A A上的一個等價關(guān)系。上的一個等價關(guān)系。2022-5-102022-5-10計算機學(xué)院計算機學(xué)院2626例例8 8證明：證明：“” 若若R R是等價關(guān)系。是等價關(guān)系。1 1）顯然顯然R R是自反的。是自反的。2 2）對任意對任意a,b,cAa,b,cA，若，若R,RR,R，則由，則由R R是對稱的，有是對稱的，有RR并且并且RR，由，由R R是傳遞是傳遞的，所以，的，所以，RR。即。即R R是循環(huán)的關(guān)系。是循環(huán)

22、的關(guān)系。由由1)1)，2)2)知知R R是自反的和循環(huán)的。是自反的和循環(huán)的。 設(shè)設(shè)R R是集合是集合A A上的一個關(guān)系，對上的一個關(guān)系，對 a,b,cAa,b,cA，若若RR并且并且RR，則有：，則有：RR，則，則R R稱為稱為A A上的上的循環(huán)關(guān)系循環(huán)關(guān)系。試證明。試證明R R是是A A上的一個等價上的一個等價關(guān)系的充要條件是關(guān)系的充要條件是R R是循環(huán)關(guān)系和自反關(guān)系。是循環(huán)關(guān)系和自反關(guān)系。2022-5-102022-5-10計算機學(xué)院計算機學(xué)院2727“” 若若R R是自反的和循環(huán)的。是自反的和循環(huán)的。1 1）顯然顯然R R是是自反性自反性的；的；2 2）對任意對任意a,bA,a,bA,若

23、若R,R,則由則由R R是自反的是自反的, ,有有RR，因，因R R是循環(huán)的，所以，是循環(huán)的，所以，RR且且R R RR，即即R R是對稱的。是對稱的。3 3）對任意對任意a,b,cAa,b,cA，若，若RR，RR，則由則由R R對稱的，有對稱的，有RR并且并且RR；由；由R R是循環(huán)的，所以是循環(huán)的，所以RR且且RRRR，即，即R R是傳遞的。是傳遞的。由由1),2),3)1),2),3)知，知，R R是是A A上的一個等價關(guān)系。上的一個等價關(guān)系。2022-5-102022-5-10計算機學(xué)院計算機學(xué)院2828例例9 9設(shè)設(shè)A A22，3 3，4 4，B B11，2 2，4 4?？紤]?？紤]從

24、從A A到到B B的的“大于等于大于等于”關(guān)系關(guān)系R R和和“小于等于小于等于”關(guān)關(guān)系系S S：R R,，S S,。求出求出R R S S、 R R S S、 R-S R-S、 R R S S、 、S S-1-1。解：解： R R S= ,S= ,R R S= ,S= ,R2022-5-102022-5-10計算機學(xué)院計算機學(xué)院2929 R-S= ,R-S= , R R S = ,S = , = = , ,S S-1-1= ,= ,R2022-5-102022-5-10計算機學(xué)院計算機學(xué)院3030例例1010解：解：最大元：無；最小元：最大元：無；最小元：x x5 5； 設(shè)設(shè)A Axx1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,A A上定義偏序集上定義偏序集的哈斯圖如下，求的哈斯圖如下，求B Bxx3 3,x,x4 4,x,x5 5 的最大的最大( (小小) )元、極大元、極大( (小小) )元、上元、上( (下下) )界、最小上界、最界、最小上界、最大下界。大下界。極大元