第一章-命题逻辑4.pptx

数理逻辑
马殿富
北航计算机学院
******@buaa.
2012-9
第4节对偶定理
对偶定理

设A是由{0,1,,∨,∧}生成的公式,将A中的∨和∧互换,0和1互换得到A*,称A*与A互为对偶式。
A = (p∨q)∧r B = (p∨0) ∧1
A* = (p∧q)∨r B* = (p∧1)∨0
相反真值赋值
如果真值赋值v1和v2满足对每个命题变元p, ,则称v1和v2是相反的。
v1 = <p0, q1, t0>
v2 = <p1, q0, t1>
例
(p∨q∨0)∧r∧1 v(p)=1,v(q)=0,v(r)=1
(p∧q∧1)∨r∨0 v'(p)=0,v'(q)=1,v'(r)=0
v((p∨q∨0)∧r∧1)
=(v(p)∨v(q)∨v(0))∧v(r)∧v(1)
=(1∨0∨0)∧1∧1=1
v'((p∧q∧1)∨r∨0 )
= (v'(p)∧ v'( q)∧v'(1))∨v'(r)∨v'(0)
= (0∧1∧1)∨0∨0=0= 1
对偶式的真值赋值
:设A是由{0,1,,∨,∧}生成的公式,A*与A互为对偶式,v和v'是相反的真值赋值,则v(A*)=v'(A)。
证明:归纳证明
若A的长度为1
若A为命题变元p,则A*也为p,v(p)=v'(p)
若A为0,则A*为1,v(1)=v'(0)。
若A为1,则A*为0,v(0)=v'(1)。
假设对于长度不超过n的每个公式B,v(B*)=v'(B)。
证明长度等于n,定理成立。
若A为B,v(B*)=v' (B),并且A*为B*,有:
v(A*)=v(B*)=v(B*)=v'(B)=v'(B)= v'(A)
若A为B∧C,v(B*)=v' (B)且v(C*)=v' (C),并且A*为B*∨C*。因此有:
v(A*)=v(B*∨C*)=v(B*)∨v(C*)
=v'(B)∨v'(C)= v'(B∨C)=v'((B∧C))
= v'(B∧C) = v'(A)
若A为B∨C,v(B*)=v‘(B)且v(C*)=v’(C),
并且A*为B*∧C*。因此有:
v(A*)=v(B*∧C*)=v(B*)∧v(C*)
=v'(B)∧