第一章命題邏輯

1、離散數(shù)學(xué)離散數(shù)學(xué)教材：教材：左孝凌等編著離散數(shù)學(xué) 上海科學(xué)技術(shù)文獻(xiàn)出版社 習(xí)題集：習(xí)題集：離散數(shù)學(xué) 理論分析題解 上?？茖W(xué)技術(shù)文獻(xiàn)出版社 聯(lián)系方式聯(lián)系方式 馮志慧馮志慧 E-Mail ： QQ：541161983考考 試試 卷面卷面 占占 70% 平時(shí)平時(shí) 占占 30%第第 一一 章章命題邏輯命題邏輯 數(shù)據(jù)邏輯最早傳入中國(guó)是數(shù)據(jù)邏輯最早傳入中國(guó)是在在19201920年。當(dāng)時(shí)，作為數(shù)理邏年。當(dāng)時(shí)，作為數(shù)理邏輯奠基人之一的羅素在北京大輯奠基人之一的羅素在北京大學(xué)作了五大講演。在數(shù)理邏輯學(xué)作了五大講演。在數(shù)理邏輯的講題下，介紹了他創(chuàng)建的命的講題下，介紹了他創(chuàng)建的命題演算和類演算。題演算和類演算。 摘

2、自摘自 宋文堅(jiān)宋文堅(jiān)“中國(guó)數(shù)理邏輯八十年中國(guó)數(shù)理邏輯八十年”伯特蘭羅素是二十世紀(jì)英國(guó)哲學(xué)家、數(shù)學(xué)家、邏輯學(xué)家、歷史學(xué)家，無(wú)神論或者不可知論者，也是上世紀(jì)西方最著名、影響最大的學(xué)者和和平主義社會(huì)活動(dòng)家之一，1950年諾貝爾文學(xué)獎(jiǎng)得主， 羅素悖論：羅素悖論： 把所有集合分為把所有集合分為2類，第一類中的集合以其自身為元素，第類，第一類中的集合以其自身為元素，第二類中的集合不以自身為元素，假令第一類集合所組成的集合為二類中的集合不以自身為元素，假令第一類集合所組成的集合為P，第二類所組成的集合為，第二類所組成的集合為Q，于是有：，于是有： P=A AA Q=A A A 問(wèn)，問(wèn)，QP 還是還是 QQ？

3、 若若QP，那么根據(jù)第一類集合的定義，必有，那么根據(jù)第一類集合的定義，必有QQ，但是，但是Q中任何集合都有中任何集合都有A A的性質(zhì)，因?yàn)榈男再|(zhì)，因?yàn)镼Q，所以，所以QQ，引出矛，引出矛盾。盾。 若若QQ，根據(jù)第一類集合的定義，必有，根據(jù)第一類集合的定義，必有QP，而顯然，而顯然PQ= ，所以，所以Q Q，還是矛盾。，還是矛盾。 這就是著名的這就是著名的“羅素悖論羅素悖論”。羅素悖論還有一些較為通俗。羅素悖論還有一些較為通俗的版本，如的版本，如理發(fā)師悖論理發(fā)師悖論等。等。 邏輯學(xué)邏輯學(xué): : 研究人的思維形式和規(guī)律的科研究人的思維形式和規(guī)律的科學(xué)由于研究的對(duì)象和方法各有側(cè)重而又分為形學(xué)由于研究

4、的對(duì)象和方法各有側(cè)重而又分為形式邏輯、辯證邏輯和數(shù)理邏輯式邏輯、辯證邏輯和數(shù)理邏輯 數(shù)理邏輯是用數(shù)理邏輯是用數(shù)學(xué)方法來(lái)研究來(lái)研究推理的形式結(jié)構(gòu)和和推理規(guī)律的數(shù)學(xué)學(xué)科。這里所指的數(shù)學(xué)方的數(shù)學(xué)學(xué)科。這里所指的數(shù)學(xué)方法就是引進(jìn)一套法就是引進(jìn)一套符號(hào)體系的方法。所以數(shù)理邏輯的方法。所以數(shù)理邏輯又稱又稱符號(hào)邏輯，它是從量的側(cè)面來(lái)研究思維規(guī)律，它是從量的側(cè)面來(lái)研究思維規(guī)律的。的。 現(xiàn)代數(shù)理邏輯可分為邏輯演算、證明論、現(xiàn)代數(shù)理邏輯可分為邏輯演算、證明論、公理集合論、遞歸論和模型論。公理集合論、遞歸論和模型論。 研究思維的邏輯結(jié)構(gòu)和推理，人們關(guān)心的研究思維的邏輯結(jié)構(gòu)和推理，人們關(guān)心的問(wèn)題是前提和結(jié)論之間是否存

5、在一種邏輯推理問(wèn)題是前提和結(jié)論之間是否存在一種邏輯推理關(guān)系？如果前提和結(jié)論之間存在這樣一種邏輯關(guān)系？如果前提和結(jié)論之間存在這樣一種邏輯推理關(guān)系，那么，具體按照什么方法，在前提推理關(guān)系，那么，具體按照什么方法，在前提為真的情況下，可以推出結(jié)論為真？為真的情況下，可以推出結(jié)論為真？ 下面舉二個(gè)例子來(lái)說(shuō)明這一點(diǎn)。下面舉二個(gè)例子來(lái)說(shuō)明這一點(diǎn)。例例1 1 考慮一元二次方程考慮一元二次方程 ax ax2 2+bx+c=0+bx+c=0我們知道：如果我們知道：如果b b2 2-4ac0-4ac0，則方程有實(shí)數(shù)解。，則方程有實(shí)數(shù)解。顯然，顯然，b b2 2-4ac0-4ac0是是前提前提，方程有實(shí)數(shù)解是，方程

6、有實(shí)數(shù)解是結(jié)論結(jié)論抽象來(lái)看：當(dāng)抽象來(lái)看：當(dāng)前提前提為為真真時(shí)，可以推出時(shí)，可以推出結(jié)論結(jié)論為為真真。例例2 2 考慮來(lái)人是華佗，他能治療關(guān)羽的箭傷這考慮來(lái)人是華佗，他能治療關(guān)羽的箭傷這樣一個(gè)歷史事件。樣一個(gè)歷史事件。 顯然，來(lái)人如果是華佗為顯然，來(lái)人如果是華佗為前提前提，他（，他（= =來(lái)來(lái)人）能治療關(guān)羽的箭傷是人）能治療關(guān)羽的箭傷是結(jié)論結(jié)論。抽象來(lái)看：當(dāng)抽象來(lái)看：當(dāng)前提前提為為真真時(shí)，可以推出時(shí)，可以推出結(jié)論結(jié)論為為真真 上述兩個(gè)看似不相關(guān)的實(shí)例說(shuō)明了一個(gè)共上述兩個(gè)看似不相關(guān)的實(shí)例說(shuō)明了一個(gè)共同的問(wèn)題：同的問(wèn)題：推理問(wèn)題推理問(wèn)題，這就是我們要研究的。，這就是我們要研究的。 抽象成數(shù)理邏輯語(yǔ)言

7、表達(dá)方式：抽象成數(shù)理邏輯語(yǔ)言表達(dá)方式： 如果如果A A 蘊(yùn)涵蘊(yùn)涵 B B，現(xiàn)又有，現(xiàn)又有A A，則可以推導(dǎo)出，則可以推導(dǎo)出B B。 1.1 命題及其表示法命題及其表示法 1.2 聯(lián)結(jié)詞聯(lián)結(jié)詞 1.5 重言式與蘊(yùn)含式重言式與蘊(yùn)含式 1.4 真值表與等價(jià)公式真值表與等價(jià)公式第一章第一章 命題邏輯命題邏輯 1.3 命題公式與翻譯命題公式與翻譯 1.6 其他聯(lián)結(jié)詞其他聯(lián)結(jié)詞 1.7 對(duì)偶與范式對(duì)偶與范式 1.8 推理理論推理理論1 1、教學(xué)內(nèi)容：、教學(xué)內(nèi)容： 命題及表示、聯(lián)結(jié)詞、命題公式與翻譯、真值命題及表示、聯(lián)結(jié)詞、命題公式與翻譯、真值表與等價(jià)公式、重言式與蘊(yùn)涵式、其他聯(lián)結(jié)詞、對(duì)表與等價(jià)公式、重言式

8、與蘊(yùn)涵式、其他聯(lián)結(jié)詞、對(duì)偶與范式、推理理論。偶與范式、推理理論。2 2、教學(xué)目的及要求：、教學(xué)目的及要求： 深刻理解和掌握命題邏輯中的基本概念和基本深刻理解和掌握命題邏輯中的基本概念和基本方法。方法。3 3、教學(xué)重點(diǎn)：、教學(xué)重點(diǎn)： 命題邏輯中的基本概念和基本推理方法。命題邏輯中的基本概念和基本推理方法。4 4、教學(xué)難點(diǎn)：、教學(xué)難點(diǎn)： 推理理論。推理理論。 推理是從前提推出結(jié)論推理是從前提推出結(jié)論。在各門(mén)具體科學(xué)的研究活動(dòng)和人類日。在各門(mén)具體科學(xué)的研究活動(dòng)和人類日常生活實(shí)踐中，都離不開(kāi)推理。推理中的前提和結(jié)論都是命題，都常生活實(shí)踐中，都離不開(kāi)推理。推理中的前提和結(jié)論都是命題，都有具體的涵義。從怎

9、樣的前提出發(fā)，能推出怎樣的結(jié)論，這是各門(mén)有具體的涵義。從怎樣的前提出發(fā)，能推出怎樣的結(jié)論，這是各門(mén)具體科學(xué)自己要研究的問(wèn)題。具體科學(xué)自己要研究的問(wèn)題。數(shù)理邏輯研究推理時(shí)，一般并不涉及數(shù)理邏輯研究推理時(shí)，一般并不涉及前提和結(jié)論的具體內(nèi)容，而是研究前提和結(jié)論之間的關(guān)系，以及這前提和結(jié)論的具體內(nèi)容，而是研究前提和結(jié)論之間的關(guān)系，以及這種關(guān)系的合理性。種關(guān)系的合理性。這里所述的前提和結(jié)論之間的關(guān)系包括形式推理這里所述的前提和結(jié)論之間的關(guān)系包括形式推理關(guān)系和邏輯推理關(guān)系兩種，它們分別屬于形式語(yǔ)言語(yǔ)法和語(yǔ)義研究關(guān)系和邏輯推理關(guān)系兩種，它們分別屬于形式語(yǔ)言語(yǔ)法和語(yǔ)義研究的范疇。（的范疇。（參看前面兩命題推理

10、例子參看前面兩命題推理例子） 我們已經(jīng)知道，我們已經(jīng)知道，邏輯演算是為了研究推理中前提和結(jié)論之間的邏輯演算是為了研究推理中前提和結(jié)論之間的形式推理關(guān)系而構(gòu)造的形式語(yǔ)言形式推理關(guān)系而構(gòu)造的形式語(yǔ)言。邏輯演算作為一個(gè)數(shù)學(xué)系統(tǒng)，需。邏輯演算作為一個(gè)數(shù)學(xué)系統(tǒng)，需要有符號(hào)，而作為一種形式語(yǔ)言，它必須要有構(gòu)成語(yǔ)言的符號(hào)，即要有符號(hào)，而作為一種形式語(yǔ)言，它必須要有構(gòu)成語(yǔ)言的符號(hào)，即字母，而且，從便于使用和理解的角度考慮，兩者應(yīng)該盡可能地保字母，而且，從便于使用和理解的角度考慮，兩者應(yīng)該盡可能地保持一致。持一致。第一章第一章 命題邏輯命題邏輯第一章第一章 命題邏輯命題邏輯邏輯成為一門(mén)科學(xué)，是從邏輯成為一門(mén)科學(xué)

11、，是從亞里士多德亞里士多德開(kāi)始的開(kāi)始的。命題（百度）：命題（百度）： 1.1 1.1 命題及其表示法命題及其表示法 在現(xiàn)代哲學(xué)、數(shù)學(xué)、邏輯學(xué)、語(yǔ)言學(xué)中，在現(xiàn)代哲學(xué)、數(shù)學(xué)、邏輯學(xué)、語(yǔ)言學(xué)中，命題是指一個(gè)判斷（陳述）的語(yǔ)義（實(shí)際表達(dá)命題是指一個(gè)判斷（陳述）的語(yǔ)義（實(shí)際表達(dá)的概念），這個(gè)概念是可以被定義并觀察的現(xiàn)的概念），這個(gè)概念是可以被定義并觀察的現(xiàn)象。象。命題命題不是指判斷（陳述）本身，而是指所不是指判斷（陳述）本身，而是指所表達(dá)的語(yǔ)義。當(dāng)相異判斷（陳述）具有相同語(yǔ)表達(dá)的語(yǔ)義。當(dāng)相異判斷（陳述）具有相同語(yǔ)義的時(shí)候，他們表達(dá)相同的命題。義的時(shí)候，他們表達(dá)相同的命題。第一章第一章 命題邏輯命題邏輯具

12、有單一、明確的含義具有單一、明確的含義。其基本元素是具有判斷內(nèi)容的陳述句其基本元素是具有判斷內(nèi)容的陳述句。日常中使用的語(yǔ)言稱日常中使用的語(yǔ)言稱。古典邏輯認(rèn)為：命題或真或假，不能兼而有之古典邏輯認(rèn)為：命題或真或假，不能兼而有之。 無(wú)所謂真假的語(yǔ)句（感嘆、祈使、疑問(wèn)）不能構(gòu)成命題。無(wú)所謂真假的語(yǔ)句（感嘆、祈使、疑問(wèn)）不能構(gòu)成命題。 1.1 1.1 命題及其表示法命題及其表示法第一章第一章 命題邏輯命題邏輯表示命題的符號(hào)稱為表示命題的符號(hào)稱為如：如：P P、A Ai i、 33 。命題有命題有： 不能分解為更簡(jiǎn)單的陳述句為不能分解為更簡(jiǎn)單的陳述句為； 由聯(lián)結(jié)詞、標(biāo)點(diǎn)符號(hào)、原子命題構(gòu)成由聯(lián)結(jié)詞、標(biāo)點(diǎn)符

13、號(hào)、原子命題構(gòu)成。對(duì)命題變?cè)獙?duì)命題變?cè)狿 P以特定命題取代，稱對(duì)以特定命題取代，稱對(duì)P P進(jìn)行進(jìn)行。一個(gè)命題標(biāo)識(shí)符（一個(gè)命題標(biāo)識(shí)符（P P）如表示確定的命題，稱）如表示確定的命題，稱。 否則稱否則稱（不是命題）。（不是命題）。 1.1 1.1 命題及其表示法命題及其表示法第一章第一章 命題邏輯命題邏輯例：例：（1）雪是黑的；）雪是黑的；（2）張三唱歌并且張三跳舞；）張三唱歌并且張三跳舞；（3）全體立正！）全體立正?。?）你會(huì)開(kāi)汽車嗎？）你會(huì)開(kāi)汽車嗎？（5）我正在說(shuō)謊。）我正在說(shuō)謊。（6）如果天氣好，那么我要進(jìn)城去。）如果天氣好，那么我要進(jìn)城去。（7）如果地球是方的，那么恐龍現(xiàn)在還活著。）如果地

14、球是方的，那么恐龍現(xiàn)在還活著。（8）陳勝、吳廣起義那天鄭州下雨。）陳勝、吳廣起義那天鄭州下雨。（9）大于）大于2的偶數(shù)均可分解為兩個(gè)質(zhì)數(shù)的和（哥德的偶數(shù)均可分解為兩個(gè)質(zhì)數(shù)的和（哥德 巴赫猜想）。巴赫猜想）。 1.1 1.1 命題及其表示法命題及其表示法第一章第一章 命題邏輯命題邏輯 （1） 4是素?cái)?shù)。是素?cái)?shù)。例例 : 判斷下列句子是否為命題判斷下列句子是否為命題（7） 這朵花真美麗啊！這朵花真美麗啊?。?） 請(qǐng)不要吸煙！請(qǐng)不要吸煙！2（5） 大于大于 嗎？嗎？（4） 2050年元旦是晴天。年元旦是晴天。（3） 火星上有水?；鹦巧嫌兴?。5（2） 是無(wú)理數(shù)是無(wú)理數(shù) 。第一章第一章 命題邏輯命題邏輯

15、定義定義 1 :設(shè)設(shè) P 為命題，復(fù)合命題為命題，復(fù)合命題“非非P ” (即即 “P的否定的否定”)稱為稱為 P 的否定式，記為的否定式，記為 P 。 符號(hào)符號(hào) 稱為稱為否定否定聯(lián)結(jié)詞。聯(lián)結(jié)詞。規(guī)定：規(guī)定：P為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P 為假。為假。則則: (1) P ； (2) Q .例例 符號(hào)化：（符號(hào)化：（1）張偉不是三好學(xué)生）張偉不是三好學(xué)生; （2） 不是有理數(shù)不是有理數(shù) 。 2解：記解：記 P：張偉是三好學(xué)生。張偉是三好學(xué)生。 Q： 是有理數(shù)。是有理數(shù)。 2 1.2 1.2 聯(lián)結(jié)詞聯(lián)結(jié)詞聯(lián)結(jié)詞聯(lián)結(jié)詞是是復(fù)合命題復(fù)合命題中重要組成部分中重要組成部分 。第一章第一章 命題邏輯命題邏輯 1

16、.2 1.2 聯(lián)結(jié)詞聯(lián)結(jié)詞 定義定義2 ：設(shè)：設(shè) P , P , Q Q 為兩個(gè)命題。復(fù)合命題為兩個(gè)命題。復(fù)合命題“ “ P P 與與Q Q” ” 即即“ “P P 并且并且Q Q” ” 稱為稱為 P P 與與 Q Q 的合取式，記為的合取式，記為 P P Q Q。符號(hào)。符號(hào)稱為稱為合取合取聯(lián)結(jié)詞。聯(lián)結(jié)詞。規(guī)定：規(guī)定： P P Q Q為真為真當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) P P 與與Q Q 同時(shí)為真同時(shí)為真。注：自然語(yǔ)言中注：自然語(yǔ)言中 “與與”, “和和”, “且且”, “既既.又又”, “不僅不僅而而且且”, “雖然雖然但是但是”, “一面一面一面一面”等聯(lián)結(jié)詞都可以符號(hào)等聯(lián)結(jié)詞都可以符號(hào)化為化為；

17、但并不是所有的但并不是所有的“與與”、“和和”等都能用聯(lián)結(jié)詞等都能用聯(lián)結(jié)詞替代。替代。第一章第一章 命題邏輯命題邏輯 (1) 吳穎既用功又聰明吳穎既用功又聰明. . (2) 吳穎吳穎不僅用功而且聰明不僅用功而且聰明. . (3) 吳穎吳穎雖然聰明，但不用功雖然聰明，但不用功. . (4) 張輝和王張輝和王麗麗都是三好學(xué)生都是三好學(xué)生. . (5) 張張輝輝和王麗是同學(xué)和王麗是同學(xué). .例例：將下列命題符號(hào)化將下列命題符號(hào)化 PQ; PQ； QP；RS。(5) 是原子命題是原子命題, ,符號(hào)化為符號(hào)化為T(mén): 張張輝輝和王麗是同學(xué)。和王麗是同學(xué)。則符號(hào)化分別為：則符號(hào)化分別為： 解解: (1)、(

18、2)、(3)、(4)： 令令P:吳穎吳穎用功；用功；Q:吳穎吳穎聰明，聰明， R: 張偉是三好學(xué)生；張偉是三好學(xué)生；S: 王輝是三好學(xué)生王輝是三好學(xué)生.第一章第一章 命題邏輯命題邏輯 1.2 1.2 聯(lián)結(jié)詞聯(lián)結(jié)詞定義定義3 ：設(shè)：設(shè) P , Q 為兩個(gè)命題為兩個(gè)命題 , 復(fù)合命題復(fù)合命題 “ P 或或 Q ” 稱為稱為 P 與與 Q 的析取式的析取式, 記為記為 PQ。符號(hào)。符號(hào)稱為稱為析取析取聯(lián)結(jié)詞。聯(lián)結(jié)詞。規(guī)定：規(guī)定： PQ 為假當(dāng)且僅當(dāng)為假當(dāng)且僅當(dāng) P 與與 Q 同時(shí)為假。同時(shí)為假。注注: 自然語(yǔ)言中的自然語(yǔ)言中的 “或或” 聯(lián)結(jié)的兩個(gè)命題可以具有相容性，聯(lián)結(jié)的兩個(gè)命題可以具有相容性，也

19、可以具有排斥性。也可以具有排斥性。前者稱為前者稱為相容或相容或，后者稱為后者稱為排斥或排斥或。析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞指的是指的是“相容或相容或”。第一章第一章 命題邏輯命題邏輯（1）張曉靜愛(ài)唱歌或愛(ài)聽(tīng)音樂(lè)。）張曉靜愛(ài)唱歌或愛(ài)聽(tīng)音樂(lè)。（2）張曉靜只能挑選）張曉靜只能挑選202房或房或203房。房。（3）張曉靜是江西人或安徽人。）張曉靜是江西人或安徽人。解：解：(1)令令P:張曉靜愛(ài)唱歌；張曉靜愛(ài)唱歌；Q:張曉靜愛(ài)聽(tīng)音樂(lè)，張曉靜愛(ài)聽(tīng)音樂(lè)， 則：則：例例：將下列命題符號(hào)化將下列命題符號(hào)化PQ ; (2)令令R:張曉靜住張曉靜住202房；房；S:張曉靜住張曉靜住203房，房，則則:(RS)(RS);(3

20、)令令T:張曉靜是江西人；張曉靜是江西人；U:張曉靜是安徽人，張曉靜是安徽人，則：則：(TU U)(T TU U).).第一章第一章 命題邏輯命題邏輯 定義定義4 ：設(shè)設(shè) P, ,Q為兩個(gè)命題。復(fù)合命題為兩個(gè)命題。復(fù)合命題 “ “如果如果 P, ,則則 Q ”稱為稱為P與與Q的的條件條件式，記作式，記作PQ。符號(hào)。符號(hào)稱為稱為條件條件聯(lián)結(jié)詞，聯(lián)結(jié)詞， 稱稱P是是條件條件式的式的前件前件，Q是是條件式的條件式的后件后件，Q是是P的必的必要條件。要條件。規(guī)定：規(guī)定： PQ為假為假當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) P 為真為真Q為假為假。第一章第一章 命題邏輯命題邏輯注：注： 1. 在自然語(yǔ)言中，在自然語(yǔ)言中，“如

21、果如果P, 則則Q”這種命題還有其它敘述方式，這種命題還有其它敘述方式，比如：比如：“只要只要P, 就就Q”，“ 因?yàn)橐驗(yàn)镻，所以，所以 Q”, “P僅當(dāng)僅當(dāng)Q”, “只有只有Q才才P”，“除非除非Q Q才才P”, “除非除非Q，否則非，否則非P ”等等，它們都可等等，它們都可符號(hào)化為符號(hào)化為 PQ。2. 在數(shù)學(xué)或其它自然科學(xué)中，在數(shù)學(xué)或其它自然科學(xué)中，“如果如果P,則則Q” 往往表達(dá)的是前件往往表達(dá)的是前件P為真，后件為真，后件Q也為真的推理關(guān)系。但在數(shù)理邏輯中，作為一種也為真的推理關(guān)系。但在數(shù)理邏輯中，作為一種規(guī)定，當(dāng)規(guī)定，當(dāng) P為假時(shí)，無(wú)論為假時(shí)，無(wú)論Q是真是假，是真是假，PQ均為真（因

22、考慮的均為真（因考慮的整個(gè)語(yǔ)句）。整個(gè)語(yǔ)句）。3. 在自然語(yǔ)言中，在自然語(yǔ)言中，“如果如果 P, 則則 Q ” 中的前件中的前件 P 和后件和后件 Q 往往往往具有某種內(nèi)在聯(lián)系，而在數(shù)理邏輯中，具有某種內(nèi)在聯(lián)系，而在數(shù)理邏輯中，P 與與 Q 可以無(wú)任何內(nèi)在可以無(wú)任何內(nèi)在聯(lián)系。聯(lián)系。第一章第一章 命題邏輯命題邏輯(1) 如果如果3+3 = 6,則雪是白色的。則雪是白色的。(2) 如果如果3+3 6,則雪是白色的。則雪是白色的。(3) 如果如果3+3 = 6,則雪不是白色的。則雪不是白色的。(4) 如果如果3+3 6,則雪不是白色的。則雪不是白色的。(5) 只要只要 a 能被整除，則能被整除，則

23、a 一定能被整除。一定能被整除。(6) a 能被整除，僅當(dāng)能被整除，僅當(dāng) a 能被整除。能被整除。(7) 除非除非 a 能被整除，能被整除，a 才能被整除。才能被整除。(8) 除非除非 a 能被整除，否則能被整除，否則 a 不能被整除。不能被整除。(9) 只有只有 a 能被整除，能被整除，a 才能被整除。才能被整除。例例：將下列命題符號(hào)化，并指出各復(fù)合命題的真值。將下列命題符號(hào)化，并指出各復(fù)合命題的真值。解：令解：令P：3+3=6； Q：雪是白色的。則：雪是白色的。則 (1) 到到 (4) 的符號(hào)化形式分別為：的符號(hào)化形式分別為： 令令R：a 能被整除；能被整除； S: : a能被整除。能被整

24、除。 (5) 到到 (9) 都可符號(hào)化為都可符號(hào)化為:PQ；PQ；PQ；PQ。它們的真值分別為：它們的真值分別為：,。RS, ,真值為。真值為。第一章第一章 命題邏輯命題邏輯 1.2 1.2 聯(lián)結(jié)詞聯(lián)結(jié)詞定義定義 5：設(shè)：設(shè) P, Q 是兩個(gè)命題，復(fù)合命題是兩個(gè)命題，復(fù)合命題 “ P 當(dāng)且當(dāng)且僅當(dāng)僅當(dāng) Q ”稱為稱為 P 與與 Q 的等價(jià)式，記為的等價(jià)式，記為 PQ。符號(hào)。符號(hào)稱為稱為雙條件雙條件聯(lián)結(jié)詞。聯(lián)結(jié)詞。規(guī)定：規(guī)定： PQ 為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng) P 與與 Q 同時(shí)為真或同時(shí)同時(shí)為真或同時(shí)為假。為假。注：注：PQ 可理解為可理解為“Q與與P互為充分必要條件互為充分必要條件”； 它與它

25、與(PQ)(QPQP) )的邏輯關(guān)系完全一致。的邏輯關(guān)系完全一致。第一章第一章 命題邏輯命題邏輯 (1) 3 是無(wú)理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲。是無(wú)理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲。(2) 2+3=5的充要條件是的充要條件是3是無(wú)理數(shù)。是無(wú)理數(shù)。(3) 若兩圓的面積相等若兩圓的面積相等, 則它們的半徑相等則它們的半徑相等, 反之亦然。反之亦然。(4) 當(dāng)王小紅心情愉快當(dāng)王小紅心情愉快時(shí)時(shí), 她就唱歌她就唱歌, 反之反之, 當(dāng)她唱歌時(shí)當(dāng)她唱歌時(shí), 一定心情愉快。一定心情愉快。解：解：(1)令令P:3是無(wú)理數(shù)；是無(wú)理數(shù)；Q: 加拿大位于亞洲，則符號(hào)化為加拿大位于亞洲，則符號(hào)化為(4)令令U:王小紅心情愉快

26、王小紅心情愉快；V:王小紅唱歌王小紅唱歌，則，則符號(hào)化為符號(hào)化為P Q , 真值為真值為0。(2)令令R:2+3=5；令；令P:3是無(wú)理數(shù)，則是無(wú)理數(shù)，則符號(hào)化為符號(hào)化為 R P , 真值為真值為1。 (3)令令S:兩圓面積相等；兩圓面積相等；T:兩圓半徑相等，則符號(hào)化為兩圓半徑相等，則符號(hào)化為U V, 真值由具體情況而定。真值由具體情況而定。ST ,真值為真值為1。例例：將下列命題符號(hào)化，并討論它們的真值。將下列命題符號(hào)化，并討論它們的真值。第一章第一章 命題邏輯命題邏輯例例 : 將下列命題符號(hào)化。將下列命題符號(hào)化。 (1) 是有理數(shù)是不對(duì)的是有理數(shù)是不對(duì)的. .（2）2是偶素?cái)?shù)是偶素?cái)?shù).

27、(3) 2或或4是偶素?cái)?shù)是偶素?cái)?shù). (4) 如果如果2是素?cái)?shù)，則是素?cái)?shù)，則3也是素?cái)?shù)也是素?cái)?shù). (5) 2是素?cái)?shù)當(dāng)且僅當(dāng)是素?cái)?shù)當(dāng)且僅當(dāng)3是素?cái)?shù)是素?cái)?shù).2解：記解：記 P： 是有理數(shù)是有理數(shù). Q：2是素?cái)?shù)是素?cái)?shù). R：2是偶數(shù)是偶數(shù). S：3是素?cái)?shù)是素?cái)?shù). T：4是偶數(shù)是偶數(shù).2則各語(yǔ)句表述為：則各語(yǔ)句表述為：非非P; (2) Q與與R; (3) P或或T; (4)如果如果Q,則則S；(5) Q當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)S . 第一章第一章 命題邏輯命題邏輯 ：設(shè)：設(shè)P P是一個(gè)命題，是一個(gè)命題，P P的否定也是一個(gè)新命題。的否定也是一個(gè)新命題。( () ) ：設(shè)：設(shè)P P、Q Q是兩個(gè)命題，是兩個(gè)命題

28、，P PQ Q表示表示P P、Q Q的析取。的析取。( () ) ：設(shè)：設(shè)P P 、Q Q是命題，是命題，P PQ Q表示表示P P、Q Q的合取。（的合取。（）小小 結(jié)結(jié)：設(shè)設(shè)P P、Q Q是兩個(gè)命題，是兩個(gè)命題，P PQ Q表示命題若表示命題若P P則則Q Q。 Q Q是是P P的必要條件，的必要條件，P P是是，Q Q是是。：設(shè)：設(shè)P P、Q Q是兩個(gè)命題，是兩個(gè)命題，P PQ Q表示命題表示命題 “ “P PQ”Q”。第一章第一章 命題邏輯命題邏輯 以上定義的五種最基本的聯(lián)結(jié)詞組成一個(gè)聯(lián)結(jié)詞集以上定義的五種最基本的聯(lián)結(jié)詞組成一個(gè)聯(lián)結(jié)詞集， 。由其中某個(gè)聯(lián)結(jié)詞聯(lián)結(jié)兩個(gè)原子命題（。由其中某

29、個(gè)聯(lián)結(jié)詞聯(lián)結(jié)兩個(gè)原子命題（聯(lián)結(jié)一聯(lián)結(jié)一個(gè)原子命題）所形成的復(fù)合命題稱為基本復(fù)合命題，它們的真值個(gè)原子命題）所形成的復(fù)合命題稱為基本復(fù)合命題，它們的真值情況如下表。情況如下表。 P QPPQPQPQPQ小小 結(jié)結(jié)110000010111110110010 00 11 01 1第一章第一章 命題邏輯命題邏輯命題演算命題演算的合式公式（的合式公式（wff）規(guī)定為：）規(guī)定為：( (命題公式命題公式) )定義定義1：1)1)單個(gè)命題變?cè)旧硎且粋€(gè)單個(gè)命題變?cè)旧硎且粋€(gè)合式公式合式公式；2)2)如如A A是合式公式，則是合式公式，則 A A也是也是合式公式合式公式；3)3)如果如果A A和和B B是合式公

30、式，則是合式公式，則ABAB、ABAB、A AB B、ABAB 也是也是合式公式合式公式； 4)4)當(dāng)且僅當(dāng)能夠有限次地應(yīng)用當(dāng)且僅當(dāng)能夠有限次地應(yīng)用1)1)、2)2)、3)3)所得到的包含所得到的包含 命題變?cè)?、?lián)結(jié)詞和括號(hào)的符號(hào)串是命題變?cè)⒙?lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式合式公式。 1.3 1.3 命題公式與翻譯命題公式與翻譯 第一章第一章 命題邏輯命題邏輯 由于命題公式中含有命題變?cè)?，故其真值一般是不確定的。由于命題公式中含有命題變?cè)势湔嬷狄话闶遣淮_定的。當(dāng)公式中所有命題變?cè)贾概沙删唧w的命題后，命題公式就成當(dāng)公式中所有命題變?cè)贾概沙删唧w的命題后，命題公式就成了真值確定的命題了。了真

31、值確定的命題了。 例如，命題公式例如，命題公式 (PQ)R :則命題公式則命題公式 (PQ)R 就被解釋成了一個(gè)真命題。就被解釋成了一個(gè)真命題。 若將若將 P 解釋成解釋成:2 是素?cái)?shù)是素?cái)?shù), Q 解釋成解釋成:3是偶數(shù)是偶數(shù), R 解釋成：解釋成： 是是無(wú)理數(shù)。無(wú)理數(shù)。2則則 (PQ)R 就被解釋成了一個(gè)假命題。就被解釋成了一個(gè)假命題。另外，如果另外，如果P, Q 的解釋不變，而將的解釋不變，而將R解釋成：解釋成： 是有理數(shù)，是有理數(shù)，2第一章第一章 命題邏輯命題邏輯 14次車下午五點(diǎn)半開(kāi)或六點(diǎn)開(kāi)。次車下午五點(diǎn)半開(kāi)或六點(diǎn)開(kāi)。我們要做到身體好、學(xué)習(xí)好、工作好，為祖四化建設(shè)而我們要做到身體好、學(xué)

32、習(xí)好、工作好，為祖四化建設(shè)而奮斗。奮斗。他既聰明又用功。他既聰明又用功。他雖聰明但不用功。他雖聰明但不用功。除非天氣好，否則我不去公園。（天氣好也不一定去）除非天氣好，否則我不去公園。（天氣好也不一定去）張三或李四都可以做這件事。張三或李四都可以做這件事。 1.3 1.3 命題公式與翻譯命題公式與翻譯 第一章第一章 命題邏輯命題邏輯符號(hào)化：符號(hào)化：辱罵和恐嚇決不是戰(zhàn)斗。辱罵和恐嚇決不是戰(zhàn)斗。小王和小李是夫妻，他們都很自私。小王和小李是夫妻，他們都很自私。如果天不下雨，則我去看足球比賽，否則我在家復(fù)習(xí)功課。如果天不下雨，則我去看足球比賽，否則我在家復(fù)習(xí)功課。如果蘋(píng)果是紅的或者是甜的，那么我買(mǎi)。如

33、果蘋(píng)果是紅的或者是甜的，那么我買(mǎi)。除非你努力，否則你將失敗。除非你努力，否則你將失敗。 1.3 1.3 命題公式與翻譯命題公式與翻譯 第一章第一章 命題邏輯命題邏輯符號(hào)化：符號(hào)化：張三是大學(xué)生，張三獲獎(jiǎng)學(xué)金，張三放聲歌唱。張三是大學(xué)生，張三獲獎(jiǎng)學(xué)金，張三放聲歌唱。我和他之間至少有一個(gè)要去邊疆。我和他之間至少有一個(gè)要去邊疆。如果他不來(lái)，那么他或是生病了，或是不在本地。如果他不來(lái)，那么他或是生病了，或是不在本地。如果你和他不都是傻子，那么你倆都不會(huì)去自討沒(méi)趣。如果你和他不都是傻子，那么你倆都不會(huì)去自討沒(méi)趣。說(shuō)小學(xué)生編不了程序，或說(shuō)小學(xué)生用不了計(jì)算機(jī)，那是不說(shuō)小學(xué)生編不了程序，或說(shuō)小學(xué)生用不了計(jì)算機(jī)

34、，那是不對(duì)的。對(duì)的。 1.3 1.3 命題公式與翻譯命題公式與翻譯 第一章第一章 命題邏輯命題邏輯 對(duì)命題公式中各分量（命題變?cè)┲概伤锌赡艿恼鎸?duì)命題公式中各分量（命題變?cè)┲概伤锌赡艿恼嬷?，及由此確定的命題公式的真值匯列成的表稱值，及由此確定的命題公式的真值匯列成的表稱。定義定義1： 有些命題公式在分量不同的指派下，對(duì)應(yīng)的真值與另有些命題公式在分量不同的指派下，對(duì)應(yīng)的真值與另一命題公式的真值完全相同。一命題公式的真值完全相同。 真值表中，命題公式真值的取值數(shù)目，決定于分量的個(gè)真值表中，命題公式真值的取值數(shù)目，決定于分量的個(gè)數(shù)。數(shù)。n個(gè)命題變?cè)M成的命題公式共有個(gè)命題變?cè)M成的命題公式共有

35、2n種真值情況。種真值情況。 1.4 1.4 真值表與等價(jià)公式真值表與等價(jià)公式 第一章第一章 命題邏輯命題邏輯 1.4 1.4 真值表與等價(jià)公式真值表與等價(jià)公式 含含n n個(gè)命題變個(gè)命題變?cè)墓焦灿械墓焦灿? 2n n 個(gè)不同的賦值。構(gòu)造個(gè)不同的賦值。構(gòu)造真值表的一般步驟如下：真值表的一般步驟如下：（1 1）列出命題公式中的所有命題變列出命題公式中的所有命題變?cè)?P, Q, ，列列出這些變出這些變?cè)乃械乃? 2n n 個(gè)賦值。個(gè)賦值。 （2 2） 按從低到高的順序依次列出公式的各個(gè)層。按從低到高的順序依次列出公式的各個(gè)層。（3） 對(duì)應(yīng)于變?cè)膶?duì)應(yīng)于變?cè)? 2n n 個(gè)賦值分別

36、計(jì)算出各層的真值，個(gè)賦值分別計(jì)算出各層的真值，直至算出公式的真值。直至算出公式的真值。第一章第一章 命題邏輯命題邏輯例例 寫(xiě)出下列公式的真值表，并求它們的成真、成假賦值。寫(xiě)出下列公式的真值表，并求它們的成真、成假賦值。 (1)(PQ)R; (2)(PP)(QQ); (3) (PQ)QRP Q RPRPQ(PQ)R解：解： (PQ)R 的真值表的真值表 111100000 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1101010100011000011101111(PP)(QQ)的真值表的真值表 P QPQPPQQ(PP)(QQ)0 00 11 01 1(PQ)Q

37、R 的真值表的真值表 P Q RPQ(PQ)(PQ)Q(PQ)QR0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 11111110010100000000011110011000011000000000000000000第一章第一章 命題邏輯命題邏輯 真值表中，兩個(gè)命題公式真值表中，兩個(gè)命題公式A A、B B在分量的不同指派，在分量的不同指派，其真值總是相同，則稱其真值總是相同，則稱A A和和B B是是等價(jià)等價(jià)的或的或邏輯相等邏輯相等的，并的，并記作：記作：ABAB。定義定義2： 當(dāng)兩個(gè)命題公式邏輯等價(jià)時(shí)，這兩個(gè)命題公式具有當(dāng)兩個(gè)命題公式邏輯等價(jià)時(shí)，這兩個(gè)命題公式

38、具有相同的相同的邏輯含義邏輯含義。 1.4 1.4 真值表與等價(jià)公式真值表與等價(jià)公式 第一章第一章 命題邏輯命題邏輯 給定給定n個(gè)命題變個(gè)命題變?cè)褂寐?lián)結(jié)詞和括號(hào)，可構(gòu)成無(wú)窮，使用聯(lián)結(jié)詞和括號(hào)，可構(gòu)成無(wú)窮多個(gè)命題公式。多個(gè)命題公式。 個(gè)命題變個(gè)命題變?cè)灿泄灿?2 2n n 個(gè)可能的賦值，而在每個(gè)賦值下個(gè)可能的賦值，而在每個(gè)賦值下公式只能取公式只能取值值0或或1。因此含個(gè)命題變項(xiàng)的公式其真值表。因此含個(gè)命題變項(xiàng)的公式其真值表只有只有2 22 2種可能的情況。從而必有無(wú)窮多個(gè)公式具有相同種可能的情況。從而必有無(wú)窮多個(gè)公式具有相同的真值表。的真值表。第一章第一章 命題邏輯命題邏輯例例 ：下列

39、公式中哪些具有相同的真值表？下列公式中哪些具有相同的真值表？(1)PQ； (2)PQ； (3) (PQ)；(4) (PQ)(QP)； (5) QPP QPQPQ(PQ)(PQ)(QP)QP0 00 11 01 1解：解： 5個(gè)公式的真值表個(gè)公式的真值表 從上表可見(jiàn)，命題公式從上表可見(jiàn)，命題公式 “PQ” 與與 “ (PQ) ”有相同的真值表有相同的真值表。1101100111011001 1011命題命題 “PQ” 與與 “ (PQ)(QP) ” 有相同的真值表。有相同的真值表。第一章第一章 命題邏輯命題邏輯例例 ：判斷公式判斷公式(PQ) (PQ) 與與 PQ PQ是否等值。是否等值。解：用

40、真值表法判斷解：用真值表法判斷, 如下：如下：P QPQPQ(PQ)PQ(PQ)(PQ)0 00 11 01 1注：注：A A與與B B等值當(dāng)且僅當(dāng)?shù)戎诞?dāng)且僅當(dāng)A A與與B B的真值表相同。因此，檢驗(yàn)的真值表相同。因此，檢驗(yàn)A A與與B B是否等值，也可通過(guò)是否等值，也可通過(guò)檢查檢查A A與與B B的真值表是否相同來(lái)實(shí)現(xiàn)。的真值表是否相同來(lái)實(shí)現(xiàn)。從表中可見(jiàn)，從表中可見(jiàn)，(PQ)(PQ)與與P PQQ等值。等值。110111101001011001001001第一章第一章 命題邏輯命題邏輯 (1) P(QR)(1) P(QR)與與(PQ)R; (2)(PQ)R (PQ)R; (2)(PQ)R 與

41、與(PQ)R(PQ)R。解：所給的解：所給的3 3個(gè)公式的真值表如下：個(gè)公式的真值表如下：P Q RP(QR)(PQ)R(PQ)R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1但但(PQ)R(PQ)R(PQ)R.(PQ)R.110111110111111111000111由真值表可見(jiàn)，由真值表可見(jiàn)，P(QR)P(QR)(PQ)R,(PQ)R,第一章第一章 命題邏輯命題邏輯 當(dāng)命題公式中變當(dāng)命題公式中變?cè)^多時(shí)，用上述方法判斷兩個(gè)公式是否等值計(jì)算量很較多時(shí)，用上述方法判斷兩個(gè)公式是否等值計(jì)算量很大。為此，人們將一組經(jīng)檢驗(yàn)為正確的等值式作為大。為此，人們將一組經(jīng)

42、檢驗(yàn)為正確的等值式作為命題定律（邏輯等價(jià)式命題定律（邏輯等價(jià)式，可用真值表驗(yàn)證可用真值表驗(yàn)證），通過(guò)公式間的等值演算來(lái)判斷兩公式是否等值。常用的，通過(guò)公式間的等值演算來(lái)判斷兩公式是否等值。常用的命題定律命題定律(P15 表表1-4.8)如下如下： 1. 1.雙重否定律：雙重否定律：P P (P) 2. (P) 2.冪等律：冪等律：P PPP, PPP, PPPPP 3. 3.交換律交換律: PQ: PQQP, PQQP, PQQPQP 4. 4.結(jié)合律結(jié)合律: (PQ)R: (PQ)RP(QR), (PQ)RP(QR), (PQ)RP(QR)P(QR) 5. 5.分配律：分配律：P(QR)P(

43、QR)(PQ)(PR) (PQ)(PR) (對(duì)對(duì)的分配律的分配律) ) P(QR) P(QR)(PQ)(PR) (PQ)(PR) (對(duì)對(duì)的分配律的分配律) ) 6. 6.德摩根律：德摩根律：(PQ)(PQ) PQ, (PQ) PQ, (PQ)PQPQ 7. 7.吸收律：吸收律：P(PQ)P(PQ)P, P(PQ)P, P(PQ)P P第一章第一章 命題邏輯命題邏輯8.8.零律：零律：PPT TT T, P, PF FF F9. 9. 同一律：同一律：PPF FP, PP, PT TP P10. 10. 排中律：排中律：PPPPT T （否定律）（否定律）11. 11. 矛盾律：矛盾律：PPPP

44、F F （否定律）（否定律）12. 12. 條件條件等值式：等值式：PQPQPQPQ13. 13. 雙條件雙條件等值式等值式: (P: (PQ)Q)(PQ)(QP)(PQ)(QP)14. 14. 假言易位假言易位: PQ: PQ QP QP15. 15. 雙條件雙條件否定等值否定等值式式: P: PQ QPPQQ16. 16. 歸謬論歸謬論: (PQ)(PQ) : (PQ)(PQ) P P第一章第一章 命題邏輯命題邏輯 1.4 1.4 真值表與等價(jià)公式真值表與等價(jià)公式 利用這利用這1616組組2424個(gè)等值式可以推演出更多的個(gè)等值式可以推演出更多的邏輯等價(jià)邏輯等價(jià)式式。由已知的。由已知的邏輯等

45、價(jià)式邏輯等價(jià)式推演出另一些推演出另一些邏輯等價(jià)式邏輯等價(jià)式的的過(guò)過(guò)程稱為等值演算。在等值演算中程稱為等值演算。在等值演算中, ,經(jīng)常用到如下置換規(guī)經(jīng)常用到如下置換規(guī)則則（定理（定理1 1）。 第一章第一章 命題邏輯命題邏輯 如果如果X X是合式公式是合式公式A A的一部分，且的一部分，且X X本身也是一個(gè)合式本身也是一個(gè)合式公式，則稱公式，則稱。定義定義3：定理定理1： 1.4 1.4 真值表與等價(jià)公式真值表與等價(jià)公式 設(shè)設(shè)X X是合式公式是合式公式A A的子公式，若的子公式，若X YX Y，如果將，如果將A A中中的的X X用用Y Y來(lái)置換，所得到公式來(lái)置換，所得到公式B B與公式與公式A

46、A等價(jià)，即等價(jià)，即ABAB。 第一章第一章 命題邏輯命題邏輯 1.4 1.4 真值表與等價(jià)公式真值表與等價(jià)公式 例如，對(duì)公式例如，對(duì)公式(PQ)R,(PQ)R,如果用如果用PQPQ置換其中的置換其中的PQ,PQ,則得則得(PQ)R.(PQ)R.由于由于PQPQPQPQ，故，故(PQ)R (PQ)R (PQ)R(PQ)R。類似地，可進(jìn)行如下等值演算：類似地，可進(jìn)行如下等值演算： (PQ)R (PQ)R (PQ)R(PQ)R (PQ)R (PQ)R (PQ)R (PQ)R (PR)(QR)(PR)(QR)為簡(jiǎn)便起見(jiàn)為簡(jiǎn)便起見(jiàn), 以后凡用到置換規(guī)則時(shí)以后凡用到置換規(guī)則時(shí), 均不必標(biāo)出。均不必標(biāo)出。條

47、件等值式，置換規(guī)則）條件等值式，置換規(guī)則）( (條件等值式，置換規(guī)則）條件等值式，置換規(guī)則）( (德摩根律，置換規(guī)則）德摩根律，置換規(guī)則）( (分配律，置換規(guī)則）分配律，置換規(guī)則）第一章第一章 命題邏輯命題邏輯 1.4 1.4 真值表與等價(jià)公式真值表與等價(jià)公式 例例 用等值演算證明用等值演算證明: (P: (PQ)Q)R (PR)(QR)(PR)(QR) 注：用等值演算證明等值式時(shí)，既可以從左向右推演，也可以從右向左推演。注：用等值演算證明等值式時(shí)，既可以從左向右推演，也可以從右向左推演。證：證：(PR)(QR)(PR)(QR)(PR)(QR)(PR)(QR)(PQ)R(PQ)R(PQ)R(P

48、Q)R(PQ)R (PQ)R ( (條件等值式條件等值式) )( (分配律分配律) )( (德摩根律德摩根律) )( (條件等值式條件等值式)第一章第一章 命題邏輯命題邏輯 例例 證明：證明：(PQ)R (PQ)R P(QR P(QR）. .方法二方法二: : 記記A=(PQ)R, B= P(QR)A=(PQ)R, B= P(QR)。先將。先將A,BA,B等值演算等值演算 化成易于觀察真值的公式，再進(jìn)行判斷?；梢子谟^察真值的公式，再進(jìn)行判斷。 A=(PQ)RA=(PQ)R(PQ)R(PQ)R (PQ)R (PQ)R (PQ)R(PQ)R B=P(QR) B=P(QR)P(QR)P(QR) P

49、QRPQR 易見(jiàn)，易見(jiàn)，000000，010010是是A A的成假賦值，而它們是的成假賦值，而它們是B B的成真賦值。的成真賦值。 (PQ)R (PQ)R P(QR) P(QR)。證：方法一：真值表法。證：方法一：真值表法。故故 ( (條件等值式條件等值式) ) ( (條件等值式條件等值式) ) ( (德摩根律德摩根律) )( (條件等值式條件等值式) )( (結(jié)合律結(jié)合律) )第一章第一章 命題邏輯命題邏輯v例 在某次研討會(huì)的休息時(shí)間，3名與會(huì)者根據(jù)王教授的口音對(duì)他是哪個(gè)省市的人進(jìn)行了判斷：v 甲說(shuō)王教授不是蘇州人，是上海人。v 乙說(shuō)王教授不是上海人，是蘇州人。v 丙說(shuō)王教授不是上海人，也不

50、是杭州人。v聽(tīng)完3人的判斷，王教授笑著說(shuō)，他們3人中有一人說(shuō)得全對(duì)，有一人說(shuō)對(duì)了一半，有一人說(shuō)得全不對(duì)。試用邏輯演算法分析王教授到底是哪里的人？ v解： 設(shè)命題 P, Q, R分別表示 ： 王教授是蘇州、上海、杭州人。則P, Q, R中必有一個(gè)真命題，兩個(gè)假命題。要通過(guò)邏輯演算將真命題找出來(lái)。v設(shè)： 甲的判斷為： A1= PQ; 乙的判斷為：A2= PQ; 丙的判斷為：A3= QR。 第一章第一章 命題邏輯命題邏輯v那么甲的判斷全對(duì)： B1= A1= PQv 甲的判斷對(duì)一半： B2=(PQ)(PQ)v 甲的判斷全錯(cuò)： B3=PQv 乙的判斷全對(duì)： C1= A2= PQv 乙的判斷對(duì)一半： C2

51、=(PQ)(PQ)v 乙的判斷全錯(cuò)： C3=PQv 丙的判斷全對(duì)： D1= A3=QRv 丙的判斷對(duì)一半： D2=(QR)(QR)v 丙的判斷全錯(cuò)： D3=QR v由王教授所說(shuō) v E=(B1C2D3) (B1C3D2) (B2C1D3) v (B2C3D1) (B3C1D2) (B3C2D1) v為真命題. 第一章第一章 命題邏輯命題邏輯vB1C2D3=(PQ) (PQ)(PQ)(QR)v (PQQR) (PQPR)0vB1C3D2=(PQ)(PQ)(QR)(QR)v (PQR) (PQQR)v PQRvB2C1D3=(PQ)(PQ) (PQ)(QR)v (PPPQQR) (PQQR)v 0

52、v類似可得v B2C3D10, B3C1D2PQR, B3C2D10v于是，由同一律可知 E(PQR) (PQR)v但因?yàn)橥踅淌诓荒芗仁翘K州人，又是杭州人，因而P,R必有一個(gè)為假命題，即PQR0 。v于是 EPQR 為真命題，因而必有P,R為假命題，Q為真命題，即王教授為上海人，甲說(shuō)得全對(duì)，丙說(shuō)對(duì)了一半，而乙全說(shuō)錯(cuò)啦。 第一章第一章 命題邏輯命題邏輯 給定一命題公式，無(wú)論對(duì)分量作怎樣的指派，其對(duì)給定一命題公式，無(wú)論對(duì)分量作怎樣的指派，其對(duì)應(yīng)真值永為應(yīng)真值永為T(mén) T，則稱該命題公式為，則稱該命題公式為重言式重言式或或永真式永真式。 定義定義1：定義定義2： 1.5 1.5 重言式與蘊(yùn)含式重言式與

53、蘊(yùn)含式 給定一命題公式，無(wú)論對(duì)分量作怎樣的指派，其對(duì)給定一命題公式，無(wú)論對(duì)分量作怎樣的指派，其對(duì)應(yīng)真值永為，則稱該命題公式為應(yīng)真值永為，則稱該命題公式為永假式永假式或或矛盾式矛盾式。 第一章第一章 命題邏輯命題邏輯 1.5 1.5 重言式與蘊(yùn)含式重言式與蘊(yùn)含式 若若A既不是永真式又不是矛盾式，則稱既不是永真式又不是矛盾式，則稱A為為可滿足式可滿足式。 注：注：A是可滿足式當(dāng)且僅當(dāng)是可滿足式當(dāng)且僅當(dāng)A至少存在一個(gè)成真賦值。至少存在一個(gè)成真賦值。 1. 重言式必是可滿足式，但反之不真。重言式必是可滿足式，但反之不真。 2. 可用真值表來(lái)判斷公式的類型：可用真值表來(lái)判斷公式的類型：(1) 若真值表最

54、后一列全為若真值表最后一列全為T(mén)，則公式為重言式；，則公式為重言式；(2) 若真值表最后一列全為若真值表最后一列全為F，則公式為矛盾式；，則公式為矛盾式；(3)若真值表最后一列至少有一個(gè)若真值表最后一列至少有一個(gè)T，則公式為可滿足式。，則公式為可滿足式。第一章第一章 命題邏輯命題邏輯(1)（(PQ)P)Q; (2) (P(PQ)R; (3) P(PQ)P)Q).解解: (1) （PQ)PQ (PQ)P)Q (PQ)P)Q (PQ)P)Q (PQ)P)Q (PP)(QP)Q (T(QP)Q (QP)Q (QQ)P TP T 故故 (PQ)PQ是重言式。是重言式。例例:用用等值演算判斷下列公式的類

55、型等值演算判斷下列公式的類型(條件等值式條件等值式)(條件等值式條件等值式)(德摩根律德摩根律)(德摩根律德摩根律)(分配律分配律)(排中律排中律)(同一律）同一律）(交換律，結(jié)合律）交換律，結(jié)合律）（排中律）（排中律）（零律）（零律）第一章第一章 命題邏輯命題邏輯(2) (2) (P(PQ)R (PPQ)R (PP Q)R (FQ)R FR F 故故 (P(PQ)R是矛盾式。是矛盾式。( (條件等值式，結(jié)合律）條件等值式，結(jié)合律） ( (德摩根律）德摩根律）( (矛盾律）矛盾律）( (零律零律) )( (零律）零律）第一章第一章 命題邏輯命題邏輯P(PQ)P)Q) P(PQ)P)Q) ( (

56、條件條件等值式等值式) ) P(PP)(QP)Q) ( (分配律分配律) ) P(0(QP)Q) ( (矛盾律矛盾律) ) P(QP)Q) ( (同一律同一律) ) P(QP)Q) ( (德摩根律，雙重否定律德摩根律，雙重否定律) ) P(QQ)P) ( (交換律，結(jié)合律交換律，結(jié)合律) ) P(TP) （排中律）（排中律） PT （零律）（零律） P （同一律）（同一律） 可見(jiàn)，（可見(jiàn)，（3 3）中公式不是重言式，因?yàn)椋┲泄讲皇侵匮允?，因?yàn)?000，01 01 都是成假賦值；都是成假賦值；它也不是矛盾式，因?yàn)樗膊皇敲苁?，因?yàn)?010，11 11 都是其成真賦值，故它是可滿足式。都是其成

57、真賦值，故它是可滿足式。第一章第一章 命題邏輯命題邏輯 任何兩個(gè)重言式的合取、析取，仍是一個(gè)重言式。任何兩個(gè)重言式的合取、析取，仍是一個(gè)重言式。 定理定理1：定理定理2： 1.5 1.5 重言式與蘊(yùn)含式重言式與蘊(yùn)含式 一個(gè)重言式，對(duì)同一分量都用任一合式公式置換，一個(gè)重言式，對(duì)同一分量都用任一合式公式置換，其結(jié)果仍為一重言式。其結(jié)果仍為一重言式。 第一章第一章 命題邏輯命題邏輯1、其否定為永假式；、其否定為永假式；2、其合、析取、（雙）條件都永真，可由簡(jiǎn)單、其合、析取、（雙）條件都永真，可由簡(jiǎn)單 推出復(fù)雜重言式；推出復(fù)雜重言式；3、其中有許多有用的恒等式和永真蘊(yùn)含式。、其中有許多有用的恒等式和永

58、真蘊(yùn)含式。 重言式有以下特點(diǎn)：重言式有以下特點(diǎn)： 1.5 1.5 重言式與蘊(yùn)含式重言式與蘊(yùn)含式 第一章第一章 命題邏輯命題邏輯設(shè)設(shè)A A、B B為兩命題公式，為兩命題公式，ABAB當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)ABAB為一重言式。為一重言式。定理定理3：定義定義3： 1.5 1.5 重言式與蘊(yùn)含式重言式與蘊(yùn)含式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P PQ Q是一個(gè)重言式時(shí)，我們稱是一個(gè)重言式時(shí)，我們稱“P P蘊(yùn)含蘊(yùn)含Q Q”：P=QP=Q。P PQ Q的的逆換式：逆換式：Q QP P； 反換式：反換式： P P Q Q； 逆反式：逆反式： Q Q P P。 第一章第一章 命題邏輯命題邏輯 在研究推理過(guò)程中，人們發(fā)現(xiàn)了一些重要

59、的重言蘊(yùn)含式，并將它在研究推理過(guò)程中，人們發(fā)現(xiàn)了一些重要的重言蘊(yùn)含式，并將它們作為推理定律，在推理過(guò)程中可直接引用。常用的推理定律（們作為推理定律，在推理過(guò)程中可直接引用。常用的推理定律（P21P21表表1-5.21-5.2蘊(yùn)含式蘊(yùn)含式）有：）有：(1)(1) 附加律附加律: A AB(2) 化簡(jiǎn)律化簡(jiǎn)律: AB A(3) 假言推理假言推理: (AB)A B(4) 拒取式拒取式: (AB)B A(5) 析取三段論析取三段論: (AB)B A(6) 假言三段論假言三段論: (AB)(BC) (AC)(7) 等價(jià)三段論等價(jià)三段論: (AB)(BC) (AC)(8) 構(gòu)造性二難構(gòu)造性二難: (AB)

60、(CD)(AC) (BD) 構(gòu)造性二難構(gòu)造性二難(特殊形式特殊形式): (AB)(AB)(AA) B(9) 破壞性二難破壞性二難: (AB)(CD)(BD)(AC)推理定律推理定律第一章第一章 命題邏輯命題邏輯 此外此外, 1 1.4中中給出的給出的24個(gè)個(gè)邏輯邏輯等等價(jià)價(jià)式中的每一個(gè)都派生出兩條推理式中的每一個(gè)都派生出兩條推理定律定律. 比如比如 A A產(chǎn)生出產(chǎn)生出AA 和和A A . 還有一些等還有一些等價(jià)價(jià)式和重言蘊(yùn)含式可在推理中引用式和重言蘊(yùn)含式可在推理中引用。如如:A (AB)(AB)(AB) ABA(BC) (AB) C(AB) (AB)(AB)(AB) ABA ABB ABAB