最新數(shù)理邏輯是以數(shù)學(xué)的方法研究推理的形式結(jié)構(gòu)和

1、第第1章章 命題邏輯命題邏輯數(shù)理邏輯是以數(shù)學(xué)的方法研究推理的形式結(jié)數(shù)理邏輯是以數(shù)學(xué)的方法研究推理的形式結(jié)構(gòu)和規(guī)律的數(shù)學(xué)學(xué)科構(gòu)和規(guī)律的數(shù)學(xué)學(xué)科數(shù)學(xué)方法：建立一套符號(hào)來(lái)描述和討論問(wèn)題，避免歧義性推理：就是研究前提和結(jié)論之間的關(guān)系和思維規(guī)律，亦即符號(hào)之間的關(guān)系第第1章章 命題邏輯命題邏輯第第1章章 命題邏輯命題邏輯 1.1 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化及聯(lián)結(jié)詞1.2 命題公式及分類(lèi)命題公式及分類(lèi) 1.3 等值演算等值演算 1.4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 1.5 對(duì)偶與范式對(duì)偶與范式 1.6 推理理論推理理論 *1.7 命題演算的自然推理形式系統(tǒng)命題演算的自然推理形式系統(tǒng)n 1.8 例題選解例題

2、選解 習(xí)習(xí) 題題 一一第第1章章 命題邏輯命題邏輯1.1 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化及聯(lián)結(jié)詞 任何基于命題分析的邏輯稱(chēng)為命題邏輯。命題是研究思維規(guī)律的科學(xué)中的一項(xiàng)基本要素，它是一個(gè)判斷的語(yǔ)言表達(dá)。命題: 能唯一判斷真假的陳述句。第第1章章 命題邏輯命題邏輯 這種陳述句的判斷只有兩種可能，一種是正確的判斷，一種是錯(cuò)誤的判斷。如果某個(gè)陳述句的判斷為真（與人們公認(rèn)的客觀事實(shí)相符），則我們稱(chēng)其為一真命題，并說(shuō)此命題的，否則稱(chēng)為假命題，并說(shuō)此命題的。第第1章章 命題邏輯命題邏輯【例1.1.1】 下述各句均為命題：（1）4是偶數(shù)。（2）煤是白色的。（3）幾何原本的作者是歐幾里德。（4）2190年人類(lèi)將移

3、居火星。（5）地球外也有生命存在。第第1章章 命題邏輯命題邏輯 上述命題中（1）、（3）是真命題，（2）是假命題，其中的（3）可能有人說(shuō)不出它的真假，但客觀上能判斷真假。（4）的結(jié)果目前誰(shuí)也不知道，但到了時(shí)候則真假可辨，即其真值是客觀存在的，因而是命題。同樣，（5）的真值也是客觀存在的，只是我們地球人尚不知道而已，隨著科學(xué)技術(shù)的發(fā)展，其真值是可以知道的，因而也是命題。第第1章章 命題邏輯命題邏輯 【例1.1.2】 下列語(yǔ)句不是命題： （1）你好嗎？ （2）好棒??！ （3）請(qǐng)勿吸煙。 （4）x3。 （5）我正在說(shuō)謊。 （1）、（2）、（3）均不是陳述句，因而不是命題。（4）是陳述句，但它的真假取

4、決于變量x的取值，例如取x為4時(shí)其值為真，取x為2時(shí)其值為假，即其真值不唯一，因此不是命題。（5）也是陳述句，但它是悖論悖論，因而也不是命題。第第1章章 命題邏輯命題邏輯 從上面討論可以看出，判斷一個(gè)語(yǔ)句是否是命題的關(guān)鍵是： (1)語(yǔ)句必須是陳述句。 (2)陳述句必須具有唯一的真值。要注意兩點(diǎn)： 一個(gè)陳述句在客觀上能判斷真假，而不受人的知識(shí)范圍的限制。 一個(gè)陳述句暫時(shí)不能確定真值，但到了一定時(shí)候就可以確定，與一個(gè)陳述句的真值不能唯一確定是不同的。 第第1章章 命題邏輯命題邏輯 以上所討論的命題均是一些簡(jiǎn)單陳述句。在語(yǔ)言學(xué)中稱(chēng)為簡(jiǎn)單句，其結(jié)構(gòu)均具有“主語(yǔ)+謂語(yǔ)”的形式，在數(shù)理邏輯中，我們將這種由

5、簡(jiǎn)單句構(gòu)成的命題稱(chēng)為簡(jiǎn)單命題簡(jiǎn)單命題，或稱(chēng)為原子命題原子命題，用p、q、r、pi、qi、ri等符號(hào)表示（亦可用其它小寫(xiě)的英文字母表示）。如： p：4是偶數(shù)。 q：煤是白的。 r：幾何原本的作者是歐幾里德。第第1章章 命題邏輯命題邏輯【例1.1.3】 下列命題不是簡(jiǎn)單命題：（1）4是偶數(shù)且是2的倍數(shù)。（2）北京不是個(gè)小城市。（3）小王或小李考試得第一。（4）如果你努力，則你能成功。（5）三角形是等邊三角形，當(dāng)且僅當(dāng)三內(nèi)角相等。第第1章章 命題邏輯命題邏輯 上面的命題除（3）的真假需由具體情況客觀判斷外，余者的真值均為1。但是它們均不是簡(jiǎn)單命題，分別用了“且”、“非”、“或”、“如果則”、“當(dāng)且僅

6、當(dāng)”等聯(lián)結(jié)詞。 由命題和聯(lián)結(jié)詞構(gòu)成的命題稱(chēng)為復(fù)合復(fù)合命題命題。構(gòu)成復(fù)合命題的可以是原子命題，也可以是另一個(gè)復(fù)合命題。一個(gè)復(fù)合命題的真值不僅與構(gòu)成復(fù)合命題的命題的真值有關(guān)，而且也與所用聯(lián)結(jié)詞有關(guān)。下面我們給出幾個(gè)基本的聯(lián)結(jié)詞。第第1章章 命題邏輯命題邏輯 1.否定否定聯(lián)結(jié)詞 設(shè)p為任一命題，復(fù)合命題“非p”（p的否定）稱(chēng)為p的否定式，記作 。 為否定聯(lián)結(jié)詞。 為真，當(dāng)且僅當(dāng)p為假。 的真值亦可由表1.1.1所示的稱(chēng)為“真值表”的表格確定。由表1.1.1可知：命題p為真，當(dāng)且僅當(dāng) 為假。p ppp 表 1.1.1 p0110p第第1章章 命題邏輯命題邏輯【例1.1.4】 (1) p：4是偶數(shù)。其真

7、值為1。 ：4不是偶數(shù)。其真值為0。 (2) q：這些都是學(xué)生。 ：這些不都是學(xué)生。pq第第1章章 命題邏輯命題邏輯 注：否定聯(lián)結(jié)詞使用的原則：將真命題變成假命題，將假命題變成真命題。但這并不是簡(jiǎn)單的隨意加個(gè)不字就能完成的。例如上例中的（2），q的否定式就不能寫(xiě)成“這些都不是學(xué)生”。事實(shí)上嚴(yán)格來(lái)講，“不是”不一定否定“是”。如阿契貝難題：“本句是六字句”與“本句不是六字句”均是真命題。不過(guò)，一般地，自然語(yǔ)言中的“不”、“無(wú)”、“沒(méi)有”、“并非”等詞均可符號(hào)化為 .第第1章章 命題邏輯命題邏輯 2.合取合取聯(lián)結(jié)詞 “” 設(shè)p、q是任意兩個(gè)命題，復(fù)合命題“p且q”（p與q）稱(chēng)為p與q的合取式，記作

8、：pq。 “ ”是合取聯(lián)結(jié)詞。pq為真，當(dāng)且僅當(dāng)p、q均為真。 pq的真值表如表1.1.2所示。 表 1.1.2 p qpq0 0 00 101 001 11第第1章章 命題邏輯命題邏輯【例1.1.5】 (1) p：4是偶數(shù)。q：3是素?cái)?shù)。則 pq：4是偶數(shù)且3是素?cái)?shù)。其真值為1。 (2) r：煤是白的。則 pr：4是偶數(shù)且煤是白的。真值為0。 第第1章章 命題邏輯命題邏輯 3.析取析取聯(lián)結(jié)詞“” 設(shè)p、q是任意兩個(gè)命題，復(fù)合命題“p或q”稱(chēng)為p、q的析取式，記作：pq?！啊狈Q(chēng)為析取聯(lián)結(jié)詞。pq為假，當(dāng)且僅當(dāng)p、q同為假。 表 1.1.3 p qpq0 0 00 111 011 11第第1章章

9、 命題邏輯命題邏輯【例1.1.6】 (1) p：小王喜歡唱歌。 q：小王喜歡跳舞。則 pq：小王喜歡唱歌或喜歡跳舞。 (2) p：明天刮風(fēng)。 q：明天下雨。則 pq：明天刮風(fēng)或者下雨。第第1章章 命題邏輯命題邏輯 注 “”的邏輯關(guān)系是明確的。即p、q二命題中至少有一個(gè)為真則析取式為真。因而，自然語(yǔ)言中常用的聯(lián)結(jié)詞諸如：“或者或者”、“可能可能”等，都可以符號(hào)化為“”。但日常語(yǔ)言中的“或”是具有二義性的，用“或”聯(lián)結(jié)的命題有時(shí)是具有相容性的，如例1.1.6中的二例，我們稱(chēng)之為可兼或。而有時(shí)又具有排斥性，稱(chēng)為不可兼或（異或），如：（1）小李明天出差去上?；蛉V州。（2）劉昕這次考試可能是全班第一也

10、可能是全班第二。第第1章章 命題邏輯命題邏輯 4.蘊(yùn)含蘊(yùn)含聯(lián)結(jié)詞“” 設(shè)p、q是任意兩個(gè)命題，復(fù)合命題“如果p，則q”稱(chēng)為p與q的蘊(yùn)含式，記作：pq。p稱(chēng)為蘊(yùn)含式的前件，q稱(chēng)為蘊(yùn)含式的后件，稱(chēng)為蘊(yùn)含聯(lián)結(jié)詞。pq為假，當(dāng)且僅當(dāng)p為真、q為假。 表 1.1.4 p qp q0 0 10 111 001 11第第1章章 命題邏輯命題邏輯【例1.1.7】 (1) p：天下雨了。 q：路面濕了。則 pq：如果天下雨，則路面濕。 (2) r：三七二十一。則 pr：如果天下雨，則三七二十一。 第第1章章 命題邏輯命題邏輯 注 (1)邏輯中，前件p為假時(shí)，無(wú)論后件q是真是假，蘊(yùn)含式pq的真值均為1。這與日常語(yǔ)

11、言中的，特別是數(shù)學(xué)上常用的“真蘊(yùn)含真”不太一樣。事實(shí)上并不矛盾，例如某人說(shuō)：“如果張三能及格，那太陽(yáng)從西邊升起?！闭f(shuō)話(huà)者當(dāng)然知道“張三能及格”與“太陽(yáng)從西邊升起”風(fēng)馬牛不相及，而一般人此時(shí)并沒(méi)有說(shuō)謊的必要，即這是真命題，它所要明確的是“張三能及格”是假命題。第第1章章 命題邏輯命題邏輯 （2）正如前面所說(shuō)，數(shù)理邏輯中的聯(lián)結(jié)詞是對(duì)日常語(yǔ)言中的聯(lián)結(jié)詞的一種邏輯抽象，日常語(yǔ)言中聯(lián)結(jié)詞所聯(lián)結(jié)的句子之間是有一定內(nèi)在聯(lián)系的，但在數(shù)理邏輯中，聯(lián)結(jié)詞所聯(lián)結(jié)的命題可以毫無(wú)關(guān)系。如在日常語(yǔ)言中“如果則”所聯(lián)結(jié)的句子之間表現(xiàn)的是一種因果關(guān)系，如例1.1.7中的（1）。但在數(shù)理邏輯中，盡管說(shuō)前件蘊(yùn)涵后件，但兩個(gè)命題可

12、以是毫不相關(guān)的，如例1.1.7中的（2）。第第1章章 命題邏輯命題邏輯 （3）pq的邏輯關(guān)系是：p是q的充分條件，q是p的必要條件。在日常語(yǔ)言中，特別是在數(shù)學(xué)語(yǔ)言中，q是p的必要條件還有許多不同的敘述方式，如：“p僅當(dāng)q（僅當(dāng)q，則p）”、“只有q才p”、“只要p就q”、“除非q，否則非p（非p，除非q）”等，均可符號(hào)化成pq的形式。第第1章章 命題邏輯命題邏輯【例1.1.8】 符號(hào)化下列命題： （1）只要天下雨，我就回家。 （2）只有天下雨，我才回家。 （3）除非天下雨，否則我不回家。 （4）僅當(dāng)天下雨，我才回家。 解： 設(shè)p：天下雨。q：我回家。則（1）符號(hào)化為pq。（2）、（3）、（4）

13、均符號(hào)化為qp（或等價(jià)形式： ). pq第第1章章 命題邏輯命題邏輯 5.等價(jià)等價(jià)聯(lián)結(jié)詞“ ” 設(shè)p、q是任意兩個(gè)命題，復(fù)合命題“p當(dāng)且當(dāng)q”稱(chēng)為p與q的等價(jià)式，記作：p q。 “ ”稱(chēng)為等價(jià)聯(lián)結(jié)詞。p q為真，當(dāng)且僅當(dāng)p、q真值相同。p q的真值表如表1.1.5所示表 1.1.5 p qp q0 0 10 101 001 11第第1章章 命題邏輯命題邏輯 【例1.1.9】 (1)p：2+2=4。 q：5是素?cái)?shù)。則 p q：2+2=4當(dāng)且僅當(dāng)5是素?cái)?shù)。 (2)p：a=b。 q：二角是同位角。則 p q：a=b當(dāng)且僅當(dāng)二角是同位角。 在（1）中的p與q并無(wú)內(nèi)在關(guān)系，但因二者均為真，所以p q的真

14、值為1。 在（2）中由于相等的兩角不一定是同位角，所以真值為0。第第1章章 命題邏輯命題邏輯【例1.1.10】 將下列自然語(yǔ)言形式化:（1）如果天不下雨并且不刮風(fēng)，我就去書(shū)店。（2）小王邊走邊唱。（3）除非a能被2整除，否則a不能被4整除。（4）此時(shí)，小綱要么在學(xué)習(xí)，要么在玩游戲。（5）如果天不下雨，我們?nèi)ゴ蚧@球，除非班上有會(huì)。第第1章章 命題邏輯命題邏輯 解 （1）設(shè)p：今天天下雨，q：今天天刮風(fēng)，r：我去書(shū)店。則原命題符號(hào)化為： (2)設(shè)p：小王走路，q：小王唱歌。則原命題符號(hào)化為： pq (3)設(shè)p：a能被2整除，q：a能被4整除。則原命題符號(hào)化為： pqr pqqp或第第1章章 命題邏

15、輯命題邏輯 (4)設(shè)p：小剛在學(xué)習(xí)，q：小剛在玩游戲。則原命題符號(hào)化為：()()()() pqpqpqpq或 (5)設(shè)p：今天天下雨，q：我們?nèi)ゴ蚧@球，r：今天班上有會(huì)。則原命題符號(hào)化為：() rpq第第1章章 命題邏輯命題邏輯補(bǔ)充：補(bǔ)充：小明和小亮既是兄弟又是同學(xué)。pq如果你和他不都是白癡，則你倆都不會(huì)去干此傻事。無(wú)論你和他去不去，我去。)()(srqp)()()()(rqprqprqprqp第第1章章 命題邏輯命題邏輯1.2 命題公式及分類(lèi)命題公式及分類(lèi) 為了用數(shù)學(xué)的方法研究命題，就必須像數(shù)學(xué)處理問(wèn)題那樣將命題公式化，并討論對(duì)于這些公式的演算（推理）規(guī)則，以期由給定的公式推導(dǎo)出新的命題公式

16、來(lái)。第第1章章 命題邏輯命題邏輯 前面我們用p、q、r等符號(hào)表示確定的簡(jiǎn)單命題，通常此時(shí)稱(chēng)它們?yōu)槊}常元。而事實(shí)上，這些常元無(wú)論具體是怎樣的簡(jiǎn)單命題，它們的真值均只可能是“1”或“0”。為了更廣泛地應(yīng)用命題演算，在研究時(shí)，我們只考慮命題的“真”與“假”，而不考慮它的具體涵義（即只重“外延”，不顧“內(nèi)涵”）。譬如：當(dāng)p是一個(gè)真命題時(shí)， p就是一個(gè)假命題，而不管此時(shí)p表示的是命題“三七二十一”，還是命題“今天天下雨”。這時(shí)的p實(shí)際上就是一個(gè)簡(jiǎn)單命題的抽象，就如同數(shù)學(xué)公式中的變量x一樣，我們稱(chēng)其為命題變?cè)?。第?章章 命題邏輯命題邏輯命題常元 一個(gè)真值確定的命題命題變?cè)?一個(gè)真值尚未確定的命題，以p

17、、q、r等表之。注意：命題變?cè)皇敲}，沒(méi)有確定的真值，只有代以確定的命題，變成常元，才有真值第第1章章 命題邏輯命題邏輯 命題公式命題公式 由命題變?cè)ǔＴ┓?、?lián)結(jié)詞和圓括號(hào)按一定邏輯關(guān)系聯(lián)結(jié)起來(lái)的字符串。 所謂按一定的邏輯關(guān)系，即字符串的構(gòu)成要求合理，如（ p）是個(gè)合理的構(gòu)成，是命題，（p）不是合理的構(gòu)成，就不是命題公式，同樣（pq）r）也不是合理的構(gòu)成（括號(hào)必須成對(duì)出現(xiàn)），因此也不是命題公式。合理的命題公式叫做合式公式（亦稱(chēng)真值函數(shù)），記作： wff（wff=well-formed formulas）。第第1章章 命題邏輯命題邏輯定義定義1.2.1 合式公式的遞歸定義：合式公式的遞歸定

18、義：1單個(gè)的命題變?cè)ɑ虺Ｔ┦呛鲜焦健?如果a是一個(gè)合式公式，則（ a）也是合式公式。3如果a、b均是合式公式，則（ab）、（ab）、（ab）、 （a b）也都是合式公式。4有限次地應(yīng)用1,2,3組成的公式是合式公式。默認(rèn)聯(lián)結(jié)詞的優(yōu)先級(jí)：、第第1章章 命題邏輯命題邏輯 例如：（pq）r）、 均是合式公式。第3式的生成過(guò)程如下： p 1 q 1 （pq） 3 r 1 （qr） 3 （p） 2 (p) r) 3 (pq) (qr) 3 3 )()()(rprqqp)()(rqp)()()(rprqqp第第1章章 命題邏輯命題邏輯 定義1.2.2(1)若a是單個(gè)命題（變?cè)虺Ｔ?，則稱(chēng)為0層公式

19、。(2)稱(chēng)a為n+1（n0）層公式是指a符合下列諸情況之一 a= b，b是n層公式； a=bc，其中b為i層公式、c為j層公式， max（i，j）= n； a=bc，其中b、c的層次同； a=bc，其中b、c的層次同； a=b c，其中b、c的層次同。第第1章章 命題邏輯命題邏輯解釋?zhuān)褐付}變?cè)砟硞€(gè)具體的命題【例1.2.1】 公式：a=（pq）r。 解釋i1：假設(shè)p：現(xiàn)在是白天，q：現(xiàn)在是晴天，r：我們能看見(jiàn)太陽(yáng)。則 a：如果現(xiàn)在是白天且是晴天，則我們能看見(jiàn)太陽(yáng)。其真值為1。 解釋i2：假設(shè)p、q如上，r：我們能看見(jiàn)星星。則a：如果現(xiàn)在是白天且是晴天，則我們能看見(jiàn)星星。其真值為0。第第1

20、章章 命題邏輯命題邏輯 由此可見(jiàn)，不同的解釋解釋可使公式有不同的真值。事實(shí)上，對(duì)于命題變?cè)獰o(wú)論做什么樣的解釋?zhuān)贾挥袃煞N結(jié)果：或者是“真”，或者是“假”。從而由變?cè)吐?lián)結(jié)詞組成的公式所表示的復(fù)合命題，也是或?yàn)椤罢妗?，或?yàn)椤凹佟?。如前所述這才是我們所需要的。因此，欲獲取命題公式的真值，并非只有“解釋解釋”一個(gè)途徑，還可以通過(guò)“賦值”獲得。第第1章章 命題邏輯命題邏輯賦值（真值指派） 對(duì)命題變?cè)概纱_定的真值。賦值是一組由0、1構(gòu)成的數(shù)串，按字典順序（或下標(biāo)）對(duì)應(yīng)公式中的命題符。如例1.2.1中，對(duì)公式a=(pq）r：解釋 i1 實(shí)際上是對(duì)變?cè)猵、q、r賦值111，得a的真值為1；解釋 i2 實(shí)

21、際上是對(duì)變?cè)猵、q、r賦值110，得a的真值為0；a的真值是在對(duì)p、q、r的某種賦值下所得的真值。第第1章章 命題邏輯命題邏輯 定義1.2.3 設(shè)p1，p2，pn是公式a中所包含的所有命題變?cè)?，給p1，p2，pn各賦一個(gè)真值稱(chēng)為對(duì)a的一個(gè)賦值，那些使a的真值為1的賦值稱(chēng)為a的成真賦值成真賦值，使a的真值為0的賦值稱(chēng)為a的成成假賦值假賦值。 如例1.2.1中，111是a=（pq）r的成真賦值，110是a的成假賦值。根據(jù)前面對(duì)聯(lián)結(jié)詞的討論知：001、011、101、000、010也都是a的成真賦值。第第1章章 命題邏輯命題邏輯 問(wèn)題問(wèn)題 若公式a含有n（n1）個(gè)命題變?cè)?，那么?duì)a共有多少種不同的賦

22、值？答：因?yàn)閚個(gè)變?cè)x值后形成一個(gè)n位的二進(jìn)制數(shù)，所以共有2n個(gè)。 將公式a在所有賦值情況下的取值列成表，稱(chēng)為a的真值表真值表。第第1章章 命題邏輯命題邏輯構(gòu)造真值表的步驟如下： （1）找出命題公式中所含的所有命題變?cè)聪聵?biāo)或字典順序給出； （2）按從低到高的順序?qū)懗龈鲗哟危?（3）順序列出所有的賦值（2n個(gè)）；對(duì)應(yīng)每個(gè)賦值，計(jì)算命題公式各層次的真值，直到最后計(jì)算出命題公式的真值。第第1章章 命題邏輯命題邏輯 【例1.2.2】 求下列命題公式的真值表：(1)()(2)()()(3)() pqqpqpqpqr第第1章章 命題邏輯命題邏輯表1.2.1公式 的真值表如表1.2.1所示。 ()pqq

23、第第1章章 命題邏輯命題邏輯表 1.2.2 公式 的真值表 )()(qpqp第第1章章 命題邏輯命題邏輯 表 1.2.3 公式 的真值表如表1.2.3所示rqp)(第第1章章 命題邏輯命題邏輯 由上可知，有的公式在任何賦值情況下真值恒為1，如例1.2.2（1）；有的公式在任何賦值情況下真值恒為0，如例1.2.2（2）；有的公式某些賦值使其真值為1，而另一些賦值使其真值為0，因此可將公式分為如下三類(lèi)： 永真式永真式（重言式） 所有賦值均為成真賦值的公式。 永假式永假式（矛盾式） 所有賦值均為成假賦值的公式。 可滿(mǎn)足式可滿(mǎn)足式 至少有一組賦值是成真賦值的公式。 由定義可知，任何不是矛盾式的公式是可

24、滿(mǎn)足式，其中包含永真式第第1章章 命題邏輯命題邏輯補(bǔ)充：寫(xiě)出下列公式的真值表：)()()()()()()()()()()(rqprpqpsrqprqpqsrprqrprqprqp第第1章章 命題邏輯命題邏輯1.3 等值演算等值演算 【例1.3.1】 構(gòu)造公式 的真值表 解 公式 的真值表如表1.3.1所示。 qp )(qpqp pqqp )(qpqp pq第第1章章 命題邏輯命題邏輯 表 1.3.1 第第1章章 命題邏輯命題邏輯 由例題可見(jiàn)， 的真值表是完全相同的，這種情況并不是偶然的。事實(shí)上，給定n個(gè)命題變?cè)?，按照公式的生成?guī)則，我們可以得到無(wú)窮多個(gè)命題公式，但這無(wú)窮多個(gè)命題公式的真值表卻只

25、有有限個(gè)。如例1.3.1，許多公式在變?cè)母鞣N賦值下真值是一樣的，我們稱(chēng)其為等值的，那么如何判斷兩個(gè)公式等值呢？ qp )(qpqp pq第第1章章 命題邏輯命題邏輯 定義1.3.1 設(shè)a、b是任意兩個(gè)命題公式若等價(jià)式 a b為重言式，則稱(chēng)a與b是等值的，記作:a b。 定理1.3.1 a b為重言式，當(dāng)且僅當(dāng)a、b具有相同的真值表。 注 (1)如果a b不是重言式，則稱(chēng)a與b不等值，可記作：a b。 (2)“ ”與“=”不同，“a=b”表示二公式一樣，“a b”表示二公式真值一樣，第第1章章 命題邏輯命題邏輯 (3)“ ”與“ ”是兩個(gè)完全不同的符號(hào)?！?”是聯(lián)結(jié)詞，a b是一個(gè)公式。“ ”

26、不是聯(lián)結(jié)詞，而是兩個(gè)公式之間的關(guān)系符，a b并不是一個(gè)公式，而只是表示a與b是兩個(gè)真值相同的公式。 (4)“ ”的性質(zhì)： a a（自反性）； 若a b，則b a（對(duì)稱(chēng)性）； 若a b，b c，則a c（傳遞性）。第第1章章 命題邏輯命題邏輯利用真值表我們可以證明許多等值式：(1)雙重否定律 (2)冪等律 a aa a aa(3)交換律 ab ba ab ba(4)結(jié)合律 (ab)c a(bc) (ab)c a(bc)(5)分配律 a(bc) (ab)(ac) a(bc) (ab)(ac)(6)德摩根律 aa()() abababab第第1章章 命題邏輯命題邏輯(7)吸收律 (8)零律(9)同一

27、律aaaaaaabaaabaa100011)()(第第1章章 命題邏輯命題邏輯(10)排中律 (11)矛盾律 (12)蘊(yùn)涵等值式 (13)等價(jià)等值式 (14)假言易位 (15)等價(jià)否定等值式 (16)歸謬論 ababababaabbaabbabababaaaaa)()()()(01第第1章章 命題邏輯命題邏輯【例1.3.2】 證明等價(jià)等值式：a b (ab)(ba)。 解 作如表1.3.2所示的真值表。 表 1.3.2 因此，a b (ab)(ba)。第第1章章 命題邏輯命題邏輯 【例1.3.3】 用等值演算驗(yàn)證等值式 p（qr） （pq）r。 證明 ()()()()()() pqrpqrpq

28、rpqrpqrpqr（蘊(yùn)涵等值式） （蘊(yùn)涵等值式） （結(jié)合律） （德摩根律） （蘊(yùn)涵等值式） 第第1章章 命題邏輯命題邏輯【例1.3.4】 化簡(jiǎn)公式并判斷公式的類(lèi)型。()()() pqrqrpr解 ()()()()()()()()()()()()( ()()1 pqrqrprpqrqrprpqrqprpqrpqrpqpqrpqpqrrr（結(jié)合律） （分配律） （結(jié)合律、交換律）（分配律） （德摩根律） （排中律） （同一律） 該公式為可滿(mǎn)足式第第1章章 命題邏輯命題邏輯【例1.3.5】判斷下列公式 的類(lèi)型。 ()pqqp解 （分配律） （矛盾律） （同一律） （蘊(yùn)涵等值式） （德摩根律、雙重否

29、定律）（交換律、結(jié)合律） （排中律） （零律） 11)()()()()0)()()()(qqpppqppqppqppqppqqqppqqp第第1章章 命題邏輯命題邏輯 因此，公式 是一個(gè)重言式。 等值演算在計(jì)算機(jī)硬件設(shè)計(jì)，開(kāi)關(guān)理論和電子元器件中都占據(jù)重要地位。()pqqp第第1章章 命題邏輯命題邏輯1.4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 前面我們一共介紹了五個(gè)聯(lián)結(jié)詞： 、和 ，并用它們構(gòu)成了一些命題公式，且看到了有些公式書(shū)寫(xiě)形式盡管不同，但實(shí)際上是等值的。因此我們不禁要問(wèn)： （1）總共有多少個(gè)命題公式？ （2）總共有多少個(gè)聯(lián)結(jié)詞？第第1章章 命題邏輯命題邏輯 對(duì)于含有兩個(gè)命題變?cè)墓剑碚撋现v

30、可以書(shū)寫(xiě)出無(wú)窮多個(gè)公式，但互不等值的公式恰有 =24=16個(gè)。對(duì)應(yīng)著16個(gè)不同的真值表（真值表共有22行，行上的每個(gè)記入值又可在0、1中任取其一，因此構(gòu)成 個(gè)不同的真值表），亦即對(duì)應(yīng)著16個(gè)真值函數(shù)fi（i=0，1，15），其中fi：00，01，10，110，1，如表1.4.1所示。222222第第1章章 命題邏輯命題邏輯 表 1.4.1 第第1章章 命題邏輯命題邏輯 這里，f0和f15正是兩個(gè)常值函數(shù)：永假式0和永真式1； f3和f5分別是命題變?cè)猵和q； f1是我們所熟知的二元真值函數(shù)pq； f7是二元真值函數(shù)pq； f9是二元真值函數(shù)p q； f10和f12分別是一元真值函數(shù) q和 p；

31、 f11和f13 分別是二元真值函數(shù)qp和pq。第第1章章 命題邏輯命題邏輯 1.如果則的否定“ ” 設(shè)p、q為任意兩個(gè)命題，復(fù)合命題“如果p則q的否定”稱(chēng)為p、q蘊(yùn)含的否定，記作：p q ?！?”稱(chēng)為蘊(yùn)含的否定聯(lián)結(jié)詞。p q為真，當(dāng)且僅當(dāng)p為真，q為假。 由上面所述可知，f2是二元真值函數(shù) p q。)(qpqp第第1章章 命題邏輯命題邏輯 2.異或（排斥或）“ ” 設(shè)p、q為任意兩個(gè)命題，復(fù)合命題“p異或q”稱(chēng)為p、q的異或（排斥或），記作：p q?！?”稱(chēng)為異或（排斥或）聯(lián)結(jié)詞。p q為真，當(dāng)且僅當(dāng)p、q中恰有一個(gè)為真。 由表1.4.1和前面所述可知，f6是二元真值函數(shù)p q。)()()(

32、)()(qpqpqpqpqpqp)()()()()()()()()()()(qpqppqqppqqppqqppqqpqp證：等價(jià)等值式德摩根律蘊(yùn)含等值式德摩根律交換律第第1章章 命題邏輯命題邏輯(1)(2)()()(3)()()(4)0(5)0(6)1 abbaabcabcabcabaaaaaa(ac)【例1.4.1】用真值表證明)()(cbacba聯(lián)結(jié)詞“ ”有以下性質(zhì)：第第1章章 命題邏輯命題邏輯【例1.4.2】用等值演算證明)()()(cabacba)()()()(0)()()()()()()()()()()()()()(cbcbacbcbacbcbaacbacbacbacabacaba

33、cabacbcbacba真值函數(shù)f6真值函數(shù)f6分配、德摩根分配矛盾、零律同一律第第1章章 命題邏輯命題邏輯 3.與非“” 設(shè)p、q為任意兩個(gè)命題，復(fù)合命題“p與q的否定”稱(chēng)為p、q的與非，記作：pq。“”稱(chēng)為與非聯(lián)結(jié)詞。pq為假，當(dāng)且僅當(dāng)p、q均為真。 由定義可知，f14是二元真值函數(shù)pq。() pqpq性質(zhì)：（pq）r p（qr） 第第1章章 命題邏輯命題邏輯證明： 因?yàn)?()() pqrp qr所以 )()()()()()()()(rqprqprqprqprqprqprqprqp()()pqrpqr第第1章章 命題邏輯命題邏輯 【例1.4.3】 將下列公式化成僅含聯(lián)結(jié)詞“”的公式。 (1

34、)(2)(3) apbpqcpq解 (1)()(2)()()()()(3)()()() appqppbpqpqpqpqpqcpqpqpqpqqq第第1章章 命題邏輯命題邏輯 4.或非“” 設(shè)p、q為任意兩個(gè)命題，復(fù)合命題“p或q的否定”稱(chēng)為p、q的或非，記作：pq。“”稱(chēng)為或非聯(lián)結(jié)詞。pq為真，當(dāng)且僅當(dāng)p、q均為假。 由定義可知，f8是二元真值函數(shù)pq。 pq （pq） 類(lèi)似于“”，“”同樣不滿(mǎn)足結(jié)合律，并類(lèi)似可將例1.4.3中的公式化成僅含聯(lián)結(jié)詞“”的公式。 第第1章章 命題邏輯命題邏輯 【例1.4.4】 將公式p（q r）化成僅含聯(lián)結(jié)詞 、的公式形式。 （等價(jià)等值式）（蘊(yùn)涵等值式） （德摩

35、根律） （雙重否定律） )()()()()()()()()(qrrqpqrrqpqrrqpqrrqprqp第第1章章 命題邏輯命題邏輯 【例1.4.5】 將公式pq化成僅含聯(lián)結(jié)詞、的公式形式。解 )()()()()()()()(qppqppqpqpqpqpqpqpqqpqpqpqpqp第第1章章 命題邏輯命題邏輯1.5 對(duì)偶與范式對(duì)偶與范式 在1.3節(jié)中介紹的基本等值式中，多數(shù)公式是成對(duì)出現(xiàn)的，這些成對(duì)出現(xiàn)的公式是對(duì)偶的。 定義1.5.1 在僅含聯(lián)結(jié)詞 、的命題公式a中，將換成，將換成，若a中含有0或1，則將0換成1，1換成0，所得命題公式稱(chēng)為a的對(duì)偶式對(duì)偶式，記作a*。由定義易知，對(duì)偶式是相

36、互的，(a*)*=a，我們稱(chēng)a與a*是對(duì)偶的。第第1章章 命題邏輯命題邏輯 例如：(1)()1()0(2)()()()() pqrpqrpqqrpqqr與 與 互為對(duì)偶式。 是對(duì)偶的。第第1章章 命題邏輯命題邏輯 定理1.5.1 設(shè)a與a*是對(duì)偶的，p1,p2,，pn是出現(xiàn)在a、a*中的所有命題變?cè)?，則 a（p1， p2， , pn） a*（ p1， p2， ， pn） （1） a（ p1， p2， ， pn） a*（p1， p2， ， pn） （2） 第第1章章 命題邏輯命題邏輯 定理1.5.2 設(shè)a*、 b*分別是公式a、 b的對(duì)偶式， 如果a b， 則a* b*。 -對(duì)偶定理 證明 設(shè)a

37、、 b中所有不同的變?cè)獮閜1， p2， ， pn， 則由a b知： a（p1， p2， ， pn) b（p1， p2， ， pn）是永真式， a（p1， p2， ， pn） b（p1， p2， ， pn）亦是永真式。 所以， 1212(,)(,)nna p ppb p pp 第第1章章 命題邏輯命題邏輯 定義1.5.2 將命題變?cè)捌浞穸ńy(tǒng)稱(chēng)為文字。 簡(jiǎn)單析取式（基本和） 僅由有限個(gè)文字文字構(gòu)成的析取式。 簡(jiǎn)單合取式（基本積） 僅由有限個(gè)文字文字構(gòu)成的合取式。 例如， p、 q既是一個(gè)文字的簡(jiǎn)單析取式， 又是一個(gè)文字的簡(jiǎn)單合取式。 p q、 pr均是有兩個(gè)文字的簡(jiǎn)單析取式。 pqr、 pq q

38、均是有三個(gè)文字的簡(jiǎn)單合取式。 第第1章章 命題邏輯命題邏輯性質(zhì) (1) 一個(gè)文字既是簡(jiǎn)單析取式又是簡(jiǎn)單合取式。 (2) 一個(gè)簡(jiǎn)單析取式是重言式， 當(dāng)且僅當(dāng)它同時(shí)含有一個(gè)命題變?cè)捌浞穸ā?(3) 一個(gè)簡(jiǎn)單合取式是矛盾式， 當(dāng)且僅當(dāng)它同時(shí)含有一個(gè)命題變?cè)捌浞穸ā?例如， pq p是重言式， p q q是矛盾式。 第第1章章 命題邏輯命題邏輯 定義 1.5.3 析取范式析取范式 由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式。 合取范式合取范式 由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式。 第第1章章 命題邏輯命題邏輯【例1.5.1】 判斷下列各式是析取范式還是合取范式。 （1） p（2） p q（3） pqr（4） p（

39、q r） r（5） p（pq）（p qr）q第第1章章 命題邏輯命題邏輯 解: （1）既是一個(gè)簡(jiǎn)單析取式又是一個(gè)簡(jiǎn)單合取式， 是只有一個(gè)簡(jiǎn)單析取式的合取范式，也是只有一個(gè)簡(jiǎn)單合取式的析取范式。 （2）是有兩個(gè)簡(jiǎn)單合取式的析取范式，也是只有一個(gè)簡(jiǎn)單析取式的合取范式。 （3）是有三個(gè)簡(jiǎn)單析取式的合取范式，也是只有一個(gè)簡(jiǎn)單合取式的析取范式。 （4）是有三個(gè)簡(jiǎn)單合取式的析取范式。 （5）是有四個(gè)簡(jiǎn)單析取式的合取范式。第第1章章 命題邏輯命題邏輯 性質(zhì)： (1) 一個(gè)文字既是一析取范式又是一合取范式。 (2) 一個(gè)析取范式為矛盾式， 當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式是矛盾式。 (3) 一個(gè)合取范式為重言式，

40、當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式是重言式。 例如： a=（ ppq）（pq q）是矛盾式。 a=（ ppq）（pq q）（q rr）是重言式。第第1章章 命題邏輯命題邏輯 定理1.5.3 任一命題公式都存在著與之等值的析取范式，任一命題公式都存在著與之等值的合取范式。 證明 對(duì)于任一公式， 可用下面的方法構(gòu)造出與其等值的范式： （1） 利用等值式 a b (ab）（ba） ab ab使公式中僅含聯(lián)結(jié)詞 、 、 。 第第1章章 命題邏輯命題邏輯 （2） 利用德摩根律和雙重否定律 （ab） a b （ab） a b a a 將否定符移至命題變?cè)埃⑷サ舳嘤嗟姆穸ǚ?。 第第1章章 命題邏輯命題邏輯

41、（3） 利用分配律 a（bc) （ab）（ac） a（bc） （ab）（ac）將公式化成析取范式或合取范式。 所得即與原公式等值的范式。 第第1章章 命題邏輯命題邏輯【例1.5.2】 求公式 （pq）r） p的析取范式。 解 ()()()()()()()()()()()()()()()()()pqrppqrpppqrpqrpppqrpqrpppqrpqrpprprqrpprprpqrprpqrpr （消 ）（消） （德摩根律）（分配律） （交換律） （吸收律） （雙重否定律、吸收律）第第1章章 命題邏輯命題邏輯()()()()()()()0()()0()()pprqprprprqrpqrrpr

42、pqrprpqr （分配律） （分配律）（矛盾式）（同一律） -析取范式 事實(shí)上， 第*步已經(jīng)是析取范式了， 最后是化簡(jiǎn)了的結(jié)果。 這說(shuō)明一個(gè)公式的析取范式不是唯一的。 第第1章章 命題邏輯命題邏輯 【例1.5.3】 求例1.5.2中公式的合取范式。 解 由例1.5.2第4步原式 ()()()()()()()()pqrpprpqprpprpqprpr （分配律） -合取范式 （冪等律、 交換律）第第1章章 命題邏輯命題邏輯 定義1.5.3 對(duì)于公式a： 極小項(xiàng) 包含a中所有命題變?cè)蚱浞穸ㄒ淮吻覂H一次的簡(jiǎn)單合取式； 極大項(xiàng) 包含a中所有命題變?cè)蚱浞穸ㄒ淮吻覂H一次的簡(jiǎn)單析取式。 注 極小項(xiàng)或極

43、大項(xiàng)中各文字要求按角標(biāo)順序或字典順序排列。 第第1章章 命題邏輯命題邏輯 【例1.5.4】 求公式a（p， q）的極小項(xiàng)和極大項(xiàng)。 解 極小項(xiàng)： p q、 pq、 p q、 pq 極大項(xiàng)： pq 、 p q、 pq、 p q 即極小（大）項(xiàng)的個(gè)數(shù)等于22個(gè)。 （n元的公式為2n個(gè)。) 我們做出僅含兩個(gè)命題變?cè)墓降臉O小項(xiàng)的真值表， 如表1.5.1 所示。 第第1章章 命題邏輯命題邏輯表 1.5.1 第第1章章 命題邏輯命題邏輯 由真值表可看出： 對(duì)于p、 q的任一組賦值， 有且僅有一個(gè)極小項(xiàng)的真值為1， 即極小項(xiàng)之間是不等值的， 4個(gè)真值賦值與4個(gè)極小項(xiàng)值之間有一一對(duì)應(yīng)關(guān)系。 我們用mi表示

44、在十進(jìn)制為i的賦值下真值為1的極小項(xiàng)。 第第1章章 命題邏輯命題邏輯 定義1.5.5 對(duì)于公式a： 主析取范式主析取范式 與a等值的由極小項(xiàng)構(gòu)成的析取范式； 主合取范式主合取范式 與a等值的由極大項(xiàng)構(gòu)成的合取范式。 由定理1.5.3知， 任一公式的析（合）取范式總是存在的， 求主范式只需在求范式的基礎(chǔ)上將每個(gè)簡(jiǎn)單合（析）取式化成極小（大）項(xiàng)。 第第1章章 命題邏輯命題邏輯 【例1.5.5】 求公式 （pq）r p的主析取范式。 解 由例1.5.2已求得公式的析取范式， 在此基礎(chǔ)上求主析取范式。 即： 第第1章章 命題邏輯命題邏輯257()()()()()()()()()()()(2,5,7)p

45、qrpprpqrprqqpqrprqprqpq rpqrpqrpqrmmm -析取范式 -主析取范式（同一律） （分配律） （交換律） 2、 5、 7恰是使三個(gè)極小項(xiàng)成真的賦值的十進(jìn)制表示。 第第1章章 命題邏輯命題邏輯 【例1.5.6】 求（p（pr）（q p）的主析取范式。 解 ()()()()()()()()1()()()()()()pprqppprpqqppprpqpqpqpqpqpqpqppqq （等價(jià)等值式）（蘊(yùn)涵等值式） （排中律） （同一律）（分配律） 第第1章章 命題邏輯命題邏輯0167()()()()()()()()()()()()()()()()()()(0,1,6,7)

46、ppqpppqqqpppqprrpqrrqprqprpqrpqrpqrpqrpqrpqrmmmm （分配律） （矛盾式、 同一律）（同一律） （分配律） （交換律） -主析取范式析取范式qq第第1章章 命題邏輯命題邏輯 定理1.5.4 任何命題公式的主析取范式存在且唯一。 證明 由析取范式的存在性知主析取范式的存在性成立。 下面證唯一性： 設(shè)任一命題公式a有兩個(gè)主析取范式b和c， 則因?yàn)?a b， a c， 所以b c。 若b、 c是a的（在不計(jì)極小項(xiàng)的順序的情況下）不等值的主析取范式（bc）， 則必存在某個(gè)極小項(xiàng)mi， mi只存在于b、 c之一中。 不妨設(shè)mi在b中， 而不在c中， 因此i之

47、二進(jìn)制表示是b的成真賦值， 而對(duì)于c則為成假賦值， 這與 b c矛盾， 故b=c。 第第1章章 命題邏輯命題邏輯 【例1.5.7】 用真值表法求上例公式 （p（pr）（q p）的主析取范式。 解 構(gòu)造公式的真值表如表1.5.2所示。 第第1章章 命題邏輯命題邏輯表 1.5.2 第第1章章 命題邏輯命題邏輯故 0167()()(0,1,1,6,7)()()()()pprqpmmmmpq rpqrpqrpqr 第第1章章 命題邏輯命題邏輯 結(jié)論：(主析取范式的用途) (1) 重言式的主析取范式包含公式的全部2n個(gè)極小項(xiàng)。 (2)（規(guī)定）矛盾式的主析取范式為0。 (3) 二等值的公式必有相同的主析取

48、范式。 (4) 不列真值表，由主析取范式可得公式的成真、 成假賦值。 第第1章章 命題邏輯命題邏輯 (5) 僅由真值表，可得公式的表達(dá)式（主析取范式形式）。 (6) 解決應(yīng)用問(wèn)題。 前兩條可用來(lái)判斷公式的類(lèi)型， 第三條判斷兩個(gè)公式的等值， 由此前面提出的三個(gè)問(wèn)題得到了解決。 第第1章章 命題邏輯命題邏輯 【例1.5.8】 不列真值表， 求公式（pq）r的成真賦值。 解 1345()()()()()()()()()()()()()()()()()()()()()()pqrpqrpqrpqrrpprpqrpqrprprpqrpqrprqqprqqpqrpqrpqrpqrprpqrmmmmm 7(1

49、,3,4,5,7) (消） （內(nèi)移 )所以， 公式（pq）r成真的賦值為： 001， 011， 100， 101， 111。 q第第1章章 命題邏輯命題邏輯 【例1.5.9】 已知命題公式a（p， q， r）的成真賦值為010， 101， 110， 求a。 解 a m2m5m6 （ pq r）（p q r）（pq r） 第第1章章 命題邏輯命題邏輯 【例1.5.10】 四人比賽， 三人估計(jì)成績(jī)。 甲說(shuō)： “ a第一、 b第二， 乙說(shuō)： c第二、 d第四， 丙說(shuō)： a第二、 d第四。 結(jié)果每人都說(shuō)對(duì)了一半， 假設(shè)無(wú)并列名次， 問(wèn)a、 b、 c、 d 的實(shí)際名次如何？ 解 設(shè) p： a 第一， q

50、： b 第二。 （ 甲說(shuō)） （ pq） （p q） 1 r： c 第二， s： d 第四。 （乙說(shuō)） （ rs）（r s） 1 t： a 第二， s： d 第四。 （丙說(shuō)） （ st）（s t） 1第第1章章 命題邏輯命題邏輯010100110110010101011()()()() ()()()()()()()()()()()()pqpqrsrsststpqrspqrspqrspqrsststpqrstpqrstpqrstp qrstmmmm p： a 第一q： b 第二 r： c 第二s： d 第四 t： a 第二 p0011q1100r0101s1010t0101第第1章章 命題邏輯命題

51、邏輯表 1.5.3 第第1章章 命題邏輯命題邏輯 對(duì)應(yīng)p、 q的每一組賦值，極大項(xiàng)的真值有且僅有一個(gè)為0： 極大項(xiàng)與其成假賦值有著一一對(duì)應(yīng)關(guān)系， 我們用mi表示在十進(jìn)制為i的賦值下真值為0的極大項(xiàng)。 因此， 求一個(gè)公式的主合取范式， 只需知道該公式的成假賦值，并將對(duì)應(yīng)著這個(gè)賦值也成假的那些極大項(xiàng)合取起來(lái)，即得該公式的主合取范式主合取范式。 第第1章章 命題邏輯命題邏輯 【例1.5.11】 求公式（p（pr）（q p）的主合取范式。 解 由例1.5.7已知此公式的成假賦值為010， 011， 100， 101， 可得主合取范式為2345()()(2,3,4,5)()()()()pprqpmmmm

52、pqrpqrpqrpqr 第第1章章 命題邏輯命題邏輯同樣， 利用等值演算法也可得主合取范式： ()()()()()1()()()()()()()()()()pprqppprqppqpqpqpqrpqrpqrpqrpqrpqrpqrpqr （等價(jià)等值式、 蘊(yùn)涵等值式） （排中律、零律、交換律） （同一律、 分配律） -主合取范式 （交換律） 第第1章章 命題邏輯命題邏輯 注意到， 對(duì)于任一公式， 在它的2n個(gè)賦值中， 非0即1， 因此其主析取范式中的極小項(xiàng)和其主合取范式中的極大項(xiàng)的個(gè)數(shù)之和恰為2n， 且其下標(biāo)不會(huì)相同。 故當(dāng)我們知道了一個(gè)公式的所有成真賦值時(shí)， 也就知道了它的所有成假賦值。 亦

53、即： 知道了主析取范式， 相應(yīng)地也就得到了主合取范式， 反之亦然。 另外：任何命題公式的主合取范式存在且唯一。（規(guī)定）重言式的主合取范式為1。第第1章章 命題邏輯命題邏輯 【例1.5.12】 求（ pr）（pq）（qr）的主析取范式。 解 ()()()()()()()()()()()()()()()()prpqqrprpqqrpqrpqrpqrpqrpqrpqrpqrpqrpqrpqr -主合取范式 第第1章章 命題邏輯命題邏輯2456(2,4,5,6)(0,1,3,7)()()()()mmmmpqrpqrpqr pqr -主析取范式 第第1章章 命題邏輯命題邏輯1.6 推推 理理 理理 論論

54、 推理是“前提 結(jié)論的思維過(guò)程。在命題邏輯中，前提是已知的命題公式，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。在傳統(tǒng)數(shù)學(xué)中定理的證明均是由前提（已知條件，全是真命題）推出結(jié)論（亦全是真命題），這樣的結(jié)論稱(chēng)為合法結(jié)論。 第第1章章 命題邏輯命題邏輯 數(shù)理邏輯有所不同，它著重研究的是推理的過(guò)程，這種過(guò)程稱(chēng)為演繹或形式證明。 在過(guò)程中使用的推理規(guī)則必須是公認(rèn)的且要明確列出，而對(duì)于作為前提和結(jié)論的命題并不一定要求它們?nèi)钦婷}，這樣的結(jié)論稱(chēng)為有效結(jié)論。 第第1章章 命題邏輯命題邏輯 定理1.6.1 稱(chēng)蘊(yùn)涵式（a1a2an）b為推理的形式結(jié)構(gòu)， a1， a2， ， an為推理的前提， b為推理的結(jié)論。

55、 若（a1a2an）b是重言式， 則稱(chēng)從前提a1， a2， ， an推出結(jié)論b的推理正確， b是a1， a2， ， an的有效結(jié)論或邏輯結(jié)論。 記作： （a1a2an） b 或 a1, a2, , an b 否則稱(chēng)推理不正確， 或b不是前提a1， a2， ，an的有效結(jié)論。 第第1章章 命題邏輯命題邏輯 【例1.6.1】 驗(yàn)證下面推理是否正確： 一個(gè)數(shù)是復(fù)數(shù)， 僅當(dāng)它是實(shí)數(shù)或是虛數(shù)， 一個(gè)數(shù)既不是實(shí)數(shù)也不是虛數(shù)， 因此它不是復(fù)數(shù)。 證明 設(shè)p： 它是復(fù)數(shù)， q： 它是實(shí)數(shù)， r： 它是虛數(shù)。 推理的形式結(jié)構(gòu)為： （p（qr）（ q r） p。 （1） 真值表法(真值表如表1.6.1所示)。 因

56、為只有第一行前提、結(jié)論均為真，所以推理正確第第1章章 命題邏輯命題邏輯 表 1.6.1 第第1章章 命題邏輯命題邏輯（2） 等值演算法： ()()()()()()()1)()()11pqrqrppqrqrppqrqrppqrppqrppqrppqrpqr （蘊(yùn)涵等值式）（德摩根律） （分配律、 排中律） （同一律） （蘊(yùn)涵等值式） （德摩根律） （交換律、 排中律） （零律） 0第第1章章 命題邏輯命題邏輯 （3） 主析取范式法（略）。 以上的證明方法， 當(dāng)形式結(jié)構(gòu)比較復(fù)雜， 特別是所含命題變?cè)^多時(shí)， 一般是很不方便的。 下面介紹構(gòu)造證明法， 這種方法必須在給定的規(guī)則下進(jìn)行， 其中有些規(guī)則建

57、立在推理定律（重言蘊(yùn)涵式）的基礎(chǔ)之上。 第第1章章 命題邏輯命題邏輯推理定律： (1) a（ab） 附加(2) （ab）a 化簡(jiǎn)(3) （ab）a）b 假言推理(4) （ab） b） a 拒取式(5) （ab） b）a 析取三段論(6) （ab）（bc）（ac） 假言三段論(7) （ab）（bc）（ac） 等價(jià)三段論(8) （ab）（cd）（ac）（bd） 構(gòu)造性二難第第1章章 命題邏輯命題邏輯 推理規(guī)則： 前提引入規(guī)則 在證明的任何步驟上，都可以引入前提。 結(jié)論引入規(guī)則 在證明的任何步驟上，所得到的結(jié)論均可作后續(xù)證明的前提加以引用。 置換規(guī)則 在證明的任何步驟上，命題公式中的任何子公式都可以

58、用與之等值的公式置換。另外， 由前面的8個(gè)推理定律可得下面8個(gè)推理規(guī)則：（這里a1， a2， ， an b表示b是a1， a2， ， an的邏輯結(jié)論。）第第1章章 命題邏輯命題邏輯附加規(guī)則 a（ab） 化簡(jiǎn)規(guī)則 （ab）a 假言推理規(guī)則 （ab）, ab拒取式規(guī)則 （ab）， b a假言三段論規(guī)則 (ab)，(bc) (ac)析取三段論規(guī)則 （ab）， b a構(gòu)造性二難規(guī)則 (ab), (cd),(ac) (bd)合取引入規(guī)則 a， b (ab)第第1章章 命題邏輯命題邏輯 構(gòu)造證明法： 構(gòu)造證明可以看作公式的序列， 其中的每個(gè)公式都是按照事先規(guī)定的規(guī)則得到的， 且需將所用的規(guī)則在公式后寫(xiě)明，

59、 該序列的最后一個(gè)公式正是所要證明的結(jié)論。 第第1章章 命題邏輯命題邏輯 【例1.6.4】 構(gòu)造下列推理的證明 前提： pq， p r， st， sr， t 結(jié)論： q 解 （1） st 前提引入 （2） t 前提引入 （3） s （1）（2）拒取式 （4） sr 前提引入第第1章章 命題邏輯命題邏輯 （5） r （3）（4）假言推理 （6） r （5）置換 （7） p r 前提引入 （8） p （6）（7）拒取式 （9） pq 前提引入 （10） qp （9）置換 （11） q （10）（8）析取三段論 證畢 第第1章章 命題邏輯命題邏輯 【例1.6.5】 用構(gòu)造證明的方法證明下列推理的正確

60、性。 如果小張守一壘且小李向乙隊(duì)投球，則甲隊(duì)取勝。如果甲隊(duì)取勝，則甲隊(duì)成為聯(lián)賽第一名。 小張守第一壘。甲隊(duì)沒(méi)有成為聯(lián)賽第一名。因此，小李沒(méi)有向乙隊(duì)投球。 解 設(shè)p： 小張守一壘， q： 小李向乙隊(duì)投球， r： 甲隊(duì)取勝， s： 甲隊(duì)成為聯(lián)賽第一名。 第第1章章 命題邏輯命題邏輯前提： （pq）r， rs， p， s結(jié)論： q（1） rs 前提引入（2） s 前提引入（3） r （1）（2）拒取式（4）（pq）r 前提引入第第1章章 命題邏輯命題邏輯（5） （pq） （3）（4）拒取式（6） p q （5）置換（7） p 前提引入（8） q （6）（7）析取三段論 所以推理正確。 第第1章章 命