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

(簡稱公式)：

(1)命題變元和命題常元是命題公式。

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

B)是合式公式。

(3)只有有限次地使用(1)和(2)所得到的符號串才是命題公式。3例如：以下字符串就不是命題公式,因為它們不符合形成規(guī)則：

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

為了減少圓括號的使用,以后書寫命題公式時，可按約定省略公式中的部分圓括號。4例用定義說明(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.公式的賦值或解釋（指派）如果一個命題公式含有命題變元，則它的真值是不確定的。只有對它的每個命題變元用指定的真值后，命題公式才變成命題，其真值才能唯一確定。定義設A為一個命題公式，P1,P2,…,Pn

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

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

設命題公式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個命題變元的命題公式，共有2n組賦值。將命題公式在所有賦值下取值的情況列成表，稱為命題公式的真值表。構造真值表的具體步驟如下：

(1)找出命題公式中所含的所有命題變元p1,p2,…,pn(若無下角標就按字典順序給出)，列出所有可能的賦值(2n個)；—按二進制加法進行。

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

(3)對應每個賦值，計算各列的值，直到最后計算出命題公式的值。8例(a)構造命題公式((P∨Q)∧P)和┒((P∨Q)∧P)

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

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

的真值表。

兩個命題公式，

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

所以它們是邏輯等價命題。解：

P?Q的真值表如下：10課堂練習構造下列命題公式的真值表。

(1)

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

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

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

(3)若A至少存在一組賦值是使A為真，則A是可滿足式。由定義可知，重言式一定是可滿足式，但反之不成立。12命題邏輯的重點是對重言式的研究，它在數(shù)理邏輯中起著重要作用。因為它有以下特點：

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

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

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

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

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

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

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

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

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

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

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

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

與┒(p∨q)

0101001011101001101110110100qp18課堂練習判斷下列命題公式是否邏輯等價。

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

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

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

將邏輯恒等式的某個命題變元的所有出現(xiàn)可用一命題公式代入，其等式不變。就如同在代數(shù)式中，

若x

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

對交換律：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)

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

例如：對公式：

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

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

判別下列公式的類型

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

分配律矛盾律德.摩根律結合律排中律零律26應用2

證明公式恒等和對復合語句化簡證明P∧┒Q∨Q?

P∨Q

證：P∧┒Q∨Q?

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

Q∨P?

P∨Q 27

(b)試將語句“情況并非如此:如果他不來,那么我也不去?！被啞?/p>

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

Q∧┒P 化簡后的語句含義是：“我去了，而他不來”。

解設P：他要來，

Q：我要去。

則該復合語句可符號化為：┒(┒P→┒Q)。

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

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應用3

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

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

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

(P∧S)∧(Q∨R)所以其開關設計圖可簡化為：33(2)

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

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

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

乙的判斷為A2=P∧┐Q

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

37甲的判斷全對

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

B3=P∧┐Q乙的判斷全對

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

C3=┐P∧Q丙的判斷全對

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

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

Ｂ∧(Ａ∨┐Ａ)Ｂ

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

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

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

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

方法2:

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

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

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

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

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

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

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

即：邏輯恒等和重言蘊含都是傳遞的。

(2).若A?B，A?C，則A?B∧C。證(2)：因為A是真時，B和C都真。