離散數(shù)學(xué)17對偶與范式(編輯修改稿)
2025-02-12 20:09 本頁面
【文章內(nèi)容簡介】 (吸收律 ， 析取范式 ) ?P∨ (172。P∧ 172。P∧ 172。Q) (交換律 ) ?P∨ (172。P∧ 172。Q) (冪等律 ， 析取范式 ) *由此例可以看出 ， 命題公式的析取范式也不惟一 。 16 三、主析取范式 上述范式不唯一 ， 下面追求一種更嚴(yán)格的范式 主范式 ， 它是存在且唯一的 。 定義 n個(gè)命題變元的合取式 ， 稱作 布爾合取、小項(xiàng)或極小項(xiàng) 。 其中每個(gè)變元與它的否定不能同時(shí)存在 ，但兩者 必須出現(xiàn)且僅出現(xiàn)一次 。 如： P， Q的構(gòu)成的極小項(xiàng)為： P∧Q ， P∧ 172。Q， 172。P∧Q ， 172。P∧ 172。Q 練習(xí)：寫出三個(gè)命題變元 P、 Q、 R構(gòu)成的極小項(xiàng) 。 17 三、主析取范式 由于每個(gè)命題變項(xiàng)在極小項(xiàng)中以原形或否定式形式出現(xiàn)且僅出現(xiàn)一次，因而 n個(gè)命題變項(xiàng) 共可產(chǎn)生2n個(gè)不同的極小項(xiàng)。 其中沒有兩個(gè)極小項(xiàng)是相等價(jià)的， 每個(gè)極小項(xiàng)都有且僅有一個(gè)成真指派 。以成真指派所對應(yīng)的二進(jìn)制數(shù) ， 就可將所對應(yīng) 極小項(xiàng)記作 mi,（ 其中 i為相應(yīng)的二進(jìn)制符號串） 。 18 三、主析取范式 兩個(gè)命題變元的真值表、極小項(xiàng)、成真賦值 和符號標(biāo)記如下： 真值表 P Q P∧ Q P∧ 172。Q 172。P∧ Q 172。P∧ 172。Q 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 兩個(gè)命題變元的極小項(xiàng) 極小項(xiàng) 成真賦值 記作 172。P∧ 172。Q 00 m00 172。P∧ Q 01 m01 P∧ 172。Q 10 m10 P∧ Q 11 m11 19 三、主析取范式 *可以看出，極小項(xiàng)與成真賦值的對應(yīng)關(guān)系為：變元對應(yīng) 1，而變元的否定對應(yīng) 0。 三個(gè)命題變元的極小項(xiàng) 極小項(xiàng) 成真賦值 記作 172。P∧ 172。Q∧ 172。R 000 m000 172。P∧ 172。Q∧ R 001 m001 172。P∧ Q∧ 172。R 010 m010 172。P∧ Q∧ R 011 m011 P∧ 172。Q∧ 172。R 100 m100 P∧ 172。Q∧ R 101 m101 P∧ Q∧ 172。R 110 m110 P∧ Q∧ R 111 m111 20 三、主析取范式 極小項(xiàng)有如下幾個(gè)性質(zhì)： ? （ 1）每一個(gè)極小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為 1，其它 2n1指派情況下均為 0。 ? （ 2） 任意兩個(gè)不同極小項(xiàng)的合取式永假。 例如： m001∧ m100 ?(172。P∧ 172。Q∧ R)∧ (P∧ 172。Q∧ 172。R) ?172。P∧ 172。Q∧ R∧ P∧ 172。Q∧ 172。R?0 ? （ 3）全體小項(xiàng)的析取式永為真。記為： Tmmmm nnii ??????? ???? 121201021 三、主析取范式 定義 對于給定的命題公式，如果有一個(gè)它的等價(jià)公式，僅由 極小項(xiàng)的析取 所組成，稱該公式為原公式的 主析取范式 。 定理 在真值表中，一個(gè)公式的真值為 T 的指派所對應(yīng)的極小項(xiàng)的析取 ，即為此公式的主析取范式。 定理 P34 22 三、主析取范式 由定理 主析取范式的步驟如下： ? （ 1）構(gòu)造命題公式的真值表。 ? （ 2）找出公式的成真賦值對應(yīng)的極小項(xiàng)。 ? （ 3）這些極小項(xiàng)的析取就是此公式的主析取范式。 例 用真值表法，求 (P→Q)→R的主析取范式。 23 三、主析取范式 解： 1.(P→Q)→R的真值表如下： ： 172。P∧ 172。Q∧ R(成真賦值為001)、 172。P∧ Q∧ R(成真賦值為 011)、 P∧ 1
電大資料相關(guān)推薦
鄂ICP備17016276號-1