第一章命題邏輯2公式及分類

命題公式(合式公式)(wff,wellformedformula)

：(1)單個命題變元本身是一個命題公式.(2)如果A和B是命題公式，那么

A,(A

B),(A

B),(A

B),(A

B)都是命題公式.(3)當(dāng)且僅當(dāng)能夠有限次地應(yīng)用(1),(2)生成的公式是命題公式.二、命題公式及分類(一)命題公式的概念例1.2.1

用定義說明下列字符串是否為合式公式解題思想：嚴(yán)格按定義判斷，但習(xí)慣上可以省去外層括號。(1)

(P

Q)(2)P

(P

Q)(3)(

P

Q)∧(PR)(5)PQR二、命題公式及分類(4)(P

Q)

(

Q)(6)(P

Q,(P

Q)

Q)

×××聯(lián)結(jié)詞運(yùn)算的次序沒有括號時按強(qiáng)弱先后順序執(zhí)行.運(yùn)算符結(jié)合力的強(qiáng)弱順序約定為：

,,

,,

.要養(yǎng)成“先后”的習(xí)慣.相同運(yùn)算符按從左至右順序執(zhí)行，括號可省去.例如，(A

B)C與A

BC運(yùn)算順序一樣.最外層的括號總可以省去.例如，(A

B)

常寫為A

B.例1.2.2下式的運(yùn)算順序是怎樣的？P

S

QR

RP

Q與((P

S)

(QR))

((RP)

Q)運(yùn)算順序相同.答：二、命題公式及分類(二)命題公式的指派P1,P2,…,Pn為出現(xiàn)在A中的所有的命題變項,由A的真值將每次賦值分為成真指派和成假指派.

設(shè)A為一命題公式，

一個含有命題變元的命題公式的真值是不確定的，因此有必要對它的真值進(jìn)行具體的分析.二、命題公式及分類P1,P2,…,Pn指定一組真值，就是對A的一個指派.真值表：將含有n個命題變元的命題公式按字典順序進(jìn)行2n組賦值后所得真值表,稱為該命題公式的真值表.(三)真值表二、命題公式及分類構(gòu)造真值表的步驟(1)將變元按一定順序排出，再按從內(nèi)到外的順序列出公式的各個運(yùn)算層次，將它們排在表頭上；(2)如有n個變元，則所有可能的賦值有2n組，每組可用n位的二進(jìn)制數(shù)表示，按字典順序每行排一組;(3)在表上由左到右填寫相應(yīng)的真值.二、命題公式及分類真值表的構(gòu)造例1.2.3構(gòu)造

PQ

的真值表.解：PQP

PQTTTFFTFFF

F

TTTF

TT二、命題公式及分類真值表的構(gòu)造例1.2.4構(gòu)造

(PQ)

(P

Q)的真值表.解：PQPQ

P

TTTFFTFFTF

FFF

F

TT(PQ)F

TTT

Q

F

TFTP

QF

TTT二、命題公式及分類PQTTTFFTFF(PQ)F

TTTP

QF

TTT(PQ)

(P

Q)TTTT(PQ)

(P

Q)的真值全為真，這類公式稱為永真公式，記為T.(另有永假公式，記為F.)(PQ)

與

(P

Q)的所有真值相同，稱二者是等價的.真值表的構(gòu)造例1.2.4構(gòu)造

(PQ)

(P

Q)的真值表.解：二、命題公式及分類(四)命題公式的類型重言式(tautology)(永真公式)：無論對分量作怎樣的指派，其對應(yīng)的真值永為T，記為T.例如，

(PQ)

(P

Q)是重言式.任何兩個重言式的合取或析取，仍然是一個重言式.(A為T，B為T，A與B合取(或析取)仍為T.)一個重言式，對同一分量都用任何Wff置換，其結(jié)果仍為一重言式.(因為重言式的真值與分量的指派無關(guān).)二、命題公式及分類矛盾式(contradictionorabsurdity)(永假公式)：無論對分量作怎樣的指派，其對應(yīng)的真值永為F

，記為F.任何兩個矛盾式的合取