4-邏輯與證明

1、1,數(shù)理邏輯部分,邏輯學(xué)(1ogic)是研究人類推理規(guī)則（過(guò)程）的科學(xué)。邏輯學(xué)分為兩大流派：傳統(tǒng)邏輯（亞式邏輯）數(shù)理邏輯（符號(hào)邏輯）,2,傳統(tǒng)邏輯由亞里士多德創(chuàng)立（故稱亞式邏輯） ，它是從日常生活的經(jīng)驗(yàn)出發(fā)，訓(xùn)練我們?cè)谏钪腥绾问褂酶拍?，以及如何判斷和推理。其推理的主要?guī)則是定言三段論。數(shù)理邏輯(mathematical logic)則是近代由歐美人創(chuàng)立的，使用的都是抽象的數(shù)學(xué)符號(hào)和數(shù)學(xué)公式，也就是用數(shù)學(xué)的方法來(lái)研究邏輯，所以數(shù)

2、理邏輯又叫符號(hào)邏輯（symbolic Logic）。,3,邏輯研究的內(nèi)容： ——著重于推理過(guò)程是否正確； ——著重于語(yǔ)句之間的關(guān)系，而不是一個(gè)具體語(yǔ)句的內(nèi)容。例: 語(yǔ)句1: 所有的數(shù)學(xué)家都穿涼鞋。語(yǔ)句2: 任何一個(gè)穿涼鞋的人都是代數(shù)學(xué)家。語(yǔ)句3: 所有數(shù)學(xué)家都是代數(shù)學(xué)家。從技術(shù)上來(lái)說(shuō)， 邏輯并不幫助確定這些語(yǔ)句是否為真; 然而，如果前兩個(gè)語(yǔ)句為真， 邏輯可以保證語(yǔ)句3也為真。,4,傳統(tǒng)邏輯適用于日常生活中的推理；數(shù)理邏

3、輯則偏重演算，適用于計(jì)算機(jī)實(shí)現(xiàn)推理。數(shù)理邏輯是計(jì)算機(jī)軟件理論技術(shù)和硬件邏輯設(shè)計(jì)、人工智能等學(xué)科的重要理論基礎(chǔ)。程序＝算法＋數(shù)據(jù)算法＝邏輯＋控制本課程包含了數(shù)理邏輯的兩個(gè)基礎(chǔ)演算(命題演算和謂詞演算)，叫作邏輯代數(shù)。,5,第4章 邏輯與證明,6,4.1 命題邏輯,4.1.1命題的定義與運(yùn)算一、命題的概念 推理的構(gòu)成: 前提(一個(gè)或多個(gè)判斷句) ? 結(jié)論(一個(gè)或多個(gè)判斷句) 判斷句----

4、表達(dá)判斷的陳述句----是推理的基本單位。 表達(dá)判斷----有真假意義, 要么為真, 要么為假, 但不能兼而有之。 【定義】能判斷出真假的陳述句，稱為命題（proposition 或 statement）。,7,命題的真值：作為命題的陳述句所表達(dá)的判斷結(jié)果。真值只有兩種取值：真(true)或假(false)。 任何命題的真值都是唯一的。 真命題： 假命題：

5、 判斷給定句子是否為命題，一般分為兩步： 首先判斷它是否為陳述句，然后判斷它是否有唯一真值。,8,【例】 判斷下列句子是不是命題: 4是素?cái)?shù)（質(zhì)數(shù)）。 π是無(wú)理數(shù)。 x 大于 y。大于2的偶數(shù)等于兩個(gè)素?cái)?shù)之和(歌德巴赫猜想)。 火星上有生物。 你能幫助我嗎？請(qǐng)不要吸煙！ 這朵花真美麗啊！ 我正在說(shuō)假話。,?,?,?,?,?,?,?,?,?,9,解： 6)是疑問(wèn)句，7)是祈使句，8)

6、是感嘆句，因而這3句都不是命題。 3) 盡管是陳述句，但x,y表示變?cè)?，它們不是確定的對(duì)象（從而導(dǎo)致真值不惟一），所以不是命題。 9)是一個(gè)自相矛盾的病態(tài)語(yǔ)句----稱為悖論，我們不承認(rèn)此類語(yǔ)句為陳述句，因而9）不是命題。 1)、2)、4)、5)這4句是命題，其中第１)句是假命題；第２)句是真命題； 第4)句和第5)句雖然目前暫時(shí)無(wú)法判斷其真假, 但它們的真值是客觀存在的，而且是唯一的，將來(lái)總會(huì)找到它們的真

7、值。,10,二、原子命題和復(fù)合命題 【定義】不能再分解為更簡(jiǎn)單句子的命題叫原子命題（簡(jiǎn)單命題），否則稱為復(fù)合命題。 例：今天是星期一。 例：今天是星期一并且今天天晴。 原子命題中的“原子”取原子的“不可再分”之意, 它是最基本的命題, 相當(dāng)于自然語(yǔ)言的簡(jiǎn)單陳述句。,11,【例】 下面的命題由哪些原子命題組成: 1) 王斌貧窮但快樂(lè)。

8、2) 只要明天天氣好, 我就去春游。,12,三、 命題及真值的符號(hào)化1、用小寫(xiě)字母p, q, r, …或加下標(biāo)的小寫(xiě)字母pi, qi, ri, …表示命題。 【示例】 p: 4是素?cái)?shù)。 （句中的“：”讀作“表示”） q: 1+1=2 r: 火星上有生物。 2、用 T 或1表示真，用 F或0表示假。示例中 p 的真值為0，q 的真值為1，r的真值暫時(shí)還不知道。,13,四

9、、邏輯常量與命題變?cè)壿嫵Ａ浚}常元）---- 表示一個(gè)確定的、具體的原子命題的標(biāo)識(shí)符。邏輯常量有確定的真值, 其真值不是０就是１。,14,深入的討論還需要引進(jìn)命題變?cè)母拍睿好}變?cè)ㄟ壿嬜兞浚?---- 表示任意一個(gè)命題的標(biāo)識(shí)符，以“T、F”或“1、0”為取值范圍, 仍用小寫(xiě)字母表示。一個(gè)命題變?cè)舯荒硞€(gè)確定的命題替代, 就具有確定的真值。（參考：常量與變量）,15,注：1）命題變?cè)皇敲}。（參：整型變量不

10、 是整數(shù)。） 2） p表示命題常元還是命題變?cè)捎缮稀?下文來(lái)確定。,16,4.1.2 邏輯聯(lián)結(jié)詞 由簡(jiǎn)單命題通過(guò) “非”、“并且”、“或者”、“如果…那么…”等聯(lián)結(jié)詞組合可產(chǎn)生新命題。 但在自然語(yǔ)言中出現(xiàn)的聯(lián)結(jié)詞有時(shí)有二義性。因而在數(shù)理邏輯中，必須給出聯(lián)結(jié)詞的嚴(yán)格定義，并且將它們形式化。,17,設(shè)p是一個(gè)命題, 復(fù)合命題“非p” 稱為p的否定式, 記作┐p。 ┐稱作否定聯(lián)結(jié)詞。,“┐”

11、的讀法：not （英） 非、…的否定（中）,1. 非,18,┐p的真值定義為： ┐p為真 iff p為假。（符號(hào)iff表示“當(dāng)且僅當(dāng)”） 命題┐p的取值（和p的關(guān)系）可以用表4.3表示。該 表稱為┐p的真值表。,表4.3 ┐p 的真值表,19,?常見(jiàn)錯(cuò)誤：命題的表述不符合日常規(guī)范。 例： p：3是偶數(shù)，則┐p表示的命題是什么？ 常見(jiàn)的錯(cuò)誤答案是：“不是

12、3是偶數(shù)”。 正確的答案是：“3不是偶數(shù)”。,20,?常見(jiàn)錯(cuò)誤：部分否定與全部否定。 例： p：所有的蘋(píng)果都是紅的，則┐p表示的命題是什么？ 常見(jiàn)的錯(cuò)誤答案是：“所有的蘋(píng)果都不是紅的”。 正確的答案是：“并非所有的蘋(píng)果都是紅的”。,21,設(shè)p, q是兩個(gè)命題, 復(fù)合命題“p并且q”稱為p與q的合取式，記做 p∧q， ∧ 稱為合取聯(lián)結(jié)詞。,“∧”的讀法：and （英）

13、合取、且（中）,2. 與（且）,22,表4.1 p∧q 真值表,p∧q的真值定義為： p∧q為真 iff p, q都為真。 復(fù)合命題p∧q 的取值，即p∧q的真值表如表4.1所示。,23,可以抽象成合取詞∧的自然語(yǔ)言的連接詞有:“并且”“和”“及”“既…又…”“不但…而且…”“雖然…但是…” “一面…一面…”,24,【例】 將下列命題符號(hào)化。(1)

14、吳穎不僅用功而且聰明。(2)吳穎雖然聰明但不用功，這不是真的。(3)張輝與王麗都是三好學(xué)生。(4)張輝與王麗是同學(xué)。,解 首先將原子命題符號(hào)化： p: 吳穎用功 q:吳穎聰明 r: 張輝是三好學(xué)生 s:王麗是三好學(xué)生 t: 張輝與王麗是同學(xué),25,則符號(hào)化的命題如下：(1) p∧q (2) ┐ ( ┐ p∧ q )(3) r∧s(4) t,26,關(guān)于命題

15、符號(hào)化需要注意以下兩點(diǎn)： （1）p、q、r等符號(hào)用來(lái)代表肯定形式的命題，而不是否定形式的命題。如下面的符號(hào)化不合適（不是原子命題）: 命題：今天不是星期二并且今天天晴。 設(shè) p：今天不是星期二 q：今天天晴 則命題符號(hào)化為：p∧q。 （2）p、q、r等符號(hào)不能用來(lái)代表復(fù)合命題（上例其實(shí)也是這種

16、情況），因?yàn)檫@樣會(huì)掩蓋命題的結(jié)構(gòu)，不利于推理。,27,設(shè)p, q是兩個(gè)命題, 復(fù)合命題“p或q”稱為p與q的析取式，記做 p∨q， ∨稱為析取聯(lián)結(jié)詞。,“ ∨”的讀法：or （英） 析取、或（中）,3. 或,28,表4.2 p∨q 真值表,p∨q的真值定義為： p∨q為真 iff p, q至少有一個(gè)為真 復(fù)合命題p∨q的取值，即p∨q的真值表如表4.2。,29,析取詞∨是自然語(yǔ)言中的連接詞“或者”

17、等的邏輯抽象。但自然語(yǔ)言中的“或者”具有二義性： (1) 相容或(可兼或)：用它聯(lián)結(jié)的命題具有相容性：命題可以同時(shí)為真，如：張三會(huì)講英語(yǔ)或日語(yǔ)。 (2) 排斥或(不可兼或)：用它聯(lián)結(jié)的命題具有排斥性：命題不能同時(shí)為真，如：(1)這張桌子是紅色或藍(lán)色。 (2)派小王或小李中的一人去開(kāi)會(huì)?！疟硎鞠嗳莼颉?30,注： 在使用析取聯(lián)結(jié)詞時(shí)，首先應(yīng)分析表達(dá)的是可兼或還是不可兼或。若是可兼或，以及

18、p, q不能同時(shí)為真的不可兼或①，均可直接符號(hào)化為p∨q的形式。如果是不可兼或②，并且p與q可同時(shí)為真，就應(yīng)符號(hào)化為 (p∧┐q)∨(┐p∧q) 的形式。,31,【例】 將下列命題符號(hào)化。張三選修了英語(yǔ)課或者微積分課。今晚張三要么只看書(shū)要么只聽(tīng)音樂(lè)。a>0或a=0。,32,分析： (1) 是“可兼或”（為什么？），可用析取式表示：p∨q 其中p:張三選修了英語(yǔ)課，

19、q:張三選修了微積分課(2) 是“不可兼或②”： (p∧┐q)∨(┐p∧q) (3) 是“不可兼或①”： p∨q,33,設(shè)p, q是兩個(gè)命題, 復(fù)合命題“如果p，則q”稱為p與q的蘊(yùn)涵式（條件式），記做 p → q， → 稱為蘊(yùn)涵聯(lián)結(jié)詞， p稱為前件， q稱為后件。,“→ ”的讀法：implies, if…then… （英） 蘊(yùn)涵、如果…則… （中）,4. 條件,34,表4.4 p→q真值表,p→q的真值定義為：

20、 p→q為假 iff p為真而q為假 復(fù)合命題p→q的取值如表4.4所示。,35,蘊(yùn)涵詞→是自然語(yǔ)言中的連接詞“如果……, 則……”“只要……, 就……”“因?yàn)椤? 所以……” “只有……, 才……”“除非……, 否則……”等的邏輯抽象。 p→q表明的邏輯關(guān)系是：p是q的充分條件，q是p的必要條件。,36,日常生活中的“如果p, 則q”是聯(lián)系兩個(gè)有邏輯關(guān)系的語(yǔ)句p和q。 而在數(shù)理邏輯

21、中，前件p和后件q可以沒(méi)有任何邏輯聯(lián)系，蘊(yùn)涵式p→q的真值僅由p, q的真值惟一確定。,例：如果1+1=2，那么雪是白的。,37,在數(shù)學(xué)和其他自然科學(xué)中， “如果p, 則q”往往表達(dá)前件p為真，后件也為真的推理關(guān)系；而在數(shù)理邏輯中，當(dāng)前件p為假，不管后件是真是假，規(guī)定 p→q都是真 (∵復(fù)合命題p →q應(yīng)有真值)。 例：校長(zhǎng)宣布： 如果氣溫超過(guò)38℃，則全校停課。,38,?關(guān)于“只有……, 才……”和“除非……, 否

22、則……”的符號(hào)化：(1) 只有肚子餓了，我才去麥當(dāng)勞。 其意思相當(dāng)于： 如果我去麥當(dāng)勞，則我肚子餓了。 設(shè) p：我肚子餓了 q：我去麥當(dāng)勞 則原命題可符號(hào)化為：q → p 。,39,(2) 除非下雨，否則我就騎自行車上班。 其意思相當(dāng)于： 如果不下雨，我就騎自行車上班。 設(shè) p：天下雨 q：我騎自行車上班 則原

23、命題可符號(hào)化為： ┐ p → q 。,40,翻譯時(shí), 為了減少圓括號(hào), 我們對(duì)4個(gè)命題聯(lián)結(jié)詞的強(qiáng)弱次序規(guī)定為 ┐、 ∧、 ∨、→?聯(lián)結(jié)詞小結(jié)： 聯(lián)結(jié)詞類似于代數(shù)中的＋、－、×、/，只不過(guò)＋、－、×、/作用的是數(shù)（實(shí)數(shù)，甚至復(fù)數(shù)），而聯(lián)結(jié)詞作用的是命題。也就是說(shuō)，聯(lián)結(jié)詞提供了命題之間的一種運(yùn)算。在本質(zhì)上，聯(lián)結(jié)詞用于反映復(fù)合命題的內(nèi)部邏輯結(jié)構(gòu)。,41,【練習(xí)

24、】下列命題是否是含有蘊(yùn)涵的復(fù)合命題? 若是, 指出其前件和后件。a) 只要你發(fā)給我一個(gè)電子郵件，我就會(huì)把地址寄給你。b) 暖天持續(xù)一周蘋(píng)果樹(shù)就開(kāi)花。c) 活塞隊(duì)贏得冠軍就意味著他們打敗了湖人隊(duì)。d) 必須走8英里才能到朗斯峰的頂峰。e) 只有你購(gòu)買(mǎi)的Mp4機(jī)不超過(guò)90天，你的保修單才有效。f) 如果你駕車超過(guò)400英里，就需要買(mǎi)汽油了。,42,g) 你獲得這一職位表明你有最好的信譽(yù)。h) 要成為美國(guó)公民，只要你生在美國(guó)就

25、行了。i) 有風(fēng)暴時(shí)沙灘受侵蝕。j) 要在服務(wù)器登錄必須有一個(gè)有效的口令。,43,4.1.3 邏輯等價(jià)一、命題公式的真值表 1、命題公式的賦值 命題公式的真值情況取決于其所含命題變?cè)恼嬷怠?【定義】 設(shè)p1,p2,…,pn是出現(xiàn)在公式A中的所有命題變?cè)?，給p1,p2,…,pn各指定一個(gè)真值，稱為對(duì)公式A的一個(gè)真值指派（也稱解釋）。,44,由定義可知, 具有n個(gè)命題變?cè)墓接?n組不同的真值指派。

26、 在命題公式中，將各分量的所有可能的指派以及由此確定的命題公式的真值匯列成表，稱為命題公式的真值表。,45,p∧q真值表,例：,46,2、真值表的構(gòu)造【示例】 求公式(p∧q)∧┐p的真值表。 解 分以下３步求得: 1) 寫(xiě)出公式p∧q的真值表; 2) 寫(xiě)出公式┐p的真值表; 3) 根據(jù)1)和2), 寫(xiě)出公式(p∧q)∧┐p的真值表。 為清楚起見(jiàn), 我們將這３步列在一個(gè)表內(nèi)

27、, 見(jiàn)下表。,47,(p∧q)∧┐p的真值表,48,構(gòu)造真值表注意事項(xiàng)：命題變?cè)聪聵?biāo)進(jìn)行排列，若無(wú)下標(biāo)，則按字典順序進(jìn)行排列；命題變?cè)娜≈蛋炊M(jìn)制編碼從小到大（或從大到?。┡帕?，這樣容易做到“不重不漏”；根據(jù)經(jīng)驗(yàn)，最好是逐列求值，而不是逐行求值，這樣不容易出錯(cuò)；對(duì)于一個(gè)具體的命題公式，其真值表究竟分成幾列，要根據(jù)自己的熟練程度來(lái)定。,49,【示例】 求 (┐ p∧q) → ┐r的真值表。,50,二、邏輯等價(jià)的概念,若命題公式

28、A和B在任何真值指派下的真值總是相同的，則稱這兩個(gè)命題公式A和B是邏輯等價(jià) (邏輯等值)的，記作A = B 。,51,對(duì)兩個(gè)含有相同命題變?cè)墓紸和B, 當(dāng)A=B時(shí), 公式A和B的真值表完全相同，即在任何賦值情形下，A和B的真值相同（?稱為邏輯等值）, 而反過(guò)來(lái)也成立。 注：邏輯等值具有①自反性；②對(duì)稱性；③傳遞性。 （?又稱為邏輯等價(jià)）,52,我們常常利用真值表來(lái)判斷兩個(gè)命題公式是否邏輯等價(jià)。 【例】證明p→q = ┐p∨q

29、,從真值表可以看出： p→q = ┐p∨q,53,【例4.1.1】證明p→q = ┐q→┐p證明：寫(xiě)出它們的真值表,從真值表可以看出： p→q = ┐q→┐p,54,【例4.1.2】證明 ┐(p∨q) = ┐p∧┐q證明：寫(xiě)出它們的真值表,從真值表可以看出： ┐(p∨q) = ┐p∧┐q,55,【例4.1.3】證明 ┐(p∧q) = ┐p∨┐q證明：寫(xiě)出它們的真值表,從真值表可以看出： ┐(p∧q) = ┐p∨┐q,56,【例】

30、判斷下面兩組公式是否等值： (1) p→ (q→ r) 與 (p∧q) → r (2) ( p→ q)→ r 與 (p∧q) → r 解：,從真值表可以看出： p→ (q→ r) = (p∧q) → r 但：( p→ q)→ r ? (p∧q) → r,57,4.2 謂詞邏輯,前面學(xué)習(xí)的命題邏輯不能描述數(shù)學(xué)和計(jì)算機(jī)科學(xué)中的多數(shù)命題。例

31、如，考慮句子P：n ? 0常見(jiàn)于數(shù)學(xué)斷言和計(jì)算機(jī)程序，但句子P不是命題（ n不是確定的對(duì)象）。由于數(shù)學(xué)和計(jì)算機(jī)科學(xué)中的多數(shù)句子使用變?cè)?，所以必須擴(kuò)展邏輯系統(tǒng)，使之包括這樣的句子。,58,為了克服命題邏輯的局限性，弗雷格（Frege）的天才著作《概念演算》，提出了謂詞演算方法。 處理思路：將原子命題進(jìn)一步分解，分析出個(gè)體詞、謂詞、量詞，以期表達(dá)命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系。,59,一、個(gè)體詞與謂詞 在謂

32、詞邏輯中, 我們首先對(duì)原子命題加以分解, 引入個(gè)體和謂詞的概念。 1、概念　 原子命題的構(gòu)成： 1) 個(gè)體(object)－－客體，可以是一個(gè)具體的事物，也可以是一個(gè)抽象的概念 ，在句中作主語(yǔ)或賓語(yǔ)。 2) 謂詞(predicate)－－謂語(yǔ)部分，用以刻畫(huà)客體的性質(zhì)或客體之間的關(guān)系。,60,例如：　　1) 張三是大學(xué)生?！　?) 小李比小王高2cm。 “張三”、“小李”、“小王”是個(gè)體

33、詞；　“……是大學(xué)生”、“……比……高2cm”是謂詞。,61,2、個(gè)體與謂詞的符號(hào)化表示　　1）個(gè)體： ①個(gè)體常元－－具體或特定的客體的個(gè)體詞，常用小寫(xiě)字母a, b, c,……等表示。　?、趥€(gè)體變?cè)橄蠡蚍褐傅膫€(gè)體詞, 常用小寫(xiě)字母x, y, z,……等表示。,62,個(gè)體變量的取值范圍叫個(gè)體域(論域)。個(gè)體域可以是有限集, 也可以是無(wú)限集。 有一個(gè)特殊的個(gè)體域，它是由宇宙間一切事物構(gòu)成的，稱為全總

34、個(gè)體域。 　　2）謂詞：用小寫(xiě)字母p, q, r 等表示，如　　p(b)：個(gè)體b具有性質(zhì)A ，如“b是整數(shù)”。　　q(a,b)：個(gè)體a與b具有關(guān)系B ，如“a大于b”。,63,【示例】考慮下面句子，指出其中的個(gè)體詞與謂詞： (1) π是無(wú)理數(shù)。 (2) 小王與小李同歲。 (3) 南京位于武漢和上海之間。,64,一元謂詞：只與一個(gè)個(gè)體相聯(lián)系的謂詞, 稱之為一元謂詞，記為p( )或p(x) 。 一元謂詞刻畫(huà)了一個(gè)個(gè)體的性質(zhì)。

35、 二元謂詞：與兩個(gè)個(gè)體相聯(lián)系的謂詞，稱之為二元謂詞，記為p( , )或p(x,y) 。二元謂詞刻畫(huà)了兩個(gè)個(gè)體的關(guān)系。 ...... n 元謂詞：與n個(gè)個(gè)體相聯(lián)系的謂詞叫n元謂詞,記為p(x1,x2,…,xn) 。它刻畫(huà)了n 個(gè)個(gè)體間的關(guān)系。,65,注意：在n元謂詞p(x1, x2, …, xn)和n個(gè)個(gè)體a1, a2, …, an所表示的命題p(a1, a2, …, an)中,

36、要注意n個(gè)個(gè)體a1, a2, …, an的排列次序, 一般是不能隨意調(diào)換的。,【例】設(shè) r：……是……的算術(shù)平方根, a：５, b：25, 則有 r(a,b)：5是25的算術(shù)平方根。（真命題） r(b,a)：25是5的算術(shù)平方根。 （假命題）,66,3、謂詞填式 【示例】設(shè) p(x)：x是偶數(shù)， a：2, 則： p(a) 表示命題“2是偶數(shù)”。 因?yàn)?/p>

37、x是個(gè)體變?cè)? p(x)不能判斷真假，所以不是命題。 但是一旦x用具體確定的個(gè)體, 如2替換后就得到一個(gè)命題, 所以我們稱p(a)是謂詞填式，謂詞填式是命題（有真值）。,67,【例】考慮下面的謂詞填式： (1) 令p(x) 表示“x大于3”， p(4) 和p(2) 的值是什么？ (2)令q(x,y) 表示“x=y+3”， q(1,2) 和q(3,0) 的值是什么？ (3)令r(x,y,z) 表示“x+y=z”， r(1

38、,2,3) 和r(0,0,1) 的值是什么？,68,【例】考慮C語(yǔ)句 if x >0 x=x+1; 當(dāng)程序運(yùn)行到這一條語(yǔ)句時(shí)，變量x的值即被代入謂詞p(x): x >0，也就是代入“x>0”。如果對(duì)x的這一值p(x)為真，即執(zhí)行賦值語(yǔ)句x=x+1;于是x的值增加1。如果對(duì)x的這一值p(x)為假，則不執(zhí)行賦值語(yǔ)句，所以x的值不改變。,69,二

39、、量詞－－表示數(shù)量的詞 有了個(gè)體、謂詞、命題函數(shù)的概念以后, 對(duì)于有些命題，還是不能正確地符號(hào)化。以下面的三段論斷言為例: r: 凡人必死。 s: 蘇格拉底是人。 t: 蘇格拉底必死。,70,令 p(x): x是人。 q(x): x必死。 a: 蘇格拉底。 則s可以表示為

40、命題p(a), t可以表示為命題q(a)。然而, r卻不能表示為p(x)→q(x)。 因?yàn)? “凡人要死”是一個(gè)真的命題, 而p(x)→q(x)是由謂詞p(x)和q(x)以及命題聯(lián)結(jié)詞“→”構(gòu)成的更復(fù)雜的謂詞, 它不是一個(gè)謂詞填式，所以不是命題。 這說(shuō)明僅用個(gè)體和謂詞等概念還不能確切地表示命題 r。,r: 凡人必死。 s: 蘇格拉底是人。 t: 蘇格拉底必死。,71,1. 全稱量詞(universal quantification)

41、 日常生活中常用的“一切”、“凡”、“所有的”、“任意的”、“每一個(gè)”等，對(duì)應(yīng)數(shù)理邏輯中的全稱量詞? 。?x表示“對(duì)個(gè)體域中所有的x”、 “對(duì)個(gè)體域任意一個(gè)x”、 “對(duì)個(gè)體域每一個(gè)x”。,72,2. 存在量詞(existential quantification) 日常生活中常用的 “至少有一個(gè)”、“存在”、“有一個(gè)”、“有的”等，對(duì)應(yīng)數(shù)理邏輯中的存在量詞? 。 符號(hào)?x表示“對(duì)個(gè)體域中某一個(gè)x”、“

42、個(gè)體域中至少存在一個(gè)x”、 “個(gè)體域中存在某一個(gè)x”等。,73,【例 】在不同的個(gè)體域限制條件下，將下面命題符號(hào)化。凡人都要死。 有的人用左手寫(xiě)字。其中: (a) 個(gè)體域D1為人類集合 (b) 個(gè)體域D2為全總個(gè)體域,74,解 令 p(x): x是人； q(x): x要死； r(x): x用左手寫(xiě)字。,(a) 個(gè)體域D1為人類集合 ，則 (1) 可以符號(hào)

43、化為： x q(x) (2) 可以符合化為: x r(x),(b) 個(gè)體域D2為全總個(gè)體域 ，則 (1) 可以符號(hào)化為： x (p(x)→q(x)) (2) 可以符合化為: x (p(x)∧r(x)),謂詞p(x)描述了個(gè)體域中一個(gè)特定的個(gè)體域，這種謂詞稱為特性謂詞,(1)凡人都要死。 (2)有的人用左手寫(xiě)字。,75,比較p(x)→q(x)和?x(p(x) → q(x) )可知

44、, 前者僅僅是個(gè)謂詞, 其中x是個(gè)體變?cè)? 它可以取個(gè)體域中的任何個(gè)體, 而后者是一個(gè)真的命題, 其中的 x 不再起變?cè)淖饔? 它被全稱量詞?x限制住了。 該例說(shuō)明, 對(duì)不同的個(gè)體域, 同一命題可能有不同形式的謂詞公式, 這對(duì)我們討論問(wèn)題是很不方便的。一般沒(méi)有特別說(shuō)明，論域采用全總個(gè)體域。,76,【示例】 把下面命題符號(hào)化: 1) 至少有一個(gè)人不死。 解 設(shè) p(x): x是人； q(x)

45、: x要死。 則原命題可以表示為?x(p(x)∧┐q(x)) 2) 所有的蘋(píng)果都是紅的。 解 設(shè) p(x): x是蘋(píng)果。 r(x): x是紅的。 則原命題可以表示為?x(p(x)→r(x)),由前例可看出，特性謂詞與全稱量詞? 結(jié)合使用時(shí)，要用→；特性謂詞與存在量詞?結(jié)合使用時(shí)，要用∧。,77,【練】 將下列命題符合化，并討論真值。所有人都長(zhǎng)著黑頭發(fā)。有的人登上過(guò)月球。沒(méi)有人登上木星。在美國(guó)留學(xué)的學(xué)生未必都是亞洲人

46、。其中: (a) 個(gè)體域D1為人類集合 (b) 個(gè)體域D2為全總個(gè)體域,78,【示例】 將下列謂詞公式譯為自然語(yǔ)句并判斷是不是命題: 1) ?x(p(x)→q(x)) ，其中 p(x): x是人。 q(x): x犯錯(cuò)誤。 解: 該謂詞公式可以譯為“對(duì)于所有的x, 如果x是人, 則x要犯錯(cuò)誤”，即為命題“人都要

47、犯錯(cuò)誤”。,79,2) ?x(p(x)∧q(x))，其中 p(x): x是孩子。 q(x): x是天才。 解:該謂詞公式可以譯為“存在一些x, x是孩子且x是天才”，即為命題“有些孩子是神童”。,80,3)?x(p(x)∧q(x))∧┐(?x(p(x)→q(x))) ，其中 p(x)

48、: x是人。 q(x): x聰明。 解：該謂詞公式可以譯為“有些人聰明, 但不是所有的人都聰明?！?81,【例】將下列命題符合化。兔子比烏龜跑得快。有的兔子比所有的烏龜跑得快。并不是所有的兔子都比烏龜跑得快。解: p(x): x是兔子。 q(x): x是烏龜。 r(x,y): x比y跑得快。(1) ?x?y(p(x)?q(y)

49、→r(x,y))(2) ?x(p(x)??y(q(y)→r(x,y))) (3)??x?y(p(x)?q(y)→r(x,y))或?x?y(p(x)?q(y)??r(x,y)),82,【例】 D＝{1，2，3}，p(x)：x是奇數(shù)，則 ?xp(x) = p(1)∧p(2)∧p(3) = 0 ?xp(x) = p(1)∨p(2)∨p(3) = 1,補(bǔ)充：量詞消去等值式： 若個(gè)體域D＝｛a1, a

50、2, …, an｝, 則有: ?xp(x) = p(a1)∧p(a2) ∧…∧p(an)  ?xp(x) = p(a1)∨p(a2) ∨…∨p(an),83,【例】 設(shè)個(gè)體域Ｄ={-2, 3, 6}，謂詞p(x): x5求下列謂詞公式的真值: 1) ?x (p(x)∧q(x))2) ?x (p(x)∨q(x)),84,解：個(gè)體域Ｄ={-2,3,6}，謂詞p(x): x51) ? x(p(x)∧q(x))

51、=(p(-2)∧q(-2)) ∧(p(3)∧q(3)) ∧(p(6)∧q(6))=(1∧0)) ∧(1∧0) ∧(0∧1)=02) ? x(p(x) ∨q(x))=(p(-2) ∨q(-2)) ∨(p(3) ∨q(3)) ∨(p(6) ∨q(6))=(1∨0)) ∨(1∨0) ∨(0∨1)=1,85,【練】 將下列命題符號(hào)化: 1) 金子是閃光的, 但閃光的并不一定都是金子。 2) 所有運(yùn)動(dòng)員都?xì)J佩某些教練員。3

52、) 有些大學(xué)生不欽佩運(yùn)動(dòng)員。,86,4.4 推理與證明,在人類的思維活動(dòng)中存在大量邏輯推理, 即從一些已知的條件（即前提）推出新的命題（即結(jié)論）。 在這些推理過(guò)程中, 只有在假設(shè)前提為真, 而且從前提得出結(jié)論的推理過(guò)程又是依據(jù)了某些公認(rèn)的推理規(guī)則時(shí), 我們才承認(rèn)這樣得到的結(jié)論是真的、 正確的。,87,4.4.1 等式推理 等式推理是建立在命題邏輯中的一種邏輯推理形式化系統(tǒng)。它由兩部分組成：（1）基本等式－

53、－基本邏輯等價(jià)式 （2）推理規(guī)則 推理過(guò)程就是應(yīng)用基本等式與推理規(guī)則，對(duì)一個(gè)命題公式逐步推導(dǎo)，最后得到預(yù)期的新的公式作為結(jié)論。,88,1. 基本邏輯等價(jià)式 人們已經(jīng)驗(yàn)證一組基本而又重要的邏輯等價(jià)式，以它們?yōu)榛A(chǔ)可進(jìn)行公式之間的演算。第1組：結(jié)合律 （1） (p∨q)∨r = p∨(q∨r) （2） (p∧q)∧r = p∧(q∧r)第2組：交換率

54、（3） p∨q = q∨p （4） p∧q = q∧p,89,第3組： 分配律 （5） p∧(q∨r) = (p∧q)∨(p∧r) （6） p∨(q∧r) = (p∨q)∧(p∨r) 第4組：否定深入 （7） ┐ ┐p = p （雙否定律） （8） ┐(p∨q) = ┐p∧┐q （德摩根律）

55、 （9） ┐(p∧q) = ┐p∨┐q （德摩根律）,90,第5組：變?cè)韧?（10） p∨p = p （等冪律） （11） p∧p = p （等冪律） （12） p∧┐p = 0 （矛盾律） （13） p∨┐p = 1 （排中律）第6組：常值與變?cè)穆?lián)結(jié) （14） 1∧p

56、 = p （同一律） （15） 0∧p = 0 （零律） （16） 1∨p = 1 （零律） （17） 0∨p = p （同一律）,91,第7組： 聯(lián)結(jié)詞化歸 （18） p→q = ┐q → ┐p （逆否等值式 ） （19） p→q = ┐p∨q （蘊(yùn)涵等值式 ）,9

57、2,說(shuō)明:1) 在上面的基本等值式中，很多是成對(duì)出現(xiàn)的，如果將∧, ∨, ０, １分別換為∨, ∧, １, ０, 就得到另外一個(gè)等值式。2) 這些等值式都可用列真值表的方法證明。 3) 由于聯(lián)結(jié)詞∨、 ∧滿足可結(jié)合性， 因此可將(p∨q)∨r和p∨(q∨r)簡(jiǎn)記為p∨q∨r； (p∧q)∧r和p∧(q∧r)簡(jiǎn)記為p∧q∧r。 4) 性質(zhì)(1)-(17)可對(duì)照集合運(yùn)算的性質(zhì)記憶（P10－P11）。,93,?關(guān)于上述基本等值式應(yīng)

58、注意以下問(wèn)題：在使用上述基本等值式時(shí)，應(yīng)做到能熟練地將左邊替換成右邊，同時(shí)能熟練地將右邊替換成左邊。應(yīng)特別重視如下基本等值式：分配律、德摩根律、蘊(yùn)涵等值式。常見(jiàn)錯(cuò)誤：┐(p∨q) = ┐p∨┐q ┐(p∨q) = ┐p∧q,94,邏輯等價(jià)的應(yīng)用,【例】利用基本的邏輯等價(jià)關(guān)系，化簡(jiǎn)電路圖,解：上述電路圖可描述為：((p∧q∧r)∨(p∧q∧s))∧((p∧r)∨(p∧s)),95

59、,利用基本邏輯等價(jià)式，化簡(jiǎn)公式可得： ((p∧q∧r)∨(p∧q∧s))∧((p∧r)∨(p∧s)) = ((p∧q∧(r∨s))∧(p∧(r∨s)) = p∧q∧(r∨s)；,96,【例】將下面程序語(yǔ)言進(jìn)行化簡(jiǎn)。if A then if B then X else Y else if B then X else Y,解：執(zhí)行X的條件為： (Ａ∧Ｂ)∨(?Ａ∧Ｂ),執(zhí)行Y的條件為： (Ａ

60、∧?Ｂ)∨(?Ａ∧?Ｂ),97,執(zhí)行X的條件可化簡(jiǎn)為： (Ａ∧Ｂ)∨(?Ａ∧Ｂ)＝ (Ａ∨ ?Ａ) ∧Ｂ＝Ｂ執(zhí)行Y的條件可化簡(jiǎn)為： (Ａ∧?Ｂ)∨(?Ａ∧?Ｂ)＝ (Ａ∨?Ａ) ∧ ?Ｂ ＝?Ｂ,程序可簡(jiǎn)化為：If B then X else Y,98,2. 推理規(guī)則（1）假言推理 如果： p→q 為真，且 p 為真 則： q 為真（2）三段論推理 如

61、果： p→q 為真，且 q→r 為真 則： p→r 為真（3）拒取推理 如果： p→q 為真，且 ┐q 為真 則： ┐p 為真,99,（4）合取推理如果： p 為真，且 q 為真則： p∧q 為真（5）附加推理如果： p 為真則： p∨q 為真,100,（6）化簡(jiǎn)推理 如果：p∧q 為真 則： p 為真（7）析取推理 如果： p∨q

62、 為真， 且 ┐p 為真 則： q 為真,101,在推理過(guò)程中還經(jīng)常用到以下推理規(guī)則：,1）前提引入規(guī)則（P規(guī)則）: 在推理過(guò)程中,任何地方都可以引用前提。,2）結(jié)論引用規(guī)則（Ｔ規(guī)則）: 在推理過(guò)程中得到的中間結(jié)論S可以作為后繼證明的前提引入。,102,3. 命題邏輯的等式推理 命題邏輯的等式推理系統(tǒng):命題邏輯的符號(hào)系統(tǒng)+基本等式+推理規(guī)則,（1）推理問(wèn)題的描述： 前提： P1,

63、 P2, …, Pn 結(jié)論：Q,（2）按照推理規(guī)則逐步由前提推出結(jié)論。,103,【例 】 試證 p→q, q→r, p ? r 　。 前提： p→q （1） q→r （2） p （3） 結(jié)論： r 證明：,（1）（3

64、）? q （4） 假言推理,（2）（4）? r （5） 假言推理,104,例4.4.1：設(shè)如果學(xué)生認(rèn)真上課就能做好作業(yè)。學(xué)生或者不認(rèn)真上課或者通過(guò)考試。學(xué)生做好作業(yè)且通過(guò)考試則綜合成績(jī)就合格。證明：如果學(xué)生認(rèn)真上課，綜合成績(jī)就合格。,證明：分別用命題 p、q、r、t 表示： p：學(xué)生認(rèn)真上課。 q：學(xué)生能做好作業(yè)。 r：學(xué)生能通過(guò)考試。 t：學(xué)生綜合成績(jī)合格

65、。,105,前提： p→q (1) ┐p∨r (2) (p∧r)→t (3) p (4)結(jié)論： t 證明： (1) (4) => q （5） 假言推理 (2) =>

66、; p→r （6） 基本等式 (6) (4) => r （7） 假言推理 (4) (7) => p∧r （8） 合取推理 (3) (8) => t （9） 假言推理,106,【例】 證明: 如果今天是星期三, 那么我有離散數(shù)學(xué)或數(shù)字邏輯測(cè)驗(yàn)。如果離散數(shù)學(xué)課老師有事, 那么沒(méi)有離散數(shù)學(xué)測(cè)驗(yàn)。 今天是星期三且

67、離散數(shù)學(xué)老師有事。所以, 我有數(shù)字邏輯測(cè)驗(yàn)。 證明： 設(shè) p: 今天是星期三。 q: 我有離散數(shù)學(xué)測(cè)驗(yàn)。 r: 我有數(shù)字邏輯測(cè)驗(yàn)。 s: 離散數(shù)學(xué)課老師有事。 前提： p→q∨r （1） s→┐q （2）

68、 p∧s （3） 結(jié)論：r,107,（3）? p （4） 化簡(jiǎn)推理,（1）（4）? q∨r （5） 假言推理,（3）? s （6） 化簡(jiǎn)推理,（2）（6）? ┐q