离散数学：第一章第7节 逻辑推论201009final [兼容模式].pdfVIP

第一章命题逻辑 §1.7 逻辑推论 §1.1 命题和联结词 定义1.20 若真值赋值v 满足公式集Γ 中的每个公 §1.2 公式和真值赋值 式，则称v 满足Γ 。若有真值赋值满足Γ ，则称 §1.3 等值演算 Γ是可满足的，否则称Γ是不可满足的。 有有限公式集式集{A , …, A } 是可满满足的的当且仅当公 §1.4 对偶定理 1 n 式A 1 ∧…∧An 是可满足式。因此，判断一个有限 §1.5 联结词的完全集 公式集的不可满足性可归结为判断公式的永假性。 §1.6 范式 任何真值赋值v 都满足空集∅ 。 §1.7 逻辑推论 对于每个公式A ，若A ∈∅，则v(A) = 1 。 例 判断以下公式集是否可满足。 例 判断以下公式集是否可满足。 {p →(¬(s ∧r) →¬q), ¬s ∧p , q} {p ∨q →r, r →s , ¬s } 解 设v 是真值赋值。若v(q) = v(¬s ∧p ) = 1 ，则 解 若真值赋值v 满足该公式集，则 v(p ) = 1 且v(s) = 0 。因而，v(s ∧r) = 0 ，所以， v(p ∨q →r) = v(r →s) = v(¬s) = 1 v(p →(¬(s ∧r) →¬q)) = 0 因而因而vv((ss)) == 00，vv((rr)) == 00，vv((pp ∨∨qq)) == 00 。 这表明不存在使得p →(¬(s ∧r) →¬q), ¬s ∧p , q 所以，只要令v = (p /0, q/0, r/0, s/0) ，v 就满足该公 这三个公式同时为真的真值赋值。因此， 式集。这表明公式集 {p →(¬(s ∧r) →¬q), ¬s ∧p , q} {p ∨q →r, r →s , ¬s } 是不可满足的。 是可满足的。 例 判断公式集 {p ∧q →r, p ∨q →¬r }是否可满足。 要说明公式集Γ不可满足，需要证明每个真值赋 p q r p q r p q r ∧ → ∨ →¬ 0 0 0 1 1 值都使得Γ 中至少一个公式为假。 0 0 1 1 1