第四章數(shù)理邏輯

1、第四章 數(shù)理邏輯數(shù)理邏輯是應(yīng)用數(shù)學(xué)方法引進(jìn)一套符號(hào)系統(tǒng)來(lái)研究思維的形式結(jié)構(gòu)和規(guī)律的學(xué)科，它起源于公元十七世紀(jì)。十九世紀(jì)英國(guó)的德摩根和喬治布爾發(fā)展了邏輯代數(shù)，二十世紀(jì)三十年代數(shù)理邏輯進(jìn)入了成熟時(shí)期，基本內(nèi)容（命題邏輯和謂詞邏輯）有了明確的理論基礎(chǔ)，成為數(shù)學(xué)的一個(gè)重要分支，同時(shí)也是電子元件設(shè)計(jì)和性質(zhì)分析的工具。馮諾意曼，圖靈，克林， 等人研究了邏輯與計(jì)算的關(guān)系?；诶碚撗芯亢蛯?shí)踐，隨著1946年第一臺(tái)通用電子數(shù)字計(jì)算機(jī)的誕生和近代科學(xué)的發(fā)展，計(jì)算技術(shù)中提出了大量的邏輯問(wèn)題，邏輯程序設(shè)計(jì)語(yǔ)言的研制，更促進(jìn)了數(shù)理邏輯的發(fā)展。除古典二值（真，假）邏輯外，還研究了多值邏輯、模態(tài)邏輯、概率邏輯、模糊邏輯、非

2、單調(diào)邏輯等。不僅有演繹邏輯，也還有歸納邏輯。計(jì)算機(jī)科學(xué)中還專門研究計(jì)算邏輯、程序邏輯、時(shí)序邏輯等?，F(xiàn)代數(shù)理邏輯分為四論：證明論，遞歸論（它們與形式語(yǔ)言語(yǔ)法有關(guān)），模型論，公理化集合論（它們與形式語(yǔ)言的語(yǔ)義有關(guān)）。學(xué)習(xí)要求: 掌握命題，命題公式，重言式，等價(jià)式，蘊(yùn)涵式等基本概念，能利用邏輯聯(lián)結(jié)詞或真值表，等價(jià)式與蘊(yùn)涵式進(jìn)行命題演算和推理；學(xué)習(xí)范式時(shí)與集合的范式進(jìn)行對(duì)比。 表述客觀世界的各種現(xiàn)象，表述人們的思想，表述各門學(xué)科的規(guī)則、理論等，除使用自然語(yǔ)言（這常常是上有歧異性的）外，還要使用一些特定的術(shù)語(yǔ)、符號(hào)、規(guī)律等“對(duì)象語(yǔ)言”，這些是所研究學(xué)科的一種特殊的形式化語(yǔ)言，研究思維結(jié)構(gòu)與規(guī)律的邏輯學(xué)也

3、有其對(duì)象語(yǔ)言。本章就是討論邏輯學(xué)中的對(duì)象語(yǔ)言命題及其演算，它相當(dāng)于自然語(yǔ)言中的語(yǔ)句。4-4-1 命題 邏輯聯(lián)結(jié)詞與真值表一、 命題的基本概念首先我們從下面的例子加以分析。例4-4-1.1人總是要死的。例4-4-1.2 蘇格拉底是人。例4-4-1.3 蘇格拉底是要死的。例4-4-1.4 中國(guó)人民是勤勞和勇敢的。例4-4-1.5 鴕鳥是鳥。例4-4-1.6 1是質(zhì)（素）數(shù)。例4-4-1.7 今天沒(méi)有下雨。例4-4-1.8 公元二千年會(huì)出現(xiàn)生物計(jì)算機(jī)。例4-4-1.9 太陽(yáng)系外的星球上有人。例4-4-1.10 他喜歡讀書也喜歡運(yùn)動(dòng)。例4-4-1.11 他在機(jī)房里或者在圖書館里。例4-4-1.12 電

4、燈不亮是燈泡或線路有毛病，或者是停電所致。例4-4-1.13 如果和都是正數(shù)，則也是正數(shù)。例4-4-1.14 當(dāng)且僅當(dāng)和都大于零。例4-4-1.15 101+1=110。例4-4-1.16 天氣多好?。坷?-4-1.17 他來(lái)了嗎？例4-4-1.18 全體起立！例4-4-1.19 幫幫我吧！例4-4-1.20 =0。例4-4-1.21 我正在說(shuō)謊。上述例4-4-1.14-4-1.4，例4-4-1.124-4-1.13是可以判斷為對(duì)（真，成立）的陳述句，例4-4-1.5，4-4-1.6，4-4-1.14是能夠判斷為不對(duì)（假，不成立）的陳述句，例4-4-1.74-4-1.9在人類歷史發(fā)展的長(zhǎng)河中能

5、夠判斷它是真或是假的陳述句，例4-4-1.104-4-1.11根據(jù)“他”當(dāng)時(shí)的情況能夠判斷出是真或是假的陳述句，例4-4-1.15在二進(jìn)制計(jì)算中為真，在十進(jìn)制計(jì)算中為假，也還是可以判斷為真或?yàn)榧俚年愂鼍洌?-4-1.16是感嘆句，例4-4-1.17是疑問(wèn)句，例4-4-1.18是命令句，例4-4-1.19是祈使句，例4-4-1.20中x是一個(gè)未知數(shù)（變量），無(wú)法判斷是真還是假，例4-4-1.21是無(wú)法判斷真假的悖論。從以上的分析可以看出，表達(dá)思想的語(yǔ)句有不同的類別，數(shù)理邏輯中研究的是出現(xiàn)較多而又比較規(guī)范的語(yǔ)句可以判斷出真或假的陳述句。 定義 4-4-1.1 凡是能判斷是真或是假的陳述句稱為命題

6、。如前面的例4-4-1.14-4-1.15都是命題，例4-4-1.164-4-1.21都不是命題。命題的值為真或假。今后約定用1表示真，0表示假，除T和F以外的大寫英文字母或它們后面跟上數(shù)字如A，A1，B5，Pi等或數(shù)字（如123，28，）表示命題。如P：M8085 芯片有40條引線，或12：M8085芯片有40條引線。P或12稱為命題“M8085芯片有40條引線“的標(biāo)識(shí)符。當(dāng)命題標(biāo)識(shí)符代表一個(gè)確定的命題時(shí)（如P或12，A：人總是要死的），稱為命題常元，當(dāng)命題標(biāo)識(shí)符代表非確指的命題時(shí)，稱這樣的命題標(biāo)識(shí)符為命題變?cè)?注意：命題變?cè)皇敲}，只有對(duì)命題變?cè)靡粋€(gè)確定的命題代入后，才能確定其值是1

7、還是0。 定義 4-4-1.2 用一個(gè)確定的命題代入一個(gè)命題標(biāo)識(shí)符（如P），稱為對(duì)P進(jìn)行指派（賦值，或解釋）。 再看前面的例4-4-1.14-4-1.6，這些命題不能再分解為更簡(jiǎn)單的能判斷其值為1或0的陳述句了，這類命題稱為原子命題。在例4-4-1.7中，如果表示今天下雨為原子命題P，則今天沒(méi)有下雨是P的否定；例10可分解為原子命題P：他喜歡讀書，Q：他喜歡運(yùn)動(dòng)，用聯(lián)結(jié)詞“也”聯(lián)結(jié)起來(lái)；例4-4-1.11可分解為原子命題P：他在機(jī)房里，Q：他在圖書館里，用聯(lián)結(jié)詞“或者”聯(lián)系起來(lái)；例4-4-1.13可分解為原子命題P：a是正數(shù)，Q：b是正數(shù)，R：ab是正數(shù)，用聯(lián)結(jié)詞“和”與“如果，則”聯(lián)系起來(lái)；

8、例4-4-1.14可分解為原子命題P：xy0，Q：x0，R：y0，用聯(lián)結(jié)詞“當(dāng)且僅當(dāng)”與“都”聯(lián)系起來(lái)，這類用聯(lián)結(jié)詞，標(biāo)點(diǎn)符號(hào)和原子命題構(gòu)成的命題稱為復(fù)合命題。 二、邏輯聯(lián)結(jié)詞日常生活、工作和學(xué)習(xí)中，自然語(yǔ)言里我們常常使用下面的一些聯(lián)結(jié)詞，例如：非，不，沒(méi)有，無(wú)，并非，并不等等來(lái)表示否定；并且，同時(shí)，以及，而（且），不但而且，既又，盡管仍然，和，也，同，與等等來(lái)表示同時(shí)；雖然也，可能可能，或許或許，等和“或（者）”的意義一樣；若則，當(dāng)則與“如果那么”的意義相同；充分必要，等同，一樣，相同與“當(dāng)且僅當(dāng)”的意義一樣。即是說(shuō)在自然語(yǔ)言中，這些邏輯聯(lián)結(jié)詞的作用一般是同義的。在數(shù)理邏輯中將這些同義的聯(lián)結(jié)

9、詞也統(tǒng)一用符號(hào)表示，以便書寫、推演和討論。現(xiàn)定義常用聯(lián)結(jié)詞如下： 定義 4-4-1.3 在命題P的適當(dāng)?shù)胤讲迦搿安弧被蛘摺皼](méi)有”產(chǎn)生的新命題稱為P的否定，記為P讀成“非P”。P的取值依賴于P 的取值，即定義運(yùn)算表為命題PP真值1001例如P: 2是一個(gè)質(zhì)數(shù)（值為1），P：2不是一個(gè)質(zhì)數(shù)（值為0）或2是一個(gè)和數(shù)。注意：(1)不同的陳述句可能確定同一個(gè)命題；(2)否定是一個(gè)一元運(yùn)算。定義4-4-1.4 兩個(gè)命題P和Q產(chǎn)生的一個(gè)新命題記為PQ ，讀成“P與Q”或“P和Q的合取”。合取的運(yùn)算表為命題PQPQ真值111100010000如例4-4-1.10，P：他喜歡讀書，Q:他喜歡運(yùn)動(dòng)，P和Q的合取為

10、PQ：他喜歡讀書也喜歡運(yùn)動(dòng)。 又如A：貓吃魚，B：2+2=0，則A B ：貓吃魚而且2+2=0。注意：(1) 數(shù)理邏輯中的聯(lián)結(jié)詞“合取”只考慮命題之間的形式關(guān)系，不考慮命題內(nèi)容的實(shí)際含義，只有在研究取值時(shí)才加以考慮。(2)合取是一個(gè)二元運(yùn)算。定義 4-4-1.5 兩個(gè)命題P或Q產(chǎn)生一個(gè)新命題，記為PQ ，讀成“P析取Q”，析取的運(yùn)算表為命題PQP Q真值111101011000如例4-4-1.12，P：他在機(jī)房里，Q：他在圖書館里，PQ：他在機(jī)房或圖書館里。又如P1：他是游泳冠軍，P2：他百米是賽冠軍，P1P2：他是游泳冠軍或百米賽跑冠軍。A：貓吃魚，B：2+2=0，AB：貓吃魚或者2+2=0

11、。注意：(1)析取可細(xì)分為兩種，一種是“不可兼或”如前面例4-4-1.12，一種是“可兼或”，如P1P2。有的將不可兼或記為“”，可兼或記為“”。顯然“”包含“”為其特殊情況。故我們著重考慮“”的情形。(2) 在自然語(yǔ)言或形式邏輯中，用來(lái)析取聯(lián)結(jié)的對(duì)象往往要求屬于同一類事物，但是在數(shù)理邏輯中不作這種限制，例如AB：貓吃魚或者2+2=0是允許存在的命題。(3) 析取是一個(gè)二元運(yùn)算。定義 4-4-1.6 設(shè)P，Q是兩個(gè)命題，“若P則Q”是一個(gè)新命題，記為PQ ，讀成P推出Q（或Q是P的必要條件，P是Q的充分條件），P稱為條件聯(lián)結(jié)詞“”的前件，Q為后件。如P：河水泛濫，Q：周圍的莊稼被毀。 PQ：若

12、河水泛濫，則周圍的莊稼被毀。A：23，B: 今天陽(yáng)光明媚。 AB：若20及命題：x和y都大于零用雙條件聯(lián)結(jié)詞產(chǎn)生的命題，這個(gè)命題取值為0。又如，我沒(méi)有收到信當(dāng)且僅當(dāng)沒(méi)有人給我寫信，它的值為1。約定在整數(shù)范圍內(nèi)討論，P：2+2=0，Q：IBM-PC是一種微型計(jì)算機(jī)，PQ：2+2=0當(dāng)且僅當(dāng)IBM-PC是一種微型計(jì)算機(jī)，此命題取值為0。注意：(1) 雙條件聯(lián)結(jié)詞聯(lián)系的命題不限定屬于同一類事物。 (2) 雙條件是一個(gè)二元運(yùn)算。這五種邏輯聯(lián)結(jié)詞也可以稱為邏輯運(yùn)算，與一般數(shù)的運(yùn)算一樣，可以規(guī)定運(yùn)算的優(yōu)先級(jí)，我們規(guī)定的優(yōu)先級(jí)順序依次為，。如果出現(xiàn)的邏輯聯(lián)結(jié)詞相同，又沒(méi)有括號(hào)時(shí)，從左到右順序運(yùn)算。如果遇到有

13、括號(hào)時(shí)就先進(jìn)行括號(hào)中的運(yùn)算?？疾炖?-4-1.12令P：電燈亮，Q：燈泡有毛病，R：線路有毛病，S：停電。則可將該語(yǔ)句符號(hào)化為QRSP。三、命題運(yùn)算的真值表定義 4-4-1.8 在命題公式中，對(duì)于分量指派的各種可能組合，即確定了該命題的各種真值情況，把它匯列成表格，就是命題的真值表。任意給定一個(gè)復(fù)合命題后，用原子命題和邏輯聯(lián)結(jié)詞表出，再利用真值表就可以計(jì)算出復(fù)合命題的值。當(dāng)復(fù)合命題用原子命題變?cè)?、邏輯?lián)結(jié)詞和括號(hào)組成時(shí)，可以得出該復(fù)合命題變?cè)恼嬷当?。?-4-1.22 求P(PQ)，PP，PP的真值表。解：PQPQP(PQ) 1111100101000000PPPP100100010010

14、PPPP101101011011例4-4-1.23 求QRSP的真值表。解：PQRSRSQRSPQRSP11111100111001001101010010111100110001001010000110010001100000010111111101100111010101110011111101000111001000110001001100000011例4-4-1.24 求(PQ) PQ的真值表。解：PQPQ(PQ)PQ(PQ)PQ1110011010010110010001114-4-1 習(xí) 題1 舉出原子命題和復(fù)合命題的例子五個(gè)以上。2 將下列命題符號(hào)化：(1) 我一邊看書一邊聽音樂(lè)

15、。(2) 天下雨了，我不去上街。(3) 實(shí)函數(shù)可微當(dāng)且僅當(dāng)連續(xù)。此命題的真值是什么？(4) 除非你努力，否則你就會(huì)失敗。(5) 合肥到北京的列車是中午十二點(diǎn)半或下午五點(diǎn)五十分開。(6) 優(yōu)秀學(xué)生應(yīng)做到思想身體學(xué)習(xí)都好。3 求下列各式的真值表(1) P (QP)。(2) (P(QR)(PR)Q)。(3) (P(QP)( P(PQ)。(4) (P(QR)(PQ)(PR)。(5) (PQ)(RQ)(PR)Q。(6) P(Q(R(P(QR)。(7) PQ。4 設(shè)命題A1，A2的真值為1，A3，A4兩命題的真值為0，求下列命題的真值：(1) 。 (2) 。 (3) 。 (4) 。5 將下列語(yǔ)句符號(hào)化：(

16、1) 占據(jù)空間的，有質(zhì)量而且不斷變化的稱之為物質(zhì)。(2) 占據(jù)空間的，有質(zhì)量者稱為物質(zhì)，而物質(zhì)是不斷變化的。(3) 如果你來(lái)了，那么他唱歌與否要看你是否伴奏而定。(4) 我們不能既劃船又跑步。4-4-2 命題公式與真值函數(shù) 由命題變?cè)?，括?hào)，邏輯聯(lián)結(jié)詞按下列規(guī)定形成的符號(hào)串是我們討論的對(duì)象。一、命題演算公式定義 4-4-2.1 由命題變?cè)?，邏輯?lián)結(jié)詞和括號(hào)構(gòu)成的下述表達(dá)式稱為命題合式公式（well formed formula）或命題演算公式，簡(jiǎn)稱公式，記為wff：(1) 單個(gè)原子命題變?cè)莣ff ；(2) 若P，Q是wff ，則 都是wff ；(3) 只有有限次使用(1),(2)得到的表達(dá)式

17、才是wff 。為了書寫和輸入計(jì)算機(jī)，以及進(jìn)行運(yùn)算方便起見，規(guī)定：(1) 的括號(hào)，整個(gè)wff的最外層括號(hào)可以省略，(2) 已定好邏輯聯(lián)結(jié)詞的優(yōu)先級(jí)后，優(yōu)先級(jí)的括號(hào)可省略。等都是wff。但就不是wff，因?yàn)榍耙槐磉_(dá)式R與S之間沒(méi)有邏輯聯(lián)結(jié)詞，后一表達(dá)式中括號(hào)不配對(duì)，故不符合定義4-4-2.1。按BNF（BackusNaur Form）符號(hào)，wff的語(yǔ)法定義為：wff：=| | ：=， ：=原子公式| wff *定義 4-4-2.2 令A(yù)為wff，對(duì)A中出現(xiàn)的全部原子命題變?cè)狿1，P2，Pn分別賦以真值0或1所得到的一組真值（n個(gè)）稱為A的一個(gè)指派或解釋。從4-4-1的例4-4-1.224-4-1.

18、24可以看出，對(duì)命題變?cè)髦概?，再利用邏輯?lián)結(jié)詞的真值表（即邏輯運(yùn)算規(guī)則）可以演算出wff的真值表。下面再看幾個(gè)例子。例4-4-2.1 求(PQ)(QP)的真值表。PQPQQP(PQ)QP）11111100100110000111解：例4-4-2.2 (PQ)PQ的真值表為解：PQPQ(PQ)P(PQ)PQ11111100010110100101 例4-4-2.3 (PQ)(PQ) 的真值表為PQPQPQ(PQ)(PQ)11100100100110000100 二、真值函數(shù)定義 4-4-2.3 以真，假為定義域和值域的函數(shù)為真值函數(shù)。 如由五個(gè)邏輯聯(lián)結(jié)詞產(chǎn)生的所有wff都是真值函數(shù)，因此有無(wú)窮

19、多個(gè)真值函數(shù)，顯然最基本而重要的真值函數(shù)還是 。 當(dāng)真值函數(shù)的變?cè)獮閚個(gè)時(shí)，共有2個(gè)指派。通過(guò)列出真值表也可以定義真值函數(shù)。例4-4-2.4 確定下列真值表對(duì)應(yīng)的真值函數(shù)：PQRf1 (P , Q , R)f2 (P , Q , R)1111111000101101001001100010000011000001以f1（P，Q，R）來(lái)考慮，表的第一行說(shuō)明f1的值為1，且指派中P，Q，R都取值為1，可用項(xiàng)PQR，表示，表的第三行說(shuō)明f1的值為1，此時(shí)指派中P，R取值為1，Q取值為0，即Q取值為1，可用表示，此時(shí)P，Q，R的其它指派都使PQR，或?yàn)?，同理可用分別表示表第四、七行的1，故f1（P，

20、Q，R）=同理 f2（P，Q，R）= 。注意： 由真值表確定的真值函數(shù)不一定是最簡(jiǎn)單的wff，不一定只有一個(gè)表達(dá)式。例如：PQRPRRPQQR(PR)(PQ)(QR)1111000111001000101101111000110101100000010010000010001100001000將這個(gè)真值表與f1（P，Q，R）的真值表相比較，對(duì)變?cè)娜我恢概?，可以看到與（*）這兩個(gè)表達(dá)式可代表同一個(gè)真值函數(shù)，而此兩式相比，(*) 就不是最簡(jiǎn)單的wff 。三、重言式與矛盾式 我們注意到例4-4-2.2，4-4-2.3和例4-4-2.1，4-4-2.4。對(duì)命題變?cè)獰o(wú)論作什么樣的指派，例4-4-2.2

21、中的wff永遠(yuǎn)取值為1，這種類型的wff稱為重言(永真)式；例4-4-2.3中的wff永遠(yuǎn)取值為0，這種類型的wff稱為矛盾（永假）式；而例4-4-2.1，4-4-2.4中的wff則對(duì)有的指派取值為1。對(duì)另外指派又取值為0，這種類型的wff稱為可滿足公式。顯然重言式（或永真函數(shù)）是可滿足公式，矛盾式是不可滿足公式。定義 4-4-2.4 對(duì)wff的命題變?cè)獰o(wú)論作什么指派，公式均取值1時(shí)，稱之為重言式，記為T；公式均取值0時(shí)稱之為矛盾式（或不可滿足式），記為F。若有指派使wff取值1，則稱該公式為可滿足公式。定理 4-4-2.1 任意兩個(gè)重言（矛盾）式的合取或析取仍然是一個(gè)重言（矛盾）式。由定義4

22、-4-2.4及析取、合取的真值表立即可以證明此定理。4-4-2 習(xí) 題1 下列符號(hào)串哪些是合式公式？哪些是重言式或矛盾式？哪些是可滿足公式？(1) ；(2) ；(3) ； (4) ；(5) ；(6) 。2 用真值表證明下列各式為重言式： ； ； 。4-4-3 公式的等價(jià)與蘊(yùn)涵在4-4-2中我們已經(jīng)看到真值函數(shù)f1(P,Q,R) 的表達(dá)式有： 或，又如和代表同一真值函數(shù)，對(duì)同一真值函數(shù)的幾個(gè)不同的wff 有下面的定義。定義 4-4-3.1 設(shè)P1，P2，Pn為出現(xiàn)在兩個(gè)wff A和B中的原子命題變?cè)?。如果?duì)P1，P2，Pn的任意真值指派，A和B的真值都相同，則稱A和B邏輯相等或說(shuō)A和B等價(jià)，記為

23、例如 ，用真值表和定義4-4-3.1可以得到下列基本等價(jià)式： (對(duì)合律) (冪等律) (交換律) (結(jié)合律)(分配律) (吸收律) (德.摩根律) (同一律) (零一律) (否定律) (條件等價(jià)式) (雙條件等價(jià)式) 當(dāng)wff中出現(xiàn)的原子命題變?cè)芏鄷r(shí)，用真值表和定義4-4-3.1來(lái)判斷兩個(gè)wff是否等價(jià)就顯得麻煩，因而可利用上述基本等價(jià)式和下面的定理4-4-3.1就可以得到一些復(fù)雜的等價(jià)式。定義 4-4-3.2 若wff X 是wff A的子串，則稱X為A的子公式。定理 4-4-3.1 X是wff A的一個(gè)子公式，wff Y與X等價(jià)，則將A中的X用Y來(lái)代替所得的wff B，必有A與B等價(jià)（替

24、換規(guī)則）。證明: 因?yàn)樵诿}變?cè)娜我庵概上耎與Y的真值相同，故用Y代替X后所得的wff B與A在任意相應(yīng)的指派下也有相同的真值，故A與B等價(jià)。例4-4-3.1 由吸收律和替換規(guī)則可知例 4-4-3.2 證明證明: 定理 4-4-3.2 在一個(gè)重言（矛盾）式中對(duì)同一命題變?cè)加萌我庖粋€(gè)wff去替換，仍可得一個(gè)重言（矛盾）式。證明: 因?yàn)橹匮裕埽┦降恼嬷涤罏?（0），與變?cè)闹概蔁o(wú)關(guān)，故對(duì)同一變?cè)萌我粀ff 替換后，其值仍為1（0），所以結(jié)果為一個(gè)重言（矛盾）式。例4-4-3.3 因?yàn)?，?dāng)P以某 wff 替換后仍為重言(矛盾)式，例如P以去代替，則有定理4-4-3.3 合式公式A和B等價(jià)當(dāng)

25、且僅當(dāng)AB為重言式。證明:必要性：若A與B等價(jià)，則對(duì)出現(xiàn)在A，B中的原子命題變?cè)娜我庵概葾和B有相同的真值，即AB永遠(yuǎn)取值1，即AB為重言。充分性：若AB為重言（矛盾）式，則無(wú)論任何指派AB均取值1，即A，B的真值相同，故AB。例4-4-3.4 證明 。證明: 故由定理4-4-3.3得證。例4-4-3.5 P(QR)(PQ)R證明： 容易驗(yàn)證 wff 等價(jià)具有下列性質(zhì)：(1) 反身（自反）性: 。(2) 對(duì)稱性: 若則。(3) 傳遞性:若，則。定義 4-4-3.3設(shè)合式公式A和B中出現(xiàn)的原子命題變?cè)獮?，如果?duì)它們的指派使A取值為1時(shí)B也取值為1，則稱A蘊(yùn)涵B（或稱B是A的邏輯結(jié)果），記為。例

26、4-4-3.6 。證明:PQPPQ1101100001110011從上面的真值表可知，使P取值1的指派0，1和0，0它也使PQ取值為1，根據(jù)定義4-4-3.3得證 PPQ。例4-4-3.7 。證明:PQRPQQR(PQ)(QR)PR11111111101000101010110001000111111010100100111110001111由真值表可知使(PQ)(QR )取值為1的指派(1，1，1)；(0,1,1)；(0,0,1)；（0，0，0）也使PR取值為1，根據(jù)定義4-4-3.3知。定理4-4-3.4合式公式AB當(dāng)且僅當(dāng)AB是重言式。證明：必要性：由AB的定義知當(dāng)A取值為1時(shí)，B取值也

27、為1。再由AB的運(yùn)算表知，當(dāng)A取值為1時(shí)，B取值也為1，AB為重言式。充分性：因?yàn)锳B為重言式，所以，當(dāng)A取值為1時(shí)，B的真值必為1(否則AB真值為假，與題設(shè)矛盾)，所以AB。例4-4-3.8 證明：由定理4-4-3.4得證。用定義4-4-3.3及定理4-4-3.4易證下列常用的基本蘊(yùn)涵式：(1) PQP，PQQ；(2) PPQ，QPQ；(3) P PQ；(4) QPQ；(5) (PQ)P；(PQ)Q；(6) P(PQ)Q； (分離規(guī)則)(7) Q(PQ)P；(8) P(PQ)Q ；(9) (PQ)(QR) PR；(10) (PQ)(PR) (QR) R；(11) (PQ) (RS)(PR)(

28、QS)；(12) (PQ) (Q R) P R。蘊(yùn)涵具有下列常用性質(zhì)：(1) A為重言式，AB，則B必為重言式；(2) 自反性 AA；(3) 反對(duì)稱性 若AB且 BA 則AB；(4) 傳遞性 若AB且 BC 則AC； (5) 若A B且 A C 則A B C 。(6) 若AB且CB，故A CB。證明: (1)、(2) 由AB的定義即可知。(3) 因?yàn)锳B且BA，所以AB與BA為重言式，由基本等價(jià)式(12)知AB為重言式，所以AB。(4) 由AB且BC知(AB)(BC)為重言式，據(jù)基本蘊(yùn)涵式(9)知(AB)(BC)AC，由性質(zhì)1知AC為重言式，故AC。(5) 因AB且AC，故(AB)，(BC)都

29、為重言式，如果A取值為1，則B和C都取值為1，因而BC取值為1；如果A取值為0，無(wú)論BC取值為1還是取0 ，ABC取值均為1，故ABC為重言式，所以ABC 。(6) 因AB且CB故(AB)(CB)T。即 (A B)(C B)T，即 (A C) BT，即 (A C) BT，即(A C)BT，故 AC B。4-4-3 習(xí) 題1證明（AB）（BC）（CA）（AB）（BC）（CA）。2不要構(gòu)造真值表證明下列蘊(yùn)涵式：(1) ；(2) ；(3) ；(4) ；(5) ；(6) 。3若是否有？若是否有？若是否有？4證明時(shí)。5證明時(shí)，反之也對(duì)。4-4-4 命題邏輯的推理理論邏輯是研究思維結(jié)構(gòu)和規(guī)則的科學(xué)，要求能

30、夠提供正確的思維規(guī)律，提供判定一個(gè)論斷之有效的準(zhǔn)則。數(shù)理邏輯則研究正確的推理規(guī)則，研究論斷的有效性,但要注意到：論斷的正確性涉及到實(shí)踐的檢驗(yàn)。什么是論斷的有效性呢？回憶4-4-3中命題公式的蘊(yùn)涵概念，并把它推廣。定義 4-4-4.1 和B為合式公式，若A1 A2 AnB，則稱B為前提的有效結(jié)論，或說(shuō)B是的邏輯結(jié)果，或者說(shuō)共同蘊(yùn)涵B。例4-4-4.1 證明 RS是P(QS)，RP ，Q的有效結(jié)論。證明：即要證(P(QS)(RP)QRS，也就是要證明(P(QS)(RP)Q(RS)為重言式。當(dāng)然可以應(yīng)用真值表驗(yàn)證，也可以用等價(jià)是驗(yàn)證，往往是比較麻煩的。因此判定論斷的有效性，需要有其他論證方法，希望有

31、比較簡(jiǎn)明的過(guò)程，還要有正確的依據(jù)。定理 4-4-4.1 若，則 。證明：已知，故為重言式。即為重言式，即為重言式，即為重言式，所以 。 定義4-4-4.2 設(shè)S為若干公式的集合（稱為前提集合）。如果有公式的有限序列其中Ai S 或Ai 是中某些公式的有效結(jié)論，且，則稱B是S的邏輯結(jié)果或有效結(jié)論，或者說(shuō)從S演繹出B。定理4-4-4.2 設(shè)S為公式集，B是一個(gè)公式，S能演繹出B的充分必要條件是：B是S的邏輯結(jié)果。證明： 充分性：因?yàn)锽是S的邏輯結(jié)果，由定義4-4-4.2知存在公式的有限序列,B(AiS), B是,的邏輯結(jié)果，因而由定義4-4-4.2得證S演繹出B。必要性：設(shè)S演繹出B，則存在公式的

32、有限序列其中A n=B且AiS或Ai是中某些公式的邏輯結(jié)果。下面用歸納法證明，因?yàn)?，A1S且A1A1，故A1是S的邏輯結(jié)果（歸納基礎(chǔ)）。設(shè)Ai (in) 是S的邏輯結(jié)果。（歸納假定），考慮i=n時(shí)的情形，即An是A1，A2，An-1 中某些公式的邏輯結(jié)果，設(shè)Aj1Aj2 Ajl An (4-4-4.1)其中。由歸納假定都是S的邏輯結(jié)果，即由4-4-3蘊(yùn)涵的性質(zhì)5得是S的邏輯結(jié)果，即 (4-4-4.2) 由(4-4-4.1)和(4-4-4.2)式及蘊(yùn)涵的傳遞性得SAn，而An =B，故SB，即B是S的邏輯結(jié)果。定理4-4-4.3 設(shè)S為前提公式集合，B和C是兩個(gè)公式，若SB演繹出C，則S演繹出B

33、C。證明：設(shè)S=A1, A2, , A n,因?yàn)镾B演繹出C，則C是SB的邏輯結(jié)果，即(A1A2 A n) BC。由定理4-4-4.1得A1A2 A n B C 。定理 4-4-4.3和基本等價(jià)式及基本蘊(yùn)涵式是論證演繹的根據(jù)，故在演繹推導(dǎo)過(guò)程中必須遵循下列推理規(guī)則：P規(guī)則：在推演過(guò)程中可以隨便使用前提。T規(guī)則：在推演過(guò)程中可以任意使用前面演繹的某些公式的邏輯結(jié)果，當(dāng)借助于等價(jià)式記為TE，當(dāng)借助于蘊(yùn)涵式時(shí)記為TI。CP規(guī)則：如果需要演繹出的公式為BC形，那么將B作為附加前提，設(shè)法演繹出C來(lái)。P規(guī)則和T規(guī)則的依據(jù)是定義4-4-4.2，CP規(guī)則的依據(jù)是定理4-4-4.3。當(dāng)然，論證的方法是前變?nèi)f化的

34、，除使用真值表方法以外，基本的方法就是：直接證法：由一組前提和P規(guī)則，T規(guī)則演繹出有效結(jié)論；另一方法是間接證法：(1)由一組前提和P規(guī)則，T規(guī)則，CP規(guī)則演繹出有效結(jié)論；(2)反證法，否定結(jié)論后作為附加前提，利用P規(guī)則和T規(guī)則得出矛盾式。定義4-4-4.3 設(shè)P1，P2 ，P n 是A1，A2 ，A m 中出現(xiàn)的原子命題變?cè)?，若?duì)P1，P2 ，P3 ，Pn 的一些真值指派，A1 A2 Am 取值為1，則稱A1，A2，A m 是相容的，若對(duì)P1，P2，P3 ，Pn 的任何指派，A1 A2 Am 取值為0，則稱A1，A2 ，A m 是不相容的（矛盾的）。定理4-4-4.4 A1 A2 A m B

35、當(dāng)且僅當(dāng)A1，A2 ，Am ，B是不相容的。證明: A1 A2 A m B 當(dāng)且僅當(dāng)A1 A2 A m B T（重言式），當(dāng)且僅當(dāng)(A1 A2 A m )BT，當(dāng)且僅當(dāng)A1 A2 Am BF(矛盾式)，當(dāng)且僅當(dāng)A1，A2 ，A n，B是不相容的。下面給出利用上面的推理理論來(lái)論證若干實(shí)例。例4-4-4.1 證明RS是 P(QS)，RP，Q 的邏輯結(jié)果。證明：(1) P(2) R P( 附 加 前 提)(3) P T (1)(2) I(4) P(QS) P(5) QS T(3)(4)I(6) Q P(7) S T(5)(6) I(7) RS CP (2)(7)例4-4-4.1 的這種書寫方法寫出了

36、演繹的公式序列和使用的規(guī)則，便于復(fù)核檢查推演的過(guò)程，以下都采用這樣的書寫方法。例4-4-4.2 (PQ)(PR) (QS) SR證明: (1) PQ P(2) PQ T(1)E(3) QS P(4) PS T(2)(3)I(5) SP T(4)E(6) PR P(7) SR T(5)(6)I(8) SR T(7)E或者(1) PR P(2) PQRQ T(1)I(3) QS P(4) RQRS T(3)I(5) PQ RS T(2)(4)I(6) PQ P(7) RS T(5)(6)I這個(gè)例子說(shuō)明：從前提演繹出公式時(shí)的有限序列不是唯一的，將兩種演繹步驟直觀地分別表示為下面的兩個(gè)圖： （1） （

37、1） （3） （2） （3） （2） （4） （4） （5） （6） （5） （6） （7）（7）（8） 圖4-4-4.1例4-4-4.2采用的是直接證法。例4-4-4.3 證明S=AB，(BC)演繹出 A。證明： (1) AB P(2) A P （附加前提） (3) (BC） P(4) BC T(3)E(5) B T(1)(2)I(6) B T(4)I(7) BBF T(5)(6)E(8) A 定理4-4-4.4例4-4-4.4 用間接證法證明例4-4-4.2。證明: (1) (SR) P（附加前提） (2) SR T(1)E (3) PQ P (4) PQ T(3)E(5) QS P(6)

38、 PS T(4)(5)I(7) SP T(6)E(8) SRRP T(7)I(9) RP T(2)(8)I(10) PR P(11) PR T(10)E(12) (PR） T(11)E(13) (PR)(PR)F T(9)(12)E(14) SR 定理4-4-4.4例4-4-4.5 “如果下雨，春游就改期，如果沒(méi)有球賽，春游就不改期。結(jié)果沒(méi)有球賽，所以沒(méi)有下雨”，證明這是有效的論斷。證明： 令A(yù)：天下雨 B：春游改期 C：沒(méi)有球賽。 符號(hào)化題中各語(yǔ)句得 S= AB，C B，C ，SA。(1) AB P(2) CB P(3) BC T(2)E(4) AC T(1)(3)I(5) CA T(4)E

39、(6) C P(7) A T(5)(6)I例4-4-4.6 如果學(xué)生學(xué)習(xí)努力，他們的父親或母親就高興，若母親高興，學(xué)生就不努力學(xué)習(xí)，若老師只表?yè)P(yáng)學(xué)生，學(xué)生的父親就不高興，故如果學(xué)生學(xué)習(xí)努力，老師就不是只表?yè)P(yáng)學(xué)生。試證這是有效的結(jié)論。證明: 令A(yù)：學(xué)生學(xué)習(xí)努力；B：學(xué)生的父親高興；C：學(xué)生的母親高興；D：老師只表?yè)P(yáng)學(xué)生。則問(wèn)題符號(hào)化為：ABC，C A，DBAD(1) DB P(2) BD T(1)E(3) CA P (4) AC T(3)E(5) A(BC) P(6) A(CB) T(5)E(7) A P(附加前提)(8) C T(4)(7)I(9) CB T(6)(7)I(10) B T(8)

40、(9)I (11) D T(2)(10)I (12) AD CP例4-4-4.7 證明下列命題是不相容的：如果他因病缺課，那么他考試不及格，如果他考試不及格，他就受不到教育。若他讀了許多書，則他受到了教育，但是，雖然他因病缺課，他還是讀了許多書。證明 令P：他因病缺課，Q：他考試不及格，R：他受不到教育，S：他讀了許多書。則問(wèn)題符號(hào)化為 PQ，QR，SR，PSF ?，F(xiàn)證之。(1) PQP(2) QR P(3) PRT(1)(2)I(4) SR P(5) RS T(4)E(6) PST(3)(5)I(7) PST(6)E(8) (PS) T(7)E(9) PSP(10) FT(8)(9)E例4-

41、4-4.6和例4-4-4.7的推演步驟分別如下圖所示： （1） （5） （3） （1） （2） （4） （2） （6）（7）（4） （3） （5） （8） （9） （6）（10） （7） （11） （8） （9）（12） （10） 圖4-4-4.24-4-4 習(xí) 題1.用直接證法推演下列蘊(yùn)涵式。(1) AB，CBAC； (2) ABCD，DEGAG； (3) A(BC)，CDE，GDEA(BG)；(4) (ABC)(BD)(EG)D)(BAE)BE；(5) (AB)(CD)，(BE)(DG)，(EG)，ACA；2用間接證法證明上題。3將上題中推演步驟的圖示作出來(lái)。4在下列前提下，結(jié)論是否有效？

42、今天或著天晴或者下雨。如果天晴，我去看電影，若我去看電影，我就不看書，故我在看書時(shí)說(shuō)明今天下雨。5如果廠方拒絕增加工資，那么罷工就不會(huì)停止，除非罷工超過(guò)一年并且工廠撤換了廠長(zhǎng)。問(wèn)：若廠方拒絕增加工資，而罷工剛開始，罷工是否能夠停止？6下列命題相容嗎？(1) PQ ，QR ，RS ，PS ，S；(2) PQ ，RS ，Q ，S。7下面的推導(dǎo)正確嗎？如果不正確要指出原因。(1) AB，CB，D(AC)，DB。 D(AC) P D P AC TI AB P CB P ACB T I B T I(2) A(CB)，DA，CDB。 DA P D P(附加前提) A T I A(CB) P CB T I

43、C P B TI DB CP8對(duì)下面的每一組前提，寫出可能導(dǎo)出的結(jié)論和所用的推理規(guī)則：（1）我跑步就感到累，我不累。（2）若他犯了錯(cuò)誤，則他的神色慌張，他神色慌張。（3）如果我編的程序通過(guò)了，那么我很快活，若我很快活，則天氣很好，現(xiàn)在是半夜天很好。（4）如果我學(xué)習(xí)，那么我的功課不會(huì)不及格。若我不熱衷于玩撲克，則我學(xué)習(xí)，但我的功課不及格。（5）人總是要死的，蘇格拉底是人。4-4-5 對(duì)偶與范式在4-4-4中我們已經(jīng)看到基本等價(jià)式在推論中是非常有用的，而4-4-3列出基本等價(jià)式(2)(10)都是成對(duì)出現(xiàn)的，即把一個(gè)公式的換成。T換成F就可得出另一式，反過(guò)來(lái)將另一公式的換成，F(xiàn)換成T也可以得到這一個(gè)公式，我們認(rèn)為邏輯聯(lián)結(jié)詞和，重言式T與矛盾式F是互為對(duì)偶的。定義4-4-5.1 在只含邏輯聯(lián)結(jié)詞，的公式A中將換成，換成，如果A中有T或者F就分別換成F或T，所得到的新公式A