(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