離散數(shù)學(xué)-第1章-命題邏輯

第1章命題邏輯

1.1命題及聯(lián)結(jié)詞

1.2命題公式與翻譯

1.3真值表和等價(jià)公式

1.4重言式

1.5范式

1.6全功能聯(lián)結(jié)詞集

1.7對偶式與蘊(yùn)含式

1.8命題邏輯的推理理論

返回總目錄1.1命題及聯(lián)結(jié)詞1.1.1命題的根本概念命題的定義在數(shù)理邏輯中把能判斷真假的陳述句稱為命題。命題的表示一般用小寫英文字母或帶下標(biāo)的小寫英文字母表示。Remark：⑴只有陳述句才有可能成為命題⑵能判斷真假的陳述句⑶雖然要求命題能判斷真假，但不要求現(xiàn)在就能確定真假，將來可以確定真假也可以。命題的真值：一個(gè)命題表達(dá)的判斷結(jié)果稱為命題的真值。任何命題的真值是惟一的。真值為“真〞TrueT1(真)真命題真值為“假〞FalseF0(假)假命題【例1.1】判斷以下語句是否為命題。假設(shè)是命題，確定其真值。⑴上海是個(gè)小村莊。⑵存在外星人。⑶禁止吸煙?、缺本┦侵袊氖锥?。⑸4是素?cái)?shù)或6是素?cái)?shù)。⑹今天你吃了嗎？⑺11+1=100 ⑻我正在說謊。解：⑴命題(F)，⑵命題(待定)，⑶不是命題(祈使句)，⑷命題(T)，⑸命題(F)，⑹不是命題(疑問句),⑺命題(由上下文確定),⑻不是命題(悖論)。

命題常量與命題變元表示命題的小寫英文字母或帶下標(biāo)的小寫英文字母常稱為命題標(biāo)識符。如果命題標(biāo)識符表示一個(gè)具體、確定的命題，稱為命題常元。如果命題標(biāo)識符表示任意一個(gè)命題，稱為命題變元。？命題變元是命題嗎？不是命題變元代表任意的命題，其真值是不確定的。因而不是命題。

原子命題與復(fù)合命題〔將命題完整分類〕原子命題:如果一個(gè)命題不能再分解成更簡單的命題復(fù)合命題:如果一個(gè)命題不是原子命題原子變元：顧名思義，原子變元表示的是任意一個(gè)原子命題。思考：原子命題和復(fù)合命題之間有什么樣的關(guān)系呢？

在自然語言中，可以通過“如果…，那么…〞，“不但…，而且…〞這樣的連詞將簡單的陳述句聯(lián)結(jié)成復(fù)合語句，同樣在命題邏輯當(dāng)中，也可以通過命題聯(lián)結(jié)詞將原子變元聯(lián)結(jié)起來表示復(fù)合命題。1.1.2命題聯(lián)結(jié)詞常用的邏輯聯(lián)結(jié)詞有五種：否認(rèn)、合取、析取、條件和雙條件。

1.否認(rèn)聯(lián)結(jié)詞〔否〕設(shè)p為命題，那么p的否認(rèn)是一個(gè)復(fù)合命題.記作：?p，讀作“非p〞或“p的否認(rèn)〞。定義為：假設(shè)p為T，那么?p為F；假設(shè)p為F，那么?p的真值為T。表1.1

p?p

0110【例1.2】否認(rèn)以下命題。p：中國的每一個(gè)城市都是沿海城市。?p：??中國的每一個(gè)城市都不是沿海城市。中國的每一個(gè)城市不都是沿海城市。2.合取聯(lián)結(jié)詞〔與〕設(shè)p和q均為命題，那么p和q的合取是一個(gè)復(fù)合命題記作p∧q，讀作“p與q〞或“p合取q〞。定義：當(dāng)且僅當(dāng)p和q均為T時(shí)，p∧q的才為T。聯(lián)結(jié)詞“∧〞是二元邏輯運(yùn)算。

pqp∧q000010100111

【例1.3】設(shè)p：2023年在北京舉辦奧運(yùn)會。q：中國是世界四大文明古國之一。那么p∧q：2023年在北京舉辦奧運(yùn)會并且中國是世界四大文明古國之一。補(bǔ)充說明：在自然語言中：p和q假設(shè)沒有內(nèi)在的聯(lián)系，p∧q所表示的命題沒有實(shí)際意義在命題邏輯中：只要p和q的真值能確定，那么p∧q就可以成為一個(gè)新命題，不管這新命題在自然語言中是否有意義。3.析取聯(lián)結(jié)詞〔或者〕設(shè)p和q均為命題，那么p和q的析取是一個(gè)復(fù)合命題，記作p∨q，讀作“p或q〞或者“p析取q〞。定義為：當(dāng)且僅當(dāng)p和q均為F時(shí)，p∨q才為F。聯(lián)結(jié)詞“∨〞是二元邏輯運(yùn)算。pqp∨q000011101111

“∨〞與漢語中的“或〞相似，但又不相同?！纠?.4】以下兩個(gè)命題中的“或〞，哪個(gè)是可兼或？哪個(gè)是不可兼或？⑴在電視上看這場雜技或在劇場里看這場雜技。(不可兼)⑵燈泡有故障或開關(guān)有故障。(可兼,“∨〞是可兼或)4.條件聯(lián)結(jié)詞〔如果…那么…〕設(shè)p和q均為命題，其條件命題是個(gè)復(fù)合命題。記為：p→q。讀作“如果p，那么q〞或“假設(shè)p，那么q〞。定義為：當(dāng)且僅當(dāng)p為T，q為F時(shí)，p→q才為F。pqp→q00011011

p稱為條件命題p→q的前件，q稱為條件命題p→q的后件。聯(lián)結(jié)詞“→〞是二元邏輯運(yùn)算。【例1.5】p：小王努力學(xué)習(xí)。q：小王學(xué)習(xí)成績優(yōu)秀。p→q：如果小王努力學(xué)習(xí)，那么他的學(xué)習(xí)成績就優(yōu)秀。

聯(lián)結(jié)詞“→〞與漢語中的“如果…，那么…〞或“假設(shè)…，那么…〞相似，但又是不相同的。(區(qū)別有2條)5.雙條件聯(lián)結(jié)詞(當(dāng)且僅當(dāng))設(shè)p和q均為命題，其復(fù)合命題p?q稱為雙條件命題。讀作：“p雙條件q〞或者“p當(dāng)且僅當(dāng)q〞。定義為：當(dāng)且僅當(dāng)p和q的真值相同時(shí)，p?q為T。聯(lián)結(jié)詞“?〞是二元邏輯運(yùn)算。

pqp?q00011011雙條件聯(lián)結(jié)詞表示的是一個(gè)充分必要關(guān)系，可以不必顧及其前因后果，而只根據(jù)聯(lián)結(jié)詞的定義來確定其真值。本節(jié)學(xué)習(xí)目標(biāo)：〔1〕理解并掌握命題的概念，學(xué)會判斷一個(gè)語句是否為命題并確定其真值?！?〕牢固掌握五類聯(lián)結(jié)詞的定義與其真值表。1.2命題公式與翻譯把命題常量，命題變量按照一定的邏輯順序用命題聯(lián)結(jié)詞連接起來就構(gòu)成了命題演算的合式公式，也叫命題公式。

定義按以下規(guī)那么構(gòu)成的符號串稱為命題演算的合式公式。〔根底〕⑴單個(gè)命題變元和常元是合式公式?！矚w納〕⑵如果A是合式公式，那么?A是合式公式。〔歸納〕⑶如果A和B是合式公式，那么(A∧B)、(A∨B)、(A→B)和(A?B)是合式公式?！步缦蕖尝犬?dāng)且僅當(dāng)有限次地應(yīng)用了⑴、⑵、⑶所得到的符號串是合式公式。

命題公式一般的用大寫的英文字母A，B，C，…表示。為方便起見，對命題公式約定如下：

⑴最外層括號可以省略。⑵規(guī)定聯(lián)結(jié)詞的優(yōu)先級由高到低依次為

?，∧，∨，→，?。按此優(yōu)先級別，如果去掉括號，不改變原公式運(yùn)算次序，也可以省掉這些括號。？命題公式是命題嗎？一般地說，命題公式中包含命題變元，因而無法計(jì)算其真值，所以不是命題。

用命題公式表示復(fù)合命題，常將這個(gè)過程稱為命題的符號化?！卜g〕命題的符號化可按如下步驟進(jìn)行：⑴找出原子命題。⑵用小寫的英文字母或帶下標(biāo)的小寫的英文字母表示原子命題。⑶用命題聯(lián)結(jié)詞將這些小寫的英文字母或帶下標(biāo)的小寫的英文字母連接起來。

從例1.7中可以看出：〔1〕具有否認(rèn)意義的命題一定不是原子命題〔2〕對于不可兼或的表示，可用?(p?q)本小節(jié)學(xué)習(xí)目標(biāo)：〔1〕了解命題公式的概念，掌握五類連接詞的優(yōu)先級〔2〕掌握如何將一個(gè)復(fù)合命題符號化？1.3真值表和等價(jià)公式命題公式的真值表定義設(shè)pl，p2，…，pn是出現(xiàn)在公式A中的全部命題變元，給pl，p2，…，pn各指定一個(gè)真值，稱為對公式A的一個(gè)賦值或解釋。假設(shè)賦值使A的真值為T，那么稱這個(gè)賦值為A的成真賦值，假設(shè)賦值使A的真值為F，那么稱這個(gè)賦值為A的成假賦值。

定義1.3.2在命題公式A中，對A的每一個(gè)賦值，就確定了A的一個(gè)真值，把它們匯列成表，稱該表為命題公式A的真值表。構(gòu)造真值表的幾點(diǎn)注意：[1]先找出公式中所含的所有命題變元[2]第1行：命題變元；排列：由小到大；字典順序[3]前n列：賦值；排列：從00…0到11…1遞增如果公式A有n個(gè)命題變元，那么A的真值表應(yīng)該有多少行？【例1.8】構(gòu)造命題公式?p∨q的真值表，并求成真賦值和成假賦值。解：表1.6pq?p?p∨q001011100110表1.7pqp∧q?p?q?p∧?q(p∧q)∨(?p∧?q)0001111010100010001001110001【例1.9】構(gòu)造命題公式(p∧q)∨(?p∧?q)的真值表，并求成真賦值和成假賦值。解：命題公式(p∧q)∨(?p∧?q)的真值表如表1.7所示。00，11是成真賦值，01，10是成假賦值。Remark：1.如果公式A有n個(gè)命題變元，那么A的真值表應(yīng)該有多少行？2.什么叫做兩個(gè)真值表相等？取決于真值表的最后一列是否相同。命題公式的等價(jià)定義1.3.3設(shè)A和B是兩個(gè)命題公式，對A和B的任一賦值，A和B的真值都相同，那么稱A和B等價(jià)的或邏輯相等的，記為AB命題公式等價(jià)有下面的三條性質(zhì)：⑴自反性，AA⑵對稱性，假設(shè)AB，那么BA⑶傳遞性，假設(shè)AB，BC，那么AC

所謂兩個(gè)命題公式等價(jià)即為兩個(gè)公式的真值表相同，所以我們可以用真值表來驗(yàn)證兩個(gè)命題公式是否等價(jià).

【例1.12】根據(jù)等價(jià)的定義，用真值表證明

p→(q→p)

?p→(p→?q)證明：構(gòu)造p→(q→p)和

p→(p→

q)的真值表表1.10pq?p?qq→pp→(q→p)p→?q?p→(p→?q)00111111011001111001111111001101證明等價(jià)的另外一種方法叫做等價(jià)演算法，其根本思想是：先用真值表證明一組根本等價(jià)式，以它們?yōu)楦走M(jìn)行公式之間的演算。根本等價(jià)式常叫命題定律。下面是常用的命題定律。1.雙重否認(rèn)律 A??A2.交換律 A∨BB∨A，A∧BB∧A3.結(jié)合律 (A∨B)∨CA∨(B∨C) (A∧B)∧CA∧(B∧C)4.分配律 A∧(B∨C)(A∧B)∨(A∧C) A∨(B∧C)(A∨B)∧(A∨C)5.德摩根律

?(A∨B)

?A∧?B

?(A∧B)

?A∨?B6.冪等律

A∧A

A，A∨A

A7.吸收律

A∨(A∧B)

A，

A∧(A∨B)

A8.零律

A∨1

1，A∧0

09.同一律A∨0

A，

A∧1

A

10.排中律 A∨?A111.矛盾律A∧?A012.條件等價(jià)式 A→B?A∨B13.雙條件等價(jià)式 A?B(A→B)∧(B→A)14.假言易位式 A→B?B→?A15.雙條件否認(rèn)等價(jià)式A?B?A??B

定義〔子公式〕如果X是合式公式A的一局部且X本身也是合式公式，那么稱X為公式A的子公式。例如，Aq→(p∨(p∧q))，Xp∧q，那么X是A的子公式。定理〔等價(jià)置換〕設(shè)X是合式公式A的子公式，假設(shè)XY，如果將A中的X用Y來置換，得到的公式記為B，那么B與A等價(jià)，即AB

返回章目錄本小節(jié)學(xué)習(xí)目標(biāo)：1.能夠?qū)懗鋈我幻}公式的真值表。2.能熟練地應(yīng)用命題定律來證明兩個(gè)命題公式的等價(jià)。1.4重言式定義設(shè)A是任一命題公式。⑴假設(shè)對A的任意賦值，其真值永為真，那么稱命題公式A為重言式或永真式。⑵假設(shè)對A的任意賦值，其真值永為假，那么稱命題公式A為矛盾式或永假式。⑶假設(shè)A不是矛盾式，那么稱命題公式A為可滿足的。Remark：1.任何重言式都是可滿足的。2.重言式的真值表的最后一列全為1，矛盾式的真值表的最后一列全為0，可滿足的公式真值表的最后一列至少有一個(gè)1。3.亦可以用等價(jià)演算法判斷公式的類型。

定理

任何兩個(gè)重言式的合取或析取都是重言式。任何兩個(gè)矛盾式的合取或析取都是矛盾式。定理

一個(gè)重言式，對同一分量出現(xiàn)的每一處都用同一合式公式置換，其結(jié)果仍是重言式。一個(gè)矛盾式，對同一分量出現(xiàn)的每一處都用同一合式公式置換，其結(jié)果仍是矛盾式?！纠?.19】由排中律知p∨?p為重言式，以((p∨q)∧r)去置換其中的p，得公式((p∨q)∧r)∨?((p∨q)∧r)，這是重言式。

定理

設(shè)A、B為兩個(gè)命題公式，A

B當(dāng)且僅當(dāng)A?B是重言式。證明：設(shè)A

B，下證A?B是重言式。因?yàn)锳

B，所以A，B具有相同的真值，由雙條件聯(lián)結(jié)詞的定義知A?B為真，所以A?B為重言式。設(shè)A?B為重言式，下證A

B給A，B的任何賦值，因?yàn)锳?B為重言式，故A，B的真值相同，由命題公式等價(jià)的定義知A

B1.5范式析取范式與合取范式定義1.5.1(根本和)由一些命題變元或其否認(rèn)構(gòu)成的析取式稱為根本和，也叫簡單析取式。約定單個(gè)變元或其否認(rèn)是根本和。定義1.5.2(根本積)由一些命題變元或其否認(rèn)構(gòu)成的合取式稱為根本積，也叫簡單合取式。約定單個(gè)變元或其否認(rèn)是根本積。定義1.5.3(合取范式)由根本和的合取構(gòu)成的公式叫做合取范式。約定單個(gè)根本和是合取范式。定義1.5.4(析取范式)由根本積的析取構(gòu)成的公式叫做析取范式。約定單個(gè)根本積是析取范式。

任何命題公式都可以化成與其等價(jià)的析取范式或合取范式。步驟如下：⑴消去聯(lián)結(jié)詞“→〞和“?〞⑵消去“?〞(雙重否認(rèn)律)內(nèi)移“?〞(德摩根律)⑶利用分配律，結(jié)合律將公式歸約為合取范式和析取范式。

【例1.21】求命題公式(p∨q)?p的合取范式和析取范式。解：⑴求合取范式(p∨q)?p

((p∨q)→p)∧(p→(p∨q))(消去?)

(?(p∨q)∨p)∧(?p∨(p∨q))(消去→)

((?p∧?q)∨p)∧(?p∨(p∨q))(

內(nèi)移)

(?p∨p)∧(?q∨p)∧(?p∨p∨q)(分配律，合取范式)

1∧(?q∨p)∧(1∨q)(排中律)

1∧(?q∨p)∧1(零律，合取范式)

(?q∨p)(同一律，合取范式)

⑵求析取范式(p∨q)?p

((p∨q)∧p)∨(?(p∨q)∧?p)(消去?)

((p∨q)∧p)∨((?p∧?q)∧?p)(

內(nèi)移)

p∨(?p∧?q∧?p) (吸收律，析取范式)

p∨(?p∧?p∧?q) (交換律)

p∨(?p∧?q) (冪等律，析取范式)命題公式的公式的合取范式并不唯一,析取范式也不惟一。

主析取范式定義1.5.5(極小項(xiàng))在根本積中，每個(gè)變元及其否認(rèn)不同時(shí)存在，但兩者之一必須出現(xiàn)且僅出現(xiàn)一次，這樣的根本積叫做布爾合取也叫小項(xiàng)或極小項(xiàng)。兩個(gè)命題變元的極小項(xiàng)有:p∧q，p∧?q，?p∧q，?p∧?qn個(gè)命題變元共有幾個(gè)極小項(xiàng)??2n表1.13極小項(xiàng)成真賦值名稱?p∧?q00m0?p∧q01m1p∧?q10m2p∧q11m3表1.12

pqp∧qp∧?q?p∧q?p∧?q000001010010100100111000極小項(xiàng)有以下的性質(zhì)：⑴每個(gè)極小項(xiàng)只有一個(gè)成真賦值，且各極小項(xiàng)的成真賦值互不相同。極小項(xiàng)和它的成真賦值構(gòu)成了一一對應(yīng)的關(guān)系?？捎贸烧尜x值為極小項(xiàng)進(jìn)行編碼;(極小項(xiàng)與其成真賦值的對應(yīng)關(guān)系為：變元對應(yīng)1，而變元的否認(rèn)對應(yīng)0。)(2)任意兩個(gè)不同的極小項(xiàng)的合取為永假式;(3)所有極小項(xiàng)的析取為永真式;表1.14極小項(xiàng)成真賦值名稱?p∧?q∧?r000m0?p∧?q∧r001m1?p∧q∧?r010m2?p∧q∧r011m3p∧?q∧?r100m4p∧?q∧r101m5p∧q∧?r110m6p∧q∧r111m7

定義1.5.6(主析取范式)對于給定的命題公式，如果有一個(gè)它的等價(jià)公式，僅由極小項(xiàng)的析取組成，稱該公式為原公式的主析取范式.任何命題公式都存在著與之等價(jià)的主析取范式?？捎梢韵聝煞N方法求得：⑴等價(jià)演算法⑵真值表法

用等價(jià)演算法求主析取范式的步驟如下：①化歸為析取范式。②除去析取范式中所有永假的根本積。③在根本積中，將重復(fù)出現(xiàn)的合取項(xiàng)和相同變元合并。④在根本積中補(bǔ)入沒有出現(xiàn)的命題變元，即添加∧(p∨?p)，再用分配律展開，最后合并相同的極小項(xiàng)。

用真值表求主析取范式的步驟如下：①構(gòu)造命題公式的真值表。

②找出公式的成真賦值對應(yīng)的極小項(xiàng)。③這些極小項(xiàng)的析取就是此公式的主析取范式。

【例1.24】用等價(jià)演算法和真值表法，求(p→q)→r的主析取范式。

解：表1.15pqrp→q(p→q)→r0001000111010100111110001101011101011111公式的成真賦值對應(yīng)的極小項(xiàng)為：?p∧?q∧r (成真賦值為001)?p∧q∧r (成真賦值為011)p∧?q∧?r (成真賦值為100)p∧?q∧r (成真賦值為101)p∧q∧r (成真賦值為111)(p→q)→r的主析取范式為：(p∧q∧r)∨(p∧?q∧r)∨(p∧?q∧?r)∨(?p∧q∧r)∨(?p∧?q∧r)

m111∨m101∨m100∨m011∨m001

m7∨m5∨m4∨m3∨m1

∑1，3，4，5，7Remark:(1)矛盾式無成真賦值，因而主析取范式為0。(2)重言式無成假賦值，因而主析取范式含2n

(n為公式中命題變元的個(gè)數(shù))個(gè)極小項(xiàng)。主合取范式定義1.5.7(極大項(xiàng))在根本和中，每個(gè)變元及其否認(rèn)不同時(shí)存在，但兩者之一必須出現(xiàn)且僅出現(xiàn)一次，這樣的根本和叫作布爾析取，也叫大項(xiàng)或極大項(xiàng)。兩個(gè)變元p，q構(gòu)成的極大項(xiàng)為：p∨q，p∨?q，?p∨q，?p∨?qn個(gè)變元共有2n個(gè)極大項(xiàng)。極大項(xiàng)有以下三個(gè)性質(zhì)：⑴每個(gè)極大項(xiàng)只有一個(gè)成假賦值，極大項(xiàng)不同，成假賦值也不同。極大項(xiàng)和它的成假賦值構(gòu)成了一一對應(yīng)的關(guān)系。故可用成假賦值為該極大項(xiàng)進(jìn)行編碼;(極大項(xiàng)與成假賦值的對應(yīng)關(guān)系為：變元對應(yīng)0，而變元的否認(rèn)對應(yīng)1。)⑵任意兩個(gè)不同的極大項(xiàng)的析取式為永真式;⑶全體極大項(xiàng)的合取式為永假式;定義(主合取范式)對于給定的命題公式，如果有一個(gè)它的等價(jià)公式，僅由極大項(xiàng)的合取組成，那么該等價(jià)式稱為原公式的主合取范式。

任何命題公式都存在著與之等價(jià)的主合取范式。也可由以下兩種方法求得。⑴等價(jià)演算法(2)真值表法

用等價(jià)演算法求主合取范式,步驟如下：①化歸為合取范式。②除去所有永真的根本和。③在根本和中合并重復(fù)出現(xiàn)的析取項(xiàng)和相同的變元。④在根本和中補(bǔ)入沒有出現(xiàn)的命題變元。即增加∨(p∧?p)，然后，應(yīng)用分配律展開公式，最后合并相同的極大項(xiàng)。

用真值表求主合取范式的步驟如下：①構(gòu)造命題公式的真值表。②找出公式的成假賦值對應(yīng)的極大項(xiàng)。③這些極大項(xiàng)的析取就是此公式的主合取范式。

Remark:(1)矛盾式無成真賦值，因而矛盾式的主合取范式含2n(n為公式中命題變元的個(gè)數(shù))個(gè)極大項(xiàng)。(2)重言式無成假賦值，因而主合取范式記為1。同一公式的主析取范式中m的下標(biāo)和主合取范式中M的下標(biāo)是互補(bǔ)的。因此，知道了主析(合)取范式就可以寫出主合(析)取范式。本小節(jié)學(xué)習(xí)目標(biāo):1.能熟練寫出任一命題公式的等價(jià)主合取范式和主析取范式.不可兼析取有以下性質(zhì):(1)交換律(2)結(jié)合律定義(與非)設(shè)p和q是兩個(gè)命題，復(fù)合命題p↑q稱作p和q的與非。定義為：當(dāng)且僅當(dāng)p和q真值都是真時(shí)，p↑q才為假。由定義可以看出下式成立：p↑q

?(p∧q)

表1.19pqp↑q001011101110

聯(lián)結(jié)詞“↑〞還有以下幾個(gè)性質(zhì)：⑴p↑p?(p∧p)?p⑵(p↑q)↑(p↑q)?(p↑q)??(p∧q)p∧q⑶(p↑p)↑(q↑q)(?p)↑(?q)?(?p∧?q)p∨q

定義1.6.3(或非)設(shè)p和q是兩個(gè)命題，復(fù)合命題p↓q稱作p和q的或非。定義為：當(dāng)且僅當(dāng)p、q的真值都為假時(shí)，p↓q的真值為真。表1.20pqp↓q001010100110由此定義可得：p↓q

?(p∨q)聯(lián)結(jié)詞↓還有下面的幾個(gè)性質(zhì)：⑴

p↓p

?(p∨p)

?p⑵(p↓q)↓(p↓q)?(p↓q)

??(p∨q)

p∨q⑶(p↓p)↓(q↓q)?p↓?q?(?p∨?q)

p∧q

定義1.6.4設(shè)S是一個(gè)聯(lián)結(jié)詞集合，如果任何n(n≥1)個(gè)變元組成的公式，都可以由S中的聯(lián)結(jié)詞來表示，那么稱S是全功能聯(lián)結(jié)詞集。?，∧，∨?，∧和?，∨定義1.6.5(最小全功能聯(lián)結(jié)詞集)設(shè)S是全功能聯(lián)結(jié)詞集，如果去掉其中的任何聯(lián)結(jié)詞后，就不是全功能聯(lián)結(jié)詞集.

?，∧

，

?，∨

，

↑

，

↓

是最小全功能聯(lián)結(jié)詞集。n個(gè)命題變元可以構(gòu)成多少個(gè)不等價(jià)的命題公式??

上述問題就轉(zhuǎn)化為n個(gè)命題變元構(gòu)成的命題公式有多少個(gè)不同的真值表？

表1.21pq公式001或0011或0101或0111或0返回章目錄

1.7對偶式與蕰含式

對偶式定義在僅含聯(lián)結(jié)詞?，∧，∨的命題公式A中，將聯(lián)結(jié)詞∨，∧，F(xiàn)，T分別換成∧，∨，T，F(xiàn)所得的公式稱為公式A的對偶式，記為A*。設(shè)A*是A的對偶式，那么A

是A*的對偶式，(A*)*

A。A*和A互為對偶式。

【例1.27】求p↑q和p↓q的對偶式。解：

p↑q

?(p∧q)?(p∧q)的對偶式是?(p∨q)

p↓q故p↑q的對偶式是p↓q對偶式概念可以推廣為：在僅含有聯(lián)結(jié)詞?，∧，∨，↑，↓的命題公式中，將聯(lián)結(jié)詞∨，∧，↑，↓，F(xiàn)，T分別換成

∧，∨，↓，↑，T，F(xiàn)，就得到了它的對偶式。

定理1.7.1設(shè)A*是A的對偶式，p1，p2，…，pn是出現(xiàn)在A和A*中的原子變元，那么?A(p1，p2，…，pn)A*(?p1，?p2，…，?pn)A(?p1，?p2，…，?pn)?A*(p1，p2，…，pn)【例1.28】設(shè)命題公式A(p,q,r)

(p∨q)∧r，試用此公式驗(yàn)證定理的有效性。證明：⑴驗(yàn)證?A(p,q,r)

A*(?p,?q,?r)A(p,q,r)

(p∨q)∧r?A(p,q,r)

?((p∨q)∧r)

(?p∧?q)∨?rA*(p,q,r)

(p∧q)∨rA*(?p,?q,?r)

(?p∧?q)∨?r所以，?A(p,q,r)

A*(?p,?q,?r)⑵驗(yàn)證A(?p,?q,?r)

?A*(p,q,r)A(?p,?q,?r)

(?p∨?q)∧?r

?((p∧q)∨r)

?A*(p,q,r)

定理1.7.2(對偶原理)設(shè)p1，p2，…，pn是出現(xiàn)在公式A和B中的所有原子變元，如果AB，那么A*B*證明：因?yàn)锳B所以A(p1，p2，…，pn)?B(p1，p2，…，pn)是重言式A(?p1，?p2，…，?pn)?B(?p1，?p2，…，?pn)是重言式。所以A(?p1，?p2，…，?pn)B(?p1，?p2，…，?pn)由定理1.7.1?A*(p1，p2，…，pn)?B*(p1，p2，…，pn)即?A*?B*由雙條件否認(rèn)等價(jià)式知A*B*

由對偶定理顯然有：重言式的對偶式是矛盾式，矛盾式的對偶式是重言式。

蘊(yùn)含式 定義1.7.2〔蘊(yùn)含式〕設(shè)A和B是命題公式，假設(shè)A→B是重言式，那么稱A蘊(yùn)含B，記為AB。證明AB的方法：⑴對A指定真值T，假設(shè)由此推出B的真值不為F，而為T，那么A→B是重言式，即AB。⑵對B指定真值F，假設(shè)由此推出A的真值不為T，而為F，那么A→B是重言式，即AB。

【例1.31】推證?p∧(p∨q)q證法1：假定?p∧(p∨q)為T?p為T且p∨q為Tp為F且p∨q為Tq為T。所以?p∧(p∨q)q證法2：假定q為F，那么p可以為T或F。①當(dāng)p為T時(shí)，?p為F，所以?p∧(p∨q)為F。②當(dāng)p為F時(shí)，(p∨q)為F，所以?p∧(p∨q)為F。故?p∧(p∨q)q蘊(yùn)含式是邏輯推理的重要工具。下面是一些重要的蘊(yùn)含式。1.附加律AA∨B，BA∨B2.化簡律A∧BA，A∧BB3.假言推理A∧(A→B)B4.拒取式?B∧(A→B)?A5.析取三段論?A∧(A∨B)B，?B∧(A∨B)A6.假言三段論(A→B)∧(B→C)(A→C)7.等價(jià)三段論(A?B)∧(B?C)(A?C)8.構(gòu)造性二難(A∨C)∧(A→B)∧(C→D)B∨D(A∨?A)∧(A→B)∧(?A→B)B9.破壞性二難(?B∨?D)∧(A→B)∧(C→D)(?A∨?C)4、5的證明做為練習(xí)〔作業(yè)〕等價(jià)式和蘊(yùn)含式有下面的關(guān)系。定理1.7.3設(shè)A，B為任意兩個(gè)命題公式，那么AB的充分必要條件是AB且BA證明：設(shè)AB，下證AB且BA因?yàn)锳B，所以A?BT(A→B)∧(B→A)A?BTA→B與B→A都是重言式，故有AB且BA。設(shè)AB且BA，下證AB。因?yàn)锳B且BA，所以A→B與B→A都是重言式，(A→B)∧(B→A)T(A?B)(A→B)∧(B→A)T即A?B為重言式，故有AB。

定理設(shè)A、B、C為合式公式。⑴AA(即蘊(yùn)含是自反的)⑵假設(shè)AB且A為重言式，那么B必為重言式。⑶假設(shè)AB且BC，那么AC⑷假設(shè)AB且AC，那么AB∧C⑸假設(shè)AB且CB，那么A∨CB⑹假設(shè)AB，C是任意公式，那么A∧CB∧C

本小節(jié)學(xué)習(xí)目標(biāo)：1、理解對偶式和蘊(yùn)含式的概念。2、學(xué)會如何判斷兩個(gè)命題公式之間是否有蘊(yùn)含關(guān)系。1.8命題邏輯的推論理論定義〔前提和有效結(jié)論〕設(shè)A1，A2，…，An和C是n+1個(gè)命題公式，假設(shè)A1∧A2∧…∧AnC，那么稱C為A1，A2，…，An的有效結(jié)論，A1，A2，…，An叫做C的一組前提。要證明C是一組前提A1，A2，…，An的有效結(jié)論，只需證明A1∧A2∧…∧An→C為重言式。找出C為假的行，假設(shè)在每個(gè)這樣的行中，A1，A2，…，An的真值至少有一個(gè)為假，那么A1∧A2∧…∧AnC，即C為一組前提A1，A2，…，An的有效結(jié)論。

【例1.32】分析事實(shí)：“如果我有時(shí)間，那么我就去上街；如果我上街，那么我就去書店買書；但我沒有去書店買書，所以我沒有時(shí)間。〞。試指出這個(gè)推理前提和結(jié)論，并證明結(jié)論是前提的有效結(jié)論。解：令p：我有時(shí)間。q：我去上街。r：我去書店買書。根據(jù)題意，前提為：p→q，q→r，?r結(jié)論為：?p以下證明(p→q)∧(q→r)∧?r?p

表1.23pqrp→qq→r?r?p00011110011101010101101111011000110101010011010101111100命題邏輯的推理是一個(gè)描述推理過程的命題公式序列，其中的每個(gè)命題公式或者是前提，或者是由某些前提應(yīng)用推理規(guī)那么得到的結(jié)論(中間結(jié)論或推理中的結(jié)論)。它有兩種方法：直接推理和間接推理。⑴直接推理直接推理的根本思想是：由一組前提出發(fā)，利用一些公認(rèn)的規(guī)那么，根據(jù)的等價(jià)式或蘊(yùn)含式，推演得到有效結(jié)論。公認(rèn)的推理規(guī)那么有4條：P規(guī)那么：前提在推導(dǎo)過程中的任何時(shí)候都可以引入使用。T規(guī)那么：推理中，如果一個(gè)或多個(gè)公式，蘊(yùn)含了公式S，那么公式S可以引入到以后的推理之中。置換規(guī)那么：在推導(dǎo)過程的任何步驟上，命題公式中的子公式都可以用與之等價(jià)的公式置換。合取引入規(guī)那么：任意兩個(gè)命題公式A，B可以推出A∧B。例1.34用直接推理法證(p→q)∧(q→r)∧p

r

證明：

⑴p→q P⑵p P