離散數(shù)學(xué)17對(duì)偶與范式-資料下載頁(yè)
2025-01-16 20:09本頁(yè)面
【正文】 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 四、主合取范式 極大項(xiàng)有如下幾個(gè)性質(zhì)： ? （ 1）每一個(gè)極大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為 0，其它 2n1指派情況下均為 1。 ? （ 2） 任意兩個(gè)不同的極大項(xiàng)的析取式為永真式。 ? （ 3） 全體極大項(xiàng)的合取式為永假式。記為： ???120niiM?M0∧ M1∧ ? ∧ ?0 32 四、主合取范式 定義 對(duì)于給定的命題公式，如果有一個(gè)它的等價(jià)公式， 僅由極大項(xiàng)的合取 組成，則該等價(jià)式稱(chēng)為原公式的 主合取范式 。 定理 在真值表中，一個(gè)公式的真值為 F 的指派所對(duì)應(yīng)的極大項(xiàng)的合取，即為此公式的主合取范式。 33 四、主合取范式 由定理 主析取范式的步驟如下： ? （ 1）構(gòu)造命題公式的真值表。 ? （ 2）找出公式的成假賦值對(duì)應(yīng)的極大項(xiàng)。 ? （ 3）這些極大項(xiàng)的合取就是此公式的主合取范式。 例 用真值表法，求 (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 四、主合取范式 與求主析取范式相似，除了用真值表方法外，也可利用 等值演算法 求得給定命題公式的主合取范式。 其演算步驟如下： ① 化歸為合取范式 。 ② 除去所有永真的合取項(xiàng) 。 ③ 在合取式中合并重復(fù)出現(xiàn)的析取項(xiàng)和相同的變?cè)?。 ④ 對(duì)析取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)?。 即 增加∨ (P∧ 172。 P)， 然后 ， 應(yīng)用分配律展開(kāi)公式 ， 最后合并相同的極大項(xiàng) 。 36 五、主析取范式與主合取范式的關(guān)系 我們今后可用 ∑表示 極小項(xiàng)的析取 ， ∑i,j,k 即表示 mi∨ mj∨ mk 可用 ∏表示大項(xiàng)的合取 ， ∏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é) 對(duì)偶式與對(duì)偶原理 析取范式與合取范式 主析取范式 主合取范式 主析取范式與主合取范式的關(guān)系 39 課后作業(yè) P39 （ 4） a,c,e,f (可用真值表法或等值演算法 )
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1