离散数学(上)

　　我们来证明一下定理2.5.3。可用数学归纳法, 施归纳于A中出现的联结词个数n来证明

证明
　　基始: 设n=0, A中无联结词, 便有
　　　A=P, 从而

A =

P
　　但 A^*－ =

P
　　∴ n=0时定理成立。
　　归纳：设n ≤k时定理成立，来证n = k + 1时定理也成立
　　∵ n = k + 1 ≥1, A中至少有一个联结词，可分为三种情形。
　　　A =

A₁, A = A₁∧A₂, A = A₁∨A₂
　　其中A₁, A₂中联结词个数≤k。
　　依归纳法假设，

A₁ = A1^*－,

A₂ = A₁^*－
　　当 A =

A₁时。
　　　

A =

(

A₁)
　　=

(A₁^*－) 归纳法假设
　　= (

A₁)^*－定理2.5.1, 2.5.2
　　= A^*－
　　当 A = A₁∧A₂时。
　　　

A =

(A₁∧A₂)
　　=

A₁∨

A₂ 摩根律
　　= A₁^*－∨A₂^*－归纳法假设
　　= (A₁^*∨A₂^*)^- A^-定义
　　= (A₁∧A₂)^*－ A^*定义
　　= A^*－
　　从而定理得证。这定理实为摩根律的另一种形式。它把

、S、－联系起来了。

证明2.5.4
　　证明: 因为A = B等价于A

B 永真。
　　从而

B 永真。
　　依定理2.5.3,

A = A^*－,

B = B^*－
　　于是 A^*－

B^*－永真
　　必有 A^*

B^* 永真
　　故 A^* = B^*