１ (零律）
由于该公式与1等值， 故它为重言式．
（２） ┐(p→q)∧ｒ∧q
┐(┐ｐ∨q)∧ｑ∧ｒ （蕴含等值式、交换律)
p∧（┐ｑ∧ｑ)∧r （德·摩根律、结合律）ﻫ p∧0∧r (矛盾律)ﻫ 0 （零律)
由于公式与０等值， 故它为矛盾式.
（3） (p→q)∧┐p
(┐p∨q）∧┐p （蕴含等值式)ﻫ ┐p （吸收律)
ｐ∧┐ｑ∧q∧r (┐内移)
0 (矛盾律和零律)
该公式的主析取范式为０， 故它为矛盾式， 0０, 01, 10, 1１全为成假赋值, 无成真赋值.
(3) （ｐ→q)∧┐ｐﻫ (┐p∨q)∧┐p （消去→）
┐p∨（┐p∧ｑ) (分配律、幂等律) 已为析取范式
(┐p∧┐q）∨(┐ｐ∧ｑ)
m０∨m1ﻫ 主析取范式中含２个极小项, 成真赋值为０0和01.
(3）若A为重言式, 说明2ｎ个赋值都是成真赋值， 因而主析取范式中含有2ｎ个极小项．
(4）若A为矛盾式， 则Ａ无成真赋值, 因而A的主析取范式不含任何极小项, 规定A的主析取范式为０, 而
不是1． 若是1, 则A 1， 这与A为矛盾式不是矛盾了吗?
(5）若A为矛盾式, 则A的2n个赋值都是成假赋值, 因而主合取范式应含有2n个极大项, 而不是1. 若为1，
（１） (p→q)→(┐q→┐ｐ)ﻫ ┐(┐p∨q)∨(q∨┐p） (消去→)
(ｐ∧┐q)∨┐p∨q (┐内移) (已为析取范式）ﻫ (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨（ｐ∧q） (*）ﻫ m2∨m０∨m1∨ｍ1∨m3ﻫ m0∨ｍ1∨m2∨m3(幂等律、排序)
(*)由┐p及q派生的极小项的过程如下：
（3)若A为重言式, 则A的主析取范式中含有2ｎ个极小项.
该命题为真 该命题为假
（4)若A为矛盾式, 则Ａ的主析取范式为１．
该命题为真 该命题为假
（５）若A为矛盾式, 则Ａ的主合取范式为1.
该命题为真 该命题为假
（6)任何公式A都能等值地化为联结词集｛∧、∨} 中的公式.
该命题为真 该命题为假
（7）任何公式A都能等值地化为联结词集{┐、→、∧}中的公式. ﻫ 该命题为真 该命题为假
由最后一步可知， 该公式既有成真赋值０0和0１, 又有成假赋值10和１1， 故它为可满足式．
注意：等项演算的过程不是唯一的， 但重言式一定与1等值, 矛盾式一定与0等值. 而可满足式化简到
能观察出成真和成假赋值都存在即可.
题3分析：
求主析取范式可用真值表法, 也可以用等值演算法, 这里用等值演算法.
题4分析:
求公式的主合取范式一般可有三种方法:
（i） 真值表法;
(ii） 等值演算法;
(iii)用主析取范式求主合取范式.
这里用方法（ｉiｉ）， 其余两种方法留给读者.
2.
用等值演算法来判断下列公式的类型.
（1)(ｐ→ｑ）→(┐ｑ→┐p)
(2)┐(p→q)∧ｒ∧q
（3）(p→q)∧┐p
3.
用主析取范式法判断题2中3个公式的类型, 并求公式的成真赋值.
题2中三个公式如下：
（１)(p→q)→(┐ｑ→┐p）
(2)┐（p→q)∧ｒ∧q
（3）(ｐ→q）∧┐p
4.
求题2中3个公式的主合取范式, 并求公式的成假赋值.
┐p ┐p∧(┐ｑ∨ｑ)
（┐p∧┐q)∨(┐p∧q)ﻫﻫ q （┐p∨p)∧q
(┐p∧ｑ）∨(p∧q）
熟练之后, 以上过程可不写在演算过程中. 该公式中含n=2个命题变项， 它的主析取范式中含了22=4
个极小项， 故它为重言式, 00, 0１, 10, １1全为成真赋值.
(２） ┐(ｐ→ｑ）∧ｒ∧qﻫ ┐(┐p∨q)∧ｒ∧q （消去→)
命题逻辑等值演算
———————————————————————————————— 作者：
———————————————————————————————— 日期：
1.
设A与B均为含n个命题变项的公式, 判断下列命题是否为真？
（1）A Ｂ 当且仅当 A B是可满足式． ﻫ 该命题为真 该命题为假
(2)A B 当且仅当 A与B有相同的主析取范式. ﻫ 该命题为真 该命题为假
则Ａ 1， A不就成了重言式了吗？
（6){∧、∨}不是联结词完备集. 因而, 有的公式不能等值地化为它中的公式. 例如:ﻫ p q ┐ｐ∨q ┐（p∧┐q) .．． 但无论如何不能只含联结词∧和∨.
（7)｛┐、→}是联结词完备集, 在它中再加一个联结词∧, 所得集合{┐、→、∧}也为完备集， 因而
任何公式A都能等值地化为联结词集｛┐、→、∧}中的公式.
题2中三个公式如下：
（１）(p→q)→(┐ｑ→┐ｐ)
(2)┐(ｐ→q)∧r∧q
(３)(p→q)∧┐ｐ
ﻫﻫ
５.
已知命题公式A中含3个命题变项p, q， r， 并知道它的成真赋值分别为00１， 010, 111， 求Ａ的主析取范式和主合取范式.
6.
用等值演算法证明下面等值式.
(１）(┐p∨q)∧(p→r) p→（ｑ∧r)
（5）若周去， 则赵、钱也同去
问该公司应选派哪些人出国？
例题分析
题１分析:
（1）A B 当且仅当 A B为重言式, 而不是可满足式.
（2）A B说明A与B有相同的成真赋值, 因而有相同的主析取范式;反之若A与B有相同的主析取范式，
说明它们有相同的成真赋值,当然也有相同的成假赋值. 因而Ａ B为重言式，故Ａ Ｂ.
（2）(p∧q)∨┐（┐p∨q) p
7.
求公式(p→┐q)∧r在以下各联结词完备集中与之等值的一个公式：
（1){┐，∧, ∨}
(2){┐,∧}
(３）{┐,∨}
(4）{┐, →}
（5）｛↑}Βιβλιοθήκη 8.用等值演算法求解下面问题.
某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件:ﻫ （1)若赵去, 则钱也去ﻫ （2）李、周中至少去一人ﻫ (３）钱、孙中去且仅去一人ﻫ （4)孙、李两人都去或都不去
题2分析:
(１） （p→q)→(┐ｑ→┐p)ﻫ ┐（┐ｐ∨q）∨(q∨┐p) (蕴涵等值式）ﻫ (ｐ∧┐q）∨(┐p∨q） （德·摩根律、交换律)
(（p∧┐q）∨┐p)∨q （结合律)
（(ｐ∨┐p)∧(┐q∨┐ｐ）)∨q (分配律)ﻫ (１∧(┐ｐ∨┐q))∨q (排中律、交换律）
┐ｐ∨(┐q∨q） (同一律、结合律）ﻫ ┐ｐ∨１ (排中律）