左孝凌離散數(shù)學(xué)課件1

1、v邏輯：是研究推理的科學(xué)。公元前四世紀(jì)邏輯：是研究推理的科學(xué)。公元前四世紀(jì)由希臘的哲由希臘的哲學(xué)家亞里斯多德首創(chuàng)。作為一門(mén)獨(dú)立科學(xué)，十七世紀(jì)，學(xué)家亞里斯多德首創(chuàng)。作為一門(mén)獨(dú)立科學(xué)，十七世紀(jì)，德國(guó)的萊布尼茲德國(guó)的萊布尼茲(Leibniz)給邏輯學(xué)引進(jìn)了符號(hào)給邏輯學(xué)引進(jìn)了符號(hào), 又稱(chēng)又稱(chēng)為數(shù)理邏輯為數(shù)理邏輯(或符號(hào)邏輯或符號(hào)邏輯)。 邏輯邏輯可分為：可分為：1. 形式邏輯（通過(guò)數(shù)學(xué)方法）形式邏輯（通過(guò)數(shù)學(xué)方法） 數(shù)理邏輯數(shù)理邏輯 2. 辯證邏輯辯證邏輯 指引進(jìn)一套符號(hào)體系的方法。指引進(jìn)一套符號(hào)體系的方法。 辯證邏輯辯證邏輯是研究反映客觀(guān)世界辯證發(fā)展過(guò)程的人類(lèi)思是研究反映客觀(guān)世界辯證發(fā)展過(guò)程的人類(lèi)思

2、維的形態(tài)的。維的形態(tài)的。v形式邏輯形式邏輯是研究思維的形式結(jié)構(gòu)和規(guī)律的科學(xué)，它撇是研究思維的形式結(jié)構(gòu)和規(guī)律的科學(xué)，它撇開(kāi)具體的、個(gè)別的思維內(nèi)容，從形式結(jié)構(gòu)方面研究概開(kāi)具體的、個(gè)別的思維內(nèi)容，從形式結(jié)構(gòu)方面研究概念、判斷和推理及其正確聯(lián)系的規(guī)律。念、判斷和推理及其正確聯(lián)系的規(guī)律。v數(shù)理邏輯數(shù)理邏輯是用數(shù)學(xué)方法研究推理的形式結(jié)構(gòu)和推理的是用數(shù)學(xué)方法研究推理的形式結(jié)構(gòu)和推理的規(guī)律的數(shù)學(xué)學(xué)科。它的創(chuàng)始人規(guī)律的數(shù)學(xué)學(xué)科。它的創(chuàng)始人Leibniz，為了實(shí)現(xiàn)把，為了實(shí)現(xiàn)把推理變?yōu)檠菟愕南敕?，把?shù)學(xué)引入了形式邏輯。其后，推理變?yōu)檠菟愕南敕ǎ褦?shù)學(xué)引入了形式邏輯。其后，又經(jīng)多人努力，逐漸使得數(shù)理邏輯成為一門(mén)專(zhuān)門(mén)

3、的學(xué)又經(jīng)多人努力，逐漸使得數(shù)理邏輯成為一門(mén)專(zhuān)門(mén)的學(xué)科?？?。v上個(gè)世紀(jì)上個(gè)世紀(jì)30年代以后，數(shù)理邏輯進(jìn)入一個(gè)嶄新的發(fā)展年代以后，數(shù)理邏輯進(jìn)入一個(gè)嶄新的發(fā)展階段，邏輯學(xué)不僅與數(shù)學(xué)結(jié)合，還與計(jì)算機(jī)科學(xué)等密階段，邏輯學(xué)不僅與數(shù)學(xué)結(jié)合，還與計(jì)算機(jī)科學(xué)等密切關(guān)聯(lián)。切關(guān)聯(lián)。v1931年年Godel不完全性定理的提出，以及遞不完全性定理的提出，以及遞歸函數(shù)可計(jì)算性的引入，促使了歸函數(shù)可計(jì)算性的引入，促使了1936年年Turing機(jī)的產(chǎn)生，十年后，第一臺(tái)電子計(jì)機(jī)的產(chǎn)生，十年后，第一臺(tái)電子計(jì)算機(jī)問(wèn)世算機(jī)問(wèn)世。v從廣義上講，數(shù)理邏輯包括四論、兩演從廣義上講，數(shù)理邏輯包括四論、兩演算算即集合論、模型論、遞歸論、證明即

4、集合論、模型論、遞歸論、證明論和命題演算、謂詞演算，但現(xiàn)在提到數(shù)論和命題演算、謂詞演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題演算和謂詞演算。理邏輯，一般是指命題演算和謂詞演算。本書(shū)也只研究這兩個(gè)演算。本書(shū)也只研究這兩個(gè)演算。2022-3-10v數(shù)理邏輯與計(jì)算機(jī)學(xué)、控制論、人工智能的相互滲透數(shù)理邏輯與計(jì)算機(jī)學(xué)、控制論、人工智能的相互滲透推動(dòng)了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏推動(dòng)了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏輯、時(shí)態(tài)邏輯等都是目前比較熱門(mén)的研究領(lǐng)域。輯、時(shí)態(tài)邏輯等都是目前比較熱門(mén)的研究領(lǐng)域。v本篇我們只從語(yǔ)義出發(fā)，對(duì)數(shù)理邏輯中的命題演算與本篇我們只從語(yǔ)義出發(fā)，對(duì)數(shù)理邏輯中的命題演算

5、與謂詞演算等作一簡(jiǎn)單的、直接的、非形式化的介紹，謂詞演算等作一簡(jiǎn)單的、直接的、非形式化的介紹，將不涉及任何公理系統(tǒng)。將不涉及任何公理系統(tǒng)。2022-3-10 1.1.1 命題（命題（Proposition) 1.1.2 命題的表示方法命題的表示方法 1.1.3 命題的分類(lèi)命題的分類(lèi)2022-3-101.1.1 命題命題 數(shù)理邏輯研究的中心問(wèn)題是推理（數(shù)理邏輯研究的中心問(wèn)題是推理（inference),而而推理的前提和結(jié)論都是表達(dá)判斷的陳述句，因而表達(dá)推理的前提和結(jié)論都是表達(dá)判斷的陳述句，因而表達(dá)判斷的陳述句構(gòu)成了推理的基本單位判斷的陳述句構(gòu)成了推理的基本單位?；靖拍罨靖拍?命題：能夠判斷真

6、假的陳述句。命題：能夠判斷真假的陳述句。 命題的真值：命題的判斷結(jié)果。命題的真值只取兩個(gè)命題的真值：命題的判斷結(jié)果。命題的真值只取兩個(gè) 值值:真（真（用用T(true)或或1表示表示）、假（）、假（用用F(false)或或0表示表示） 。 真命題：判斷為正確的命題，即真值為真的命題。真命題：判斷為正確的命題，即真值為真的命題。 假命題：判斷為錯(cuò)誤的命題，即真值為假的命題。假命題：判斷為錯(cuò)誤的命題，即真值為假的命題。2022-3-10因而又可以稱(chēng)因而又可以稱(chēng)命題是具有唯一真值的陳述句。命題是具有唯一真值的陳述句。判斷命題的兩個(gè)步驟判斷命題的兩個(gè)步驟： 1 1、是否為陳述句；、是否為陳述句； 2

7、2、是否有確定的、唯一的真值。、是否有確定的、唯一的真值。 例例：判斷下列句子是否為命題。：判斷下列句子是否為命題。 (1). 100是自然數(shù)。是自然數(shù)。 T (2). 太陽(yáng)從西方升起。太陽(yáng)從西方升起。 F (3). 3+3=8 . F(4). How do you do ? 疑問(wèn)句，疑問(wèn)句，不是命題不是命題(5). 明年的十月一日是晴天。明年的十月一日是晴天。是命題，其真值到是命題，其真值到明年明年 十月一日方可知道。十月一日方可知道。(6). x+39 不是命題不是命題(7). 我正在說(shuō)謊。我正在說(shuō)謊。是悖論是悖論(8). 1+101=110 二進(jìn)制中為真，十進(jìn)制中為假。二進(jìn)制中為真，十進(jìn)

8、制中為假。(9). 如果太陽(yáng)從西方升起，那么如果太陽(yáng)從西方升起，那么2是奇數(shù)是奇數(shù)。T(10). 國(guó)足能殺入國(guó)足能殺入2006世界杯當(dāng)且僅當(dāng)世界杯當(dāng)且僅當(dāng)2+2=4。F(11). 今天天氣多好?。〗裉焯鞖舛嗪冒。?感嘆句，感嘆句，不是命題不是命題(12). 請(qǐng)你關(guān)上門(mén)！請(qǐng)你關(guān)上門(mén)！ 祁使句，不祁使句，不是命題，是命題， (13). 別的星球上有生物。別的星球上有生物。 是命題，客觀(guān)上能判斷真是命題，客觀(guān)上能判斷真 假。假。說(shuō)明：說(shuō)明：（1）只有）只有具有確定真值具有確定真值的的陳述句陳述句才是命題。一才是命題。一 切沒(méi)有判斷內(nèi)容的句子，無(wú)所謂是非的句子，切沒(méi)有判斷內(nèi)容的句子，無(wú)所謂是非的句子，

9、 如如感嘆句、祁使句、疑問(wèn)句等都不是命題。感嘆句、祁使句、疑問(wèn)句等都不是命題。（2） 因?yàn)橐驗(yàn)槊}只有兩種真值，所以命題只有兩種真值，所以“命題邏輯命題邏輯”又稱(chēng)又稱(chēng) “二值邏輯二值邏輯”。 (3) “具有確定真值具有確定真值”是指客觀(guān)上的具有，與我們是否是指客觀(guān)上的具有，與我們是否知道它的真值是兩回事。如上例中的（知道它的真值是兩回事。如上例中的（5）和（）和（13）。）。1.1.2 命題的表示方法命題的表示方法 在本書(shū)中，用大寫(xiě)英文字母在本書(shū)中，用大寫(xiě)英文字母A,B,P,Q或帶下標(biāo)的字或帶下標(biāo)的字母母P1,P2,P3 , ,或數(shù)字或數(shù)字(1),2, ,等表示命題，稱(chēng)之為等表示命題，稱(chēng)之為命

10、題標(biāo)識(shí)符。命題標(biāo)識(shí)符。 例如：例如： P：羅納爾多是球星。：羅納爾多是球星。 Q：5是負(fù)數(shù)。是負(fù)數(shù)。 P3：明天天氣晴。明天天氣晴。 (2)：太陽(yáng)從西方升起。：太陽(yáng)從西方升起。 皆為符號(hào)化的命題，其真值依次為皆為符號(hào)化的命題，其真值依次為1、0、1或或0、0。 命題標(biāo)識(shí)符又有命題常量、命題變?cè)驮幼冊(cè)}標(biāo)識(shí)符又有命題常量、命題變?cè)驮幼冊(cè)?。之分。命題常量命題常量：表示確定命題的命題標(biāo)識(shí)符。：表示確定命題的命題標(biāo)識(shí)符。命題變?cè)}變?cè)好}標(biāo)識(shí)符如僅是表示任意命題的位置標(biāo)：命題標(biāo)識(shí)符如僅是表示任意命題的位置標(biāo) 志，就稱(chēng)為命題變?cè)?。志，就稱(chēng)為命題變?cè)?。原子變?cè)幼冊(cè)寒?dāng)命題變?cè)硎驹?/p>

11、命題時(shí)，該變?cè)Q(chēng)為：當(dāng)命題變?cè)硎驹用}時(shí)，該變?cè)Q(chēng)為 原子變?cè)?。原子變?cè)?。命題變?cè)灿妹}變?cè)灿肁,B,P,Q,P1,P2,P3 , , 表示。表示。1.1.3 命題的分類(lèi)：命題的分類(lèi)：簡(jiǎn)單簡(jiǎn)單/原子命題：原子命題：不能分解為更簡(jiǎn)單的陳述語(yǔ)句的命題不能分解為更簡(jiǎn)單的陳述語(yǔ)句的命題(如如上例中的命題上例中的命題)。復(fù)合命題：復(fù)合命題：由簡(jiǎn)單命題通過(guò)由簡(jiǎn)單命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。聯(lián)結(jié)而成的命題。 聯(lián)結(jié)詞就是復(fù)合命題中的運(yùn)算符。聯(lián)結(jié)詞就是復(fù)合命題中的運(yùn)算符。 注意注意：（1）一個(gè)符號(hào)）一個(gè)符號(hào)(如如P), 它表示的是命題常量還是命題變它表示的是命題常量還是命題變?cè)?，一般由上下文?lái)確

12、定。元，一般由上下文來(lái)確定。（2）命題變?cè)梢员硎救我饷}，它不能確定真值，）命題變?cè)梢员硎救我饷}，它不能確定真值，故命題變?cè)皇敲}。這與故命題變?cè)皇敲}。這與“變數(shù)變數(shù)x不是數(shù)不是數(shù)”是一樣是一樣的道理。的道理。小結(jié)：小結(jié)：本節(jié)主要介紹了命題、命題的真值、原子命題、本節(jié)主要介紹了命題、命題的真值、原子命題、復(fù)合命題、命題標(biāo)識(shí)符、命題常量、命題變?cè)驮訌?fù)合命題、命題標(biāo)識(shí)符、命題常量、命題變?cè)驮幼冊(cè)母拍?。變?cè)母拍?。重點(diǎn)理解和掌握命題、命題變?cè)獌蓚€(gè)概重點(diǎn)理解和掌握命題、命題變?cè)獌蓚€(gè)概念。念。 作業(yè)：作業(yè)：P8 （1）1920 1.2邏輯邏輯聯(lián)結(jié)詞聯(lián)結(jié)詞(Logical Conne

13、ctives)1.2.1 否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞(Negation) 1.2.2 合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞(Conjunction)1.2.3 析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞(Disjunction)1.2.4 條件聯(lián)結(jié)詞條件聯(lián)結(jié)詞(蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞Conditional)1.2.5 雙條件聯(lián)結(jié)雙條件聯(lián)結(jié)(等值聯(lián)結(jié)詞等值聯(lián)結(jié)詞Biconditional) 21 1.2邏輯邏輯聯(lián)結(jié)詞聯(lián)結(jié)詞(Logical Connectives) 在命題邏輯中,主要研究的是復(fù)合命題,而復(fù)合命題是由原子命題與邏輯聯(lián)結(jié)詞組合而成,聯(lián)結(jié)詞組是復(fù)合命題的重要組成部分.1.2.1 否定否定聯(lián)結(jié)詞聯(lián)結(jié)詞 定義1.2.1 設(shè)設(shè)P為一命題

14、，為一命題， P的否定是一個(gè)新的復(fù)合的否定是一個(gè)新的復(fù)合命題命題, 稱(chēng)為稱(chēng)為P的否定式，記作的否定式，記作 “P”讀作讀作“非非P”. 符符號(hào)號(hào)“ ” 稱(chēng)為否定聯(lián)結(jié)詞。稱(chēng)為否定聯(lián)結(jié)詞。 P為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P為為假假.說(shuō)明說(shuō)明： “”屬于一元屬于一元(unary)運(yùn)算符運(yùn)算符22 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives) “”的定義也可用下表來(lái)說(shuō)明的定義也可用下表來(lái)說(shuō)明. 聯(lián)結(jié)詞聯(lián)結(jié)詞“”的定義真值表的定義真值表 P P011023 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives)例例1. P: 天津是一個(gè)城市天津是一個(gè)城市. Q: 3是偶

15、數(shù)是偶數(shù).于是于是: P: 天津不是一個(gè)城市天津不是一個(gè)城市. Q: 3不是偶數(shù)不是偶數(shù).例例2. P:蘇州處處清潔蘇州處處清潔. Q:這些都是男同學(xué)這些都是男同學(xué). P:蘇州不處處清潔蘇州不處處清潔 (注意注意,不是處處不清潔不是處處不清潔). Q:這些不都是男同學(xué)這些不都是男同學(xué).24 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives)1.2.2 合取合取聯(lián)結(jié)聯(lián)結(jié)詞詞(Conjunction)定義定義1.2.2 設(shè)設(shè)P,Q為二命題，復(fù)合命題為二命題，復(fù)合命題“P并且并且Q”（或（或“P與與Q”）稱(chēng)為）稱(chēng)為P與與Q的合取式，記作的合取式，記作P Q，符號(hào)，符號(hào)“” 稱(chēng)為合取

16、聯(lián)結(jié)詞稱(chēng)為合取聯(lián)結(jié)詞. P P Q Q 為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P P和和Q Q同同時(shí)為真時(shí)為真. . 聯(lián)結(jié)詞聯(lián)結(jié)詞“”的定義真值表的定義真值表P PQ Q P P Q Q 0 00 00 00 01 10 01 10 00 01 11 11 125 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives)說(shuō)明：說(shuō)明：“” 屬于二元屬于二元(binary)運(yùn)算符運(yùn)算符.合取運(yùn)算特點(diǎn)合取運(yùn)算特點(diǎn)：只有參與運(yùn)算的二命題全為真時(shí)，運(yùn)算：只有參與運(yùn)算的二命題全為真時(shí)，運(yùn)算 結(jié)果才為真，否則為假。結(jié)果才為真，否則為假。 自然語(yǔ)言中的表示自然語(yǔ)言中的表示“并且并且”意思的聯(lián)結(jié)詞，如意思的聯(lián)結(jié)詞

17、，如“既既又又”、“不但不但而且而且”、“雖然雖然但是但是”、“一面一面一一面面”、 “和和”、 “與與”等都可以符號(hào)化為等都可以符號(hào)化為 。26 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives)例例3. 將下列命題符號(hào)化將下列命題符號(hào)化. (1) 李平既聰明又用功李平既聰明又用功. (2) 李平雖然聰明李平雖然聰明, 但不用功但不用功. (3)李平不但聰明李平不但聰明,而且用功而且用功. (4)李平不是不聰明李平不是不聰明,而是不用功而是不用功.解解: 設(shè)設(shè) P:李平聰明李平聰明. Q:李平用功李平用功.則則 (1) PQ (2) P Q (3) PQ (4) (P) Q

18、 注意注意：不要見(jiàn)到不要見(jiàn)到“與與”或或“和和”就使用聯(lián)結(jié)詞就使用聯(lián)結(jié)詞 ！例如例如: (1)見(jiàn)課本見(jiàn)課本P11 例題例題6 (2) 李敏和李華是姐妹。李敏和李華是姐妹。 （3）李敏和張華是朋友。）李敏和張華是朋友。27 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives) 例例4. 試生成下列命題的合取試生成下列命題的合取. (1) P: 我們?cè)谖覀冊(cè)赬NA303. Q: 今天是星期二今天是星期二. (2) S：李平在吃飯李平在吃飯. R：張明在吃飯張明在吃飯. 解解: (1) PQ :我們?cè)谖覀冊(cè)赬NA303且今天是星期二且今天是星期二. (2) SR:R:李平與張明在吃飯

19、李平與張明在吃飯. 同之處的不和與語(yǔ)言中與日常.):(, , )2(1).(.(,) 1 (李華和李敏是姐妹如去翻譯不能一概用和與不同意義上使用聯(lián)結(jié)詞自然語(yǔ)言中有時(shí)在各種如上例的命題原子命題生成一個(gè)新的甚至互為否定的獨(dú)立無(wú)關(guān)的邏輯學(xué)中允許兩個(gè)相互28 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives)1.2.3 析取聯(lián)結(jié)析取聯(lián)結(jié)詞詞(Disjunction)定義定義1.2.3 設(shè)設(shè)P,Q為二命題，復(fù)合命題為二命題，復(fù)合命題“P或或Q” 稱(chēng)為稱(chēng)為P與與Q的的析取式，記作析取式，記作PQ ，符號(hào)，符號(hào)稱(chēng)為析取聯(lián)結(jié)詞稱(chēng)為析取聯(lián)結(jié)詞. PQ為真為真當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) P與與Q中至少有一

20、個(gè)為真中至少有一個(gè)為真. 聯(lián)結(jié)詞聯(lián)結(jié)詞“”的定義真值表的定義真值表P PQ Q P P Q Q 0 00 00 00 01 11 11 10 01 11 11 11 129 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives)說(shuō)明：說(shuō)明：“” 屬于二元屬于二元(binary)運(yùn)算符運(yùn)算符.析取運(yùn)算特點(diǎn)析取運(yùn)算特點(diǎn)：只有參與運(yùn)算的二命題全為假時(shí)，：只有參與運(yùn)算的二命題全為假時(shí)，運(yùn)算結(jié)果才為假，否則為真。運(yùn)算結(jié)果才為假，否則為真。 由析取聯(lián)結(jié)詞的定義可以看出，由析取聯(lián)結(jié)詞的定義可以看出， “”與漢與漢語(yǔ)中的聯(lián)結(jié)詞語(yǔ)中的聯(lián)結(jié)詞“或或”意義相近，但又不完全相同。意義相近，但又不完全相同

21、。在現(xiàn)代漢語(yǔ)中，聯(lián)結(jié)詞的在現(xiàn)代漢語(yǔ)中，聯(lián)結(jié)詞的“或或”實(shí)際上有實(shí)際上有“”和和“”之分。考察下面命題：之分?？疾煜旅婷}：（1）小王愛(ài)打球或愛(ài)跑步。）小王愛(ài)打球或愛(ài)跑步。（ 設(shè)設(shè)P：小王愛(ài)打球。：小王愛(ài)打球。 Q：小王愛(ài)跑步。：小王愛(ài)跑步。 則上述命題可符號(hào)化為：則上述命題可符號(hào)化為：P Q30 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives)（2）林芳學(xué)過(guò)英語(yǔ)或法語(yǔ)。）林芳學(xué)過(guò)英語(yǔ)或法語(yǔ)。 （設(shè)設(shè)P：林芳學(xué)過(guò)英語(yǔ)林芳學(xué)過(guò)英語(yǔ)。 Q：林芳學(xué)過(guò)法語(yǔ)林芳學(xué)過(guò)法語(yǔ)。 則上述命題可符號(hào)化為：則上述命題可符號(hào)化為： P Q（3）派小王或小李中的一人去開(kāi)會(huì)。）派小王或小李中的一人去開(kāi)會(huì)

22、。（） 設(shè)設(shè)P：派小王去開(kāi)會(huì)。派小王去開(kāi)會(huì)。Q：派小李去開(kāi)會(huì)。派小李去開(kāi)會(huì)。 則上述命題可符號(hào)化為：則上述命題可符號(hào)化為：(P Q) ( PQ)（4）人固有一死，或重于泰山或輕于鴻毛）人固有一死，或重于泰山或輕于鴻毛.(） （5）ab=0, 即即a=0 或或 b=0. （由此可見(jiàn)由此可見(jiàn), “P Q”表示的是表示的是“ 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives)注意：注意：當(dāng)當(dāng)P和和Q客觀(guān)上不能同時(shí)發(fā)生時(shí)，客觀(guān)上不能同時(shí)發(fā)生時(shí)，“P或或Q”可可以符號(hào)化為以符號(hào)化為“P Q”。例如：小王現(xiàn)在在宿舍或在圖書(shū)館。例如：小王現(xiàn)在在宿舍或在圖書(shū)館。 設(shè)設(shè) P：小王現(xiàn)在在宿舍。：

23、小王現(xiàn)在在宿舍。Q：小王現(xiàn)在在圖書(shū)館。：小王現(xiàn)在在圖書(shū)館。 則上述命題可符號(hào)化為：則上述命題可符號(hào)化為：P Q。同之處的不或語(yǔ)言中與日常) 36:(, )2(.) 1 (例如去翻譯不能一概用或不同意義上使用聯(lián)結(jié)詞自然語(yǔ)言中有時(shí)在各種題聯(lián)結(jié)兩個(gè)毫無(wú)關(guān)系的命邏輯學(xué)中允許P32 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives)1.2.4. 條件聯(lián)結(jié)詞條件聯(lián)結(jié)詞(蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞Conditional)定義定義1.2.4 設(shè)設(shè)P,Q為二命題，復(fù)合命題為二命題，復(fù)合命題“如果如果P則則Q(若若P則則Q)” 稱(chēng)為稱(chēng)為P與與Q的條件命題的條件命題,記作記作P Q. P Q為假當(dāng)且為假

24、當(dāng)且僅當(dāng)僅當(dāng)P為真且為真且Q為假為假.稱(chēng)符號(hào)稱(chēng)符號(hào)“”為條件聯(lián)結(jié)詞。并稱(chēng)為條件聯(lián)結(jié)詞。并稱(chēng)P為前件，為前件，Q為后件為后件. 聯(lián)結(jié)詞聯(lián)結(jié)詞“”的定義真值表的定義真值表P PQ QP P Q Q0 00 01 10 01 11 11 10 00 01 11 11 133 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives) 注：注：（1）P Q表示的基本邏輯關(guān)系是表示的基本邏輯關(guān)系是,Q是是P的必要的必要條件或條件或P是是Q的充分條件的充分條件. 因此復(fù)合命題因此復(fù)合命題“只要只要P P就就Q Q”、“因?yàn)橐驗(yàn)镻 P，所以，所以Q Q”、“P P僅當(dāng)僅當(dāng)Q Q”、“只有只有Q才才

25、P”等都可以符號(hào)化為等都可以符號(hào)化為P Q 的形式。的形式。 （2） ”“ 屬于二元屬于二元(binary)運(yùn)算符。運(yùn)算符。例例5. 5. 將下列命題符號(hào)化。將下列命題符號(hào)化。 （1 1）天不下雨，則草木枯黃。）天不下雨，則草木枯黃。 P P：天下雨。：天下雨。 Q Q：草木枯黃。：草木枯黃。 則原命題可表示為：則原命題可表示為： PQPQ。34 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives) （2）如果小明學(xué)日語(yǔ)，小華學(xué)英語(yǔ)，則小芳學(xué)德語(yǔ)。）如果小明學(xué)日語(yǔ)，小華學(xué)英語(yǔ)，則小芳學(xué)德語(yǔ)。 P P：小明學(xué)日語(yǔ)：小明學(xué)日語(yǔ) Q Q：小華學(xué)英語(yǔ)：小華學(xué)英語(yǔ) R R：小芳學(xué)德語(yǔ)：小

26、芳學(xué)德語(yǔ). . 則原命題可表示為：則原命題可表示為：(PQ)R(PQ)R （3）只要不下雨，我就騎自行車(chē)上班。）只要不下雨，我就騎自行車(chē)上班。 P：天下雨。：天下雨。Q：我騎自行車(chē)上班。：我騎自行車(chē)上班。 則原命題可表示為：則原命題可表示為： PQPQ。 （4）只有只有不下雨，我才騎自行車(chē)上班。不下雨，我才騎自行車(chē)上班。 P：天下雨。：天下雨。Q：我騎自行車(chē)上班。：我騎自行車(chē)上班。 則原命題可表示為：則原命題可表示為： Q Q P P 。 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives) （5）如果如果 2+2=4, 則則太陽(yáng)從東方升起太陽(yáng)從東方升起。 (P Q, T) P

27、 Q 如果如果 2+2=4, 則則太陽(yáng)從西方升起太陽(yáng)從西方升起。 (P R, F) R 如果如果 2+2 4, 則太陽(yáng)從東方升起。則太陽(yáng)從東方升起。 (P Q , T) 如果如果 2+2 4, 則太陽(yáng)從西方升起。則太陽(yáng)從西方升起。 (P R, T)注意注意: (1)與自然語(yǔ)言的不同：與自然語(yǔ)言的不同：前件與后件可以沒(méi)有任何內(nèi)在聯(lián)系！前件與后件可以沒(méi)有任何內(nèi)在聯(lián)系！ (2) 在數(shù)學(xué)中，在數(shù)學(xué)中，“若若P則則Q”往往表示前件往往表示前件P為真，則后件為真，則后件Q為真的為真的推理關(guān)系推理關(guān)系. 但數(shù)理邏輯中，當(dāng)前件但數(shù)理邏輯中，當(dāng)前件P為假時(shí)，為假時(shí)， P Q的真值為真。的真值為真。36 1.2邏

28、輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives)1.2.5 雙條件聯(lián)結(jié)雙條件聯(lián)結(jié)(等值聯(lián)結(jié)詞等值聯(lián)結(jié)詞Biconditional) 定義定義1.2.5 設(shè)設(shè)P,Q為二命題，復(fù)合命題為二命題，復(fù)合命題“P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q” 稱(chēng)為稱(chēng)為P與與Q的雙條件命題，記作的雙條件命題，記作P iff Q或或 PQ，符號(hào)，符號(hào)稱(chēng)為雙條件（等值）聯(lián)結(jié)詞。稱(chēng)為雙條件（等值）聯(lián)結(jié)詞。 PQ為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P，Q真值相同真值相同。 聯(lián)結(jié)詞聯(lián)結(jié)詞“”的定義真值表的定義真值表P PQ QP P Q Q0 00 01 10 01 10 01 10 00 01 11 11 137 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞

29、詞(Logical Connectives)注：注：（1 1）P P僅當(dāng)僅當(dāng)Q Q 可譯為可譯為PQPQ P P當(dāng)當(dāng)Q Q 可譯為可譯為QPQP P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q 譯為譯為PQ （2）“”屬于二元屬于二元(binary)運(yùn)算符。運(yùn)算符。 (3) 雙條件命題雙條件命題PQ所表達(dá)的邏輯關(guān)系是所表達(dá)的邏輯關(guān)系是, P與與Q互為充分必要條件互為充分必要條件,相當(dāng)于相當(dāng)于(P Q) (Q P). 只要只要P與與Q的真值同為的真值同為1或同為或同為0, PQ的真值就為的真值就為1, 否則否則PQ的真值為的真值為0. 雙條件聯(lián)結(jié)詞連接的兩個(gè)命題之間可以沒(méi)雙條件聯(lián)結(jié)詞連接的兩個(gè)命題之間可以沒(méi)有因果關(guān)系。有

30、因果關(guān)系。例例6.6.分析下列命題的真值分析下列命題的真值. . (1) 2+2=4 (1) 2+2=4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)3 3是奇數(shù)是奇數(shù) . (P PQ)Q) P P： 2+2=4. Q2+2=4. Q：3 3是奇數(shù)是奇數(shù) . . 38 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives) (2) 2+2=4 2+2=4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)3 3不是奇數(shù)不是奇數(shù) . (P PQ)Q)(3) 2+2 4 (3) 2+2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)3 3是奇數(shù)是奇數(shù) . (PPQ)Q)(4) 2+2 4 (4) 2+2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)3 3不是奇數(shù)不是奇數(shù) . (PPQ)Q)約約

31、 定定: :1. 1. 運(yùn)算次序優(yōu)先級(jí)：運(yùn)算次序優(yōu)先級(jí)：， ， ，. . 2. 2. 相同的運(yùn)算符按從左至右次序計(jì)算，否則要相同的運(yùn)算符按從左至右次序計(jì)算，否則要 加上括號(hào)。加上括號(hào)。 3.3.最外層圓括號(hào)可省去。最外層圓括號(hào)可省去。 小結(jié)小結(jié): 本節(jié)介紹了五種聯(lián)結(jié)詞本節(jié)介紹了五種聯(lián)結(jié)詞(， ， ，),),重重點(diǎn)是理解和掌握點(diǎn)是理解和掌握五種聯(lián)結(jié)詞的內(nèi)涵及它們與自然語(yǔ)五種聯(lián)結(jié)詞的內(nèi)涵及它們與自然語(yǔ)言中相應(yīng)聯(lián)結(jié)詞的不同之處言中相應(yīng)聯(lián)結(jié)詞的不同之處.39 1.2邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞(Logical Connectives)作業(yè)作業(yè): 1. P8 (3), (5). 2. 預(yù)習(xí)預(yù)習(xí)1.3, 1.4思

32、考題思考題: 1. 何謂合式公式何謂合式公式? 2. 復(fù)合命題符號(hào)化的基本步驟是什么復(fù)合命題符號(hào)化的基本步驟是什么? 3.何謂真值表何謂真值表? 4. 兩個(gè)命題公式等價(jià)的涵義是什么兩個(gè)命題公式等價(jià)的涵義是什么? 5.兩個(gè)等價(jià)的命題公式其真值表有何關(guān)系兩個(gè)等價(jià)的命題公式其真值表有何關(guān)系?40411.3命題命題公式與翻譯公式與翻譯1.3.1 命題公式命題公式1.3.2 復(fù)合命題的符號(hào)化復(fù)合命題的符號(hào)化(翻譯翻譯)1.3.1 命題合式公式命題合式公式(Well-formed formula)(wff)定義定義1.3.1: :單個(gè)命題變?cè)兔}常量稱(chēng)為單個(gè)命題變?cè)兔}常量稱(chēng)為原子公式原子公式。命題合

33、式公式命題合式公式是由命題變?cè)?、是由命題變?cè)?、命題常量、命題常量、聯(lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起聯(lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來(lái)的符號(hào)串。我們以如下遞歸的形式來(lái)定來(lái)的符號(hào)串。我們以如下遞歸的形式來(lái)定義合式公式：義合式公式：421.3命題命題公式與翻譯公式與翻譯 定義定義1.3.2：(1)(1)原子公式是原子公式是合式合式公式公式( (wffwff) )。 （2）若）若A是合式公式，則是合式公式，則( A)也是合式公式。也是合式公式。 （3）若）若A，B是合式公式，則是合式公式，則(AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。 （4）當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)有限次地應(yīng)用有

34、限次地應(yīng)用(1)(3)所得到的包含所得到的包含原原子公式、子公式、聯(lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式。聯(lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式。注注: (1)合式公式也稱(chēng)為命題公式，并簡(jiǎn)稱(chēng)為公式。合式公式也稱(chēng)為命題公式，并簡(jiǎn)稱(chēng)為公式。 (2)命題公式一般不是命題命題公式一般不是命題,僅當(dāng)公式中的命題變僅當(dāng)公式中的命題變?cè)么_定的命題代入時(shí)元用確定的命題代入時(shí),才得到一個(gè)命題才得到一個(gè)命題.其真值依其真值依賴(lài)于代換變?cè)哪切┟}的真值賴(lài)于代換變?cè)哪切┟}的真值.431.3命題命題公式與翻譯公式與翻譯例例1 1：指出指出(P(P(P(P Q)Q)是否是命題公式是否是命題公式( (wffwff) )，如果是，則

35、具體說(shuō)明。如果是，則具體說(shuō)明。解：解： P P是是wffwff 由由(1)(1) Q Q是是wffwff 由由(1)(1) P P Q Q是是wffwff 由由(3) (3) (P(P (P(P Q) Q) 由由(3) (3) 例例2: 2: (P Q) , (R S) Q , P，( P)等均為合等均為合式公式，而式公式，而PQ S , (P W) Q)等不是合式等不是合式公式。公式。441.3命題命題公式與翻譯公式與翻譯 1.3.2 復(fù)合命題的符號(hào)化復(fù)合命題的符號(hào)化(翻譯翻譯) 有了命題演算的合式公式的概念有了命題演算的合式公式的概念,我們可我們可以把自然語(yǔ)言中的有些語(yǔ)句以把自然語(yǔ)言中的有

36、些語(yǔ)句(復(fù)合命題復(fù)合命題),翻譯成數(shù)理邏輯中的符號(hào)形式翻譯成數(shù)理邏輯中的符號(hào)形式.基本步驟基本步驟如下如下: (1) 分析出各簡(jiǎn)單命題分析出各簡(jiǎn)單命題,將它們符號(hào)化將它們符號(hào)化; (2) 使用合適的聯(lián)結(jié)詞使用合適的聯(lián)結(jié)詞,把簡(jiǎn)單命題逐個(gè)的把簡(jiǎn)單命題逐個(gè)的聯(lián)結(jié)起來(lái)聯(lián)結(jié)起來(lái),組成復(fù)合命題的符號(hào)化表示組成復(fù)合命題的符號(hào)化表示.451.3命題命題公式與翻譯公式與翻譯 例例3： 1) 我今天進(jìn)城，除非下雨。我今天進(jìn)城，除非下雨。1-3.(7) 2) 僅當(dāng)你走我將留下。僅當(dāng)你走我將留下。 3) 假如上午不下雨，我去看電影，否則就在家里假如上午不下雨，我去看電影，否則就在家里 讀書(shū)或看報(bào)。讀書(shū)或看報(bào)。 4)

37、除非你努力，否則你將失敗。除非你努力，否則你將失敗。P11例例5 5)一個(gè)人起初說(shuō)：一個(gè)人起初說(shuō)：“占據(jù)空間的、有質(zhì)量的而且不占據(jù)空間的、有質(zhì)量的而且不斷變化的叫做物質(zhì)斷變化的叫做物質(zhì)”；后來(lái)他改說(shuō)，；后來(lái)他改說(shuō)，“占據(jù)空間占據(jù)空間的有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的。的有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的?！眴?wèn)他前后主張的差異在什么地方，試以命題形式問(wèn)他前后主張的差異在什么地方，試以命題形式進(jìn)行分析進(jìn)行分析。 1-3.(6)461.3命題命題公式與翻譯公式與翻譯 例例4：P10 例題例題1 小結(jié)小結(jié)：本節(jié)介了命題公式的概念及復(fù)合：本節(jié)介了命題公式的概念及復(fù)合命題的符號(hào)化命題的符號(hào)化.重點(diǎn)是

38、理解命題公式的遞重點(diǎn)是理解命題公式的遞歸定義歸定義,掌握復(fù)合命題的符號(hào)化方法掌握復(fù)合命題的符號(hào)化方法. 作業(yè)作業(yè): P12 (1),(5)47481.4.1 真值表真值表(Truth Table)1.4.2 等價(jià)公式等價(jià)公式(1.4.1 真值表真值表 前面在定義聯(lián)結(jié)詞時(shí)前面在定義聯(lián)結(jié)詞時(shí),曾經(jīng)使用過(guò)真值表曾經(jīng)使用過(guò)真值表,下面給出下面給出真值表的定義真值表的定義. 定義定義1.4.1 (對(duì)公式的賦值或解釋對(duì)公式的賦值或解釋)設(shè)設(shè)P1 , P2 ,Pn是出是出現(xiàn)在公式現(xiàn)在公式A中的全部的命題變?cè)械娜康拿}變?cè)? 給給P1 , P2 ,Pn各指各指定一個(gè)真值，稱(chēng)為對(duì)定一個(gè)真值，稱(chēng)為對(duì)A的一個(gè)的

39、一個(gè)賦值賦值或或解釋解釋。若指定的。若指定的一組值使一組值使A的真值為真的真值為真(假假), 稱(chēng)這組值為稱(chēng)這組值為A的的成真成真(假假)賦值賦值.49比如比如:對(duì)公式對(duì)公式(PQ)R,賦值賦值011(即令即令P=0,Q=1,R=1) 為為(PQ)R的成真賦值的成真賦值; 另一組賦值另一組賦值010為為(PQ)R的成假賦值；還有的成假賦值；還有000，001，111考慮：考慮：含有含有n個(gè)命題變?cè)墓焦灿卸嗌俳M個(gè)命題變?cè)墓焦灿卸嗌俳M不同的賦值？不同的賦值？定義定義1.4.2(真值表真值表)在命題公式在命題公式A中中, 對(duì)于命題變?cè)膶?duì)于命題變?cè)拿恳唤M賦值和由它們所確定的命題公式每一組賦值

40、和由它們所確定的命題公式A的真值列的真值列成表，稱(chēng)做命題公式成表，稱(chēng)做命題公式A 的的真值表真值表。50對(duì)公式對(duì)公式A構(gòu)造真值表的具體步驟為：構(gòu)造真值表的具體步驟為：（1）找出公式中所有命題變?cè)┱页龉街兴忻}變?cè)狿1 , P2 ,Pn , 列出全部的列出全部的2n組賦值。組賦值。（2）按從小到大的順序列出對(duì)命題變?cè)┌磸男〉酱蟮捻樞蛄谐鰧?duì)命題變?cè)狿1 , P2 ,Pn ,的全部的全部2n組賦值。組賦值。（3）對(duì)應(yīng)各組賦值計(jì)算出公式）對(duì)應(yīng)各組賦值計(jì)算出公式A的真值，并的真值，并將其列在對(duì)應(yīng)賦值的后面。將其列在對(duì)應(yīng)賦值的后面。51例例1. 1. 給出給出(P(P Q)Q)(P(P Q)Q)的

41、真值表：的真值表：P P Q Q P P Q Q (P(P Q)Q) PP Q Q(P(P Q) Q) (P (P Q)Q)0 0 0 00 0 1 11 1 0 01 1 1 152例例1. 1. 給出給出(P(P Q)Q)(P(P Q)Q)的真值表：的真值表：P P Q Q P P Q Q (P(P Q)Q) PP Q Q(P(P Q) Q) (P (P Q)Q)0 0 0 00 01 11 11 10 0 1 10 01 11 11 11 1 0 00 01 11 11 11 1 1 11 10 00 01 153例例2：構(gòu)造公式：構(gòu)造公式 (P Q) R的的 真值表。真值表。PQRPQ

42、(P Q) R00000101001110010111011154例例2：構(gòu)造公式：構(gòu)造公式 (P Q) R的的 真值表。真值表。PQRPQ(P Q) R000100011101010011111000010100110101111155 練習(xí)練習(xí)1：構(gòu)造公式：構(gòu)造公式 (PQ)( Q P真值表。真值表。P Q P QP Q Q P(P Q)( Q P)0001101156 練習(xí)練習(xí)1：構(gòu)造公式：構(gòu)造公式 (PQ)( Q P真值表。真值表。P Q P QP Q Q P(P Q)( Q P)001111101101111001001110011157PQ (P Q) (P Q) (P Q) Q0

43、0011011練習(xí)練習(xí)2：構(gòu)造公式：構(gòu)造公式 (P Q Q 真值表。真值表。58PQ (P Q) (P Q) (P Q) Q00100011001001011100練習(xí)練習(xí)2：構(gòu)造公式：構(gòu)造公式 (P Q Q 真值表。真值表。591.4.2 等價(jià)公式等價(jià)公式給定給定n個(gè)個(gè) 命題命題變?cè)冊(cè)? 按合式按合式公式的形公式的形成規(guī)則可以形成無(wú)數(shù)多個(gè)命題公式成規(guī)則可以形成無(wú)數(shù)多個(gè)命題公式, 但這但這些無(wú)窮盡的些無(wú)窮盡的命題公式中，有些具有相同的命題公式中，有些具有相同的真值表。真值表。考慮：考慮：由由n個(gè)命題變?cè)苌蓚€(gè)命題變?cè)苌? 種真值種真值(表表)不同的命題公式？不同的命題公式？) 1( n

44、601.4.2 等價(jià)公式等價(jià)公式定義定義1.4.3: 給定兩個(gè)命題公式給定兩個(gè)命題公式A和和B,設(shè)設(shè)P1 , P2 ,Pn為為出現(xiàn)于出現(xiàn)于A和和B中的所有原子變?cè)械乃性幼冊(cè)?若給若給P1 , P2 ,Pn任任一組真值指派一組真值指派, A和和B的真值都相同的真值都相同,則稱(chēng)則稱(chēng)A和和B是等價(jià)是等價(jià)的或邏輯相等的或邏輯相等.記作記作A B注注: (1) “ ”不是邏輯聯(lián)結(jié)詞不是邏輯聯(lián)結(jié)詞.(2)命題公式之間的邏輯相等關(guān)系具有命題公式之間的邏輯相等關(guān)系具有： 自反性：自反性：A A ；對(duì)稱(chēng)性：若；對(duì)稱(chēng)性：若A B，則，則B A； 傳遞性：若傳遞性：若A B且且B C，則，則A C。61 證明

45、公式等價(jià)的方法：證明公式等價(jià)的方法： 1. 真值表法真值表法 2. 等值演算法等值演算法v1. 真值表法真值表法 例例1. (P1. (P Q) Q) (P(P Q) Q) 見(jiàn)真值表例題見(jiàn)真值表例題1.1. 例例2. 2. 證明證明: P: PQ Q (PQ)(PQ) (QP)(QP)P PQ QP PQ QQPQPPQPQ (PQ)(PQ) (QP)(QP)0 00 00 01 11 10 01 11 162 證明公式等價(jià)的方法：證明公式等價(jià)的方法： 1. 真值表法真值表法 2. 等值演算法等值演算法v1. 真值表法真值表法 例例1. (P1. (P Q) Q) (P(P Q) Q) 見(jiàn)真值

46、表例題見(jiàn)真值表例題1.1. 例例2. 2. 證明證明: P: PQ Q (PQ)(PQ) (QP)(QP)P PQ QP PQ QQPQPPQPQ (PQ)(PQ) (QP)(QP)0 00 01 11 11 11 10 01 10 00 01 10 01 10 00 01 10 00 01 11 11 11 11 11 163例例3：判斷公式：判斷公式 P(QR)、(PQ)R是否等價(jià)。是否等價(jià)。P Q RP QQ R P (Q R) (P Q R0000111001011101000110110111100011110101111101000111111164 由真值表可知，兩個(gè)公式為等價(jià)式

47、。由真值表可知，兩個(gè)公式為等價(jià)式。 2、等值演算法、等值演算法(Equivalent Caculation)（利用（利用P15表表1-4.8) 重要的等價(jià)式重要的等價(jià)式(補(bǔ)充補(bǔ)充): 11. 蘊(yùn)涵等值式蘊(yùn)涵等值式: : P PQ Q P P Q Q 12. 等價(jià)等價(jià)等值式等值式: : P PQ Q (PQ)(PQ) (QP)(QP) 13. 假言易位假言易位: P PQ Q Q Q PP 14. 等價(jià)否定等價(jià)否定等值式等值式: : P PQ Q PPQ Q 15. 歸謬論歸謬論: (P PQ Q ) ( ( P P Q)Q) P P 65 其中其中P, Q, R等代表任意命題公式等代表任意命題

48、公式. 這樣上面的每一這樣上面的每一個(gè)公式都是一個(gè)模式個(gè)公式都是一個(gè)模式, 它可以代表無(wú)數(shù)多個(gè)同類(lèi)它可以代表無(wú)數(shù)多個(gè)同類(lèi)型的命題公式型的命題公式. 例如例如, P P PPT T 中中, , 用用(P(P Q)Q)置置換換P,P,則得則得 (P(P Q)Q) (P(P Q)Q)T ,T ,用用P P置換置換P,P,則則得得 (P(P) ) (P(P) )T T 。等值演算中使用的一條重要規(guī)則：等值演算中使用的一條重要規(guī)則：置換規(guī)則。置換規(guī)則。 定義定義1.4.4(1.4.4(子公式子公式) )：如果如果X X是是wffwff A A的的一部分一部分, ,且且X X本身也是本身也是wffwff，

49、則稱(chēng)，則稱(chēng)X X是是A A的的子公式。例如子公式。例如, P, P (P(P Q)Q)為為Q Q (P P (P(P Q)Q)的子公式。的子公式。66定理定理1.4.1(置換定理置換定理Axiom of replacement)設(shè)設(shè)X X是是wffwff A A的子的子wffwff，若，若X XY Y，則若將，則若將A A中的中的X X用用Y Y來(lái)置換，來(lái)置換，所得公式所得公式B B與與A A等價(jià)，即等價(jià)，即A AB B。證：因?yàn)閷?duì)變?cè)娜我恢概勺C：因?yàn)閷?duì)變?cè)娜我恢概?X,X與與Y Y真值相同，所以真值相同，所以Y Y 取代取代X X后，公式后，公式B B與公式與公式A A對(duì)變?cè)娜我恢概烧?/p>

50、對(duì)變?cè)娜我恢概烧嬷狄蚕嗤狄蚕嗤? ,所以所以A AB B。注注: : 滿(mǎn)足滿(mǎn)足定理定理1.4.1的條件的置換稱(chēng)為等價(jià)置換的條件的置換稱(chēng)為等價(jià)置換(或等或等價(jià)代換價(jià)代換).定義定義1.4.5(1.4.5(等值演算等值演算) )：根據(jù)已知的等價(jià)公式根據(jù)已知的等價(jià)公式, ,推演推演出另外一些等價(jià)公式的過(guò)程稱(chēng)為出另外一些等價(jià)公式的過(guò)程稱(chēng)為等值演算等值演算. 67例例1 1： 證明證明 QQ（P P （P P Q Q）QPQP 證證: Q: Q（P P （P P Q Q）QPQP P( P(吸收律吸收律) ) 例例2 2： 證明證明 P P QQ Q Q P P Q Q證：證： (P(P Q)Q)

51、Q Q(P(P Q)Q) ( (QQ Q)Q)( (P P Q)Q) T TP P Q Q例例3 3：證明（：證明（PQPQ）（Q Q P P） P P Q Q R R證：（證：（PQPQ）（Q Q P P） （P P Q Q）（Q Q R R） （P P Q Q） （Q Q R R） （P P QQ） （Q Q R R） （P P Q Q R R） （Q Q Q Q R R） P Q R 68例例4：驗(yàn)證驗(yàn)證P(QR) (P Q) R證證: 右右 (P Q) R P Q R P ( Q R) P (Q R) P (Q R)練：練：1.(P Q) (P R) P (Q R) 2.(P Q) (

52、 P Q) (P Q) (P Q) 69v等值演算等值演算在計(jì)算機(jī)硬件設(shè)計(jì)中在計(jì)算機(jī)硬件設(shè)計(jì)中,在開(kāi)關(guān)理論和電子元在開(kāi)關(guān)理論和電子元器件中都占有重要地位器件中都占有重要地位.v小結(jié)小結(jié): 本節(jié)介紹了真值表、公式等價(jià)、等值演算和等本節(jié)介紹了真值表、公式等價(jià)、等值演算和等價(jià)置換等概念，給出了常用的重要等價(jià)公式（價(jià)置換等概念，給出了常用的重要等價(jià)公式（24個(gè)）。個(gè)）。重點(diǎn)掌握用真值表法驗(yàn)證公式的等價(jià)性和等值演算法重點(diǎn)掌握用真值表法驗(yàn)證公式的等價(jià)性和等值演算法推演兩個(gè)公式等價(jià)。推演兩個(gè)公式等價(jià)。作業(yè)：作業(yè)：P17 1 c,e, 4 a,c, 7d,e, 8.預(yù)習(xí)預(yù)習(xí): 1.5, 1.6思考題：思考題：

53、970張捷71蘊(yùn)含蘊(yùn)含1.5.1 命題公式的分類(lèi)命題公式的分類(lèi)1.5.2 重言式重言式(與矛盾式與矛盾式 (contradictory)的性質(zhì)的性質(zhì)1.5.3 721.5.1 命題公式的分類(lèi)命題公式的分類(lèi) 復(fù)合命題復(fù)合命題(compound propositions)定義定義1.5.1 設(shè)設(shè)A為任一命題公式，為任一命題公式，（1）若）若A在其各種賦值下的取值均為真，則稱(chēng)在其各種賦值下的取值均為真，則稱(chēng)A是是重言式重言式或或永真式永真式, 記為記為T(mén)或或1。（2）若）若A在其各種賦值下的取值均為假，則稱(chēng)在其各種賦值下的取值均為假，則稱(chēng)A是是矛盾式矛盾式或或永假式永假式, 記為記為F或或0。（3）

54、若）若A不是矛盾式則稱(chēng)不是矛盾式則稱(chēng)A為為可滿(mǎn)足式可滿(mǎn)足式(satisfiable)。注注: 由定義可知由定義可知,重言式一定是可滿(mǎn)足式重言式一定是可滿(mǎn)足式,反之不真反之不真. )()()log(esatisfiablorycontradictytauto可滿(mǎn)足式矛盾式重言式或永真式73 判別命題公式的類(lèi)型有兩種方法判別命題公式的類(lèi)型有兩種方法: 真值表法和等值真值表法和等值演算法演算法. 等值演算法等值演算法是將所給命題公式通過(guò)等值演算化為最是將所給命題公式通過(guò)等值演算化為最簡(jiǎn)單的形式簡(jiǎn)單的形式, 然后再進(jìn)行判別然后再進(jìn)行判別.例例1.判別下列命題公式的類(lèi)型判別下列命題公式的類(lèi)型.(1).

55、Q(PQ)P) (重言式重言式)(2). (PP) (QQ)R (矛盾式矛盾式)(3). (P Q)P. (可滿(mǎn)足式可滿(mǎn)足式)741.5.2 重言式重言式(與矛盾式與矛盾式(contradictory)的性質(zhì)的性質(zhì)定理定理1.5.1:任何兩個(gè)重言式的合取或析取任何兩個(gè)重言式的合取或析取,仍然是一重言式仍然是一重言式.（由冪等律立得）（由冪等律立得） 證明證明:設(shè)設(shè)A和和B為兩個(gè)重言式為兩個(gè)重言式,則不論則不論A和和B的分量指派任何的分量指派任何真值真值,總有總有A為為T(mén),B為為T(mén),故故A B T,A T,A B B T T 定理定理1.5.2:1.5.2:一個(gè)重言式一個(gè)重言式( (矛盾式矛盾式

56、), ,對(duì)同一分量都用任何對(duì)同一分量都用任何合式公式置換合式公式置換, ,其結(jié)果仍為一重言式其結(jié)果仍為一重言式( (矛盾式矛盾式). . 證明證明: 由于由于重言式重言式( (矛盾式矛盾式)的真值與對(duì)變?cè)馁x值無(wú)關(guān)，的真值與對(duì)變?cè)馁x值無(wú)關(guān)，故對(duì)同一變?cè)匀魏喂蕦?duì)同一變?cè)匀魏魏鲜焦街脫Q后，重言式合式公式置換后，重言式( (矛盾式矛盾式)的真值仍永為的真值仍永為T(mén)（F）。）。75 定理定理1.5.3： A,B是兩個(gè)命題公式，是兩個(gè)命題公式，A B的的充要條件是充要條件是A B為重言式。為重言式。證明證明: : 若若A AB B為重言式，則為重言式，則A AB B永為永為T(mén) T，即，即A A，

57、B B的真的真 值表相同，所以值表相同，所以A AB B。 反之，反之，若若A A B B，則，則A A，B B真值表相同，真值表相同， 所以所以 A AB B永為永為T(mén) T，所以，所以A AB B為重言式。為重言式。1.5.3 定義定義1.5.2：當(dāng)且僅當(dāng)：當(dāng)且僅當(dāng)P Q是一個(gè)重言式時(shí)，是一個(gè)重言式時(shí)，我們稱(chēng)我們稱(chēng)“P蘊(yùn)含蘊(yùn)含Q”，并記作，并記作P Q.76 它們之間具有如下關(guān)系它們之間具有如下關(guān)系: PQ Q P 由由P21 表表1-5.1 QP P Q 可以得出可以得出 因此因此, 要證明要證明P Q有三種方法有三種方法: 1)1)真值表法真值表法: :即列出即列出PQ的的真值表真值表,

58、 ,觀(guān)察其是否為永真。觀(guān)察其是否為永真。 2)2)直接證法直接證法: :假定前件假定前件P P是真，推出后件是真，推出后件Q Q是真。是真。 3)3)間接證法間接證法: :假定后件是假，推出前件是假假定后件是假，推出前件是假, ,即證即證 Q P 。原命題原命題逆換式逆換式反換式反換式逆反式逆反式PQQP P Q Q P77例例: : 證明證明Q Q （PQPQ）P P1) 1) 法法1 1：真值表：真值表2) 2) 法法2 2：若：若 Q Q ( (PQ)PQ)為真，則為真，則 Q Q，PQPQ為真，為真， 所以所以Q Q為假，為假，P P為假，所以為假，所以P P為真。為真。3) 3) 法

59、法3 3：若：若P P為假，則為假，則P P為真，再分二種情況：為真，再分二種情況： 若若Q Q為真，則為真，則Q Q為假為假, ,從而從而Q Q （PQPQ） 為假為假. .若若Q Q為假，則為假，則PQPQ為假，則為假，則Q Q （PQPQ）為假）為假. .根據(jù)根據(jù) ，所以，所以 Q Q （PQPQ）P PP21 P21 表表1-5.21-5.2給出了給出了1414個(gè)個(gè)蘊(yùn)含式蘊(yùn)含式, 它們都可以用上述方法加它們都可以用上述方法加以推證以推證.78 等價(jià)式與蘊(yùn)含式的關(guān)系等價(jià)式與蘊(yùn)含式的關(guān)系: 定理定理1.5.4:1.5.4: 設(shè)設(shè)P,QP,Q為任意兩個(gè)命題公式為任意兩個(gè)命題公式,P,PQ Q

60、的的充要條件為充要條件為P PQ Q且且Q QP.P. 證：若證：若P PQ Q，則，則P PQ Q為永真式為永真式 因?yàn)橐驗(yàn)?P PQ Q （PQPQ） （QPQP） 所以所以 PQPQ，QPQP為永真式為永真式, ,從而從而 P PQ Q，Q QP.P. 反之，若反之，若P PQ Q，Q QP P，則，則PQPQ，QPQP為永真式為永真式, , 所以（所以（PQPQ） （QPQP）為永真式，）為永真式， 從而從而 P PQ Q為永真式，即為永真式，即P PQ.Q.79 蘊(yùn)含的性質(zhì)蘊(yùn)含的性質(zhì): 設(shè)設(shè)A A，B B，C C為任意為任意wffwff, ,1) 1) 若若A AB B，且，且A A