习题参考答案
第1章 数理逻辑
1.1命题
1．解（a）(ⅰ)┐P∧R→Q (ⅱ)Q→R
(ⅲ)┐P (ⅳ)P∧┐Q ( b)(ⅰ)我去镇上当且仅当我有时间且天不下雪。 (ⅱ)我有时间并且去镇上。
(ⅲ)如果我去镇上，那么我有时间；如果我有时间，那么我去镇上（或：我去
镇上当且仅当我有时间）。
(ⅳ)说我有时间或我去镇上是不对的。
2．解（a）上海并非处处清洁。
（b）并非每一个自然数都是偶数。
3．解（a）逆命题：如果我不去，那么天下雨。
逆反命题：如果我去，那么天不下雨。 （b）逆命题：如果你去，我将逗留。
逆反命题：如果你不去，我将不逗留。
（c）逆命题：如果方程xn?yn?zn无正整数解，那么n是大于2的正整数。
逆反命题：如果方程xn?yn?zn有正整数解，那么n不是大于2的正整数。
（d）逆命题：如果我不能完成这个任务，那么我没有获得更多帮助。 逆反命题：如果我能完成这个任务，那么我获得了更多帮助。
4．给P和Q指派真值T，给R和S指派真值F，求出下列命题的真值： （a）P∨Q∧R
(b) P∨Q∧R∨┐((P∨Q)∧(R∨S))
(c) (┐(P∧Q)∨┐R)∨(P┐∧Q∨┐R)∧S (d) ┐(P∧Q)∨┐R∨((Q?┐P)→R∨┐S) (e) (P?R)∧(┐Q→S)
(f) P∨(Q→R∧┐P)?Q∨┐S
解：做出各个命题的真值表，求出真值。 （a） T P Q R Q∧R P∨Q∧R T T F F T (b) T(c) T(d) T(e)F (f)T (b) (c) (d) (e) (f) (表略) 5．解： （a） P Q 0 0 P→Q 1 Q∧(P→Q) 0 Q∧(P→Q)→P 1 0 1 1 0 1 1 （b）
1 0 1 1 0 1 0 1 1 P Q Q∧R ┐(P∨Q∧R) (P∨Q)∧(P∨R) ┐(P∨Q∧R)? (P∨Q)∧(P∨R) R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0
（c）(略)；（d）(略)。 6.证明下列公式的真值与他们的变元值无关： (a)P∧(P→Q)→Q (b)(P→Q)→(┐P∨Q)
(c)(P→Q)∧(Q→R)→(P→R) (d)(P?Q) ? (P∧Q∨┐P∧┐Q)
证明：做出各个命题的真值表，证明公式的真值与他们的变元值无关 (a) P 0 0 1 1 Q 0 1 0 1 P→Q 1 1 0 1 P∧(P→Q) 0 0 0 1 P∧(P→Q)→Q 1 1 1 1 (b) (c) (d) (表略) 7．证明 作真值表： P Q 0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0 1
P ? Q P→Q Q→P （P→Q）∧（Q→P）
1 1 1 1 1 由表可知，P? Q 在第一，四行上取真值，这时，P→Q ，Q→P也为真；另一
方面，在第一，四行上P→Q 和Q→P同时为真，这时P? Q也为真。于是本题得证。
8．对P和Q的所有值，证明P→Q与┐P∨Q有同样真值。证明(P→Q)?( ┐P∨Q)总是真
的。
证明：做出(P→Q)?( ┐P∨Q)的真值表 P 0 0 1 1
9．解（a）∧、∨、? 是可交换的。
（b）作出P∧Q、Q∧P；P∨Q、Q∨P；P ? Q、Q ? P和P→Q、Q→P的真值表，
由表得出前三对公式等价，后一对公式不等价（表略）。
10．设*是具有两个运算对象的逻辑运算符，如果（x*y）*z和x*(y*z)逻辑等价，那么运算符*是可结合的。
(a)确定逻辑运算符∧、∨、→、?那些事可结合的。 (b)用真值表确定你的断言。 解：(a) ∧、∨、?是可结合的。
(b) 做出（P∧Q）∧R、P∧(Q∧R)；(P∨Q) ∨R、P∨(Q∨R)；(P?Q) ?R、P? (Q?R)；(P→Q) →R、P→(Q→R)的真值表，由表得出前三对公式等价，后一对公式不等价。
(表略) 11. 解：（b）、（c）不是命题公式，因为它们不能根据命题公式的形成规则而得到。（a）和（d）
是命题公式，它们的构造过程如下：（a）①P是命题公式 根据条款1
②Q是命题公式 根据条款1 ③（P∧Q）是命题公式 根据①、②条款2 ④（┐P）是命题公式 根据①条款2 ⑤（（┐P）→（P∧Q））是命题公式 根据③、④条款2 ⑥R是命题公式 根据条款1
⑦（（┐P→（P∧Q））∨R）是命题公式 根据⑤、⑥条款2
（d）①P是命题公式 根据条款1
②Q是命题公式 根据条款1 ③(P→Q)是命题公式 根据①、②条款2 ④(Q∧(P→Q))是命题公式 根据②、③条款2 ⑤(Q∧(P→Q)→P)是命题公式 根据①、④条款2
Q 0 1 0 1 ┐P 1 1 0 0 P→Q 1 1 0 1 ┐P∨Q 1 1 0 1 (P→Q)?( ┐P∨Q) 1 1 1 1 1.2 重言式
1. 指出下列命题哪些是重言式、偶然式和矛盾式：
重言式有：a c d e f h i k l
偶然式有：g j m n 矛盾式有：b
2. (a)= P∨Q∨┐R= ┐（┐P∧┐Q∧R） (b)= P∨┐（┐Q∧R）∨P = P∨Q∨┐R
= ┐（┐P∧┐Q∧R） (c)= ┐P∨（┐Q∨R）
= T
(d)= F
(e)=（┐P∨（Q∨┐R））∧┐P∧Q
= ┐P∧Q
= ┐（P∨┐Q）
(f)= ┐P∧┐Q∧（R∨P）
= ┐P∧┐Q∧R∨┐P∧┐Q∧P = ┐P∧┐Q∧R∨F = ┐（P∨Q∨┐R）
3. (a)= ┐（P∧Q）∨P=┐P∨┐Q∨P=T (b)= ┐(┐(P∨Q)→┐P)
= ┐(P∨Q∨┐P) = F
(c)= (┐Q∨P)∧(P∨Q)∧T =P (d)= ┐P∧P=F 4.(a)= ┐P∨┐Q∨P
= P∨(┐P∨┐Q) = ┐P→(P→┐Q)
(b)= (┐P∨Q)∧(┐R∨Q)
= (┐P∧┐R)∨Q = ┐(P∨Q)∨Q = P∨R→Q
(c)= ┐((P→Q)∧(Q→P)
= ┐((┐P∨Q)∧(┐Q∨P)) = ┐(┐P∨Q)∨┐(P∨┐Q) = (P∧┐Q)∨(┐P∧Q)
= (P∨┐P)∧(P∨Q)∧(┐Q∨┐P)∧(┐Q∨Q) = (P∨Q)∧┐(P∧Q) (d)= ┐(┐P∨Q) = P∧┐Q
5．使用恒等式证明下列各式，并写出与他们对偶的公式。
(a)(┒(┒P∨┒Q)∨┒(┒P∨Q) ?P
(b)(P∨┒Q)∧(P∨Q)∧(┐P∨┐Q) ?┐(┐P∨Q) (c)Q∨┐((┐P∨Q)∧P) ?T
证明：(a)(┒(┒P∨┒Q)∨┒(┒P∨Q)
?((P∧Q)∨(P∧┐Q) ? (P∧(Q∨┐Q)) ?P
对偶公式: (┒(┒P∧┒Q)∧┒(┒P∧Q)
(b) (P∨┒Q)∧(P∨Q)∧(┐P∨┐Q)
? (P∨(┒Q∧Q)) ∧(┐P∨┐Q) ? P∧(┐P∨┐Q) ? P∧┐P∨P∧┐Q ?┐ (┐P∨Q)
对偶公式: (P∧┒Q)∨(P∧Q)∨(┐P∧┐Q)
(c) Q∨┐((┐P∨Q)∧P)
? Q∨┐(Q∧P) ? Q∨┐Q∨┐P ?T∨┐P ?T
对偶公式: Q∧┐((┐P∧Q)∨P)
6.求出下列公式的最简等价式。
(a)((P→Q)?(┐Q→┐P))∧R (b)P∨┐P∨(Q∧┐Q)
(c)(P∧(Q∧S))∨(┐P∧(Q∧S)) 解：(a)((P→Q)?(┐Q→┐P))∧R
? ((┐P∨Q) ? (Q∨┐P)) ∧R ?T∧R ? R
(b)P∨┐P∨(Q∧┐Q) ?T∨F ? T
(c)(P∧(Q∧S))∨(┐P∧(Q∧S)) ? (P∨┐P) ∧(Q∧S) ? Q∧S
7.证明下列蕴含式。
(a)P∧Q?(P→Q) (b)P? (Q→P)
(c)(P→(Q→R)) ? (P→Q)→(P→R)
证明：(a)方法一：只要证明P∧Q→(P→Q)是永真式 P∧Q→(P→Q) ?┐(P∧Q)∨(┐P∨Q)
习题1.1-1.2参考答案
