左孝凌離散數(shù)學(xué)13命題公式與翻譯-14真值表與等價(jià)課件

1(DiscreteMathematics)1.3.1命題公式1.3.2復(fù)合命題的符號(hào)化(翻譯)2第一章命題邏輯（PropositionalLogic）1.3命題公式與翻譯1.3.1合式公式(Well-formedformula)(wff)定義1.3.1:原子公式

單個(gè)命題變?cè)兔}常量稱為原子公式。3第一章命題邏輯（PropositionalLogic）1.3命題公式與翻譯定義1.3.2：合式公式

(1)原子公式是合式公式(wff)。（2）若A，B是合式公式，則（A），(A∧B)，(A∨B)，(AB)，(AB)也是合式公式。（3）當(dāng)且僅當(dāng)有限次地應(yīng)用(1)(2)所得到的包含原子公式、聯(lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式。聯(lián)結(jié)詞的優(yōu)先級(jí)：┐、∧、∨、→、。

則：P∧Q→R是合式公式等價(jià)于Wff

：（（P∧Q）→R）命題公式外層的括號(hào)可以省略等價(jià)于Wff

：（P∧Q）→R不等價(jià)于Wff

：P∧（Q→R）第一章命題邏輯（PropositionalLogic）1.3命題公式與翻譯6第一章命題邏輯（PropositionalLogic）1.3命題公式與翻譯1.3.2復(fù)合命題的符號(hào)化(翻譯)自然語(yǔ)言的語(yǔ)句用Wff

形式化：

①

要準(zhǔn)確確定原子命題，并將其形式化。

②

要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于識(shí)別自然語(yǔ)言中的聯(lián)結(jié)詞（有時(shí)它們被省略），否定詞的位置要放準(zhǔn)確。

③

必要時(shí)可以進(jìn)行改述，即改變?cè)瓉淼臄⑹龇绞剑ＷC表達(dá)意思一致。④

需要的括號(hào)不能省略，而可以省略的括號(hào)，在需要提高公式可讀性時(shí)亦可不省略。

⑤要注意語(yǔ)句的形式化未必是唯一的?？梢园驯久}表達(dá)為：┐(P?Q）。

解P：上海到北京的14次列車是下午五點(diǎn)半開。

Q：上海到北京的14次列車是下午六點(diǎn)開。在本例中，漢語(yǔ)的“或”是不可兼或，而邏輯聯(lián)結(jié)詞∨是“可兼或”，因此不能直接對(duì)兩命題析取。構(gòu)造如表1-3.1所示。PQ原命題P?Q┐(P?Q)TTFTFTFTFTFTTFTFFFTF表1-3.1例題2上海到北京的14次列車是下午五點(diǎn)半或六點(diǎn)開。

解這個(gè)命題的意義是：

可兼或若設(shè)

P：張三可以做這事。Q：李四可以做這事。本例可表示為：

P∨Q例題6張三或李四都可以做這件事。10第一章命題邏輯（PropositionalLogic）1.3命題公式與翻譯1)我今天進(jìn)城，除非下雨。[1-3.(7)]2)僅當(dāng)你走我將留下。[1-3.(7)]3)假如上午不下雨，我去看電影，否則就在家里讀書或看報(bào)。[1-3.(7)]4)一個(gè)人起初說：“占據(jù)空間的、有質(zhì)量的而且不斷變化的叫做物質(zhì)”；后來他改說，“占據(jù)空間的有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的。”問他前后主張的差異在什么地方，試以命題形式進(jìn)行分析。[1-3.(6)]練習(xí)111第一章命題邏輯（PropositionalLogic）1.3命題公式與翻譯我今天進(jìn)城，除非下雨。[1-3.(7)]P：我今天進(jìn)城。Q:天下雨。┓Q→P2)僅當(dāng)你走我將留下。[1-3.(7)]P:你走。Q:我留下。Q→P3)假如上午不下雨，我去看電影，否則就在家里讀書或看報(bào)。[1-3.(7)]P:上午下雨。Q:我去看電影。R:我在家里讀或看報(bào)。┓(┓P→Q)?(P→R)）（要么看電影要么留在家里，排斥或）解答練習(xí)2

（小李不在圖書館），（他要么找老師去了），（要么就是因?yàn)樯眢w不適，回宿舍去了）。命題符號(hào)化是很重要的，一定要掌握好，在命題推理中常常最先遇到的就是符號(hào)化一個(gè)問題，解決不好，等于說推理的首要前提沒有了。解設(shè)P：小李在圖書館。Q：小李找老師。

R：小李身體不適。S：小李回宿舍。則命題符號(hào)化為：（┐P）∧（┐(Q(R→S)）（小李不是……而是……∧）（要么……要么……排斥或）14第一章命題邏輯（PropositionalLogic）1.3命題公式與翻譯小結(jié)：本節(jié)介紹了命題公式的概念及復(fù)合命題的符號(hào)化.重點(diǎn)是理解命題公式的遞歸定義,掌握復(fù)合命題的符號(hào)化方法.作業(yè)：p12(5)15離散數(shù)學(xué)(DiscreteMathematics)1.4.1真值表(TruthTable)1.4.2等價(jià)公式(PropositionalEquivalences)17第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式對(duì)公式A構(gòu)造真值表的具體步驟為：（1）找出公式中所有命題變?cè)狿1,P2,…,Pn（2）按從小到大的順序列出對(duì)命題變?cè)狿1,P2,…,Pn,的全部2n組賦值。（3）對(duì)應(yīng)各組賦值計(jì)算出公式A的真值，并將其列在對(duì)應(yīng)賦值的后面。18第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例1.給出┐(PQ)(┐P┐Q)的真值表：PQPQ ┐(PQ)┐P┐Q┐(PQ)(┐P┐Q)0001101119第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例1.給出┐(PQ)(┐P┐Q)的真值表：PQPQ ┐(PQ)┐P┐Q┐(PQ)(┐P┐Q)00011011000111101110111121第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例2：構(gòu)造公式(PQ)∧R的真值表。PQRPQ(PQ)∧R000100011101010011111000010100110101111122第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式練習(xí)1：構(gòu)造公式(PQ)(QP）真值表。PQ

P

QP

Q

QP(P

Q)(

Q

P)0001101123第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式練習(xí)1：構(gòu)造公式(PQ)(QP）真值表。PQ

P

QP

Q

QP(P

Q)(

Q

P)001111101101111001001110011125第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式PQ(P

Q)(P

Q)(P

Q)∧Q00100011001001011100練習(xí)2：構(gòu)造公式

(PQ）∧Q真值表。永真公式永假公式：無(wú)論對(duì)其分量作怎樣的真值指派，其真值永為T，稱為永真公式，記為T。如例1無(wú)論對(duì)其分量作怎樣的真值指派，其真值永為F，稱為永假公式，記為F。如例2

第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式29第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式定義1.4.3:給定兩個(gè)命題公式A和B,設(shè)P1,P2,…,Pn為出現(xiàn)于A和B中的所有原子變?cè)?若給P1,P2,…,Pn任一組真值指派,A和B的真值都相同,則稱A和B是等價(jià).

記作AB。1.4.2等價(jià)公式30第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式1.真值表法2.等值演算法1.真值表法

例1.┐(PQ)(┐P┐Q)見真值表例題1.例2.證明:PQ(P→Q)(Q→P)PQPQQ→PP→Q(P→Q)(Q→P)00011011證明公式等價(jià)的方法：31第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式1.真值表法2.等值演算法1.真值表法

例1.┐(PQ)(┐P┐Q)見真值表例題1.例2.證明:PQ(P→Q)(Q→P)PQPQQ→PP→Q(P→Q)(Q→P)001111010010100100111111所以：PQ(P→Q)(Q→P)(P∧Q)∨(┐P∧┐Q)試用等值演算方法證明另外，PQ(┐P∨Q)∧(┐Q∨P)32第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式2.等值演算法(EquivalentCaculation)（利用P15表1-4.8)重要的等價(jià)式(補(bǔ)充):11.蘊(yùn)涵等值式:PQ┐PQQ┐P┐Q┐P（假言易位）12.等價(jià)等值式:PQ(P→Q)(Q→P)

(┐P∨Q)∧(┐Q∨P)(P∧Q)∨(┐P∧┐Q)

13.假言易位:PQ┐Q┐P

14.等價(jià)否定等值式:PQ┐P┐Q

15.歸謬論:(PQ)(

P┐Q)┐P對(duì)合律┐┐PP1冪等律P∨PP，P∧PP2結(jié)合律(P∨Q）∨RP∨（Q∨R）(P∧Q）∧RP∧（Q∧R）3交換律P∨QQ∨PP∧QQ∧P4分配律P∨（Q∧R）（P∨Q）∧（P∨R）P∧（Q∨R）（P∧Q）∨（P∧R）5吸收律P∨（P∧Q）

PP∧（P∨Q）

P6德摩根律┐(P∨Q)┐P∧┐Q┐(P∧Q)┐P∨┐Q7同一律P∨F

P，P∧T

P8零律P∨TT，P∧FF9否定律P∨┐P

T，P∧┐P

F10表1-4.8命題定律任何數(shù)與0相或還是任何數(shù)任何數(shù)與1相與為1任何數(shù)與1相與還是任何數(shù)與0相與為0例題6驗(yàn)證吸收律P∨（P∧Q）

PP∧（P∨Q）

P證明列出真值表表1-4.9PQP∧QP∨（P∧Q）P∨QP∧（P∨Q）TTTTTTTFFTTTFTFFTFFFFFFF由表1-4.9可知吸收律成立。練習(xí)18頁(yè)（4）35第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式等值演算中使用的一條重要規(guī)則：置換規(guī)則。定義1.4.4子公式：如果X是wffA的一部分,且X本身也是wff，則稱X是A的子公式。

例如,P(PQ)為Q(P(PQ))的子公式。定理1.4.1

置換定理：設(shè)X是wffA的子公式，若XY，則若將A中的X用Y來置換，所得公式B與A等價(jià)，即AB。定義1.4.5

等值演算：根據(jù)已知的等價(jià)公式,推演出另外一些等價(jià)公式的過程稱為等值演算.36第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例1：證明Q→（P（PQ））Q→P

證:Q→（P（PQ））Q→P

P(吸收律)例2：證明（P┐Q）Q

PQ

證：(P┐Q)Q(PQ)(┐QQ)(PQ)TPQ例3：證明（P→Q）→（QR）

PQR證：（P→Q）→（QR）（┐PQ）→（QR）┐(┐PQ)（QR）（P┐Q）（QR）

（PQR）（┐QQR）

(PQR)

((┐QQ)R)

(PQR)

(TR)

(PQR)

T

(PQR)

37第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例4：驗(yàn)證P(QR)(P

∧

Q)R證:右

(P

∧

Q)∨R（蘊(yùn)含等值）