離散數(shù)學(xué)一PPT課件

1、教師簡(jiǎn)介19851985年畢業(yè)于北京大學(xué)數(shù)學(xué)系計(jì)算數(shù)學(xué)專業(yè)年畢業(yè)于北京大學(xué)數(shù)學(xué)系計(jì)算數(shù)學(xué)專業(yè)專業(yè)技術(shù)職務(wù)：教授、碩士導(dǎo)師專業(yè)技術(shù)職務(wù)：教授、碩士導(dǎo)師主講課程：主講課程： 計(jì)算機(jī)類計(jì)算機(jī)類BASICBASIC、FORTRANFORTRAN、人工智能、人工智能原理、原理、C C、C+C+、 PASCALPASCAL、Visual BASICVisual BASIC、程、程序設(shè)計(jì)方法學(xué)、序設(shè)計(jì)方法學(xué)、 SQL server 2000SQL server 2000、數(shù)據(jù)庫(kù)系、數(shù)據(jù)庫(kù)系統(tǒng)概論、軟件工程、統(tǒng)概論、軟件工程、 Visual FoxProVisual FoxPro 數(shù)學(xué)類數(shù)學(xué)類數(shù)值分析、最優(yōu)化

2、計(jì)算方法、數(shù)值分析、最優(yōu)化計(jì)算方法、運(yùn)籌學(xué)、離散數(shù)學(xué)、解題理論、圖論及其應(yīng)用運(yùn)籌學(xué)、離散數(shù)學(xué)、解題理論、圖論及其應(yīng)用E-mail：wyh_Tel : 665677 : 665677第1頁(yè)/共198頁(yè)課程主要內(nèi)容 第一部分第一部分 數(shù)理邏輯數(shù)理邏輯 第二部分第二部分 集合論集合論 第三部分第三部分 代數(shù)系統(tǒng)代數(shù)系統(tǒng) 第四部分第四部分 圖論圖論第2頁(yè)/共198頁(yè)離散數(shù)學(xué)與計(jì)算機(jī)的關(guān)系第一部分第一部分 數(shù)理邏輯數(shù)理邏輯 計(jì)算機(jī)是數(shù)理邏輯和電子學(xué)相結(jié)合的產(chǎn)物計(jì)算機(jī)是數(shù)理邏輯和電子學(xué)相結(jié)合的產(chǎn)物 第二部分第二部分 集合論集合論 集合：一種重要的數(shù)據(jù)結(jié)構(gòu)集合：一種重要的數(shù)據(jù)結(jié)構(gòu) 關(guān)系：關(guān)系數(shù)據(jù)庫(kù)的理論基礎(chǔ)

3、關(guān)系：關(guān)系數(shù)據(jù)庫(kù)的理論基礎(chǔ) 函數(shù)：所有計(jì)算機(jī)語(yǔ)言中不可缺少的一部分函數(shù)：所有計(jì)算機(jī)語(yǔ)言中不可缺少的一部分 第三部分第三部分 代數(shù)系統(tǒng)代數(shù)系統(tǒng) 計(jì)算機(jī)編碼和糾錯(cuò)碼理論數(shù)字邏輯設(shè)計(jì)基礎(chǔ)，計(jì)算計(jì)算機(jī)編碼和糾錯(cuò)碼理論數(shù)字邏輯設(shè)計(jì)基礎(chǔ)，計(jì)算機(jī)使用的各種運(yùn)算機(jī)使用的各種運(yùn)算 第四部分第四部分 圖論圖論 數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、計(jì)算機(jī)網(wǎng)絡(luò)原理數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、計(jì)算機(jī)網(wǎng)絡(luò)原理的基礎(chǔ)的基礎(chǔ) 第3頁(yè)/共198頁(yè)參考教材1、離散數(shù)學(xué) 耿素云、屈婉玲、張立昂 清華大學(xué)出版社2、離散數(shù)學(xué)題解 耿素云、屈婉玲、張立昂 清華大學(xué)出版社3、離散數(shù)學(xué)導(dǎo)論 徐潔磐 高等教育出版社4、離散數(shù)學(xué) 洪帆等編 電子工業(yè)

4、出版社5、 離散數(shù)學(xué) 李盤(pán)林等編 人民郵電出版社第4頁(yè)/共198頁(yè)學(xué)習(xí)要求出勤出勤 思考思考 筆記筆記 作作業(yè)業(yè)第5頁(yè)/共198頁(yè)緒論本課程是高校計(jì)算機(jī)專業(yè)學(xué)生的必修課之一，是計(jì)算本課程是高校計(jì)算機(jī)專業(yè)學(xué)生的必修課之一，是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心、骨干課程，也是數(shù)學(xué)、信息機(jī)科學(xué)與技術(shù)專業(yè)的核心、骨干課程，也是數(shù)學(xué)、信息與計(jì)算科學(xué)、信息管理與信息系統(tǒng)等專業(yè)的專業(yè)基礎(chǔ)課與計(jì)算科學(xué)、信息管理與信息系統(tǒng)等專業(yè)的專業(yè)基礎(chǔ)課程，是計(jì)算機(jī)科學(xué)與技術(shù)的理論基礎(chǔ)程，是計(jì)算機(jī)科學(xué)與技術(shù)的理論基礎(chǔ)該課程主要學(xué)習(xí)數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論該課程主要學(xué)習(xí)數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論等四大方面的內(nèi)容，包括：命

5、題邏輯、謂詞邏輯、集合等四大方面的內(nèi)容，包括：命題邏輯、謂詞邏輯、集合與關(guān)系、函數(shù)、代數(shù)結(jié)構(gòu)、格與布爾代數(shù)、圖論等與關(guān)系、函數(shù)、代數(shù)結(jié)構(gòu)、格與布爾代數(shù)、圖論等離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)中的數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)中的數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、算法分析、邏輯設(shè)計(jì)、系統(tǒng)結(jié)構(gòu)等課程聯(lián)系緊譯原理、算法分析、邏輯設(shè)計(jì)、系統(tǒng)結(jié)構(gòu)等課程聯(lián)系緊密密本課程重點(diǎn)在于培養(yǎng)和提高大學(xué)生的抽象思維、邏輯本課程重點(diǎn)在于培養(yǎng)和提高大學(xué)生的抽象思維、邏輯推理和概括能力，從而為以后專業(yè)課程的學(xué)習(xí)及工作需推理和概括能力，從而為以后專業(yè)課程的學(xué)習(xí)及工作需要打下基礎(chǔ)要打下基礎(chǔ)第6頁(yè)/共198頁(yè)緒論 離散數(shù)學(xué)課程地位：

6、離散數(shù)學(xué)課程地位： 計(jì)算機(jī)專業(yè)（核心課程）計(jì)算機(jī)專業(yè)（核心課程） 信息類專業(yè)（必修課程）信息類專業(yè)（必修課程） 其它類專業(yè)（重要選修課程）其它類專業(yè)（重要選修課程） 離散數(shù)學(xué)的后繼課程：離散數(shù)學(xué)的后繼課程： 數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、 算法分析與設(shè)計(jì)、算法分析與設(shè)計(jì)、 數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)、C+C+語(yǔ)言語(yǔ)言第7頁(yè)/共198頁(yè)緒論離散數(shù)學(xué)課程的學(xué)習(xí)方法離散數(shù)學(xué)課程的學(xué)習(xí)方法: : 強(qiáng)調(diào)強(qiáng)調(diào)：邏輯性、抽象性；：邏輯性、抽象性； 注重注重：概念、方法與應(yīng)用：概念、方法與應(yīng)用離散數(shù)學(xué)的學(xué)習(xí)要領(lǐng)：離散數(shù)學(xué)的學(xué)習(xí)要領(lǐng)： 概念（正確）概念（正確） 必須掌握好離散數(shù)學(xué)中大量的必須掌握好離散數(shù)學(xué)中大量的

7、 概念概念 判斷（準(zhǔn)確）判斷（準(zhǔn)確） 根據(jù)概念對(duì)事物的屬性進(jìn)行判斷根據(jù)概念對(duì)事物的屬性進(jìn)行判斷 推理（可靠）推理（可靠） 根據(jù)多個(gè)判斷推出一個(gè)新的判斷根據(jù)多個(gè)判斷推出一個(gè)新的判斷第8頁(yè)/共198頁(yè)例1：說(shuō)謊者與說(shuō)真話者問(wèn)題：說(shuō)謊者與說(shuō)真話者問(wèn)題：N N夫婦晚上出門(mén)，邀請(qǐng)了夫婦晚上出門(mén)，邀請(qǐng)了W W小姐小姐照看他們的照看他們的4 4個(gè)孩子。在個(gè)孩子。在N N夫婦離家以前，向夫婦離家以前，向W W小姐交待小姐交待了許多注意事項(xiàng)，其中包括了許多注意事項(xiàng)，其中包括4 4個(gè)孩子的情況。個(gè)孩子的情況。N N夫婦說(shuō)他夫婦說(shuō)他們的們的4 4個(gè)孩子中只有一個(gè)孩子總是說(shuō)真話，另外個(gè)孩子中只有一個(gè)孩子總是說(shuō)真話，另

8、外3 3個(gè)則總個(gè)則總是說(shuō)謊。是說(shuō)謊。N N夫婦告訴了夫婦告訴了W W小姐說(shuō)真話的孩子的名字，但由小姐說(shuō)真話的孩子的名字，但由于注意事項(xiàng)太多，于注意事項(xiàng)太多，W W小姐把名字忘記了。當(dāng)她在為孩子小姐把名字忘記了。當(dāng)她在為孩子們準(zhǔn)備晚飯時(shí)，一個(gè)孩子在鄰室打碎了一個(gè)花瓶。們準(zhǔn)備晚飯時(shí)，一個(gè)孩子在鄰室打碎了一個(gè)花瓶。這是孩子們的話：這是孩子們的話：B B說(shuō)：是說(shuō)：是S S干的。干的。S S說(shuō)：是說(shuō)：是J J干的。干的。L L說(shuō)：不是我打碎的。說(shuō)：不是我打碎的。J J說(shuō)：說(shuō)：S S說(shuō)是我干的，他在說(shuō)慌。說(shuō)是我干的，他在說(shuō)慌。由于由于W W小姐知道只有一個(gè)孩子說(shuō)真話，她很快就找出了小姐知道只有一個(gè)孩子說(shuō)真

9、話，她很快就找出了打碎花瓶的孩子。你知道是誰(shuí)嗎？打碎花瓶的孩子。你知道是誰(shuí)嗎？第9頁(yè)/共198頁(yè)例2： 設(shè)整數(shù)集合為設(shè)整數(shù)集合為Z Z 設(shè)自然數(shù)集合為設(shè)自然數(shù)集合為N N 比較比較Z Z與與N N元素的多少元素的多少第10頁(yè)/共198頁(yè)例3： 對(duì)于給定自然數(shù)對(duì)于給定自然數(shù)1n的任意排列，能否通過(guò)反復(fù)交換的任意排列，能否通過(guò)反復(fù)交換1，2，3，n中的元素而得到此排列？中的元素而得到此排列？=(1 5 2 3 6)(7 8)=(1 5)(1 2)(1 3)(1 6)(7 8) 7 8 1 2 4 6 3 58 7 6 5 4 3 2 1第11頁(yè)/共198頁(yè)例4： 任意任意6 6人聚會(huì)中，必有人聚會(huì)

10、中，必有3 3人彼此相識(shí)，或有人彼此相識(shí)，或有3 3人人彼此不相識(shí)彼此不相識(shí) 用兩種顏色填涂完全圖用兩種顏色填涂完全圖K K6 6的各邊，必包含有同的各邊，必包含有同色的色的“三角形三角形”K K3 3第12頁(yè)/共198頁(yè)第一部分 數(shù)理邏輯先看著名物理學(xué)家愛(ài)因斯坦出過(guò)的一道題：先看著名物理學(xué)家愛(ài)因斯坦出過(guò)的一道題： 一個(gè)土耳其商人想找一個(gè)十分聰明的助手協(xié)助他經(jīng)商，有兩人前來(lái)一個(gè)土耳其商人想找一個(gè)十分聰明的助手協(xié)助他經(jīng)商，有兩人前來(lái)應(yīng)聘，這個(gè)商人為了試試哪個(gè)更聰明些，就把兩個(gè)人帶進(jìn)一間漆黑的屋子應(yīng)聘，這個(gè)商人為了試試哪個(gè)更聰明些，就把兩個(gè)人帶進(jìn)一間漆黑的屋子里，他打開(kāi)燈后說(shuō)：里，他打開(kāi)燈后說(shuō)：“

11、這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的，現(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置弄亂，然后我們?nèi)齻€(gè)人每色的，現(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置弄亂，然后我們?nèi)齻€(gè)人每人摸一頂帽子戴在自己頭上，在我開(kāi)燈后，請(qǐng)你們盡快說(shuō)出自己頭上戴的人摸一頂帽子戴在自己頭上，在我開(kāi)燈后，請(qǐng)你們盡快說(shuō)出自己頭上戴的帽子是什么顏色的。帽子是什么顏色的?！闭f(shuō)完后，商人將電燈關(guān)掉，然后三人都摸了一頂帽說(shuō)完后，商人將電燈關(guān)掉，然后三人都摸了一頂帽子戴在頭上，同時(shí)商人將余下的兩頂帽子藏了起來(lái)，接著把燈打開(kāi)。這時(shí)，子戴在頭上，同時(shí)商人將余下的兩頂帽子藏了起來(lái)，接著把燈打開(kāi)。這時(shí)

12、，那兩個(gè)應(yīng)試者看到商人頭上戴的是一頂紅帽子，其中一個(gè)人便喊道：那兩個(gè)應(yīng)試者看到商人頭上戴的是一頂紅帽子，其中一個(gè)人便喊道：“我我戴的是黑帽子。戴的是黑帽子。” 請(qǐng)問(wèn)這個(gè)人說(shuō)得對(duì)嗎？他是怎么推導(dǎo)出來(lái)的呢？請(qǐng)問(wèn)這個(gè)人說(shuō)得對(duì)嗎？他是怎么推導(dǎo)出來(lái)的呢？ 第13頁(yè)/共198頁(yè)主要內(nèi)容1 1 命題邏輯基本概念命題邏輯基本概念2 2 命題邏輯等值演算命題邏輯等值演算 3 3 命題邏輯的推理理論命題邏輯的推理理論4 4 一階邏輯基本概念一階邏輯基本概念 5 5 一階邏輯等值演算與推理一階邏輯等值演算與推理第14頁(yè)/共198頁(yè)1 1 命題邏輯基本概念命題邏輯基本概念 本章的主要內(nèi)容：本章的主要內(nèi)容： 命題、聯(lián)結(jié)

13、詞、復(fù)合命題命題、聯(lián)結(jié)詞、復(fù)合命題 命題公式、賦值、命題公式的分類命題公式、賦值、命題公式的分類 1.1 1.1 命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 1.2 1.2 命題公式及其賦值命題公式及其賦值第15頁(yè)/共198頁(yè)1.1 1.1 命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 命題及其分類命題及其分類 聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命題 復(fù)合命題的真假值復(fù)合命題的真假值第16頁(yè)/共198頁(yè)1.1.1 1.1.1 命題及其分類命題及其分類 命題：命題：具有真假意義（判斷結(jié)果唯一）的陳述句具有真假意義（判斷結(jié)果唯一）的陳述句 命題的真值：命題的真值：判斷結(jié)果判斷結(jié)果 真值的取值：真值的取值：真（真（1 1）、假（）、假（0 0

14、） 真命題與假命題真命題與假命題 注意：注意：感嘆句、祈使句、疑問(wèn)句、悖論都不是命題感嘆句、祈使句、疑問(wèn)句、悖論都不是命題第17頁(yè)/共198頁(yè)例1.11.1 下列句子中那些是命題？ (1) 是無(wú)理數(shù). (2) 2 + 5 8. (3) x + 5 3. (4) 你有鉛筆嗎？ (5) 這只兔子跑得真快呀！ (6) 請(qǐng)不要講話！ (7) 我正在說(shuō)謊話.真命題假命題真值不確定疑問(wèn)句感嘆句祈使句悖論(3)(7)都不是命題21.1.1 1.1.1 命題及其分類命題及其分類第18頁(yè)/共198頁(yè)1.1.1 1.1.1 命題及其分類命題及其分類命題的分類 （1）簡(jiǎn)單命題（原子命題） （2）復(fù)合命題簡(jiǎn)單命題符號(hào)

15、化 （1）用小寫(xiě)英文字母 等來(lái)表示簡(jiǎn)單命題 （2）用1表示真，用0表示假例如： :3是無(wú)理數(shù)，則 是假命題， 的真值為0,kkkrqprqpppp第19頁(yè)/共198頁(yè)1.1.2 聯(lián)結(jié)詞與復(fù)合命題例： 3是無(wú)理數(shù)是不對(duì)的 2是偶素?cái)?shù) 2或4是素?cái)?shù) 如果2是素?cái)?shù)，則3也是素?cái)?shù) 2是素?cái)?shù)當(dāng)且僅當(dāng)3也是素?cái)?shù)。上述命題都是通過(guò)諸如上述命題都是通過(guò)諸如“或或”，“如果如果，則，則”等連詞等連詞聯(lián)結(jié)而成，這樣命題，稱為復(fù)合命題。相對(duì)地，構(gòu)成復(fù)合聯(lián)結(jié)而成，這樣命題，稱為復(fù)合命題。相對(duì)地，構(gòu)成復(fù)合命題的命題稱為簡(jiǎn)單命題。命題的命題稱為簡(jiǎn)單命題。第20頁(yè)/共198頁(yè)1.1.2 聯(lián)結(jié)詞與復(fù)合命題定義1.1 設(shè)p為命

16、題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式否定式,記作p，符號(hào)稱作否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞。并規(guī)定p為真當(dāng)且僅當(dāng)p為假。定義1.2 設(shè)p,q為二命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式合取式，記作pq，稱作合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞。并規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真。定義1.3 設(shè)p，q為二命題，復(fù)合命題“p或q”稱作p與q的析取式析取式，記作pq，稱作析取聯(lián)析取聯(lián)結(jié)詞結(jié)詞。并規(guī)定pq為假當(dāng)且僅當(dāng)p與q同時(shí)為假。 第21頁(yè)/共198頁(yè)1.1.2 聯(lián)結(jié)詞與復(fù)合命題 相容相容“或或”與排斥與排斥“或或”例 將下列命題符號(hào)化。將下列命題符號(hào)化。 (1)(1)張曉靜愛(ài)唱歌或愛(ài)聽(tīng)

17、音樂(lè)。張曉靜愛(ài)唱歌或愛(ài)聽(tīng)音樂(lè)。 (2)(2)張曉靜是江西人或安徽人。張曉靜是江西人或安徽人。 (3)(3)張曉靜只能挑選張曉靜只能挑選202202或或203203房間。房間。 解 在解題時(shí)，先將原子命題符號(hào)化。在解題時(shí)，先將原子命題符號(hào)化。 (1) p(1) p：張曉靜愛(ài)唱歌。：張曉靜愛(ài)唱歌。 q q：張曉靜愛(ài)聽(tīng)音樂(lè)。：張曉靜愛(ài)聽(tīng)音樂(lè)。 (2) r(2) r：張曉靜是江西人。：張曉靜是江西人。 s s：張曉靜是安徽人。：張曉靜是安徽人。 (3) t(3) t：張曉靜挑選：張曉靜挑選202202房間。房間。u u：張曉靜挑選：張曉靜挑選203203房間。房間。 qp sr)()(utut第22頁(yè)

18、/共198頁(yè)1.1.2 聯(lián)結(jié)詞與復(fù)合命題 思考題：只能在周二說(shuō)的話 某人在周一總是說(shuō)謊話，而在其它日子總是說(shuō)真話。那么，有沒(méi)有他只能在周二才能說(shuō)的話呢？某人在周一總是說(shuō)謊話，而在其它日子總是說(shuō)真話。那么，有沒(méi)有他只能在周二才能說(shuō)的話呢？ “今天不是周一就是周二。今天不是周一就是周二?！?第23頁(yè)/共198頁(yè)1.1.2 聯(lián)結(jié)詞與復(fù)合命題定義1.4 設(shè)p，q為二命題，復(fù)合命題“如果p，則q”稱作p與q的蘊(yùn)涵式，記作pq，稱作蘊(yùn)涵聯(lián)結(jié)詞。并規(guī)定pq為假當(dāng)且僅當(dāng)p為真q為假。 pq的邏輯關(guān)系表示q是p的必要條件。 注意在使用聯(lián)結(jié)詞時(shí)，特別注意以下幾點(diǎn)： 第24頁(yè)/共198頁(yè)1.1.2 聯(lián)結(jié)詞與復(fù)合命題

19、在自然語(yǔ)言里，特別是在數(shù)學(xué)中，在自然語(yǔ)言里，特別是在數(shù)學(xué)中，q q是是p p的必要條件有的必要條件有許多不同的敘述方式。例如，許多不同的敘述方式。例如，“只要只要p p，就，就q q”，“因因?yàn)闉閜 p，所以，所以q q”，“p p僅當(dāng)僅當(dāng)q q”，“只有只有q q才才p p”，“除非除非q q才才p p”，“除非除非q q，否則非，否則非p p”等等。以上各種敘述方等等。以上各種敘述方式表面看來(lái)有所不同，但都表達(dá)的是式表面看來(lái)有所不同，但都表達(dá)的是q q是是p p的必要條件，的必要條件，因而所用聯(lián)結(jié)詞均應(yīng)符號(hào)化為因而所用聯(lián)結(jié)詞均應(yīng)符號(hào)化為，上述各種敘述方式，上述各種敘述方式都應(yīng)符號(hào)化為都應(yīng)符

20、號(hào)化為pqpq。 在自然語(yǔ)言中，在自然語(yǔ)言中，“如果如果p p，則，則q q”中的前件中的前件p p與后件與后件q q往往往具有某種內(nèi)在聯(lián)系。而在數(shù)理邏輯中，往具有某種內(nèi)在聯(lián)系。而在數(shù)理邏輯中，p p與與q q可以無(wú)可以無(wú)任何內(nèi)在聯(lián)系。任何內(nèi)在聯(lián)系。 在數(shù)學(xué)或其它自然科學(xué)中，在數(shù)學(xué)或其它自然科學(xué)中，“如果如果p p，則，則q q”往往表達(dá)往往表達(dá)的是前件的是前件p p為真，后件為真，后件q q也為真的推理關(guān)系。但在數(shù)理也為真的推理關(guān)系。但在數(shù)理邏輯中，作為一種規(guī)定，當(dāng)邏輯中，作為一種規(guī)定，當(dāng)p p為假時(shí)，無(wú)論為假時(shí)，無(wú)論q q是真是假，是真是假，pqpq均為真。也就是說(shuō)，只有均為真。也就是說(shuō)，

21、只有p p為真為真q q為假這一種情況為假這一種情況使得復(fù)合命題使得復(fù)合命題pqpq為假。為假。 第25頁(yè)/共198頁(yè)1.1.2 聯(lián)結(jié)詞與復(fù)合命題定義1.5 設(shè)p，q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作 ，稱作等價(jià)聯(lián)結(jié)詞。并規(guī)定 為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假。 的邏輯關(guān)系為p與q互為充分必要條件。 以上定義了五種最基本、最常用、也是最重要的聯(lián)結(jié)詞， ，將它們組成一個(gè)集合， ，稱為一個(gè)聯(lián)結(jié)詞集。其中為一元聯(lián)結(jié)詞，其余的都是二元聯(lián)結(jié)詞。 qp qp qp 第26頁(yè)/共198頁(yè)1.1.2 聯(lián)結(jié)詞與復(fù)合命題 例 將下列命題符號(hào)化，并指出各復(fù)合命題的真值： (1) 如果3+

22、36，則雪是白的。 (2) 如果3+36，則雪是白的。 (3) 如果3+36，則雪不是白的。 (4) 如果3+36，則雪不是白的。 以下命題中出現(xiàn)的a是一個(gè)給定的正整數(shù)： (5) 只要a能被4整除，則a一定能被2整除。 (6) a能被4整除，僅當(dāng)a能被2整除。 (7) 除非a能被2整除，a才能被4整除。 (8) 除非a能被2整除，否則a不能被4整除。 (9) 只有a能被2整除，a才能被4整除。 (10)只有a能被4整除，a才能被2整除。 第27頁(yè)/共198頁(yè)1.1.3 復(fù)合命題真假值聯(lián)結(jié)詞可以嵌套使用，在嵌套使用時(shí)，規(guī)定如下優(yōu)先順序： ( )， ，對(duì)于同一優(yōu)先級(jí)的聯(lián)結(jié)詞，先出現(xiàn)者先運(yùn)算。 第2

23、8頁(yè)/共198頁(yè)1.2 命題公式及其賦值 命題公式的定義命題公式的定義 公式的層次公式的層次 公式的賦值公式的賦值 真值表真值表 公式的真假值分類公式的真假值分類 第29頁(yè)/共198頁(yè)1.2.1 命題公式的定義命題公式的定義 由于簡(jiǎn)單命題是真值唯一確定的命題邏輯中最基本的研究單位，由于簡(jiǎn)單命題是真值唯一確定的命題邏輯中最基本的研究單位，所以也稱簡(jiǎn)單命題為所以也稱簡(jiǎn)單命題為命題常項(xiàng)命題常項(xiàng)或或命題常元命題常元。從本節(jié)開(kāi)始對(duì)命題進(jìn)一步。從本節(jié)開(kāi)始對(duì)命題進(jìn)一步抽象，首先稱真值可以變化的陳述句為抽象，首先稱真值可以變化的陳述句為命題變項(xiàng)命題變項(xiàng)或或命題變?cè)}變?cè)?，也用，也用p,q,r,p,q,r,表

24、示命題變項(xiàng)。當(dāng)表示命題變項(xiàng)。當(dāng)p,q,r,p,q,r,表示命題變項(xiàng)時(shí)，它們就表示命題變項(xiàng)時(shí)，它們就成了取值成了取值0 0或或1 1的變項(xiàng)，因而命題變項(xiàng)已不是命題。這樣一來(lái)，的變項(xiàng)，因而命題變項(xiàng)已不是命題。這樣一來(lái)，p,q,r,p,q,r,既可以表示命題常項(xiàng)，也可以表示命題變項(xiàng)。在使用既可以表示命題常項(xiàng)，也可以表示命題變項(xiàng)。在使用中，需要由上下文確定它們表示的是常項(xiàng)還是變項(xiàng)。中，需要由上下文確定它們表示的是常項(xiàng)還是變項(xiàng)。 第30頁(yè)/共198頁(yè)1.2.1 命題公式的定義命題公式的定義定義1.6 (1)單個(gè)命題變項(xiàng)是合式公式，并稱為原子命題公式。 (2)若A是合式公式，則(A)也是合式公式。 (3)

25、若A，B是合式公式，則(AB)，(AB)，(AB)，(A B)也是合式公式。 (4)只有有限次地應(yīng)用(1)(3)形式的符號(hào)串才是合式公式。 合式公式也稱為命題公式或命題形式，并簡(jiǎn)稱為公式。 如：(pq)(qr)，(pq)r，p(qr)等都是合式公式，而pqr，（p(rq)等不是合式公式。 注意：定義1.6給出的合式公式的定義方式稱為歸納定義方式，后面還將多次出現(xiàn)這種定義方式。 第31頁(yè)/共198頁(yè)1.2.2 公式的層次公式的層次定義定義 1.71.7 (1)若公式 A 是單個(gè)的命題變項(xiàng)，則稱 A 為 0 0層合式層合式。 (2)稱 A 是 n+1(n0)層公式是指下面情況之一： (a) AB，

26、B 是 n 層公式； (b) ABC，其中 B，C 分別為 i 層和 j層公式，且 nmax(i，j)； (c) ABC， 其中 B， C 的層次及 n 同(b)； (d) ABC， 其中 B， C 的層次及 n 同(b)； (e) ABC， 其中 B， C 的層次及 n 同(b)； (3)若公式 A 的層次為 k，則稱 A 是 k 層公式層公式。 易知，(pq)r，(pq)(rs)p)分別為 3 層和 4 層公式。 第32頁(yè)/共198頁(yè)1.2.3 公式的賦值公式的賦值公式就代表命題，但代表的命題是真還是假呢？ 在命題公式中，由于有命題符號(hào)的出現(xiàn)，因而真值是不確定的。當(dāng)將公式中出現(xiàn)的全部命題符

27、號(hào)都解釋成具體的命題之后，公式就成了真值確定的命題了。例如，在公式(pq)r 中，若將 p 解釋成：2 是素?cái)?shù)，q 解釋成：3 是偶數(shù)，r 解釋成：是無(wú)理數(shù)，則 p 與 r 被解釋成真命題，q 被解釋成假命題了，此時(shí)公式(pq)r 被解釋成：若 2 是素?cái)?shù)或 3 是偶數(shù)，則是無(wú)理數(shù)。這是一個(gè)真命題。若 p，q 的解釋不變，r 被解釋為：是有理數(shù)，則(pq)r 被解釋成：若 2 是素?cái)?shù)或 3 是偶數(shù)，則是有理數(shù)。這是個(gè)假命題。其實(shí)， 將命題符號(hào) p 解釋成真命題， 相當(dāng)于指定 p 的真值為 1， 解釋成假命題，相當(dāng)于指定 p 的真值為 0。下面的問(wèn)題是，指定 p，q，r 的真值為何值時(shí)，(pq)

28、r 的真值為 1；指定 p，q，r 的真值為何值時(shí)，(pq)r 的真值為 0。 第33頁(yè)/共198頁(yè)1.2.3 公式的賦值公式的賦值 定義定義1.8 1.8 設(shè)設(shè)p p1 1,p,p2 2, ,p,pn n是出現(xiàn)在公式是出現(xiàn)在公式A A中的全部命題符號(hào)，給中的全部命題符號(hào)，給p p1 1,p,p2 2, ,p,pn n各指定一個(gè)真值，稱為對(duì)各指定一個(gè)真值，稱為對(duì)A A的一的一個(gè)賦值或解釋。若指定的一組值使個(gè)賦值或解釋。若指定的一組值使A A的真值為的真值為1 1，則稱這組值為，則稱這組值為A A的成真賦值；若使的成真賦值；若使A A的真值為的真值為0 0，則稱這組，則稱這組值為值為A A的成假

29、賦值。的成假賦值。 不難看出，含n(n=1)個(gè)命題變項(xiàng)的公式共有2n個(gè)不同的賦值。 第34頁(yè)/共198頁(yè)1.2.4 真值表定義1.9 將命題公式A在所有賦值下取值情況列成表，稱作A的真值表。構(gòu)造真值表的具體步驟如下： (1) 找出公式中所含的全體命題變項(xiàng)p1,p2,pn (若無(wú)下角標(biāo)就按字典順序排列)，列出2n個(gè)賦值。本課件規(guī)定，賦值從000開(kāi)始，然后按二進(jìn)制加法依次寫(xiě)出各賦值，直到111為止。 (2) 按從低到高的順序?qū)懗龉降母鱾€(gè)層次。 (3) 對(duì)應(yīng)各個(gè)賦值計(jì)算出各層次的真值，直到最后計(jì)算出公式的真值。 第35頁(yè)/共198頁(yè)1.2.4 真值表 例1.8 求下列公式的真值表，并求成真賦值和成

30、假賦值。rqq)(p (3)q)(qq)(p (2)rq)p( ) 1 (第36頁(yè)/共198頁(yè)1.2.4 真值表第37頁(yè)/共198頁(yè)1.2.4 真值表第38頁(yè)/共198頁(yè)1.2.4 真值表第39頁(yè)/共198頁(yè)1.2.5 公式的真假值分類定義定義1.10 1.10 設(shè)設(shè)A A為任一命題公式。為任一命題公式。 (1) (1) 若若A A在它的各種賦值下取值均為真在它的各種賦值下取值均為真, ,則稱則稱A A是是重重言式言式或或永真式永真式。 (2) (2) 若若A A在它的各種賦值下取值均為假在它的各種賦值下取值均為假, ,則稱則稱A A是是矛矛盾式盾式或或永假式永假式。 (3) (3) 若若A

31、A不是矛盾式不是矛盾式, ,則稱則稱A A是是可滿足式可滿足式。注：關(guān)于n個(gè)命題變?cè)狿1,P2,Pn,可以構(gòu)造多少個(gè)真值表呢? n個(gè)命題變?cè)伯a(chǎn)生2n個(gè)不同賦值,在每個(gè)賦值下,公式的值只有0和1兩個(gè)值。于是n個(gè)命題變?cè)恼嬷当砉灿?種不同情況。 n22第40頁(yè)/共198頁(yè)1.2.5 公式的真假值分類 例例1.10 1.10 下列公式中下列公式中, ,哪些具有相同的真值表哪些具有相同的真值表? ? (1) pq (1) pq (2) qr(2) qr (3) (pq)(pr)p)(3) (pq)(pr)p) (4) (qr)(pp) (4) (qr)(pp) 第41頁(yè)/共198頁(yè)1.2.5 公式

32、的真假值分類第42頁(yè)/共198頁(yè)第1章小結(jié) 主要內(nèi)容 1.命題與真值（或真假值）。 2.簡(jiǎn)單命題與復(fù)合命題。 3.聯(lián)結(jié)詞：否定聯(lián)結(jié)詞，合取聯(lián)結(jié)詞，析取聯(lián)結(jié)詞，蘊(yùn)涵聯(lián)結(jié)詞，等價(jià)聯(lián)結(jié)詞。 4.命題公式（簡(jiǎn)稱公式）。 5.命題公式的層次和公式的賦值。6.真值表。7.公式的類型（重言式（或永真式），矛盾式（或永假式），可滿足式）。 第43頁(yè)/共198頁(yè)第1章小結(jié) 學(xué)習(xí)要求 1.在5種聯(lián)結(jié)詞中，要特別注意蘊(yùn)涵聯(lián)結(jié)的應(yīng)用，要弄清三個(gè)問(wèn)題： pq的邏輯關(guān)系 pq的真值 pq的靈活的敘述方法 2.寫(xiě)真值表要特別仔細(xì)認(rèn)真，否則會(huì)出錯(cuò)誤。 3.深刻理解各聯(lián)結(jié)詞的邏輯含義。 4.熟練地將復(fù)合命題符號(hào)化。 5.會(huì)用真

33、值表求公式的成真賦值和成假賦值。 第44頁(yè)/共198頁(yè)2 命題邏輯的等值演算 等值式等值式 對(duì)偶與范式對(duì)偶與范式 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集第45頁(yè)/共198頁(yè)2.1 等值式 等值式的概念等值式的概念 用真值表判斷公式的等值用真值表判斷公式的等值 等值演算等值演算 第46頁(yè)/共198頁(yè)2.1.1等值式的概念等值式的概念兩公式什么時(shí)候代表了同一個(gè)命題呢？抽象地看，它們的真假取值完全相同時(shí)即代表了相同的命題。 設(shè)公式A,B共同含有n個(gè)命題變項(xiàng)，可能A或B有啞元，若A與B有相同的真值表，則說(shuō)明在2n個(gè)賦值的每個(gè)賦值下，公式A與公式B的真值都相同。于是等價(jià)式A B應(yīng)為重言式。 定義2.1 設(shè)A,B是

34、兩個(gè)命題公式，若A,B構(gòu)成的等價(jià)式A B為重言式，則稱公式A與公式B是等值的，記作A B. 第47頁(yè)/共198頁(yè)2.1.1等值式的概念等值式的概念 判斷等值式有如下方法：判斷等值式有如下方法： 真值表真值表 等值演算等值演算 范式范式 第48頁(yè)/共198頁(yè)2.1.2用真值表判斷公式的等值 例2.1 判斷下面兩個(gè)公式是否等值： (pq)與pq 第49頁(yè)/共198頁(yè)2.1.2用真值表判斷公式的等值例2.2 判斷下列各組公式是否等值： （1）p(qr)與(pq)r （2）(pq)r與(pq)r 第50頁(yè)/共198頁(yè)2.1.3 等值演算 1基本的等值式 雙重否定律 AA 冪等律 AAA, AAA 交換

35、律 ABBA, ABBA 結(jié)合律 (AB)CA(BC), (AB)CA(BC) 分配律 A(BC) (AB)(AC), A(BC) (AB)(AC) 德摩根律 (AB)AB (AB)AB 吸收律 A(AB)A, A(AB)A 第51頁(yè)/共198頁(yè)2.1.3 等值演算零律 A11, A00 同一律 A0A. A1A 排中律 AA1 矛盾律 AA0 蘊(yùn)涵等值式 ABAB 等價(jià)等值式 AB(AB)(BA) 假言易位 ABBA 等價(jià)否定等值式 ABAB 歸謬論 (AB)(AB) A 注意：要牢記各個(gè)等值式，這是繼續(xù)學(xué)習(xí)的基礎(chǔ) 第52頁(yè)/共198頁(yè)2.1.3 等值演算以上以上1616組等值式包含了組等值

36、式包含了2424個(gè)重要等值式。由于個(gè)重要等值式。由于A,B,CA,B,C可以代表任意的公式，因而以上各等值式都是用元語(yǔ)可以代表任意的公式，因而以上各等值式都是用元語(yǔ)言符號(hào)書(shū)寫(xiě)的，稱這樣的等值式為言符號(hào)書(shū)寫(xiě)的，稱這樣的等值式為等值式模式等值式模式，每個(gè)，每個(gè)等值式模式都給出了無(wú)窮多個(gè)同類型的具體的等值式。等值式模式都給出了無(wú)窮多個(gè)同類型的具體的等值式。例如，在蘊(yùn)涵等值式（例如，在蘊(yùn)涵等值式（2.122.12）中，取）中，取A=pA=p，B=qB=q時(shí)，時(shí)，得等值式得等值式 pq pq pq pq 當(dāng)取當(dāng)取A=pqrA=pqr，B=pqB=pq時(shí)，得等值式時(shí)，得等值式 (pqr)(pq) (pqr

37、)(pq)(pqr)(pq) (pqr)(pq)這些具體的等值式都被稱為原來(lái)的等值式模式的這些具體的等值式都被稱為原來(lái)的等值式模式的代入代入實(shí)例實(shí)例。 每個(gè)具體的代入實(shí)例的正確性都可以用真值每個(gè)具體的代入實(shí)例的正確性都可以用真值表證明之，而每個(gè)等值式模式可用歸納法證明之。表證明之，而每個(gè)等值式模式可用歸納法證明之。 第53頁(yè)/共198頁(yè)2.1.3 等值演算二、 等值演算與置換規(guī)則 1 等值演算由已知的等值式推演出新的等值式的過(guò)程 2等值演算的基礎(chǔ)： （1）等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞性 （2）基本的等值式 （3）置換規(guī)則（見(jiàn) 3） 3置換規(guī)則 設(shè)(A)是含公式 A 的命題公式，(B)是用公

38、式 B 置換了(A)中的所有的 A 后得到的命題公式，若 BA，則(B)(A) 第54頁(yè)/共198頁(yè)2.1.3 等值演算三、 等值演算的應(yīng)用舉例（以后章節(jié)待續(xù)） 1證明兩個(gè)公式等值 例 證明 p(qr) (pq)r 證 p(qr) p(qr) （蘊(yùn)涵等值式，置換規(guī)則） (pq)r （結(jié)合律，置換規(guī)則） (pq)r （德摩根律，置換規(guī)則） (pq)r （蘊(yùn)涵等值式，置換規(guī)則） 幾點(diǎn)說(shuō)明： 也可以從右邊開(kāi)始演算（請(qǐng)做一遍） 因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫(xiě)出 熟練后，基本等值式也可以不寫(xiě)出 用等值演算不能直接證明兩個(gè)公式不等值 第55頁(yè)/共198頁(yè)2.1.3 等值演算例 證明 p(qr) (pq)

39、r 證 方法一 真值表法（自己證） 方法二 觀察賦值法. 易知 000, 010 等是左邊的成真賦值，是右邊的成假賦值 方法三 用等值演算先化簡(jiǎn)兩個(gè)公式，再觀察. 第56頁(yè)/共198頁(yè)2.1.3 等值演算2. 判斷公式類型 例 用等值演算法判斷下列公式的類型 （1）q(pq) （2）(pq)(qp) （3）(pq)(pq)r) 解（1）q(pq) q(pq) （蘊(yùn)涵等值式） q(pq) （德摩根律） p(qq) （交換律，結(jié)合律） p0 （矛盾律） 0 （零律） 由最后一步可知， （1）為矛盾式. 第57頁(yè)/共198頁(yè)2.1.3 等值演算（2）(pq)(qp) (pq)(qp) （蘊(yùn)涵等值式）

40、 (pq)(pq) （交換律） 1 由最后一步可知， （2）為重言式. 問(wèn)：最后一步為什么等值于 1？ 說(shuō)明： （2）的演算步驟可長(zhǎng)可短，以上演算最省. 第58頁(yè)/共198頁(yè)2.1.3 等值演算（3）(pq)(pq)r) (p(qq)r （分配律） p1r （排中律） pr （同一律） 由最后一步可知， （3）不是矛盾式，也不是重言式，它是可滿足式， 其實(shí) 101, 111 是成真賦值， 000, 010 等是成假賦值. 總結(jié)：從此例可看出 A 為矛盾式當(dāng)且僅當(dāng) A 0 A 為重言式當(dāng)且僅當(dāng) A 1 3解判定問(wèn)題 見(jiàn)書(shū)上例 2.6 第59頁(yè)/共198頁(yè)2.1.3 等值演算例2.6 在某次研討會(huì)

41、的中間休息時(shí)間，3名與會(huì)者根據(jù)王教授的口音對(duì)他是哪個(gè)省市的人進(jìn)行了判斷： 甲說(shuō)王教授不是蘇州人，是上海人。 乙說(shuō)王教授不是上海人，是蘇州人。 丙說(shuō)王教授既不是上海人，也不是杭州人。 聽(tīng)完以上3人的判斷后，王教授笑著說(shuō)，他們3人中有一人說(shuō)的全對(duì)，有一人說(shuō)對(duì)了一半，另一人說(shuō)的全不對(duì)。試用邏輯演算法分析王教授到底是哪里人？ 第60頁(yè)/共198頁(yè)2.1.3 等值演算解 設(shè)命題 p：王教授是蘇州人。 q：王教授是上海人。 r：王教授是杭州人。 p,q,r中必有一個(gè)真命題，兩個(gè)假命題，要通過(guò)邏輯演算將真命題找出來(lái)。設(shè) 甲的判斷為A1=pq 乙的判斷為A2=pq 丙的判斷為A3=qr 第61頁(yè)/共198頁(yè)2

42、.1.3 等值演算則 甲的判斷全對(duì) B1=A1=pq 甲的判斷對(duì)一半 B2=(pq)(pq) 甲的判斷全錯(cuò) B3=pq 乙的判斷全對(duì) C1=A2=pq 乙的判斷對(duì)一半 C2=(pq)(pq) 乙的判斷全錯(cuò) C3=pq 丙的判斷全對(duì) D1=A3=qr 丙的判斷對(duì)一半 D2=(qr)(qr) 丙甲的判斷全錯(cuò) D3=qr 第62頁(yè)/共198頁(yè)2.1.3 等值演算由王教授所說(shuō)E=(B1C2D3) (B1C3D2) (B2C1D3) (B2C3D1) (B2C1D2) (B3C2D1) 為真命題。 E=(pqr)(pqr) 但因?yàn)橥踅淌诓荒芗仁巧虾Ｈ?，但因?yàn)橥踅淌诓荒芗仁巧虾Ｈ?，又是杭州人，因而又是杭?/p>

43、人，因而p,r必有一個(gè)必有一個(gè)假命題，即假命題，即pqr=0，于是，于是 E=pqr 為真命題，因而必有為真命題，因而必有p,r為假命為假命題，題，q為真命題，即王教授是上為真命題，即王教授是上海人。甲說(shuō)的全對(duì)，丙說(shuō)對(duì)了一海人。甲說(shuō)的全對(duì)，丙說(shuō)對(duì)了一半，而乙全說(shuō)錯(cuò)了。半，而乙全說(shuō)錯(cuò)了。 第63頁(yè)/共198頁(yè)2.2 對(duì)偶與范式 對(duì)偶式與對(duì)偶原理對(duì)偶式與對(duì)偶原理 析取范式與合取范式析取范式與合取范式 主析取范式與主合取范式主析取范式與主合取范式第64頁(yè)/共198頁(yè)2.2.1 對(duì)偶式與對(duì)偶原理對(duì)偶式與對(duì)偶原理定義 在僅含有聯(lián)結(jié)詞 , ,的命題公式A中，將換成, 換成，若A中含有0或1，就將0換成1，

44、1換成0，所得命題公式稱為A的對(duì)偶式，記為A*.從定義不難看出，(A*)* 還原成A，即(A*)* A。定理 設(shè)A和A*互為對(duì)偶式，p1,p2,pn是出現(xiàn)在A和A*中的全部命題變項(xiàng)，將A和A*寫(xiě)成n元函數(shù)形式，則 (1) A(p1,p2,pn) A* ( p1, p2, pn) (2) A( p1, p2, pn) A* (p1,p2,pn) 定理（對(duì)偶原理）設(shè)A，B為兩個(gè)命題公式，若A B，則A* B*. .第65頁(yè)/共198頁(yè)2.2.2 2.2.2 析取范式與合取范式對(duì)應(yīng)于同一個(gè)真值表，可以有很多公式，其形式可以不同，但彼此等值。是否有標(biāo)準(zhǔn)形式？pqG000011101110由“1”看：與

45、有一種情形成立，G即取1 G p q p q G ( p q) ( p q)由“0”看：與有一種情形成立，G即取0G (p q) ( p q)第66頁(yè)/共198頁(yè)2.2.2 2.2.2 析取范式與合取范式 文字: :命題變項(xiàng)及其否定的總稱簡(jiǎn)單析取式: :有限個(gè)文字構(gòu)成的析取式如 p, q, pq, p q r, 簡(jiǎn)單合取式: :有限個(gè)文字構(gòu)成的合取式如 p, q, pq, p q r, 析取范式: :由有限個(gè)簡(jiǎn)單合取式組成的析取式 A1 A2Ar, 其中A1,A2,Ar是簡(jiǎn)單合取式合取范式: :由有限個(gè)簡(jiǎn)單析取式組成的合取式 A1 A2Ar , 其中A1,A2,Ar是簡(jiǎn)單析取式第67頁(yè)/共19

46、8頁(yè)2.2.2 2.2.2 析取范式與合取范式范式: :析取范式與合取范式的總稱 公式A的析取范式: 與A等值的析取范式公式A的合取范式: 與A等值的合取范式說(shuō)明： 單個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式形如 pq r, p qr 的公式既是析取范式，又是合取范式 (為什么?) 第68頁(yè)/共198頁(yè)命題公式的范式 定理 任何命題公式都存在著與之等值的析取范式與合取范式. .求公式A的范式的步驟： (1) 消去A中的, （若存在） (2) 否定聯(lián)結(jié)詞 的內(nèi)移或消去 (3) 使用分配律 對(duì) 分配（析取范式） 對(duì) 分配（合取范式）公式的范式存在，但不惟一，這是它的局限性 第69頁(yè)/共198頁(yè)求公式的

47、范式舉例 例 求下列公式的析取范式與合取范式(1) A=(pq)r解 (pq)r ( pq)r （消去） pqr （結(jié)合律）這既是A的析取范式（由3個(gè)簡(jiǎn)單合取式組成的析取式），又是A的合取范式（由一個(gè)簡(jiǎn)單析取式組成的合取式）第70頁(yè)/共198頁(yè)求公式的范式舉例( (續(xù)) )(2) B=(pq)r解 (pq)r ( pq)r （消去第一個(gè)） ( pq) r （消去第二個(gè)） (p q) r （否定號(hào)內(nèi)移德摩根律）這一步已為析取范式（兩個(gè)簡(jiǎn)單合取式構(gòu)成）繼續(xù)： (p q) r (p r) (q r) （ 對(duì) 分配律）這一步得到合取范式（由兩個(gè)簡(jiǎn)單析取式構(gòu)成） 第71頁(yè)/共198頁(yè)極小項(xiàng)與極大項(xiàng) 定義

48、 在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式( (簡(jiǎn)單析取式) )中，若每個(gè)命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1 i n）個(gè)文字出現(xiàn)在左起第i位上，稱這樣的簡(jiǎn)單合取式（簡(jiǎn)單析取式）為極小項(xiàng)（極大項(xiàng)）.說(shuō)明：n個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng) 2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值 用mi表示第i個(gè)極小項(xiàng)，其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示. 用Mi表示第i個(gè)極大項(xiàng)，其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示, mi( (Mi) )稱為極小項(xiàng)( (極大項(xiàng)) )的名稱. mi與Mi的關(guān)系: : mi Mi , Mi mi 第72頁(yè)/共198頁(yè)極小項(xiàng)與極大項(xiàng)( (續(xù)) )由p, q兩個(gè)命題變

49、項(xiàng)形成的極小項(xiàng)與極大項(xiàng) 公式公式 成真賦值成真賦值名稱名稱 公式公式 成假賦值成假賦值名稱名稱 p q p q p q p q0 0 0 1 1 0 1 1 m0m1m2m3 p q p q p q p q 0 0 0 1 1 0 1 1 M0M1M2M3 極小項(xiàng)極小項(xiàng) 極大項(xiàng)極大項(xiàng) 第73頁(yè)/共198頁(yè) 由p, q, r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng) 極小項(xiàng)極小項(xiàng) 極大項(xiàng)極大項(xiàng) 公式公式 成真成真賦值賦值名稱名稱 公式公式 成假成假賦值賦值名稱名稱 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0

50、 11 1 01 1 1m0m1m2m3m4m5m6m7p q r p q r p q r p q r p q r p q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M7 第74頁(yè)/共198頁(yè)主析取范式與主合取范式 主析取范式: : 由極小項(xiàng)構(gòu)成的析取范式主合取范式: : 由極大項(xiàng)構(gòu)成的合取范式例如，n=3, 命題變項(xiàng)為p, q, r時(shí)， ( pq r) ( p q r) m1 m3 是主析取范式 (p qr) ( p qr) M1 M5 是主合取范式 A的主析取范式: 與A等值的主析取范式 A的主合

51、取范式: : 與A等值的主合取范式. 第75頁(yè)/共198頁(yè)主析取范式與主合取范式( (續(xù)) )定理 任何命題公式都存在著與之等值的主析取范式和主合取范式, 并且是惟一的. . 用等值演算法求公式的主范式的步驟： (1) 先求析取范式（合取范式） (2) 將不是極小項(xiàng)（極大項(xiàng)）的簡(jiǎn)單合取式（簡(jiǎn) 單析取式）化成與之等值的若干個(gè)極小項(xiàng)的析 ?。O大項(xiàng)的合?。枰猛宦桑?律）、排中律（矛盾律）、分配律、冪等律等. (3) 極小項(xiàng)（極大項(xiàng)）用名稱mi（Mi）表示，并按角標(biāo)從小到大順序排序. 第76頁(yè)/共198頁(yè)求公式的主范式例 求公式 A=(pq)r的主析取范式與主合 取范式. . (1) 求

52、主析取范式 (pq)r (p q) r , （析取范式） (p q) (p q) ( r r) (p qr) (p q r) m6 m7 , 第77頁(yè)/共198頁(yè)求公式的主范式( (續(xù)) ) r ( p p) ( q q) r ( pq r) ( p q r) (pq r) (p q r) m1 m3 m5 m7 , 代入并排序，得 (pq)r m1 m3 m5 m6 m7（主析取范式） 第78頁(yè)/共198頁(yè)求公式的主范式( (續(xù)) ) (2) 求A的主合取范式 (pq)r (p r) (q r) , （合取范式） p r p (qq) r (p q r) (pq r) M0 M2, 第79頁(yè)

53、/共198頁(yè)求公式的主范式( (續(xù)) ) q r (pp) q r (p q r) ( p q r) M0 M4 , 代入并排序，得 (pq)r M0 M2 M4 （主合取范式） 第80頁(yè)/共198頁(yè)主范式的用途與真值表相同 (1) 求公式的成真賦值和成假賦值 例如 (pq)r m1 m3 m5 m6 m7， 其成真賦值為001, 011, 101, 110, 111， 其余的賦值 000, 010, 100為成假賦值. 類似地，由主合取范式也可立即求出成 假賦值和成真賦值. 第81頁(yè)/共198頁(yè)主范式的用途( (續(xù)) ) (2) 判斷公式的類型 設(shè)A含n個(gè)命題變項(xiàng)，則 A為重言式A的主析取范

54、式含2n個(gè)極小項(xiàng) A的主合取范式為1.A為矛盾式 A的主析取范式為0 A的主合析取范式含2n個(gè)極大項(xiàng)A為非重言式的可滿足式A的主析取范式中至少含一個(gè)且不含全部極小項(xiàng)A的主合取范式中至少含一個(gè)且不含全部極大項(xiàng) 第82頁(yè)/共198頁(yè)主范式的用途( (續(xù)) )例 用主析取范式判斷下述兩個(gè)公式是否等值： p(qr) 與 (p q)r p(qr) 與 (pq)r解 p(qr) = m0 m1 m2 m3 m4 m5 m7 (p q)r = m0 m1 m2 m3 m4 m5 m7 (pq)r = m1 m3 m4 m5 m7顯見(jiàn)，中的兩公式等值，而的不等值. (3) 判斷兩個(gè)公式是否等值說(shuō)明： 由公式A

55、的主析取范式確定它的主合取范式，反之亦然. 用公式A的真值表求A的主范式.第83頁(yè)/共198頁(yè)主范式的用途( (續(xù)) ) 例 某公司要從趙、錢(qián)、孫、李、周五名新畢業(yè)的大學(xué)生中選派一些人出國(guó)學(xué)習(xí). 選派必須滿足以下條件： (1)(1)若趙去，錢(qián)也去； (2)(2)李、周兩人中至少有一人去； (3)(3)錢(qián)、孫兩人中有一人去且僅去一人； (4)(4)孫、李兩人同去或同不去； (5)(5)若周去，則趙、錢(qián)也去. 試用主析取范式法分析該公司如何選派他們出國(guó)？第84頁(yè)/共198頁(yè)例 (續(xù))解此類問(wèn)題的步驟為： 將簡(jiǎn)單命題符號(hào)化 寫(xiě)出各復(fù)合命題 寫(xiě)出由中復(fù)合命題組成的合取式 求中所得公式的主析取范式 第8

56、5頁(yè)/共198頁(yè)例 (續(xù))解 設(shè)p：派趙去，q：派錢(qián)去，r：派孫去， s：派李去，u：派周去. . (1) (pq) (2) (s u) (3) (qr) ( q r) (4) (r s) ( rs) (5) (u(p q) (1) (5)構(gòu)成的合取式為 A=(pq) (s u) (qr) ( q r) (r s) ( rs) (u(p q)第86頁(yè)/共198頁(yè)例 (續(xù)) A ( pq r su) (p qrs u)結(jié)論：由可知，A的成真賦值為00110與11001，因而派孫、李去（趙、錢(qián)、周不去）或派趙、錢(qián)、周去（孫、李不去）. . A的演算過(guò)程如下: : A ( p q) (qr) ( q

57、 r) (s u) ( u (p q) (r s) ( rs) （交換律) )B1= ( p q) (qr) ( q r) ( p qr) ( pq r) (qr) （分配律）第87頁(yè)/共198頁(yè)例 (續(xù))B2= (s u) ( u (p q) (su) (p q s) (p q u) （分配律）B1 B2 ( p qr su) ( pq r su) (qr su) (p qr s) (p qr u)再令 B3 = (r s) ( rs)得 A B1 B2 B3 ( pq r su) (p qrs u)注意：在以上演算中多次用矛盾律要求：自己演算一遍 第88頁(yè)/共198頁(yè)2.3 聯(lián)結(jié)詞全功能集

58、（完備集） 復(fù)合聯(lián)結(jié)詞 排斥或 與非式 或非式 真值函數(shù) 聯(lián)結(jié)詞全功能集（完備集）第89頁(yè)/共198頁(yè)復(fù)合聯(lián)結(jié)詞 排斥或: p q(pq) ( p q) 與非式: p q(p q) 或非式: p q(p q) 第90頁(yè)/共198頁(yè)真值函數(shù) 問(wèn)題：含n個(gè)命題變項(xiàng)的所有公式共產(chǎn)生多少個(gè)互不相同的真值表？定義 稱定義域?yàn)?00, 001, , 111，值域?yàn)?,1的函數(shù)是n元真值函數(shù)，定義域中的元素是長(zhǎng)為n的0,1串. 常用F:0,1n0,1 表示F是n元真值函數(shù). 共有多少個(gè)n元真值函數(shù). 例如 F:0,120,1，且F(00)=F(01)=F(11)=0，F(xiàn)(10)=1，則F為一個(gè)確定的2元真值

59、函數(shù).第91頁(yè)/共198頁(yè)命題公式與真值函數(shù) )2(13F對(duì)于任何一個(gè)含n個(gè)命題變項(xiàng)的命題公式A，都存在惟一的一個(gè)n元真值函數(shù)F為A的真值表. .等值的公式對(duì)應(yīng)的真值函數(shù)相同.下表給出所有2元真值函數(shù)對(duì)應(yīng)的真值表, 每一個(gè)含2 2個(gè)命題變項(xiàng)的公式的真值表都可以在下表中找到. 例如：pq, p q, ( p q) ( (pq) q) 等都對(duì)應(yīng)表中的第92頁(yè)/共198頁(yè)2元真值函數(shù)對(duì)應(yīng)的真值表p q0 00 10 11 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 )2(7)2(6)2(5)2(4)2(3)2(2

60、)2(1)2(0FFFFFFFFp q0 00 10 11 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 )2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF第93頁(yè)/共198頁(yè)聯(lián)結(jié)詞的全功能集 定義 在一個(gè)聯(lián)結(jié)詞的集合中，如果一個(gè)聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為冗余的聯(lián)結(jié)詞，否則稱為獨(dú)立的聯(lián)結(jié)詞.例如, ,在聯(lián)結(jié)詞集 , , , , 中，由于 pqp q,所以，為冗余的聯(lián)結(jié)詞; 類似地，也是冗余的聯(lián)結(jié)詞. 又在 , , 中，由于 p q( pq)，所以