命题逻辑等价演算
1． 设A、B、C为任意的命题公式。
（1）已知A∨CB∨C，问：AB一定成立吗？
（2）已知A∧CB∧C，问：AB一定成立吗？
（3）已知┐A┐B，问：AB一定成立吗？
2． 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出
成真赋值。
（1）┐(p∧q→q)
（2）(p→(p∨q))∨(p→r)
（3）(p∨q)→(p∧r)
3． 用等值演算法证明下面等值式：
（1）┐(pq)(p∨q)∧┐(p∧q)
（2）(p∧┐q)∨(┐p∧q)(p∨q)∧┐(p∧q)
4． 求下列公式的主析取范式，并求成真赋值：
（1）(┐p→q)→(┐q∨p)
（2）┐(p→q)∧q∧r
（3）(p∨(q∧r))→(p∨q∨r)
5． 求下列公式的主合取范式，并求成假赋值：
（1）┐(q→┐p)∧┐p
（2）(p∧q)∨(┐p∨r)
（3）(p→(p∨q))∨r
6． 求下列公式的主析取范式，再用主析取范式求合取范式：
（1）(p∧q)∨r
（2）(p→q)∧(q→r)
7． 用主析取范式判断下列公式是否等值：
（1）(p→q)→r与q→(p→r)
（2）┐(p∧q)与┐(p∨q)
8． 用主合取范式判断下列公式是否等值：
（1）p→（q→r）与┐(p∧q)∨r
（2）p→（q→r）与(p→q)→r
9． 某电路中有一个灯泡和三个开关A,B,C。已知在且仅在下述四种情况下灯亮：
（1）C的扳键向上，A,B的扳键向下。
（2）A的扳键向上，B,C的扳键向下。
（3）B,C的扳键向上，A的扳键向下。
（4）A,B的扳键向上，C的扳键向下。
设F为1表示灯亮，p,q,r分别表示A,B,C的扳键向上。
（a）求F的主析取范式。
（b）在联结词完备集{┐,∧}上构造F.
（c）在联结词完备集{┐,→,}上构造F.
答案
1．
（1）不一定。
（2）不一定。
（3）一定。
2．
（1）矛盾式。
（2）重言式。
（3）可满足式，000，001，101，111为成真赋值。
3．
（1）
┐(pq) ┐((p→q)∧(q→p)) ┐((┐p∨q)∧(┐q∨p)) (p∧┐q)∨(q∧┐p) (p∨q)∧(p∨┐p)∧(┐q∨q)∧(┐p∨┐q) (p∨q)∧┐(p∧q) （2）
(p∧┐q)∨(┐p∧q) (p∨┐p)∧(p∨q)∧(┐q∨┐p)∧(┐q∨q) (p∨q)∧┐(p∧q)
4．
（1）m0∨m2∨m3，00，10，11为成真赋值。
（2）主析取范式为0，无成真赋值，为矛盾式。
（3）m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7，为重言式。 5．
（1）M0∧M1∧M2∧M3，为矛盾式。
（2）M4，成假赋值为100。
（3）主合取范式为1，为重言式。
6．
（1）m1∨m3∨m5∨m6∨m7M0∧M2∧M4
（2）m0∨m1∨m3∨m7M2∧M4∧M5∧M6
7．
（1）
(p→q)→r)m1∨m3∨m4∨m5∨m7 q→(p→r)m0∨m1∨m2∨m3∨m4∨m5∨m7 所以(p→q)→r)q→(p→r)
（2） ┐(p∧q)m0∨m1∨m2 ┐(p∨q)m0 所以┐(p∧q)┐(p∨q) 8． （1）
p→(q→r)M6 ┐(p∧q)∨rM6 所以p→(q→r)┐(p∧q)∨r
（2）
p→(q→r)M6 (p→q)→rM0∧M1∧M2∧M6 所以p→(q→r)(p→q)→r
9． (a)
由条件（1）-（4）可知，F的主析取范式为 F(┐p∧┐q∧r)∨(p∧┐q∧┐r)∨(┐p∧q∧r)∨(p∧q∧┐r) m1∨m4∨m3∨m6 m1∨m3∨m4∨m6
(b)
先化简公式 F(┐p∧┐q∧r)∨(p∧┐q∧┐r)∨(┐p∧q∧r)∨(p∧q∧┐r) ┐q∧((┐p∧r)∨(p∧┐r))∨q∧((┐p∧r)∨(p∧┐r)) (┐q∨q)∧((┐p∧r)∨(p∧┐r)) (┐p∧r)∨(p∧┐r) ┐(┐(┐p∧r)∧┐(p∧┐r)) （已为{┐,∧}中公式）
(c) F(┐p∧r)∨(p∧┐r) ┐┐(┐p∧r)∨(p∧┐r) ┐(┐p∧r) →(p∧┐r) (p∨┐r) →┐(┐p∨r) (r→p) →┐(p→r)
（已为{┐,→,}中公式）