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

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

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

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

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

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

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

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

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

9、話，她很快就找出了打碎花瓶的孩子。你知道是誰嗎？打碎花瓶的孩子。你知道是誰嗎？第9頁/共198頁例2： 設整數(shù)集合為設整數(shù)集合為Z Z 設自然數(shù)集合為設自然數(shù)集合為N N 比較比較Z Z與與N N元素的多少元素的多少第10頁/共198頁例3： 對于給定自然數(shù)對于給定自然數(shù)1n的任意排列，能否通過反復交換的任意排列，能否通過反復交換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頁/共198頁例4： 任意任意6 6人聚會中，必有人聚會

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25、若A，B是合式公式，則(AB)，(AB)，(AB)，(A B)也是合式公式。 (4)只有有限次地應用(1)(3)形式的符號串才是合式公式。 合式公式也稱為命題公式或命題形式，并簡稱為公式。 如：(pq)(qr)，(pq)r，p(qr)等都是合式公式，而pqr，（p(rq)等不是合式公式。 注意：定義1.6給出的合式公式的定義方式稱為歸納定義方式，后面還將多次出現(xiàn)這種定義方式。 第31頁/共198頁1.2.2 公式的層次公式的層次定義定義 1.71.7 (1)若公式 A 是單個的命題變項，則稱 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頁/共198頁1.2.3 公式的賦值公式的賦值公式就代表命題，但代表的命題是真還是假呢？ 在命題公式中，由于有命題符號的出現(xiàn)，因而真值是不確定的。當將公式中出現(xiàn)的全部命題符

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

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

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

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

31、A不是矛盾式不是矛盾式, ,則稱則稱A A是是可滿足式可滿足式。注：關于n個命題變元P1,P2,Pn,可以構造多少個真值表呢? n個命題變元共產生2n個不同賦值,在每個賦值下,公式的值只有0和1兩個值。于是n個命題變元的真值表共有 種不同情況。 n22第40頁/共198頁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頁/共198頁1.2.5 公式

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

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

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

35、律 ABBA, ABBA 結合律 (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頁/共198頁2.1.3 等值演算零律 A11, A00 同一律 A0A. A1A 排中律 AA1 矛盾律 AA0 蘊涵等值式 ABAB 等價等值式 AB(AB)(BA) 假言易位 ABBA 等價否定等值式 ABAB 歸謬論 (AB)(AB) A 注意：要牢記各個等值式，這是繼續(xù)學習的基礎 第52頁/共198頁2.1.3 等值演算以上以上1616組等值式包含了組等值

36、式包含了2424個重要等值式。由于個重要等值式。由于A,B,CA,B,C可以代表任意的公式，因而以上各等值式都是用元語可以代表任意的公式，因而以上各等值式都是用元語言符號書寫的，稱這樣的等值式為言符號書寫的，稱這樣的等值式為等值式模式等值式模式，每個，每個等值式模式都給出了無窮多個同類型的具體的等值式。等值式模式都給出了無窮多個同類型的具體的等值式。例如，在蘊涵等值式（例如，在蘊涵等值式（2.122.12）中，?。┲?，取A=pA=p，B=qB=q時，時，得等值式得等值式 pq pq pq pq 當取當取A=pqrA=pqr，B=pqB=pq時，得等值式時，得等值式 (pqr)(pq) (pqr

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

38、式 B 置換了(A)中的所有的 A 后得到的命題公式，若 BA，則(B)(A) 第54頁/共198頁2.1.3 等值演算三、 等值演算的應用舉例（以后章節(jié)待續(xù)） 1證明兩個公式等值 例 證明 p(qr) (pq)r 證 p(qr) p(qr) （蘊涵等值式，置換規(guī)則） (pq)r （結合律，置換規(guī)則） (pq)r （德摩根律，置換規(guī)則） (pq)r （蘊涵等值式，置換規(guī)則） 幾點說明： 也可以從右邊開始演算（請做一遍） 因為每一步都用置換規(guī)則，故可不寫出 熟練后，基本等值式也可以不寫出 用等值演算不能直接證明兩個公式不等值 第55頁/共198頁2.1.3 等值演算例 證明 p(qr) (pq)

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

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

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

42、.1.3 等值演算則 甲的判斷全對 B1=A1=pq 甲的判斷對一半 B2=(pq)(pq) 甲的判斷全錯 B3=pq 乙的判斷全對 C1=A2=pq 乙的判斷對一半 C2=(pq)(pq) 乙的判斷全錯 C3=pq 丙的判斷全對 D1=A3=qr 丙的判斷對一半 D2=(qr)(qr) 丙甲的判斷全錯 D3=qr 第62頁/共198頁2.1.3 等值演算由王教授所說E=(B1C2D3) (B1C3D2) (B2C1D3) (B2C3D1) (B2C1D2) (B3C2D1) 為真命題。 E=(pqr)(pqr) 但因為王教授不能既是上海人，但因為王教授不能既是上海人，又是杭州人，因而又是杭州

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

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

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

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

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

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

49、項形成的極小項與極大項 公式公式 成真賦值成真賦值名稱名稱 公式公式 成假賦值成假賦值名稱名稱 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 極小項極小項 極大項極大項 第73頁/共198頁 由p, q, r三個命題變項形成的極小項與極大項 極小項極小項 極大項極大項 公式公式 成真成真賦值賦值名稱名稱 公式公式 成假成假賦值賦值名稱名稱 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頁/共198頁主析取范式與主合取范式 主析取范式: : 由極小項構成的析取范式主合取范式: : 由極大項構成的合取范式例如，n=3, 命題變項為p, q, r時， ( pq r) ( p q r) m1 m3 是主析取范式 (p qr) ( p qr) M1 M5 是主合取范式 A的主析取范式: 與A等值的主析取范式 A的主合

51、取范式: : 與A等值的主合取范式. 第75頁/共198頁主析取范式與主合取范式( (續(xù)) )定理 任何命題公式都存在著與之等值的主析取范式和主合取范式, 并且是惟一的. . 用等值演算法求公式的主范式的步驟： (1) 先求析取范式（合取范式） (2) 將不是極小項（極大項）的簡單合取式（簡 單析取式）化成與之等值的若干個極小項的析 ?。O大項的合?。?，需要利用同一律（零 律）、排中律（矛盾律）、分配律、冪等律等. (3) 極小項（極大項）用名稱mi（Mi）表示，并按角標從小到大順序排序. 第76頁/共198頁求公式的主范式例 求公式 A=(pq)r的主析取范式與主合 取范式. . (1) 求

52、主析取范式 (pq)r (p q) r , （析取范式） (p q) (p q) ( r r) (p qr) (p q r) m6 m7 , 第77頁/共198頁求公式的主范式( (續(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頁/共198頁求公式的主范式( (續(xù)) ) (2) 求A的主合取范式 (pq)r (p r) (q r) , （合取范式） p r p (qq) r (p q r) (pq r) M0 M2, 第79頁

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

54、式含2n個極小項 A的主合取范式為1.A為矛盾式 A的主析取范式為0 A的主合析取范式含2n個極大項A為非重言式的可滿足式A的主析取范式中至少含一個且不含全部極小項A的主合取范式中至少含一個且不含全部極大項 第82頁/共198頁主范式的用途( (續(xù)) )例 用主析取范式判斷下述兩個公式是否等值： 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顯見，中的兩公式等值，而的不等值. (3) 判斷兩個公式是否等值說明： 由公式A

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

56、5頁/共198頁例 (續(xù))解 設p：派趙去，q：派錢去，r：派孫去， s：派李去，u：派周去. . (1) (pq) (2) (s u) (3) (qr) ( q r) (4) (r s) ( rs) (5) (u(p q) (1) (5)構成的合取式為 A=(pq) (s u) (qr) ( q r) (r s) ( rs) (u(p q)第86頁/共198頁例 (續(xù)) A ( pq r su) (p qrs u)結論：由可知，A的成真賦值為00110與11001，因而派孫、李去（趙、錢、周不去）或派趙、錢、周去（孫、李不去）. . A的演算過程如下: : 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頁/共198頁例 (續(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頁/共198頁2.3 聯(lián)結詞全功能集

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

59、函數(shù).第91頁/共198頁命題公式與真值函數(shù) )2(13F對于任何一個含n個命題變項的命題公式A，都存在惟一的一個n元真值函數(shù)F為A的真值表. .等值的公式對應的真值函數(shù)相同.下表給出所有2元真值函數(shù)對應的真值表, 每一個含2 2個命題變項的公式的真值表都可以在下表中找到. 例如：pq, p q, ( p q) ( (pq) q) 等都對應表中的第92頁/共198頁2元真值函數(shù)對應的真值表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頁/共198頁聯(lián)結詞的全功能集 定義 在一個聯(lián)結詞的集合中，如果一個聯(lián)結詞可由集合中的其他聯(lián)結詞定義，則稱此聯(lián)結詞為冗余的聯(lián)結詞，否則稱為獨立的聯(lián)結詞.例如, ,在聯(lián)結詞集 , , , , 中，由于 pqp q,所以，為冗余的聯(lián)結詞; 類似地，也是冗余的聯(lián)結詞. 又在 , , 中，由于 p q( pq)，所以