习题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是素数。
⑶ 若地球上没有树木，则人类不能生存。 ⑷ 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进制)
⑺ 若两圆O 1，O 2的面积相等，则它们的半径相等，反之亦然。
⑻ 当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设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 ：两圆O 1,O 2的面积相等；q ：两圆O 1,O 2的半径相等；原命题符号化为：p q ；该命题是真命题。
⑻ p ：王小红心情愉快；q ：王小红唱歌；原命题符号化为：p q ；该命题是真命题。
习题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. 用符号形式写出下列命题。
⑴假如上午不下雨，我去看电影，否则就在家里读书或看报。 ⑵我今天进城，除非下雨。 ⑶仅当你走，我将留下。
解：⑴ p ：上午下雨；q ：我去看电影；r ：我在家读书；s ：我在家看报；原命题符号化为：（⌝p →q ）∧（p →r ∨s ）。
⑵ p ：我今天进城；q ：天下雨；原命题符号化为：⌝q →p 。 ⑶ p ：你走；q ：我留下；原命题符号化为：q →p 。
习题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
使得公式q ∧(p →q ) →p 成真的赋值是：00，10，11，使得公式q ∧(p →q ) →p 成假的赋值是：01。
⑵ p →(q ∨r ) 的真值表如表1.25所示。
表1.25
使得公式p →(q ∨r ) 成真的赋值是：000，001，010，011，101，110，111，使得公式p →(q ∨r ) 成假的赋值是：100。
⑶ (p ∨q ) (q ∨p ) 的真值表如表1.26所示。
表1.26
所有的赋值均使得公式(p ∨q ) (q ∨p ) 成真，即(p ∨q ) (q ∨p ) 是一个永真式。 ⑷ (p ∧⌝q ) ∨(r ∧q ) →r 的真值表如表1.27所示。
表1.27
111，
使得公式(p ∧⌝q ) ∨(r ∧q ) →r 成假的赋值是：100。
⑸((⌝p →(p ∧⌝q )) →r ) ∨(q ∧⌝r ) 的真值表如表1.28所示。
表1.28
使得公式((⌝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 →q ) 和p ∧⌝q 的真值表完全相同，所以⌝(p →q ) ⇔p ∧⌝q 。 ⑵p →q ⇔⌝q →⌝p
证明：证明p →q ⇔⌝q →⌝p 的真值表如表1.30所示。
表1.30
由上表可见：p →q 和⌝q →⌝p 的真值表完全相同，所以p →q ⇔⌝q →⌝p 。
⑶⌝(p q ) ⇔p ⌝q
证明：证明⌝(p q ) 和p ⌝q 的真值表如表1.31所示。
表1.31
由上表可见：⌝(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 →(q →r ) ⇔(p ∧q ) →r 。 ⑸p →(q →p ) ⇔ ⌝p →(p →⌝q )
证明：证明p →(q →p ) 和⌝p →(p →⌝q ) 的真值表如表1.33所示。
表1.33
由上表可见：p →(q →p ) 和⌝p →(p →⌝q ) 的真值表完全相同，且都是永真式，所以p →(q →p ) ⇔⌝p →(p →⌝q ) 。
⑹⌝(p q ) ⇔(p ∨q ) ∧⌝(p ∧q )
证明：证明⌝(p q ) 和(p ∨q ) ∧⌝(p ∧q ) 的真值表如表1.34所示。
表1.34
由上表可见：⌝(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 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 →(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 )
(条件等价式) (德·摩根律) (条件等价式) (双重否定律) (交换律)
(条件等价式) (双条件等价式) (条件等价式) (德·摩根律) (分配律) (分配律) (交换律) (条件等价式) (双条件等价式) (条件等价式) (结合律)
(德·摩根律) (条件等价式) (条件等价式)
(条件等价式)
(例1.17) (德·摩根律) (德·摩根律)
(双条件等价式) (条件等价式) (德·摩根律)
⑻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
表1.38
由真值表可知结合律成立。
⑵分配律：p ∧(q ∨r ) ⇔(p ∧q ) ∨(p ∧r ) ，
p ∨(q ∧r ) ⇔(p ∨q ) ∧(p ∨r )
证明：证明合取对析取的分配律的真值表如表1.39所示，析取对合取的的分配律的真值表如表1.40所示。
表1.39
表1.40
由真值表可知分配律成立。 ⑶假言易位式：p →q ⇔⌝q →⌝p
证明：证明假言易位式的真值表如表1.41所示。
表1.41
由真值表可知假言易位律成立。
⑷双条件否定等价式：p q ⇔⌝p ⌝q
证明：证明双条件否定的真值表如表1.42所示。
表1.42
由真值表可知双条件否定等价式成立。
习题 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. 用真值表证明下列命题公式是重言式。
（条件等价式） （德·摩根律） （吸收律） （条件等价式） （德·摩根律） （结合律、矛盾律） （条件等价式） （分配律）
（同一律、矛盾律） （条件等价式） （德·摩根律） （零律、排中律） （条件等价式） （吸收律） （假言易位式）
（条件等价式） （德·摩根律） （分配律）
（同一律、排中律、零律）（分配律）
（条件等价式）
（条件等价式）
⑴(p ∧(p →q )) →q
(p ∧(p →q )) →q 的真值表如表1.43所示。由表1.43可以看出(p ∧(p →q )) →q 是重言式。
表1.43
⑵(⌝q ∧(p →q )) →⌝p
(⌝q ∧(p →q )) →⌝p 的真值表如表1.44所示。由表1.44可以看出(⌝q ∧(p →q )) →⌝p 是重言式。
表1.44
⑶(⌝p ∧(p ∨q )) →q
(⌝p ∧(p ∨q
)) →q 的真值表如表1.45所示。由表1.45可以看出(⌝p ∧(p ∨q )) →q 是重言式。
表1.45
⑷((p →q ) ∧(q →r )) →(p →r )
((p →q ) ∧(q →r )) →(p →r ) 的真值表如表1.46所示。由表1.46可以看出((p →q ) ∧(q →r )) →(p →r ) 是重言式。
表1.46
⑸((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 →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 q ) ∧(q r )) →(p r )
((p q ) ∧(q r )) →(p r ) 的真值表如表1.49所示。由表1.49可以看出((p q ) ∧(q r )) →(p r ) 是重言式。
表1.49
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 ) ∨
((⌝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
习题 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
3. 求下列命题公式的主析取范式，并求命题公式的成真赋值。 ⑴(p ∧q ) ∨(p ∧r )
作(p ∧q ) ∨(p ∧r ) 的真值表，如表1.50所示。
表1.50
由真值表可知，原式⇔(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 ∧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 ) 的真值表，如表1.52所示。
表1.52
由真值表可知:
原式⇔(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 ∧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
⇔(⌝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.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 )
⇔(⌝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 )
习题 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
而⌝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 →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
所以，p →(q →r ) ⇒(p →q ) →(p →r ) ⑸p ∧(p →q ) ⇒q
证明：作(p ∧(p →q )) →q 的真值表，如表1.54所示。
表1.54
由以上真值表可知：(p ∧(p →q )) →q 是一个永真式，所以p ∧(p →q ) ⇒q ⑹⌝q ∧(p →q ) ⇒⌝p
证明：作(p ∧(p →q )) →q 的真值表，如表1.55所示。
表1.55
由以上真值表可知：(⌝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 为真，
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 。
习题 1.8
1. 用全真值表或部分真值表证明下列各题的有效结论。 ⑴(p →(q →r )) ，p ∧q ⇒r
((p →(q →r )) ∧(p ∧q )) →r 的全真值表如表1.56所示。
表1.56
由真值表可知，((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 ∨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所示。
表1.58
→⌝r 。 ⑷p →q ，q →r ⇒p →r
((p →q ) ∧(q →r )) →(p →r )
的真值表如表1.59所示。
表1.59
由真值表可知：((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 ∨⌝p ) ∧(p →q ) ∧(⌝p →q )) →q 是永真式，所以p ∨⌝p , p →q , ⌝p →
q ⇒q 。
⑹p q ，q r ⇒p r
((p q ) ∧(q r )) →(p r ) 的真值表如表1.61所示。
表1.61
由真值表可知：((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 )
⇔((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
⑵(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
证明:
⑵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
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 ⑹⑺假言推理
⑶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 规则
证明:
⑴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 ⑴双重否定律
⑶⌝(⌝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
第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.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进制)
⑺ 若两圆O 1，O 2的面积相等，则它们的半径相等，反之亦然。
⑻ 当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设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 ：两圆O 1,O 2的面积相等；q ：两圆O 1,O 2的半径相等；原命题符号化为：p q ；该命题是真命题。
⑻ p ：王小红心情愉快；q ：王小红唱歌；原命题符号化为：p q ；该命题是真命题。
习题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. 用符号形式写出下列命题。
⑴假如上午不下雨，我去看电影，否则就在家里读书或看报。 ⑵我今天进城，除非下雨。 ⑶仅当你走，我将留下。
解：⑴ p ：上午下雨；q ：我去看电影；r ：我在家读书；s ：我在家看报；原命题符号化为：（⌝p →q ）∧（p →r ∨s ）。
⑵ p ：我今天进城；q ：天下雨；原命题符号化为：⌝q →p 。 ⑶ p ：你走；q ：我留下；原命题符号化为：q →p 。
习题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
使得公式q ∧(p →q ) →p 成真的赋值是：00，10，11，使得公式q ∧(p →q ) →p 成假的赋值是：01。
⑵ p →(q ∨r ) 的真值表如表1.25所示。
表1.25
使得公式p →(q ∨r ) 成真的赋值是：000，001，010，011，101，110，111，使得公式p →(q ∨r ) 成假的赋值是：100。
⑶ (p ∨q ) (q ∨p ) 的真值表如表1.26所示。
表1.26
所有的赋值均使得公式(p ∨q ) (q ∨p ) 成真，即(p ∨q ) (q ∨p ) 是一个永真式。 ⑷ (p ∧⌝q ) ∨(r ∧q ) →r 的真值表如表1.27所示。
表1.27
111，
使得公式(p ∧⌝q ) ∨(r ∧q ) →r 成假的赋值是：100。
⑸((⌝p →(p ∧⌝q )) →r ) ∨(q ∧⌝r ) 的真值表如表1.28所示。
表1.28
使得公式((⌝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 →q ) 和p ∧⌝q 的真值表完全相同，所以⌝(p →q ) ⇔p ∧⌝q 。 ⑵p →q ⇔⌝q →⌝p
证明：证明p →q ⇔⌝q →⌝p 的真值表如表1.30所示。
表1.30
由上表可见：p →q 和⌝q →⌝p 的真值表完全相同，所以p →q ⇔⌝q →⌝p 。
⑶⌝(p q ) ⇔p ⌝q
证明：证明⌝(p q ) 和p ⌝q 的真值表如表1.31所示。
表1.31
由上表可见：⌝(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 →(q →r ) ⇔(p ∧q ) →r 。 ⑸p →(q →p ) ⇔ ⌝p →(p →⌝q )
证明：证明p →(q →p ) 和⌝p →(p →⌝q ) 的真值表如表1.33所示。
表1.33
由上表可见：p →(q →p ) 和⌝p →(p →⌝q ) 的真值表完全相同，且都是永真式，所以p →(q →p ) ⇔⌝p →(p →⌝q ) 。
⑹⌝(p q ) ⇔(p ∨q ) ∧⌝(p ∧q )
证明：证明⌝(p q ) 和(p ∨q ) ∧⌝(p ∧q ) 的真值表如表1.34所示。
表1.34
由上表可见：⌝(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 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 →(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 )
(条件等价式) (德·摩根律) (条件等价式) (双重否定律) (交换律)
(条件等价式) (双条件等价式) (条件等价式) (德·摩根律) (分配律) (分配律) (交换律) (条件等价式) (双条件等价式) (条件等价式) (结合律)
(德·摩根律) (条件等价式) (条件等价式)
(条件等价式)
(例1.17) (德·摩根律) (德·摩根律)
(双条件等价式) (条件等价式) (德·摩根律)
⑻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
表1.38
由真值表可知结合律成立。
⑵分配律：p ∧(q ∨r ) ⇔(p ∧q ) ∨(p ∧r ) ，
p ∨(q ∧r ) ⇔(p ∨q ) ∧(p ∨r )
证明：证明合取对析取的分配律的真值表如表1.39所示，析取对合取的的分配律的真值表如表1.40所示。
表1.39
表1.40
由真值表可知分配律成立。 ⑶假言易位式：p →q ⇔⌝q →⌝p
证明：证明假言易位式的真值表如表1.41所示。
表1.41
由真值表可知假言易位律成立。
⑷双条件否定等价式：p q ⇔⌝p ⌝q
证明：证明双条件否定的真值表如表1.42所示。
表1.42
由真值表可知双条件否定等价式成立。
习题 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. 用真值表证明下列命题公式是重言式。
（条件等价式） （德·摩根律） （吸收律） （条件等价式） （德·摩根律） （结合律、矛盾律） （条件等价式） （分配律）
（同一律、矛盾律） （条件等价式） （德·摩根律） （零律、排中律） （条件等价式） （吸收律） （假言易位式）
（条件等价式） （德·摩根律） （分配律）
（同一律、排中律、零律）（分配律）
（条件等价式）
（条件等价式）
⑴(p ∧(p →q )) →q
(p ∧(p →q )) →q 的真值表如表1.43所示。由表1.43可以看出(p ∧(p →q )) →q 是重言式。
表1.43
⑵(⌝q ∧(p →q )) →⌝p
(⌝q ∧(p →q )) →⌝p 的真值表如表1.44所示。由表1.44可以看出(⌝q ∧(p →q )) →⌝p 是重言式。
表1.44
⑶(⌝p ∧(p ∨q )) →q
(⌝p ∧(p ∨q
)) →q 的真值表如表1.45所示。由表1.45可以看出(⌝p ∧(p ∨q )) →q 是重言式。
表1.45
⑷((p →q ) ∧(q →r )) →(p →r )
((p →q ) ∧(q →r )) →(p →r ) 的真值表如表1.46所示。由表1.46可以看出((p →q ) ∧(q →r )) →(p →r ) 是重言式。
表1.46
⑸((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 →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 q ) ∧(q r )) →(p r )
((p q ) ∧(q r )) →(p r ) 的真值表如表1.49所示。由表1.49可以看出((p q ) ∧(q r )) →(p r ) 是重言式。
表1.49
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 ) ∨
((⌝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
习题 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
3. 求下列命题公式的主析取范式，并求命题公式的成真赋值。 ⑴(p ∧q ) ∨(p ∧r )
作(p ∧q ) ∨(p ∧r ) 的真值表，如表1.50所示。
表1.50
由真值表可知，原式⇔(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 ∧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 ) 的真值表，如表1.52所示。
表1.52
由真值表可知:
原式⇔(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 ∧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
⇔(⌝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.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 )
⇔(⌝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 )
习题 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
而⌝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 →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
所以，p →(q →r ) ⇒(p →q ) →(p →r ) ⑸p ∧(p →q ) ⇒q
证明：作(p ∧(p →q )) →q 的真值表，如表1.54所示。
表1.54
由以上真值表可知：(p ∧(p →q )) →q 是一个永真式，所以p ∧(p →q ) ⇒q ⑹⌝q ∧(p →q ) ⇒⌝p
证明：作(p ∧(p →q )) →q 的真值表，如表1.55所示。
表1.55
由以上真值表可知：(⌝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 为真，
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 。
习题 1.8
1. 用全真值表或部分真值表证明下列各题的有效结论。 ⑴(p →(q →r )) ，p ∧q ⇒r
((p →(q →r )) ∧(p ∧q )) →r 的全真值表如表1.56所示。
表1.56
由真值表可知，((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 ∨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所示。
表1.58
→⌝r 。 ⑷p →q ，q →r ⇒p →r
((p →q ) ∧(q →r )) →(p →r )
的真值表如表1.59所示。
表1.59
由真值表可知：((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 ∨⌝p ) ∧(p →q ) ∧(⌝p →q )) →q 是永真式，所以p ∨⌝p , p →q , ⌝p →
q ⇒q 。
⑹p q ，q r ⇒p r
((p q ) ∧(q r )) →(p r ) 的真值表如表1.61所示。
表1.61
由真值表可知：((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 )
⇔((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
⑵(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
证明:
⑵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
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 ⑹⑺假言推理
⑶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 规则
证明:
⑴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 ⑴双重否定律
⑶⌝(⌝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
第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