第九章命題邏輯

1、數(shù)理邏輯又稱符號(hào)邏輯、理論邏輯。數(shù)理邏輯又稱符號(hào)邏輯、理論邏輯。它既是數(shù)學(xué)的一個(gè)分支，也是邏輯學(xué)的它既是數(shù)學(xué)的一個(gè)分支，也是邏輯學(xué)的一個(gè)分支；是用數(shù)學(xué)的方法研究邏輯或一個(gè)分支；是用數(shù)學(xué)的方法研究邏輯或形式邏輯的學(xué)科。形式邏輯的學(xué)科。數(shù)理邏輯就是精確化、數(shù)學(xué)化的形式邏輯。數(shù)理邏輯就是精確化、數(shù)學(xué)化的形式邏輯。數(shù)理邏輯包括數(shù)理邏輯包括命題邏輯命題邏輯和和謂詞邏輯謂詞邏輯。它是現(xiàn)代計(jì)算機(jī)技術(shù)的基礎(chǔ)。它是現(xiàn)代計(jì)算機(jī)技術(shù)的基礎(chǔ)。它為機(jī)器證明、自動(dòng)程序設(shè)計(jì)、它為機(jī)器證明、自動(dòng)程序設(shè)計(jì)、計(jì)算機(jī)輔助設(shè)計(jì)等計(jì)算機(jī)應(yīng)用計(jì)算機(jī)輔助設(shè)計(jì)等計(jì)算機(jī)應(yīng)用提供必要的理論基礎(chǔ)。提供必要的理論基礎(chǔ)。第第9章章 命題邏輯命題邏輯例

2、例1 張三說(shuō)李四在說(shuō)謊張三說(shuō)李四在說(shuō)謊,李四說(shuō)王五在說(shuō)謊李四說(shuō)王五在說(shuō)謊, 王五說(shuō)張三和李四都在說(shuō)謊王五說(shuō)張三和李四都在說(shuō)謊. 問(wèn)問(wèn):誰(shuí)說(shuō)的是真話誰(shuí)說(shuō)的是真話? 例例2 有一倉(cāng)庫(kù)被盜有一倉(cāng)庫(kù)被盜,經(jīng)偵察確定甲經(jīng)偵察確定甲,乙乙,丙丙,丁丁 四人中四人中 的兩人作案的兩人作案,且可靠的線索有且可靠的線索有: (1) 甲甲,乙兩人中有且只有一個(gè)人去過(guò)倉(cāng)庫(kù)乙兩人中有且只有一個(gè)人去過(guò)倉(cāng)庫(kù); (2) 乙和丁不會(huì)同時(shí)去倉(cāng)庫(kù)乙和丁不會(huì)同時(shí)去倉(cāng)庫(kù); (3) 丙若去倉(cāng)庫(kù)丙若去倉(cāng)庫(kù),丁必定同去丁必定同去; (4) 丁若沒(méi)去倉(cāng)庫(kù)丁若沒(méi)去倉(cāng)庫(kù),則甲也沒(méi)去則甲也沒(méi)去. 判斷四人中哪兩人作案判斷四人中哪兩人作案?解答解答

3、:(1)李四說(shuō)真話李四說(shuō)真話; (2)作案者為甲和丁作案者為甲和丁.9.1 命題和命題聯(lián)結(jié)詞命題和命題聯(lián)結(jié)詞 一、一、命題的概念命題的概念 二、二、命題聯(lián)結(jié)詞和真值表命題聯(lián)結(jié)詞和真值表 三、命題的符號(hào)化三、命題的符號(hào)化 四、四、命題公式命題公式 1.命題的定義命題的定義 能夠確定或分辨其真假的陳述句能夠確定或分辨其真假的陳述句, 且真與假必居其一。且真與假必居其一。 簡(jiǎn)言之簡(jiǎn)言之,命題是非真即假的陳述句命題是非真即假的陳述句。 2.命題的真值命題的真值 命題是真就說(shuō)其真值為真命題是真就說(shuō)其真值為真,用用“1”表示，表示， 命題是假就說(shuō)其真值為假命題是假就說(shuō)其真值為假,用用“0”表示。表示。 真

4、值為真的命題稱為真命題真值為真的命題稱為真命題, 真值為假的命題稱假命題。真值為假的命題稱假命題。一、命題的概念一、命題的概念 3.說(shuō)明說(shuō)明：判斷命題應(yīng)注意以下幾點(diǎn)判斷命題應(yīng)注意以下幾點(diǎn) (1) 那些那些“自稱謂自稱謂”的陳述句可能產(chǎn)生自相矛盾的的陳述句可能產(chǎn)生自相矛盾的 結(jié)論結(jié)論(悖論悖論),故不在討論之列故不在討論之列. 例如：我現(xiàn)在說(shuō)真話例如：我現(xiàn)在說(shuō)真話. (2) “很難很難”,“相當(dāng)年輕相當(dāng)年輕”等這些概念等這些概念 沒(méi)有清晰的界限沒(méi)有清晰的界限,屬于模糊概念屬于模糊概念,故不在討論之列故不在討論之列. 例如：這個(gè)題目很難例如：這個(gè)題目很難. (3) 某些命題尚未確定其真值某些命題尚

5、未確定其真值. 例如：火星上存在有生命的物種例如：火星上存在有生命的物種. (4) 某些命題可能無(wú)法查明其真值某些命題可能無(wú)法查明其真值. 例如例如: 公元公元1014年元旦北京下過(guò)雨年元旦北京下過(guò)雨. (5) 命題真假會(huì)因時(shí)因地而異命題真假會(huì)因時(shí)因地而異. 例如例如: 現(xiàn)在是上午現(xiàn)在是上午. 例例1 判斷下列句子是否是命題判斷下列句子是否是命題 (1) 4是素?cái)?shù)是素?cái)?shù). (2) 是無(wú)理數(shù)是無(wú)理數(shù). (3) 月球上有水月球上有水. (4) 大于大于2嗎嗎 (5) 請(qǐng)不要吸煙！請(qǐng)不要吸煙！ (6) 這朵花真美麗啊！這朵花真美麗??！ (7) x大于大于y. -是假命題是假命題-是真命題是真命題-是

6、真命題是真命題-不是命題不是命題-不是命題不是命題-不是命題不是命題-不是命題不是命題4.命題的表示命題的表示一般用大寫(xiě)的英文字母表示一個(gè)最簡(jiǎn)單命題。一般用大寫(xiě)的英文字母表示一個(gè)最簡(jiǎn)單命題。例如例如：P： 我是學(xué)生。我是學(xué)生。Q： 我明天要上學(xué)。我明天要上學(xué)。 1.原子命題原子命題 再細(xì)分不成為句子的命題稱為再細(xì)分不成為句子的命題稱為原子命題原子命題。 例如例如: “明天下雪明天下雪”和和“7是素?cái)?shù)是素?cái)?shù)” 都是原子命題。都是原子命題。 2.復(fù)合命題復(fù)合命題 原子命題常可通過(guò)一些原子命題?？赏ㄟ^(guò)一些命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞 構(gòu)成新命題構(gòu)成新命題,這種命題稱為這種命題稱為復(fù)合命題復(fù)合命題。 例如例如

7、: “明天下雪或下雨明天下雪或下雨”； “明天下雨并且下雪明天下雨并且下雪”; “如果明天下雨如果明天下雨,我就不去游泳我就不去游泳”等，等， 都是復(fù)合命題。都是復(fù)合命題。 二、二、 命題的類型命題的類型 1.命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞: 又稱邏輯運(yùn)算符號(hào)，又稱邏輯運(yùn)算符號(hào)， 是通常語(yǔ)言里的連接詞的邏輯抽象。是通常語(yǔ)言里的連接詞的邏輯抽象。 常用的命題聯(lián)結(jié)詞有五種常用的命題聯(lián)結(jié)詞有五種: 否定、合取、析取、蘊(yùn)涵、等值否定、合取、析取、蘊(yùn)涵、等值三、命題聯(lián)結(jié)詞三、命題聯(lián)結(jié)詞 注注: P為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P為假。為假。 P的真值表：的真值表：P PP P假假真真真真假假P P P P 1 0 0

8、1 設(shè)設(shè)P為命題為命題,那么那么“對(duì)對(duì)P的否定的否定”為另一命為另一命題。題。 表示為表示為P,叫做叫做P的的否定否定,讀做讀做“非非P”。2. 五種聯(lián)結(jié)詞五種聯(lián)結(jié)詞 例例2 設(shè)設(shè)P: 3是素?cái)?shù)是素?cái)?shù); 則則P: 3不是素?cái)?shù)。不是素?cái)?shù)。 1) 否定否定 （ ） 設(shè)設(shè)Q: 這些都是男生這些都是男生; 則則Q:這些都不是男生。這些都不是男生。設(shè)設(shè)P,Q為命題為命題,那么那么“P并且并且Q”為一復(fù)合命題為一復(fù)合命題,表示為表示為PQ,叫做叫做P和和Q的的合取合取,讀做讀做“P且且Q”。注注: PQ為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P和和Q同為真。同為真。 PQ的的真值表：真值表：P Q P Q P PQQ0

9、00 00 10 11 01 01 11 10 00 00 01 1 例例3 設(shè)設(shè)P: 2是素?cái)?shù)是素?cái)?shù), Q: 2是偶數(shù)是偶數(shù); 則則PQ: 2是素?cái)?shù)是素?cái)?shù),并且是偶數(shù)并且是偶數(shù) 2) 合?。ê先。?）3） 析?。ㄎ鋈。?） 設(shè)設(shè)P,Q為命題為命題,那么那么“P或者或者Q”為一復(fù)合命題為一復(fù)合命題, 表示為表示為PQ,叫做叫做P和和Q的的析取析取, 讀做讀做“P或或Q”。 注注: PQ為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P和和Q至少一個(gè)為真。至少一個(gè)為真。 PQ的的真值表：真值表：P Q P Q P PQQ0 00 00 10 11 01 01 11 10 01 11 11 1 例例4 設(shè)設(shè)P: 張三愛(ài)唱

10、歌張三愛(ài)唱歌, Q: 張三愛(ài)聽(tīng)張三愛(ài)聽(tīng) 音樂(lè)音樂(lè); 則則PQ: 張三愛(ài)唱歌或愛(ài)聽(tīng)音樂(lè)。張三愛(ài)唱歌或愛(ài)聽(tīng)音樂(lè)。思考思考: 張明下午在寢室或在圖書(shū)館。張明下午在寢室或在圖書(shū)館。 “或或”:可兼或和排斥或（不可兼或）?？杉婊蚝团懦饣颍ú豢杉婊颍?。 (PQ)(PQ)表示排斥或表示排斥或, 表示表示P和和Q不能同時(shí)發(fā)生。不能同時(shí)發(fā)生。 4) 蘊(yùn)含（條件）（蘊(yùn)含（條件）（ ） 設(shè)設(shè)P,Q為命題為命題,則則“如果如果P就就Q”為一復(fù)合命題為一復(fù)合命題, 表示為表示為PQ, 讀做讀做“若若P則則Q”。 這里這里, P叫做叫做前提前提,假設(shè)假設(shè)或或前件前件; Q叫做叫做結(jié)論或后件結(jié)論或后件。 注注: PQ為假當(dāng)

11、且僅當(dāng)為假當(dāng)且僅當(dāng)P為真而為真而Q為假。為假。 PQ的的真值表：真值表：P Q P Q P PQ Q0 00 00 10 11 01 01 11 11 11 10 01 1PQ的邏輯關(guān)系的邏輯關(guān)系: Q是是P的必要條件的必要條件, P是是Q的充分條件。的充分條件。若若P,則則Q； 如果如果P,那么那么Q； 因?yàn)橐驗(yàn)镻,所以所以Q。 例例:如果如果(因?yàn)橐驗(yàn)?我有課我有課,那么那么(所以所以)我去教室。我去教室。 Q每當(dāng)每當(dāng)P； P僅當(dāng)僅當(dāng)Q。 例例:每當(dāng)有課我去教室。我去教室僅當(dāng)我有課。每當(dāng)有課我去教室。我去教室僅當(dāng)我有課。只要只要P,就就Q； 只有只有P才才Q 。 例例: 只要只要(只有只有

12、)我有課我有課,我就我就(才才)去教室。去教室。除非除非Q才才P； 除非除非Q,否則非否則非P。 例例:除非我有課除非我有課,我才我才(否則我不否則我不)去教室。去教室。說(shuō)明：說(shuō)明：注注1 在數(shù)理邏輯中在數(shù)理邏輯中,“如果如果P,那么那么Q”中的中的 前件前件P與后件與后件Q可以無(wú)任何內(nèi)在聯(lián)系?？梢詿o(wú)任何內(nèi)在聯(lián)系。 例如：例如： “若若6是偶數(shù)，則明天下雨是偶數(shù)，則明天下雨”。注注2 在數(shù)理邏輯中在數(shù)理邏輯中,作為一種規(guī)定作為一種規(guī)定, 當(dāng)當(dāng)P為假時(shí)為假時(shí),無(wú)論無(wú)論Q是真是假是真是假,PQ均為真。均為真。例例5 張三對(duì)李四說(shuō)張三對(duì)李四說(shuō): “我去書(shū)店一定幫你買那本書(shū)我去書(shū)店一定幫你買那本書(shū)”。

13、 設(shè)設(shè)P:張三去書(shū)店張三去書(shū)店; Q:張三買那本書(shū)張三買那本書(shū); 則可以將這句話表示為命題則可以將這句話表示為命題:PQ. 5) 等值（雙條件）（等值（雙條件）（ ） 設(shè)設(shè)P,Q為命題為命題,則則“P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q”為復(fù)合命題為復(fù)合命題,表示為表示為PQ,讀做讀做“P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q”。 PQ也可讀做也可讀做“P是是Q的充要條件的充要條件”。 注注: PQ為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)P和和Q同為真或同為假。同為真或同為假。 或當(dāng)且僅當(dāng)或當(dāng)且僅當(dāng)PQ和和QP都為真都為真,PQ的真值表的真值表: P Q P Q P PQ Q0 00 00 10 11 01 01 11 11 10 00 01 1

14、 例例6: 設(shè)設(shè)P: 我去游泳我去游泳, Q: 天下雨天下雨; 則則PQ: 我去游泳當(dāng)且僅當(dāng)天不下雨。我去游泳當(dāng)且僅當(dāng)天不下雨。3.命題的符號(hào)化命題的符號(hào)化 符號(hào)化應(yīng)注意以下幾點(diǎn)符號(hào)化應(yīng)注意以下幾點(diǎn): (1)確定語(yǔ)句是否為命題確定語(yǔ)句是否為命題,不是就不必翻譯。不是就不必翻譯。 (2)確定語(yǔ)句中的連接詞是否能對(duì)應(yīng)于并且確定語(yǔ)句中的連接詞是否能對(duì)應(yīng)于并且 對(duì)應(yīng)于哪一個(gè)命題聯(lián)結(jié)詞對(duì)應(yīng)于哪一個(gè)命題聯(lián)結(jié)詞; (3)正確表示原子命題和選擇命題聯(lián)結(jié)詞正確表示原子命題和選擇命題聯(lián)結(jié)詞; (5)原子命題一般表示成肯定。原子命題一般表示成肯定。 (4)要按邏輯關(guān)系翻譯而不能憑字面翻譯。要按邏輯關(guān)系翻譯而不能憑字

15、面翻譯。例例7 將下列命題符號(hào)化將下列命題符號(hào)化: (1) 他有理論知識(shí)但無(wú)實(shí)踐經(jīng)驗(yàn)。他有理論知識(shí)但無(wú)實(shí)踐經(jīng)驗(yàn)。 (2) 小張是計(jì)算機(jī)學(xué)院的學(xué)生，小張是計(jì)算機(jī)學(xué)院的學(xué)生， 他住在他住在8號(hào)樓號(hào)樓202室或室或203室。室。 (3) 又大又紅的蘋(píng)果我才會(huì)買。又大又紅的蘋(píng)果我才會(huì)買。 (4) 如果小王和小張都不去如果小王和小張都不去,則小李去。則小李去。 (5) 如果小王和小張不都去如果小王和小張不都去,則小李去。則小李去。 PQ(PQ)R(PQ)R(PQ)RP(QR)(QR)9.2 命題公式命題公式 1.命題變?cè)}變?cè)? 如果如果P代表真值未指定的任意命題代表真值未指定的任意命題, 就稱就稱P

16、為為命題變?cè)}變?cè)?2. 命題常元命題常元: 如果如果P代表真值已指定的命題代表真值已指定的命題, 就稱就稱P為為命題常元命題常元.(1和和0稱為命題常元稱為命題常元) 3. 原子公式原子公式:單個(gè)命題變?cè)兔}常元單個(gè)命題變?cè)兔}常元.一、命題變?cè)?、命題變?cè)?常元）常元） 定義定義 遞歸定義遞歸定義命題公式命題公式: (1) 0和和1是命題公式是命題公式; (2)命題變?cè)敲}公式命題變?cè)敲}公式; (3)如果如果A是命題公式是命題公式,則則A是命題公式是命題公式; (4)如果如果A和和B是命題公式是命題公式, 則則AB,AB, AB,AB是命題公式是命題公式; (5)只有有限次利用

17、上述只有有限次利用上述(1)(2)(3)(4) 而產(chǎn)生的符號(hào)串才是命題公式。而產(chǎn)生的符號(hào)串才是命題公式。二、命題公式二、命題公式 例例1 下面的符號(hào)串不是公式下面的符號(hào)串不是公式 PQP, RP, PP, (PQR)QR). 下面的符號(hào)串是公式下面的符號(hào)串是公式 (PQ)(PR), (P(QR)(QR). 定義定義 設(shè)設(shè)P1,P2,Pn是出現(xiàn)在命題公式是出現(xiàn)在命題公式 F中的全部命題變?cè)械娜棵}變?cè)? 給給P1,P2,Pn各指定一個(gè)真值各指定一個(gè)真值(真或假真或假), 稱為對(duì)稱為對(duì)F的一個(gè)的一個(gè)真值指派真值指派(賦值或解釋賦值或解釋)。 思考思考:含有含有n個(gè)命題變?cè)拿}公式個(gè)命題變?cè)?/p>

18、命題公式F 有多少種真值指派有多少種真值指派? 三、公式的真值指派（賦值）三、公式的真值指派（賦值）四、公式的真值表四、公式的真值表用表格的形式來(lái)反映公式在所有不同的用表格的形式來(lái)反映公式在所有不同的真值指派下與其命題變?cè)g的真值關(guān)系，真值指派下與其命題變?cè)g的真值關(guān)系，這樣的表格稱為公式的這樣的表格稱為公式的真值表真值表。 定義定義 設(shè)設(shè)A為任一命題公式為任一命題公式: (1) 若公式若公式A在它的各種賦值下取值均為真在它的各種賦值下取值均為真, 則稱公式則稱公式A 是是重言式重言式或或永真式永真式; (2) 若公式若公式A在它的各種賦值下取值均為假在它的各種賦值下取值均為假, 則稱公式

19、是則稱公式是矛盾式矛盾式或或永假式永假式; (3) 若至少有一組真值指派使公式若至少有一組真值指派使公式 A的值為真，的值為真， 則稱公式則稱公式A是是可滿足式可滿足式。五、公式的類型五、公式的類型9.3 命題公式的等值關(guān)系和蘊(yùn)含關(guān)系命題公式的等值關(guān)系和蘊(yùn)含關(guān)系 1.定義定義 設(shè)設(shè)A和和B是兩個(gè)命題公式是兩個(gè)命題公式, 若公式若公式AB為重言式為重言式, 則稱公式則稱公式A和和B是等值的公式是等值的公式,記為記為AB。 注注: (1) 當(dāng)且僅當(dāng)在所有真值指派下，當(dāng)且僅當(dāng)在所有真值指派下， 公式公式A和和B的真值完全相同時(shí)的真值完全相同時(shí), 公式公式A和和B才是兩個(gè)等值的公式。才是兩個(gè)等值的公式

20、。 (2) AB是表示一個(gè)公式，是表示一個(gè)公式， 而而AB是表示兩公式是表示兩公式A和和B的關(guān)系是等值。的關(guān)系是等值。一、一、 命題公式的等值關(guān)系命題公式的等值關(guān)系 1）自反性：）自反性： AA。 2）對(duì)稱性：）對(duì)稱性： 若若 AB 則則 BA。 3) 傳遞性：傳遞性： 若若AB,BC,則則AC。 2. 等值關(guān)系的性質(zhì)等值關(guān)系的性質(zhì)等值關(guān)系是一個(gè)等價(jià)關(guān)系。等值關(guān)系是一個(gè)等價(jià)關(guān)系。 3.證明邏輯恒等式證明邏輯恒等式AB的方法的方法: (1) 利用真值表利用真值表: 證明公式證明公式AB為重言式。為重言式。 例例1 證明：德證明：德.摩根定律摩根定律(PQ) PQ證明證明: 公式公式(PQ) )

21、(PQ )真值表：真值表：P QP QPQPQ(PQ)(PQ)P PQ Q( (PQ) )(PQ) )( (PPQ)Q)0 00 00 10 11 01 01 11 10 01 11 11 11 10 00 00 01 10 00 00 01 11 11 11 1 從真值表可得：從真值表可得： (PQ) PQ。 1)代入規(guī)則代入規(guī)則: 重言式中某命題變?cè)霈F(xiàn)的每一處重言式中某命題變?cè)霈F(xiàn)的每一處 均代以同一命題公式后所得命題公式均代以同一命題公式后所得命題公式 (代入實(shí)例代入實(shí)例)仍為重言式。仍為重言式。 如：如： 在在P(PQ)P中以中以(RP)代代P得得 (RP)(RP)Q)(RP) 在在

22、PQQP中以中以C代代P,同時(shí)以同時(shí)以(AB)代代Q得得 C(AB)(AB)C (2) 等值演算：等值演算： a) 常用的等值式常用的等值式 b) 兩個(gè)規(guī)則兩個(gè)規(guī)則 2) 2) 定義定義 若若C是公式是公式A中的一部分且中的一部分且C為公式為公式, 則稱則稱C為為A的的子公式子公式。 例例: PQ和和PR是公式是公式PQPR 的子公式。的子公式。 3) 替換規(guī)則替換規(guī)則: 若若C是是A的子公式的子公式,且且CD。 如果將公式如果將公式A中的子公式中的子公式C， 置換成公式置換成公式D之后之后,得到公式得到公式B, 則則AB。 1.定義定義 設(shè)設(shè)A和和B是兩個(gè)公式是兩個(gè)公式, 若公式若公式AB是

23、重言式是重言式,即即AB1, 則稱公式則稱公式A蘊(yùn)含公式蘊(yùn)含公式B,記作記作AB。 2.蘊(yùn)含關(guān)系的性質(zhì)蘊(yùn)含關(guān)系的性質(zhì) 二、命題公式的蘊(yùn)含關(guān)系二、命題公式的蘊(yùn)含關(guān)系 自反性：自反性： AA. 反對(duì)稱性：若反對(duì)稱性：若AB,BA,則則AB. 傳遞性：傳遞性： 若若AB,BC,則則AC.蘊(yùn)含關(guān)系是一個(gè)偏序關(guān)系。蘊(yùn)含關(guān)系是一個(gè)偏序關(guān)系。 (2) 演繹推理：演繹推理： a）證明）證明A為真時(shí)為真時(shí)B為真為真. b) 證明證明B為假時(shí)為假時(shí)A為假。為假。 3.證明永真蘊(yùn)涵式證明永真蘊(yùn)涵式AB的方法的方法:(1) 利用真值表利用真值表: 證明公式證明公式AB為重言式。為重言式。 例例1 證明證明 (PQ)Q

24、 P。 證明證明:設(shè)設(shè) (PQ)Q為真為真, 則則 PQ和和Q同為真同為真; 因此因此Q為假為假;從而從而P為假為假; 所以所以P為真。為真。 例例2 證明證明(PQ)(QR) PR。 證明證明:設(shè)設(shè) PR為假為假, 則則P為真而為真而R為假為假; 對(duì)對(duì)Q分兩種情況討論分兩種情況討論: (a) 若若Q為真為真,則因則因R為假為假,故故QR為假為假; (b) 若若Q為假為假,則因則因P為真為真,故故PQ為假為假; 則則(PQ)(QR)為假。為假。9.4 范式范式 一、質(zhì)合取式與質(zhì)析取式一、質(zhì)合取式與質(zhì)析取式 二、二、析取范式與合取范式析取范式與合取范式 三、最三、最小項(xiàng)與最大項(xiàng)小項(xiàng)與最大項(xiàng) 四、

25、主析取范式與主合取范式四、主析取范式與主合取范式 定義定義1 一個(gè)由命題變?cè)蛎}變?cè)姆穸ㄒ粋€(gè)由命題變?cè)蛎}變?cè)姆穸?所組成的所組成的合取式合取式稱為稱為質(zhì)合取式質(zhì)合取式。 定義定義2 一個(gè)由命題變?cè)蛎}變?cè)姆穸ㄒ粋€(gè)由命題變?cè)蛎}變?cè)姆穸?所組成的所組成的析取式析取式稱為稱為質(zhì)析取式質(zhì)析取式。 如：設(shè)如：設(shè)P和和Q是兩個(gè)命題變?cè)莾蓚€(gè)命題變?cè)? 則則P, PQ,PQ, PQ都是質(zhì)合取式都是質(zhì)合取式, 而而 Q,PQ, PQ, PQ都是質(zhì)析取式。都是質(zhì)析取式。 一、質(zhì)合（析）取式一、質(zhì)合（析）取式1.質(zhì)合（析）取式的定義質(zhì)合（析）取式的定義 (1) 質(zhì)合取式為矛盾式質(zhì)合取式為矛盾式

26、的充分必要條件是的充分必要條件是, 它同時(shí)包含某個(gè)命題變?cè)瑫r(shí)包含某個(gè)命題變?cè)狿及其否定及其否定P。 (2) 質(zhì)析取式為重言式質(zhì)析取式為重言式的充分必要條件是的充分必要條件是, 它同時(shí)包含某個(gè)命題變?cè)瑫r(shí)包含某個(gè)命題變?cè)狿及其否定及其否定P。2.定理定理 定義定義3 一個(gè)由一個(gè)由質(zhì)合取式質(zhì)合取式的的析取析取所組成的公式所組成的公式, 稱為稱為析取范式析取范式, 即該公式具有形式即該公式具有形式: A1A2 An(n1) 其中其中A1,A2,An都是質(zhì)合取式。都是質(zhì)合取式。 定義定義4一個(gè)由一個(gè)由質(zhì)析取式質(zhì)析取式的的合取合取所組成的公式所組成的公式, 稱為稱為合取范式合取范式, 即該公式具有

27、形式即該公式具有形式: A1A2 An(n1) 其中其中A1,A2,An都是質(zhì)析取式。都是質(zhì)析取式。 如：如： P(PQ)(QR) 為析取范式。為析取范式。 (PQR)(QR) Q 為合取范式。為合取范式。二、二、 析（合）取范式析（合）取范式1. 析（合）取范式的定義析（合）取范式的定義 3.定理定理:對(duì)于任何命題公式對(duì)于任何命題公式A都存在都存在 與其等值的析取范式和合取范式。與其等值的析取范式和合取范式。 4.求求與與A邏輯等價(jià)的析取范式和合取范式的方法邏輯等價(jià)的析取范式和合取范式的方法: (1) 用蘊(yùn)涵表達(dá)式和等值表達(dá)式消去用蘊(yùn)涵表達(dá)式和等值表達(dá)式消去 公式公式A中的中的和和 聯(lián)結(jié)詞聯(lián)

28、結(jié)詞; (2) 用雙重否定律和德用雙重否定律和德 摩根律將摩根律將A中的中的都消去都消去 或移到命題變?cè)盎蛞频矫}變?cè)? (3) 用結(jié)合律和分配律將公式化成析取范式用結(jié)合律和分配律將公式化成析取范式 或合取范式?；蚝先》妒?。 例例1 求公式：求公式：(PQ)P的析取范式的析取范式 與合取范式。與合取范式。 解解:公式公式 (PQ)P(PQ)P (析取范式析取范式) (PP)(QP) (合取范式合取范式) P(PQ) (合取范式合取范式) n*ii=1Pn*ii= 1P*iP三、三、 最?。ù螅╉?xiàng)最?。ù螅╉?xiàng) 定義定義5 思考思考:含含n個(gè)變?cè)淖钚№?xiàng)和最大項(xiàng)的個(gè)數(shù)？個(gè)變?cè)淖钚№?xiàng)和最大

29、項(xiàng)的個(gè)數(shù)？設(shè)有個(gè)設(shè)有個(gè)n命題變?cè)}變?cè)狿1,P2,Pn, 形如形如P1,P2,Pn所產(chǎn)生的所產(chǎn)生的最大項(xiàng)最大項(xiàng)。的命題公式稱為由命題變?cè)拿}公式稱為由命題變?cè)稳缍稳绲拿}公式稱由命題變?cè)拿}公式稱由命題變?cè)狿1,P2,Pn所產(chǎn)生的所產(chǎn)生的最小項(xiàng)最小項(xiàng)。其中每個(gè)其中每個(gè) 或?yàn)榛驗(yàn)镻i, 或?yàn)榛驗(yàn)镻i ，即即Pi、Pi 必出現(xiàn)一個(gè)，且只能出現(xiàn)一個(gè)。必出現(xiàn)一個(gè)，且只能出現(xiàn)一個(gè)。最小項(xiàng)最小項(xiàng)最大項(xiàng)最大項(xiàng)公式公式成成真真賦值賦值編編號(hào)號(hào)公式公式成成假假賦值賦值編編號(hào)號(hào)PPQ QP QP Q P PQ Q P Q P Q0000010110101111m00m01m10m11 P Q P Q

30、P PQ QP QP QPPQ Q0000010110101111M00M01M10M11 含含2個(gè)命題變?cè)獋€(gè)命題變?cè)狿,Q的最小項(xiàng)和最大項(xiàng)的最小項(xiàng)和最大項(xiàng)最小項(xiàng)最小項(xiàng)最大項(xiàng)最大項(xiàng)公式公式成成真真賦值賦值編號(hào)編號(hào)公式公式成成假假賦值賦值編號(hào)編號(hào)PPQQR RPPQ RQ RP QP QR RP Q RP Q R P PQQR R P PQ RQ R P Q P QR R P Q R P Q R000000001001010010011011100100101101110110111111m000m001m010m011m100m101m110m111 P Q R P Q R P Q P QR

31、R P PQ RQ R P PQQR RP Q RP Q RP QP QR RPPQ RQ RPPQQR R000000001001010010011011100100101101110110111111M000M001M010M011M100M101M110M111 含含3個(gè)命題變?cè)獋€(gè)命題變?cè)狿,Q,R的最小項(xiàng)和最大項(xiàng)的最小項(xiàng)和最大項(xiàng) 1.定義定義 由不同的最小項(xiàng)所組成的析取式由不同的最小項(xiàng)所組成的析取式, 稱為稱為主析取范式主析取范式。 由不同的最大項(xiàng)所組成由不同的最大項(xiàng)所組成 的合取式的合取式, 稱為稱為主合取范式主合取范式。 四、四、 主析（合）取范式主析（合）取范式任何非重言式都有唯

32、一的主合取范式。任何非重言式都有唯一的主合取范式。 重言式重言式無(wú)主合取范式，定義為無(wú)主合取范式，定義為“1”。2. 定理定理 3. 定理定理 任何非矛盾式都有唯一的主析取范式。任何非矛盾式都有唯一的主析取范式。 矛盾式矛盾式無(wú)主析取范式，定義為無(wú)主析取范式，定義為“0”。 矛盾式矛盾式主合取范式必是所有最大項(xiàng)的合取。主合取范式必是所有最大項(xiàng)的合取。 重言式重言式主析取范式必是所有最小項(xiàng)的析取。主析取范式必是所有最小項(xiàng)的析取。 a. 利利用用真值表法求主析真值表法求主析(合合)取范式取范式: (1) 求主析取范式考慮真值表中對(duì)應(yīng)求主析取范式考慮真值表中對(duì)應(yīng)1的行的行 所有最小項(xiàng)的析取。所有最小

33、項(xiàng)的析取。 (2) 求主合取范式考慮真值表中對(duì)應(yīng)求主合取范式考慮真值表中對(duì)應(yīng)0的行的行 所有最大項(xiàng)的合取。所有最大項(xiàng)的合取。 4. 求命題公式主析求命題公式主析(合合)取范式的方法取范式的方法 例例2 用真值表求公式用真值表求公式(PQ)Q的主析的主析(合合)取范式。取范式。 P QP QPQPQ(PQ)Q(PQ)Q0 00 00 10 11 01 01 11 11 11 10 01 10 01 10 01 1考慮真值表為真的行考慮真值表為真的行,得公式的主析取范式：得公式的主析取范式：(PQ)(PQ)考慮真值表為假的行考慮真值表為假的行,得公式的主合取范式：得公式的主合取范式： (PQ) (

34、PQ) 。b. 利用等值演算求主析利用等值演算求主析(合合)取范式步驟取范式步驟:(1) 把給定命題公式化成析把給定命題公式化成析(合合)取范式取范式;(2) 刪除析刪除析(合合)取范式中所有為永假取范式中所有為永假(真真)的的 質(zhì)合取式質(zhì)合取式(質(zhì)析取式質(zhì)析取式);(3) 用等冪律將重復(fù)出現(xiàn)的變?cè)癁橐淮纬霈F(xiàn)用等冪律將重復(fù)出現(xiàn)的變?cè)癁橐淮纬霈F(xiàn);(4) 補(bǔ)進(jìn)析補(bǔ)進(jìn)析(合合)取范式中未出現(xiàn)的所有變?cè)》妒街形闯霈F(xiàn)的所有變?cè)?(5) 用等冪律消去重復(fù)出現(xiàn)的最小用等冪律消去重復(fù)出現(xiàn)的最小(大大)項(xiàng)。項(xiàng)。 例例3 求公式：求公式：(PQ)Q的主析取范式與主合取范式。的主析取范式與主合取范式。 解解:

35、 (PQ)Q (PQ)Q (P Q) (Q (P P) (P Q) (P Q) (P Q) (P Q) (P Q) (主合取范式主合取范式) 主析取范式主析取范式: (P Q) (P Q) 9.5 命題演算的推理理論命題演算的推理理論 一、推理規(guī)則一、推理規(guī)則 二、證明方法二、證明方法 1.定義定義 設(shè)設(shè)A和和B是兩個(gè)命題公式是兩個(gè)命題公式,如果如果AB, 即如果命題公式即如果命題公式AB為重言式為重言式, 則稱則稱B是前提是前提A的的結(jié)論結(jié)論或從或從A推出結(jié)論推出結(jié)論B。 一般地一般地,假設(shè)假設(shè)H1,H2,Hn和和C是一些命題是一些命題, 如果如果: H1H2Hn C 則稱從前提則稱從前提H

36、1,H2,Hn推出結(jié)論推出結(jié)論C, 有時(shí)候也記為有時(shí)候也記為H1,H2,Hn C， 并且稱并且稱H1,H2,Hn 為為C的的前提集合前提集合。 一、一、 有效推理的概念有效推理的概念 P QP Q P PQ Q P(PP(PQ)Q)Q QQ(PQ(PQ)Q)P P0 00 00 10 11 01 01 11 11 1 1 1 0 0 1 10 00 00 01 10 01 10 01 10 0 1 1 0 0 1 10 00 01 11 1例例1判斷結(jié)論判斷結(jié)論C能否可以從前提能否可以從前提H1和和H2推出推出 (1)H1: PQ, H2:P, C:Q (2)H1: PQ, H2:Q, C:P

37、解解:寫(xiě)出前提的合取式和結(jié)論的真值表寫(xiě)出前提的合取式和結(jié)論的真值表, 看是否出現(xiàn)前提合取式為真看是否出現(xiàn)前提合取式為真,而結(jié)論為假的情形。而結(jié)論為假的情形。 由真值表可得：由真值表可得：(1)可以，可以，(2)不行不行 例例2 判斷下列推理是否正確判斷下列推理是否正確: 若下午氣溫超過(guò)若下午氣溫超過(guò)30,則小王必去游泳則小王必去游泳; 若他去游泳若他去游泳,他就不去看電影了他就不去看電影了. 所以若小王沒(méi)去看電影所以若小王沒(méi)去看電影,下午氣溫必超過(guò)下午氣溫必超過(guò)30。 解解:設(shè)設(shè)P:下午氣溫超過(guò)下午氣溫超過(guò)30; Q:小王去游泳小王去游泳; R:小王去看電影小王去看電影. 則前提則前提:PQ,

38、QR; 結(jié)論結(jié)論:RP; 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu):(PQ)(QR)(RP) (PQ)(QR)(RP) (PQ)(QR)(RP) (PQ)(QR)(RP) PR 非永真非永真, 因此推理不正確。因此推理不正確。 1.定義：定義： 形式證明是一個(gè)描述推理過(guò)稱的命題序列。形式證明是一個(gè)描述推理過(guò)稱的命題序列。 其中每個(gè)命題或是已知的命題，其中每個(gè)命題或是已知的命題， 或是有某些前提所推得的結(jié)論。或是有某些前提所推得的結(jié)論。 序列中最后一個(gè)命題就是所要求的結(jié)論。序列中最后一個(gè)命題就是所要求的結(jié)論。 二、二、 形式證明的概念形式證明的概念 2. 推理規(guī)則：推理規(guī)則： (1) 前提引入規(guī)則前提引入規(guī)

39、則: 在證明的任何步驟上都可以引用前提。在證明的任何步驟上都可以引用前提。 (2) 結(jié)論引用規(guī)則結(jié)論引用規(guī)則: 在證明的任何步驟上所得到的結(jié)論，在證明的任何步驟上所得到的結(jié)論， 都可以在其后的證明中引用。都可以在其后的證明中引用。 (3) 置換規(guī)則置換規(guī)則: 在證明的任何步驟上在證明的任何步驟上,命題公式的子公式命題公式的子公式 都可以用與之等值的其他命題公式置換。都可以用與之等值的其他命題公式置換。 (4) 代入規(guī)則代入規(guī)則: 在證明的任何步驟上在證明的任何步驟上, 重言式中的任一命題變?cè)匮允街械娜我幻}變?cè)?都可以用一命題公式代入都可以用一命題公式代入,得到的仍是重言式。得到的仍是重言式

40、。 3.證明的有效性：證明的有效性： 定義定義 如果證明過(guò)程中的每一步所得到的結(jié)論如果證明過(guò)程中的每一步所得到的結(jié)論 都是根據(jù)推理規(guī)則得到的都是根據(jù)推理規(guī)則得到的, 則這樣的證明稱為是則這樣的證明稱為是有效的有效的。 通過(guò)有效的證明而得到的結(jié)論通過(guò)有效的證明而得到的結(jié)論, 稱為是稱為是有效的有效的 結(jié)論結(jié)論。 4.證明方法證明方法: 直接證明法和間接證明法。直接證明法和間接證明法。 直接證明法有兩種方法：直接證明法有兩種方法： PT規(guī)則和規(guī)則和CP規(guī)則規(guī)則 例例3 證明：證明： PQ,QR,PS, S R(PQ)。 證明證明: 編號(hào)編號(hào) 公式公式 依據(jù)依據(jù) (1) (2) (3) (4) (5) (6) (7) (8) PS S P PQ Q QR RR(PQ) P P T(1)(2) P T(3)(4) P T(5)(6) T(4)(7)a) PT規(guī)則規(guī)則例例4 證明證明下列推理的正確性：下列推理的正確性： 若這里有球賽若這里有球賽,則通行是困難的則通行是困難的; 若他們按時(shí)到達(dá)若他們按時(shí)到達(dá),則通行是不困難的則通行是不困難的; 他們按時(shí)到達(dá)了他們按時(shí)到達(dá)了, 所以這里沒(méi)有球賽。所以這里沒(méi)有球賽。解：設(shè)解：設(shè) P:這里有球賽這里有球賽; Q:通行是困難的通行是困難的;