離散數(shù)學(xué)(對偶和范式)-wenkub.com
2025-08-02 10:08 本頁面
【正文】 例如， (p?q)?q?m1?m3，則(p?q)?q?M0?M2。 (4) 用同一律補進(jìn)簡單合取式中未出現(xiàn)的所有命題變元，如 q，則 p?p∧ （ ?q∨ q)，并用分配律展開之，將相同的簡單合取式的多次出現(xiàn)化為一次出現(xiàn)， 這樣得到了給定公式的主析取范式。 ? (b) 任何兩個不同大項之析取是永真的 ， 即Mi∨ Mj?Ｔ ， i≠j。（ 將 n個命題變元排序，并且把命題變元與０對應(yīng)，命題變元的否定與１對應(yīng)，則可對 2n個大項按二進(jìn)制數(shù)編碼 ） mi(Mi)稱為極小項 (極大項 )的名稱 . mi與 Mi的關(guān)系 : ?mi ? Mi , ?Mi ? mi 16 極小項與極大項 (續(xù) ) 由 p, q兩個命題變項形成的極小項與極大項 公式 成真賦值 名稱 公式 成假賦值 名稱 ?p ? ?q ?p ? q p ? ?q p ? q 0 0 0 1 1 0 1 1 m0 m1 m2 m3 p ? q p ? ?q ?p ? q ?p ? ?q 0 0 0 1 1 0 1 1 M0 M1 M2 M3 極小項 極大項 17 由 p, q, r三個命題變項形成的極小項與極大項 極小項 極大項 公式 成真 賦值 名稱 公式 成假 賦值 名稱 ?p ??q ??r ?p ??q ? r ?p ? q ??r ?p ? q ? r p ??q ? ?r p ??q ? r p ?q ??r p ?q ? r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 m0 m1 m2 m3 m4 m5 m6 m7 p ? q ? r p ? q ??r p ? ?q ? r p ? ?q ??r ?p ? q ? r ?p ? q ??r ?p ? ?q ? r ?p ? ?q ??r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 M0 M1 M2 M3 M4 M5 M6 M7 小項的性質(zhì)： ? (a) 沒有兩個小項是等價的 ， 即是說各小項的真值表都是不同的； ? (b)任意兩個不同的小項的合取式是永假的：mi∧ mj?Ｆ ， i≠j。 8 析取范式與合取范式 簡單析取式 :有限個文字構(gòu)成的析取式 如 p, ?q, p??q, p?q?r, … 簡單合取式 :有限個文字構(gòu)成的合取式 如 p, ?q, p??q, p?q?r, … 析取范式 :由有限個簡單合取式組成的析取式 A1?A2??? Ar, 其中 A1,A2,? ,Ar是 簡單合取式 合取范式 :由有限個簡單析取式組成的合取式 A1?A2??? Ar , 其中 A1,A2,? ,Ar是 簡單析取式 9 析取范式與合取范式 (續(xù) ) 范式 :析取范式與合取范式的總稱 公式 A的析取范式 : 與 A等值的析取范式 公式 A的合取范式 : 與 A等值的合取范式 說明： 單個文字既是簡單析取式 ， 又是簡單合取式 形如 p??q?r, ?p?q??r 的公式既是析取范式
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1