(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