第1章 离散数学习题解答

第1章 习题解答

习题1.1

1. 下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 ⑴ 中国有四大发明。 ⑵ 计算机有空吗? ⑶ 不存在最大素数。 ⑷ 21+3＜5。

⑸ 老王是山东人或河北人。 ⑹ 2与3都是偶数。 ⑺ 小李在宿舍里。

⑻ 这朵玫瑰花多美丽呀! ⑼ 请勿随地吐痰!

⑽ 圆的面积等于半径的平方乘以?。 ⑾ 只有6是偶数，3才能是2的倍数。 ⑿ 雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。

解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。

2. 将下列复合命题分成若干原子命题。 ⑴ 李辛与李末是兄弟。

⑵ 因为天气冷，所以我穿了羽绒服。 ⑶ 天正在下雨或湿度很高。 ⑷ 刘英与李进上山。

⑸ 王强与刘威都学过法语。

⑹ 如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻ 除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题；

⑵ p：天气冷；q：我穿羽绒服； ⑶ p：天在下雨；q：湿度很高； ⑷ p：刘英上山；q：李进上山；

⑸ p：王强学过法语；q：刘威学过法语； ⑹ p：你看电影；q：我看电影；

⑺ p：我看电视；q：我外出；r：我睡觉； ⑻ p：天下大雨；q：他乘班车上班。 3. 将下列命题符号化。

⑴ 他一面吃饭，一面听音乐。 ⑵ 3是素数或2是素数。

1

第1章 习题解答

⑶ 若地球上没有树木，则人类不能生存。 ⑷ 8是偶数的充分必要条件是8能被3整除。 ⑸ 停机的原因在于语法错误或程序错误。

⑹ 四边形ABCD是平行四边形当且仅当它的对边平行。 ⑺ 如果a和b是偶数，则a+b是偶数。

解：⑴ p：他吃饭；q：他听音乐；原命题符号化为：p∧q ⑵ p：3是素数；q：2是素数；原命题符号化为：p∨q

⑶ p：地球上有树木；q：人类能生存；原命题符号化为：?p→?q ⑷ p：8是偶数；q：8能被3整除；原命题符号化为：p?q

⑸ p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p

⑹ p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：p?q。

⑺ p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：p∧q→r 4. 将下列命题符号化，并指出各复合命题的真值。 ⑴ 如果3+3=6，则雪是白的。 ⑵ 如果3+3≠6，则雪是白的。 ⑶ 如果3+3=6，则雪不是白的。 ⑷ 如果3+3≠6，则雪不是白的。

⑸3是无理数当且仅当加拿大位于亚洲。

⑹ 2+3=5的充要条件是3是无理数。(假定是10进制)

⑺ 若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。

⑻ 当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设p：3＋3＝6。q：雪是白的。

⑴ 原命题符号化为：p→q；该命题是真命题。 ⑵ 原命题符号化为：?p→q；该命题是真命题。 ⑶ 原命题符号化为：p→?q；该命题是假命题。 ⑷ 原命题符号化为：?p→?q；该命题是真命题。

⑸ p：3是无理数；q：加拿大位于亚洲；原命题符号化为：p?q；该命题是假命题。

⑹ p：2+3＝5；q：

3是无理数；原命题符号化为：p?q；该命题是真命题。

⑺ p：两圆O1,O2的面积相等；q：两圆O1,O2的半径相等；原命题符号化为：p?q；该命题是真命题。

⑻ p：王小红心情愉快；q：王小红唱歌；原命题符号化为：p?q；该命题是真命题。

2

第1章 习题解答

习题1.2

1.判断下列公式哪些是合式公式，哪些不是合式公式。 ⑴ (p∧q→r) ⑵ (p∧(q→r)

⑶ ((?p→q)?(r∨s)) ⑷ (p∧q→rs)

⑸ ((p→(q→r))→((q→p)?q∨r))。

解：⑴⑶⑸是合式公式；⑵⑷不是合式公式。 2.设 p：天下雪。

q：我将进城。 r：我有时间。 将下列命题符号化。

⑴ 天没有下雪，我也没有进城。 ⑵ 如果我有时间，我将进城。

⑶ 如果天不下雪而我又有时间的话，我将进城。 解：⑴ ?p∧?q ⑵ r→q

⑶ ?p∧r→q

3.设p、q、r所表示的命题与上题相同，试把下列公式译成自然语言。 ⑴ r∧q ⑵ ? (r∨q) ⑶ q? (r∧? p) ⑷ (q→r)∧(r→q)

解：⑴ 我有时间并且我将进城。 ⑵ 我没有时间并且我也没有进城。

⑶ 我进城，当且仅当我有时间并且天不下雪。 ⑷ 如果我有时间，那么我将进城，反之亦然。

4. 试把原子命题表示为p、q、r等，将下列命题符号化。 ⑴ 或者你没有给我写信，或者它在途中丢失了。 ⑵ 如果张三和李四都不去，他就去。 ⑶ 我们不能既划船又跑步。

⑷ 如果你来了，那末他唱不唱歌将看你是否伴奏而定。

解：⑴ p：你给我写信；q：信在途中丢失；原命题符号化为：(?p∧? q)∨(p∧q)。 ⑵ p：张三去；q：李四去；r：他去；原命题符号化为：?p∧?q→r。 ⑶ p：我们划船；q：我们跑步；原命题符号化为：?（p∧q）。

⑷ p：你来了；q：他唱歌；r：你伴奏；原命题符号化为：p→（q?r）。 5. 用符号形式写出下列命题。

3

第1章 习题解答

⑴假如上午不下雨，我去看电影，否则就在家里读书或看报。 ⑵我今天进城，除非下雨。 ⑶仅当你走，我将留下。

解：⑴ p：上午下雨；q：我去看电影；r：我在家读书；s：我在家看报；原命题符号化为：（?p→q）∧（p→r∨s）。

⑵ p：我今天进城；q：天下雨；原命题符号化为：?q→p。 ⑶ p：你走；q：我留下；原命题符号化为：q→p。

4

第1章 习题解答

习题1.3

1.设A、B、C是任意命题公式，证明： ⑴A?A

⑵若A?B，则B?A

⑶若A?B，B?C，则A?C

证明：⑴由双条件的定义可知A?A是一个永真式，由等价式的定义可知A?A成立。 ⑵因为A?B，由等价的定义可知A?B是一个永真式，再由双条件的定义可知B?A也是一个永真式，所以，B?A成立。

⑶对A、B、C的任一赋值，因为A?B，则A?B是永真式， 即A与B具有相同的真值，又因为B?C，则B?C是永真式， 即B与C也具有相同的真值，所以A与C也具有相同的真值；即A?C成立。

2.设A、B、C是任意命题公式，

⑴若A∨C?B∨C, A?B一定成立吗？ ⑵若A∧C?B∧C, A?B一定成立吗？ ⑶若?A??B，A?B一定成立吗？

解：⑴不一定有A?B。若A为真，B为假，C为真，则A∨C?B∨C成立，但A?B不成立。

⑵不一定有A?B。若A为真，B为假，C为假，则A∧C?B∧C成立，但A?B不成立。

⑶一定有A?B。

3.构造下列命题公式的真值表，并求成真赋值和成假赋值。 ⑴ q∧(p→q)→p ⑵ p→(q∨r)

⑶ (p∨q)?(q∨p) ⑷ (p∧?q)∨(r∧q)→r

⑸ ((?p→(p∧?q))→r)∨(q∧?r)

解：⑴ q∧(p→q)→p的真值表如表1.24所示。

表1.24

p 0 0 1 1 q 0 1 0 1 p→q 1 1 0 1 q∧(p→q) 0 1 0 1 q∧(p→q)→p 1 0 1 1

使得公式q∧(p→q)→p成真的赋值是：00，10，11，使得公式q∧(p→q)→p成假的赋值是：01。

5

第1章 习题解答

⑵ p→(q∨r) 的真值表如表1.25所示。

表1.25

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 q∨r 0 1 1 1 0 1 1 1 p→(q∨r) 1 1 1 1 0 1 1 1

使得公式p→(q∨r)成真的赋值是：000，001，010，011，101，110，111，使得公式p→(q∨r)成假的赋值是：100。

⑶ (p∨q)?(q∨p) 的真值表如表1.26所示。

表1.26

p 0 0 1 1 q 0 1 0 1 p∨q?0 1 1 1 q∨p?0 1 1 1 (p∨q)?(q∨p) 1 1 1 1

所有的赋值均使得公式(p∨q)?(q∨p)成真，即(p∨q)?(q∨p)是一个永真式。 ⑷ (p∧?q)∨(r∧q)→r的真值表如表1.27所示。

表1.27

p 0 0 0 0 1 1 1 q 0 0 1 1 0 0 1 r 0 1 0 1 0 1 0 ?q 1 1 0 0 1 1 0 p∧?q 0 0 0 0 1 1 0 r∧q 0 0 0 1 0 0 0 (p∧?q)∨(r∧q)?0 0 0 1 1 1 0 (p∧?q)∨(r∧q)→r 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 使得公式(p∧?q)∨(r∧q)→r成真的赋值是：000，001，010，011，101，110，111，

6

第1章 习题解答

使得公式(p∧?q)∨(r∧q)→r成假的赋值是：100。

⑸((?p→(p∧?q))→r)∨(q∧?r) 的真值表如表1.28所示。

表1.28

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r p∧?q ?p→(p∧?q) (?p→(p∧?q))→r 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 q∧?r ((?p→(p∧?q))→r)∨(q∧?r) 0 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 使得公式((?p→(p∧?q))→r)∨(q∧?r)成真的赋值是：000，001，010，011，101，110，111，使得公式((?p→(p∧?q))→r)∨(q∧?r)成假的赋值是：100。

4.用真值表证明下列等价式： ⑴?(p→q)?p∧?q

证明：证明?(p→q)?p∧?q的真值表如表1.29所示。

表1.29

p 0 q p→q ?(p→q)??q?0 1 1 0 1 0 0 1 0 1 0 1 0 p∧?q?0 0 1 0 0 1 1 0 1 1

由上表可见：?(p→q)和p∧?q的真值表完全相同，所以?(p→q)?p∧?q。 ⑵p→q??q→?p

证明：证明p→q??q→?p的真值表如表1.30所示。

表1.30

p 0 0 1 1 q p→q 0 1 0 1 1 1 0 1 ?p?1 1 0 0 ?q?1 0 1 0 ?q→?p?1 1 0 1 由上表可见：p→q和?q→?p的真值表完全相同，所以p→q??q→?p。

7

第1章 习题解答

⑶?(p?q)?p??q

证明：证明?(p?q)和p??q的真值表如表1.31所示。

表1.31

p 0 0 1 1 q p?q ?(p?q)??q?0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 p??q?0 1 1 0

由上表可见：?(p?q)和p??q的真值表完全相同，所以?(p?q)?p??q。 ⑷p→(q→r)?(p∧q)→r

证明：证明p→(q→r)和(p∧q)→r的真值表如表1.32所示。

表1.32

p 0 0 0 0 1 1 1 1 q 0 r 0 q→r?p→(q→r)?p∧q?(p∧q)→r?1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 由上表可见：p→(q→r)和(p∧q)→r的真值表完全相同，所以p→(q→r)?(p∧q)→r。 ⑸p→(q→p)???p→(p→?q)

证明：证明p→(q→p)和?p→(p→?q)的真值表如表1.33所示。

表1.33

p 0 0 1 1 q q→p p→(q→p)??p??q?p→?q??p→(p→?q)?0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 0 1 1 1 1

由上表可见：p→(q→p)和?p→(p→?q)的真值表完全相同，且都是永真式，所以p→(q→p)??p→(p→?q)。

⑹?(p?q)?(p∨q)∧?(p∧q)

8

第1章 习题解答

证明：证明?(p?q)和(p∨q)∧?(p∧q)的真值表如表1.34所示。

表1.34

p 0 0 1 1 q p?q ?(p?q)?p∨q?p∧q??(p∧q)?(p∨q)∧?(p∧q)?0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0

由上表可见：?(p?q)和(p∨q)∧?(p∧q)的真值表完全相同，所以?(p?q)?(p∨q)∧?(p∧q)

⑺?(p?q)?(p∧?q)∨(?p∧q)

证明：证明?(p?q)和(p∧?q)∨(?p∧q)的真值表如表1.35所示。

表1.35

p 0 0 1 1 q p?q ?(p?q)?p∧?q??p∧q?0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 (p∧?q)∨(?p∧q)?0 1 1 0

由上表可见：?(p?q)和(p∧?q)∨(?p∧q)的真值表完全相同，所以?(p?q)?(p∧?q)∨(?p∧q)。

⑻p→(q∨r)?(p∧?q)→r

证明：证明p→(q∨r)和(p∧?q)→r的真值表如表1.36所示。

表1.36

p 0 0 0 0 1 1 1 1 q 0 1 1 0 0 r 0 0 1 0 1 q∨r?p→(q∨r)?0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 ?q?1 1 0 0 1 1 0 0 p∧?q?(p∧?q)→r?0 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1

由上表可见：p→(q∨r)和(p∧?q)→r的真值表完全相同，所以p→(q∨r)?(p∧?q)→r。

9

第1章 习题解答

5. 用等价演算证明习题4中的等价式。 ⑴?(p→q) ??(?p∨q) ?p∧?q ⑵?q→?p ???q∨?p ?q∨?p ??p∨q ? p→q ⑶?(p?q)

??((p→q)∧(q→p)) ??((?p∨q)∧(?q∨p)) ?(p∧?q)∨(q∧?p)

?((p∧?q)∨q)∧((p∧?q)∨?p) ?(p∨q)∧(?q∨?p) ?(?p∨?q)∧(q∨p) ?(p→?q)∧(?q→p) ?p??q ⑷p→(q→r) ??p∨(?q∨r) ?(?p∨?q)∨r ??(p∧q)∨r ?(p∧q)→r ⑸p→(q→p) ??p∨(?q∨p) ?T

?p→(p→?q) ?p∨(?p∨?q)

?T

所以p→(q→p)???p→(p→?q) ⑹?(p?q)

??((p∧q)∨(?p∧?q)) ?(p∨q)∧(?p∨?q) ?(p∨q)∧?(p∧q)

所以?(p?q)?(p∨q)∧?(p∧q) ⑺?(p?q)

??((p→q)∧(q→p)) ??((?p∨q)∧(?q∨p)) ?(p∧?q)∨(?p∧q)

(条件等价式) (德·摩根律) (条件等价式) (双重否定律) (交换律)

(条件等价式) (双条件等价式) (条件等价式) (德·摩根律) (分配律) (分配律) (交换律) (条件等价式) (双条件等价式) (条件等价式) (结合律)

(德·摩根律) (条件等价式) (条件等价式)?

(条件等价式)?

(例1.17) (德·摩根律) (德·摩根律)

(双条件等价式) (条件等价式) (德·摩根律)

10

第1章 习题解答

⑻p→(q∨r) ??p∨(q∨r) (条件等价式) ?(?p∨q)∨r (结合律) ??(p∧?q)∨r (德·摩根律) ?(p∧?q)→r (条件等价式)

6.试用真值表证明下列命题定律。

⑴结合律：(p∨q)∨r?p∨(q∨r)，(p∧q)∧r?p∧(q∧r) 证明：证明结合律的真值表如表1.37和表1.38所示。

表1.37

p 0 0 0 0 1 1 1 1 q 0 1 1 0 0 r 0 0 1 0 1 p∨q?(p∨q)∨r?q∨r?p∨(q∨r)?0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1

表1.38

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p∧q?(p∧q)∧r?q∧r?p∧(q∧r)?0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1

由真值表可知结合律成立。

⑵分配律：p∧(q∨r)?(p∧q)∨(p∧r)，

p∨(q∧r)?(p∨q)∧(p∨r)

证明：证明合取对析取的分配律的真值表如表1.39所示，析取对合取的的分配律的真值表如表1.40所示。

11

第1章 习题解答

表1.39

p 0 0 0 0 1 1 1 1 q 0 1 1 0 0 r 0 0 1 0 1 q∨r?0 1 1 1 0 1 1 1 p∧(q∨r)?0 0 0 0 0 1 1 1 p∧q?0 0 0 0 0 0 1 1 p∧r?0 0 0 0 0 1 0 1 (p∧q)∨(p∧r)?0 0 0 0 0 1 1 1 0 1 1 0 1 1

表1.40

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 q∧r?0 0 0 1 0 0 0 1 p∨(q∧r)?0 0 0 1 1 1 1 1 p∨q?0 0 1 1 1 1 1 1 p∨r?0 1 0 1 1 1 1 1 (p∨q)∧(p∨r)?0 0 0 1 1 1 1 1

由真值表可知分配律成立。 ⑶假言易位式：p→q??q→?p

证明：证明假言易位式的真值表如表1.41所示。

表1.41

p 0 0 1 1 q 0 1 0 1 p→q 1 1 0 1 ?q?1 0 1 0 ?p?1 1 0 0 ?q→?p?1 1 0 1

由真值表可知假言易位律成立。

⑷双条件否定等价式：p?q??p??q

证明：证明双条件否定的真值表如表1.42所示。

12

第1章 习题解答

表1.42

p 0 0 1 1 q 0 1 0 1 p?q 1 0 0 1 ?p?1 1 0 0 ?q?1 0 1 0 ?p??q?1 0 0 1

由真值表可知双条件否定等价式成立。

13

第1章 习题解答

习题 1.4

1.用真值表或等价演算判断下列命题公式的类型。 ⑴(p∨?q)→q ??(p∨?q)∨q ?(?p∧q)∨q

?q （可满足式） ⑵?(p→q)∧q ??(?p∨q)∧q ?(p∧?q)∧q ?F（永假式） ⑶(p→q)∧p→q ?(?p∨q)∧p→q

?(?p∧p)∨(q∧p)→q ?(q∧p)→q ??(q∧p)∨q ?(?q∨?p)∨q ?T(永真式) ⑷(p→q)∧q ?(?p∨q)∧q ?q（可满足式） ⑸(p→q)→(?q→?p) ?(p→q)→(p→q) ?T(永真式)

⑹((p→q)∧(q→r))→(p→r)

??((?p∨q)∧(?q∨r))∨(?p∨r) ?(p∧?q)∨(q∧?r)∨(?p∨r)

?(p∧?q)∨((?p∨q∨r)∧(?p∨?r∨r)) ?(p∧?q)∨(?p∨q∨r)

?(?p∨q∨r∨p)∧(?p∨q∨r∨?q) ?T(永真式) ⑺?p→(p→q) ? p∨(?p∨q) ?T(永真式) ⑻p→(p∨q∨r) ??p∨(p∨q∨r) ?T(永真式)

2.用真值表证明下列命题公式是重言式。

14

（条件等价式） （德·摩根律） （吸收律） （条件等价式） （德·摩根律） （结合律、矛盾律） （条件等价式） （分配律）

（同一律、矛盾律） （条件等价式） （德·摩根律） （零律、排中律） （条件等价式） （吸收律） （假言易位式）

（条件等价式） （德·摩根律） （分配律）

（同一律、排中律、零律）（分配律）

（条件等价式）

（条件等价式）

第1章 习题解答

⑴(p∧(p→q))→q

(p∧(p→q))→q的真值表如表1.43所示。由表1.43可以看出(p∧(p→q))→q是重言式。

表1.43

p 0 0 1 1 q p→q p∧(p→q)?(p∧(p→q))→q?0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1

⑵(?q∧(p→q))→?p

(?q∧(p→q))→?p的真值表如表1.44所示。由表1.44可以看出(?q∧(p→q))→?p是重言式。

表1.44

p 0 0 1 1 q p→q ?q??q∧(p→q)??p?(?q∧(p→q))→?p?0 1 0 1 1 1 0 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1

⑶(?p∧(p∨q))→q

(?p∧(p∨q))→q的真值表如表1.45所示。由表1.45可以看出(?p∧(p∨q))→q是重言式。

表1.45

p 0 0 1 1 q p∨q ? p??p∧(p∨q)?0 1 0 1 0 1 1 1 1 1 0 0 0 1 0 0 (?p∧(p∨q))→q?1 1 1 1

⑷((p→q)∧(q→r))→(p→r)

((p→q)∧(q→r))→(p→r)的真值表如表1.46所示。由表1.46可以看出((p→q)∧(q→r))→(p→r)是重言式。

15

第1章 习题解答

表1.46

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p→q 1 1 1 1 0 0 1 1 q→r 1 1 0 1 1 1 0 1 (p→q)∧(q→r) 1 1 0 1 0 0 0 1 p→r 1 1 1 1 0 1 0 1 ((p→q)∧(q→r))→(p→r) 1 1 1 1 1 1 1 1

⑸((p∨q)∧(p→r)∧(q→r))→r

((p∨q)∧(p→r)∧(q→r))→r的真值表如表1.47所示。由表1.47可以看出((p∨q)∧(p→r)∧(q→r))→r是重言式。

表1.47

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p∨q?0 0 1 1 1 1 1 1 p→r?1 1 1 1 0 1 0 1 q→r?(p∨q)∧(p→r)∧(q→r)?((p∨q)∧(p→r)∧(q→r))→r?1 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1

16

第1章 习题解答

⑹((p→q)∧(r→s))→((p∧r)→(q∧s))

((p→q)∧(r→s))→((p∧r)→(q∧s))的真值表如表1.48所示。由表1.48可以看出((p→q)∧(r→s))→((p∧r)→(q∧s))是重言式。

表1.48

p 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 q 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 r 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 s?0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 p→q?r→s?(p→q)∧(r→s)?p∧r?q∧s?(p∧r)→(q∧s)?1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 原公式?1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ⑺((p?q)∧(q?r))→(p?r)

((p?q)∧(q?r))→(p?r)的真值表如表1.49所示。由表1.49可以看出((p?q)∧(q?r))→(p?r)是重言式。

表1.49

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p?q 1 1 0 0 0 0 1 1 q?r 1 0 0 1 1 0 0 1 (p?q)∧(q?r) 1 0 0 0 0 0 0 1 p?r 1 0 1 0 0 1 0 1 ((p?q)∧(q?r))→(p?r) 1 1 1 1 1 1 1 1

17

第1章 习题解答

3. 用等价演算证明题2中的命题公式是重言式。 ⑴(p∧(p→q))→q ??(p∧(?p∨q))∨q ?(?p∨(p∧?q))∨q

?((?p∨p)∧(?p∨?q))∨q ?(?p∨?q)∨q ?T

⑵(?q∧(p→q))→?p ?(?q∧(?p∨q))→?p ??(?q∧(?p∨q))∨?p ?(q∨(p∧?q))∨?p ?(?p∨q)∨(p∧?q) ??(p∧?q)∨(p∧?q) ?T

⑶(?p∧(p∨q))→q ?(?p∧q)→q ??(?p∧q)∨q ?p∨?q∨q

?T ⑷((p→q)∧(q→r))→(p→r)

??((?p∨q)∧(?q∨r))∨(?p∨r) ?(p∧?q)∨(q∧?r)∨(?p∨r)

?(p∧?q)∨((?p∨q∨r)∧(?p∨?r∨r)) ?(p∧?q)∨(?p∨q∨r)

?(?p∨q∨r∨p)∧(?p∨q∨r∨?q) ?T

⑸((p∨q)∧(p→r)∧(q→r))→r ?((p∨q)∧(?p∨r)∧(?q∨r))→r ?((p∨q)∧(?(p∨q)∨r))→r ?((p∨q)∧r)→r ??((p∨q)∧r)∨r ??(p∨q)∨?r∨r ?T

⑹((p→q)∧(r→s))→((p∧r)→(q∧s))

??((?p∨q)∧(?r∨s))∨(?(p∧r)∨(q∧s)) ?((p∧?q)∨(r∧?s))∨((?p∨?r)∨(q∧s))

?((p∧?q)∨(r∧?s))∨((?p∨?r∨q)∧(?p∨?r∨s))

?((p∧?q)∨(r∧?s)∨(?p∨?r∨q))∧((p∧?q)∨(r∧?s)∨(?p∨?r∨s)) ?((r∧?s)∨((?p∨?r∨q∨p)∧(?p∨?r∨q∨?q)))∧((r∧?s)∨

18

第1章 习题解答

((?p∨?r∨s∨p)∧(?p∨?r∨s∨?q)))

?((r∧?s)∨T)∧((r∧?s)∨(?p∨?q∨?r∨s)) ?(r∧?s)∨(?p∨?q∨?r∨s)

?(?p∨?q∨?r∨s∨r)∧(?p∨?q∨?r∨s∨?s) ?T

⑺((p?q)∧(q?r))→(p?r)

?((?p∨q)∧(?q∨p)∧(?q∨r)∧(?r∨q))→(p?r)

??((?p∨q)∧(?q∨p)∧(?q∨r)∧(?r∨q))∨(p∧r)∨(?p∧?r) ?(p∧?q)∨(p∧r)∨(r∧?q)∨(q∧?r)∨(q∧?p)∨(?p∧?r) ?((p∧(?q∨r))∨?(?q∨r))∨(r∧?q)∨(q∧?p)∨(?p∧?r)

?((?(?q∨r)∨(?q∨r))∧(p∨?(?q∨r)))∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?(T∧(p∨?(?q∨r)))∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?p∨(q∧?r)∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?p∨(q∧?r)∨((q∧?p)∨(?p∧?r))∨(r∧?q) ?p∨(q∧?r)∨((?p∧(q∨?r))∨?(q∨?r)) ?p∨(q∧?r)∨?p∨(?q∧r) ?T

4.证明下列等价式： ⑴((p→r)∧(q→r)) ?(?p∨r)∧(?q∨r) ?(?p∧?q)∨r ??(p∨q)∨r ?(p∨q)→r

⑵(p→q)∧(p→?q) ?(?p∨q)∧(?p∨?q) ??p∨(q∧?q) ??p∨F ??p

⑶p∧(p→q) ?p∧(?p∨q)

?(p∧?p)∨(p∧q) ?F∨(p∧q) ?p∧q

19

第1章 习题解答

习题 1.5

1.求下列命题公式的析取范式。 ⑴(p∧?q)→r ??(p∧?q)∨r ??p∨q∨r ⑵?(p→q)→r ???(?p∨q)∨r ?(?p∨q)∨r ??p∨q∨r ⑶p∧(p→q) ? p∧(?p∨q) ?(p∧?p)∨(p∧q) ? p∧q

⑷(p→q)∧(q∨r) ?(?p∨q)∧(q∨r) ? q∨(?p∧r)

⑸?(p∨?q)∧(r→t) ?(?p∧q)∧(?r∨t)

?(?p∧q∧?r)∨(?p∧q∧t)

2. 求下列命题公式的合取范式。 ⑴?(p→q) ??(?p∨q) ?p∧?q

⑵?q∨(p∧q∧r)

?(?q∨p)∧(?q∨q)∧(?q∨r) ?(?q∨p)∧(?q∨r) ⑶(?p∧q)∨(p∧?q)

?((?p∧q)∨p)∧((?p∧q)∨?q))

?(?p∨p)∧(q∨p)∧(?p∨?q)∧(q∨?q) ?(p∨q)∧(?p∨?q) ⑷?(p?q)

??((p∧q)∨(?p∧?q)) ?(?p∨?q)∧(p∨q) ⑸?(p→q)→r ???(?p∨q)∨r ?(?p∨q)∨r ??p∨q∨r

20

第1章 习题解答

3.求下列命题公式的主析取范式，并求命题公式的成真赋值。 ⑴(p∧q)∨(p∧r)

作(p∧q)∨(p∧r)的真值表，如表1.50所示。

表1.50

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p∧q 0 0 0 0 0 0 1 1 p∧r 0 0 0 0 0 1 0 1 (p∧q)∨(p∧r) 0 0 0 0 0 1 1 1

由真值表可知，原式?(p∧?q∧r)∨(p∧q∧?r)∨(p∧q∧r)(主析取范式)?∑5,6,7 使得命题公式(p∧q)∨(p∧r)成真的赋值是：101，110，111。 ⑵?(p∨q)→(?p∧r) ???(p∨q)∨(?p∧r) ?(p∨q)∨(?p∧r)

?(p∨q∨?p)∧(p∨q∨r) ?p∨q∨r

?(?p∧?q∧r)∨(?p∧q∧?r)∨(?p∧q∧r)∨(p∧?q∧?r)∨ (p∧?q∧r)∨(p∧q∧?r)∨(p∧q∧r)(主析取范式) ?∑1,2,3,4,5,6,7

使得命题公式?(p∨q)→(?p∧r)成真的赋值是：001，010、011，100，101，110，111。 ⑶(?p∨?q)→(p??q)

作(?p∨?q)→(p??q)的真值表，如表1.51所示。

表1.51

p 0 0 1 1 q ?p ?q 0 1 0 1 1 1 0 0 1 0 1 0 ?p∨q 1 1 1 0 p?q 0 1 1 0 (p∨q)→(p?q) 0 1 1 1

由真值表可知:

原式?(?p∧q)∨(p∧?q)∨(p∧q) (主析取范式)?∑1,2,3

使得命题公式(?p∨?q)→(p??q)成真的赋值是：01，10，11。

21

第1章 习题解答

⑷(?p→q)→(p∨?q) ??(??p∨q)∨(p∨?q) ??(p∨q)∨(p∨?q) ?(?p∧?q)∨(p∨?q)

?(p∨?q∨?p)∧(p∨?q∨?q) ?p∨?q

?(?p∧?q)∨(p∧?q)∨(p∧q)(主析取范式) ?∑0,2,3

使得命题公式(?p→q)→(p∨?q)成真的赋值是：00,10,11。 ⑸(p→(q∧r))∧(?p→(?q∧?r)) ?(?p∨(q∧r))∧(??p∨(?q∧?r))

?(?p∨q)∧(?p∨r)∧(p∨?q)∧(p∨?r)

?(?p∨q∨r)∧(?p∨q∨?r)∧(?p∨q∨r)∧(?p∨?q∨r)∧(p∨?q∨r)∧ (p∨?q∨?r)∧(p∨q∨?r)∧(p∨?q∨?r)

?(?p∨q∨r)∧(?p∨q∨?r)∧(?p∨?q∨r)∧(p∨?q∨r)∧(p∨q∨?r)∧(p∨?q∨?r) ?(?p∧?q∧?r)∨(p∧q∧r)(主析取范式)

使得命题公式(p→(q∧r))∧(?p→(?q∧?r))成真的赋值是：000,111。 4. 求下列命题公式的主合取范式，并求命题公式的成假赋值。 ⑴(p→q)∧r ?(?p∨q)∧r

?(?p∨q∨r)∧(?p∨q∨?r)∧(?p∨r)∧(p∨r)

?(?p∨q∨r)∧(?p∨q∨?r)∧(?p∨q∨r)∧(?p∨?q∨r)∧(p∨q∨r)∧(p∨?q∨r) ?(?p∨q∨r)∧(?p∨q∨?r)∧(?p∨?q∨r)∧(p∨q∨r)∧(p∨?q∨r) ?∏0,2,4,5,6

使得命题公式(p→q)∧r成假的赋值是：000,010,100,101,110。 ⑵?(p→q)?(p→?q)

作?(p→q)?(p→?q)的真值表，如表1.52所示。

表1.52

p 0 0 1 1 q p→q ?(p→q) ?q 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 p→?q 1 1 1 0 ?(p→q)?(p→?q) 0 0 1 1

由真值表可知:

原式?(p∨q)∧(p∨?q)?∏0,1

使得命题公式?(p→q)?(p→?q)成假的赋值是：00,01。 ⑶?(p∨q)→(?p∧r)

22

第1章 习题解答

???(p∨q)∨(?p∧r) ?(p∨q)∨(?p∧r)

?(p∨q∨?p)∧(p∨q∨r) ?p∨q∨r ?∏0

使得命题公式?(p∨q)→(?p∧r)成假的赋值是：000。 ⑷?(p→?q)∧?p ??(?p∨?q)∧?p ?p∧q∧?p

?F ?∏0,1,2,3

使得命题公式?(p→?q)∧?p成假的赋值是：00,01,10,11。 ⑸(p→(q∨r))∨r ??p∨q∨r∨r ??p∨q∨r ?∏4

使得命题公式(p→(q∨r))∨r成假的赋值是：100。

5. 求下列命题公式的主析取范式，再用主析取范式求出主合取范式。 ⑴(p→q)∧(q→r) ?(?p∨q)∧(?q∨r)

?((?p∨q)∧?q)∨((?p∨q)∧r) ?(?p∧?q)∨(?p∧r)∨(q∧r)

?(?p∧?q∧r)∨(?p∧?q∧?r)∨(?p∧?q∧r)∨(?p∧q∧r)∨(?p∧q∧r)∨(p∧q∧r) ?(?p∧?q∧r)∨(?p∧?q∧?r)∨(?p∧q∧r)∨(p∧q∧r)(主析取范式) ?∑0,1,3,7 ?∏2,4,5,6

?(p∨?q∨r)∧(?p∨q∨r)∧(?p∨q∨?r)∧(?p∨?q∨r)(主合取范式) ⑵?(?p∨?q)∨r ?(p∧q)∨r

?(p∧q∧r)∨(p∧q∧?r)∨(p∧r)∨(?p∧r)

?(p∧q∧r)∨(p∧q∧?r)∨(p∧q∧r)∨(p∧?q∧r)∨(?p∧q∧r)∨(?p∧?q∧r) ?(p∧q∧r)∨(p∧q∧?r)∨(p∧?q∧r)∨(?p∧q∧r)∨(?p∧?q∧r)(主析取范式) ?∑1,3,5,6,7 ?∏0,2,4

?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)(主合取范式)

6. 求下列命题公式的主合取范式，再用主合取范式求出主析取范式。 ⑴(p?q)∧r

?(p→q)∧(q→p)∧r ?(?p∨q)∧(?q∨p)∧r

23

第1章 习题解答

?(?p∨q∨r)∧(?p∨q∨?r)∧(?q∨p∨r)∧(?q∨p∨?r)∧(?p∨r)∧(p∨r) ?(?p∨q∨r)∧(?p∨q∨?r)∧(p∨?q∨r)∧(p∨?q∨?r)∧(?p∨q∨r)∧ (?p∨?q∨r)∧(p∨q∨r)∧(p∨?q∨r)

?(?p∨q∨r)∧(?p∨q∨?r)∧(p∨?q∨r)∧(p∨?q∨?r)∧ (?p∨?q∨r)∧(p∨q∨r)(主合取范式)

?∏0,2,3,4,5,6?∑1,7?(?p∧?q∧r)∨(p∧q∧r)(主析取范式) ⑵(p∧q)→q ??(p∧q)∨q ??p∨?q∨q

?T(无主合取范式)

?∑0,1,2,3?(?p∧?q)∨(?p∧q)∨(p∧?q)∨(p∧q) 7.用主析取范式判断下列命题公式是否等价。 ⑴p→(q→r)和q→(p→r)

p→(q→r)??p∨(?q∨r)??p∨?q∨r

?(?p∧?q∧?r)∨(?p∧?q∧r)∨(?p∧q∧?r)∨(?p∧q∧r)∨ (p∧?q∧?r)∨(p∧?q∧r)∨(p∧q∧r)(主析取范式) ?∑0,1,2,3,4,5,7

q→(p→r)??q∨(?p∨r)??p∨?q∨r

?(?p∧?q∧?r)∨(?p∧?q∧r)∨(?p∧q∧?r)∨(?p∧q∧r)∨ (p∧?q∧?r)∨(p∧?q∧r)∨(p∧q∧r)(主析取范式) ?∑0,1,2,3,4,5,7

因为p→(q→r)与q→(p→r)的主析取范式相同，所以p→(q→r)?q→(p→r)。 ⑵(p→q)∧(p→r)和p→(q∧p)

(p→q)∧(p→r)?(?p∨q)∧(?p∨r)??p∨(q∧r) ?(?p∧q)∨(?p∧?q)∨(?p∧q∧r)∨(p∧q∧r)

?(?p∧q∧r)∨(?p∧q∧?r)∨(?p∧?q∧r)∨(?p∧?q∧?r)∨(?p∧q∧r)∨(p∧q∧r) ?(?p∧q∧?r)∨(?p∧?q∧r)∨(?p∧?q∧?r)∨(?p∧q∧r)∨(p∧q∧r)(主析取范式) ?∑0,1,2,3,7

p→(q∧p)??p∨(q∧p)?(?p∨q)∧(?p∨p)??p∨q ?(?p∧q)∨(?p∧?q)∨(?p∧q)∨(p∧q) ?(?p∧q)∨(?p∧?q)∨(p∧q) (主析取范式) ?∑0,1,3

因为(p→q)∧(p→r)与p→(q∧p)的主析取范式不相同，所以(p→q)∧(p→r)与p→(q∧p)不等价。

8. 用主合取范式判断下列命题公式是否等价。 ⑴(p→q)→r和p→(q→r)

(p→q)→r??(?p∨q)∨r?(p∧?q)∨r?(p∨r)∧(?q∨r)

?(p∨?q∨r)∧(p∨q∨r)∧(?p∨?q∨r) ?∏0,2,6

24

第1章 习题解答

p→(q→r)??p∨(?q∨r)??p∨?q∨r

?∏6

因为(p→q)→r与p→(q→r)的主合取范式不相同，所以(p→q)→r与p→(q→r)不等价。 ⑵(p∧?q)∨(?p∧q)和(p∨q)∧?(p∧q)

(p∧?q)∨(?p∧q)?∑1,2?∏0,3?(p∨q)∧(?p∨?q) (p∨q)∧?(p∧q)?(p∨q)∧(?p∨?q)?∏0,3

因为(p∧?q)∨(?p∧q)和(p∨q)∧?(p∧q)的主合取范式相同，所以(p∧?q)∨(?p∧q)? (p∨q)∧?(p∧q)。

25

第1章 习题解答

习题1.6

1.将下列命题公式用只含?，∧，∨的等价式表示。

⑴(p??q)→r??((?p∨?q)∧(q∨p))∨r?(p∧q)∨(?p∧?q)∨r ⑵?(p→(q?(q∧r)))??(?p∨((q∧q∧r)∨(?q∧?(q∧r))))

?p∧?(q∧r)∧(q∨(q∧r)) ?p∧(?q∨?r)∧q ?p∧q∧?r

⑶p?(p→q)?p?(?p∨q)

?(p∧?(?p∨q))∨(?p∧(?p∨q)) ?(p∧?q)∨?p ??p∨?q

⑷(p?q)?r?((p∧q)∨(?p∧?q))?r

?(((p∧q)∨(?p∧?q))∧r)∨(?((p∧q)∨(?p∧?q))∧?r) ?((p∧q∧r)∨(?p∧?q∧r))∨(((?p∨?q)∧(p∨q))∧?r) ?(p∧q∧r)∨(?p∧?q∧r)∨((?p∨?q)∧(p∨q)∧?r)

⑸(p?q)?(r→t)?((?p∨q)∧(?q∨p))?(?r∨t)

?((?p∨q)∧(?q∨p)∧?(?r∨t))∨(?((?p∨q)∧(?q∨p))∧(?r∨t)) ?((?p∨q)∧(?q∨p)∧(r∧?t))∨(((p∧?q)∨(q∧?p))∧(?r∨t))

2. 将下列命题公式用只含?，∨的等价式表示。 ⑴(p∧q)∧?p??((?p∨?q)∨p)

⑵p?q?(?p∨q)∧(?q∨p)??(?(?p∨q)∨?(?q∨p)) ⑶(p↑q)∧r??(p∧q)∧r??(?(?p∨?q)∨?r)

⑷p?q??(p?q)??(p∧q)∧?(?q∧?p) ??(?(?p∨?q)∨?(p∨q)) ⑸(p?q)∧r?(?p∨q)∧(?q∨p)∧r??(?(?p∨q)∨?(?q∨p)∨?r) 3. 将下列命题公式用只含?，∧的等价式表示。 ⑴?p∨?q∨(?r→p)

??p∨?q∨(r∨p) ??(p∧q∧?r∧?p)

⑵?(p∨q)→(?p?r)

?(p∨q)∨(?p∧r)∨(p∧?r)

??((?p∧?q)∧?(?p∧r)∧?(p∧?r))

⑶(?p∨?q)∨(p→?q)

?(?p∨?q)∨(?p∨?q) ??p∨?q ??(p∧q)

⑷(?p→q)→(p??q)

??(p∨q)∨?(p??q)

26

第1章 习题解答

?(?p∧?q)∨?((p∧?q)∨(?p∧q))

??(?(?p∧?q)∧?(?(p∧?q)∧?(?p∧q)))

⑸(p→(q∨r))∨(?p→r)

?(?p∨q∨r)∨(p∨r) ?T

4.下列结论是否成立？若成立，请证明。若不成立，举反例说明。 ⑴p↑q?q↑p

成立。p↑q??(p∧q)??(q∧p)?q↑p ⑵p↓q?q↓p

成立。p↓q??(p∨q)??(q∨p)?q↓p ⑶p↑(q↑r)?(p↑q)↑r

不成立。p↑(q↑r)?p↑?(q∧r)??(p∧?(q∧r))??p∨(q∧r)

?(?p∨q∨r)∧(?p∨q∨?r)∧(?p∨?q∨r)?∏4,5,6

而(p↑q)↑r??(p∧q)↑r??(?(p∧q)∧r)?(p∧q)∨?r

?(p∨q∨?r)∧(p∨?q∨?r)∧(?p∨q∨?r)?∏1,3,5

显然上式不成立

⑷p↓(q↓r)?(p↓q)↓r

不成立。p↓(q↓r)?p↓?(q∨r)??(p∨?(q∨r))??p∧(q∨r)

?(?p∧q∧r)∨(?p∧q∧?r)∨(?p∧?q∧r)?∑1,2,3

而(p↓q)↓r??(p∨q)↓r??(?(p∨q)∨r)?(p∨q)∧?r

?(p∧q∧?r)∨(p∧?q∧?r)∨(?p∧q∧?r)?∑2,4,6

显然上式不成立。 5.证明下列等价式。 ⑴?(p↑q)??p↓?q

证明：?(p↑q)??(p↑q)???(p∧q)?p∧q ?p↓?q ??(?p∨?q)? p∧q 所以：?(p↑q)??p↓?q ⑵?(p↓q)??p↑?q

证明：?(p↓q)???(p∨q)?p∨q ?p↑?q ??(?p∧?q)?p∨q 所以：?(p↓q)??p↑?q

6.将下列命题公式仅用“↓”表示。 ⑴?p?p↓p

⑵p∨q??(p↓q)?(p↓q)↓(p↓q)

⑶p∧q??(?p∨?q)? ?p↓?q? (p↓p)↓(q↓q) 7.将下列命题公式仅用“↑”表示。 ⑴?p??(p∧p)?p↑p

⑵p∨q??(?p∧?q)??p↑?q?(p↑p)↑(q↑q) ⑶p∧q???(p∧q)??(p↑q)?(p↑q)↑(p↑q)

27

第1章 习题解答

习题 1.7

1. 写出下列命题公式的对偶式。

⑴?(?p∧?q)∧r的对偶式是：?(?p∨?q)∨r ⑵(p∨?q)∧(r∨p)对偶式是(p∧?q)∨(r∧p) ⑶ p?q??(p?q)

??(p→q)∨?(q→p) ??(?p∨q)∨?(?q∨p) ?(p∧?q)∨(q∧?p)

所以p?q的对偶式是(p∨?q)∧(q∨?p) 而(p∨?q)∧(q∨?p)

?(?p→?q)∧(?q→?p) ??p??q ?p?q

???(p?q) ??(p?q)

所以p?q的对偶式是?(p?q) ⑷(p∧q)→r

??(p∧q)∨r ??p∨?q∨r

所以(p∧q)→r的对偶式是?p∧?q∧r ⑸(p∧q)↓r的对偶式是(p∨q)↑r ⑹(p↑q)→r??(p↑q)∨r

所以(p↑q)→r的对偶式是?(p↓q)∧r ⑺p→((q→r)∧(p∧?q))

??p∨((?q∨r)∧(p∧?q)) ?(?p∨?q)∧(?p∨?q∨r)

所以p→((q→r)∧(p∧?q))的对偶式是(?p∧?q)∨(?p∧?q∧r) ⑻(p?q)→r

??(p?q)∨r

??(p→q)∨?(q→p)∨r ??(?p∨q)∨?(?q∨p)∨r ?(p∧?q)∨(?p∧q)∨r

所以(p?q)→r的对偶式是(p∨?q)∧(?p∨q)∧r

2. 设p→q为公式，则q→p称为该公式的逆换式，?p→?q称为反换式，?q→?p称为逆反式。证明：

⑴公式与它的逆反式等价，即 p→q??q→?p 证明：p→q??p∨q

28

第1章 习题解答

而?q→?p???q∨?p??p∨q 所以p→q??q→?p

⑵公式的逆换式与公式的反换式等价，即 q→p??p→?q 证明：q→p??q∨p

而?p→?q???p∨?q?p∨?q??q∨p 所以q→p??p→?q

3.用真值表或等价演算证明下列蕴含式。 ⑴p∧q?p→q

证明：(p∧q)→(p→q)

??(p∧q)∨(?p∨q) ??p∨?q∨?p∨q ?T

所以，p∧q?p→q ⑵p→q?p→(p∧q)

证明：作(p→q)→(p→(p∧q))的真值表，如表1.53所示。

表1.53

p 0 0 1 1 q 0 1 0 1 p→q 1 1 0 1 p∧q 0 0 0 1 p→(p∧q) 1 1 0 1 (p→q)→(p→(p∧q)) 1 1 1 1

由以上真值表可知：(p→q)→(p→(p∧q))是一个永真式，所以p→q?p→(p∧q) ⑶p??p→q

证明：p→(?p→q)

??p∨??p∨q ??p∨p∨q ?T

所以，p??p→q

⑷p→(q→r)?(p→q)→(p→r)

证明：(p→(q→r))→((p→q)→(p→r))

??(?p∨?q∨r)∨(?(?p∨q)∨(?p∨r)) ?(p∧q∧?r)∨(p∧?q)∨?p∨r ?((p∧q∧?r))∨r)∨((p∧?q)∨?p)

?((p∨r)∧(q∨r)∧(?r∨r))∨((p∨?p)∧(?p∨?q)) ?((p∨r)∧(q∨r))∨?p∨?q

?((p∨r∨?p)∧(q∨r∨?p))∨?q ?q∨r∨?p∨?q ?1

29

第1章 习题解答

所以，p→(q→r)?(p→q)→(p→r) ⑸p∧(p→q)?q

证明：作(p∧(p→q))→q的真值表，如表1.54所示。

表1.54

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

由以上真值表可知：(p∧(p→q))→q是一个永真式，所以p∧(p→q)?q ⑹?q∧(p→q)??p

证明：作(p∧(p→q))→q的真值表，如表1.55所示。

表1.55

p 0 0 1 1 q ?q 0 1 0 1 1 0 1 0 p→q ?q∧(p→q) (?q∧(p→q))→?p 1 1 0 1 1 0 0 0 1 1 1 1

由以上真值表可知：(?q∧(p→q))→?p是一个永真式，所以?q∧(p→q)??p

4.用“假设前件为真，推证后件也为真或假设后件为假，推证前件也为假“的方法证明下列蕴含式。

⑴p∧q?p→q

证明：假设前件p∧q为真，证明后件p→q也为真。

因为p∧q为真，所以p为真并且q也为真，根据条件的定义可知p→q也为真。 所以，p∧q?p→q ⑵p→q?p→(p∧q)

证明:假设后件p→(p∧q)为假,证明前件p→q必为假；

因为p→(p∧q)为假，则p为真,q为假；根据条件的定义可知p→q也为假。 即：p→q?p→(p∧q) ⑶p??p→q

证明:假设前件p为真,则?p为假, 根据条件的定义可知?p→q必为真。 所以，原蕴含式成立。

⑷p→(q→r)?(p→q)→(p→r)

证明:假设后件(p→q)→(p→r)为假, 证明前件p→(q→r)必为假。

因为(p→q)→(p→r)为假，所以，p→q为真，p→r为假；因为p→r为假，所以p为真，

30

第1章 习题解答

r为假；所以，q必为真；

因为q为真，r为假，所以q→r 必为假；因为p为真，所以，p→(q→r)必为假。 所以，原蕴含式成立。 ⑸p∧(p→q)?q

证明：假设前件p∧(p→q)为真，证明后件q也为真。因为p∧(p→q)为真，所以p为真，p→q也为真，根据条件的定义q必为真。

所以，原蕴含式成立。 ⑹?q∧(p→q)??p

证明：假设前件?q∧(p→q)为真，证明后件?p也为真。

因为?q∧(p→q)为真，所以，?q为真，q为假，又因为p→q为真，根据条件的定义p为假，所以?p必为真。

所以，原蕴含式成立。

5.设A是任意的命题公式，证明A?A

证明：由条件的定义可知：A→A是一个永真式；根据蕴含式的定义可知A?A。

31

第1章 习题解答

习题 1.8

1.用全真值表或部分真值表证明下列各题的有效结论。 ⑴(p→(q→r))，p∧q?r

((p→(q→r))∧(p∧q))→r的全真值表如表1.56所示。

表1.56

p q 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 r 0 1 0 1 0 1 0 1 q→r 1 1 0 1 1 1 0 1 p→(q→r) p∧q (p→(q→r))∧(p∧q) ((p→(q→r))∧(p∧q))→r 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1

由真值表可知，((p→(q→r))∧(p∧q))→r是永真式，所以(p→(q→r))，p∧q?r。 ⑵?p∨q,?(q∧?r),?r??p

((?p∨q)∧(?(q∧?r))∧?r)→?p的全真值表如表1.57所示。

表1.57

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r ?p∨q ?r ?(q∧?r) (?p∨q)∧(?(q∧?r))∧?r ((?p∨q)∧(?(q∧?r))∧?r)→?p 0 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

由真值表可知：((?p∨q)∧(?(q∧?r))∧?r)→?p是永真式，所以?p∨q，?(q∧?r)，?r??p。

⑶?p∨q,r→?q?p→?r

((?p∨q)∧(r→?q))→(p→?r)的真值表如表1.58所示。

32

第1章 习题解答

表1.58

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 ?p∨q r→?q p→?r (?p∨q)∧(r→?q) ((?p∨q)∧(r→?q))→(p→?r) 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 由真值表可知：((?p∨q)∧(r→?q))→(p→?r)是永真式，所以?p∨q,r→?q?p→?r。 ⑷p→q，q→r?p→r

((p→q)∧(q→r))→(p→r)的真值表如表1.59所示。

表1.59

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p→q 1 1 1 1 0 0 1 1 q→r 1 1 0 1 1 1 0 1 p→r 1 1 1 1 0 1 0 1 (p→q)∧(q→r) 1 1 0 1 0 0 0 1 ((p→q)∧(q→r))→(p→r) 1 1 1 1 1 1 1 1 由真值表可知：((p→q)∧(q→r))→(p→r)是永真式，所以p→q，q→r?p→r。 ⑸p∨?p,p→q,?p→q?q

((p∨?p)∧(p→q)∧(?p→q))→q的真值表如表1.60所示。

表1.60

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r p∨?p p→q ?p→q (p∨?p)∧(p→q)∧(?p→q) ((p∨?p)∧(p→q)∧(?p→q))→q 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 由真值表可知：((p∨?p)∧(p→q)∧(?p→q))→q是永真式，所以p∨?p,p→q,?p→

33

第1章 习题解答

q?q。

⑹p?q，q?r?p?r

((p?q)∧(q?r))→(p?r)的真值表如表1.61所示。

表1.61

p q 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p?q 1 1 0 0 0 0 1 1 q?r 1 0 0 1 1 0 0 1 p?r 1 0 1 0 0 1 0 1 (p?q)∧(q?r) ((p?q)∧(q?r))→(p?r) 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1

由真值表可知：((p?q)∧(q?r))→(p?r)是永真式，所以p?q，q?r?p?r。 2.用等价演算法，主析取范式法或蕴含演算法证明上题中的各有效结论。 ⑴(p→(q→r)),p∧q?r ((p→(q→r))∧(p∧q))→r

??((p→(q→r))∧(p∧q))∨r ??((?p∨?q∨r)∧(p∧q))∨r ?(p∧q∧?r)∨?(p∧q)∨r ?(p∧q∧?r)∨?(p∧q∧?r) ?1

所以(p→(q→r)),p∧q?r ⑵?p∨q,?(q∧?r),?r??p

((?p∨q)∧(?(q∧?r))∧?r)→?p

??((?p∨q)∧(?(q∧?r))∧?r)∨?p ?((p∧?q)∨(q∧?r)∨r)∨?p ?(p∧?q)∨(q∧?r)∨r∨?p ?((p∧?q)∨?p)∨((q∧?r)∨r) ?(?p∨?q)∨(q∨r) ?1

所以?p∨q,?(q∧?r),?r??p ⑶?p∨q,r→?q?p→?r ((?p∨q)∧(r→?q))→(p→?r)

?((?p∨q)∧(?r∨?q))→(?p∨?r) ??((?p∨q)∧(?r∨?q))∨(?p∨?r) ?((p∧?q)∨(r∧q))∨(?p∨?r)

34

第1章 习题解答

?((p∧?q)∨?p)∨((r∧q)∨?r) ?(?p∨?q)∨(q∨?r)

?1

所以?p∨q,r→?q?p→?r ⑷p→q，q→r?p→r ((p→q)∧(q→r))→(p→r)

?((?p∨q)∧(?q∨r))→(?p∨r) ??((?p∨q)∧(?q∨r))∨(?p∨r) ?(p∧?q)∨(?r∧q)∨?p∨r ?((p∧?q)∨?p)∨((?r∧q)∨r) ?(?p∨?q)∨(q∨r) ?1

所以p→q，q→r?p→r ⑸p∨?p,p→q,?p→q?q

((p∨?p)∧(p→q)∧(?p→q))→q

?(1∧(?p∨q)∧(p∨q))→q ??((?p∨q)∧(p∨q))∨q ?(p∧?q)∨(?p∧?q)∨q ??q∨q ?1

所以p∨?p,p→q,?p→q?q ⑹p?q，q?r?p?r ((p?q)∧(q?r))→(p?r)

?((?p∨q)∧(?q∨p)∧(?q∨r)∧(?r∨q))→(p?r)

??((?p∨q)∧(?q∨p)∧(?q∨r)∧(?r∨q))∨(p∧r)∨(?p∧?r) ?(p∧?q)∨(p∧r)∨(r∧?q)∨(q∧?r)∨(q∧?p)∨(?p∧?r) ?((p∧(?q∨r))∨?(?q∨r))∨(r∧?q)∨(q∧?p)∨(?p∧?r)

?((?(?q∨r)∨(?q∨r))∧(p∨?(?q∨r)))∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?(T∧(p∨?(?q∨r)))∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?p∨(q∧?r)∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?p∨(q∧?r)∨((q∧?p)∨(?p∧?r))∨(r∧?q) ?p∨(q∧?r)∨((?p∧(q∨?r))∨?(q∨?r)) ?p∨(q∧?r)∨?p∨(?q∧r) ?T

所以p?q，q?r?p?r

3.推理证明下列各题的有效结论。 ⑴p→(q∨r)，(t∨s)→p，(t∨s)?q∨r 证明：

⑴t∨s

P

35

第1章 习题解答

⑵(t∨s)→p ⑶p

⑷p→(q∨r) ⑸q∨r

⑵p∧q，(p?q)→(t∨s)?(t∨s) 证明:

⑴p∧q ⑵p ⑶q ⑷p→q ⑸q→p

⑹(p→q)∧(q→p) ⑺p?q

⑻(p?q)→(t∨s) ⑼t∨s

P

T⑴⑵假言推理 P

T⑶⑷假言推理

P

T⑴化简律 T⑴化简律 T⑶例1.30(2) T⑵例1.30(2) T⑷⑸合取引入 T⑹双条件等价式 P

T⑺⑻假言推理

⑶?(p→q)→?(r∨s)，(q→p)∨?r,r?p?q 证明:

⑴r P ⑵(q→p)∨?r P ⑶q→p T⑴⑵析取三段论 ⑷r∨s T⑴附加律 ⑸?(p→q)→?(r∨s) P ⑹p→q T⑷⑸拒取式 ⑺(p→q)∧(q→p) T⑶⑹合取引入 ⑻p?q T⑹双条件等价式

⑷p∧q→r，?r∨s，?s??p∨?q 证明:

⑴?s P ⑵?r∨s P ⑶?r T⑴⑵析取三段论 ⑷p∧q→r P ⑸?(p∧q) T⑶⑷拒取式 ⑹?p∨?q T⑸德·摩根律

⑸p∨?p,p→q,?p→q?q

证明:

36

第1章 习题解答

⑴?q ⑵p→q ⑶?p ⑷?p→q ⑸q

⑹?q∧q(矛盾)

⑹?p∨?s，p→q，r→s??p∨?r 证明:

⑴?(?p∨?r) ⑵p∧r ⑶p ⑷r ⑸r→s ⑹s

⑺?p∨?s ⑻?p

⑼?p∧p(矛盾)

P(附加前提) P

T⑴⑵拒取式 P

T⑶⑷假言推理 T⑴⑸合取引入

P(附加前提) T⑴条件等价式 T⑵化简律 T⑵化简律 P

T⑷⑸假言推理 P

T⑹⑺析取三段论 T⑶⑻合取引入

4.用CP规则推证下列各题的有效结论。 ⑴?p∨q,r→?q?p→?r 证明:

⑴p P(附加前提) ⑵?p∨q P ⑶q T⑴⑵析取三段论 ⑷r→?q P ⑸?r T⑶⑷拒取式 ⑹p→?r CP规则

⑵p∨q→r∧s，s∨t→u?p→u

证明:

⑴p ⑵p∨q

⑶p∨q→r∧s ⑷r∧s ⑸s ⑹s∨t ⑺s∨t→u ⑻u

P(附加前提) T⑴附加律 P

T⑵⑶假言推理 T⑷化简律 T⑸附加律 P

T⑹⑺假言推理

37

第1章 习题解答

⑼p→u

CP规则

⑶p→(q∧r)，?q∨s，(t→?u)→?s，q→(p∧?t)?q→t 证明:

⑴q P(附加前提) ⑵?q∨s P ⑶s T⑴⑵析取三段论 ⑷(t→?u)→?s P ⑸?(t→?u) T⑶⑷拒取式 ⑹?(? t∨?u) T⑸条件等价式 ⑺t∧u T⑹德·摩根律 ⑻t T⑺化简律 ⑼q→t CP规则

⑷p∨q，p→r，q→s?s∨r

证明:因为s∨r??s→r，原题可改写为：p∨q，p→r，q→s??s→r。

⑴?s P(附加前提) ⑵q→s P ⑶?q T⑴⑵拒取式 ⑷p∨q P ⑸p T⑶⑷析取三段论 ⑹p→r P ⑺r T⑸⑹假言推理 ⑻?s→r CP规则

⑸p∧q→r，?r∨s，p→?s?p→?q

证明:

⑴p

⑵p→?s ⑶?s ⑷?r∨s ⑸?r

⑹p∧q→r ⑺?(p∧q) ⑻?p∨?q ⑼?q ⑽p→?q

⑹p→r∧q，?s∨p，r?s→q

P(附加前提) P

T⑴⑵假言推理 P

T⑶⑷析取三段论 P

T⑸⑹拒取式 T⑺德·摩根律 T⑴⑻析取三段论 CP规则

38

第1章 习题解答

证明:

⑴s

⑵?s∨p ⑶p

⑷p→r∧q ⑸r∧q ⑹q ⑺s→q

5.用归谬法推证下列各题的有效结论。 ⑴p∧q，(p?q)→(t∨s)?t∨s 证明:

⑴?(t∨s)

⑵(p?q)→(t∨s) ⑶?(p?q)

⑷?((p∧q)∨(?p∧?q)) ⑸?(p∧q)∧? (?p∧?q) ⑹?(p∧q) ⑺p∧q

⑻(p∧q)∧?(p∧q)(矛盾)

⑵r→?q，r∨s，s→?q，p→q??p 证明:

⑴??p ⑵p ⑶p→q ⑷q

⑸r→?q ⑹?r ⑺r∨s ⑻s

⑼s→?q ⑽?q

⑾q∧?q（矛盾）

⑶p→q，(?q∨r)∧?r，?(?p∧s)??s 证明:

⑴??s ⑵s

P(附加前提) P

T⑴⑵析取三段论 P

T⑶⑷假言推理 T⑸化简律 CP规则

P(附加前提) P

T⑴⑵拒取式 T⑶例1.17 T⑷德·摩根律 T⑸化简律 P

T⑹⑺合取引入

P(附加前提) T⑴双重否定律 P

T⑵⑶假言推理 P

T⑷⑸拒取式 P

T⑹⑺析取三段论 P

T⑻⑼假言推理 T⑷⑽合取引入

P(附加前提) T⑴双重否定律

39

第1章 习题解答

⑶?(?p∧s) ⑷p∨?s ⑸p ⑹p→q ⑺q

⑻(?q∨r)∧?r ⑼?q∨r ⑽?r ⑾r

⑿r∧?r(矛盾)

P

T⑶德·摩根律 T⑵⑷析取三段论 P

T⑸⑹假言推理 P

T⑻化简律 T⑻化简律

T⑺⑼析取三段论 T⑽⑾合取引入

⑷(p→q)∧(r→s)，(q→t)∧(s→u)，?(t∧u)，p→r??p 证明:

⑴??p P(附加前提) ⑵p T⑴双重否定律 ⑶p→r P ⑷r T⑵⑶假言推理 ⑸(p→q)∧(r→s) P ⑹p→q T⑸化简律 ⑺r→s T⑸化简律 ⑻q T⑵⑹假言推理 ⑼s T⑷⑺假言推理 ⑽(q→t)∧(s→u) P ⑾q→t T⑽化简律 ⑿s→u T⑽化简律 ⒀t T⑻⑾假言推理 ⒁u T⑼⑿假言推理 ⒂t∧u T⒀⒁合取引入 ⒃?(t∧u) P ⒄(t∧u)∧(?(t∧u))(矛盾) T⒂⒃合取引入

⑸p→(q∨r)，(t∨s)→p，(t∨s)?q∨r

证明：

⑴?(q∨r) ⑵p→(q∨r) ⑶?p

⑷(t∨s)→p ⑸?(t∨s) ⑹(t∨s)

P(附加前提) P

T⑴⑵拒取式 P

T⑶⑷拒取式 P

40

第1章 习题解答

⑺?(t∨s)∧(t∨s)(矛盾)

T⑸⑹合取引入

⑹p→q，r→?q，r??p 证明：

⑴??p P(附加前提) ⑵p T⑴双重否定律 ⑶p→q P ⑷q T⑵⑶假言推理 ⑸r→?q P ⑹?r T⑷⑸拒取式 ⑺r P ⑻r∧?r（矛盾） T⑹⑺合取引入

6. 证明下面各命题推得的结论是有效的：如果今天是星期三，那么我有一次离散数学或数字逻辑测验。如果离散数学课老师有事，那么没有离散数学测验。今天是星期三且离散数学老师有事。所以，我有一次数字逻辑测验。

证明：设 p：今天是星期三。

q：我有一次离散数学测验。 r：我有一次数字逻辑测验。 s：离散数学课老师有事。

该推理就是要证明：p→(q∨r)，s→?q，p∧s?r

⑴p∧s P ⑵p T⑴化简律 ⑶s T⑴化简律 ⑷s→?q P ⑸?q T⑶⑷假言推理 ⑹p→(q∨r) P ⑺q∨r T⑵⑹假言推理 ⑻r T⑸⑺析取三段论

41

第1章 习题解答

⑺?(t∨s)∧(t∨s)(矛盾)

T⑸⑹合取引入

⑹p→q，r→?q，r??p 证明：

⑴??p P(附加前提) ⑵p T⑴双重否定律 ⑶p→q P ⑷q T⑵⑶假言推理 ⑸r→?q P ⑹?r T⑷⑸拒取式 ⑺r P ⑻r∧?r（矛盾） T⑹⑺合取引入

6. 证明下面各命题推得的结论是有效的：如果今天是星期三，那么我有一次离散数学或数字逻辑测验。如果离散数学课老师有事，那么没有离散数学测验。今天是星期三且离散数学老师有事。所以，我有一次数字逻辑测验。

证明：设 p：今天是星期三。

q：我有一次离散数学测验。 r：我有一次数字逻辑测验。 s：离散数学课老师有事。

该推理就是要证明：p→(q∨r)，s→?q，p∧s?r

⑴p∧s P ⑵p T⑴化简律 ⑶s T⑴化简律 ⑷s→?q P ⑸?q T⑶⑷假言推理 ⑹p→(q∨r) P ⑺q∨r T⑵⑹假言推理 ⑻r T⑸⑺析取三段论

41

本文来源：https://www.bwwdw.com/article/h05p.html