1、離散數(shù)學 Discrete Mathematics,主講教師：王耀輝 wyh_c,教師簡介,1985年畢業(yè)于北京大學數(shù)學系計算數(shù)學專業(yè) 專業(yè)技術(shù)職務：教授、碩士導師 主講課程： 計算機類BASIC、FORTRAN、人工智能原理、C、C+、 PASCAL、Visual BASIC、程序設計方法學、 SQL server 2000、數(shù)據(jù)庫系統(tǒng)概論、軟件工程、 Visual FoxPro 數(shù)學類數(shù)值分析、最優(yōu)化計算方法、運籌學、離散數(shù)學、解題理論、圖論及其應用 E-mail：wyh_c Tel : 665677,課程主要內(nèi)容,第一部分 數(shù)理邏輯 第二部分 集合論 第三部分 代數(shù)系統(tǒng) 第四部分 圖論,

2、離散數(shù)學與計算機的關(guān)系,第一部分 數(shù)理邏輯 計算機是數(shù)理邏輯和電子學相結(jié)合的產(chǎn)物 第二部分 集合論 集合：一種重要的數(shù)據(jù)結(jié)構(gòu) 關(guān)系：關(guān)系數(shù)據(jù)庫的理論基礎 函數(shù)：所有計算機語言中不可缺少的一部分 第三部分 代數(shù)系統(tǒng) 計算機編碼和糾錯碼理論數(shù)字邏輯設計基礎，計算機使用的各種運算 第四部分 圖論 數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、計算機網(wǎng)絡原理的基礎,參考教材,1、離散數(shù)學 耿素云、屈婉玲、張立昂 清華大學出版社 2、離散數(shù)學題解 耿素云、屈婉玲、張立昂 清華大學出版社 3、離散數(shù)學導論 徐潔磐 高等教育出版社 4、離散數(shù)學 洪帆等編 電子工業(yè)出版社 5、 離散數(shù)學 李盤林等編 人民郵電出版社,學習要求

3、,出勤 思考 筆記 作業(yè),緒論,本課程是高校計算機專業(yè)學生的必修課之一，是計算機科學與技術(shù)專業(yè)的核心、骨干課程，也是數(shù)學、信息與計算科學、信息管理與信息系統(tǒng)等專業(yè)的專業(yè)基礎課程，是計算機科學與技術(shù)的理論基礎 該課程主要學習數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論等四大方面的內(nèi)容，包括：命題邏輯、謂詞邏輯、集合與關(guān)系、函數(shù)、代數(shù)結(jié)構(gòu)、格與布爾代數(shù)、圖論等 離散數(shù)學與計算機科學中的數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、算法分析、邏輯設計、系統(tǒng)結(jié)構(gòu)等課程聯(lián)系緊密 本課程重點在于培養(yǎng)和提高大學生的抽象思維、邏輯推理和概括能力，從而為以后專業(yè)課程的學習及工作需要打下基礎,緒論,離散數(shù)學課程地位： 計算機專業(yè)（核心課程）

4、 信息類專業(yè)（必修課程） 其它類專業(yè)（重要選修課程） 離散數(shù)學的后繼課程： 數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、 算法分析與設計、 數(shù)據(jù)庫、C+語言,緒論,離散數(shù)學課程的學習方法: 強調(diào)：邏輯性、抽象性； 注重：概念、方法與應用 離散數(shù)學的學習要領： 概念（正確） 必須掌握好離散數(shù)學中大量的 概念 判斷（準確） 根據(jù)概念對事物的屬性進行判斷 推理（可靠） 根據(jù)多個判斷推出一個新的判斷,例1：,說謊者與說真話者問題：N夫婦晚上出門，邀請了W小姐照看他們的4個孩子。在N夫婦離家以前，向W小姐交待了許多注意事項，其中包括4個孩子的情況。N夫婦說他們的4個孩子中只有一個孩子總是說真話，另外3個則總是說謊。N夫婦告訴了

5、W小姐說真話的孩子的名字，但由于注意事項太多，W小姐把名字忘記了。當她在為孩子們準備晚飯時，一個孩子在鄰室打碎了一個花瓶。 這是孩子們的話： B說：是S干的。 S說：是J干的。 L說：不是我打碎的。 J說：S說是我干的，他在說慌。 由于W小姐知道只有一個孩子說真話，她很快就找出了打碎花瓶的孩子。你知道是誰嗎？,例2：,設整數(shù)集合為Z 設自然數(shù)集合為N 比較Z與N元素的多少,例3：,對于給定自然數(shù)1n的任意排列，能否通過反復交換1，2，3，n中的元素而得到此排列？,=(1 5 2 3 6)(7 8)=(1 5)(1 2)(1 3)(1 6)(7 8),例4：,任意6人聚會中，必有3人彼此相識，或

6、有3人彼此不相識 用兩種顏色填涂完全圖K6的各邊，必包含有同色的“三角形”K3,第一部分 數(shù)理邏輯,先看著名物理學家愛因斯坦出過的一道題： 一個土耳其商人想找一個十分聰明的助手協(xié)助他經(jīng)商，有兩人前來應聘，這個商人為了試試哪個更聰明些，就把兩個人帶進一間漆黑的屋子里，他打開燈后說：“這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的，現(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置弄亂，然后我們?nèi)齻€人每人摸一頂帽子戴在自己頭上，在我開燈后，請你們盡快說出自己頭上戴的帽子是什么顏色的?！闭f完后，商人將電燈關(guān)掉，然后三人都摸了一頂帽子戴在頭上，同時商人將余下的兩頂帽子藏了起來，接著把燈打開。這時，那兩個應試者看到

7、商人頭上戴的是一頂紅帽子，其中一個人便喊道：“我戴的是黑帽子?！?請問這個人說得對嗎？他是怎么推導出來的呢？,推理,主要內(nèi)容,1 命題邏輯基本概念 2 命題邏輯等值演算 3 命題邏輯的推理理論 4 一階邏輯基本概念 5 一階邏輯等值演算與推理,1 命題邏輯基本概念,本章的主要內(nèi)容： 命題、聯(lián)結(jié)詞、復合命題 命題公式、賦值、命題公式的分類 1.1 命題與聯(lián)結(jié)詞 1.2 命題公式及其賦值,1.1 命題與聯(lián)結(jié)詞,命題及其分類 聯(lián)結(jié)詞與復合命題 復合命題的真假值,1.1.1 命題及其分類,命題：具有真假意義（判斷結(jié)果唯一）的陳述句 命題的真值：判斷結(jié)果 真值的取值：真（1）、假（0） 真命題與假命題

8、注意：感嘆句、祈使句、疑問句、悖論都不是命題,例1.1 下列句子中那些是命題？ (1) 是無理數(shù). (2) 2 + 5 8. (3) x + 5 3. (4) 你有鉛筆嗎？ (5) 這只兔子跑得真快呀！ (6) 請不要講話！ (7) 我正在說謊話.,真命題,假命題,真值不確定,疑問句,感嘆句,祈使句,悖論,(3)(7)都不是命題,1.1.1 命題及其分類,1.1.1 命題及其分類,命題的分類 （1）簡單命題（原子命題） （2）復合命題 簡單命題符號化 （1）用小寫英文字母 等來表示簡單命題 （2）用1表示真，用0表示假 例如： :3是無理數(shù)，則 是假命題， 的真值為0,1.1.2 聯(lián)結(jié)詞與復合

9、命題,例： 3是無理數(shù)是不對的 2是偶素數(shù) 2或4是素數(shù) 如果2是素數(shù)，則3也是素數(shù) 2是素數(shù)當且僅當3也是素數(shù)。,上述命題都是通過諸如“或”，“如果，則”等連詞聯(lián)結(jié)而成，這樣命題，稱為復合命題。相對地，構(gòu)成復合命題的命題稱為簡單命題。,1.1.2 聯(lián)結(jié)詞與復合命題,定義1.1 設p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式,記作p，符號稱作否定聯(lián)結(jié)詞。并規(guī)定p為真當且僅當p為假。 定義1.2 設p,q為二命題，復合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作pq，稱作合取聯(lián)結(jié)詞。并規(guī)定pq為真當且僅當p與q同時為真。 定義1.3 設p，q為二命題，復合命題“p或q”

10、稱作p與q的析取式，記作pq，稱作析取聯(lián)結(jié)詞。并規(guī)定pq為假當且僅當p與q同時為假。,1.1.2 聯(lián)結(jié)詞與復合命題,相容“或”與排斥“或” 例 將下列命題符號化。 (1)張曉靜愛唱歌或愛聽音樂。 (2)張曉靜是江西人或安徽人。 (3)張曉靜只能挑選202或203房間。 解 在解題時，先將原子命題符號化。 (1) p：張曉靜愛唱歌。 q：張曉靜愛聽音樂。 (2) r：張曉靜是江西人。 s：張曉靜是安徽人。 (3) t：張曉靜挑選202房間。u：張曉靜挑選203房間。,1.1.2 聯(lián)結(jié)詞與復合命題,思考題：只能在周二說的話 某人在周一總是說謊話，而在其它日子總是說真話。那么，有沒有他只能在周二才能

11、說的話呢？ “今天不是周一就是周二?！?1.1.2 聯(lián)結(jié)詞與復合命題,定義1.4 設p，q為二命題，復合命題“如果p，則q”稱作p與q的蘊涵式，記作pq，稱作蘊涵聯(lián)結(jié)詞。并規(guī)定pq為假當且僅當p為真q為假。 pq的邏輯關(guān)系表示q是p的必要條件。 注意在使用聯(lián)結(jié)詞時，特別注意以下幾點：,1.1.2 聯(lián)結(jié)詞與復合命題,在自然語言里，特別是在數(shù)學中，q是p的必要條件有許多不同的敘述方式。例如，“只要p，就q”，“因為p，所以q”，“p僅當q”，“只有q才p”，“除非q才p”，“除非q，否則非p”等等。以上各種敘述方式表面看來有所不同，但都表達的是q是p的必要條件，因而所用聯(lián)結(jié)詞均應符號化為，上述各種

12、敘述方式都應符號化為pq。 在自然語言中，“如果p，則q”中的前件p與后件q往往具有某種內(nèi)在聯(lián)系。而在數(shù)理邏輯中，p與q可以無任何內(nèi)在聯(lián)系。 在數(shù)學或其它自然科學中，“如果p，則q”往往表達的是前件p為真，后件q也為真的推理關(guān)系。但在數(shù)理邏輯中，作為一種規(guī)定，當p為假時，無論q是真是假，pq均為真。也就是說，只有p為真q為假這一種情況使得復合命題pq為假。,1.1.2 聯(lián)結(jié)詞與復合命題,定義1.5 設p，q為二命題，復合命題“p當且僅當q”稱作p與q的等價式，記作 ，稱作等價聯(lián)結(jié)詞。并規(guī)定 為真當且僅當p與q同時為真或同時為假。 的邏輯關(guān)系為p與q互為充分必要條件。 以上定義了五種最基本、最常

13、用、也是最重要的聯(lián)結(jié)詞， ，將它們組成一個集合， ，稱為一個聯(lián)結(jié)詞集。其中為一元聯(lián)結(jié)詞，其余的都是二元聯(lián)結(jié)詞。,1.1.2 聯(lián)結(jié)詞與復合命題,例 將下列命題符號化，并指出各復合命題的真值： (1) 如果3+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整除

14、。 (10)只有a能被4整除，a才能被2整除。,1.1.3 復合命題真假值,聯(lián)結(jié)詞可以嵌套使用，在嵌套使用時，規(guī)定如下優(yōu)先順序： ( )， ，對于同一優(yōu)先級的聯(lián)結(jié)詞，先出現(xiàn)者先運算。,1.2 命題公式及其賦值,命題公式的定義 公式的層次 公式的賦值 真值表 公式的真假值分類,1.2.1 命題公式的定義,由于簡單命題是真值唯一確定的命題邏輯中最基本的研究單位，所以也稱簡單命題為命題常項或命題常元。從本節(jié)開始對命題進一步抽象，首先稱真值可以變化的陳述句為命題變項或命題變元，也用p,q,r,表示命題變項。當p,q,r,表示命題變項時，它們就成了取值0或1的變項，因而命題變項已不是命題。這樣一來，p,

15、q,r,既可以表示命題常項，也可以表示命題變項。在使用中，需要由上下文確定它們表示的是常項還是變項。,1.2.1 命題公式的定義,定義1.6 (1)單個命題變項是合式公式，并稱為原子命題公式。 (2)若A是合式公式，則(A)也是合式公式。 (3)若A，B是合式公式，則(AB)，(AB)，(AB)，(A B)也是合式公式。 (4)只有有限次地應用(1)(3)形式的符號串才是合式公式。 合式公式也稱為命題公式或命題形式，并簡稱為公式。 如：(pq)(qr)，(pq)r，p(qr)等都是合式公式，而pqr，（p(rq)等不是合式公式。 注意：定義1.6給出的合式公式的定義方式稱為歸納定義方式，后面還

16、將多次出現(xiàn)這種定義方式。,1.2.2 公式的層次,1.2.3 公式的賦值,1.2.3 公式的賦值,定義1.8 設p1,p2,pn是出現(xiàn)在公式A中的全部命題符號，給p1,p2,pn各指定一個真值，稱為對A的一個賦值或解釋。若指定的一組值使A的真值為1，則稱這組值為A的成真賦值；若使A的真值為0，則稱這組值為A的成假賦值。 不難看出，含n(n=1)個命題變項的公式共有2n個不同的賦值。,1.2.4 真值表,定義1.9 將命題公式A在所有賦值下取值情況列成表，稱作A的真值表。 構(gòu)造真值表的具體步驟如下： (1) 找出公式中所含的全體命題變項p1,p2,pn (若無下角標就按字典順序排列)，列出2n個

17、賦值。本課件規(guī)定，賦值從000開始，然后按二進制加法依次寫出各賦值，直到111為止。 (2) 按從低到高的順序?qū)懗龉降母鱾€層次。 (3) 對應各個賦值計算出各層次的真值，直到最后計算出公式的真值。,1.2.4 真值表,例1.8 求下列公式的真值表，并求成真賦值和成假賦值。,1.2.4 真值表,1.2.4 真值表,1.2.4 真值表,1.2.5 公式的真假值分類,定義1.10 設A為任一命題公式。 (1) 若A在它的各種賦值下取值均為真,則稱A是重言式或永真式。 (2) 若A在它的各種賦值下取值均為假,則稱A是矛盾式或永假式。 (3) 若A不是矛盾式,則稱A是可滿足式。 注：關(guān)于n個命題變元P

18、1,P2,Pn,可以構(gòu)造多少個真值表呢? n個命題變元共產(chǎn)生2n個不同賦值,在每個賦值下,公式的值只有0和1兩個值。于是n個命題變元的真值表共有 種不同情況。,1.2.5 公式的真假值分類,例1.10 下列公式中,哪些具有相同的真值表? (1) pq (2) qr (3) (pq)(pr)p) (4) (qr)(pp),1.2.5 公式的真假值分類,第1章小結(jié),主要內(nèi)容,1.命題與真值（或真假值）。 2.簡單命題與復合命題。 3.聯(lián)結(jié)詞：否定聯(lián)結(jié)詞，合取聯(lián)結(jié)詞，析取聯(lián)結(jié)詞，蘊涵聯(lián)結(jié)詞，等價聯(lián)結(jié)詞。 4.命題公式（簡稱公式）。 5.命題公式的層次和公式的賦值。 6.真值表。 7.公式的類型（重言

19、式（或永真式），矛盾式（或永假式），可滿足式）。,第1章小結(jié),學習要求,1.在5種聯(lián)結(jié)詞中，要特別注意蘊涵聯(lián)結(jié)的應用，要弄清三個問題： pq的邏輯關(guān)系 pq的真值 pq的靈活的敘述方法 2.寫真值表要特別仔細認真，否則會出錯誤。 3.深刻理解各聯(lián)結(jié)詞的邏輯含義。 4.熟練地將復合命題符號化。 5.會用真值表求公式的成真賦值和成假賦值。,2 命題邏輯的等值演算,等值式 對偶與范式 聯(lián)結(jié)詞的完備集,2.1 等值式,等值式的概念 用真值表判斷公式的等值 等值演算,2.1.1等值式的概念,兩公式什么時候代表了同一個命題呢？抽象地看，它們的真假取值完全相同時即代表了相同的命題。 設公式A,B共同含有n個

20、命題變項，可能A或B有啞元，若A與B有相同的真值表，則說明在2n個賦值的每個賦值下，公式A與公式B的真值都相同。于是等價式A B應為重言式。 定義2.1 設A,B是兩個命題公式，若A,B構(gòu)成的等價式A B為重言式，則稱公式A與公式B是等值的，記作A B.,2.1.1等值式的概念,判斷等值式有如下方法： 真值表 等值演算 范式,2.1.2用真值表判斷公式的等值,例2.1 判斷下面兩個公式是否等值： (pq)與pq,2.1.2用真值表判斷公式的等值,例2.2 判斷下列各組公式是否等值： （1）p(qr)與(pq)r （2）(pq)r與(pq)r,2.1.3 等值演算,2.1.3 等值演算,2.1.

21、3 等值演算,以上16組等值式包含了24個重要等值式。由于A,B,C可以代表任意的公式，因而以上各等值式都是用元語言符號書寫的，稱這樣的等值式為等值式模式，每個等值式模式都給出了無窮多個同類型的具體的等值式。 例如，在蘊涵等值式（2.12）中，取A=p，B=q時，得等值式 pq pq 當取A=pqr，B=pq時，得等值式 (pqr)(pq) (pqr)(pq) 這些具體的等值式都被稱為原來的等值式模式的代入實例。 每個具體的代入實例的正確性都可以用真值表證明之，而每個等值式模式可用歸納法證明之。,2.1.3 等值演算,2.1.3 等值演算,2.1.3 等值演算,2.1.3 等值演算,2.1.3

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

23、斷為A2=pq 丙的判斷為A3=qr,2.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,2.1.3 等值演算,由王教授所說 E=(B1C2D3) (B1C3D2) (B2C1D3) (B2C3D1) (B2C1D2) (B3C2D1) 為真命題。,E=(pqr)(pqr) 但因為王教授不能既是上海人，又是杭州人，因而p,r必有

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

25、,pn) A* ( p1, p2, pn) (2) A( p1, p2, pn) A* (p1,p2,pn) 定理（對偶原理）設A，B為兩個命題公式， 若A B，則A* B*.,2.2.2 析取范式與合取范式,對應于同一個真值表，可以有很多公式，其形式可以不同，但彼此等值。是否有標準形式？,由“1”看：與有一種情形成立，G即取1 G p q p q G (p q) ( p q),由“0”看：與有一種情形成立，G即取0 G (p q) (p q),2.2.2 析取范式與合取范式,文字:命題變項及其否定的總稱 簡單析取式:有限個文字構(gòu)成的析取式 如 p, q, pq, pqr, 簡單合取式:有限個

26、文字構(gòu)成的合取式 如 p, q, pq, pqr, 析取范式:由有限個簡單合取式組成的析取式 A1A2Ar, 其中A1,A2,Ar是簡單合取式 合取范式:由有限個簡單析取式組成的合取式 A1A2Ar , 其中A1,A2,Ar是簡單析取式,2.2.2 析取范式與合取范式,范式:析取范式與合取范式的總稱 公式A的析取范式: 與A等值的析取范式 公式A的合取范式: 與A等值的合取范式 說明： 單個文字既是簡單析取式，又是簡單合取式 形如 pqr, pqr 的公式既是析取范式， 又是合取范式 (為什么?),命題公式的范式,定理 任何命題公式都存在著與之等值的析取范式 與合取范式. 求公式A的范式的步驟

27、： (1) 消去A中的, （若存在） (2) 否定聯(lián)結(jié)詞的內(nèi)移或消去 (3) 使用分配律 對分配（析取范式） 對分配（合取范式） 公式的范式存在，但不惟一，這是它的局限性,求公式的范式舉例,例 求下列公式的析取范式與合取范式 (1) A=(pq)r 解 (pq)r (pq)r （消去） pqr （結(jié)合律） 這既是A的析取范式（由3個簡單合取式組成的析 取式），又是A的合取范式（由一個簡單析取式 組成的合取式）,求公式的范式舉例(續(xù)),(2) B=(pq)r 解 (pq)r (pq)r （消去第一個） (pq)r （消去第二個） (pq)r （否定號內(nèi)移德摩根律） 這一步已為析取范式（兩個簡單合

28、取式構(gòu)成） 繼續(xù)： (pq)r (pr)(qr) （對分配律） 這一步得到合取范式（由兩個簡單析取式構(gòu)成）,極小項與極大項,定義 在含有n個命題變項的簡單合取式(簡單析取式)中， 若每個命題變項均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一 次，而且第i（1in）個文字出現(xiàn)在左起第i位上，稱這樣 的簡單合取式（簡單析取式）為極小項（極大項）. 說明：n個命題變項產(chǎn)生2n個極小項和2n個極大項 2n個極小項（極大項）均互不等值 用mi表示第i個極小項，其中i是該極小項成真賦值的十進制表示. 用Mi表示第i個極大項，其中i是該極大項成假賦值的十進制表示, mi(Mi)稱為極小項(極大項)的名稱. mi與Mi的

29、關(guān)系: mi Mi , Mi mi,極小項與極大項(續(xù)),由p, q兩個命題變項形成的極小項與極大項,由p, q, r三個命題變項形成的極小項與極大項,主析取范式與主合取范式,主析取范式: 由極小項構(gòu)成的析取范式 主合取范式: 由極大項構(gòu)成的合取范式 例如，n=3, 命題變項為p, q, r時， (pqr)(pqr) m1m3 是主析取范式 (pqr)(pqr) M1M5 是主合取范式 A的主析取范式: 與A等值的主析取范式 A的主合取范式: 與A等值的主合取范式.,主析取范式與主合取范式(續(xù)),定理 任何命題公式都存在著與之等值的主析取范 式和主合取范式, 并且是惟一的. 用等值演算法求公式

30、的主范式的步驟： (1) 先求析取范式（合取范式） (2) 將不是極小項（極大項）的簡單合取式（簡 單析取式）化成與之等值的若干個極小項的析 ?。O大項的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、冪等律等. (3) 極小項（極大項）用名稱mi（Mi）表示，并 按角標從小到大順序排序.,求公式的主范式,例 求公式 A=(pq)r的主析取范式與主合 取范式. (1) 求主析取范式 (pq)r (pq)r , （析取范式） (pq) (pq)(rr) (pqr)(pqr) m6m7 , ,求公式的主范式(續(xù)),r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m

31、3m5m7 , 代入并排序，得 (pq)r m1m3m5 m6m7（主析取范式）,求公式的主范式(續(xù)),(2) 求A的主合取范式 (pq)r (pr)(qr) , （合取范式） pr p(qq)r (pqr)(pqr) M0M2, ,求公式的主范式(續(xù)),qr (pp)qr (pqr)(pqr) M0M4 , 代入并排序，得 (pq)r M0M2M4 （主合取范式）,主范式的用途與真值表相同,(1) 求公式的成真賦值和成假賦值 例如 (pq)r m1m3m5 m6m7， 其成真賦值為001, 011, 101, 110, 111， 其余的賦值 000, 010, 100為成假賦值. 類似地，由

32、主合取范式也可立即求出成 假賦值和成真賦值.,主范式的用途(續(xù)),(2) 判斷公式的類型 設A含n個命題變項，則 A為重言式A的主析取范式含2n個極小項 A的主合取范式為1. A為矛盾式 A的主析取范式為0 A的主合析取范式含2n個極大項 A為非重言式的可滿足式 A的主析取范式中至少含一個且不含全部極小項 A的主合取范式中至少含一個且不含全部極大項,主范式的用途(續(xù)),例 用主析取范式判斷下述兩個公式是否等值： p(qr) 與 (pq)r p(qr) 與 (pq)r 解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (pq)r = m1m3

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

34、式 求中所得公式的主析取范式,例 (續(xù)),解 設p：派趙去，q：派錢去，r：派孫去， s：派李去，u：派周去. (1) (pq) (2) (su) (3) (qr)(qr) (4) (rs)(rs) (5) (u(pq) (1) (5)構(gòu)成的合取式為 A=(pq)(su)(qr)(qr) (rs)(rs)(u(pq),例 (續(xù)), A (pqrsu)(pqrsu) 結(jié)論：由可知，A的成真賦值為00110與11001， 因而派孫、李去（趙、錢、周不去）或派趙、錢、 周去（孫、李不去）. A的演算過程如下: A (pq)(qr)(qr)(su)(u(pq) (rs)(rs) （交換律) B1= (

35、pq)(qr)(qr) (pqr)(pqr)(qr) （分配律）,例 (續(xù)),B2= (su)(u(pq) (su)(pqs)(pqu) （分配律） B1B2 (pqrsu)(pqrsu) (qrsu)(pqrs)(pqru) 再令 B3 = (rs)(rs) 得 A B1B2B3 (pqrsu)(pqrsu) 注意：在以上演算中多次用矛盾律 要求：自己演算一遍,2.3 聯(lián)結(jié)詞全功能集（完備集）,復合聯(lián)結(jié)詞 排斥或 與非式 或非式 真值函數(shù) 聯(lián)結(jié)詞全功能集（完備集）,復合聯(lián)結(jié)詞,排斥或: pq(pq)(pq) 與非式: pq(pq) 或非式: pq(pq),真值函數(shù),問題：含n個命題變項的所有

36、公式共產(chǎ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(10)=1，則F為一個確定的2元真值函數(shù).,命題公式與真值函數(shù),對于任何一個含n個命題變項的命題公式A，都存在 惟一的一個n元真值函數(shù)F為A的真值表. 等值的公式對應的真值函數(shù)相同. 下表給出所有2元真值函數(shù)對應的真值表, 每一個含 2個命題變項的公式的真值表都可以在下表中找到. 例如：p

37、q, pq, (pq)(pq)q) 等都對應 表中的,2元真值函數(shù)對應的真值表,聯(lián)結(jié)詞的全功能集,定義 在一個聯(lián)結(jié)詞的集合中，如果一個聯(lián)結(jié)詞可 由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為冗余 的聯(lián)結(jié)詞，否則稱為獨立的聯(lián)結(jié)詞. 例如,在聯(lián)結(jié)詞集, , , , 中，由于 pqpq, 所以，為冗余的聯(lián)結(jié)詞; 類似地，也是冗余的 聯(lián)結(jié)詞. 又在, , 中，由于 pq(pq)， 所以，是冗余的聯(lián)結(jié)詞. 類似地，也是冗余的聯(lián) 結(jié)詞.,聯(lián)結(jié)詞的全功能集(續(xù)),定義 設S是一個聯(lián)結(jié)詞集合，如果任何n(n1) 元 真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表 示，則稱S是聯(lián)結(jié)詞全功能集. 說明： 若S是聯(lián)結(jié)詞全功

38、能集，則任何命題公式都可用S 中的聯(lián)結(jié)詞表示. 若S1, S2是兩個聯(lián)結(jié)詞集合，且S1 S2. 若S1是全 功能集，則S2也是全功能集.,聯(lián)結(jié)詞的全功能集實例,(1) S1=, , , (2) S2=, , , , (3) S3=, (4) S4=, (5) S5=, (6) S6= (7) S8=, 而, 等則不是聯(lián)結(jié)詞全功能集.,第2章 小結(jié),主要內(nèi)容,1. 等值式與等值演算。 2. 基本的等值式，其中含：雙重否定律、冪等律、交換律、結(jié)合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾律、蘊含等值式、等價等值式、假言易位、等價否定等值式、歸謬論。 3. 與主析取范式及主合取范式有關(guān)

39、的概念：簡單合取式、簡單析取式、析取范式、合取范式、極小項、極大項、主析取范式、主合取范式。 4. 聯(lián)結(jié)詞完備集（或完全集）。,第2章 小結(jié),學習要求,1. 深刻理解等值式的概念。 2. 牢記24個基本等值式，這是等值演算的基礎；能熟練地應用它們進行等值演算。 3. 了解簡單析取式、簡單合取式、析取范式、合取范式的概念。 4. 深刻理解極小項及極大項的定義及它們的名稱，及名稱下角標與成真賦值的關(guān)系。 5. 熟練掌握求公式的主析取范式的方法。 6. 熟練掌由公式的主析取范式求公式的主合取范式的方法。 7. 會用公式的主析取范式（主合取范式）求公式的成真賦值、成假賦值。 8. 會將公式等值地化為任

40、何聯(lián)結(jié)詞完備集中的公式。,3 命題邏輯的推理理論,推理的形式結(jié)構(gòu) 判斷推理是否正確的方法 推理定律與推理規(guī)則 構(gòu)造證明法,推理的形式結(jié)構(gòu)問題的引入,推理舉例: (1) 正項級數(shù)收斂當且僅當部分和上有界. (2) 若ACBD，則AB且CD. 推理: 從前提出發(fā)推出結(jié)論的思維過程 上面(1)是正確的推理，而(2)是錯誤的推理. 證明: 描述推理正確或錯誤的過程.,推理的形式結(jié)構(gòu),定義 若對于每組賦值，A1A2 Ak 均為假，或 當A1A2Ak為真時, B也為真, 則稱由A1,A2, Ak 推B的推理正確 , 否則推理不正確（錯誤）. “A1, A2, , Ak 推B” 的推理正確 當且僅當 A1A

41、2AkB為重言式. 推理的形式結(jié)構(gòu): A1A2AkB 或 前提： A1, A2, , Ak 結(jié)論： B 若推理正確，則記作：A1A2AkB.,判斷推理是否正確的方法,真值表法 等值演算法 主析取范式法 構(gòu)造證明法 說明：當命題變項比較少時，用前3個方法比較方 便, 此時采用形式結(jié)構(gòu)“ A1A2AkB” . 而在構(gòu) 造證明時，采用“前提: A1, A2, , Ak, 結(jié)論: B”.,實例,例 判斷下面推理是否正確 (1) 若今天是1號，則明天是5號. 今天是1號. 所 以明天是5號. 解 設 p：今天是1號，q：明天是5號. 證明的形式結(jié)構(gòu)為: (pq)pq 證明（用等值演算法） (pq)pq

42、(pq)p)q pqq 1 得證推理正確,實例 (續(xù)),(2) 若今天是1號，則明天是5號. 明天是5號. 所以今天是1號. 解 設p：今天是1號，q：明天是5號. 證明的形式結(jié)構(gòu)為: (pq)qp 證明（用主析取范式法） (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 結(jié)果不含m1, 故01是成假賦值，所以推理不正確.,推理定律重言蘊涵式,重要的推理定律 A (AB) 附加律 (AB) A 化簡律 (AB)A B 假言推理 (AB)B A 拒取式 (AB)B A 析取三段論 (AB)(BC) (AC) 假言三段論 (AB)(BC) (AC)

43、 等價三段論 (AB)(CD)(AC) (BD) 構(gòu)造性二難,推理定律 (續(xù)),(AB)(AB)(AA) B 構(gòu)造性二難（特殊形式） (AB)(CD)( BD) (AC) 破壞性二難,說明： A, B, C為元語言符號 若某推理符合某條推理定律，則它自然是正確的 AB產(chǎn)生兩條推理定律: A B, B A,推理規(guī)則,推理規(guī)則(續(xù)),構(gòu)造證明直接證明法,例 構(gòu)造下面推理的證明： 若明天是星期一或星期三，我就有課. 若有課，今天必備課. 我今天下午沒備課. 所以， 明天不是星期一和星期三. 解 設 p：明天是星期一，q：明天是星期三， r：我有課，s：我備課 形式結(jié)構(gòu)為 前提：(pq)r, rs,

44、s 結(jié)論：pq,直接證明法 (續(xù)),證明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置換,構(gòu)造證明附加前提證明法,欲證明 前提：A1, A2, , Ak 結(jié)論：CB 等價地證明 前提：A1, A2, , Ak, C 結(jié)論：B 理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,附加前提證明法 (續(xù)),例 構(gòu)造下面推理的證明: 2是素數(shù)或合數(shù). 若2是素數(shù)，則 是無理數(shù). 若 是無理數(shù)，則4不是素數(shù). 所以，如果4是 素數(shù)，則2是合數(shù). 用附加前提證明法構(gòu)造證明 解 設 p：2是素數(shù)，q：2是合

45、數(shù)， r： 是無理數(shù)，s：4是素數(shù) 形式結(jié)構(gòu) 前提：pq, pr, rs 結(jié)論：sq,附加前提證明法 (續(xù)),證明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段論 p 拒取式 pq 前提引入 q 析取三段論 請用直接證明法證明之,構(gòu)造證明歸謬法（反證法）,欲證明 前提：A1, A2, , Ak 結(jié)論：B 將B加入前提，若推出矛盾，則得證推理正確. 理由: A1A2AkB (A1A2Ak)B (A1A2AkB) 括號內(nèi)部為矛盾式當且僅當 (A1A2AkB)為 重言式,歸謬法 (續(xù)),例 構(gòu)造下面推理的證明 前提：(pq)r, rs, s, p 結(jié)論：q 證明（用歸繆法） q

46、結(jié)論否定引入 rs 前提引入 s 前提引入 r 拒取式,歸謬法 (續(xù)), (pq)r 前提引入 (pq) 析取三段論 pq 置換 p 析取三段論 p 前提引入 pp 合取 請用直接證明法證明之,第3章 小結(jié),主要內(nèi)容,1. 推理的形式結(jié)構(gòu)： 推理的前提 推理的結(jié)論 推理正確 有效結(jié)論 2. 判斷推理是否正確的方法： 真值表法 等值演算法 主析取范式法 3. 對于正確的推理，在自然推理系統(tǒng)P中構(gòu)造證明,4. 自然推理系統(tǒng)P的定義 自然推理系統(tǒng)P的推理規(guī)則： 前提引入規(guī)則、結(jié)論引入規(guī)則、置換規(guī)則、假言推理規(guī)則、附加規(guī)則、化簡規(guī)則、拒取式規(guī)則、假言三段式規(guī)則、構(gòu)造性二難規(guī)則、合取引入規(guī)則。 附加前提

47、證明法 歸謬法,第3章 小結(jié),學習要求,1. 理解并記住推理的形式結(jié)構(gòu)的三種等價形式，即 A1,A2,AkB A1A2AkB 前提與結(jié)論分開寫： 前提：A1,A2,Ak 結(jié)論：B 在判斷推理是否正確時，用；在P系統(tǒng)中構(gòu)造證明時用。 2. 熟練掌握判斷推理是否正確的三種方法（真值表法，等值演算法，主析取范式法）。 3. 牢記P系統(tǒng)中的各條推理規(guī)則。 4. 對于給定的正確推理，要求在P系統(tǒng)中給出嚴謹?shù)淖C明序列。 5. 會用附加前提證明法和歸謬法。,命題邏輯習題,1將下列命題符號化。,（1）劉曉月跑得快，跳得高。 （2）老王是山東人或河北人。 （3）因為天氣冷，所以我穿了羽絨服。 （4）王歡與李樂組

48、成一個小組。 （5）李辛與李末是兄弟。 （6）王強與劉威都學過法語。 （7）他一面吃飯，一面聽音樂。,（1）pq，其中，p：劉曉月跑得快，q：劉曉月跳得高。 （2）pq，其中，p：老王是山東人，q：老王是河北人。 （3）pq，其中，p：天氣冷，q：我穿了羽絨服。 （4）p，其中，p：王歡與李樂組成一個小組，是簡單命題。 （5）p，其中，p：李辛與李末是兄弟。 （6）pq，其中，p：王強學過法語，q：劉威學過法語。 （7）pq，其中，p：他吃飯，q：他聽音樂。,命題邏輯習題,1將下列命題符號化。,（8）pq，其中，p：天下大雨，q：他乘班車上班。 （9）pq，其中，p：他乘班車上班，q：天下大雨

49、。 （10）pq，其中，p：他乘班車上班，q：天下大雨。 （11）pq，其中，p：下雪路滑，q：他遲到了。 （12）(pq)或pq，其中，p：2是素數(shù)，q：4是素數(shù)。 （13）(pq)或pq，其中，p：2是素數(shù)，q：4是素數(shù)。,（8）如果天下大雨，他就乘班車上班。 （9）只有天下大雨，他才乘班車上班。 （10）除非天下大雨，他才乘班車上班。 （11）下雪路滑，他遲到了。 （12）2與4都是素數(shù)，這是不對的。 （13）“2或4是素數(shù)，這是不對的”是不對的。,命題邏輯習題,（1）pq，其中，p：224，q：地球靜止不動，真值為0。 （2）pq，其中，p：224，q：地球運動不止，真值為1。 （3）

50、pq，其中，p：地球上有樹木，q：人類能生存，真值為1。 （4）pq，其中，p：地球上有水，q： 是無理數(shù)，真值為1。,2將下列命題符號化，并給出各命題的真值： （1）若324，則地球是靜止不動的。 （2）若324，則地球是運動不止的。 （3）若地球上沒有樹木，則人類不能生存。 （4）若地球上沒有水，則 是無理數(shù)。,命題邏輯習題,3.設A與B均為含n個命題變項的公式，判斷下列命題是否為真？ （1）A B 當且僅當 AB是可滿足式。 （2）A B 當且僅當 A與B有相同的主析取范式。 （3）若A為重言式，則A的主析取范式中含有2n個極小項。 （4）若A為矛盾式，則A的主析取范式為1。 （5）若A

51、為矛盾式，則A的主合取范式為1。 （6）任何公式A都能等值地化為聯(lián)結(jié)詞集、 中的公式。 （7）任何公式A都能等值地化為聯(lián)結(jié)詞集、中的公式。,命題邏輯習題,（1）(pq)(qp) （2）(pq)rq （3）(pq)p,4. 用等值演算法來判斷公式的類型。,5. 用主析取范式法判斷公式的類型，并求公式的成真賦值。,6. 求公式的主合取范式，并求公式的成假賦值。,命題邏輯習題,7. 已知命題公式A中含3個命題變項p，q，r，并知道它的成真賦值分別為001，010，111，求A的主析取范式和主合取范式。,由于公式含3個命題變項，并且已知該公式有3個成真賦值001，010，111，因而有5個成假賦值00

52、0，011，100，101，110。 成真賦值對應的極小項分別為m1，m2，m7，故主析取范式為 A m1m2m7 成假賦值對應的極大項分別為M0，M3，M4，M5，M6，故主合取范式為 A M0M3M4M5M6 注意：公式的真值表與主析取范式(主合取范式)可以相互唯一確定。,命題邏輯習題,8.用等演算法證明下面等值式。 （1）(pq)(pr) (p(qr) （2）(pq)(pq) p,用等值演算法證明AB，可以有3種方式： 從A出發(fā)，證到B； 從B出發(fā)證到A； 或證明AC和BC，由于等值關(guān)系有傳遞性和對稱性，故AB。,命題邏輯習題,9.求公式(pq)r 在以下各聯(lián)結(jié)詞完備集中與之等值的一個公式： （1）,， （2）, （3）, （4）， （5）,1） (pq)r (pq)r 2） (pq)r (pq)r (pq)r 3） (pq)r (pq)r (pq)r) (pq)r),4） (pq)r (pq)r) (pq)r)( (pq)r),5） (pq)r (pq)r (pq)r(pq)r (pq)r) (