我们来证明一下定理2.5.3。可用数学归纳法,
施归纳于A中出现的联结词个数n来证明![]() 基始: 设n=0, A中无联结词, 便有 A=P, 从而 ![]() ![]() 但 A*- = ![]() ∴ n=0时定理成立。 归纳: 设n ≤k时定理成立,来证n = k + 1时定理也成立 ∵ n = k + 1 ≥1, A中至少有一个联结词,可分为三种情形。 A = ![]() 其中A1, A2中联结词个数≤k。 依归纳法假设, ![]() ![]() 当 A = ![]() ![]() ![]() ![]() = ![]() = ( ![]() = A*- 当 A = A1∧A2时。 ![]() ![]() = ![]() ![]() = A1*-∨A2*- 归纳法假设 = (A1*∨A2*)- A-定义 = (A1∧A2)*- A*定义 = A*- 从而定理得证。这定理实为摩根律的另一种形式。它把 ![]() ![]() 证明: 因为A = B等价于A ![]() 从而 ![]() ![]() ![]() 依定理2.5.3, ![]() ![]() 于是 A*- ![]() 必有 A* ![]() 故 A* = B* |