数理逻辑练习题及答案-2

命题逻辑等价演算

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)

（已为{┐,→,}中公式）

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数理逻辑练习题及答案-2在线全文阅读。