x本科數理邏輯-命題3-(留存版)

　　

【正文】 表中真值 為真 的 相應賦值所對應的極小項 進行析取 主合取范式 1）極大項 ：在含有 n個命題變項的 簡單析取式 中，若每個命題變項和它的否定式不同時出現，而二者之一必出現且僅出現一次，稱這樣的簡單析取式極大項。 稱 B是前提集合 {A1， A2， A3， … ， Am}的 有效結論 。 這種論證稱為有效的論證。 2）極大項與所含變元的個數有關 三個變元的所有極大項為： p∨q∨r 、 p∨q∨┑r 、 p∨┑q∨r 、 p∨┑q∨┑r 、 M0(0,0,0)、 M1(0,0,1)、 M2(0,1,0)、 M3(0,1,1) 、 ┑ p∨q∨r 、 ┑ p∨q∨┑r 、 ┑ p∨┑q∨r 、 ┑ p∨┑q∨┑r M4(1,0,0)、 M5(1,0,1)、 M6(1,1,0)、 M7(1,1,1) 3） n個變元的所有極大項共有 2n 4）主合取范式 設由 n個命題變項構成的合取范式中所有的 簡單合取式都是極大項 ，則稱該合取范式為主合取范式。 記為 :｛ A1， A2， A3， … ， Am｝ ╞ B 即： A1∧A 2∧ … ∧A m = B 注： 1）由前提集合 A1， A2， A3， … ， Am 推出 B的推理是否是有效的與前提集合各命題公式的次序無關。 不管各 前提的真值如何（由符號組成的 ），從前提的集合出發， 依據公認的邏輯規則 推導出來的 任何結論 ，都稱為 有效的結論。 例 ( p → q) ? r ? (p ∨ r) ∧ (┐ q ∨ r) ∧ (┐ p ∨ q ∨ ┐ r) ? (p ∨ q ∨ r) ∧ (p ∨ ┐ q ∨ r) ∧ (┐p ∨ ┐ q ∨ r) ∧ (┐p ∨ q ∨ ┐ r) 該公式的真值表 注：該式的極大項所對應的賦值均為該公式的成假賦值， 也是該公式的全部成假賦值（ 可從真值表得出） 主合取范式的確定方法： 1）等值演算法 a)先確定公式的合取范式 b)將簡單析取式化為極大項（通過不斷析取所缺變元的永假式） c)將相同極大項去掉 2）真值表法 列出公式的真值表 將真值表中真值為假的相應賦值所對應的極大項進行合取 3）利用主析取范式與主合取范式的關系 若已知公式 A的主析取范式 首先寫出 ┑ A的主析取范式 (從全部極小項去掉 A式包含的極小項得到） 對 ┑ A的主析取范式取否定可得到 A的主合取范式 例：已知 A的主析取范式為 A ? (p ∨ q ) → r ? m0 ∨ m1 ∨ m3 ∨ m5 ∨ m7 從真值表更易看出 ┑ A ? m2 ∨ m4 ∨ m6 A ? ┑ （ ┑ A ） ? ┑ （ m2 ∨ m4 ∨ m6 ） 主合取范式－由極大項的合取構成 極大項的成假賦值 可以使公式的真值為假 故極大項的成假賦值即為 公式的成假賦值 公式的主合取范式中 極大項的個數 與其真值表中 賦值為假的 個數相同（且是全部成假賦值） 一個命題公式的主合取范式表示是存在唯一的 公式 (p→ q ) ∧ r ? (p∨ q∨ r) ∧ (p ∨ ┐q∨ r)∧ (┐p∨ q∨ r)∧ (┐p∨ q∨ ┐r )∧ (┐p∨ ┐q∨ r) ? M0 ∧ M2 ∧ M4 ∧ M5 ∧ M6 主合取范式 p q r (p→ q )∧r 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0