離散數學(對偶和范式)(編輯修改稿)
2024-09-01 10:08 本頁面
【文章內容簡介】 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 小項的性質： ? (a) 沒有兩個小項是等價的 ， 即是說各小項的真值表都是不同的； ? (b)任意兩個不同的小項的合取式是永假的：mi∧ mj?Ｆ ， i≠j。 ? (c)所有小項之析取為永真： mi?Ｔ 。 ? (d)每個小項只有一個解釋為真 ， 且其真值 1位于主對角線上 。 18 1ni??大項的性質： ? (a) 沒有兩個大項是等價的 。 ? (b) 任何兩個不同大項之析取是永真的 ， 即Mi∨ Mj?Ｔ ， i≠j。 ? (c) 所有大項之合取為永假 ， 即 Mi?Ｆ 。 ? (d) 每個大項只有一個解釋為假 ， 且其真值 0位于主對角線上 。 19 1ni??20 主析取范式與主合取范式 主析取范式 : 由極小項構成的析取范式 主合取范式 : 由極大項構成的合取范式 例如 ， n=3, 命題變項為 p, q, r時 ， (?p??q?r)?(?p?q?r) ? m1?m3 是 主析取范式 (p?q??r)?(?p?q??r) ? M1?M5 是 主合取范式 A的主析取范式 : 與 A等值的主析取范式 A的主合取范式 : 與 A等值的主合取范式 . 21 主析取范式與主合取范式 (續(xù) ) 定理 任何命題公式都存在著與之等值的主析取范 式和主合取范式 , 并且是惟一的 . 用等值演算法求公式的主范式的步驟： (1) 先求析取范式 （ 合取范式 ） (2) 將不是極小項 （ 極大項 ） 的簡單合取式 （ 簡 單析取式 ） 化成與之等值的若干個極小項的析 取 （ 極大項的合取 ） ， 需要利用同一律 （ 零 律 ） 、 排中律 （ 矛盾律 ） 、 分配律 、 冪等律等 . (3) 極小項（極大項）用名稱 mi（ Mi）表示，并 按角標從小到大順序排序 . 22 主析取范式與主合取范式 (續(xù) ) 用等值演算法求公式的主范式的步驟： (1) 先求析取范式 (2) 刪
環(huán)評公示相關推薦
鄂ICP備17016276號-1