離散數(shù)學(xué)17對偶與范式-資料下載頁
2025-01-16 20:09本頁面
【正文】 000 M000 P∨ Q∨ 172。R 001 M001 P∨ 172。Q∨ R 010 M010 P∨ 172。Q∨ 172。R 011 M011 172。P∨ Q∨ R 100 M100 172。 P∨ Q∨ 172。R 101 M101 172。P∨ 172。Q∨ R 110 M110 172。P∨ 172。Q∨ 172。R 111 M111 31 四、主合取范式 極大項有如下幾個性質(zhì)： ? （ 1）每一個極大項當(dāng)其真值指派與編碼相同時，其真值為 0，其它 2n1指派情況下均為 1。 ? （ 2） 任意兩個不同的極大項的析取式為永真式。 ? （ 3） 全體極大項的合取式為永假式。記為： ???120niiM?M0∧ M1∧ ? ∧ ?0 32 四、主合取范式 定義 對于給定的命題公式，如果有一個它的等價公式， 僅由極大項的合取 組成，則該等價式稱為原公式的 主合取范式 。 定理 在真值表中，一個公式的真值為 F 的指派所對應(yīng)的極大項的合取，即為此公式的主合取范式。 33 四、主合取范式 由定理 主析取范式的步驟如下： ? （ 1）構(gòu)造命題公式的真值表。 ? （ 2）找出公式的成假賦值對應(yīng)的極大項。 ? （ 3）這些極大項的合取就是此公式的主合取范式。 例 用真值表法，求 (P→Q)→R的主合取范式 34 四、主合取范式 解： 1.(P→Q)→R的真值表如下： ： P∨ Q∨ R (成假賦值為000) 、 P∨ 172。Q∨ R (成假賦值為 010)、 172。P∨ 172。Q∨ R (成假賦值為 110) ： (P∨ Q∨ R)∧ (P∨ 172。Q∨ R)∧ (172。P∨ 172。Q∨ R) ?M000∧ M010∧ M110?M0∧ M2∧ M6 P Q R P→ Q (P→ Q)→ R 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 35 四、主合取范式 與求主析取范式相似，除了用真值表方法外，也可利用 等值演算法 求得給定命題公式的主合取范式。 其演算步驟如下： ① 化歸為合取范式 。 ② 除去所有永真的合取項 。 ③ 在合取式中合并重復(fù)出現(xiàn)的析取項和相同的變元 。 ④ 對析取項補入沒有出現(xiàn)的命題變元 。 即 增加∨ (P∧ 172。 P)， 然后 ， 應(yīng)用分配律展開公式 ， 最后合并相同的極大項 。 36 五、主析取范式與主合取范式的關(guān)系 我們今后可用 ∑表示 極小項的析取 ， ∑i,j,k 即表示 mi∨ mj∨ mk 可用 ∏表示大項的合取 ， ∏i,j,k即表示Mi∧ Mj∧ Mk 例如： ? (p∧ q∧ r)∨( p∧ 172。q∧ r)∨( p∧ 172。q∧ 172。r)∨( 172。p∧ q∧ r)∨( 172。p∧ 172。q∧ r) ?m111∨ m101∨ m100∨ m011∨ m001?∑1， 3， 4， 5， 7 ? (p∨q∨r)∧(p∨ 172。q∨r)∧( 172。p∨ 172。q∨r) ?M000∧ M010∧ M110 ?∏0， 2， 6 37 五、主析取范式與主合取范式的關(guān)系 可以證明如果命題公式 P的主析取范式為 ∑i1,i2,… ik ， 則 P的主合取范式為： ∏0,1,2,… i11,i1+1,… ik1,ik+1, … ,2n1 例： (P→Q)→Q ? ∑1， 3， 4， 5， 7?∏0， 2， 6 38 內(nèi)容小結(jié) 對偶式與對偶原理 析取范式與合取范式 主析取范式 主合取范式 主析取范式與主合取范式的關(guān)系 39 課后作業(yè) P39 （ 4） a,c,e,f (可用真值表法或等值演算法 )
電大資料相關(guān)推薦
鄂ICP備17016276號-1