第一章-命题逻辑4.pptx

数理逻辑马殿富北航计算机学院dfma@buaa.edu.cn2012-9第4节 对偶定理 1.4 对偶定理定义1.10对偶式 设A是由{0,1,?,∨,∧}生成的公式，将A中的∨和∧互换，0和1互换得到A*，称A*与A互为对偶式。A = (p∨q)∧r B = ?(p∨0) ∧1A* = (p∧q)∨r B* = ?(p∧1)∨0定义1.11 相反真值赋值 如果真值赋值v1和v2满足对每个命题变元p， ，则称v1和v2是相反的。v1 = p0, q1, t0v2 = 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)=0v((p∨?q∨0)∧r∧1) =(v(p)∨?v(q)∨v(0))∧v(r)∧v(1) =(1∨?0∨0)∧1∧1=1v((p∧?q∧1)∨r∨0 ) = (v(p)∧? v( q)∧v(1))∨v(r)∨v(0) = (0∧?1∧1)∨0∨0=0= ?1对偶式的真值赋值定理1.14：设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)∧?v(C) = v(?B∧?C) = v(?(B∨C)) = ?v(B∨C)= ?v(A)证毕。 对偶定理定理1.5 (对偶定理)：设A, B是由{0, 1, ?, ∨, ∧}生成的公式，A*与A互为对偶式，B*与B互为对偶式。如果A ? B，则A* ? B*。证明：任取真值赋值v，令v是与v相反的真值赋值，因为A?B，所以v(A)=v(B)，因此，v(A*)=?v(A)= ?v(B)=v(B*)所以，A* ? B*。证毕借助对偶定理的证明例1.9 证明等值式： (1) (p?q)?(?p?(?p ?q)) ? ?p ?q (2) (p?q) ?(?p?(?p ? q)) ? ?p ? q证明：等值式(1)(p?q)?(?p?(?p ?q)) ? (p?q)?(?p??p ?q) ? (p?q)??p?q ? ?p?q证明：等值式(2)对偶定理 等值式证明方法真值表等值演算对偶定理