離散數(shù)學(xué)第1章命題公式與翻譯 真值表與等價公式

1、Discrete Mathematics山東科技大學(xué)山東科技大學(xué)信息科學(xué)與工程學(xué)院信息科學(xué)與工程學(xué)院課程回顧課程回顧 命題：命題的定義、真值、分類及其表示。命題聯(lián)結(jié)詞： 否定、合取、析取、條件、雙條件。PQPPQPQPQP QTT FTT TTTF FFT FFFT TFT TFFF TFF TT練習(xí)v判斷是否命題？黃島是個大城市。我們要努力學(xué)習(xí)。練習(xí)v只有具有確定真值的陳述句才是命題。只有具有確定真值的陳述句才是命題。v黃島是個大城市。是命題，其真值為假。v 我們要努力學(xué)習(xí)。 祈使句，不是命題。 第一章 命題邏輯 第2講 13 命題公式與翻譯 14真值表與等價公式 要求：理解合式公式及兩個合

2、式公式等價的定義，熟悉命題定律，會證明等價公式。重點：合式公式的定義，兩個合式公式等價的定義，10個命題定律。難點：推證等價公式。13 命題公式與翻譯命題公式與翻譯一、合式公式 前面已經(jīng)提到，不包含任何聯(lián)結(jié)詞的命題叫做原子命題，至少包含一個聯(lián)結(jié)詞的命題稱作復(fù)合命題。 設(shè)P和Q是任意兩個命題，則P， PQ，(PQ）(FQ），P (Q P)等都是復(fù)合命題。 若P和Q是命題變元，則上述各式均稱作命題公式。P和Q稱作命題公式的分量。說明：命題公式?jīng)]有真值，僅當(dāng)其中命題變元用確定的命題代入時，才得到一個命題。這個命題的真值，依賴于代換變元的那些命題的真值。并不是由命題變元，聯(lián)結(jié)詞和一些括號組成的字符串都

3、能成為命題公式。定義1-3.1 命題演算的合式公式(wff)，規(guī)定為： (1)單個命題變元本身是一個合式公式。 (2)如果A是合式公式，那么A是合式公式。 (3)如果A和B是合式公式，那么(AB)，(AB)， (AB）和(A B)都是合式公式。 (4)當(dāng)且僅當(dāng)能夠有限次地應(yīng)用(1)、(2)、(3)所得到 的包含命題變元，聯(lián)結(jié)詞和括號的符號串是合式公式。v 這個合式公式的定義，是以遞歸形式給出的，其中(1)稱為基礎(chǔ)，(2)(3)稱為歸納，(4)稱為界限。按照定義，下列公式都是合式公式： (PQ），(PQ)，(P(PQ)， (PQ）(QR) （S T) 而 (PQ）(Q)，(PQ，(PQ）Q）等都

4、不是合式公式。v目的：減少使用括號的數(shù)量目的：減少使用括號的數(shù)量v約定：命題公式外層的括號可以省略；約定：命題公式外層的括號可以省略；、。v范例：范例： PQRv等價于等價于 ： （PQ）R ）v等價于等價于 ： （PQ）Rv不等價于不等價于 ： P（QR）命題的翻譯 v有了聯(lián)結(jié)詞的合式公式概念，我們可以把自然語言中的有些語句，翻譯成數(shù)理邏輯中的符號形式。v把一個用文字敘述的命題相應(yīng)地寫成由命題標(biāo)識符、聯(lián)結(jié)詞和圓括號表示的合式公式，稱為命題的符號化。v符號化應(yīng)該注意下列事項： 確定給定句子是否為命題。 句子中聯(lián)結(jié)詞是否為命題聯(lián)結(jié)詞。 要正確地表示原子命題和適當(dāng)選擇命題聯(lián)結(jié)詞。(1)找出原子命題

5、(2)用大寫字母代替命題(3)按題意用聯(lián)結(jié)詞自然語言的語句用自然語言的語句用形式化形式化主要注意以下幾個方面：主要注意以下幾個方面： 要準(zhǔn)確確定原子命題，并將其形式化。要準(zhǔn)確確定原子命題，并將其形式化。 要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于識別自然語要選用恰當(dāng)?shù)穆?lián)結(jié)詞，尤其要善于識別自然語言中的聯(lián)結(jié)詞（有時它們被省略），否定詞的位置要言中的聯(lián)結(jié)詞（有時它們被省略），否定詞的位置要放準(zhǔn)確。放準(zhǔn)確。 必要必要時可以進行改述，即改變原來的敘述方式，時可以進行改述，即改變原來的敘述方式，但要保證表達意思一致但要保證表達意思一致。 需要的括號不能省略，而可以省略的括號，需要的括號不能省略，而可以省略的括號，在

6、需要提高公式可讀性時亦可不省略。在需要提高公式可讀性時亦可不省略。 要注意語句的形式化未必是唯一的。要注意語句的形式化未必是唯一的。 自然語言的語句用自然語言的語句用 形式化形式化解 若設(shè) P：他聰明。 Q：他用功。 在自然語言中這個“既又”顯然與“且”的意義一樣，故本例可記為： PQ 。例題3 他既聰明又用功。例題解 這里“雖但”這個詞不能用前述聯(lián)結(jié)詞表達，但其實際意義是：他聰明且不用功。若設(shè) P：他聰明。 Q：他用功。 本例可表示為： PQ例題4 他雖聰明但不用功。從表中可看出原命題不能用前述五個聯(lián)結(jié)詞單獨寫出，但是如用命題和聯(lián)結(jié)詞組合，可以把本命題表達為：(P Q）。 解 P：上海到北京

7、的14次列車是下午五點半開。 Q：上海到北京的14次列車是下午六點開。 在本例中，漢語的“或”是不可兼或，而邏輯聯(lián)結(jié)詞是“可兼或”，因此不能直接對兩命題析取。構(gòu)造表如表1-3.1所示。PQ原命題P Q (P Q)TT F T FTF T F TFT T F TFF F T F表1-3.1例題2 上海到北京的14次列車是下午五點半或六點開。例題 解 這個命題的意義，亦可理解為：如果你不努力則你將失敗。 若設(shè) P：你努力。 Q：你失敗。 本例可表示為： PQ例題5 除非你努力，否則你將失敗。 解 這個命題的意義是： 張三可以做這件事，并且李四也可以做這件事。 若設(shè)P：張三可以做這事。 Q：李四可以

8、做這事。 本例可表示為： PQ例題6 張三或李四都可以做這件事。例題v解 找出各原子命題，并用命題符號表示： A：我們要做到身體好。 B：我們要做到學(xué)習(xí)好。 C：我們要做到工作好。 P：我們要為祖國四化建設(shè)而奮斗。 v 例題1 試以符號形式寫出命題：我們要做到身體好、學(xué)習(xí)好、工作好，為祖國四化建設(shè)而奮斗。v故命題可形式化為：（A B C） P思考vA：我們要做到身體好。vA：我們要努力學(xué)習(xí)。 祈使句，不是命題。v 從上面的例子中可以看到，自然語言中的一些聯(lián)結(jié)詞，如：“與”“且”“或”“除非則”等等都各有其具體含義，因此需分別不同情況，根據(jù)實際含義，翻譯成適當(dāng)?shù)倪壿嬄?lián)結(jié)詞。v為了便于正確表達命題

9、間的相互關(guān)系，有時也常常采用列出“真值表”的方法，進一步分析各原命題，以此尋找邏輯聯(lián)結(jié)詞，使原來的命題能夠正確地用形式符號予以表達。 小結(jié) 學(xué)習(xí)本節(jié)要深刻理解命題公式的定義，能夠把用自然語言中的有些語句，翻譯成數(shù)理邏輯中的符號形式。 合式公式：命題演算的合式公式(wff) 規(guī)定為： (1)單個命題變元本身是一個合式公式。 (2)如果A是合式公式，那么A是合式公式。 (3)如果A和B是合式公式，那么(AB)，(AB)，(AB）和(A B)都是合式公式。 (4)當(dāng)且僅當(dāng)能夠有限次地應(yīng)用(1)、(2)、(3)所得到的包含命題變元，聯(lián)結(jié)詞和括號的符號串是合式公式。 翻譯 把自然語言中的有些語句，翻譯成

10、數(shù)理邏輯中的符號形式。 優(yōu)先次序 規(guī)定聯(lián)結(jié)詞運算的優(yōu)先次序為：、14 真值表與等價公式真值表與等價公式 1.真值表 定義1-4.1 在命題公式中，對于分量（命題變元）指派真值的各種可能組合，就確定了這個命題公式的各種真值情況，把它匯列成表，就是命題公式的真值表。P Q P PQTTFTTFFF FTTTFFTT舉例：構(gòu)造PQ的真值表。解（見表 1-4.1 ）表 1-4.1例題例題2 給出給出(PQ）P的真值表。的真值表。解解 （見表（見表1-4.2） P Q PQP(PQ）PTTTFFTFFFFFTFTFFFFTF例題3 給出(PQ）（PQ）的真值表。解 PQPQPQPQ（PQ） （PQ）TT

11、 F F T F TTF F T F F FFT T F F F FFF T T F T T表1-4.3例題例題4 給出給出(PQ） （PQ）的真值表。）的真值表。解解PQPQ(PQ)PQPQ(PQ） （PQ）TT T F F F F TTF F T F T T TFT F T T F T TFF F T T T T T表表 1-4.4v 由表1-4.4 (表1-4.2)可以看出，有一類公式不論命題變元作何種指派，其真值永為真(假)，我們把這類公式記為T(F)。注意回顧PQPQ(PQ)PQPQ(PQ） （PQ）TT T F F F F TTF F T F T T TFT F T T F T T

12、FF F T T T T T表1-4.4回顧v 表 1-4.2v PQ PQP(PQ）PTT T F FTF F F FFT F T FFF F T Fv 重言式和矛盾式重言式和矛盾式這兩類特殊的命題公式在今后的命題演算中極為有用。v 定義定義1-5.1 給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為T，則稱該命題公式為重言式重言式或永真公式永真公式。定義定義1-5.2 給定一命題公式，若無論對分量作怎樣的指派，其對應(yīng)的真值永為F，則稱該命題公式為矛盾式矛盾式或永假公式永假公式。v 由表1-4.4 (表1-4.2)可以看出，有一類公式不論命題變元作何種指派，其真值永為真(假)，我們

13、把這類公式記為T(F)。v 在真值表中，命題公式真值的取值數(shù)目，決定于分量（命題變元）的個數(shù)。例如，由2個命題變元組成的命題公式共有四種可能的真值，由3個命題變元組成的命題公式共有八種真值。一般說來，n個命題變元組成的命題公式共有2n種真值情況。注意 從真值表中可以看到，有些命題公式在分量的不同指派下，其對應(yīng)的真值與另一命題公式完全相同，如PQ與PQ的對應(yīng)真值相同，如表1-4.5所示。 PQPQPQTT T TTF F FFT T TFF T T表1-4.5我們說我們說PQ和和PQ是等價的，是等價的，這在以后的推理中這在以后的推理中特別有用。特別有用。 同理(PQ)(PQ)與P Q對應(yīng)的真值相

14、同，如表1-4.6所示。 表1-4.6 P Q P Q (PQ)(PQ)TT T TTF F FFT F FFF T T二、等價公式 1.定義 定義1-4.2 給定兩個命題公式A和B，設(shè)P1，P2，Pn為所有出現(xiàn)于A和B中的原子變元，若給P1，P2，Pn任一組真值指派，A和B的真值都相同，則稱A和B是等價的或邏輯相等。記作A B。v在這里，請注意和的區(qū)別與聯(lián)系：v區(qū)別：是邏輯聯(lián)結(jié)詞，它出現(xiàn)在命題公式中； 不是邏輯聯(lián)結(jié)詞，它表示兩個命題公式的一種關(guān)系，不屬于這兩個公式的任何一個公式中的符號。v2、等價公式的證明方法： 真值表法 由表1-4.7可知P Q與(PQ) (QP）真值相同，命題得證。例題

15、5 證明 P Q (PQ) (QP)證明 列出其值表 表 1-4.7PQP QQPP Q (PQ) (QP）TT T T T TTF F T F FFT T F F FFF T T T Tv2、等價公式的證明方法：（1）值表法（2）推導(dǎo)的證明方法命題定律推導(dǎo)的證明方法命題定律（表1-4.8列出的命題定律都可以用真值表予以驗證） 表1-4.8對合律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

16、同一律PF P，PT P8零律PT T，PF F9否定律PP T，PP F10PQ PQ例題6 驗證吸收律 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可知吸收律成立。v2、等價公式的證明方法：（1）值表法（2）推導(dǎo)的證明方法命題定律等價置換等價置換 在一個命題公式中，如果用公式置換命題的某個部分，一般地將會產(chǎn)生某種新的公式，新公式不一定與原公式等價，例如Q(P(PQ)中以(PQ)取代(PQ)，則Q(P(PQ) )就與原式不同。PQP(PQ)Q(P(

17、PQ)PQP(PQ)Q(P(PQ) )TT T T T T TTF T T T T TFT F F T T TFF F T F F T等價置換為了保證置換后的公式與原始公式是等價的，需對置換作出一些規(guī)定。 v等價置換v定義1-4.3 如果X是合式公式A的一部分，且X本身也是一個合式公式，則稱X為公式A的子公式子公式。v證明 因為在相應(yīng)變元的任一種指派情況下，X與Y的真值相同，故以Y取代X后，公式B與公式A在相應(yīng)的指派情況下，其真值亦必相同，故A B。 口 v滿足定理1-4.1條件的置換稱為等價置換(等價代換)。v證明命題公式A和B等價的方法：將命題公式A的子公式不斷做等價替換后得到新命題公式B

18、，則命題公式A和B等價v定理定理1-4.1 設(shè)設(shè)X是合式公式是合式公式A的子公式，若的子公式，若X Y，如果將如果將A中的中的X用用Y來置換，所得到公式來置換，所得到公式B與公式與公式A等價，即等價，即A B。 例題7 證明Q(P(PQ) QP PQPQP（PQ）QP（PQ）QPTT T T T TTF F T T TFT F F F FFF F F T T有了最基本的的命題公式的等價關(guān)系，再利用定理1-4.1，就可以推證一些更為復(fù)雜的命題等價公式。證明 設(shè)A：Q(P(PQ)， B：QP 因為 P(PQ) P 故 A B 對A B亦可用表1-4.10予以驗證： 表 1-4.10吸收律 例題8 證明(PQ) (PQ) P (PQ) (PQ) (PQ)P) ( (PQ ) Q)