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

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

單個命題變元和命題常量稱為原子公式。3第一章命題邏輯（PropositionalLogic）1.3命題公式與翻譯定義1.3.2：合式公式

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

則：P∧Q→R是合式公式等價于Wff

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

：（P∧Q）→R不等價于Wff

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

形式化：

①

要準確確定原子命題，并將其形式化。

②

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

③

必要時可以進行改述，即改變原來的敘述方式，但要保證表達意思一致。④

需要的括號不能省略，而可以省略的括號，在需要提高公式可讀性時亦可不省略。

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

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

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

解這個命題的意義是：

可兼或若設

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

P∨Q例題6張三或李四都可以做這件事。10第一章命題邏輯（PropositionalLogic）1.3命題公式與翻譯1)我今天進城，除非下雨。[1-3.(7)]2)僅當你走我將留下。[1-3.(7)]3)假如上午不下雨，我去看電影，否則就在家里讀書或看報。[1-3.(7)]4)一個人起初說：“占據(jù)空間的、有質(zhì)量的而且不斷變化的叫做物質(zhì)”；后來他改說，“占據(jù)空間的有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的?！眴査昂笾鲝埖牟町愒谑裁吹胤剑囈悦}形式進行分析。[1-3.(6)]練習111第一章命題邏輯（PropositionalLogic）1.3命題公式與翻譯我今天進城，除非下雨。[1-3.(7)]P：我今天進城。Q:天下雨。┓Q→P2)僅當你走我將留下。[1-3.(7)]P:你走。Q:我留下。Q→P3)假如上午不下雨，我去看電影，否則就在家里讀書或看報。[1-3.(7)]P:上午下雨。Q:我去看電影。R:我在家里讀或看報。┓(┓P→Q)?(P→R)）（要么看電影要么留在家里，排斥或）解答練習2

（小李不在圖書館），（他要么找老師去了），（要么就是因為身體不適，回宿舍去了）。命題符號化是很重要的，一定要掌握好，在命題推理中常常最先遇到的就是符號化一個問題，解決不好，等于說推理的首要前提沒有了。解設P：小李在圖書館。Q：小李找老師。

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

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

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

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

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

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

P

QP

Q

QP(P

Q)(

Q

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

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

P

QP

Q

QP(P

Q)(

Q

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

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

Q)(P

Q)(P

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

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

第一章命題邏輯（PropositionalLogic）

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

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

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

1.4真值表與等價公式1.真值表法2.等值演算法1.真值表法

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

1.4真值表與等價公式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真值表與等價公式2.等值演算法(EquivalentCaculation)（利用P15表1-4.8)重要的等價式(補充):11.蘊涵等值式:PQ┐PQQ┐P┐Q┐P（假言易位）12.等價等值式:PQ(P→Q)(Q→P)

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

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

14.等價否定等值式:PQ┐P┐Q

15.歸謬論:(PQ)(

P┐Q)┐P對合律┐┐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驗證吸收律P∨（P∧Q）

PP∧（P∨Q）

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

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

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

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

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

1.4真值表與等價公式例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真值表與等價公式例4：驗證P(QR)(P

∧

Q)R證:右

(P

∧

Q)∨R（蘊含等值）