习题3.1 (0)选择一阶逻辑语言,并将下列语句转换成一阶语句。你认为推理有错误吗?为什么? (a)如果存在存在着的鬼,则鬼存在。 (b)存在着的鬼当然存在。 (c)鬼存在。 (1)假定我们的一阶语言中有一元谓词符号N和1,分别用来表示“是一个数”和“好 玩的”;二元谓词符号<表示“小于”;还有常数符号0表示数字零。将下列中文语 句转换成该一阶语言的公式。你可能会得到不同的结果,因为语句可能会有歧义。 (a)零小于所有的数 (b)要是有数好玩的话,零就好玩。 (c)没有小于零的数 (d)要是一个不好玩的数满足所有比它小的数都好玩这条性质,则它本身也好玩 (e)不存在所有数都比它小的数 (f)不存在没有数不比它小的数 (2)沿用上题的一阶语言,将下列一阶语句转换成日常的中文。 vx(Nx→Ix→vy(Ny→Iy→<y) 注意:虽然我们无法定义“日常中文”但“对所有的x,如果Nx则..”绝对不属 于日常中文 (3)假定我们的一阶语言中有二元函数符号+和,分别用来表示“加法”和“乘法” 常数符号1,2,3,4分别表示数字 四。再假定变元都代表整数 (a)将下列一阶语言的公式转换成中文语句 x)[(m){x≈2.m+1→(n){x:x≈2.m+1]l (b)将下列中文语句转换成该一阶语言的公式:“没有形如4k+3的整数是平方 和 (4)(下面的练习严格说与本节没有关系,请大家当作数学练习来做。)
习题 3.1. (0) 选择一阶逻辑语言，并将下列语句转换成一阶语句。你认为推理有错误吗？为什么？ (a) 如果存在存在着的鬼，则鬼存在。 (b) 存在着的鬼当然存在。 (c) 鬼存在。 (1) 假定我们的一阶语言中有一元谓词符号 N 和 I，分别用来表示“是一个数”和“好 玩的”；二元谓词符号 < 表示“小于”；还有常数符号 0 表示数字零。将下列中文语 句转换成该一阶语言的公式。你可能会得到不同的结果，因为语句可能会有歧义。 (a) 零小于所有的数。 (b) 要是有数好玩的话，零就好玩。 (c) 没有小于零的数。 (d) 要是一个不好玩的数满足所有比它小的数都好玩这条性质，则它本身也好玩。 (e) 不存在所有数都比它小的数。 (f) 不存在没有数不比它小的数。 (2) 沿用上题的一阶语言，将下列一阶语句转换成日常的中文。 ∀x(Nx → Ix → ¬∀y(Ny → Iy → ¬x < y)). 注意：虽然我们无法定义“日常中文”但“对所有的 x, 如果 Nx 则 . . . ”绝对不属 于日常中文。 (3) 假定我们的一阶语言中有二元函数符号 + 和 ·，分别用来表示“加法”和“乘法”； 常数符号 1, 2, 3, 4 分别表示数字一、二、三、四。再假定变元都代表整数。 (a) 将下列一阶语言的公式转换成中文语句: (∀x)[(∃m)[x ≈ 2 · m + 1] → (∃n)[x · x ≈ 2 · n + 1]]。 (b) 将下列中文语句转换成该一阶语言的公式：“没有形如 4k + 3 的整数是平方 和”。 (4) （下面的练习严格说与本节没有关系，请大家当作数学练习来做。） 1
(a)在数学分析中,极限的定义如下:limf(x)=l当且仅当 ve∈R+)(6∈R+)Nx∈R)0<|x-a|<8→f(x)-l|k< 写出lmf(x)≠l的定义 (b)在线性代数中,我们说向量组,2,……,是线性相关的,如果 (1∈R)(32∈R)…(cn∈R)(不全为零)∧a1+c22+…+nEn=0 写出向量组1,2,…,n为线性无关的定义 习题4.1 (1)以下公式是公理吗?如果是,属于哪组公理? a)[(Px→vyPy)→P]→rPr→( Pz) (b)vyNr(Px→Pr)→(Pc→Pc) (c) rdy Pay→+彐yPyy (2)证明变元x在任何公式φ中都可以替换自己 (3)(本练习讨论公理的独立性。)证明:如果没有第二组替换公理,则其余的公理不能 证明r(x米x)→xx。提示:定义函数h:{公式}→{0,1}满足对所有的素公 式a,h(a)=1;然后将其自然地扩展到h(-a)和h(a→B)上。证明如果a为其余 公理的一个语法后承,则h(a)=1 习题42. (1)给出一个从空集M到Wryp→彐ry的一个推演。[注意:本题要求你给出推演序列, 不准使用任何元定理。] (2)假设有一个从公式集r到φ长度为n的推演序列,并且x不在r中自由出现,概括 定理告诉我们存在一个从r到wry的一个推演序列,令函数∫(n)表示该序列的长 度。找出一个函数增长速度尽可能慢的∫。 (3)(a)证明如果}a→B,则}Vra→xB (b)证明a→Ba→xB不一定总成立
(a) 在数学分析中，极限的定义如下：lim x→a f(x) = l 当且仅当 (∀ϵ ∈ R + )(∃δ ∈ R + )(∀x ∈ R)[0 <| x − a |< δ →| f(x) − l |< ϵ]。 写出 lim x→a f(x) ̸= l 的定义。 (b) 在线性代数中，我们说向量组 ⃗x1, ⃗x2, · · · , ⃗xn 是线性相关的，如果 (∃c1 ∈ R)(∃c2 ∈ R)· · ·(∃cn ∈ R)[(不全为零) ∧ c1⃗x1 + c2⃗x2 + · · · + cn⃗xn = ⃗0]。 写出向量组 ⃗x1, ⃗x2, · · · , ⃗xn 为线性无关的定义。 习题 4.1. (1) 以下公式是公理吗？如果是，属于哪组公理？ (a) [(∀xP x → ∀yP y) → P z] → [∀xP x → (∀yP y → P z)]。 (b) ∀y[∀x(P x → P x) → (P c → P c)]。 (c) ∀x∃yP xy → ∃yP yy。 (2) 证明变元 x 在任何公式 φ 中都可以替换自己。 (3) （本练习讨论公理的独立性。）证明：如果没有第二组替换公理，则其余的公理不能 证明 ∀x(x ̸≈ x) → x ̸≈ x。提示：定义函数 h : { 公式 } → {0, 1} 满足对所有的素公 式 α，h(α) = 1；然后将其自然地扩展到 h(¬α) 和 h(α → β) 上。证明如果 σ 为其余 公理的一个语法后承，则 h(σ) = 1。 习题 4.2. (1) 给出一个从空集 ∅ 到 ∀xφ → ∃xφ 的一个推演。[注意：本题要求你给出推演序列， 不准使用任何元定理。] (2) 假设有一个从公式集 Γ 到 φ 长度为 n 的推演序列，并且 x 不在 Γ 中自由出现，概括 定理告诉我们存在一个从 Γ 到 ∀xφ 的一个推演序列，令函数 f(n) 表示该序列的长 度。找出一个函数增长速度尽可能慢的 f。 (3) (a) 证明如果 ⊢ α → β，则 ⊢ ∀xα → ∀xβ。 (b) 证明 α → β |= ∀xα → ∀xβ 不一定总成立。 2
(4)证明: (a)hr(Px→rPr) (b)Qy, Vy(Qy-V2Pz)b epr (5)证明内定理 (a)彐rav彐xB分r(aVB) vxB→vx(aVB)。 B)→彐a∧彐xB (d)r(a∧B)+ ca A VaB (e)vr(a→B)→(ra→彐rB) (f)r(Py∧Qx)分 Py A dcQa 习题43 (1)(a)给出两个(y}不等于的例子,要求在一个例子中x出现在(y}中而不出 现在φ中;在另一个例子中x出现在φ中而不出现在(y)中。 (b)(循环替換引理)如果变元y完全不在公式φ中出现,则变元x可以在公式y 中替换y并且()=φ。 (2)证明 P ry h VyV (3)证明(Eq3) (4)证明下列的等价替换定理:假定公式y'是由把公式y中的若干个v,v2…,vn分 别替换成v,叫,…,v而得到的。如果}分,v4,…,}vnv 则 习题4.4
(4) 证明： (a) ⊢ ∃x(P x → ∀xP x)。 (b) {Qy, ∀y(Qy → ∀zP z)} ⊢ ∀xP x。 (5) 证明内定理： (a) ∃xα ∨ ∃xβ ↔ ∃x(α ∨ β)。 (b) ∀xα ∨ ∀xβ → ∀x(α ∨ β)。 (c) ∃x(α ∧ β) → ∃xα ∧ ∃xβ。 (d) ∀x(α ∧ β) ↔ ∀xα ∧ ∀xβ。 (e) ∀x(α → β) → (∃xα → ∃xβ)。 (f) ∃x(P y ∧ Qx) ↔ P y ∧ ∃xQx。 习题 4.3. (1) (a) 给出两个 (φ x y ) y x 不等于 φ 的例子，要求在一个例子中 x 出现在 (φ x y ) y x 中而不出 现在 φ 中；在另一个例子中 x 出现在 φ 中而不出现在 (φ x y ) y x 中。 (b) （循环替换引理）如果变元 y 完全不在公式 φ 中出现，则变元 x 可以在公式 φ x y 中替换 y 并且 (φ x y ) y x = φ。 (2) 证明： ∀x∀yP xy ⊢ ∀y∀xP yx。 (3) 证明 (Eq3)： ⊢ ∀x∀y∀z(x ≈ y → y ≈ z → x ≈ z)。 (4) 证明下列的等价替换定理：假定公式 φ ′ 是由把公式 φ 中的若干个 ψ1, ψ2, · · · , ψn 分 别替换成 ψ ′ 1 , ψ′ 2 , · · · , ψ′ n 而得到的。如果 ⊢ ψ1 ↔ ψ ′ 1，⊢ ψ2 ↔ ψ ′ 2，· · · ，⊢ ψn ↔ ψ ′ n， 则 ⊢ φ ↔ φ ′。 习题 4.4. 3
(1)假定x不在a中自由出现,证明(Q2b)和(Q3a): (a→彐xB)分r(a→B) (vxB→a)分3x(6→a) (2)分别找出一个与下列公式语法等价的前束公式 (a)(xAx∧彐xBx)→Cr (b)xAx彐Bx。 习题45. (1)证明弱化定理的下列弱形式:对所有的有穷公式集r和公式a,如果r则+I,a (2)证明:如果+r,vra(x),则对于任意项t(在我们简化了的版本里只有变元v) I,a(t)。[为什么我们这里没有t可在a中替换x的条件呢?] 弱化定理, Weakening,的一般形式为△+△,r。但如何在自然推理中定义△r我们没有讲,所以暂不要求大家 证明弱化定理
(1) 假定 x 不在 α 中自由出现，证明 (Q2b) 和 (Q3a)： ⊢ (α → ∃xβ) ↔ ∃x(α → β) ⊢ (∀xβ → α) ↔ ∃x(β → α)。 (2) 分别找出一个与下列公式语法等价的前束公式： (a) (∃xAx ∧ ∃xBx) → Cx。 (b) ∀xAx ↔ ∃xBx。 习题 4.5. (1) 证明弱化定理1的下列弱形式：对所有的有穷公式集 Γ 和公式 α，如果 ⊢ Γ 则 ⊢ Γ, α。 (2) 证明：如果 ⊢ Γ, ∀xα(x)，则对于任意项 t （在我们简化了的版本里只有变元 vi） ⊢ Γ, α(t)。[为什么我们这里没有 t 可在 α 中替换 x 的条件呢？] 1弱化定理，Weakening，的一般形式为 ∆ ⊢ ∆, Γ。但如何在自然推理中定义 ∆ ⊢ Γ 我们没有讲，所以暂不要求大家 证明弱化定理。 4