习题61. (1)(a)令为一个结构并且s:V→|为一个给变元的赋值。由此诱导出一个真值 指派v定义在素公式(所形成的命题符号)上 v(a)=T当且仅当(2,s)}ao 证明对任意公式a(不一定为素公式)都有 (a)=T当且仅当(a,s)ao (b)由(a)导出:如果φ是第一组公理中的公式(事实上,对任何一阶意义下的重 言式φ),则}φ。[这是可靠性定理证明的一部分。 习题62. (1)证明引理??。 (2)令Δ为我们前面选定了一阶逻辑的公理集。我们下面对A进行一些改动,看看它对 语法和语义有什么影响。 (a)假如我们向A添加一个非普遍有效的公式v,证明可靠性定理不再成立 (b)假如我们走向另一个极端,令A=⑩,即没有任何的逻辑公理。证明完全性定 理不再成立 (c)假如我们向A添加一个新的普遍有效公式v,证明此时可靠性定理和完全性定 理都依然成立。 (3)(本练习讨论存在量词例化规则的两种形式,请不要用可靠性和完全性定理。 (a)规则的语法形式:假定常数符号c在公式φ,,和公式集r中都不出现,并 且rU{y}v。则ru{ryp}vo (b)规则的语义形式:假定常数符号c在公式φ,v,和公式集r中都不出现,并 且rU{ya}Fv。则rU{Bry}v。 习题6.3 (1)证明自然推演系统的可靠性 (2)证明自然推演系统的子公式性质:如果}r,则存在一个证明树,其中出现的公式 都是r的子公式
习题 6.1. (1) (a) 令 A 为一个结构并且 s : V →| A | 为一个给变元的赋值。由此诱导出一个真值 指派 v 定义在素公式（所形成的命题符号）上： v(α) = T 当且仅当 (A, s) |= α。 证明对任意公式 α （不一定为素公式）都有： v¯(α) = T 当且仅当 (A, s) |= α。 (b) 由 (a) 导出：如果 φ 是第一组公理中的公式（事实上，对任何一阶意义下的重 言式 φ），则 |= φ。[这是可靠性定理证明的一部分。] 习题 6.2. (1) 证明引理 ??。 (2) 令 Λ 为我们前面选定了一阶逻辑的公理集。我们下面对 Λ 进行一些改动，看看它对 语法和语义有什么影响。 (a) 假如我们向 Λ 添加一个非普遍有效的公式 ψ，证明可靠性定理不再成立。 (b) 假如我们走向另一个极端，令 Λ = ∅，即没有任何的逻辑公理。证明完全性定 理不再成立。 (c) 假如我们向 Λ 添加一个新的普遍有效公式 ψ，证明此时可靠性定理和完全性定 理都依然成立。 (3) （本练习讨论存在量词例化规则的两种形式，请不要用可靠性和完全性定理。） (a) 规则的语法形式：假定常数符号 c 在公式 φ，ψ，和公式集 Γ 中都不出现，并 且 Γ ∪ {φ x c } ⊢ ψ。则 Γ ∪ {∃xφ} ⊢ ψ。 (b) 规则的语义形式：假定常数符号 c 在公式 φ，ψ，和公式集 Γ 中都不出现，并 且 Γ ∪ {φ x c } |= ψ。则 Γ ∪ {∃xφ} |= ψ。 习题 6.3. (1) 证明自然推演系统的可靠性。 (2) 证明自然推演系统的子公式性质：如果 ⊢ Γ，则存在一个证明树，其中出现的公式 都是 Γ 的子公式。 1
习题6.4 (1)证明紧致性定理 (2)证明引理? (3)假定闭语句σ在r的所有无穷模型中都成立。证明:存在一个自然数k使得σ在r 的所有多于k个元素的模型中都成立。 (4)假定语言中有一个二元谓词符号<。令结构%=(N,<)为自然数集和其上的通常的 序。证明存在一个与α初等等价的模型使得<有一个无穷降链,即,存在|9 中的元素ao,a1,…使得对任意自然数,(a1+1,a)∈<。[注:本题可以解读成:良 序不是一个一阶的概念 (5)考察一阶逻辑可靠性和完全性的下列弱形式:a当且仅当}a。利用紧致性定理, 从上述弱形式推导出一阶逻辑可靠性和完全性的一般形式
习题 6.4. (1) 证明紧致性定理。 (2) 证明引理 ??。 (3) 假定闭语句 σ 在 Γ 的所有无穷模型中都成立。证明：存在一个自然数 k 使得 σ 在 Γ 的所有多于 k 个元素的模型中都成立。 (4) 假定语言中有一个二元谓词符号 <。令结构 A = (N, <) 为自然数集和其上的通常的 序。证明存在一个与 A 初等等价的模型 B 使得 <B 有一个无穷降链，即，存在 | B | 中的元素 a0, a1, · · · 使得对任意自然数 i，(ai+1, ai) ∈<B。[注：本题可以解读成：良 序不是一个一阶的概念。] (5) 考察一阶逻辑可靠性和完全性的下列弱形式：⊢ α 当且仅当 |= α。利用紧致性定理， 从上述弱形式推导出一阶逻辑可靠性和完全性的一般形式。 2