最新命题逻辑等值演算.doc

命题逻辑等值演算
1.
设A与B均为含n个命题变项的公式, 判断以下命题是否为真？
   〔1〕AB 当且仅当 AB是可满足式. 
       该命题为真    该命题为假  
   〔2〕AB 当且仅当 A与B∧(┐p∨┐q))∨q          (排中律、交换律)
    ┐p∨(┐q∨q)               (同一律、结合律)
    ┐p∨1                      (排中律)
    1                           (零律)
    由于该公式与1等值, 故它为重言式.
〔2〕  ┐(p→q)∧r∧q
    ┐(┐p∨q)∧q∧r            (蕴含等值式、交换律)
    p∧(┐q∧q)∧r              (德·摩根律、结合律)
    p∧0∧r                     (矛盾律)
    0                           (零律)
    由于公式与0等值, 故它为矛盾式.
〔3〕  (p→q)∧┐p
    (┐p∨q)∧┐p               (蕴含等值式)
   
┐p                         (吸收律)
    由最后一步可知, 该公式既有成真赋值00和01, 又有成假赋值10和11, 故它为可满足式.
注意：等项演算的过程不是唯一的, 但重言式一定与1等值, 矛盾式一定与0等值. 而可满足式化简到
能观察出成真和成假赋值都存在即可.
题3分析：
求主析取范式可用真值表法, 也可以用等值演算法, 这里用等值演算法.
〔1〕 (p→q)→(┐q→┐p)
   ┐(┐p∨q)∨(q∨┐p)                (消去→)
   (p∧┐q)∨┐p∨q                    (┐内移)  (已为析取范式)
   (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)  〔*〕
   m2∨m0∨m1∨m1∨m3
   m0∨m1∨m2∨m3                      (幂等律、排序)
(*)由┐p及q派生的极小项的过程如下：
      ┐p┐p∧(┐q∨q)
         (┐p∧┐q)∨(┐p∧q)
        q(┐p∨p)∧q
         (┐p∧q)∨(p∧q)
熟练之后, 以上过程可不写在演算过程中. 该公式中含n=2个命题变项, 它的主析取范式中含了22=4
个极小项, 故它为重言式, 00, 01, 10, 11全为成真赋值.
〔2〕 ┐(p→q)∧r∧q
   ┐(┐p∨q)∧r∧q                     (消去→)
   p∧┐q∧q∧r                         (┐内移)
   0                                    (矛盾律和零律)
   该公式的主析取范式为0, 故它为矛盾式, 00, 01, 10, 11全为成假赋值, 无成真赋值.
〔3〕 (p→q)∧┐p
   (┐p∨q)∧┐p