- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
论域也称为个体域，其中的元素称为个体。论域是 变元的取值范围，它规定了全称量词的意义。 解释规定了常元、函数符号、谓词符号的具体意义， 但并没有为变元规定具体的值。变元的取值由赋值 规定。 在解释中，并不要求不同的常元解释为不同的个体， 在解释中 并不要求不同的常元解释为不同的个体 不要求不同的函数符号解释为不同的运算，也不要 求不同的谓词符号解释为不同的谓词。 一个解释是由四部分构成的，即使两个解释的论域 相同，而对常元、函数符号、谓词符号的解释不完 全相同，也不能认为它们是同样的解释。
⎧ d1 ⎪ ⎪ M v [ x1 / d1 ,L, x n / d n ]( y ) = ⎨ ⎪ dn ⎪v( y ) ⎩
若 y 是 x1 M 若 y 是 xn 否则
1
解释和赋值共同规定了项和公式的意义。 给定一个解释 I 以后，还不能确定项 t 指哪个个体， 因为 t 中变元的值还没有确定。一旦变元的值确定 后， t 指哪个个体就唯一确定了。因此，可以将 t 在 解释 I 下的意义 I(t) 看做从赋值集合到论域 DI 的函 数，一旦给定了赋值 v，所指的个体就唯一确定了， 即函数 I(t) 在自变量 v 处的值 I(t)( ) 同样 给定 I(t)(v)。同样，给定一 个解释 I 以后，还不能确定公式 A 指哪个命题，因 为 A 中自由变元的值还没有确定。因此，可以将 A 在解释 I 下的意义 I(A) 看做从赋值集合到真值集合 {0, 1} 的函数，一旦给定了赋值 v，所指的命题的真 值就唯一确定了，即函数 I(A) 在自变量 v 处的值 I(A)(v)。
2
I (P( f (x), y) → Q(x))(v[x/e]) = I (P( f (x), y))(v[x/e]) → I(Q(x))(v[x/e]) = = PI(I(f (x))(v[x/e]), I(y)(v[x/e])) → v(y)) → QI(e) QI(e) PI(f I(e),
第二章 谓词逻辑
§2.1 §2.2 §2.3 §2.4 §2.5 §2.6 作业 谓词和量词 项和公式 解释和赋值 永真式 等值演算 逻辑推论
§2.3 解释和赋值
定义2.11 一个解释 I 由以下四部分组成。 1. 指定一个非空集合 DI ，称为 I 的论域。 2. 对于每个常元 a 指定 DI 中一个元素 aI 。 中 个元素 3. 对于每个 n 元函数符号 f ，指定 DI 上的一个 n 元运算 f I 。 4. 对于每个 n 元谓词符号 P ，指定 DI 上的一个 n 元谓词 PI 。
⎧1 若有 d ∈ DI 使得 I ( A)(v[ x / d ]) = 1 I (∃xA)(v) = ⎨ ⎩0 若对于每个 d ∈ DI , I ( A)(v[ x / d ]) = 0
证明 1. A ∨ B 只是 ¬A→ B 的缩写， I(A ∨ B)(v) 即为 I(¬A→ B)(v)。 I(¬A→ B)(v) = ¬I(A)(v) → I(B)(v) I(A)(v) 和 I(B)(v) 都是命题，由第一章知道， 第 ¬I(A)(v) → I(B)(v) = I(A)(v) ∨ I(B)(v) 2，3，4 可同样证明。
假设程序中的变元（量）都是简单变量，并且取值 范围都是论域，则一个赋值即是某时刻变量取值的 状态。如果赋值语句 (x1,…, xn ) := (d1,…, dn ) 执行 前的状态是 v ，则该赋值语句执行后的状态就是 [ , , v [x1 /d1,…, xn /dn ] 。 例如，设解释 I 的论域 DI 是自然数集， I 中的赋值 v 使得 v(xi) = i， i = 1, 2, …。那么， v [x2 /0, x3 /0](x2) = 0，v [x2 /0, x3 /0](x3) = 0， v [x2 /0, x3 /0](xi) = i， i = 1, 4, 5 …。
= PI(d, e) → QI(e) =0→0 =1 因此， I (∀x(P( f (x), y) → Q (x)))(v) = 1。
I (P( f (x), y) → Q(x))(v1[x/e]) = I (P( f (x), y))(v1[x/e]) → I(Q(x))(v1[x/e]) = PI(I(f (x))(v1[x/e]), I(y)(v1[x/e])) → QI(e) = PI(f I(e), v1(y)) → QI(e) = PI(d, d ) → QI(e) =1→0 =0 因此， I (∀x(P( f (x), y) → Q(x)))(v1) = 0。
在本书中，每个二元谓词符号可以解释为论域上的 任何二元谓词，这样的谓词逻辑称为不带等词的谓 词逻辑。 如果有一个二元谓词符号固定解释为论域上的恒等 谓词，也就是说，论域指定以后，这个二元谓词符 号的意义就唯一确定了，则称这样的谓词逻辑为带 等词的谓词逻辑。我们只讨论不带等词的谓词逻辑。 等 等
定义2.12 从所有变元组成的集合到解释 I 的论域 DI 的函数称为 I 中的赋值。 设 v 是解释 I 中的赋值，x1,…, xn 是不同变元， d1,…, dn 是 DI 中元素，则赋值 v [x1 /d1,…, xn /dn ] 将d1,…, dn 分别赋予变元 x1,…, xn ，而对其它变元 的赋值与 v 赋予该变元的值相同，即
定义2.14 设 v 是解释 I 中的赋值，公式 A 在解释 I 和赋值 v 下的意义 I(A)(v) 定义如下： 1. 若 A 是 P (t1,…, tn)，其中 P 是 n 元谓词符号， t1,…, tn 是项，则 I(A)(v) = PI (I(t1)(v),…, I(tn)(v)) 2. 若 A 是 ¬B，其中 B 是公式，则 I(A)(v) I(A)( ) = ¬I(B)(v) 。 I(B)( ) 3. 若 A 是 B → C，其中 B, C 是公式，则 I(A)(v) = I(B)(v) → I(C)(v) 4. 若 A 是∀xB，其中 B 是公式，x 是变元，则
I (P( f (x), y) → Q(x))(v[x/d ]) = I (P( f (x), y))(v[x/d ]) → I(Q(x))(v[x/d ]) = PI(I(f (x))(v[x/d ]), I(y)(v[x/d ])) → QI(d ) = PI(f I(d ), v(y)) → QI(d ) = PI(e, e) → QI(d ) =1→1 =1
定理2.1 设 v 是解释 I 中的赋值， A 和 B 是公式。 1. I(A ∨ B)(v) = I(A)(v) ∨ I(B)(v) 2. I(A ∧ B)(v) = I(A)(v) ∧ I(B)(v) 3. I(A ↔ B)(v) = I(A)(v) ↔ I(B)(v) 4. I(A ⊕ B)(v) = I(A)(v) ⊕ I(B)(v) 5.
例2.12 给定解释 I 如下：论域 DI 为自然数集， f I 为乘法 × ， g I 为加法 + ， aI = 2。 I 中赋值 v 使得 v(x) = 1 。 I(f (g(a, x), a))(v) = f I (I(g(a, x))(v) , I(a)(v)) = f I (gI(I(a)(v), I(x)(v)) , I(a)(v)) = f I (gI(aI, v(x)) , aI ) = × (+ (2, 1), 2) = (2 + 1) × 2 =6
定义2.13 设 v 是解释 I 中的赋值，项 t 在解释 I 和 赋值 v 下的意义 I(t)(v) 定义如下： 1. 若 t 是变元 x，则 I(t)(v) = v(x)。 2. 若 t 是常元 a，则 I(t)(v) = aI 。 3. 若 t 是 f (t1,…, tn)，其中 f 是 n 元函数符号， t1,…, tn 是项，则 I(t)(v) = f I (I(t1)(v),…, I(tn)(v)) 定义2.13 递归地定义了从赋值集到 DI 的函数 I(t)， 首先对于 t 是变元或常元的简单情况定义函数 I(t)，然后将复杂情况归结到简单情况。变元的值 由赋值指定，常元的值由解释指定。可以归纳证 明，对于每个项 t， I(t)(v) 是论域 DI 中的元素。
∨, ∧, ↔, ⊕, ∃ 不是语言的原始符号，如 A ∨ B 只是 ¬A→ B 的缩写，I(A ∨ B)(v) 已有意义。 ¬, →, ∀ 是 语言的原始符号，I(A → B)(v) 等必须由定义指 定。
3
5. ∃xA 只是 ¬∀x¬A 的缩写。 若有 d∈DI 使得 I(A)(v[x/d ]) = 1，则有 d∈DI 使 得 I(¬A)(v[x/d ]) = 0，I(∀x¬A)(v) = 0，因而 I(¬∀x¬A)(v) = 1。 ( )( [ 若对于每个 d∈DI ， I(A)(v[x/d ]) = 0，则对于每 个 d∈DI ， I(¬A)(v[x/d ]) = 1 ，I(∀x¬A)(v) = 1， 因而 I(¬∀x¬A)(v) = 0。
从这个例子可以看出，自由变元的值是由赋值指定 的，赋值并不为约束变元指定值。另外，如果赋值 不同，一个公式在同一个解释下的意义可以不同。 命题符号化实际上是要求寻找一个解释和一个语 句，使得将该语句解释为要符号化的命题。因此， 句 使得将该语句解释为要符号化的命题 因此 命题符号化需提供一个解释和一个语句，并且二者 之间必须满足条件：该语句在该解释下的意义必须 是要符号化的命题。
例2.14 设 P 是二元谓词符号，给定解释 I 如下： DI = {a, b}， PI(a, a) = PI(b, b) = 0， PI(a, b) = PI(b, a) = 1 任给 I 中赋值 v， I(∀x∃yP(x, y))(v) = I(∃yP(x, y))(v[x/a]) ∧ I(∃yP(x, y))(v[x/b]) = (I(P(x, y))(v[x/a][y/a]) ∨ I(P(x, y))(v[x/a][y/b])) ∧ (I(P(x, y))(v[x/b][y/a]) ∨ I(P(x, y))(v[x/b][y/b])) = (PI(a, a) ∨ PI(a, b)) ∧ (PI(b, a) ∨ PI(b, b)) = (0 ∨ 1) ∧ (1 ∨ 0) = 1
