數(shù)理邏輯-命題邏輯

第一章命題邏輯1.2命題公式與分類11.命題常元與命題變?cè)}常元：表示一個(gè)具體的簡(jiǎn)單命題的符號(hào)。命題常元的真值是確定不變的，不是為1，就是為0。命題變?cè)簺](méi)有賦予具體內(nèi)容的原子命題。該命題變量無(wú)具體的真值，它的只域是集合{T，F(xiàn)}(或{0，1})。命題公式是由命題常元、命題變?cè)?、?lián)結(jié)詞、括號(hào)等組成的符號(hào)串，但并不是由這些符號(hào)任意組成的符號(hào)串都是命題公式。22.命題公式的定義由以下形成規(guī)則生成的公式叫命題公式

(簡(jiǎn)稱公式)：

(1)命題變?cè)兔}常元是命題公式。

(2)如果A、B是命題公式,則(┒A),(A∧B),(A∨B),(A→B),(A?

B)是合式公式。

(3)只有有限次地使用(1)和(2)所得到的符號(hào)串才是命題公式。3例如：以下字符串就不是命題公式,因?yàn)樗鼈儾环闲纬梢?guī)則：

∧Q，(P→Q，P→∧Q，((PQ)∧R)

為了減少圓括號(hào)的使用,以后書(shū)寫(xiě)命題公式時(shí)，可按約定省略公式中的部分圓括號(hào)。4例用定義說(shuō)明(P→(P∨Q))是命題公式。解：(i)P是命題公式 根據(jù)(1)(ii)Q是命題公式 根據(jù)(1)(iii)(P∨Q)是命題公式 根據(jù)(i)(ii)和(2)

(iv)(P→(P∨Q))是命題公式根據(jù)(i)(iii)和(2)

53.公式的賦值或解釋（指派）如果一個(gè)命題公式含有命題變?cè)?，則它的真值是不確定的。只有對(duì)它的每個(gè)命題變?cè)弥付ǖ恼嬷岛?，命題公式才變成命題，其真值才能唯一確定。定義設(shè)A為一個(gè)命題公式，P1,P2,…,Pn

為出現(xiàn)該公式中的所有的命題變?cè)?。分別給P1,P2,…,Pn

指定一個(gè)真值，則稱為對(duì)A的一個(gè)賦值或解釋。若指定的一組值使A的值為真，則稱這組值為A的成真賦值，若使A的值為假，則稱這組值為A的成假賦值。6例

設(shè)命題公式A=p∧q→r則

110（p=1,q=1,r=0）為A的成假賦值。

111(p=1,q=1,r=1)是A的成真賦值。

011是A的成真賦值010是A的成真賦值。74.公式的真值表含n個(gè)命題變?cè)拿}公式，共有2n組賦值。將命題公式在所有賦值下取值的情況列成表，稱為命題公式的真值表。構(gòu)造真值表的具體步驟如下：

(1)找出命題公式中所含的所有命題變?cè)猵1,p2,…,pn(若無(wú)下角標(biāo)就按字典順序給出)，列出所有可能的賦值(2n個(gè))；—按二進(jìn)制加法進(jìn)行。

(2)按從低到高的順序?qū)γ}公式進(jìn)行分解；

(3)對(duì)應(yīng)每個(gè)賦值，計(jì)算各列的值，直到最后計(jì)算出命題公式的值。8例(a)構(gòu)造命題公式((P∨Q)∧P)和┒((P∨Q)∧P)

的真值表。解：該公式的真值表如下：9

(b)構(gòu)造公式P?Q與P∧Q∨┒P∧┒Q

的真值表。

兩個(gè)命題公式，

如果有相同的真值，則稱它們是邏輯等價(jià)命題。以上兩個(gè)命題因后兩列的真假值完全一致，

所以它們是邏輯等價(jià)命題。解：

P?Q的真值表如下：10課堂練習(xí)構(gòu)造下列命題公式的真值表。

(1)

┐q∨r(2)(q→r)∧(p→p)115.命題公式的分類根據(jù)在各種賦值下的取值情況，可將命題公式分為3類：定義設(shè)A為一個(gè)命題公式。

(1)若A在它的各種賦值下取值均為真，則稱A為重言式或永真式。

(2)若A在它的各種賦值下取值均為假，則稱A為矛盾式或永假式。

(3)若A至少存在一組賦值是使A為真，則A是可滿足式。由定義可知，重言式一定是可滿足式，但反之不成立。12命題邏輯的重點(diǎn)是對(duì)重言式的研究，它在數(shù)理邏輯中起著重要作用。因?yàn)樗幸韵绿攸c(diǎn)：

(1)重言式的否定是矛盾式，反之，矛盾式的否定是重言式。所以研究其一就可以了。

(2)兩個(gè)重言式的合取、析取、蘊(yùn)含、等值式都是重言式。(3)在重言式中有許多重要的邏輯恒等式和永真蘊(yùn)含式，它們是邏輯推理的基礎(chǔ)。

136.命題公式類型的判斷方法

方法之一就是利用命題公式的真值表：若真值表最后一列全為1，則對(duì)應(yīng)的命題公式為重言式；若最后一列全為0，則對(duì)應(yīng)的命題公式為矛盾式；若最后一列既有0又有1，則對(duì)應(yīng)的命題公式為非重言式的可滿足式。

14第一章命題邏輯1.3命題公式的重言式15一.邏輯恒等式

設(shè)A(P1,P2,…,Pn)，B(P1,P2,…,Pn)是兩個(gè)命題公式，這里Pi(i=1,2,…,n)不一定在兩公式中同時(shí)出現(xiàn)。

如果A?B是重言式，則A與B對(duì)任何解釋都有相同的真值。記為A?B，叫做邏輯恒等式，讀做“A恒等于B”。請(qǐng)注意符號(hào)?與符號(hào)意義不同：

?是邏輯聯(lián)結(jié)詞,而?是表示命題A和B有邏輯等價(jià)關(guān)系的符號(hào),它的作用相當(dāng)于代數(shù)中的“=”。161.判斷兩命題公式邏輯等價(jià)的方法—真值表法

設(shè)A，B為兩命題公式，由定義判斷A與B是否邏輯等價(jià)應(yīng)判斷A?B是否為重言式，若A?B的真值表最后一列全為1，則A?B重言式，因而A?B。

而最后一列全為1當(dāng)且僅當(dāng)在各賦值之下，A與B的真值相同，因而判斷A與B是否邏輯等價(jià)可簡(jiǎn)化為判斷公式A，B的真值表是否相同。

17例判斷下列命題公式是否邏輯等價(jià)？

(1)p∨q與┒p∨┒q(2)┒p∨┒q

與┒(p∨q)

0101001011101001101110110100qp18課堂練習(xí)判斷下列命題公式是否邏輯等價(jià)。

(1)p→(q→r)與(p∧q)→r(2)(p→q)→r與(p∧q)→r192.基本邏輯恒等式1.雙重否定律

2.等冪律3.交換律4.結(jié)合律5.分配律20基本邏輯恒等式6.德.摩根律7.吸收律8.零律9.同一律10.排中律11.矛盾律21基本邏輯恒等式12.蘊(yùn)涵等值式13.等價(jià)等值式14.假言易位15.等價(jià)否定等值式16.歸繆論223.代入規(guī)則和替換規(guī)則

(1).代入規(guī)則(RuleofSubstitution)

將邏輯恒等式的某個(gè)命題變?cè)乃谐霈F(xiàn)可用一命題公式代入，其等式不變。就如同在代數(shù)式中，

若x

2-y2=(x+y)(x-y)則(a+b)2-(mn)2=(a+b+mn)(a+b-mn)一樣。23例如：

對(duì)交換律：A∨B?B∨A若用p∧q代A，┒p∧r代B，就可得出邏輯恒等公式：(p∧q)∨(┒p∧r)

?(┒p∧r)∨(p∧q)若用┒p代A，┒p∧q∨r代B，可得就出邏輯恒等公式：┒p∨(┒p∧q∨r)?(┒p∧q∨r)∨┒p……24

(2).替換規(guī)則(RuleofReplacement)

設(shè)有恒等式A?B，若在公式C中出現(xiàn)A的地方,替換以B(不必每一處)而得到公式D，則C?D。

例如：對(duì)公式：

(P→Q)→R可利用公式P→Q?┒P∨Q，對(duì)其中的P→Q作替換。得公式

(P→Q)→R?(┒P∨Q)→R25應(yīng)用1

判別下列公式的類型

解：由此可知，該式為重言式。

分配律矛盾律德.摩根律結(jié)合律排中律零律26應(yīng)用2

證明公式恒等和對(duì)復(fù)合語(yǔ)句化簡(jiǎn)證明P∧┒Q∨Q?

P∨Q

證：P∧┒Q∨Q?

Q∨P∧┒Q?(Q∨P)∧(Q∨┒Q)?(Q∨P)∧1?

Q∨P?

P∨Q 27

(b)試將語(yǔ)句“情況并非如此:如果他不來(lái),那么我也不去?！被?jiǎn)。

28┒(┒P→┒Q)?┒(┒┒P∨┒Q) ?┒┒┒P∧┒┒Q ?┒P∧Q ?

Q∧┒P 化簡(jiǎn)后的語(yǔ)句含義是：“我去了，而他不來(lái)”。

解設(shè)P：他要來(lái)，

Q：我要去。

則該復(fù)合語(yǔ)句可符號(hào)化為：┒(┒P→┒Q)。

再簡(jiǎn)化此公式：29(c)求P→(P?Q)∨R的僅含∧和┒兩種聯(lián)結(jié)詞的等價(jià)表達(dá)式。

30解：

P→(P?Q)∨R?

P→(P→Q)∧(Q→P)∨R?┒P∨(┒P∨Q)∧(┒Q∨P)∨R?(┒P∨┒P∨Q)∧(┒P∨┒Q∨P)∨R?(┒P∨Q)∧(T∨┒Q)∨R?(┒P∨Q)∧T∨R

?┒P∨Q∨R

?┒(P∧┒Q∧┒R) 31應(yīng)用3

在實(shí)際中的應(yīng)用(1).試用較少的開(kāi)關(guān)設(shè)計(jì)一個(gè)與下圖有相同功能的電路。32解：可將上圖所示之開(kāi)關(guān)電路用下述命題公式表示：(P∧Q∧S)∨(P∧R∧S)利用基本等價(jià)公式，將上述公式轉(zhuǎn)化為：

(P∧Q∧S)∨(P∧R∧S)

((P∧S)∧Q)∨((P∧S)∧R)

(P∧S)∧(Q∨R)所以其開(kāi)關(guān)設(shè)計(jì)圖可簡(jiǎn)化為：33(2)

設(shè)計(jì)一種簡(jiǎn)單的表決器，表決者每人身旁有一個(gè)按鈕，當(dāng)表決者同意時(shí)則按下按鈕；否者不按按鈕。當(dāng)表決結(jié)果超過(guò)半數(shù)時(shí)主席臺(tái)上的綠燈亮，否者紅燈亮。為簡(jiǎn)單起見(jiàn)，設(shè)表決者僅有三人，試設(shè)計(jì)一個(gè)滿足上述條件的表決器。34解：設(shè)三個(gè)表決者的按鈕分別為P、Q、R。根據(jù)題意可知，主席臺(tái)上綠燈亮的條件可表示成命題公式：(┒P∧Q∧R)∨(P∧┒Q∧R)∨(P∧Q∧┒R)∨(P∧Q∧R)對(duì)上述命題公式化簡(jiǎn)，得：?(P∧(Q∨R))∨(Q∧R)于是可用開(kāi)關(guān)電路來(lái)設(shè)計(jì)該表決器。35(3)

在某次研討會(huì)的中間休息時(shí)間，3名與會(huì)者根據(jù)王教授的口音對(duì)他是哪個(gè)省市的人進(jìn)行了判斷： 甲說(shuō)王教授不是蘇州人，是上海人。 乙說(shuō)王教授不是上海人，是蘇州人。 丙說(shuō)王教授既不是上海人，也不是杭州人。聽(tīng)完以上3人的判斷后，王教授笑著說(shuō)，你們3人中有一人說(shuō)的全對(duì)，有一人說(shuō)對(duì)了一半，另一人說(shuō)的全不對(duì)。試用邏輯演算法分析王教授到底是哪里人？36解：分別設(shè)命題，P：王教授是蘇州人。Q：王教授是上海人。R：王教授是杭州人。

則P、Q、R中必有一個(gè)真命題，兩個(gè)假命題。要通過(guò)邏輯演算將真命題找出來(lái)，已知前提有：甲的判斷為A1=┐P∧Q

乙的判斷為A2=P∧┐Q

丙的判斷為A3=┐Q∧┐R

37甲的判斷全對(duì)

B1=A1=┐P∧Q甲的判斷對(duì)一半 B2=(┐P∧┐Q)∨(P∧Q)甲的判斷全錯(cuò)

B3=P∧┐Q乙的判斷全對(duì)

C1=A2=P∧┐Q乙的判斷對(duì)一半 C2=(P∧Q)∨(┐P∧┐Q)乙的判斷全錯(cuò)

C3=┐P∧Q丙的判斷全對(duì)

D1=A3=┐Q∧┐R丙的判斷對(duì)一半 D2=(Q∧┐R)∨(┐Q∧R)丙的判斷全錯(cuò)D3=Q∧R38根據(jù)王教授所說(shuō)，則有 E=(B1∧C2∧D3)∨(B1∧C3∧D2)∨(B2∧C1∧D3) ∨(B2∧C3∧D1)∨(B2∨C1∧D2)∨(B3∧C2∧D1)為真命題。上述命題公式經(jīng)過(guò)等價(jià)演算后,可得 E(┐P∧Q∧┐R)∨(P∧┐Q∧R)由題設(shè)，王教授不能既是上海人，又是杭州人，因而P、R中必有一個(gè)假命題，即P∧┐Q∧R0，于是 E┐P∧Q∧┐R為真命題，因而必有P、R為假命題，Q為真命題，即王教授是上海人。甲說(shuō)的全對(duì)，丙說(shuō)對(duì)了一半，而乙全說(shuō)錯(cuò)了。39(4)

在程序設(shè)計(jì)語(yǔ)言中，將程序簡(jiǎn)化：FFFTTTABBXYIFATHENIFBTHENXELSEYELSEIFBTHENXELSEY則在此程序中，執(zhí)行X的條件是：(A∧B)∨(┒A∧B)執(zhí)行Y的條件是：(A∧┒B)∨(┒A∧┒B)40可分別將兩個(gè)命題公式化簡(jiǎn)：執(zhí)行X的條件為：(Ａ∧Ｂ)∨(┐Ａ∧Ｂ)

Ｂ∧(Ａ∨┐Ａ)Ｂ

執(zhí)行Y的條件為：(Ａ∧┐Ｂ)∨(┐Ａ∧┐Ｂ)

┐Ｂ∧(Ａ∨┐Ａ)┐Ｂ經(jīng)轉(zhuǎn)換后，這段程序可簡(jiǎn)化：IfBthenXelseY，其流程圖如下圖。STARTENDBXY41二.永真（重言）蘊(yùn)含式

如果A→B是一永真式,那么稱為永真（重言）蘊(yùn)含式，記為A?B，讀做“A永真蘊(yùn)含B”。重言蘊(yùn)含式可用真值表判定，也可用以下辦法證明：(1)假定前件是真，若能推出后件是真，則此蘊(yùn)含式是真。(2)假定后件是假，若能推出前件是假，則此蘊(yùn)含式是真。42例1

證明：┒Q∧(P→Q)?┒P

方法2:

設(shè)┒P是假,則P是真。以下分情況討論：

(i)若Q為真,則┒Q是假,所以┒Q∧(P→Q)是假。

(ii)若Q是假,則P→Q是假,所以┒Q∧(P→Q)是假。故┒Q∧(P→Q)?┒P。方法1:

設(shè)┒Q∧(P→Q)是真,則┒Q,P→Q是真。所以,Q是假,P是假。因而┒P是真。故┒Q∧(P→Q)?┒P

43常用的基本重言蘊(yùn)含式44三.恒等式和重言蘊(yùn)含式的兩個(gè)性質(zhì)

(1).若A?B,B?C

則A?C；若A?B,B?C則A?C。

即：邏輯恒等和重言蘊(yùn)含都是傳遞的。

(2).若A?B，A?C，則A?B∧C。證(2)：因?yàn)锳是真時(shí)，B和C都真。