離散數(shù)學(xué)復(fù)習(xí)資料(已修改)
2025-08-17 10:25 本頁面
【正文】 離散數(shù)學(xué)復(fù)習(xí)資料第1章 命題邏輯 本章重點(diǎn)：命題與聯(lián)結(jié)詞，公式與解釋，真值表，公式的類型及判定, (主)析取(合取)范式，命題邏輯的推理理論. 一、重點(diǎn)內(nèi)容 1. 命題 命題表述為具有確定真假意義的陳述句。命題必須具備二個(gè)條件：其一，語句是陳述句；其二，語句有唯一確定的真假意義. 2. 六個(gè)聯(lián)結(jié)詞及真值表 h“216?！狈穸?lián)結(jié)詞，P是命題，216。P是P的否命題，是由聯(lián)結(jié)詞 216。 ，216。P取真值0，P取真值0，216。P取真值1. 它是一元聯(lián)結(jié)詞. h “217?！焙先÷?lián)結(jié)詞，P217。Q是命題P，Q的合取式，是“217?！焙蚉，Q組成的復(fù)合命題. “217?！痹谡Z句中相當(dāng)于“不但…而且…”，“既…又…”. P217。Q取值1，當(dāng)且僅當(dāng)P，Q均取1；P217。Q取值為0，只有P，Q之一取0. h “218?！蔽鋈÷?lián)結(jié)詞，“`218?！辈豢杉嫖鋈?異或)聯(lián)結(jié)詞， P218。Q是命題P，Q的析取式，是“218?！焙蚉，Q組成的復(fù)合命題. P`218。Q是聯(lián)結(jié)詞“`218。”和P，Q組成的復(fù)合命題. 聯(lián)結(jié)詞“218?！被颉癭218?！痹谝粋€(gè)語句中都表示“或”的含義，前者表示相容或，后者表示排斥或不相容的或. 即“P`218。Q”171?！?216。P217。Q)218。(P217。216。Q)”. P218。Q取值1，只要P，Q之一取值1，P218。Q取值0，只有P，Q都取值0. h “174?！碧N(yùn)含聯(lián)結(jié)詞， P174。Q是“174。”和P，Q組成的復(fù)合命題，只有P取值為1，Q取值為0時(shí)，P174。Q取值為0；其余各種情況，均有P174。Q的真值為1，亦即1174。0的真值為0，0174。1，1174。1，0174。0的真值均為1. 在語句中，“如果P則Q”或“只有Q，才P，”表示為“P174。Q”.h “171?！?等價(jià)聯(lián)結(jié)詞，P171。Q是P，Q的等價(jià)式，是“171?！焙蚉，Q組成的復(fù)合命題. “171?！痹谡Z句中相當(dāng)于“…當(dāng)且僅當(dāng)…”，P171。Q取值1當(dāng)且僅當(dāng)P，Q真值相同.3. 命題公式、賦值與解釋，命題公式的分類與判別 h命題公式與賦值，命題P含有n個(gè)命題變項(xiàng)P1，P2,…,Pn，給P1，P2,…,Pn各指定一個(gè)真值，稱為對(duì)P的一個(gè)賦值(真值指派). 若指定的一組值使P的真值為1，則這組值為P的真指派；若使P的真值為0，則稱這組值稱為P的假指派. h命題公式分類，在各種賦值下均為真的命題公式A，稱為重言式(永真式)；在各種賦值下均為假的命題公式A，稱為矛盾式(永假式)；命題A不是矛盾式，稱為可滿足式；判定命題公式類型的方法：其一是真值表法，任給公式，列出該公式的真值表，若真值表的最后一列全為1，則該公式為永真式；若真值表的最后一列全為0，則該公式是永假式；若真值表的最后一列既非全1，又非全0，. 利用基本等值式()，對(duì)給定公式進(jìn)行等值推導(dǎo)，若該公式的真值為1，則該公式是永真式；若該公式的真值為0，也非用假，(合取)范式法，該公式的主析取范式有2n個(gè)極小項(xiàng)(即無極大項(xiàng))，則該公式是永真式；該公式的主合取范式有2n個(gè)極大項(xiàng)(即無極小項(xiàng))，則該公式是永假式；該公式的主析取(或合取)范式的極小項(xiàng)(或極大項(xiàng))個(gè)數(shù)大于0小于2n,，則該公式是可滿足式.h等值式A219。B，命題公式A，B在任何賦值下，它們的真值均相同，稱A，B等值。定理1 設(shè)F(A)是含命題公式A的命題，F(xiàn)(B)是用命題公式B置換F(A)中的A之后得到的命題公式. 如果A219。B，則F(A)219。F(B). 4. 范式 h 析取(合取)范式，僅有有限個(gè)簡單合取式(析取式)構(gòu)成的析取式(合取式)，就是析取(合取)范式. h 極小項(xiàng)(極大項(xiàng))，n個(gè)命題變項(xiàng)P1,P2,…,Pn，每個(gè)變項(xiàng)或它的否定兩者只有其一出現(xiàn)且僅出現(xiàn)一次，第i個(gè)命題變項(xiàng)或者其否定出現(xiàn)在從左起第i個(gè)位置上(無腳標(biāo)時(shí)，按字典序排列)，這樣的簡單合取式(析取式)為極小項(xiàng)(極大項(xiàng)). 以兩個(gè)命題變項(xiàng)為例，m00=216。P217。216。Q，m01=216。P217。Q,m10=P217。216。Q,m11=P217。Q是極小項(xiàng)。M00=P217。Q，M01=P217。216。Q,M10=216。P217。Q,M11=216。P217。216。Q是極大項(xiàng). h 主析取范式(主合取范式) 含有n個(gè)命題變項(xiàng)的命題公式，如果與一個(gè)僅有極小項(xiàng)(極大項(xiàng))的析取(合取)構(gòu)成的析取(合取)范式等值，則該等值式稱為原命題公式的主析取(合取)范式。 每項(xiàng)含有n個(gè)命題變項(xiàng)(變項(xiàng)字母齊全)的合取式(析取式)的析取(合取)為主析取(合取)范式. 任意命題公式都存在與之等值的范式，存在與之等值的主范式，且是惟一的. 求范式，包括求析取范式、合取范式、主析取范式和主合取范式. 關(guān)鍵有兩點(diǎn)：其一是準(zhǔn)確掌握范式定義；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，結(jié)果的前一步適當(dāng)使用冪等律. 求析取(合取)范式的步驟： ① 將公式中的聯(lián)結(jié)詞都化成216。，217。，218。(即消去個(gè)數(shù)中的聯(lián)結(jié)詞174。，171。，`218。)；② 將否定聯(lián)結(jié)詞216。消去或移到各命題變項(xiàng)之前；③ 利用分配律、結(jié)合律等，將公式化為析取(合取)范式.求命題公式A的主析取(合取)范式的步驟：① 求公式A的析取(合取)范式； ② “消去”析取(合取)范式中所有永假式(永真式)的析取項(xiàng)(合取項(xiàng))，如P217。216。P(P218。216。P)用0(1)替代. 用冪等律將析取(合取)范式中重復(fù)出現(xiàn)的合取項(xiàng)(析取項(xiàng))或相同的變項(xiàng)合并，如P2
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1