《離散數(shù)學(xué)》課件第一章

1、離散數(shù)學(xué)一、學(xué)習(xí)離散數(shù)學(xué)課程的目的 離散數(shù)學(xué)是計算機專業(yè)的一門核心基礎(chǔ)課程。 1 離散數(shù)學(xué)為計算機專業(yè)的后繼課程如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫、編譯原理、網(wǎng)絡(luò)和算法設(shè)計等課程提供必要的數(shù)學(xué)基礎(chǔ)。計算機科學(xué)的一個重要特點是離散性.它能夠處理的數(shù)據(jù)結(jié)構(gòu)都是離散結(jié)構(gòu),所以學(xué)習(xí)離散數(shù)學(xué)是非常有必要的。 2 離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個重要分支，通過該課程的學(xué)習(xí)可以提高學(xué)生的抽象思維、嚴(yán)格推理以及綜合歸納分析能力，培養(yǎng)出高素質(zhì)的人才。 Edsger W. Dijkstra（19302002）我現(xiàn)在年紀(jì)大了, 搞了這么多年的軟件, 錯誤不知道犯了多少, 現(xiàn)在覺悟了, 我想假若我早年在數(shù)理邏輯上好好下點工夫的話,

2、 我就不會犯這么多的錯誤。不少東西, 邏輯學(xué)家早就說了,可我不知道。要是我能年輕20 歲, 我要回去學(xué)習(xí)邏輯。二、離散數(shù)學(xué)課程的特點 離散數(shù)學(xué)課程是應(yīng)計算機科學(xué)和技術(shù)發(fā)展的需要，綜合了高等數(shù)學(xué)的多個分支而形成的。 其特點是以離散量為研究對象，內(nèi)容豐富，涉及面較寬。因此概念多、定理多、推理多并且內(nèi)容較為抽象。因此其學(xué)習(xí)有一定的難度。 三、如何學(xué)好離散數(shù)學(xué) 要學(xué)好這門課程，首先必須充分認(rèn)識到這門課程的上述特點，需要做到以下幾點：1 熟讀教材。 2 獨立思考，大量練習(xí)。 3 注重抽象思維能力的培養(yǎng)。四、 離散數(shù)學(xué)課程的主要內(nèi)容第四部分 圖論。包括圖的基本概念，幾種特殊的圖。離散數(shù)學(xué)課程的主要內(nèi)容可以

3、分為四個部分：第一部分 數(shù)理邏輯。包括命題邏輯和謂詞邏輯。第二部分 集合論。包括集合、關(guān)系和函數(shù)。第三部分 代數(shù)系統(tǒng)。包括代數(shù)系統(tǒng)的一般概念，幾類典型的代數(shù)系統(tǒng)。五、 教材及參考書1、教材：離散數(shù)學(xué)，蔡之華主編，中國地質(zhì)大學(xué)出版社。2、參考教材馬振華，離散數(shù)學(xué)導(dǎo)引，清華大學(xué)出版社，1996.王憲鈞，數(shù)理邏輯引論，北京大學(xué)出版社，1998，丘維聲, 抽象代數(shù)基礎(chǔ)，高等教育出版社，2003.離散數(shù)學(xué)習(xí)題集，耿素云，北大出版社離散數(shù)學(xué)輔導(dǎo)及習(xí)題精解 湯光華編，上?？茖W(xué)技術(shù)文獻出版社。 網(wǎng)絡(luò)資源課程考核 平時成績（到課情況、書面作業(yè)、平時測驗）占30%，期末考試占70%。數(shù)理邏輯Mathematica

4、l Logic命題邏輯謂詞邏輯非經(jīng)典邏輯形式化規(guī)范化推理公理化數(shù)理邏輯第一講 命題邏輯（Propositional Logic ） 1. 命題邏輯的基本概念、命題聯(lián)結(jié)詞 2. 命題公式、自然語言的形式化 3. 等值演算 4. 范式 5. 聯(lián)結(jié)詞的完備集 6. 推理理論 7. 命題邏輯在計算機科學(xué)中的應(yīng)用1.1 命題與聯(lián)結(jié)詞1 命題與命題變元命題？能夠分辨真假的陳述句。 注： (1)命題是陳述句。其他的語句，如疑問句、祈使句、感嘆句均不是命題； (2)這個陳述句表示的內(nèi)容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假怎樣研究命題？簡單命題“構(gòu)造”復(fù)雜命題1.1 命題與聯(lián)結(jié)詞命題的

5、真值？作為命題的陳述句所表示的判斷結(jié)果 真值只取兩個值：真或假。凡是與事實相符的陳述句是真命題，而與事實不符合的陳述句是假命題。通常用1（或字母T）表示真，用0（或字母F）表示假。1.1 命題與聯(lián)結(jié)詞示例1.1 判斷下列語句是否為命題，并指出其真值（1）北京是中國的首都。（2）5可以被2整除。（3）2+2=5。（4）請勿吸煙。（5）烏鴉是黑色的嗎？（6）這個小男孩多勇敢啊?。?）地球外的星球上存在生物。（8）我正在說謊。1.1 命題與聯(lián)結(jié)詞注：一個語句本身是否能分辨真假與我們是否知道它的真假是兩回事。也就是說，對于一個句子，有時我們可能無法判定它的真假，但它本身卻是有真假的，那么這個語句是命題

6、，否則就不是命題。悖論不是命題。說謊者悖論蘇格拉底悖論:“我只知道一件事，那就是什么都不知道?！鼻f子齊物論里莊子說：“言盡悖”“如果說上帝是萬能的，他能否創(chuàng)造一塊他舉不起來的大石頭？”1.1 命題與聯(lián)結(jié)詞命題的分類原子命題：是指不能再分解為更簡單命題的命題；復(fù)合命題：是指由若干命題用聯(lián)結(jié)詞組成的新命題。 1.1 命題與聯(lián)結(jié)詞命題常元？命題變元？真值確定與否的原子命題。注： 如果命題符號P代表命題常元則意味它是某個具體命題的符號化，如果P代表命題變元則意味著它可指代任何具體命題。如果沒有特別指明，通常來說命題符號P等是命題變元，即可指代任何命題。 符號化1.1 命題與聯(lián)結(jié)詞2 命題聯(lián)結(jié)詞及真值表

7、否定詞“”（或“”）否定詞是一元聯(lián)結(jié)詞。相當(dāng)于自然語言中的“非”、“不”等，真值表如右圖。例：設(shè)P：上海是一個城市； 則有 P：上海不是一個城市; P P 0 1 1 01.1 命題與聯(lián)結(jié)詞合取詞“”合取詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的“與” 、“并且” 、“而且” 、“也”等，真值表如右圖。例 設(shè)P：我們?nèi)タ措娪啊?Q：房間里有十張桌子。 則P Q表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子?！?P Q P Q 0 0 0 0 1 0 1 0 0 1 1 11.1 命題與聯(lián)結(jié)詞析取詞“” 析取詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的“或”、“要么要么”等，真值表如右圖。 P Q PQ 0 0 0 0

8、1 1 1 0 1 1 1 1聯(lián)結(jié)詞“”是自然語言中的“或”、“或者”等邏輯抽象（可兼或）；但“或”可指 “可兼或”、“排斥或”；1.1 命題與聯(lián)結(jié)詞蘊含詞“” 蘊含詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的“若則”、“如果就”，真值表如右圖。 P QP Q 0 0 1 0 1 1 1 0 0 1 1 1 在自然語言中，前件為假，不管結(jié)論真假，整個語句的意義，往往無法判斷。但在數(shù)理邏輯中，當(dāng)前件P為假時，不管Q的真假如何，則PQ都為真。實質(zhì)蘊涵意味著可從假的前提推出任何命題來，或兩個沒有內(nèi)在聯(lián)系的命題之間存在蘊涵關(guān)系 “PQ”是表示自然語言中的“因為P所以Q”、“如果P,則Q”，“只有Q才P”、“除非

9、Q，否則非P”、“P僅當(dāng)Q”等的邏輯抽象。1.1 命題與聯(lián)結(jié)詞等價詞“ ” 等價詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的“等價”、“當(dāng)且僅當(dāng)”、“充要條件”等，真值表如右圖。 P Q PQ 0 0 1 0 1 0 1 0 0 1 1 1 例 非本倉庫工作人員，一律不得入內(nèi)。解 令P：某人不是倉庫工作人員； Q：某人不可以進入倉庫。 則 上述命題可表示為PQ。1.1 命題與聯(lián)結(jié)詞優(yōu)先級順序：的優(yōu)先級最高，接著依次是，和。1.1 命題與聯(lián)結(jié)詞練習(xí)1.1 判斷下列語句是否為命題明年的中秋節(jié)的晚上是晴天地球外的星球上存在生物x + y 10但愿中國隊能取勝。3 是有理數(shù) 1.1 命題與聯(lián)結(jié)詞練習(xí)1.2 符號

10、化下列命題1.今晚我上網(wǎng)2.今晚我去教室自習(xí)3.他已經(jīng)回家度假去了4.今晚我上網(wǎng)或我去教室自習(xí)5.今晚我上網(wǎng)或者他已經(jīng)回家度假去了6.如果今天下雨了，那么秋天就到了1.1 命題與聯(lián)結(jié)詞聯(lián)結(jié)詞“”、“”、“”與構(gòu)成電路的與門、或門和非門電路是相對應(yīng)的，從而命題邏輯是計算機硬件電路的表示、分析和設(shè)計的重要工具。聯(lián)結(jié)詞“”、“”、“”的“聯(lián)接運算”結(jié)果具有對稱性，而聯(lián)結(jié)詞“”、“”沒有；真值表；注意“”、“”的含義聯(lián)結(jié)詞是句子與句子之間的聯(lián)結(jié)；聯(lián)結(jié)詞連接的是兩個命題真值之間的聯(lián)結(jié)，而不是命題內(nèi)容之間的連接，因此復(fù)合命題的真值只取決于構(gòu)成他們的各命題的真值，而與它們的內(nèi)容、含義無關(guān)，與聯(lián)結(jié)詞所連接的兩

11、命題之間是否有關(guān)系無關(guān)；命題形式與命題意義1.2 命題公式1 命題公式(Propositional Formula)？構(gòu)造-歸納（計算機）（1）命題變元是命題公式；（2）如果P是命題公式，則P也是命題公式；（3）如果P和Q是命題公式，則(PA)，(PQ)，(PQ)，(PQ)均是命題公式；（4）只有有限次地利用（1）（3）形成的符號串才是命題公式。運算的優(yōu)先順序，“（ ）”1.2 命題公式1 命題公式(Propositional Formula)？構(gòu)造-歸納（計算機）PQ,PQ),RP是命題公式嗎？命題公式是命題嗎？如何符號化命題？1.2 命題公式示例1.3 (p q) (p) (q r)是不是

12、命題公式？它通過以下步驟生成：1. p是公式；2. q是公式；3. (p q)是公式；4. (p)是公式；5. r是公式；6. (q r)是公式；7. (p) (q r)是公式；8. (p q) (p) (q r)是公式。示例1.2 命題公式(PQ)( PR) IF P THEN Q ELSE R1.2 命題公式可以形象地用下面的一棵樹來表示這種樹在形式語言與自動機中就稱為語法分析樹。 例 將下列命題符號化 （1）我們不能既劃船又跑步； （2）如果你來了，那么他唱不唱歌將看你是否伴奏而定； （1） 令P：我們劃船；Q：我們跑步。則命題可 表示為(PQ）。 （2） 令P：你來了；Q：他唱歌；R：

13、你伴奏。 則命題可表示為 P（QR）1.2 命題公式1.2 命題公式（3）如果李明是體育愛好者，但不是文藝愛好者，那么李明不是文體愛好者； 令P：李明是體育愛好者；Q：李明是文藝愛好者。 則命題可表示為（P Q）（P Q） 。注： 如果給出一個命題公式：（P Q）（PR） 求它的真值之前要給出真值指派。 完全指派、部分指派、成真指派、成假指派、真值表、子公式。1.2 命題公式2 命題公式類型重言式或永真式（Tautology）矛盾式或永假式（Contradiction）可滿足式（Contingency）公式的值？指派真值表判定公式類型命題公式的值？真？假？真值函數(shù)1.2 命題公式示例1.3 教

14、材P6例1.6練習(xí)1.3 判斷下列公式的類型 (p(qp) ) r (pq)q)r (pq)(p(qr)1.2 命題公式pqrqpp(qp)(p(qp)r000011001011010111011111100111101111110111111111( p(qp)r 1.2 命題公式pqrpq(pq)(pq)q(pq)q)r00010000011000010100001110001000100101010011010001111000(pq)q)r1.2 命題公式pqrpqpqrpqr(pq)(p(qr)000010010010100101011000011111111001001110110

15、0111101001111110100(pq)(p (qr)真值函數(shù)pqr(p(qp)r(pq)q)rpqr.000100?001100?010100?011101?100101?101101?110101?111100?1.3 等值演算1 等值式函數(shù)相等？命題公式相等？命題公式等值或命題公式可以由一種形式轉(zhuǎn)化位另一種形式，是數(shù)理邏輯研究的重要課題定義1-8 設(shè)和是兩個命題公式, 若、構(gòu)成的等價式為永真式,則稱公式和等值，記為 ,稱 為等價式。例如 代數(shù)中令F1(x, y) = (x + y)2, F2(x, y) = x2 + 2xy + y2 則 F1(x, y) = F2(x, y) 類

16、似地，在命題邏輯中例如 令 F1(P1, P2) = P1 P2 F2(P1, P2) = P2 P1 則 P1 P2 P2 P1 即 F1(P1, P2) F2(P1, P2) 1.3 等值演算1.3 等值演算 當(dāng)且僅當(dāng) 為重言式 ：一種關(guān)系比較，自然語言中的符號：運算符號，可以計算（從而用于判斷等價關(guān)系）可以作為程序語言的符號示例1.4 閱讀教材P8例1.71.3 等值演算等值公式(命題定律)1 交換律、結(jié)合律、分配律雙否律、等冪律、德摩根律2 吸收律、零一律、同一律、排中律、矛盾律3 蘊含等值式4 假言易位（逆否律）、等價等值式、等價否定律、5 歸謬論判斷命題公式是否永真真值表方法？當(dāng)命

17、題變量增多時？1.3 等值演算吸收律 ()， ()零一律 11， 00同一律0， 1排中律1矛盾律 01.3 等值演算蘊含等值式 假言易位(逆否律） 等價等值式()()， ()()等價否定等值式歸謬論 ()() 等值式證明示例1.4 閱讀教材P9例1.81.3 等值演算2 等值演算兩個定理代入定理置換定理有兩種方法：真值表方法，命題演算方法如何進行等值演算1、真值表方法 例1 用真值表方法證明 E10： (PQ) PQ解 令：A= (PQ)，B= PQ，構(gòu)造A，B 以及A B的真值表如下： 由于公式AB所標(biāo)記的列全為1，因此AB。 0PQPQ(PQ)PQPQAB0011111011010011

18、1100101101000011.3 等值演算2等值演算方法例如 在初等代數(shù)中證明恒等式(x + 1)(x2 x + 1)(x - 1)(x2 + x + 1)=x6 1證明 原式= (x + 1)(x2 x + 1)(x - 1)(x2 + x + 1) = (x3 + 1)(x3 1) = (x3)2 1 = x6 11.3 等值演算 (1) 代入規(guī)則 代入規(guī)則 對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。 例如 F=（PQ）（QP）是重言式，若用公式AB代換命題變元P得公式 F1=（AB）Q）（Q（AB）， F1仍是重言式。1.3 等值演算注意：因為A

19、B當(dāng)且僅當(dāng)A B是重言式。所以，若對于等值式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。例如 (P Q) (P Q )，即 (P Q) P Q是永真公式于是，用PS對P進行代入得 (PS)Q) (PS) Q1.3 等值演算 (2)置換規(guī)則 設(shè)C是公式A的子公式，CD。如果將公式A中的子公式C置換成公式D之后，得到的公式是B，則AB。 若 A=(PQ)(PQ)(RS) B=(PQ)(PQ)(RS) 則 A B 例如 1.3 等值演算(3) 等值演算 等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過程。 由代入規(guī)則知前

20、述的基本等值式，不僅對任意的命題變元P，Q，R是成立的，而且當(dāng)P，Q，R分別為命題公式時，這些等值式也成立。 1.3 等值演算1.3 等值演算 例 證明命題公式的等值關(guān)系： （PQ）（RQ）（PR）Q；證明 （PQ）（RQ） （ PQ）( RQ) E11（ P R）Q E3( 分配律) (PR) Q E11 (PR)Q E10(德.摩根定律)所以（PQ）（RQ）（PR）Q 例 證明下列命題公式的等值關(guān)系 (P Q ) ( P ( P Q ) ) P Q 證明 (PQ)( P(PQ) (PQ)( (P P ) Q ) (結(jié)合律) (PQ)( PQ) (等冪律) (P Q ) ( PQ ) (交換

21、律) P(Q(PQ) (結(jié)合律) PQ (交換律，吸收律) 1.3 等值演算例 判別下列公式的類型。 （1） Q (P（PQ）) 解 Q（P（PQ） Q（P（PQ）Q（PP）（PQ）Q（1（PQ）Q（PQ）QPQ（QQ）P0所以Q (P (PQ)是矛盾式。1.3 等值演算1.3 等值演算（2）（PQ）P 解：（PQ）P （PQ）P P于是該公式是可滿足式。 (3) (P Q)P) Q 定義1.10 如果命題公式中只出現(xiàn)命題變元、命題常元、命題連結(jié)詞“”、“”、“”，則稱為限制性命題公式。 定義1.11 在限制性命題公式中，將連結(jié)詞“”換成“”， 將 “”換成 “”、將0換成1，1換成0，所得到

22、的公式稱為的對偶式，記為*。 1.3 等值演算顯然， 和*互為對偶式。例如，公式(P Q) ( R)與公式(P Q) ( R)一個性質(zhì)對偶式？1.4 范式需求命題公式規(guī)范化？AI (自動推理，Rough集數(shù)據(jù)約簡)電路設(shè)計(只根據(jù)真值表即可設(shè)計電路）可行聯(lián)接詞功能完備集：, , 1.4 范式何為命題公式規(guī)范形式？文字 P，P（P與P稱為互補對）質(zhì)合取/析取式 P，P，PQ，PQR P，Q，PQ，PQR析取/合取范式主析取/合取范式1.4 范式 定理1.5 (1)質(zhì)合取式為矛盾式的充要條件：它包含一個互補對。 (2)質(zhì)析取式為重言式的充要條件：它包含一個互補對。1.4 范式析取范式（Disjun

23、ctive Normal Form） 12n i為質(zhì)合取式。 (PQ)(PQ)合取范式（Conjunctive Normal Form） 12n i為質(zhì)析取式。 (PR)(PQR)(PR)定理1.6 任一命題公式存在析取范式 、合取范式。 如何求解析取范式和合取范式？ (1)消去聯(lián)結(jié)詞，； (2)將聯(lián)結(jié)詞向內(nèi)深入，使之只作用于命題變元； (3)利用分配律將公式化為所需要的范式。1.4 范式1.4 范式示例1.4 閱讀教材P14例1.12應(yīng)用 教材P15定理1.7練習(xí) 求命題公式的析取范式和合取范式(1).求(PQ)(PR)的析取范式和合取范式(2).求(PQ)(PR)的析取范式和合取范式1.4

24、 范式解 (1)求(PQ)(PR)的析取范式：(PQ)(PR) (PQ)(PR)/ 蘊涵等值式(PQ)(PR) / 雙否律(PP)(PR)(QP)(QR)/分配律(PR)(QP)(QR) /(PP)是矛盾式顯然(PQ)(PR)的合取范式為(PQ)(PR)。(2)求(PQ)(PR)的合取范式：(PQ)(PR)(PQ)(PR) (PQP) (PQR)顯然(PQ)(PR)的析取范式為(P)QR。1.4 范式注意到：一個命題公式的合取范式和析取范式不具有唯一性。 定義 1.14 在含n個命題變元的質(zhì)合取式（質(zhì)析取式）中，若每個命題變元與其否定不同時存在，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變元或

25、其否定出現(xiàn)在從左算起的第i位上，這樣的質(zhì)合取式（質(zhì)析取式）稱為極小項（極大項）。例如，兩個命題變元P,Q共可產(chǎn)生4個極小項，分別為：PQ對應(yīng)00，記為m0； PQ對應(yīng)01，記為m1；PQ對應(yīng)10，記為m2； PQ對應(yīng)11，記為m3；也可以產(chǎn)生4個極大項，分別為：PQ對應(yīng)00，記為M0； PQ對應(yīng)01，記為M1；PQ對應(yīng)10，記為M2； PQ對應(yīng)11，記為M3；1.4 范式 定理1.8 設(shè)mi和Mi是命題變元P1 ,P2 , ,Pn形成的極小項和極大項，則miMi ， Mi mi 定義1.15 設(shè)命題公式中含n個命題變元，如果的析取范式（合取范式）中的質(zhì)合取式（質(zhì)析取式）都是極小項（極大項），則

26、稱該析取范式（合取范式）為的主析取范式（主合取范式）。1.4 范式主析取/合取范式如何求解？極小項、極大項1 真值表法 2 等值演算1.4 范式例 求下列命題公式的主析取范式和主合取范式。 1）P(QR) 2）(PQ)R1.4 范式P Q R P (Q R) (PQ)R 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 根據(jù)真值表中P(QR)真值為1的賦值，所對應(yīng)的極小項析取即為P(QR)的主析取范式，所以有：P(QR) m0 m1 m2 m3 m4 m5 m7(PQR) (PQR)(

27、PQR)(PQR)(PQR)(PQR)(PQR) 根據(jù)真值表中P(QR)真值為0的賦值，所對應(yīng)的極大項合取即為P(QR)的主合取范式，所以有：P(QR) M6 PQR1.4 范式同理，(PQ)R的主析取范式為：(PQR)(PQR)(PQR)(PQR) (PQR)(PQ)R的主合取范式為：(PQR)(PQR)(PQR) 從上面的例題中可以看出：矛盾式?jīng)]有主析取范式，重言式?jīng)]有主合取范式。 定理1.9 任何一個不為矛盾式（重言式）的命題公式都存在著與之等值的主析取范式（主合取范式），并且是唯一的。1.4 范式1.4 范式示例 教材P17例1.16應(yīng)用 教材P18例1.17真值表方法等值演算方法如何

28、求解主析取范式和主合取范式？ (1)化為析取范式和合取范式； (2)利用同一律消去矛盾的質(zhì)合取式（重言的質(zhì)析取式）；（3）利用等冪律消去相同的質(zhì)合取式（質(zhì)析取式）以及質(zhì)合取式（質(zhì)析取式）中相同的合取項（析取項）； （4）利用同一律、分配律將每一合取項（析取項）化為極小項（極大項）。1.4 范式示例 教材P17例1.16求公式(PR)(PQ)的主合取范式。解 (PR)(PQ) (PR)(PQ)(PQ)(P(QQ)R)(PQ(RR)(PQ(RR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) M0M2M3M4M5此即所求的主合取范式。

29、因此，上式的主析取范式m1m6m71.4 范式練習(xí) 求命題公式的主范式(1).求(PQ)(PR)的主析取范式和主合取范式(2).求(PQ)(PR)的主析取范式和主合取范式1.4 范式(1)根據(jù)前例知(PQ)(PR)的一個析取范式是(PR)(QP)(QR)，現(xiàn)在將其中的每個簡單合取式展開為含有所有命題變元的極小項的析取： (PR)展開為(PQR)(PQR),(QP)展開為(PQR) (PQR),(QR)展開為(PQR)(PQR)因此(PQ)(PR)的主析取范式為(PQR)(PQR)(PQR)(PQR)，按極小項所對應(yīng)的二進制數(shù)的大小重新排列為(PQR)(PQR)(PQR)(PQR),可記為m2m

30、3m5m7。1.4 范式討論范式一定存在，但主范式不一定存在？如果命題公式是矛盾式（永真式），則其無主析取范式（合取范式）？如果命題公式存在主范式，則是唯一存在的？如果已經(jīng)求得某命題公式的主析取范式，則可以根據(jù)主析取范式求得該命題公式的主合取范式只要給定真值表，則可以求出相應(yīng)真值函數(shù)的主范式？1.5 聯(lián)結(jié)詞的完備集 定義1.16 稱F：0,1n0,1為n元真值函數(shù)（Truth Value Function）。 在這個定義中，F(xiàn)的自變量為n個命題變元，定義域0,1n =000,001,111，即0,1n中元素為由0,1組成的全體長為n的符號串，值域為0,1。n個命題變元共可構(gòu)成22n個不同的真值

31、函數(shù)。含命題變元P的1元真值函數(shù)共有4個。含兩個命題變元P,Q的真值函數(shù)共有16個。 1.5 聯(lián)結(jié)詞的完備集 定義1.17 設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集（Adequate Set of Connectives）。 定理1.10 S=，是聯(lián)結(jié)詞完備集。 證 因為任何n(n1)元真值函數(shù)都與惟一的一個主析取范式等值，而在主析取范式中僅含聯(lián)結(jié)詞，所以S=，是聯(lián)結(jié)詞完備集。 1.5 聯(lián)結(jié)詞的完備集 推論1.1 以下聯(lián)結(jié)詞集都是完備集：（1）S1=，（2）S2=，（3）S3=，（4）S4=，（5）S5=， 1.5 聯(lián)結(jié)詞的

32、完備集 證 （1），（2）的成立是顯然的。 （3）由于S=，是聯(lián)結(jié)詞完備集，因而任何真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞的公式表示。同時對于任意公式A和B，AB(AB) (AB)，因而任意真值函數(shù)都可以由僅含S3=，中的聯(lián)結(jié)詞的公式表示，所以S3是聯(lián)結(jié)詞完備集。 1.5 聯(lián)結(jié)詞的完備集 可以證明恒取0值的真值函數(shù)（即與矛盾式等值的真值函數(shù)）不能用僅含聯(lián)結(jié)詞集，中的聯(lián)結(jié)詞的公式表示，因而，不是聯(lián)結(jié)詞完備集。由此可知，等也都不是聯(lián)結(jié)詞完備集。所以，的任何子集都不是聯(lián)結(jié)詞完備集。 1.5 聯(lián)結(jié)詞的完備集 定義1.18 設(shè)P，Q為兩個命題，復(fù)合命題“P與Q的否定式”（“P或Q的否定式”）稱為P，Q的與非式

33、（或非式），記作PQ（PQ）。符號（）稱作為與非聯(lián)結(jié)詞（或非聯(lián)結(jié)詞）。PQ為真當(dāng)且僅當(dāng)P與Q不同時為真（PQ為真當(dāng)且僅當(dāng)P與Q同時為假）。 由定義不難看出 PQ(PQ)，PQ(PQ) 1.5 聯(lián)結(jié)詞的完備集 定理1.11 ，都是聯(lián)結(jié)詞完備集。 證 已知，為聯(lián)結(jié)詞完備集，因而只需證明其中的每個聯(lián)結(jié)詞都可以由定義即可。而 P(PP）PP (a) PQ(PQ)(PQ) (PQ)(PQ) (b) PQ(PQ)(PQ) PQ(PP)(QQ) (c) 由(a)(c)可知，是聯(lián)結(jié)詞完備集，類似可證是聯(lián)結(jié)詞完備集。 演繹推理 數(shù)理邏輯中，應(yīng)用公認(rèn)的推理規(guī)則(Rules of Inference)從一些前提(P

34、remise)中推導(dǎo)出結(jié)論來時，這種推導(dǎo)過程稱之為演繹推理(Deduction)或形式證明(Formal Proof)。1.6 命題邏輯的推理演算1 推理形式定義1.19 設(shè)1,2,n,都是命題公式。若(12n)是重言式，稱由前提1,2,n推出的推理是有效的或正確的，并稱是1,2,n的有效結(jié)論或邏輯結(jié)果（Logical Consequence），當(dāng)且僅當(dāng)(12n)是永真式記為12n或1,2 ,n（稱為重言蘊含或推理形式）1.6 命題邏輯的推理演算1.6 命題邏輯的推理演算 關(guān)于定義1.19還需做以下說明： （1）由前提1,2,n推結(jié)論的推理是否正確與各前提的排列次序無關(guān)，因而前提中的公式不一定

35、是序列，而是一個有限公式集合。若推理是正確的，則記為12n，否則記為12n。1.6 命題邏輯的推理演算 （2）符號與是兩個完全不同的符號，它們的區(qū)別與聯(lián)系類似于和的關(guān)系。不是命題聯(lián)結(jié)詞而是公式間的關(guān)系符號，而是命題聯(lián)結(jié)詞。這兩者之間有密切的聯(lián)系，即的充要條件是公式為重言式。 1.6 命題邏輯的推理演算 （3）必須把推理的有效性和結(jié)論的真實性區(qū)別開。有效的推理不一定產(chǎn)生真實的結(jié)論，產(chǎn)生真實結(jié)論的推理過程未必一定是有效的。再說，有效的推理中可能包含假的前提；而無效的推理卻可能包含真的前提。1.6 命題邏輯的推理演算 示例：教材例1.18 寫出下述推理關(guān)系的推理形式：“下午小王或去看電影或去游泳。他

36、沒去看電影。所以，他去游泳了。” 解 設(shè) P：小王下午去看電影；Q：小王下午去游泳。于是得到如下推理形式: 前提：PQ，P 結(jié)論：Q 推理形式為:(PQ)PQ 1.6 命題邏輯的推理演算1.6.2 推理規(guī)則 1前提引入規(guī)則(P) 在推理過程中，可以隨時引入已知的前提。 2結(jié)論引用規(guī)則(T) 在推理過程中，前面已推出的有效結(jié)論都可作為后續(xù)推理的前提引用。 3置換規(guī)則(R) 4代入規(guī)則(S)1.6 命題邏輯的推理演算1.6.3 推理定律 定理1.12 設(shè)，是兩個命題公式，當(dāng)且僅當(dāng)且。 定理1.13 設(shè)，是命題公式，若且，則。 定理1.14 設(shè)，是命題公式，則的充要條件是是矛盾式。1.6 命題邏輯的

37、推理演算 下面列出一些常用的推理定律（在后面的推理演算中以大寫字母I加以引用）。（1）化簡律 ， （2）附加律 ， （3）假言推理（又稱分離規(guī)則） ()1.6 命題邏輯的推理演算（4）假言三段論 ()()()（5）等價三段論 ()()()（6）析取三段論 ()（7）拒取式 ()（8）二難推理 ()()()1.6 命題邏輯的推理演算（9） ,（10），（11）()， ()（12）()()()（13）()()， ()()（14），1.6 命題邏輯的推理演算1.6.4 推理方法 1真值表法 要判斷如下推理形式是否成立： 12m或m 構(gòu)造命題公式12m 畫出該命題公式的真值表，如果從真值表中看出 該命

38、題公式是重言式，則說明 12m或m成立例15 證明 P（Q R）=（PQ）（PR） PQRQ RP(Q R）PQPR(PQ）(PR)(P(Q R)(PQ)(PR)0001111110011111110100111110111111111001100111011101111100010011111111111.6 命題邏輯的推理演算2直接證法 直接證法就是由一組前提，利用前面的四條推理規(guī)則，根據(jù)已知的命題等值公式（1.3節(jié)中的16組公式）和推理定律，推演而得到有效的結(jié)論。1.6 命題邏輯的推理演算 例1.21 證明(PQ)(PR)(QS)SR 證明 （1）PQ P （2）PQ R,E,(1) （

39、3）QS P （4）PS T,I,(2),(3) （5）SP R,E,(4) （6）PR P （7）SR T,I,(5),(6) （8）SR R,E,(7)1.6 命題邏輯的推理演算3. 間接證法 間接證法主要有兩種，一種就是我們經(jīng)常用的反證法，另外一種稱之為CP規(guī)則。1）反證法 要證明推理形式12m成立（記作），根據(jù)定理1.14可知，只須證明是矛盾式。因此，只須把作為附加前提加入推理過程中，推出矛盾即可。1.6 命題邏輯的推理演算 例1.22 證明PQ，QR，RSP 證明 用反證法，把(P)作為附加前提加入到前提的集合中去，證明由此導(dǎo)致矛盾。 (1) (P) P(附加) (2) P R,E,

40、(1) (3) PQ P (4) Q T,I,(2),(3) (5) QR P (6) R T,I,(4),(5) (7) RS P (8) R T,I,(7) (9) RR T,I,(6),(8),矛盾 因此，假設(shè)不成立，原推理形式正確。 1.6 命題邏輯的推理演算 2）CP規(guī)則 欲證()，即證()，亦即()永真。因為() ()()()，所以若將作為附加前提，證明成立，即得證()成立。這一證明方法稱為CP規(guī)則。1.6 命題邏輯的推理演算 例1.23 驗證下述推理是否正確。 或者邏輯學(xué)難學(xué)，或者有許多學(xué)生喜歡它；如果數(shù)學(xué)容易學(xué)，那么邏輯學(xué)并不難學(xué)。因此如果許多學(xué)生不喜歡邏輯，那么數(shù)學(xué)并不容易學(xué)。 解 求解上述類型的推理問題，應(yīng)先將命題符號化，然后寫出前提、結(jié)論和推理形式，最后進行判斷。 令P：邏輯學(xué)難學(xué)； Q：有許多學(xué)生喜歡邏輯學(xué)； R：數(shù)學(xué)容易學(xué)。 1.6 命題邏輯的推理演算前提：PQ，RP結(jié)論：QR推理形式：PQ，RPQR (1) QP(附加) (2) PQP (3) P T,I,(1),(2) (4) RP P (5) RT,I,(3),(4) (6) QR CP 因此整個推理正