习题2.1 (1)假定E是一个集合,B是E的一个子集,g:E→E和f:E×E→E分别为E上 的一个一元和二元函数。定义 C=∩x:BX并且对所有x,y(x,y∈x蕴涵g(x,f(x,y)∈x) 我们称C·为B在E中关于g和f的闭包,或者称C“为E中由B经g和∫生成的 集合。接下来定义集合序列(Cn:n∈N)如下 B CnU{q(x):x∈Cn}U{f(x,y):x,y∈Cn} 并且令 =∪ 证明C=C (2)我们称a是一个好公式,如果a中除了A3,A1r,-和→外没有别的命题符号和联 词。给出好公式的“自上而下”和“自下而上”的定义。 (3)证明归纳原理,即正文中定理??。 (4)证明没有长度为0,2,3或6的合式公式,但其它长度皆有可能。 (5)已知公式a中一元联词→出现的次数为m,其它四个二元联词出现的总次数为n 找出a的长度。 (6)在公式a中,令c表示二元联词(A,V,→,分)在a中出现的次数;s代表命题符号 出现的次数。(例如,当a为(A→(-4)时,c=1并且s=2。)用归纳原理证明 s=c+1。 (7)假定公式y的长度为n,证明y有一个长度不超过n的构造序列。 (8)给定公式p的一个构造序列,其中φ不包含命题符号A4。在此构造序列中删除所有 包含A4的项,证明删除后的序列仍是φ的一个构造序列
习题 2.1. (1) 假定 E 是一个集合，B 是 E 的一个子集，g : E → E 和 f : E × E → E 分别为 E 上 的一个一元和二元函数。定义 C ∗ = ∩ {X : B ⊆ X 并且对所有 x, y (x, y ∈ X 蕴涵 g(x), f(x, y) ∈ X)}。 我们称 C ∗ 为 B 在 E 中关于 g 和 f 的闭包，或者称 C ∗ 为 E 中由 B 经 g 和 f 生成 的 集合。接下来定义集合序列 (Cn : n ∈ N) 如下： C0 = B; Cn+1 = Cn ∪ {g(x) : x ∈ Cn} ∪ {f(x, y) : x, y ∈ Cn}。 并且令 C∗ = ∪ n∈N Cn。 证明 C ∗ = C∗。 (2) 我们称 α 是一个好公式，如果 α 中除了 A3，A17，¬ 和 → 外没有别的命题符号和联 词。给出好公式的“自上而下”和“自下而上”的定义。 (3) 证明归纳原理，即正文中定理 ??。 (4) 证明没有长度为 0, 2, 3 或 6 的合式公式, 但其它长度皆有可能。 (5) 已知公式 α 中一元联词 ¬ 出现的次数为 m，其它四个二元联词出现的总次数为 n。 找出 α 的长度。 (6) 在公式 α 中，令 c 表示二元联词 (∧, ∨, →, ↔) 在 α 中出现的次数；s 代表命题符号 出现的次数。（例如，当 α 为 (A → (¬A)) 时，c = 1 并且 s = 2。）用归纳原理证明 s = c + 1。 (7) 假定公式 φ 的长度为 n，证明 φ 有一个长度不超过 n 的构造序列。 (8) 给定公式 φ 的一个构造序列，其中 φ 不包含命题符号 A4。在此构造序列中删除所有 包含 A4 的项，证明删除后的序列仍是 φ 的一个构造序列。 1
(9)直观上说,B是公式a的一个子公式如果β本身是一个公式并且是a的一部分。 (a)给出B是公式a的一个子公式的严格定义 (b)用(a)的定义证明:如果β是a的一个子公式,y是B的一个子公式,则?也 是a的一个子公式。 (c)证明在a的最短的构造序列中出现的都是a的子公式。 习题2.2. (1)证明下列两公式互不重言蕴涵 (A分(BC),(AA(B∧C)(A)∧(B)∧(=C) (本题说明在叙述“A当且仅当B当且仅当C”时,我们要小心。) (2)(a)公式(A→B)→A)→A)是重言式吗? (b)递归地定义ak如下:ao=(A→B)并且ak+1=(k→A)。找出所有使ak为 重言式的k (3)验证下列公式为重言式 (a)((a)VB)+(a→B) (b)(a→(B→a (c)(a→(→)→(a→B)→(a→7)。 (d)(B→-a)→(-B→a)→B) (e)(a→(B→7)分(a^B)→7) (4)证明下列命题等价: (a)aB (b)F(a→B) (c)a与(a∧B)重言等价。 (d)B与(aVB)重言等价 (5)证明∑U{a}B当且仅当∑(a→B)
(9) 直观上说，β 是公式 α 的一个子公式 如果 β 本身是一个公式并且是 α 的一部分。 (a) 给出 β 是公式 α 的一个子公式的严格定义。 (b) 用 (a) 的定义证明：如果 β 是 α 的一个子公式，γ 是 β 的一个子公式，则 γ 也 是 α 的一个子公式。 (c) 证明在 α 的最短的构造序列中出现的都是 α 的子公式。 习题 2.2. (1) 证明下列两公式互不重言蕴涵： (A ↔ (B ↔ C)), ((A ∧ (B ∧ C)) ∨ ((¬A) ∧ ((¬B) ∧ (¬C))))。 （本题说明在叙述“A 当且仅当 B 当且仅当 C”时，我们要小心。） (2) (a) 公式 (((A → B) → A) → A) 是重言式吗? (b) 递归地定义 σk 如下：σ0 = (A → B) 并且 σk+1 = (σk → A)。找出所有使 σk 为 重言式的 k。 (3) 验证下列公式为重言式： (a) (((¬α) ∨ β) ↔ (α → β))。 (b) (α → (β → α))。 (c) ((α → (β → γ)) → ((α → β) → (α → γ)))。 (d) ((¬β → ¬α) → ((¬β → α) → β))。 (e) ((α → (β → γ)) ↔ ((α ∧ β) → γ))。 (4) 证明下列命题等价： (a) α |= β。 (b) |= (α → β)。 (c) α 与 (α ∧ β) 重言等价。 (d) β 与 (α ∨ β) 重言等价。 (5) 证明 Σ ∪ {α} |= β 当且仅当 Σ |= (α → β)。 2
(6)假定∑}(a→B)。证明∑}(→a)→(→B)。 (7)证明或否证(以给反例的方式)下列断言 (a)如果∑a或∑B,则∑(avB) (b)如果∑}(aVB),则∑a或∑B (8)找出所有{A1,A2,…,An}上的分别满足下列公式的真值指派: (a)a=(A1→A2)∧(42→A3)∧…∧(An-1 )? (b)B=(a∧(An→A1) (c)y=∧{(A1→(A):1≤i,j≤n并且i≠j}? 注意:(c)中γ的写法不标准,但应该不妨碍对题意的理解。] (9)证明一个真值指派v满足公式 (..(41+A2)分A3)…+An) 当且仅当在1≤i≤n中对偶数多个i,v(A1)=F。 (10)固定一个公式序列a1,a2,…。在每个公式φ,对所有的n将命题符号An都替换 成an,并把所得到的公式记作φ*。例如,当φ为(A2VA1)→A2)时,g*就是 aVan)→a2) (a)令υ为一个真值指派。定义真值指派u为u(An)=可(an)。证明(y)=可(φ*)。 (b)证明如果φ是重言式,则φ*也是。 习题2.3 (1)给出一个程序完成如下的断句任务:输入任何表达式a,该程序能够判定α是否是 个合式公式,并且在是的情况下输出a的一个生成序列。[自然地,我们不要求大 家真的去写计算机程序(能写更好),我们所要的是一个算法,即一系列简单而清晰 的指令,告诉我们先做什么后做什么等等。] (2)在定义??中将所有的右括号都省略掉。例如,原来的(A∧(B)V(C→D)就变 成了(A∧(-B∨(C→D。证明省略后仍有唯一可读性
(6) 假定 Σ |= (α → β)。证明 Σ |= ((γ → α) → (γ → β))。 (7) 证明或否证（以给反例的方式）下列断言: (a) 如果 Σ |= α 或 Σ |= β, 则 Σ |= (α ∨ β); (b) 如果 Σ |= (α ∨ β), 则 Σ |= α 或 Σ |= β。 (8) 找出所有 {A1, A2, . . . , An} 上的分别满足下列公式的真值指派： (a) α = ((A1 → A2) ∧ (A2 → A3) ∧ · · · ∧ (An−1 → An))? (b) β = (α ∧ (An → A1))? (c) γ = ∧ {(Ai → (¬Aj )) : 1 ≤ i, j ≤ n 并且 i ̸= j}? [注意: (c) 中 γ 的写法不标准，但应该不妨碍对题意的理解。] (9) 证明一个真值指派 v 满足公式 ((. . .(A1 ↔ A2) ↔ A3)· · · ↔ An) 当且仅当在 1 ≤ i ≤ n 中对偶数多个 i，v(Ai) = F。 (10) 固定一个公式序列 α1, α2, · · · 。在每个公式 φ ，对所有的 n 将命题符号 An 都替换 成 αn，并把所得到的公式记作 φ ∗。例如，当 φ 为 ((A2 ∨ A1) → A2) 时，φ ∗ 就是 ((α2 ∨ α1) → α2)。 (a) 令 v 为一个真值指派。定义真值指派 u 为 u(An) = v(αn)。证明 u(φ) = v(φ ∗ )。 (b) 证明如果 φ 是重言式，则 φ ∗ 也是。 习题 2.3. (1) 给出一个程序完成如下的断句任务：输入任何表达式 α，该程序能够判定 α 是否是 一个合式公式，并且在是的情况下输出 α 的一个生成序列。[自然地，我们不要求大 家真的去写计算机程序（能写更好），我们所要的是一个算法，即一系列简单而清晰 的指令，告诉我们先做什么后做什么等等。] (2) 在定义 ?? 中将所有的右括号都省略掉。例如，原来的 ((A ∧ (¬B)) ∨ (C → D)) 就变 成了 ((A ∧ (¬B ∨ (C → D。证明省略后仍有唯一可读性。 3
(3)假定左括号和右括号变得一样了,例如,原来的(aV(B∧)变成了|av|BA?‖, 唯一可读性还有吗? (4)将定义??中的(b)改动成 (b)如果a和β都是合式公式,则-a,∧aB,vaB,→aB和冷aB也是。 例如,原来的(AA(=B)V(C→D)就变成了VAA-B→CD。证明改动后仍有 唯一可读性。(这种表示法被称为波兰记法。 习题2.4 (1)令G为下列3-元布尔函数 G(F, F, F)=T G(T, F, F)=T G(F, F,T)=T G(T,F,T)=F G(F,T,F)=T GT,T, F)=F G(F,T,T)=F G(T,T, T)=F (a)给出一个表达G但仅涉及联词∧,V和的合式公式。 (b)重做(a),要求公式中联词出现次数不超过5次。 (2)证明|和↓是仅有的两个自身是功能完全的二元联词。 (3)证明{T,⊥,→,分,+}不是功能完全的。提示:证明用这些联词和命题符号A和B形 成的公式a在v(a)的四种可能取值里面总有偶数个T。 (4)令Ⅱ为一个三元联词满足aB取值T当且仅当a,B,中有且仅有一个赋值为T。 证明不存在二元联词。和△使得laβy等价于(aoB)△7 (5)我们称公式a是合取范式如果它形为 a=mA2∧…∧m 其中每个~都形为 Bn1VB2V…V62 并且或是一个命题符号,或是命题符号的否定。 (a)找出与AB分C重言等价的合取范式
(3) 假定左括号和右括号变得一样了，例如，原来的 (α ∨ (β ∧ γ)) 变成了 | α∨ | β ∧ γ ||， 唯一可读性还有吗？ (4) 将定义 ?? 中的 (b) 改动成 (b’) 如果 α 和 β 都是合式公式，则 ¬α，∧αβ，∨αβ，→ αβ 和 ↔ αβ 也是。 例如，原来的 ((A ∧ (¬B)) ∨ (C → D)) 就变成了 ∨ ∧ A¬B → CD。证明改动后仍有 唯一可读性。（这种表示法被称为波兰记法。） 习题 2.4. (1) 令 G 为下列 3-元布尔函数： G(F, F, F) = T G(T, F, F) = T G(F, F, T) = T G(T, F, T) = F G(F, T, F) = T G(T, T, F) = F G(F, T, T) = F G(T, T, T) = F (a) 给出一个表达 G 但仅涉及联词 ∧,∨ 和 ¬ 的合式公式。 (b) 重做 (a)，要求公式中联词出现次数不超过 5 次。 (2) 证明 | 和 ↓ 是仅有的两个自身是功能完全的二元联词。 (3) 证明 {⊤, ⊥, ¬, ↔, +} 不是功能完全的。提示：证明用这些联词和命题符号 A 和 B 形 成的公式 α 在 v(α) 的四种可能取值里面总有偶数个 T。 (4) 令 11 为一个三元联词满足 11αβγ 取值 T 当且仅当 α, β, γ 中有且仅有一个赋值为 T。 证明不存在二元联词 ◦ 和 △ 使得 11αβγ 等价于 (α ◦ β)△γ。 (5) 我们称公式 α 是合取范式 如果它形为 α = γ1 ∧ γ2 ∧ · · · ∧ γk 其中每个 γi 都形为 γi = βi1 ∨ βi2 ∨ · · · ∨ βin 并且 βij 或是一个命题符号，或是命题符号的否定。 (a) 找出与 A ↔ B ↔ C 重言等价的合取范式。 4
(b)证明每一公式都有与其重言等价的合取范式 (6)(a)假定a为一个公式其中仅包含联词→。证明A分B不重言等价于a (b)假定β为一个公式其中仅包含联词冷。证明A→B不重言等价于B。 (7)我们将真假值F和T分别看成为0和1,并规定0≤1。当n>0时,我们称一个 n-元布尔函数∫为单调的,如果对任何i=1, ∫(x1,…,x-1,0,x+1 n)≤f(x1 证明个n-元布尔函数f是单调的当且仅当它可以被仅用联词{∧,V,T,}的公式所 表达。 (8)我们称一个联词的集合C为极大不完全的,如果C不是功能完全的,但对任意C 表达不了的布尔函数g,联词集C∪{g}都是功能完全的。证明联词集{∧,v,T,⊥} 为极大不完全的。 习题25. (1)证明如果△a并且对每一B∈△,+B,则r+ao (2)证明下列公式为L中的内定理,其中a和β为合式公式。[注意:这是一个语法的 练习,请不要使用任何有关语义的结果,当然也就不能用后面的完全性定理。 (a)-→B。 (c)-→(a→B) (d)(a→B)→(-a→B)→B (e)a→ (a→B) 习题2.6. (1)用自然推演证明以前的公理(A1),(A2)和(A3)。 (2)用自然推演证明习题2.5中的公式 习题2.7
(b) 证明每一公式都有与其重言等价的合取范式。 (6) (a) 假定 α 为一个公式其中仅包含联词 →。证明 A ↔ B 不重言等价于 α。 (b) 假定 β 为一个公式其中仅包含联词 ↔。证明 A → B 不重言等价于 β。 (7) 我们将真假值 F 和 T 分别看成为 0 和 1，并规定 0 ≤ 1。当 n > 0 时，我们称一个 n-元布尔函数 f 为单调的，如果对任何 i = 1, · · · , n, f(x1, · · · , xi−1, 0, xi+1, · · · , xn) ≤ f(x1, · · · , xi−1, 1, xi+1, · · · , xn)。 证明个 n-元布尔函数 f 是单调的当且仅当它可以被仅用联词 {∧, ∨, ⊤, ⊥} 的公式所 表达。 (8) 我们称一个联词的集合 C 为极大不完全的，如果 C 不是功能完全的，但对任意 C 表达不了的布尔函数 g，联词集 C ∪ {g} 都是功能完全的。证明联词集 {∧,∨, ⊤, ⊥} 为极大不完全的。 习题 2.5. (1) 证明如果 ∆ ⊢ α 并且对每一 β ∈ ∆，Γ ⊢ β，则 Γ ⊢ α。 (2) 证明下列公式为 L 中的内定理，其中 α 和 β 为合式公式。[注意：这是一个语法的 练习，请不要使用任何有关语义的结果，当然也就不能用后面的完全性定理。] (a) ¬¬β → β。 (b) β → ¬¬β。 (c) ¬α → (α → β)。 (d) (α → β) → (¬α → β) → β。 (e) α → ¬β → ¬(α → β)。 习题 2.6. (1) 用自然推演证明以前的公理 (A1)，(A2) 和 (A3)。 (2) 用自然推演证明习题 2.5 中的公式。 习题 2.7. 5
(1)证明引理?,即:公式集∑是不相容的当且仅当对所有的公式β,∑}B。 (2)假定公式集∑相容,证明对任意公式a,∑U{a}与∑U{a}中有一个相容。(这是 林登鲍姆引理证明的一部分。) (3)假定Δ为一个极大相容集。定义真值指派v如下:对任意命题符号A, T,如果A∈△ F,如果A￠△。 证明对任意公式φ,列(9)=T当且仅当φ∈△。(这是引理?,因而也是完全性定 理证明的一部分。) (4)证明从可靠性和完全性定理的弱形式(即,}a当且仅当}a)和紧致性定理,我 们可以证明可靠性和完全性定理的一般形式(即,Fa当且仅当rha)。 (5)(独立性证明)证明某些公理(A1)的实例不能由公理(A2)和(A3)导出。[提示:考 虑下表: A A ABA→B 01 00 10 20 20 020220200 证明所有(A2)和(A3)的逻辑推论都永远取值0。] (5)a→a可以仅用公理(A2)和(A3)证明吗? (6)证明皮尔士定律 (→q)→p)→p) 不能从公理组(A1)和(A2)中导出
(1) 证明引理 ??，即：公式集 Σ 是不相容的当且仅当对所有的公式 β，Σ ⊢ β。 (2) 假定公式集 Σ 相容，证明对任意公式 α，Σ ∪ {α} 与 Σ ∪ {¬α} 中有一个相容。（这是 林登鲍姆引理证明的一部分。） (3) 假定 ∆ 为一个极大相容集。定义真值指派 v 如下：对任意命题符号 A， v(A) = { T, 如果 A ∈ ∆; F, 如果 A ̸∈ ∆。 证明对任意公式 φ，v(φ) = T 当且仅当 φ ∈ ∆。（这是引理 ??，因而也是完全性定 理证明的一部分。） (4) 证明从可靠性和完全性定理的弱形式（即，|= α 当且仅当 ⊢ α）和紧致性定理，我 们可以证明可靠性和完全性定理的一般形式（即，Γ |= α 当且仅当 Γ ⊢ α）。 (5) （独立性证明）证明某些公理 (A1) 的实例不能由公理 (A2) 和 (A3) 导出。[提示：考 虑下表： A ¬A A B A → B 0 1 0 0 0 1 1 1 0 2 2 0 2 0 0 0 1 2 1 1 2 2 1 0 0 2 2 1 2 0 2 2 0 证明所有 (A2) 和 (A3) 的逻辑推论都永远取值 0。] (5) α → α 可以仅用公理 (A2) 和 (A3) 证明吗? (6) 证明皮尔士定律 (((p → q) → p) → p) 不能从公理组 (A1) 和 (A2) 中导出。 6
(7)令C1为仅包含联词→的命题逻辑语言;并且L1是语言C1上的一个证明系统,L1 的公理为(A1),(A2)和皮尔士定律,推理规则仍只有一条分离规则。我们用卜1φ表 示φ是系统L1的一个内定理。证明:H1是完全的,即如果C1中的公式是重言 式,则卜 提示:你可以定义“极大相容集”的概念并且模仿定理??的证明。更进一步,称- 个集合Y为y-极大的如果yh1p但对所有的a∈Y,YU{a}+1。你可以先证明 每一个φ-极大的集合都是“极大相容”的。 习题2.8 (1)给出一个模型M=(W,R,V)和世界u∈W使得(M,u)}A→口B但(M,u) 口(A→B) (2)判断下列陈述的正确性并给出理由 (a)(M,u)≠a当且仅当(M,)h=ae (b)M≠a当且仅当Mk=a (3)在K中证明下列公式 (a)口(a∧B)→(口a∧口3)。 (b)(QaV◇B)→◇(aVB) 注意:虽然我们没有正式引入∧和V,但根据引理?你可以使用任何关于∧和 的古典重言式。 (4)证明下列公式不是普遍有效的 (a)口(aVB)→(av口6) (b)(Qa∧◇B)→◇(aAB)。 (6)证明系统K的可靠性定理。 (7)证明:给定框架(W,B),关系R是自反的,当且仅当对任意赋值v和任意公式a, □a→α都在模型M=(W,R,V)中真。[注:本题只是模态逻辑中大量的类似对应 中的一个。]
(7) 令 L1 为仅包含联词 → 的命题逻辑语言；并且 L1 是语言 L1 上的一个证明系统，L1 的公理为 (A1), (A2) 和皮尔士定律，推理规则仍只有一条分离规则。我们用 ⊢1 φ 表 示 φ 是系统 L1 的一个内定理。证明：⊢1 是完全的，即如果 L1 中的公式 ψ 是重言 式，则 ⊢1 ψ。 提示：你可以定义“极大相容集”的概念并且模仿定理 ?? 的证明。更进一步，称一 个集合 Y 为 φ-极大的如果 Y ̸⊢1 φ 但对所有的 α ̸∈ Y , Y ∪ {α} ⊢1 φ。你可以先证明 每一个 φ-极大的集合都是“极大相容”的。 习题 2.8. (1) 给出一个模型 M = (W, R, V ) 和世界 u ∈ W 使得 (M, u) |= A → B 但 (M, u) ̸|= (A → B)。 (2) 判断下列陈述的正确性并给出理由： (a) (M, w) ̸|= α 当且仅当 (M, w) |= ¬α。 (b) M ̸|= α 当且仅当 M |= ¬α。 (3) 在 K 中证明下列公式： (a) (α ∧ β) → (α ∧ β)。 (b) (♢α ∨ ♢β) → ♢(α ∨ β)。 注意：虽然我们没有正式引入 ∧ 和 ∨，但根据引理 ?? 你可以使用任何关于 ∧ 和 ∨ 的古典重言式。 (4) 证明下列公式不是普遍有效的： (a) (α ∨ β) → (α ∨ β)。 (b) (♢α ∧ ♢β) → ♢(α ∧ β)。 (6) 证明系统 K 的可靠性定理。 (7) 证明：给定框架 (W, R)，关系 R 是自反的，当且仅当对任意赋值 V 和任意公式 α， α → α 都在模型 M = (W, R, V ) 中真。[注：本题只是模态逻辑中大量的类似对应 中的一个。] 7
