課件代數(shù)結(jié)構(gòu)第一章

1、離散數(shù)學(xué)離散數(shù)學(xué) 主講主講 谷淑化谷淑化 中國地質(zhì)大學(xué)中國地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院一、學(xué)習(xí)離散數(shù)學(xué)課程的目的 離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)的一門核心基礎(chǔ)課程。離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)的一門核心基礎(chǔ)課程。 1 離散數(shù)學(xué)為計(jì)算機(jī)專業(yè)的后繼課程如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)離散數(shù)學(xué)為計(jì)算機(jī)專業(yè)的后繼課程如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫、編譯原理、網(wǎng)絡(luò)和算法設(shè)計(jì)等課程提供必要的數(shù)學(xué)基礎(chǔ)。據(jù)庫、編譯原理、網(wǎng)絡(luò)和算法設(shè)計(jì)等課程提供必要的數(shù)學(xué)基礎(chǔ)。計(jì)算機(jī)科學(xué)的一個(gè)重要特點(diǎn)是計(jì)算機(jī)科學(xué)的一個(gè)重要特點(diǎn)是離散性離散性. .它能夠處理的數(shù)據(jù)結(jié)構(gòu)它能夠處理的數(shù)據(jù)結(jié)構(gòu)都是離散結(jié)構(gòu)都是離散結(jié)構(gòu), ,所以學(xué)習(xí)離散數(shù)學(xué)是非常有必要的。所以學(xué)

2、習(xí)離散數(shù)學(xué)是非常有必要的。 2 2 離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，通過該課程的學(xué)習(xí)可離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，通過該課程的學(xué)習(xí)可以提高學(xué)生的抽象思維、嚴(yán)格推理以及綜合歸納分析能力，培養(yǎng)以提高學(xué)生的抽象思維、嚴(yán)格推理以及綜合歸納分析能力，培養(yǎng)出高素質(zhì)的人才。出高素質(zhì)的人才。 Edsger W. Dijkstra（19302002）我現(xiàn)在年紀(jì)大了我現(xiàn)在年紀(jì)大了, 搞了這么多搞了這么多年的軟件年的軟件, 錯(cuò)誤不知道犯了多錯(cuò)誤不知道犯了多少少, 現(xiàn)在覺悟了現(xiàn)在覺悟了, 我想假若我早我想假若我早年在數(shù)理邏輯上好好下點(diǎn)工夫年在數(shù)理邏輯上好好下點(diǎn)工夫的話的話, 我就不會(huì)犯這么多的錯(cuò)我就不會(huì)犯這么

3、多的錯(cuò)誤。不少東西誤。不少東西, 邏輯學(xué)家早就邏輯學(xué)家早就說了說了,可我不知道。要是我能年可我不知道。要是我能年輕輕20 歲歲, 我要回去學(xué)習(xí)邏輯。我要回去學(xué)習(xí)邏輯。二、離散數(shù)學(xué)課程的特點(diǎn)二、離散數(shù)學(xué)課程的特點(diǎn) 離散數(shù)學(xué)課程是應(yīng)計(jì)算機(jī)科學(xué)和技術(shù)發(fā)展的離散數(shù)學(xué)課程是應(yīng)計(jì)算機(jī)科學(xué)和技術(shù)發(fā)展的需要，綜合了高等數(shù)學(xué)的多個(gè)分支而形成的。需要，綜合了高等數(shù)學(xué)的多個(gè)分支而形成的。 其特點(diǎn)是其特點(diǎn)是以離散量為研究對(duì)象，內(nèi)容豐富，以離散量為研究對(duì)象，內(nèi)容豐富，涉及面較寬。因此概念多、定理多、推理多并且涉及面較寬。因此概念多、定理多、推理多并且內(nèi)容較為抽象內(nèi)容較為抽象。因此其學(xué)習(xí)有一定的難度。因此其學(xué)習(xí)有一定的難

4、度。 三、如何學(xué)好離散數(shù)學(xué)三、如何學(xué)好離散數(shù)學(xué) 要學(xué)好這門課程，首先必須充分認(rèn)識(shí)到這門課程的上要學(xué)好這門課程，首先必須充分認(rèn)識(shí)到這門課程的上述特點(diǎn)，需要做到以下幾點(diǎn)：述特點(diǎn)，需要做到以下幾點(diǎn)：1 熟讀教材。熟讀教材。 2 獨(dú)立思考，大量練習(xí)。獨(dú)立思考，大量練習(xí)。 3 注重抽象思維能力的培養(yǎng)。注重抽象思維能力的培養(yǎng)。四、四、 離散數(shù)學(xué)課程的主要內(nèi)容離散數(shù)學(xué)課程的主要內(nèi)容第四部分第四部分 圖論。圖論。包括圖的基本概念，幾種特殊的圖。包括圖的基本概念，幾種特殊的圖。離散數(shù)學(xué)課程的主要內(nèi)容可以分為四個(gè)部分：離散數(shù)學(xué)課程的主要內(nèi)容可以分為四個(gè)部分：第一部分第一部分 數(shù)理邏輯。數(shù)理邏輯。包括命題邏輯和謂詞

5、邏輯。包括命題邏輯和謂詞邏輯。第二部分第二部分 集合論。集合論。包括集合、關(guān)系和函數(shù)。包括集合、關(guān)系和函數(shù)。第三部分第三部分 代數(shù)系統(tǒng)。代數(shù)系統(tǒng)。包括代數(shù)系統(tǒng)的一般概念，幾類典型包括代數(shù)系統(tǒng)的一般概念，幾類典型的代數(shù)系統(tǒng)。的代數(shù)系統(tǒng)。五、五、 教材及參考書教材及參考書 1、教材：教材：離散數(shù)學(xué)離散數(shù)學(xué)，蔡之華主編，中國地質(zhì)大學(xué)出，蔡之華主編，中國地質(zhì)大學(xué)出版社版社。 2、參考教材、參考教材 馬振華，離散數(shù)學(xué)導(dǎo)引，清華大學(xué)出版社，馬振華，離散數(shù)學(xué)導(dǎo)引，清華大學(xué)出版社，1996. 王憲鈞，數(shù)理邏輯引論，北京大學(xué)出版社，王憲鈞，數(shù)理邏輯引論，北京大學(xué)出版社，1998，丘維丘維聲聲, 抽象代數(shù)基礎(chǔ)，高

6、等教育出版社，抽象代數(shù)基礎(chǔ)，高等教育出版社，2003. 離散數(shù)學(xué)習(xí)題集，耿素云，北大出版社離散數(shù)學(xué)習(xí)題集，耿素云，北大出版社 離散數(shù)學(xué)輔導(dǎo)及習(xí)題精解離散數(shù)學(xué)輔導(dǎo)及習(xí)題精解 湯光華編，上?？茖W(xué)技術(shù)文獻(xiàn)湯光華編，上?？茖W(xué)技術(shù)文獻(xiàn)出版社。出版社。 網(wǎng)絡(luò)資源網(wǎng)絡(luò)資源課程考核課程考核 平時(shí)成績（到課情況、書面作業(yè)、平時(shí)平時(shí)成績（到課情況、書面作業(yè)、平時(shí)測驗(yàn)）占測驗(yàn)）占30%，期末考試占，期末考試占70%。 形式化形式化 規(guī)范化規(guī)范化 推理推理 公理化公理化 1. 1. 命題邏輯的基本概念、命題聯(lián)結(jié)詞命題邏輯的基本概念、命題聯(lián)結(jié)詞 2. 2. 命題公式、自然語言的形式化命題公式、自然語言的形式化 3. 3

7、. 等值演算等值演算 4. 4. 范式范式 5. 5. 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 6. 6. 推理理論推理理論 7. 7. 命題邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用命題邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用1 命題與命題變?cè)}與命題變?cè)猯命題？命題？能夠分辨真假的陳述句。能夠分辨真假的陳述句。 注：注： (1)(1)命題是陳述句。其他的語句，如疑問句、祈使句、感嘆句均不是命題是陳述句。其他的語句，如疑問句、祈使句、感嘆句均不是命題；命題； (2)(2)這個(gè)陳述句表示的內(nèi)容可以分辨真假，而且不是真就是假，不能這個(gè)陳述句表示的內(nèi)容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假不真也不假，也不能既真又假

8、怎樣研究命題？怎樣研究命題？簡單命題簡單命題“構(gòu)造構(gòu)造”復(fù)雜復(fù)雜命題命題l 命題的真值？命題的真值？作為命題的陳述句所表示的判斷結(jié)果作為命題的陳述句所表示的判斷結(jié)果 真值只取兩個(gè)值：真或假。凡是與真值只取兩個(gè)值：真或假。凡是與事實(shí)事實(shí)相符的陳述句是真相符的陳述句是真命題，而與事實(shí)不符合的陳述句是假命題。通常用命題，而與事實(shí)不符合的陳述句是假命題。通常用1 1（或（或字母字母T T）表示真，用）表示真，用0 0（或字母（或字母F F）表示假。）表示假。示例示例1.11.1 判斷下列語句是否為命題，并指出其真值判斷下列語句是否為命題，并指出其真值n一個(gè)語句本身是否能分辨真假與我們是否知道它的真假是

9、兩回事。也就是說，對(duì)于一個(gè)句子，有時(shí)我們可能無法判定它的真假，但它本身卻是有真假的，那么這個(gè)語句是命題，否則就不是命題。n悖論不是命題?！拔抑恢酪患拢蔷褪鞘裁炊疾恢??！薄把员M?！眑 命題的分類命題的分類n原子命題：原子命題：是指不能再分解為更簡單命題的命題；是指不能再分解為更簡單命題的命題；n復(fù)合命題：復(fù)合命題：是指由若干命題用聯(lián)結(jié)詞組成的新命題。是指由若干命題用聯(lián)結(jié)詞組成的新命題。 l 命題常元？命題變?cè)棵}常元？命題變?cè)空嬷荡_定與否的原子命題。真值確定與否的原子命題。 如果命題如果命題符號(hào)符號(hào)P P代表命題常元?jiǎng)t意味它是某個(gè)具體命題的符號(hào)化，如代表命題常元?jiǎng)t意味它是某個(gè)具體命題

10、的符號(hào)化，如果果P P代表命題變?cè)獎(jiǎng)t意味著它可指代任何具體命題。如果沒有特別指代表命題變?cè)獎(jiǎng)t意味著它可指代任何具體命題。如果沒有特別指明，通常來說命題符號(hào)明，通常來說命題符號(hào)P P等是命題變?cè)?，即可指代任何命題。等是命題變?cè)纯芍复魏蚊}。 2 命題聯(lián)結(jié)詞及真值表命題聯(lián)結(jié)詞及真值表 否定詞否定詞“”（或（或“ ”）否定詞是一元聯(lián)結(jié)詞。否定詞是一元聯(lián)結(jié)詞。相當(dāng)于自然語言中的相當(dāng)于自然語言中的“非非”、“不不”等，真值表如右圖。等，真值表如右圖。例：例：設(shè)設(shè)P：上海是一個(gè)城市；：上海是一個(gè)城市； 則有則有 P：上海不是一個(gè)城市：上海不是一個(gè)城市; P P 0 1 1 0 合取詞合取詞“”合取詞

11、是二元聯(lián)結(jié)詞。合取詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的相當(dāng)于自然語言中的“與與” 、“并且并且” 、“而且而且” 、“也也”等，等，真值表如右圖。真值表如右圖。例例 設(shè)設(shè)P：我們?nèi)タ措娪啊＃何覀內(nèi)タ措娪啊?Q：房間里有十張桌子。：房間里有十張桌子。 則則P Q表示表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子。我們?nèi)タ措娪安⑶曳块g里有十張桌子?！?P Q P Q 0 0 0 0 1 0 1 0 0 1 1 1 析取詞析取詞“” 析取詞是二元聯(lián)結(jié)詞。析取詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的相當(dāng)于自然語言中的“或或”、“要么要么要么要么”等，真值表等，真值表如右圖。如右圖。 P Q PQ 0 0 0 0 1

12、1 1 0 1 1 1 1聯(lián)結(jié)詞聯(lián)結(jié)詞“”“”是自然語言中的是自然語言中的“或或”、“或者或者”等邏輯抽象（等邏輯抽象（可兼或可兼或）；）；但但“或或”可指可指 “ “可兼或可兼或”、“排斥或排斥或”；蘊(yùn)含詞蘊(yùn)含詞“” 蘊(yùn)含詞是二元聯(lián)結(jié)詞。蘊(yùn)含詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的相當(dāng)于自然語言中的“若若則則”、“如如果果就就”，真值表如右圖。，真值表如右圖。 P QP Q 0 0 1 0 1 1 1 0 0 1 1 1 在自然語言中，前件為假，不管結(jié)論真假，整個(gè)語句的意義，往往無法判斷。但在在自然語言中，前件為假，不管結(jié)論真假，整個(gè)語句的意義，往往無法判斷。但在數(shù)理邏輯中，當(dāng)前件數(shù)理邏輯中，當(dāng)前

13、件P P為假時(shí)，不管為假時(shí)，不管Q Q的真假如何，則的真假如何，則PQPQ都為真。都為真。實(shí)質(zhì)蘊(yùn)涵實(shí)質(zhì)蘊(yùn)涵意味著可從意味著可從假的前提推出任何命題來，或兩個(gè)沒有內(nèi)在聯(lián)系的命題之間存在蘊(yùn)涵關(guān)系假的前提推出任何命題來，或兩個(gè)沒有內(nèi)在聯(lián)系的命題之間存在蘊(yùn)涵關(guān)系 “PQPQ”是表示自然語言中的是表示自然語言中的“因?yàn)橐驗(yàn)镻 P所以所以Q”Q”、“如果如果P,P,則則Q”Q”，“只有只有Q Q才才P”P”、“除非除非Q Q，否則，否則非非P”P”、“P P僅當(dāng)僅當(dāng)Q”Q”等的邏輯抽象。等的邏輯抽象。 等價(jià)詞等價(jià)詞“ ” 等價(jià)詞是二元聯(lián)結(jié)詞。等價(jià)詞是二元聯(lián)結(jié)詞。相當(dāng)于自然語言中的相當(dāng)于自然語言中的“等價(jià)等

14、價(jià)”、“當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)”、“充要條件充要條件”等，等，真值表如右圖。真值表如右圖。 P Q PQ 0 0 1 0 1 0 1 0 0 1 1 1 例例 非本倉庫工作人員，一律不得入內(nèi)。非本倉庫工作人員，一律不得入內(nèi)。解解 令令P：某人不是倉庫工作人員；：某人不是倉庫工作人員； Q Q：某人不可以進(jìn)入倉庫。：某人不可以進(jìn)入倉庫。 則則 上述命題可表示為上述命題可表示為PQ。優(yōu)先級(jí)順序優(yōu)先級(jí)順序： 的優(yōu)先級(jí)最高，接著依次是的優(yōu)先級(jí)最高，接著依次是 ， ，和和。練習(xí)練習(xí)1.1 1.1 判斷下列語句是否為命題判斷下列語句是否為命題1.明年的中秋節(jié)的晚上是晴天2.地球外的星球上存在生物3.x + y

15、104.但愿中國隊(duì)能取勝。5.3 是有理數(shù) 練習(xí)練習(xí)1.2 1.2 符號(hào)化下列命題符號(hào)化下列命題1.今晚我上網(wǎng)2.今晚我去教室自習(xí)3.他已經(jīng)回家度假去了4.今晚我上網(wǎng)或我去教室自習(xí)5.今晚我上網(wǎng)或者他已經(jīng)回家度假去了6.如果今天下雨了，那么秋天就到了 聯(lián)結(jié)詞聯(lián)結(jié)詞“”、“”、“”與構(gòu)成與構(gòu)成電路電路的與門、或門和非門電路是相對(duì)應(yīng)的，從的與門、或門和非門電路是相對(duì)應(yīng)的，從而命題邏輯是計(jì)算機(jī)硬件電路的表示、分析和設(shè)計(jì)的重要工具。而命題邏輯是計(jì)算機(jī)硬件電路的表示、分析和設(shè)計(jì)的重要工具。 聯(lián)結(jié)詞聯(lián)結(jié)詞“”、“”、“”的的“聯(lián)接聯(lián)接運(yùn)算運(yùn)算”結(jié)果具有結(jié)果具有對(duì)稱性對(duì)稱性，而聯(lián)結(jié)詞，而聯(lián)結(jié)詞“”、“”沒有

16、；沒有； 真值表；注意真值表；注意“”、“”的含義的含義 聯(lián)結(jié)詞是句子與句子之間的聯(lián)結(jié)詞是句子與句子之間的聯(lián)結(jié)聯(lián)結(jié)；聯(lián)結(jié)詞連接的是兩個(gè)命題真值之間的聯(lián)結(jié)，而不是；聯(lián)結(jié)詞連接的是兩個(gè)命題真值之間的聯(lián)結(jié)，而不是命題內(nèi)容命題內(nèi)容之間的連接，因此復(fù)合命題的真值只取決于構(gòu)成他們的各命題的真值，而與之間的連接，因此復(fù)合命題的真值只取決于構(gòu)成他們的各命題的真值，而與它們的內(nèi)容、含義無關(guān)，與聯(lián)結(jié)詞所連接的兩命題之間是否有關(guān)系無關(guān)；它們的內(nèi)容、含義無關(guān)，與聯(lián)結(jié)詞所連接的兩命題之間是否有關(guān)系無關(guān)； 命題形式與命題意義命題形式與命題意義1 命題公式命題公式(Propositional Formula)(Propos

17、itional Formula)？構(gòu)造構(gòu)造- -歸納（計(jì)算機(jī)）歸納（計(jì)算機(jī)）Q)1 命題公式命題公式(Propositional Formula)(Propositional Formula)？構(gòu)造構(gòu)造- -歸納（計(jì)算機(jī)）歸納（計(jì)算機(jī)）P PQ,PQ,PQ),Q), R RP P是命題公式嗎？是命題公式嗎？命題公式是命題嗎？命題公式是命題嗎？如何符號(hào)化命題？如何符號(hào)化命題？示例示例1.31.3 (p (p q) q) ( ( p) p) (q (q r) r)是不是命題公式？是不是命題公式？它通過以下步驟生成：它通過以下步驟生成：1. p1. p是公式；是公式；2. q2. q是公式；是公式；

18、3. (p 3. (p q) q)是公式；是公式；4. (4. ( p)p)是公式；是公式；5. r5. r是公式；是公式；6. (q 6. (q r) r)是公式；是公式；7. (7. ( p) p) (q (q r) r)是公式；是公式；8. (p 8. (p q) q) ( ( p) p) (q (q r) r)是公式。是公式。示例示例1.2 1.2 命題公式命題公式(PQ) ( PR) IF P THEN Q ELSE R可以形象地用下面的一棵樹來表示可以形象地用下面的一棵樹來表示這種樹在形式語言與自動(dòng)機(jī)中就稱為這種樹在形式語言與自動(dòng)機(jī)中就稱為語法分析樹。語法分析樹。 例例 將下列命題

19、符號(hào)化將下列命題符號(hào)化 （1）我們不能既劃船又跑步；）我們不能既劃船又跑步； （2）如果你來了，那么他唱不唱歌將看你是否伴奏而定；）如果你來了，那么他唱不唱歌將看你是否伴奏而定； （1） 令令P：我們劃船；：我們劃船；Q：我們跑步。則命題可：我們跑步。則命題可 表示為表示為( (PQ）。）。 （2） 令令P：你來了；：你來了；Q：他唱歌；：他唱歌；R：你伴奏。：你伴奏。 則命題可表示為則命題可表示為 P（QR） （3）如果李明是體育愛好者，但不是文藝愛好者，那么李明）如果李明是體育愛好者，但不是文藝愛好者，那么李明不是文體愛好者；不是文體愛好者； 令令P：李明是體育愛好者；：李明是體育愛好者；

20、Q：李明是文藝愛好者。：李明是文藝愛好者。 則命題可表示為（則命題可表示為（P Q）（P Q） 。注：注： 如果給出一個(gè)命題公式：（如果給出一個(gè)命題公式：（P Q）（PR） 求它的真值之前要給出真值指派。求它的真值之前要給出真值指派。 完全指派、部分指派、成真指派、完全指派、部分指派、成真指派、成假指派、真值表、子公式。成假指派、真值表、子公式。2 命題公式類型命題公式類型 重言式或永真式（重言式或永真式（TautologyTautology） 矛盾式或永假式（矛盾式或永假式（ContradictionContradiction） 可滿足式（可滿足式（ContingencyContingenc

21、y）公式的值？公式的值？指派指派真值表真值表判定公式類型判定公式類型命題公式的值？命題公式的值？真？假？真？假？真值函數(shù)真值函數(shù)示例示例1.31.3 教材教材P6P6例例1.61.6練習(xí)練習(xí)1.3 1.3 判斷下列公式的類型判斷下列公式的類型1 (p(q p) ) r2 ( (pq) q) r3 (p q)( p(q r)p pq qr rq q p pp p(q(q p)p)(p(p(q(q p)p) r r0 00 00 00 01 11 10 00 01 10 01 11 10 01 10 01 11 11 10 01 11 11 11 11 11 10 00 01 11 11 11 1

22、0 01 11 11 11 11 11 10 01 11 11 11 11 11 11 11 11 1( p(q p) r p pq qr rp pq q (p(pq)q)( ( (p(pq)q) q q( (p(pq)q) q)q) r r0 00 00 01 10 00 00 00 00 01 11 10 00 00 00 01 10 01 10 00 00 00 01 11 11 10 00 00 01 10 00 00 01 10 00 01 10 01 10 01 10 00 01 11 10 01 10 00 00 01 11 11 11 10 00 00 0( (pq) q) r

23、p pq qr rp p q q p pq q r r p pq q r r(p(p q)q)( ( p p(q(q r)r)0 00 00 00 01 10 00 01 10 00 01 10 01 10 00 01 10 01 10 01 11 10 00 00 00 01 11 11 11 11 11 11 11 10 00 01 10 00 01 11 11 10 01 11 10 00 01 11 11 11 10 01 10 00 01 11 11 11 11 11 10 01 10 00 0(p q)( p (q r)真值函數(shù)真值函數(shù)p pq qr r(p(p(q(q p)p)

24、r r( (p(pq)q) q)q) r r p pq q r r.0 00 00 01 10 00 0? ?0 00 01 11 10 00 0? ?0 01 10 01 10 00 0? ?0 01 11 11 10 01 1? ?1 10 00 01 10 01 1? ?1 10 01 11 10 01 1? ?1 11 10 01 10 01 1? ?1 11 11 11 10 00 0? ?1 等值式等值式函數(shù)相等？函數(shù)相等？命題公式相等？命題公式相等？定義定義1-8 設(shè)設(shè) 和和 是兩個(gè)命題公式是兩個(gè)命題公式, 若若 、 構(gòu)成的等價(jià)式構(gòu)成的等價(jià)式為永真式為永真式,則稱公式則稱公式 和

25、和 等值，記為等值，記為 ,稱稱 為等價(jià)式。為等價(jià)式。例如例如 代數(shù)中代數(shù)中令令F1(x, y) = (x + y)2, F2(x, y) = x2 + 2xy + y2 則則 F1(x, y) = F2(x, y) 類似地，在命題邏輯中類似地，在命題邏輯中例如例如 令令 F1(P1, P2) = P1 P2 F2(P1, P2) = P2 P1 則則 P1 P2 P2 P1 即即 F1(P1, P2) F2(P1, P2) 當(dāng)且僅當(dāng) 為重言式為重言式 ：一種關(guān)系比較，自然語言中的符號(hào)：一種關(guān)系比較，自然語言中的符號(hào)：運(yùn)算符號(hào)，可以計(jì)算（從而用于判斷等價(jià)關(guān)系）可以作：運(yùn)算符號(hào)，可以計(jì)算（從而用

26、于判斷等價(jià)關(guān)系）可以作為程序語言的符號(hào)為程序語言的符號(hào)示例示例1.41.4 閱讀教材閱讀教材P8P8例例1.71.7等值公式等值公式( (命題定律命題定律) )1 1 交換律、結(jié)合律、分配律交換律、結(jié)合律、分配律雙否律、等冪律、德摩根律雙否律、等冪律、德摩根律2 2 吸收律、零一律、同一律、排中律、矛盾律吸收律、零一律、同一律、排中律、矛盾律3 3 蘊(yùn)含等值式蘊(yùn)含等值式4 4 假言易位（逆否律）、假言易位（逆否律）、等價(jià)等價(jià)等值式、等值式、等價(jià)等價(jià)否定律、否定律、5 5 歸謬論歸謬論判斷命題公式是否永判斷命題公式是否永真真真值表方法？真值表方法？當(dāng)命題變量增多時(shí)？當(dāng)命題變量增多時(shí)？ 吸收律吸收

27、律 ( () )， ( () ) 零一律零一律 1 11 1， 0 00 0 同一律同一律0 0， 1 1 排中律排中律1 1 矛盾律矛盾律 0 0 蘊(yùn)含等值式蘊(yùn)含等值式 假言易位假言易位( (逆否律）逆否律） 等價(jià)等值式等價(jià)等值式( () ) ( () )， ( () ) ( () ) 等價(jià)否定等值式等價(jià)否定等值式 歸謬論歸謬論 ( () ) ( () ) 等值式證明示例等值式證明示例1.41.4 閱讀教材閱讀教材P9P9例例1.81.82 等值演算等值演算兩個(gè)定理兩個(gè)定理代入定理代入定理置換定理置換定理有兩種方法：真值表方法，命題演算方法有兩種方法：真值表方法，命題演算方法如何進(jìn)行等值演算

28、如何進(jìn)行等值演算1、真值表方法、真值表方法 例例1 用真值表方法證明用真值表方法證明 E10： (P Q) PQ 解解 令：令：A= (P Q)，B= PQ，構(gòu)造，構(gòu)造A，B 以及以及A B的真值表如下：的真值表如下： 由于公式由于公式AB所標(biāo)記的列全為所標(biāo)記的列全為1，因此，因此AB。 0PQP Q (P Q) P Q PQAB00111110110100111100101101000012等值演算方法等值演算方法例如例如 在初等代數(shù)中在初等代數(shù)中證明恒等式證明恒等式(x + 1)(x2 x + 1)(x - - 1)(x2 + x + 1)=x6 1證明證明 原式原式= (x + 1)(x

29、2 x + 1)(x - - 1)(x2 + x + 1) = (x3 + 1)(x3 1) = (x3)2 1 = x6 1 (1) 代入規(guī)則代入規(guī)則 代入規(guī)則代入規(guī)則 對(duì)于重言式中的任一命題變?cè)霈F(xiàn)的每一處均對(duì)于重言式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。用同一命題公式代入，得到的仍是重言式。 例如例如 F=（PQ）（ QP）是重言式，若）是重言式，若用公式用公式AB代換命題變?cè)鷵Q命題變?cè)狿得公式得公式 F1=（AB）Q）（ Q（AB），）， F1仍是重言式。仍是重言式。注意：注意：因?yàn)橐驗(yàn)锳 B當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A B是重言式。所以，若對(duì)于等是重言式。所以，

30、若對(duì)于等值式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，值式中的任一命題變?cè)霈F(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。則得到的仍是等值式。例如例如 (P Q) ( P Q )，即即 (P Q) P Q是永真公式是永真公式于是，用于是，用PS對(duì)對(duì)P進(jìn)行代入進(jìn)行代入得得 (PS)Q) (PS) Q (2)(2)置換規(guī)則置換規(guī)則 設(shè)設(shè)C C是公式是公式A A的子公式，的子公式，C CD D。如果將公式如果將公式A A中的子公式中的子公式C C置換成公式置換成公式D D之后，得到之后，得到的公式是的公式是B B，則，則A AB B。 若若 A=(A=( PQ)PQ)(P(PQ)(RQ

31、)(R S)S) B=( B=( PQ)PQ)( ( ( PQ)PQ)(R(R S)S) 則則 A A B B 例如例如 (3)(3) 等值演算等值演算 等值演算是指利用已知的一些等值式，根據(jù)置換等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過程。一些等值式的過程。 由代入規(guī)則知前述的基本等值式，不僅對(duì)任意的命由代入規(guī)則知前述的基本等值式，不僅對(duì)任意的命題變?cè)}變?cè)狿 P，Q Q，R R是成立的，而且當(dāng)是成立的，而且當(dāng)P P，Q Q，R R分別為命題公分別為命題公式時(shí)，這些等值式也成立。式時(shí)，這

32、些等值式也成立。 例例 證明命題公式的等值關(guān)系：證明命題公式的等值關(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)系證明下列命題公式的等值關(guān)系 (P Q ) ( P ( P Q ) ) P Q 證明證明 (P Q) ( P ( P Q) (P Q) ( ( P P ) Q ) (結(jié)合律結(jié)合律) (P Q) ( P Q) (等冪律等冪律) ( P Q ) ( P Q ) (交換律交

33、換律) P (Q (P Q) (結(jié)合律結(jié)合律) P Q (交換律，吸收律交換律，吸收律) 例例 判別下列公式的類型。判別下列公式的類型。 （1） Q ( P（ PQ）) 解解 Q （ P（ PQ） Q （P（ PQ）Q （P P）（PQ）Q （1（PQ）Q （PQ）Q P Q（Q Q） P0所以所以Q ( P ( PQ)是矛盾式。是矛盾式。（2）（）（PQ） P 解：解：（PQ） P （ PQ） P P于是該公式是可滿足式。于是該公式是可滿足式。 (3) (P Q)P) Q 定義定義1.10 如果命題公式如果命題公式 中只出現(xiàn)命題變?cè)⒚}中只出現(xiàn)命題變?cè)?、命題常元、命題連結(jié)詞常元、命題連結(jié)詞

34、“ ”、“”、“”，則稱，則稱 為限為限制性命題公式。制性命題公式。 定義定義1.111.11 在限制性命題公式在限制性命題公式 中，將連結(jié)詞中，將連結(jié)詞“”換成換成“”， 將將 “”換成換成 “”、將、將0換成換成1，1換成換成0，所得到的公式稱為所得到的公式稱為 的的對(duì)偶式對(duì)偶式，記為，記為 * *。 顯然，顯然， 和和 *互為對(duì)偶式?；閷?duì)偶式。例如，公式例如，公式 (P Q) ( R)與公式與公式 (P Q) ( R)需求需求 命題公式規(guī)范化？命題公式規(guī)范化？ AI (AI (自動(dòng)推理，自動(dòng)推理，RoughRough集數(shù)據(jù)約簡集數(shù)據(jù)約簡) ) 電路設(shè)計(jì)電路設(shè)計(jì)( (只根據(jù)真值表即可設(shè)計(jì)

35、電路）只根據(jù)真值表即可設(shè)計(jì)電路）可行可行聯(lián)接詞功能完備集：聯(lián)接詞功能完備集： , , , , 何為命題公式規(guī)范形式？何為命題公式規(guī)范形式？ 文字文字 P， P（P與與 P稱為互補(bǔ)對(duì)）稱為互補(bǔ)對(duì)） 質(zhì)合取質(zhì)合取/ /析取式析取式 P， P， P Q，PQ R P， Q，P Q， P QR 析取析取/ /合取范式合取范式 主析取主析取/ /合取范式合取范式 定理定理1.5 (1)質(zhì)合取式為矛盾式的充要條件：它包含一個(gè)互補(bǔ)對(duì)。質(zhì)合取式為矛盾式的充要條件：它包含一個(gè)互補(bǔ)對(duì)。 (2)質(zhì)析取式為重言式的充要條件：它包含一個(gè)互補(bǔ)對(duì)。質(zhì)析取式為重言式的充要條件：它包含一個(gè)互補(bǔ)對(duì)。析取范式析取范式（Disjun

36、ctive Normal FormDisjunctive Normal Form） 1 12 2 n n i i為質(zhì)合取式為質(zhì)合取式。 (P (P Q)Q) ( ( P PQ)Q)合取范式合取范式（Conjunctive Normal FormConjunctive Normal Form） 1 12 2 n n i i為質(zhì)析取式為質(zhì)析取式。 (P (P R)R) (P(P Q QR)R) ( ( P PR)R)定理定理1.6 1.6 任一命題公式存在任一命題公式存在析取范式析取范式 、合取范式。合取范式。 如何求解析取范式和合取范式？如何求解析取范式和合取范式？ (1)(1)消消去聯(lián)結(jié)詞去聯(lián)

37、結(jié)詞，； (2)(2)將聯(lián)結(jié)詞將聯(lián)結(jié)詞 向內(nèi)深入，使之只作用于命題向內(nèi)深入，使之只作用于命題變?cè)蛔冊(cè)?(3)(3)利用利用分配律分配律將公式化為所需要的范式。將公式化為所需要的范式。示例示例1.41.4 閱讀教材閱讀教材P14P14例例1.121.12應(yīng)用應(yīng)用 教材教材P15P15定理定理1.71.7練習(xí)練習(xí) 求命題公式的析取范式和合取范式求命題公式的析取范式和合取范式(1).求求( PQ) (PR)的析取范式和合取范式的析取范式和合取范式(2).求求(PQ) (P R)的析取范式和合取范式的析取范式和合取范式解解 (1)求求( PQ) (PR)的析取范式：的析取范式：( PQ) (PR)

38、 (P Q) ( P R) / 蘊(yùn)涵等值式蘊(yùn)涵等值式(P Q) ( P R) / 雙否律雙否律(PP) (P R) (QP) (Q R)/分配律分配律(P R) (QP) (Q R) /(PP)是矛盾式是矛盾式顯然顯然( PQ) (PR)的合取范式為的合取范式為(P Q) ( P R)。(2)求求(PQ) (P R)的合取范式：的合取范式：(PQ) (P R)( P Q) (P R) ( P Q P) ( P Q R)顯然顯然(PQ) (P R)的析取范式為的析取范式為( P) Q R。注意到：注意到：一個(gè)命題公式的合取范式和析取范式不具有唯一性。一個(gè)命題公式的合取范式和析取范式不具有唯一性。

39、 定義定義 1.14 1.14 在含在含n n個(gè)命題變?cè)馁|(zhì)合取式（質(zhì)析取式）個(gè)命題變?cè)馁|(zhì)合取式（質(zhì)析取式）中，若每個(gè)命題變?cè)c其否定不同時(shí)存在，而二者之一必中，若每個(gè)命題變?cè)c其否定不同時(shí)存在，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第出現(xiàn)且僅出現(xiàn)一次，且第i i個(gè)命題變?cè)蚱浞穸ǔ霈F(xiàn)在從個(gè)命題變?cè)蚱浞穸ǔ霈F(xiàn)在從左算起的第左算起的第i i位上，這樣的質(zhì)合取式（質(zhì)析取式）稱為極位上，這樣的質(zhì)合取式（質(zhì)析取式）稱為極小項(xiàng)（極大項(xiàng)）。小項(xiàng)（極大項(xiàng)）。例如，例如，兩個(gè)命題變?cè)獌蓚€(gè)命題變?cè)狿,Q共可產(chǎn)生共可產(chǎn)生4個(gè)極小項(xiàng)，分別為：個(gè)極小項(xiàng)，分別為： P Q對(duì)應(yīng)對(duì)應(yīng)00，記為，記為m0； P Q對(duì)應(yīng)對(duì)應(yīng)01

40、，記為，記為m1；P Q對(duì)應(yīng)對(duì)應(yīng)10，記為，記為m2； P Q對(duì)應(yīng)對(duì)應(yīng)11，記為，記為m3；也可以產(chǎn)生也可以產(chǎn)生4個(gè)極大項(xiàng)，分別為：個(gè)極大項(xiàng)，分別為：P Q對(duì)應(yīng)對(duì)應(yīng)00，記為，記為M0； P Q對(duì)應(yīng)對(duì)應(yīng)01，記為，記為M1； P Q對(duì)應(yīng)對(duì)應(yīng)10，記為，記為M2； P Q對(duì)應(yīng)對(duì)應(yīng)11，記為，記為M3； 定理定理1.8 設(shè)設(shè)mi和和Mi是命題變?cè)敲}變?cè)狿1 ,P2 , ,Pn形成的極形成的極小項(xiàng)和極大項(xiàng)，則小項(xiàng)和極大項(xiàng)，則 miMi ， Mi mi 定義定義1.15 設(shè)命題公式設(shè)命題公式 中含中含n n個(gè)命題變?cè)?，如果個(gè)命題變?cè)绻?的析的析取范式（合取范式）中的質(zhì)合取式（質(zhì)析取式）都是極小

41、取范式（合取范式）中的質(zhì)合取式（質(zhì)析取式）都是極小項(xiàng)（極大項(xiàng)），則稱該析取范式（合取范式）為項(xiàng)（極大項(xiàng)），則稱該析取范式（合取范式）為 的主析的主析取范式（主合取范式）。取范式（主合取范式）。 主析取主析取/ /合取范式合取范式如何如何求解？求解？極小項(xiàng)、極大項(xiàng)極小項(xiàng)、極大項(xiàng)1 1 真值表法真值表法 2 2 等值演算等值演算例例 求下列命題公式的主析取范式和主合取范式。求下列命題公式的主析取范式和主合取范式。 1）P(QR) 2）(PQ)RP Q R P (Q R) (P Q)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

42、 1 1 1 0 0 0 1 1 1 1 1 根據(jù)真值表中根據(jù)真值表中P(QR)真值為真值為1的賦值，所對(duì)應(yīng)的的賦值，所對(duì)應(yīng)的極小項(xiàng)析取即為極小項(xiàng)析取即為P(QR)的主析取范式，所以有：的主析取范式，所以有：P(QR) m0 m1 m2 m3 m4 m5 m7(PQR) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) 根據(jù)真值表中根據(jù)真值表中P(QR)真值為真值為0的賦值，所對(duì)應(yīng)的的賦值，所對(duì)應(yīng)的極大項(xiàng)合取即為極大項(xiàng)合取即為P(QR)的主合取范式，的主合取范式，所以有：所以有：P(QR) M6 PQR同理，同理，(PQ)R的主析取范式為：的主析取范式為：(PQR)(PQR)(PQ

43、R)(PQR) (PQR)(PQ)R的主合取范式為：的主合取范式為：(PQR)(PQR)(PQR) 從上面的例題中可以看出：矛盾式?jīng)]有主析取范式，重言式?jīng)]有從上面的例題中可以看出：矛盾式?jīng)]有主析取范式，重言式?jīng)]有主合取范式。主合取范式。 定理定理1.9 任何一個(gè)不為矛盾式（重言式）的命題公式任何一個(gè)不為矛盾式（重言式）的命題公式都存在著與之等值的主析取范式（主合取范式），并且是都存在著與之等值的主析取范式（主合取范式），并且是唯一的。唯一的。示例示例 教材教材P17P17例例1.161.16應(yīng)用應(yīng)用 教材教材P18P18例例1.171.17真值表方法真值表方法等值演算方法等值演算方法如何求解主

44、析取范式和主合取范式？如何求解主析取范式和主合取范式？ (1)化為析取范式和合取范式；化為析取范式和合取范式； (2)利用同一律消去矛盾的質(zhì)合取式（重言的質(zhì)析取式）；利用同一律消去矛盾的質(zhì)合取式（重言的質(zhì)析取式）；（3）利用等冪律消去相同的質(zhì)合取式（質(zhì)析取式）以及質(zhì)合取式）利用等冪律消去相同的質(zhì)合取式（質(zhì)析取式）以及質(zhì)合取式（質(zhì)析取式）中相同的合取項(xiàng)（析取項(xiàng)）；（質(zhì)析取式）中相同的合取項(xiàng)（析取項(xiàng)）； （4）利用同一律、分配律將每一合取項(xiàng)（析取項(xiàng)）化為極小項(xiàng)）利用同一律、分配律將每一合取項(xiàng)（析取項(xiàng)）化為極小項(xiàng)（極大項(xiàng)）。（極大項(xiàng)）。示例示例 教材教材P17P17例例1.161.16求公式求公式(

45、 ( P PR)R) (P(PQ)Q)的主合取范式。的主合取范式。解解 ( ( P PR)R) (P(PQ) Q) (P(P R)R) ( ( P P Q)Q) (P(PQ)Q)(P(P (Q(QQ)Q) R)R) ( ( P P Q Q (R(RR)R) (P(PQ Q (R(RR)R)(P(P Q Q R)R) (P(PQ Q R)R) ( ( P P Q Q R)R) ( ( P P Q QR)R) (P(PQ Q R)R) (P(PQ QR)R)(P(P Q Q R)R) (P(PQ Q R)R) (P(PQ QR)R) ( ( P P Q Q R)R) ( ( P P Q QR) R

46、) M M0 0 M M2 2 M M3 3 M M4 4 M M5 5此即此即所求的所求的主合取范式。主合取范式。因此，上式的主析取范式因此，上式的主析取范式m1 1 m6 6 m7 7練習(xí)練習(xí) 求命題公式的主范式求命題公式的主范式(1).(1).求求( ( P PQ Q) ) (P(PR R) )的主析取范式和主合取范式的主析取范式和主合取范式(2).(2).求求(P(PQ Q) ) (P(P R R) )的主析取范式和主合取范式的主析取范式和主合取范式(1)(1)根據(jù)前例知根據(jù)前例知( ( P PQ)Q) (P(PR)R)的一個(gè)析取范式是的一個(gè)析取范式是(P(P R)R) (Q(QP)P

47、) (Q(Q R)R)，現(xiàn)在將其中的每個(gè)簡單合，現(xiàn)在將其中的每個(gè)簡單合取式展開為含有所有命題變?cè)臉O小項(xiàng)的析?。喝∈秸归_為含有所有命題變?cè)臉O小項(xiàng)的析?。?(P(P R)R)展開為展開為(P(P Q Q R)R) (P(PQ Q R),(QR),(QP)P)展開為展開為( ( P P Q Q R) R) ( ( P P Q QR),(QR),(Q R)R)展開為展開為(P(P Q Q R)R) ( ( P P Q Q R)R)因此因此( ( P PQ)Q) (P(PR)R)的主析取范式為的主析取范式為(P(P Q Q R)R) (P(PQ Q R)R) ( ( P P Q Q R)R) ( (

48、 P P Q QR)R)，按極小項(xiàng)按極小項(xiàng)所對(duì)應(yīng)的二進(jìn)制數(shù)的大小重新排列為所對(duì)應(yīng)的二進(jìn)制數(shù)的大小重新排列為( ( P P Q QR)R) ( ( P P Q Q R)R) (P(PQ Q R)R) (P(P Q Q R),R),可記為可記為m m2 2 m m3 3 m m5 5 m m7 7。討論討論 范式一定存在，但主范式不一定存在？范式一定存在，但主范式不一定存在？ 如果命題公式是矛盾式（永真式），則其無主析取范式如果命題公式是矛盾式（永真式），則其無主析取范式（合取范式）？（合取范式）？ 如果命題公式存在主范式，則是唯一存在的？如果命題公式存在主范式，則是唯一存在的？ 如果已經(jīng)求得某命

49、題公式的主析取范式，則可以根據(jù)主析如果已經(jīng)求得某命題公式的主析取范式，則可以根據(jù)主析取范式求得該命題公式的主合取范式取范式求得該命題公式的主合取范式 只要給定真值表，則可以求出相應(yīng)真值函數(shù)的主范式？只要給定真值表，則可以求出相應(yīng)真值函數(shù)的主范式？1.5 1.5 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 定義定義1.161.16 稱稱F F：0,10,1n n0,10,1為為n n元元真值函數(shù)真值函數(shù)（Truth Value FunctionTruth Value Function）。）。 在這個(gè)定義中，在這個(gè)定義中，F(xiàn) F的自變量為的自變量為n n個(gè)命題變?cè)瑐€(gè)命題變?cè)?，定義域定義域0,10,1n n =

50、000,001,111 =000,001,111，即，即0,10,1n n中元素為由中元素為由0,10,1組成的全體長為組成的全體長為n n的符號(hào)串，的符號(hào)串，值域?yàn)橹涤驗(yàn)?,10,1。n n個(gè)命題變?cè)部蓸?gòu)成個(gè)命題變?cè)部蓸?gòu)成2 22 2n n個(gè)不同的個(gè)不同的真值函數(shù)。含命題變?cè)嬷岛瘮?shù)。含命題變?cè)狿 P的的1 1元真值函數(shù)共有元真值函數(shù)共有4 4個(gè)。個(gè)。含兩個(gè)命題變?cè)瑑蓚€(gè)命題變?cè)狿,QP,Q的真值函數(shù)共有的真值函數(shù)共有1616個(gè)。個(gè)。 1.5 1.5 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 定義定義1.171.17 設(shè)設(shè)S S是一個(gè)聯(lián)結(jié)詞集合，如果任是一個(gè)聯(lián)結(jié)詞集合，如果任何何n(n1)n(n1)

51、元真值函數(shù)都可以由僅含元真值函數(shù)都可以由僅含S S中的聯(lián)中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱結(jié)詞構(gòu)成的公式表示，則稱S S是是聯(lián)結(jié)詞完備聯(lián)結(jié)詞完備集集（Adequate Set of ConnectivesAdequate Set of Connectives）。）。 定理定理1.101.10 S= S= ， ， 是聯(lián)結(jié)詞完備集。是聯(lián)結(jié)詞完備集。 證證 因?yàn)槿魏我驗(yàn)槿魏蝞(n1)n(n1)元真值函數(shù)都與惟一元真值函數(shù)都與惟一的一個(gè)主析取范式等值，而在主析取范式中的一個(gè)主析取范式等值，而在主析取范式中僅含聯(lián)結(jié)詞僅含聯(lián)結(jié)詞 ， ， ，所以，所以S=S= ， ， 是是聯(lián)結(jié)詞完備集。聯(lián)結(jié)詞完備集。 1.5

52、1.5 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 推論推論1.11.1 以下聯(lián)結(jié)詞集都是完備集：以下聯(lián)結(jié)詞集都是完備集：（1 1）S S1= ， ， ， （2 2）S S2= ， ， ， （3 3）S S3= ， （4 4）S S4= ， （5 5）S S5= ， 1.5 1.5 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 證證 （1 1），（），（2 2）的成立是顯然的。）的成立是顯然的。 （3 3）由于）由于S=S= ， ， 是聯(lián)結(jié)詞完備集，是聯(lián)結(jié)詞完備集，因而任何真值函數(shù)都可以由僅含因而任何真值函數(shù)都可以由僅含S S中的聯(lián)結(jié)中的聯(lián)結(jié)詞的公式表示。同時(shí)對(duì)于任意公式詞的公式表示。同時(shí)對(duì)于任意公式A A和和B B，A

53、A B B(A(A B)B) ( ( A AB)B)，因而任意，因而任意真值函數(shù)都可以由僅含真值函數(shù)都可以由僅含S S3 3= ， 中的聯(lián)結(jié)中的聯(lián)結(jié)詞的公式表示，所以詞的公式表示，所以S S3 3是聯(lián)結(jié)詞完備集。是聯(lián)結(jié)詞完備集。 1.5 1.5 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 可以證明恒取可以證明恒取0 0值的真值函數(shù)（即與矛值的真值函數(shù)（即與矛盾式等值的真值函數(shù)）不能用僅含聯(lián)結(jié)詞盾式等值的真值函數(shù)）不能用僅含聯(lián)結(jié)詞集集 ， ， 中的聯(lián)結(jié)詞的公式表示，中的聯(lián)結(jié)詞的公式表示，因而因而 ， ， 不是聯(lián)結(jié)詞完備集。不是聯(lián)結(jié)詞完備集。由此可知，由此可知， ， ， ， ， ， ， ， ， ， 等也都不是聯(lián)

54、結(jié)詞完備集。等也都不是聯(lián)結(jié)詞完備集。所以，所以， ， ， 的任何子集都不是的任何子集都不是聯(lián)結(jié)詞完備集。聯(lián)結(jié)詞完備集。 1.5 1.5 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 定義定義1.181.18 設(shè)設(shè)P P，Q Q為兩個(gè)命題，復(fù)合命題為兩個(gè)命題，復(fù)合命題“P P與與Q Q的否定式的否定式”（“P P或或Q Q的否定式的否定式”）稱為稱為P P，Q Q的的與非式與非式（或非式或非式），記作），記作PQPQ（PQPQ）。符號(hào)）。符號(hào)（）稱作為）稱作為與非聯(lián)結(jié)與非聯(lián)結(jié)詞詞（或非聯(lián)結(jié)詞或非聯(lián)結(jié)詞）。）。PQPQ為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P P與與Q Q不同時(shí)為真（不同時(shí)為真（PQPQ為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)

55、P P與與Q Q同時(shí)同時(shí)為假）。為假）。 由定義不難看出由定義不難看出 PQPQ(P(P Q)Q)，PQPQ(P(P Q)Q) 1.5 1.5 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 定理定理1.111.11 ，都是聯(lián)結(jié)詞完備集。都是聯(lián)結(jié)詞完備集。 證證 已知已知 ， ， 為聯(lián)結(jié)詞完備集，因而只需為聯(lián)結(jié)詞完備集，因而只需證明其中的每個(gè)聯(lián)結(jié)詞都可以由證明其中的每個(gè)聯(lián)結(jié)詞都可以由定義即可。而定義即可。而 P P(P(P P P）PP (a)PP (a) P P Q Q(P(P Q)Q)(PQ)(PQ) (PQ)(PQ) (b)(PQ)(PQ) (b) P P Q Q(P(P Q)Q)( ( P PQ)Q)

56、PP Q Q(PP)(QQ) (c)(PP)(QQ) (c) 由由(a)(a)(c)(c)可知，可知，是聯(lián)結(jié)詞完備集，類是聯(lián)結(jié)詞完備集，類似可證似可證是聯(lián)結(jié)詞完備集。是聯(lián)結(jié)詞完備集。 演繹推理演繹推理 數(shù)理邏輯中，應(yīng)用公認(rèn)的推理規(guī)則數(shù)理邏輯中，應(yīng)用公認(rèn)的推理規(guī)則(Rules (Rules of of I Inference)nference)從一些前提從一些前提( (P Premise)remise)中推中推導(dǎo)出結(jié)論來時(shí)，這種推導(dǎo)過程稱之為演繹導(dǎo)出結(jié)論來時(shí)，這種推導(dǎo)過程稱之為演繹推理推理(Deduction)(Deduction)或形式證明或形式證明(Formal (Formal Proof)

57、Proof)。1.6 1.6 命題邏輯的推理演算命題邏輯的推理演算1 1 推理形式推理形式定義定義1.191.19 設(shè)設(shè)1 1,2 2, ,n n,都是命題公式。都是命題公式。若若( (1 1 2 2 n)n)是重言式，是重言式，稱由前提稱由前提1 1,2 2, ,n n推推出出的推理是的推理是有效的有效的或或正確的正確的，并稱，并稱是是1 1,2 2, ,n n的的有效有效結(jié)論結(jié)論或或邏輯結(jié)果（邏輯結(jié)果（Logical ConsequenceLogical Consequence），當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)(1 1 2 2 n n)是永真式是永真式記為記為1 1 2 2 n n或或1 1,2 2 ,

58、 ,n n（稱為（稱為重言蘊(yùn)含重言蘊(yùn)含或或推理形式推理形式）1.6 1.6 命題邏輯的推理演算命題邏輯的推理演算1.6 1.6 命題邏輯的推理演算命題邏輯的推理演算 關(guān)于定義關(guān)于定義1.191.19還需做以下還需做以下說明說明： （1 1）由前提）由前提1 1, ,2 2, , ,n n推結(jié)論推結(jié)論的推理的推理是否正確與各前提的排列次序無關(guān)，因而是否正確與各前提的排列次序無關(guān)，因而前提中的公式不一定是序列，而是一個(gè)有前提中的公式不一定是序列，而是一個(gè)有限公式集合。若推理是正確的，則記為限公式集合。若推理是正確的，則記為1 1 2 2 n n，否則記為，否則記為1 1 2 2 n n。1.6 1

59、.6 命題邏輯的推理演算命題邏輯的推理演算 （2 2）符號(hào)）符號(hào)與與是兩個(gè)完全不同的符號(hào)，是兩個(gè)完全不同的符號(hào)，它們的區(qū)別與聯(lián)系類似于它們的區(qū)別與聯(lián)系類似于和和的關(guān)系。的關(guān)系。不是命題聯(lián)結(jié)詞而是公式間的關(guān)系符號(hào)，不是命題聯(lián)結(jié)詞而是公式間的關(guān)系符號(hào)，而而是命題聯(lián)結(jié)詞。這兩者之間有密切的是命題聯(lián)結(jié)詞。這兩者之間有密切的聯(lián)系，即聯(lián)系，即的充要條件是公式的充要條件是公式為重言式。為重言式。 1.6 1.6 命題邏輯的推理演算命題邏輯的推理演算 （3 3）必須把推理的有效性和結(jié)論的真實(shí)性必須把推理的有效性和結(jié)論的真實(shí)性區(qū)別開。有效的推理不一定產(chǎn)生真實(shí)的結(jié)區(qū)別開。有效的推理不一定產(chǎn)生真實(shí)的結(jié)論，產(chǎn)生真實(shí)結(jié)

60、論的推理過程未必一定是論，產(chǎn)生真實(shí)結(jié)論的推理過程未必一定是有效的。再說，有效的推理中可能包含假有效的。再說，有效的推理中可能包含假的前提；而無效的推理卻可能包含真的前的前提；而無效的推理卻可能包含真的前提。提。1.6 1.6 命題邏輯的推理演算命題邏輯的推理演算 示例示例：教材教材例例1.181.18 寫出下述推理關(guān)系的推理形式：寫出下述推理關(guān)系的推理形式：“下午小王或去看電影或去游泳。他沒去看電影。所以，下午小王或去看電影或去游泳。他沒去看電影。所以，他去游泳了。他去游泳了。” 解解 設(shè)設(shè) P P：小王下午去看電影；：小王下午去看電影；Q Q：小王下午去游泳。于是：小王下午去游泳。于是得到如