离散数学：第一章第4节 对偶定理201009final [兼容模式].pdf

第一章命题逻辑 §1.4 对偶定理 §1.1 命题和联结词 定义1.10 设A 是由{0, 1, ¬, ∨, ∧} 生成的公式，将 §1.2 公式和真值赋值 A 中的∨和∧互换，0 和1 互换得到A * ，称A * 与 §1.3 等值演算 A 互为对偶式。 §1.4 对偶定理 (p ∨q) ∧r 与(p ∧q) ∨r 互为对偶式，¬(p ∨0) ∧ 1 §1.5 联结词的完全集 与¬(p ∧ 1) ∨0 互为对偶式。 §1.6 范式 定义1.11 如果真值赋值v1 和v2 满足：对于每个命 §1.7 逻辑推论 题变元p ，v (p ) ≠v (p ) ，则称v 和v 是相反的。 1 2 1 2 定理1.4 设A 是由{0, 1, ¬, ∨, ∧} 生成的公式，A * * * * 5. 若A 为B ∧C，则A 是B ∨C ，根据归纳假设， 与A 互为对偶式，v 和v′是相反的真值赋值，则 * * v(B ) = ¬v′(B) ，v(C ) = ¬v′(C) ，所以 v(A *) = ¬v′(A) * * * v(A ) = v(B ) ∨v(C ) = ¬v′(B) ∨¬v′(C) 证明 对A 进行归纳。 = v′(¬B ∨¬C) = ¬v′(B ∧C) = ¬v′(A) 。 1. 若A 是命题变元p ，则A * 是p ，v(p ) = ¬v′(p ) 。 * * * 6. 若A 为B ∨C，则A 是B ∧C ，根据归纳假设， * * 2. 若A 为0，则A * 是1，v(1) = ¬v′(0) 。 v(B ) = ¬v′(B) ，v(C ) = ¬v′(C) ，所以 * * * 3. 若A 为1，则A * 是0，v(0) = ¬v′(1) 。 v(A ) = v(B ) ∧v(C ) = ¬v′(B) ∧¬v′(C)