第1节一阶语言的结构 第5章一阶语言的结构和真值理论 最后相信大家不会把(Q,s)}φ(还有后面马上定义的φ)和r卡φ搞混,虽 然都用了卡这个符号。有的教科书(例如安德顿[?])也会把(,s)}φ记作卡]并 且把卡φ记作 定理51.假定s1和s2为两个从V到||的赋值函数,并且它们在公式φ中所有自由出 现的变元上取值相同。则(,s)=p当且仅当(,s2)}g。 证明:固定结构。我们对公式φ施行归纳。假定赋值函数s1和s2在公式y中所有自由 出现的变元上取值相同。首先我们有 情形1:φ是一个原子公式Pt2…tn或t1≈t2。首先我们有对任意i≥1, 51(t1)=32(t1)。详细证明需要对项t施行归纳并要用到对赋值s1和s2的假设,我们 留给读者。因此(,s1)Pt1t2…tn当且仅当(1(t1),1(t2),…,31(tn)∈P当且仅当 (2(t1),52(t2),…,52(t1))∈P当且仅当(a,s2)Pt1t2…tn。当φ为t1≈t2时证明与此 类似 情形2和3:φ分别具有形式和a→β。我们把验证留给读者 情形4:φ具有形式xv。在此情形下在v中自由出现的变元至多是x加上在φ中自 由出现的变元。所以对任何的d∈|,诱导出的赋值函数(s1)和(s2)在中所有自由 出现的变元上取值相同。根据归纳假定和(s1)a满足ψ当且仅当和(s2)满足ψ。所 以%和s1满足φ当且仅当%和s2满足φ 推论51.对任何闭语句σ,或者 a)对所有函数s:V→,都有(al,s)}=σ;或者 b)对所有函数s:v→都有(,s)kσ 当情形(a)成立时,我们就称σ在以中为真,记作}σ;也经常使用下列短语:σ 在中成立;满足σ和α是σ的一个模型 推论5说明对闭语句来说,赋值函数是不重要的。类似地,如果公式y中仅有 个自由变元ω1,则对赋值函数来说,重要的只有它在n上的赋值。 例52.给定一阶语言L包含一个二元谓词符号P,一元函数符号f和一个常数符号c,考 察它的如下结构: (N,≤,S,0) 令s:V→N使得s(v) 即s(n1)=0,s(2)=1等等。什么是(fn3)?还有 s(fc)?结构w和赋值s满足下列公式吗? () Pcfa第 1 节 一阶语言的结构 第 5 章 一阶语言的结构和真值理论 最后相信大家不会把 (A, s) |= φ （还有后面马上定义的 A |= φ）和 Γ |= φ 搞混，虽 然都用了 |= 这个符号。有的教科书（例如安德顿 [?]）也会把 (A, s) |= φ 记作 |=A φ[s] 并 且把 A |= φ 记作 |=A φ。 定理 5.1. 假定 s1 和 s2 为两个从 V 到 | A | 的赋值函数，并且它们在公式 φ 中所有自由出 现的变元上取值相同。则 (A, s1) |= φ 当且仅当 (A, s2) |= φ。 证明: 固定结构 A。我们对公式 φ 施行归纳。假定赋值函数 s1 和 s2 在公式 φ 中所有自由 出现的变元上取值相同。首先我们有 情形 1：φ 是一个原子公式 P t1t2 · · ·tn 或 t1 ≈ t2。首先我们有对任意 i ≥ 1， s1(ti) = s2(ti)。详细证明需要对项 t 施行归纳并要用到对赋值 s1 和 s2 的假设，我们 留给读者。因此 (A, s1) |= P t1t2 · · ·tn 当且仅当 (s1(t1), s1(t2), · · · , s1(tn)) ∈ P A 当且仅当 (s2(t1), s2(t2), · · · , s2(tn)) ∈ P A 当且仅当 (A, s2) |= P t1t2 · · ·tn。当 φ 为 t1 ≈ t2 时证明与此 类似。 情形 2 和 3：φ 分别具有形式 ¬α 和 α → β。我们把验证留给读者。 情形 4：φ 具有形式 ∀xψ。在此情形下在 ψ 中自由出现的变元至多是 x 加上在 φ 中自 由出现的变元。所以对任何的 d ∈| A |，诱导出的赋值函数 (s1) x d 和 (s2) x d 在 ψ 中所有自由 出现的变元上取值相同。根据归纳假定 A 和 (s1) x d 满足 ψ 当且仅当 A 和 (s2) x d 满足 ψ。所 以 A 和 s1 满足 φ 当且仅当 A 和 s2 满足 φ。 推论 5.1. 对任何闭语句 σ，或者 (a) 对所有函数 s : V →| A |, 都有 (A, s) |= σ；或者 (b) 对所有函数 s : V →| A |, 都有 (A, s) ̸|= σ。 当情形 (a) 成立时，我们就称σ 在 A 中为真，记作 A |= σ；也经常使用下列短语：σ 在 A 中成立；A 满足 σ 和A 是 σ 的一个模型 。 推论 5.1 说明对闭语句来说，赋值函数是不重要的。类似地，如果公式 φ 中仅有一 个自由变元 v1，则对赋值函数来说，重要的只有它在 v1 上的赋值。 例 5.2. 给定一阶语言 L 包含一个二元谓词符号 P，一元函数符号 f 和一个常数符号 c，考 察它的如下结构： A = (N, ≤, S, 0)。 令 s : V → N 使得 s(vi) = i − 1，即 s(v1) = 0, s(v2) = 1 等等。什么是 s(ffv3)？还有 s(ff c)？结构 A 和赋值 s 满足下列公式吗？ (1) P cfv1； 4