資源描述：
《離散數(shù)學-命題邏輯2》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、第一章數(shù)理邏輯一命題邏輯命題及其表示法聯(lián)結詞命題公式與翻譯真值表與等價式等價式與蘊含式對偶與范式推理理論二謂詞邏輯謂詞的概念與表示命題函數(shù)與量詞謂詞公式與翻譯變元的約束謂詞演算的等價式與蘊含式前束范式謂詞演算的推理理論本章作業(yè)真值表與等價公式定義1-4、1在命題公式中，對于分量指派真值的各種可能組合，就確定了這個命題公式的各種真值情況，把它匯列成表，就是命題公式的真值表。例1構造┒P∨Q的真值表。例2給出(P∧Q)∧┒P的真值表。例3給出(P∧Q)∨(┒P∧┒Q)的真值表。例4給出┒(P∧Q)?(┒P∨┒Q)的真值表。等價式和蘊涵式一、幾個定義與定理定義1-5、1給定一命題公式，若
2、無論對分量作怎樣的指派，其對應的真值永為T，則稱該命題公式為重言式或永真公式。定義1-5、2給定一命題公式，若無論對分量作怎樣的指派，其對應的真值永為F，則稱該命題公式為矛盾式或永假公式。定理1-5、1任何兩個重言式的合取或析取，仍然是一個重言式。證明：設A和B為兩個重言式，則不論A和B的分量指派任何真值，總有A為T，B為T，故A∧B?T,A∨B?T。定理：一個重言式，對同一分量都用任何合式公式置換，其結果仍為一個重言式。證明：由于重言式的真值與分量的指派無關，故對同一分量以任何合式公式置換后，重言式的真值仍永為T。定義1-4、2給定兩個命題公式A和B，設P1，P2，…，Pn為所有
3、出現(xiàn)于A和B中的原子變元，若給P1，P2，…，Pn任一組真值指派，A和B的真值都相同，則稱A和B是等價的或邏輯相等。記作A?B。例5證明P?Q?(P→Q)∧(Q→P)定理：設A、B為兩個命題公式，A?B當且僅當A?B為一個重言式。等價式下表列出的命題定律，都可以用真值表予以驗證。10否定律9零律8同一律7德·摩根律6吸收律5分配律4交換律3結合律2冪等律1??對合律補充：其它常用等價公式(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(逆反式)我們稱Q→P為逆換式，稱┒P→┒Q為反換式定義1
4、-4、3如果X是合式公式A的一部分，且X本身也是一個合式公式，則稱X為公式A的子公式。定理1-4、1設X是合式公式A的子公式，若X?Y，如果將A中的X用Y來置換，所得到的公式B與公式A等價，即A?B。證明：因為在相應變元的任一種指派情況下，X與Y的真值相同，故以Y取代X后，公式B與公式A在相應的指派情況下，其真值亦必相同，故A?B。注：滿足定理1-4、1條件的置換稱為等價置換（等價代換）。例題7證明Q→(P∨(P∧Q))?Q→P例題8證明(P∧Q)∨(P∧┒Q)?P例題9證明P→(Q→R)?Q→(P→R)?┒R→(Q→┒P)例題10證明((P∨Q)∧┒(┒P∧(┒Q∨┒R)))∨(
5、┒P∧┒Q)∨(┒P∧┒R)?T下一節(jié)例7證明設A：因為故B：即例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解:TFFTTFTTTTFFFTTFFFFTTTTTQP定義：當且僅當P→Q是一個重言式時，我們稱
6、“P蘊含Q”，并記作P?Q。注意：區(qū)別條件與蘊含，同時，二者存在聯(lián)系.定理：設P，Q為任意兩個命題公式，P?Q的充分必要條件是P?Q且Q?P。證明：若P?Q，則P?Q為重言式，因為P?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。證畢。蘊含式二、蘊含有下面幾個常用的性質：（1）設A、B、C為合式公式，若A?B且A是重言式，則B必是重言式。（2）若A?B，B?C，則A?C，即蘊含關系是傳遞的。（3）若A?B且A?C，那么A?(B∧C)（4）若A?B且C?B，則A∨C
7、?B三、下表所列各蘊含式都可推理證明。1413121110987654321重言式、等價式與蘊涵式的證明：例題1證明((P∨S)∧R)∨┒((P∨S)∧R)為重言式。例題2證明┒(P∧Q)?(┒P∨┒Q)例題3推證┒Q∧(P→Q)?┒PBACK例題1證明因為P∨┒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
