離散數(shù)學(xué)復(fù)習(xí)資料

1、第1章命題邏輯本章重點：命題與聯(lián)結(jié)詞，公式與解釋，真值表，公式的類型及判定(主)析取(合取)范式，命題邏輯的推理理論.一、重點內(nèi)容1.命題命題表述為具有確定真假意義的陳述句。命題必須具備二個條件：其一，語句是陳述句；其二，語句有唯一確定的真假意義.2.六個聯(lián)結(jié)詞及真值表?“?”否定聯(lián)結(jié)詞，P是命題，?P是P的否命題，是由聯(lián)結(jié)詞?和命題P組成的復(fù)合命題.P取真值1，?P取真值0，P取真值0，?P取真值1.它是一元聯(lián)結(jié)詞.?“?”合取聯(lián)結(jié)詞

2、，P?Q是命題P，Q的合取式，是“?”和P，Q組成的復(fù)合命題.“?”在語句中相當(dāng)于“不但…而且…”，“既…又…”.P?Q取值1，當(dāng)且僅當(dāng)P，Q均取1；P?Q取值為0，只有P，Q之一取0.?“?”析取聯(lián)結(jié)詞，“??”不可兼析取(異或)聯(lián)結(jié)詞，P?Q是命題P，Q的析取式，是“?”和P，Q組成的復(fù)合命題.P??Q是聯(lián)結(jié)詞“??”和P，Q組成的復(fù)合命題.聯(lián)結(jié)詞“?”或“??”在一個語句中都表示“或”的含義，前者表示相容或，后者表示排斥或不相容的

3、或.即“P??Q”?“(?P?Q)?(P??Q)”.P?Q取值1，只要P，Q之一取值1，P?Q取值0，只有P，Q都取值0.?“?”蘊(yùn)含聯(lián)結(jié)詞，P?Q是“?”和P，Q組成的復(fù)合命題，只有P取值為1，Q取值為0時，P?Q取值為0；其余各種情況，均有P?Q的真值為1，亦即1?0的真值為0，0?1，1?1，0?0的真值均為1.在語句中，“如果P則Q”或“只有Q，才P，”表示為“P?Q”.?“?”等價聯(lián)結(jié)詞，P?Q是P，Q的等價式，是“?”和P，

4、Q組成的復(fù)合命題.“?”在語句中相當(dāng)于“…當(dāng)且僅當(dāng)…”，P?Q取值1當(dāng)且僅當(dāng)P，Q真值相同.3.命題公式、賦值與解釋，命題公式的分類與判別?命題公式與賦值，命題P含有n個命題變項P1，P2…Pn，給P1，P2…Pn各指定一個真值，稱為對P的一個賦值(真值指派).若指定的一組值使P的真值為1，則這組值為P的真指派；若使P的真值為0，則稱這組值稱為P的假指派.?命題公式分類，在各種賦值下均為真的命題公式A，稱為重言式(永真式)；在各種賦值下

5、均為假的命題公式A，稱為矛盾式(永假式)；命題A不是矛盾式，稱為可滿足式；判定命題公式類型的方法：其一是真值表法，任給公式，列出該公式的真值表，若真值表的最后一列全為1，則該公式為永真式；若真值表的最后一列全為0，則該公式是永假式；若真值表的最后一列既非全1，又非全0，則該公式是可滿足式.其二是推導(dǎo)演算法.利用基本等值式(教材P.16的十六個等值式或演算律)，對給定公式進(jìn)行等值推導(dǎo)，若該公式的真值為1，則該公式是永真式；若該公式的真值為

6、0，則該公式為永假式.既非永真，也非用假，成為非永真的可滿足式.其三主析取(合取)范式法，該公式的主析取范式有2n個極小項(即無極大項)，則該公式是永真式；該公式的主合取范式有2n個極大項(即無極小項)，則該公式是永假式；該公式的主析取(或合取)范式的極小項(或極大項)個數(shù)大于0小于2n，則該公式是可滿足式.?等值式A?B，命題公式A，B在任何賦值下，它們的真值均相同，稱A，B等值。定理1設(shè)?(A)是含命題公式A的命題，?(B)是用命題

7、公式B置換?(A)中的A之后得到的命題公式.如果A?B，則?(A)??(B).4.范式解(1)是命題，真值為1.(2)是命題，真值為0.(3)(4)不是命題因為不是陳述句.(5)是命題.真值是唯一的，遲早會被指出.例1.2將下列命題符號化：(1)雖然交通堵塞，但是老王還是準(zhǔn)時到達(dá)火車站；(2)張力是三好生，他是北京人或是天津人.(3)除非天下雨，否則我騎車上班.解(1)設(shè)P：交通堵塞，Q：老王準(zhǔn)時到達(dá)火車站.該命題符號化為：P?Q.(2

8、)設(shè)P：張力是三好生；Q：張力是北京人，R：張力是天津人.該命題符號化為P?(Q??R).(3)設(shè)P：天下雨，Q：我不騎車上班.該命題符號化為：Q?P，義即“只有天下雨，我才不騎車上班”，不下雨是我騎車上班的必要條件。它的等價說法是“如果天不下雨，我就騎車上班”，即?P??Q“如果天下雨，我就不騎車上班”，這是蘊(yùn)含關(guān)系，符號化為：P?Q注：本例各小題都是復(fù)合命題。如“李枚和張櫻花是好朋友”是簡單命題，用字母P表示。顯然P：李枚是好朋友，

9、Q：張櫻花是好朋友，符號化為Q?P是不通的.例1.3證明：P?(Q?R)?P?Q?R.證明方法1真值表法.列公式P?(Q?R)與P?Q?R的真值表如表1－1..表1－1公式P?(Q?R)與P?Q?R的真值表PQRQ?RP?(Q?R)P?QP?Q?RP?(Q?R)?P?Q?R0001101100111011010010110111101110011011101110111100010111111111由表可知，公式P?(Q?R)與P?Q?

10、R的真值完全相同，故P?(Q?R)?P?Q?R..或由表的最后一列可知，P?Q??P?Q是重言式，故P?(Q?R)?P?Q?R.注：作為本例的證明可以不要最后1列。若本例改為判斷P?(Q?R)?P?Q?R的類型，由最后列可知P?(Q?R)?P?Q?R是重言式.方法2等值演算法.P?（Q?R）?P?(?Q?R)(等值蘊(yùn)含式)??P?(?Q?R)(等值蘊(yùn)含式)?（?P??Q）?R(結(jié)合律)??(P?Q)?R(摩根律)?P?Q?R(等值蘊(yùn)含式