离散数学第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是素数。

⑶ 若地球上没有树木，则人类不能生存。

⑷ 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；该命题是真命题。

习题

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. 用符号形式写出下列命题。

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

解：⑴ p：上午下雨；q：我去看电影；r：我在家读书；s：我在家看报；原命题符

号化为：（p→q）∧（p→r∨s）。

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

习题

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

⑴AA

⑵若AB，则BA

⑶若AB，BC，则AC

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

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

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

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

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

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

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的真值表如表所示。

表

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

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

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

表

p 0 q 0 r 0 q∨r 0 p→(q∨r) 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 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) 的真值表如表所示。

表

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的真值表如表所示。

表

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，使得公式(p∧q)∨(r∧q)→r成假的赋值是：100。

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

表

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 1 1 0 0 p→(p∧(p→(p∧q))→q) 0 0 0 0 1 1 1 1 ((p→(p∧q))→r)∨(q∧1 1 1 1 0 1 1 1 r 1 1 1 1 0 1 0 1 q∧r 0 0 1 0 0 0 1 0 r)

使得公式((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的真值表如表所示。

表

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

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

表

q。

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和⑶(p↔q)p↔q

q→p的真值表完全相同，所以p→qq→p。

证明：证明(p↔q)和p↔

p 0 0 1 1 q的真值表如表所示。

表

q p↔q 0 1 0 1 1 0 0 1 (p↔q)0 1 1 0 qp↔1 0 1 0 0 1 1 0 q

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

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

表

q。

p 0 0 0 0 1 1 1 1 q 0 r q→rp→(q→r)p∧q(p∧q)→r0 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)的真值表如表所示。

表

p 0 0 1 1 q q→p p→(q→p)0 1 0 1 1 0 1 1 1 1 1 1 p→p1 1 0 0 q1 0 1 0 q1 1 1 0 p→(p→q)1 1 1 1

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

⑹(p↔q)(p∨q)∧(p∧q)

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

表

p 0 0 1 1 q p↔q 0 1 0 1 1 0 0 1 (p↔q)0 1 1 0 (p∧(p∨q)∧(p∧p∨qp∧q0 1 1 1 0 0 0 1 q)1 1 1 0 q)0 1 1 0

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

⑺(p↔q)(p∧q)∨(p∧q)

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

表

(p↔q)(p∨

p 0 0 1 1 q p↔q 0 1 0 1 1 0 0 1 (p↔qp∧)0 1 1 0 q0 0 1 0 p∧q(p∧q)∨(p∧q)0 1 0 0 0 1 1 0

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

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

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

表

(pp 0 0 0 0 1 1 1 q r q∨rp→(q∨r)0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 0 1 0 1 (p∧q)qp∧q1 1 0 0 1 1 0 0 0 0 0 1 1 0 →r1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1

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

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) ⑻p→(q∨r)

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

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

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

表

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

p∧(q∧r)

p 0 0 0 0 1 1 1 1 q 0 r p∨q(p∨q)∨rq∨rp∨(q∨r)0 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 1 0 0 0 1 0 1 1 0 1 1

表

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r p∧q(p∧q)∧rq∧rp∧(q∧r)0 1 0 1 0 1 0 1 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)

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

表

p 0 0 0 0 1 1 1 1 q 0 r 0 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 1 0 0 0 1 0 1 1 0 1 1

表

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→qq→p

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

表

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↔qp↔q

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

表

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↔1 0 0 1 q

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

习题

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.用真值表证明下列命题公式是重言式。 ⑴(p∧(p→q))→q

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

表

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

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

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

表

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

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

(p∧(p∨q))→q的真值表如表所示。由表可以看出(

表

p∧(p∨q))→q是重言式。

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

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

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

表

p 0 0 0 0 1 1 1 1 q r p→q 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 (p→q)∧(q→q→r 1 1 0 1 1 1 0 1 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的真值表如表所示。由表可以看出((p∨q)∧(p→r)∧(q→r))→r是重言式。

表

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

⑹((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 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 q r 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 (p→q)∧(r→(p∧r)→(q∧sp→qr→s0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 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 s)1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 p∧rq∧s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 s)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)的真值表如表所示。由表可以看出((p↔q)∧(q↔r))→(p↔r)是重言式。

表

p 0 0 0 q 0 0 1 r 0 1 0 p↔q 1 1 0 q↔r 1 0 0 (p↔q)∧(q↔r) 1 0 0 p↔r 1 0 1 ((p↔q)∧(q↔r))→(p↔r) 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 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∨s))

((r∧s)∨((p∨r∨q∨p)∧(p∨r∨q∨q)))∧((r∧s)∨ ((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)∨(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)

r∨

p∧

p∧q

习题

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

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

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

表

p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r p∧q 0 1 0 1 0 1 0 1 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)的真值表，如表所示。

表

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

由真值表可知:

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

使得命题公式(p∨q)→(p↔q)成真的赋值是：01，10，11。 ⑷(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)的真值表，如表所示。

表

(p→p 0 0 1 1 q p→q 0 1 0 1 1 1 0 1 q) 0 0 1 0 q p→q 1 0 1 0 1 1 1 0 (p→q)↔(p→0 0 1 1 q)

由真值表可知:

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

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

(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∧

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

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

(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

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)。

习题

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)

(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↑qq↑p 成立。p↑q(p∧q)(q∧p)q↑p ⑵p↓qq↓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.将下列命题公式仅用“↓”表示。 ⑴pp↓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)

习题

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→qq→p 证明：p→qp∨q 而q→pq∨pp∨q 所以p→qq→p

⑵公式的逆换式与公式的反换式等价，即 q→pp→q 证明：q→pq∨p 而p→qp∨qp∨qq∨p 所以q→pp→q

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

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

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

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

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

表

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

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

⑶pp→q

证明：p→(p→q)

pp∨p∨q p∨p∨q

T

所以，pp→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

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

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

表

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

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

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

表

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

由以上真值表可知：(q∧(p→q))→p是一个永真式，所以q∧(p→q)p 4.用“假设前件为真，推证后件也为真或假设后件为假，推证前件也为假“的方法证

明下列蕴含式。

⑴p∧qp→q

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

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

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

因为p→(p∧q)为假，则p为真,q为假；根据条件的定义可知p→q也为假。 即：p→qp→(p∧q) ⑶pp→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为真，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是任意的命题公式，证明AA

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

习题

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

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

表

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

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

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

表

r。

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

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

⑶p∨q,r→qp→r

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

表

r→p 0 0 0 0 1 1 1 1 p→r 1 1 1 1 1 0 1 0 (p∨q)∧(r→((p∨q)∧(r→q))→(pq) 1 1 1 0 0 0 1 0 →1 1 1 1 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 1 1 1 0 1 1 1 0 r) 由真值表可知：((p∨q)∧(r→q))→(p→r)是永真式，所以p∨q,r→q→r。

⑷p→q，q→rp→r

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

表

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

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

表

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

⑹p↔q，q↔rp↔r

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

表

p q r 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 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) 1 0 0 0 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↔rp↔r。 2.用等价演算法，主析取范式法或蕴含演算法证明上题中的各有效结论。 ⑴(p→(q→r)),p∧qr

((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∧qr ⑵p∨q,(q∧r),rp

((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),rp ⑶p∨q,r→qp→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) ((p∧q)∨p)∨((r∧q)∨r) (p∨q)∨(q∨r) 1

所以p∨q,r→qp→r ⑷p→q，q→rp→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→rp→r ⑸p∨p,p→q,p→qq

((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→qq ⑹p↔q，q↔rp↔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∧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↔rp↔r

3.推理证明下列各题的有效结论。

⑴p→(q∨r)，(t∨s)→p，(t∨s)q∨r 证明：

⑴t∨s P ⑵(t∨s)→p P ⑶p T⑴⑵假言推理 ⑷p→(q∨r) P ⑸q∨r T⑶⑷假言推理

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

⑴p∧q P ⑵p T⑴化简律 ⑶q T⑴化简律 ⑷p→q T⑶例(2) ⑸q→p T⑵例(2) ⑹(p→q)∧(q→p) T⑷⑸合取引入 ⑺p↔q T⑹双条件等价式 ⑻(p↔q)→(t∨s) P ⑼t∨s T⑺⑻假言推理

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

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

⑺(p→q)∧(q→p) ⑻p↔q

⑷p∧q→r，r∨s，sp∨q

证明:

⑴s ⑵r∨s ⑶r ⑷p∧q→r ⑸(p∧q) ⑹p∨q ⑸p∨p,p→q,p→qq 证明:

⑴q ⑵p→q ⑶p ⑷p→q ⑸q ⑹q∧q(矛盾) ⑹p∨s，p→q，r→sp∨r

证明:

⑴(p∨r) ⑵p∧r ⑶p ⑷r ⑸r→s ⑹s ⑺p∨s ⑻p ⑼p∧p(矛盾) 4.用CP规则推证下列各题的有效结论。P P

T⑴⑵析取三段论 T⑴附加律 P

T⑷⑸拒取式 T⑶⑹合取引入 T⑹双条件等价式

P P

T⑴⑵析取三段论 P

T⑶⑷拒取式 T⑸德·摩根律

P(附加前提) P

T⑴⑵拒取式 P

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

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

T⑷⑸假言推理 P

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

⑴p∨q,r→qp→r 证明:

⑴p P(附加前提) ⑵p∨q P

⑶q T⑴⑵析取三段论 ⑷r→q P

⑸r T⑶⑷拒取式 ⑹p→r CP规则

⑵p∨q→r∧s，s∨t→up→u 证明:

⑴p P(附加前提) ⑵p∨q T⑴附加律 ⑶p∨q→r∧s P

⑷r∧s T⑵⑶假言推理 ⑸s T⑷化简律 ⑹s∨t T⑸附加律 ⑺s∨t→u P

⑻u T⑹⑺假言推理 ⑼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→ss∨r 证明:因为s∨rs→r，原题可改写为：p∨q，p→r，q→s⑴s P(附加前提) ⑵q→s P ⑶q T⑴⑵拒取式 ⑷p∨q P ⑸p T⑶⑷析取三段论

→r。s

⑹p→r ⑺r ⑻s→r

⑸p∧q→r，r∨s，p→sp→q 证明:

⑴p ⑵p→s ⑶s ⑷r∨s ⑸r ⑹p∧q→r ⑺(p∧q) ⑻p∨q ⑼q ⑽p→q

⑹p→r∧q，s∨p，rs→q 证明:

⑴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→qp

P

T⑸⑹假言推理 CP规则

P(附加前提) P

T⑴⑵假言推理 P

T⑶⑷析取三段论P

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

P(附加前提) P

T⑴⑵析取三段论P

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

P(附加前提) P

T⑴⑵拒取式 T⑶例

T⑷德·摩根律 T⑸化简律 P

T⑹⑺合取引入

证明:

⑴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 ⑶(p∧s) ⑷p∨s ⑸p ⑹p→q ⑺q ⑻(q∨r)∧r ⑼q∨r ⑽r ⑾r ⑿r∧r(矛盾) ⑷(p→q)∧(r→s)，(q→t)∧(s→u)，证明:

⑴p ⑵p ⑶p→r ⑷r ⑸(p→q)∧(r→s) ⑹p→q ⑺r→s ⑻q ⑼s ⑽(q→t)∧(s→u) P(附加前提) T⑴双重否定律 P

T⑵⑶假言推理 P

T⑷⑸拒取式 P

T⑹⑺析取三段论 P

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

s

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

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

T⑸⑹假言推理 P

T⑻化简律 T⑻化简律

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

(t∧u)，p→rp

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

T⑵⑶假言推理 P

T⑸化简律 T⑸化简律 T⑵⑹假言推理 T⑷⑺假言推理 P

⑾q→t ⑿s→u ⒀t ⒁u ⒂t∧u ⒃(t∧u) ⒄(t∧u)∧(

T⑽化简律 T⑽化简律 T⑻⑾假言推理 T⑼⑿假言推理 T⒀⒁合取引入 P

(t∧u))(矛盾) T⒂⒃合取引入

⑸p→(q∨r)，(t∨s)→p，(t∨s)q∨r 证明：

⑴(q∨r) P(附加前提) ⑵p→(q∨r) P ⑶p T⑴⑵拒取式 ⑷(t∨s)→p P ⑸(t∨s) T⑶⑷拒取式 ⑹(t∨s) P

⑺(t∨s)∧(t∨s)(矛盾) T⑸⑹合取引入

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

⑴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∧sr

⑴p∧s P ⑵p T⑴化简律 ⑶s T⑴化简律

⑷s→q ⑸q ⑹p→(q∨r) ⑺q∨r ⑻r P

T⑶⑷假言推理 P

T⑵⑹假言推理 T⑸⑺析取三段论