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

1、左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式11.3.1 命題公式命題公式1.3.2 復(fù)合命題的符號(hào)化復(fù)合命題的符號(hào)化(翻譯翻譯)左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式21.3命命題公式與翻譯題公式與翻譯1.3.1 合式公式合式公式(Well-formed formula)(wff)定義定義1.3.1: :原子公式原子公式 單個(gè)單個(gè)命題變?cè)}變?cè)秃兔}常量命題常量稱為稱為原子公式原子公式。左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式31.3命命題公式與翻譯題公式與翻譯定義定義1.3.2：合式公式：合式公式 (1)原子公式原子公式是是合式公式合式公式(wff)。 （2）若）若A，B是合

2、式公式，則（是合式公式，則（ A），）， (AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。 （3）當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)有限次地應(yīng)用有限次地應(yīng)用(1)(2)所得到的包含所得到的包含原原子公式、子公式、聯(lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式。聯(lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式。左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式41.3命命題公式與翻譯題公式與翻譯例例1 1：指出(P(PQ)是否是命題公式(wff)，如果是，則具體說(shuō)明。解： P是wff 由(1) Q是wff 由(1) PQ是wff 由(2) (P(PQ) 由(2) (PQ）(Q)，(PQ，(PQ）Q），PQ S , (P W) Q)不是

3、合式公式。左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式、。則：則： PQR 是合式公式是合式公式等價(jià)于等價(jià)于 ： （PQ）R ）命題公式外層的括號(hào)可以省略命題公式外層的括號(hào)可以省略等價(jià)于等價(jià)于 ： （PQ）R不等價(jià)于不等價(jià)于 ： P（QR）1.3命命題公式與翻譯題公式與翻譯左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式61.3命命題公式與翻譯題公式與翻譯 1.3.2 復(fù)合命題的符號(hào)化復(fù)合命題的符號(hào)化(翻譯翻譯) 自然語(yǔ)言的語(yǔ)句用自然語(yǔ)言的語(yǔ)句用 形式化形式化： 要準(zhǔn)確要準(zhǔn)確確定原子命題確定原子命題，并將其，并將其形式化形式化。 要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于識(shí)別自然

4、語(yǔ)言中的聯(lián)識(shí)別自然語(yǔ)言中的聯(lián)結(jié)詞結(jié)詞（有時(shí)它們被省略），（有時(shí)它們被省略），否定詞的位置否定詞的位置要放準(zhǔn)確。要放準(zhǔn)確。 必要必要時(shí)可以時(shí)可以進(jìn)行改述進(jìn)行改述，即改變?cè)瓉?lái)的敘述方式，即改變?cè)瓉?lái)的敘述方式，但要保證表達(dá)意思一致但要保證表達(dá)意思一致。 需要的需要的括號(hào)不能省略括號(hào)不能省略，而可以省略的括號(hào)，而可以省略的括號(hào)，在需要提高公式可讀性時(shí)亦可不省略。在需要提高公式可讀性時(shí)亦可不省略。 要注意語(yǔ)句的形式化要注意語(yǔ)句的形式化未必是唯一未必是唯一的。的。左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式可以把本命題表達(dá)為：(P Q）。 解 P：上海到北京的14次列車是下午五點(diǎn)半開(kāi)。 Q：上海到北京的1

5、4次列車是下午六點(diǎn)開(kāi)。在本例中，漢語(yǔ)的“或”是不可兼或，而邏輯聯(lián)結(jié)詞是“可兼或”，因此不能直接對(duì)兩命題析取。構(gòu)造如表1-3.1所示。PQ原命題PQ(P Q)TT F T FTF T F TFT T F TFF F T F表1-3.1例題例題2 2 上海到北京的上海到北京的1414次列車是下午五點(diǎn)半或六點(diǎn)開(kāi)。次列車是下午五點(diǎn)半或六點(diǎn)開(kāi)。左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式 解 這個(gè)命題的意義，亦可理解為： 如果你不努力則你將失敗。 若設(shè) P：你努力。 Q：你失敗。 本例可表示為： PQ例題例題5 5 除非你努力，否則你將失敗。除非你努力，否則你將失敗。左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與

6、等價(jià)公式 解 這個(gè)命題的意義是： 可兼或 若設(shè) P：張三可以做這事。 Q：李四可以做這事。 本例可表示為： P Q例題例題6 6 張三或李四都可以做這件事。張三或李四都可以做這件事。左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式101.3命命題公式與翻譯題公式與翻譯1) 1) 我今天進(jìn)城，除非下雨。我今天進(jìn)城，除非下雨。1-3.(7)1-3.(7)2) 2) 僅當(dāng)你走我將留下。僅當(dāng)你走我將留下。 1-3.(7) 1-3.(7)3) 3) 假如上午不下雨，我去看電影，否則就在家里假如上午不下雨，我去看電影，否則就在家里 讀書或看報(bào)。讀書或看報(bào)。 1-3.(7) 1-3.(7)4)4)一個(gè)人起初說(shuō)：

7、一個(gè)人起初說(shuō)：“占據(jù)空間的、有質(zhì)量的而且不斷占據(jù)空間的、有質(zhì)量的而且不斷變化的叫做物質(zhì)變化的叫做物質(zhì)”；后來(lái)他改說(shuō)，；后來(lái)他改說(shuō)，“占據(jù)空間的占據(jù)空間的有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的。有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的?！眴?wèn)問(wèn)他前后主張的差異在什么地方，試以命題形式進(jìn)他前后主張的差異在什么地方，試以命題形式進(jìn)行分析行分析。 1-3.(6)1-3.(6)練習(xí)練習(xí)1左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式111.3命命題公式與翻譯題公式與翻譯我今天進(jìn)城，除非下雨。我今天進(jìn)城，除非下雨。1-3.(7)1-3.(7)P：我今天進(jìn)城。Q:天下雨。 QP2) 2) 僅當(dāng)你走我將留下。僅當(dāng)你走我

8、將留下。 1-3.(7) 1-3.(7)P: 你走。 Q:我留下。 QP3) 3) 假如上午不下雨，我去看電影，否則就在家里假如上午不下雨，我去看電影，否則就在家里 讀書或看報(bào)。讀書或看報(bào)。 1-3.(7) 1-3.(7)P: 上午下雨。 Q:我去看電影。 R:我在家里讀或看報(bào)。(PQ)(PR)）（要么看電影要么留在家里，排斥或）解答左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式121.3命命題公式與翻譯題公式與翻譯5)5)一個(gè)人起初說(shuō)：一個(gè)人起初說(shuō)：“占據(jù)空間的、有質(zhì)量的而且不斷變化占據(jù)空間的、有質(zhì)量的而且不斷變化的叫做物質(zhì)的叫做物質(zhì)”；后來(lái)他改說(shuō)，；后來(lái)他改說(shuō)，“占據(jù)空間的有質(zhì)量的占據(jù)空間的

9、有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的。叫做物質(zhì)，而物質(zhì)是不斷變化的?！眴?wèn)他前后主張的問(wèn)他前后主張的差異在什么地方，試以命題形式進(jìn)行分析。差異在什么地方，試以命題形式進(jìn)行分析。 1-3.(6)1-3.(6)P:它占據(jù)空間Q:它有質(zhì)量R:它不斷變化S:它是物質(zhì)這個(gè)人起初主張：(PQR) S后來(lái)主張：(（PQ）S)(SR)解答左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式 練習(xí)練習(xí)2 （小李不在圖書館），（他要么找老師去了），（要么就（小李不在圖書館），（他要么找老師去了），（要么就是因?yàn)樯眢w不適，回宿舍去了）。是因?yàn)樯眢w不適，回宿舍去了）。命題符號(hào)化是很重要的，一定要掌握好，在命題推命題符號(hào)化是很重

10、要的，一定要掌握好，在命題推理中常常最先遇到的就是符號(hào)化一個(gè)問(wèn)題，解決不理中常常最先遇到的就是符號(hào)化一個(gè)問(wèn)題，解決不好，等于說(shuō)推理的首要前提沒(méi)有了。好，等于說(shuō)推理的首要前提沒(méi)有了。解解 設(shè)設(shè) P P：小李在圖書館。：小李在圖書館。Q Q：小李找老師。：小李找老師。 R R：小李身體不適。：小李身體不適。S S：小李回宿舍。：小李回宿舍。則命題符號(hào)化為：則命題符號(hào)化為： （P P）（(Q (RS)(Q (RS)）（小李不是（小李不是而是而是 ）（要么（要么要么要么 排斥或）排斥或）左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式141.3命命題公式與翻譯題公式與翻譯 小結(jié)小結(jié)：本節(jié)介紹了命題公式的概

11、念及復(fù)：本節(jié)介紹了命題公式的概念及復(fù)合命題的符號(hào)化合命題的符號(hào)化.重點(diǎn)是理解命題公式的重點(diǎn)是理解命題公式的遞歸定義遞歸定義,掌握復(fù)合命題的符號(hào)化方法掌握復(fù)合命題的符號(hào)化方法. 作業(yè)：作業(yè)：p12(5)左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式151.4.1 真值表真值表(Truth Table)1.4.2 等價(jià)公式等價(jià)公式(左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式16定義定義1.4.2(真值表真值表) 在命題公式在命題公式A中中, 對(duì)于命題變?cè)拿繉?duì)于命題變?cè)拿恳唤M賦值一組賦值和由它們所確定的和由它們所確定的命題公式命題公式A的真值列成的真值列成表表，稱做命題公式，稱做命題公式A 的的

12、真值表真值表?？紤]：考慮：含有含有n個(gè)命題變?cè)獋€(gè)命題變?cè)墓焦灿械墓焦灿卸嗌俳M不同的賦值多少組不同的賦值？2n左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式17對(duì)公式對(duì)公式A構(gòu)造真值表的具體步驟為：構(gòu)造真值表的具體步驟為：（1）找出公式中所有命題變?cè)┱页龉街兴忻}變?cè)狿1 , P2 ,Pn（2）按從小到大的順序列出對(duì)命題變?cè)┌磸男〉酱蟮捻樞蛄谐鰧?duì)命題變?cè)狿1 , P2 ,Pn ,的全部的全部2n組賦值。組賦值。（3）對(duì)應(yīng)各組賦值計(jì)算出公式）對(duì)應(yīng)各組賦值計(jì)算出公式A的真值，并將其列的真值，并將其列在對(duì)應(yīng)賦值的后面。在對(duì)應(yīng)賦值的后面。左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式18例例1

13、. 1. 給出給出(P(P Q)Q)(P(P Q)Q)的真值表：的真值表：P P Q Q P P Q Q (P(P Q)Q) PP QQ(P(P Q) Q) (P (P Q)Q)0 0 0 00 0 1 11 1 0 01 1 1 1左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式19例例1. 1. 給出給出(P(P Q)Q)(P(P Q)Q)的真值表：的真值表：P P Q Q P P Q Q (P(P Q)Q) PP QQ(P(P Q) Q) (P (P Q)Q)0 0 0 00 0 1 11 1 0 01 1 1 10 00 00 01 11 11 11 10 01 11 11 10 01 1

14、1 11 11 1左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式20例例2：構(gòu)造公式：構(gòu)造公式 (P Q) R的的 真值表。真值表。PQRPQ(P Q) R000001010011100101110111左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式21例例2：構(gòu)造公式：構(gòu)造公式 (P Q) R的的 真值表。真值表。PQRPQ(P Q) R0001000111010100111110000101001101011111左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式22 練習(xí)練習(xí)1：構(gòu)造公式：構(gòu)造公式 (PQ)( Q P）真值表。真值表。PQ P QP Q Q P(P Q)( Q P)00011011

15、左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式23 練習(xí)練習(xí)1：構(gòu)造公式：構(gòu)造公式 (PQ)( Q P）真值表。真值表。PQ P QP Q Q P(P Q)( Q P)0011111011011110010011100111左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式24PQ (P Q) (P Q) (P Q) Q00011011練習(xí)練習(xí)2：構(gòu)造公式：構(gòu)造公式 (P Q） Q 真值表。真值表。左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式25PQ (P Q) (P Q) (P Q) Q00100011001001011100練習(xí)練習(xí)2：構(gòu)造公式：構(gòu)造公式 (P Q） Q 真值表。真值表。左孝凌離散

16、數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式永真公式永真公式 永假公式：永假公式： 無(wú)論對(duì)其分量作怎樣的真值指派，其真值永為無(wú)論對(duì)其分量作怎樣的真值指派，其真值永為T，稱為永真公式，記為稱為永真公式，記為T 。如例如例1 無(wú)論對(duì)其分量作怎樣的真值指派，其真值永為無(wú)論對(duì)其分量作怎樣的真值指派，其真值永為F，稱為永假公式，記為稱為永假公式，記為F 。如例如例2 左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式 從真值表中可以看到，從真值表中可以看到，有些命題公式有些命題公式在分量的不同指派在分量的不同指派下，其對(duì)應(yīng)的真值與下，其對(duì)應(yīng)的真值與另一命題公式完全相同另一命題公式完全相同，如，如PQ與與PQ的對(duì)應(yīng)真值相

17、同，如表的對(duì)應(yīng)真值相同，如表1-4.5所示。所示。 PQPQPQTT T TTF F FFT T TFF T T表1-4.5我們說(shuō)我們說(shuō)PQ和和PQ是等價(jià)的，這是等價(jià)的，這在以后的推理中特在以后的推理中特別有用。別有用。1.4.2 等價(jià)公式等價(jià)公式左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式 同理(PQ)(PQ)與P Q對(duì)應(yīng)的真值相同，如表1-4.6所示。 表1-4.6 P Q PQ (PQ)(PQ)TT T TTF F FFT F FFF T T1.4.2 等價(jià)公式等價(jià)公式左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式29定義定義1.4.3: 給定兩個(gè)命題公式給定兩個(gè)命題公式A和和B,設(shè)設(shè)P1

18、 , P2 ,Pn為出現(xiàn)為出現(xiàn)于于A和和B中的所有原子變?cè)械乃性幼冊(cè)?若給若給P1 , P2 ,Pn任一組任一組真值指派真值指派, A和和B的真值都相同的真值都相同,則則稱稱A和和B是等價(jià)是等價(jià). 記作記作A B。1.4.2 等價(jià)公式等價(jià)公式左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式30 1. 真值表法真值表法 2. 等值演算法等值演算法v1. 真值表法真值表法 例例1. (P1. (P Q) Q) (P(P Q) Q) 見(jiàn)真值表例題見(jiàn)真值表例題1.1. 例例2. 2. 證明證明: P: PQ Q (PQ)(PQ) (QP)(QP)P PQ QP PQ QQPQPPQPQ (PQ)(P

19、Q) (QP)(QP)0 00 00 01 11 10 01 11 1證明公式等價(jià)的方法：證明公式等價(jià)的方法：左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式31 1. 真值表法真值表法 2. 等值演算法等值演算法 1. 真值表法真值表法 例例1. (P1. (P Q) Q) (P(P Q) Q) 見(jiàn)真值表例題見(jiàn)真值表例題1.1. 例例2. 2. 證明證明: P: PQ Q (PQ)(PQ) (QP)(QP)P PQ QP PQ QQPQPPQPQ (PQ)(PQ) (QP)(QP)0 00 01 11 11 11 10 01 10 00 01 10 01 10 00 01 10 00 01 11

20、 11 11 11 11 1所以：所以：P PQ Q (PQ)(PQ) (QP)(QP)(PQ)(PQ)試用等值演算方法證明試用等值演算方法證明另外，另外， P PQ Q (PQ) (Q P)左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式32 2. 等值演算法等值演算法(Equivalent Caculation)（利用（利用P15表表1-4.8)重要的等價(jià)式重要的等價(jià)式(補(bǔ)充補(bǔ)充): 11. 蘊(yùn)涵等值式蘊(yùn)涵等值式: : P PQ Q PP Q Q Q Q PP Q Q PP（假言易位）（假言易位） 12. 等價(jià)等值式等價(jià)等值式: : P PQ Q (PQ)(PQ) (QP)(QP) (PQ)

21、(Q P) (PQ) (Q P) (PQ)(PQ)(PQ)(PQ) 13. 假言易位假言易位: P PQ Q Q Q PP 14. 等價(jià)否定等值式等價(jià)否定等值式: P PQ Q PPQ Q 15. 歸謬論歸謬論: (P PQ Q ) ( ( P P Q)Q) P P 左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式對(duì)合律P P1冪等律PP P，PP P2結(jié)合律(PQ）R P（QR）(PQ）R P（QR）3交換律PQ QPPQ QP4分配律P（QR） （PQ）（PR）P（QR） （PQ）（PR）5吸收律P（PQ） PP（PQ） P6德摩根律(PQ) PQ(PQ) PQ7同一律PF P，PT P8零律

22、PT T，PF F9否定律PP T，PP F10表1-4.8命題定律任何數(shù)與0相或還是任何數(shù)任何數(shù)任何數(shù)與1相與為為1任何數(shù)與1相與還是任何數(shù)任何數(shù)與0相與為為0左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式例題6 驗(yàn)證吸收律 P（PQ） P P（PQ） P證明 列出真值表 表1-4.9PQPQ P（PQ）PQP（PQ）TT T T T TTF F T T TFT F F T FFF F F F F 由表1-4.9可知吸收律成立。練習(xí)18頁(yè)（4）左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式35 等值演算中使用的一條重要規(guī)則：等值演算中使用的一條重要規(guī)則：置換規(guī)則。置換規(guī)則。定義定義1.4.4 子

23、公式：子公式：如果如果X X是是wff Awff A的一部分的一部分, ,且且X X本身也是本身也是wffwff，則稱則稱X X是是A A的子公式。的子公式。 例如例如, , P(PQ)為為Q Q (P P (P(P Q)Q)的子公式。的子公式。定理定理1.4.1 置換定理：置換定理：設(shè)設(shè)X X是是wff Awff A的子公式，若的子公式，若X XY Y，則若將，則若將A A中的中的X X用用Y Y來(lái)置換，所得公式來(lái)置換，所得公式B B與與A A等價(jià)，即等價(jià)，即A AB B。定義定義1.4.51.4.5 等值演算：等值演算：根據(jù)已知的等價(jià)公式根據(jù)已知的等價(jià)公式, ,推演出另外一些等推演出另外一

24、些等價(jià)公式的過(guò)程稱為價(jià)公式的過(guò)程稱為等值演算等值演算. .左孝凌離散數(shù)學(xué)命題公式與翻譯真值表與等價(jià)公式36例例1 1： 證明證明 QQ（P P （P P Q Q）QPQP 證證: Q: Q（P P （P P Q Q）QPQP P( P(吸收律吸收律) ) 例例2 2： 證明證明 （P P QQ） Q Q P P Q Q 證：證： (P(P Q)Q) Q Q(P(P Q)Q) ( (QQ Q)Q)( (P P Q)Q) T TP P Q Q例例3 3：證明（：證明（PQPQ）（Q Q R R） P P Q Q R R證：（證：（PQPQ）（Q Q R R）（P P Q Q）（Q Q R R） ( (P P Q)Q) （Q Q R R） （P