离散数学：第二章 第六节 逻辑推论 [兼容模式].pdfVIP

第二章谓词逻辑 §2.6 逻辑推论 §2.1 谓词和量词 定义2.19 若解释I 和I 中赋值v 满足公式集Γ 中每 §2.2 项和公式 个公式，则称I 和v 满足Γ。若有解释I 和I 中赋 §2.3 解释和赋值 值v 满足Γ，则称Γ为可满足的。否则称Γ为不可 §2.4 永真式 满足的满足的。 §2.5 等值演算 定理2.6 有穷非空公式集 {A ,…, A } 是可满足的 1 n §2.6 逻辑推论 当且仅当A 1 ∧…∧An 是可满足式。 作业 判断一个有限公式集的可满足性可归结为判断公式 的永假性。 例如，{P(x), ¬P(y )}是可满足的，可取满足它的解 例 语句集 释I 和I 中赋值v 如下： {∀x ¬P(x , x), P(a, b), P(a, c), P(b, c)} I DI 为自然数集，P (x) = 1 当且仅当x 是奇数， 是否可满足？若可满足，满足它的解释应当满足什 v(x) = 1 ，v(y ) = 2 。 么条件？ 也可取满足它的解释I ′和I ′中赋值v ′如下： 解 若解释I 满足该语句集，则 I ′ I ′ I I I I I I I I I DI ′= {1, 2} ，P (1) = 1，P (2) = 0， P (a , b ) = P (a , c ) = P (b , c ) = 1 I I I I v ′(x) = 1 ，v ′(y ) = 2 。 并且对于每个d ∈DI ，P (d, d ) = 0 。因此，a , b , c 解释I 和I 中赋值v 满足 {P(x), ¬P(y )} 当且仅当 应当是DI 中