離散數(shù)學(xué)-命題邏輯.ppt

《離散數(shù)學(xué)-命題邏輯.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第一章數(shù)理邏輯一命題邏輯命題及其表示法聯(lián)結(jié)詞命題公式與翻譯真值表與等價(jià)式等價(jià)式與蘊(yùn)含式對(duì)偶與范式推理理論二謂詞邏輯謂詞的概念與表示命題函數(shù)與量詞謂詞公式與翻譯變?cè)募s束謂詞演算的等價(jià)式與蘊(yùn)含式前束范式謂詞演算的推理理論本章作業(yè)真值表與等價(jià)公式定義1-4、1在命題公式中，對(duì)于分量指派真值的各種可能組合，就確定了這個(gè)命題公式的各種真值情況，把它匯列成表，就是命題公式的真值表。例1構(gòu)造┒P∨Q的真值表。例2給出(P∧Q)∧┒P的真值表。例3給出(P∧Q)∨(┒P∧┒Q)的真值表。例4給出┒(P∧Q)?(┒P∨┒Q)的真值表。等價(jià)式和蘊(yùn)涵式一、幾個(gè)定義與定理定義1-5、1給定

2、一命題公式，若無(wú)論對(duì)分量作怎樣的指派，其對(duì)應(yīng)的真值永為T，則稱該命題公式為重言式或永真公式。定義1-5、2給定一命題公式，若無(wú)論對(duì)分量作怎樣的指派，其對(duì)應(yīng)的真值永為F，則稱該命題公式為矛盾式或永假公式。定理1-5、1任何兩個(gè)重言式的合取或析取，仍然是一個(gè)重言式。證明：設(shè)A和B為兩個(gè)重言式，則不論A和B的分量指派任何真值，總有A為T，B為T，故A∧B?T,A∨B?T。定理：一個(gè)重言式，對(duì)同一分量都用任何合式公式置換，其結(jié)果仍為一個(gè)重言式。證明：由于重言式的真值與分量的指派無(wú)關(guān)，故對(duì)同一分量以任何合式公式置換后，重言式的真值仍永為T。定義1-4、2給定兩個(gè)命題公式A和B，

3、設(shè)P1，P2，…，Pn為所有出現(xiàn)于A和B中的原子變?cè)艚oP1，P2，…，Pn任一組真值指派，A和B的真值都相同，則稱A和B是等價(jià)的或邏輯相等。記作A?B。例5證明P?Q?(P→Q)∧(Q→P)定理：設(shè)A、B為兩個(gè)命題公式，A?B當(dāng)且僅當(dāng)A?B為一個(gè)重言式。等價(jià)式下表列出的命題定律，都可以用真值表予以驗(yàn)證。10否定律9零律8同一律7德·摩根律6吸收律5分配律4交換律3結(jié)合律2冪等律1??對(duì)合律補(bǔ)充：其它常用等價(jià)公式(1)P→Q?┒P∨Q(2)P?Q?(P→Q)∧(Q→P)?┒P?┒Q(3)(P→Q)∧(P→┒Q)?┒P(歸繆論)(4)P→Q?┒Q→┒P(逆反式)我們稱

4、Q→P為逆換式，稱┒P→┒Q為反換式定義1-4、3如果X是合式公式A的一部分，且X本身也是一個(gè)合式公式，則稱X為公式A的子公式。定理1-4、1設(shè)X是合式公式A的子公式，若X?Y，如果將A中的X用Y來(lái)置換，所得到的公式B與公式A等價(jià)，即A?B。證明：因?yàn)樵谙鄳?yīng)變?cè)娜我环N指派情況下，X與Y的真值相同，故以Y取代X后，公式B與公式A在相應(yīng)的指派情況下，其真值亦必相同，故A?B。注：滿足定理1-4、1條件的置換稱為等價(jià)置換（等價(jià)代換）。例題7證明Q→(P∨(P∧Q))?Q→P例題8證明(P∧Q)∨(P∧┒Q)?P例題9證明P→(Q→R)?Q→(P→R)?┒R→(Q→┒P)例

5、題10證明((P∨Q)∧┒(┒P∧(┒Q∨┒R)))∨(┒P∧┒Q)∨(┒P∧┒R)?T下一節(jié)例7證明設(shè)A：因?yàn)楣蔅：即例8證明例9證明又，例10證明原式左邊例1解TTFFTTTFFFFTTFTT┒P∨Q┒PQP例2解TTFF┒PFFFFFFTFFFFTFTTT(P∧Q)∧┒PP∧QQP例3解TFFF┒P∧┒QFFFTP∧QTFTF┒QTTFFFTTFFFFTTFTT(P∧Q)∨(┒P∧┒Q)┒PQP例4解TTTF┒P∨┒QTFTF┒QTTFF┒PTTTF┒(P∧Q)TFFFTFTFTFFTTTTT┒(P∧Q)?(┒P∨┒Q)P∧QQP例5解:TFFTTFTTTTFF

6、FTTFFFFTTTTTQP定義：當(dāng)且僅當(dāng)P→Q是一個(gè)重言式時(shí)，我們稱“P蘊(yùn)含Q”，并記作P?Q。注意：區(qū)別條件與蘊(yùn)含，同時(shí)，二者存在聯(lián)系.定理：設(shè)P，Q為任意兩個(gè)命題公式，P?Q的充分必要條件是P?Q且Q?P。證明：若P?Q，則P?Q為重言式，因?yàn)镻?Q?(P→Q)∧(Q→P)故P→Q為T且Q→P為T，即P?Q，Q?P成立。反之，若P?Q且Q?P，則P→Q為T且Q→P為T，因此P?Q為T，P?Q是重言式，即P?Q。證畢。蘊(yùn)含式二、蘊(yùn)含有下面幾個(gè)常用的性質(zhì)：（1）設(shè)A、B、C為合式公式，若A?B且A是重言式，則B必是重言式。（2）若A?B，B?C，則A?C，即蘊(yùn)含關(guān)系

7、是傳遞的。（3）若A?B且A?C，那么A?(B∧C)（4）若A?B且C?B，則A∨C?B三、下表所列各蘊(yùn)含式都可推理證明。1413121110987654321重言式、等價(jià)式與蘊(yùn)涵式的證明：例題1證明((P∨S)∧R)∨┒((P∨S)∧R)為重言式。例題2證明┒(P∧Q)?(┒P∨┒Q)例題3推證┒Q∧(P→Q)?┒PBACK例題1證明因?yàn)镻∨┒P?T，如以((P∨S)∧R)置換P即得((P∨S)∧R)∨┒((P∨S)∧R)?T例題2證明由上節(jié)例題4表可知，┒(P∧Q)?(┒P∨┒Q)為重言式，故根據(jù)定理1-5、3：┒(P∧Q)?(┒P∨┒Q)例題3