小语种翻译-党员宣誓誓词

第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进制)
⑺ 若两圆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< br>；
该命题是真
命题。
⑻ p
：
王小红心情愉快；q：王小红 唱歌；原命题符号化为：p↔q
；
该命题是真命题。


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

第1章 习题解答
⑵ (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。
3

第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也是一个永真
4

第1章 习题解答
式，所以，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 q
0 0
0 1
1 0
1 1
p→q q∧(p→q) q∧(p→q)→p
1
1
0
1
0
1
0
1
1
0
1
1

使得公式q∧(p→q)→p成真的赋值是：00，10，11，使得公式q∧(p→q)→p成假的赋值是： 01。
⑵ p→(q∨r) 的真值表如表1.25所示。

表1.25
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
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)成
5

第1章 习题解答
假的赋值是：100。
⑶ (p∨q)↔(q∨p) 的真值表如表1.26所示。

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


表1.28
使得公式
p q r p∧p→(p∧(p→(p∧q ))→((p→(p∧q))→r)∨(q
((p→(p∧q))
r q∧r ∧r)
q q)
→r)∨(q∧r)成
0 0 0 0 0 1 0 1
真的赋值是：
0 0 1 0 0 1 0 1
000，001，
0 1 0 0 0 1 1 1
010，011，
0 1 1 0 0 1 0 1
101，110，
1 0 0 1 1 0 0 0
111，使得公式
1 0 1 1 1 1 0 1
((p→(p∧q))
1 1 0 0 1 0 1 1
→r)∨(q∧r)成
1 1 1 0 1 1 0 1
假的赋值是：
100。
4.用真值表证明下列等价式：
6

第1章 习题解答
⑴(p→q)p∧q
证明：证明(p→q)p∧q的真值表如表1.29所示。

表1.29
p q (p→
p→q q)
q
p∧q
0 0 1 0 1 0
0 1
1 0
1 1
1
0
1
0
1
0
0
1
0
0
1
0

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

⑵p→qq→p
证明：证明p→qq→p的真值表如表1.30所示。

表1.30
p q p→q
p
0 0 1 1
0 1
1 0
1 1
1
0
1
1
0
0
q
q→p
1 1
0
1
0
1
0
1
由上表可见：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)
q
p↔q
0 0
0 1
1 0
1 1

由上表可见：(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 q→rp→(q→r)p∧q(p∧q)→r
1
1
0
1
1
1
7
1
0
0
1
0
1
1
0
1
0
1
0
0
1
1
0
0 0 0
0 0 1
0 1 0

0
0
0
1
1
1

第1章 习题解答
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1
1
1
0
1
1
1
1
0
1
0
0
0
1
1
1
1
1
0
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 q p→
q→p p→(q→p)
pqq
p→(p→q)
0 0 1 1 1 1 1 1
0 1
1 0
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)的真值表如表1.34所示。

表1.34
p q
0 0
0 1
1 0
1 1
(p∧(p∨q)∧(p∧
p↔q (p↔q)p∨qp∧qq)q)
1
0
0
1
0
1
1
0
0
1
1
1
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
1
1
1
1 0
0 1
0 0
1
1
0
1
1
1

由上表可见：(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∧
p↔q (p↔q)
q
p∧q(p∧q)∨(p∧q)
0 0 1 0 0 0 0
0 1
1 0
1 1

0
0
1
1
1
0
0
1
0
8
1
0
0
1
1
0

第1章 习题解答

由上表可见：(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 (p∧q)
r q∨rp→(q∨r)
q
p∧q→r
0 0 0 0 1 1 0 1
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
0
0
1
1
0
0
0
0
0
1
1
0
0
1
1
1
0
1
1
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 (条件等价式)
9

第1章 习题解答
⑸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)) (例1.17)
(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)∨rp∨(q∨r)，(p∧q)∧rp∧(q∧r)
证明：证明结合律的真值表如表1.37和表1.38所示。

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

0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0 0 0
0 0 1

0
0
0
0

第1章 习题解答
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1

由真值表可知结合律成立。
⑵分配律：p∧(q∨r)(p∧q)∨(p∧r)，
p∨(q∧r)(p∨q)∧(p∨r)
证明：证明合取对析取的分配律的真值表如表1. 39所示，析取对合取的的分配律的真值表如表1.40
所示。


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


由真值表可知分配律成立。
⑶假言易位式：p→qq→p
证明：证明假言易位式的真值表如表1.41所示。

11

第1章 习题解答
表1.41
p q
0 0
0 1
1 0
1 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所示。


表1.42
p q
0 0
0 1
1 0
1 1
p↔q
1
0
0
1
p
1
1
0
0
q
1
0
1
0
p↔q
1
0
0
1

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







12

第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)
13




















（条件等价式）
（德·摩根律）
（吸收律）
（条件等价式）
（德·摩根律）
（结合律、矛盾律 ）
（条件等价式）
（分配律）
（同一律、矛盾律）
（条件等价式）
（ 德·摩根律）
（零律、排中律）
（条件等价式）
（吸收律）
（假言易位式）< br>（条件等价式）
（德·摩根律）
（分配律）
（同一律、排中律、零律）
（分配律）

第1章 习题解答
 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.4 3可以看出(p∧(p→q))→q是重言式。

表1.43
p q
0 0
0 1
1 0
1 1
(p∧(p→q))→
p→q p∧(p→q)q
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

q
∧(p→(
q
∧(p→
q
))→
p →q 
q

q
)
pp
0 0 1 1 1 1 1
p q
0 1
1 0
1 1
1
0
1
0
1
0
0
0
0
1
0
0
1
1
1

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

表1.45
p q
0 0
0 1
1 0
1 1
p∧(p∨
p∨q
 p
q)(p∧(p∨q))→q
0
1
1
1
1
1
0
0
0
1
0
0
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)是重
14

第1章 习题解答
言式。






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







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

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

第1章 习题解答
1 1 0
1 1 1
1
1
0
1
0
1
0
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∨r∨s))
((r∧s)∨((p∨r∨q∨p)∧(p∨r∨q∨q)))∧((r∧s)∨
17

第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


习题 1.5
18

第1章 习题解答
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
19

第1章 习题解答
p q r p∧q p∧r
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
(p∧q)∨(p∧r)
0
0
0
0
0
1
1
1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 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 q p q p∨q
1
1
1
0
p↔q
0
1
1
0
(p∨q)→(p↔q)
0
1
1
1
0 0 1 1
0 1 1 0
1 0 0 1
1 1 0 0

由真值表可知:
原式(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)(主析取范式)
20

第1章 习题解答
∑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→
p q p→q q)
0 0
0 1
1 0
1 1

由真值表可知:
原式(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
21
q p→q
1
0
1
0
1
1
1
0
(p→q)↔(p→q)
0
0
1
1
1
1
0
1
0
0
1
0

第1章 习题解答
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)
22

第1章 习题解答
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) < br>(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)。







23

第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 ))
24

第1章 习题解答
((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
显然上式不成立。
25

第1章 习题解答
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
26

第1章 习题解答
⑺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
0
0
1
1

由以上真值表可知：(p→q)→(p→(p∧q))是一个永真式，所以p→qp→(p∧q)
⑶pp→q
证明：p→(p→q)
p∨p∨q
27
q
0
1
0
1
p→q
1
1
0
1
(p→q)→(p→(p∧
p∧q p→(p∧q) q))
0
0
0
1
1
1
0
1
1
1
1
1

第1章 习题解答
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
0
0
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∧(p→q))→p是一个永真式，所以q∧(p→q)p
4.用“假设前件为真，推证后件也为真或假设后件为假，推证前件也为假“的方法证明下列蕴含式。
⑴p∧qp→q
证明：假设前件p∧q为真，证明后件p→q也为真。
因为p∧q为真，所以p为真并且q也为真，根据条件的定义可知p→q也为真。
28
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
q∧(p→(q∧(p→q))→
q
q
p→q q)
p
0 1 1 1 1
1
0
1
0
1
0
1
0
1
0
0
0
1
1
1

第1章 习题解答
所以，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。

















29

第1章 习题解答








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

1
1
1
0
0
1
0
1
0
1
0
1
1
0
1
1
1
0
0
0
0
0
0
0
30
1
1
1
1
1
1

第1章 习题解答
1 1 1

1 0 1 0 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所示。


表1.58
p→(p∨q)∧(r→((p∨q)∧(r→q))→(p
p q r p∨q
q r
→r)
q)
0 0 0 1 1 1 1 1
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1
1
1
0
0
1
1
1
1
0
1
1
1
0
1
1
1
1
0
1
0
1
1
0
0
0
1
0
1
1
1
1
1
1
1 r→
由真值表可知：((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 q r 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))→(p→
(p→q)∧(q→r) r)
1
1
0
1
0
0
0
1
1
1
1
1
1
1
1
1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
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 q
p∨p→p→(p∨p)∧(p→q)∧(p((p∨p)∧(p→q)∧(p→
r
p
q q →q) q))→q
1
1
1
1
0
0
0
0
31
0 0 0
0 0 1

1
1

第1章 习题解答
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
由真值表可知：((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 r 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
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
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
32

第1章 习题解答
((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
证明：
33

第1章 习题解答
⑴t∨s
⑵(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
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
证明:
⑴q
⑵p→q

P(附加前提)
P
34

第1章 习题解答
⑶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(矛盾)

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→u

⑶p→(q∧r)，q∨s< br>，
(t→u)→s
，
q→(p∧t)q→t
证明:
⑴q P(附加前提)
35
P(附加前提)
T⑴附加律
P
T⑵⑶假言推理
T⑷化简律
T⑸附加律
P
T⑹⑺假言推理
CP规则

第1章 习题解答
⑵q∨s
⑶s
⑷(t→u)→s
⑸(t→u)
⑹( t∨u)
⑺t∧u
⑻t
⑼q→t

P
T⑴⑵析取三段论
P
T⑶⑷拒取式
T⑸条件等价式
T⑹德·摩根律
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
证明:
⑴s
⑵s∨p
⑶p
⑷p→r∧q
⑸r∧q
⑹q
⑺s→q

P(附加前提)
P
T⑴⑵假言推理
P
T⑶⑷析取三段论
P
T⑸⑹拒取式
T⑺德·摩根律
T⑴⑻析取三段论
CP规则
P(附加前提)
P
T⑴⑵析取三段论
P
T⑶⑷假言推理
T⑸化简律
CP规则
36

第1章 习题解答

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∧s)
⑷p∨s
⑸p
⑹p→q
⑺q
⑻(q∨r)∧r
⑼q∨r
⑽r
⑾r
⑿r∧r(矛盾)

P(附加前提)
P
T⑴⑵拒取式
T⑶例1.17
T⑷德·摩根律
T⑸化简律
P
T⑹⑺合取引入
P(附加前提)
T⑴双重否定律
P
T⑵⑶假言推理
P
T⑷⑸拒取式
P
T⑹⑺析取三段论
P
T⑻⑼假言推理
T⑷⑽合取引入
P(附加前提)
T⑴双重否定律
P
T⑶德·摩根律
T⑵⑷析取三段论
P
T⑸⑹假言推理
P
T⑻化简律
T⑻化简律
T⑺⑼析取三段论
T⑽⑾合取引入
37

第1章 习题解答
⑷(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)
⑺(t∨s)∧(t∨s)(矛盾)

⑹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. 证明下面各命题推得的结论是有效的：如果今天是星期三，那么我有一次离散数学或数字逻辑
38
P(附加前提)
P
T⑴⑵拒取式
P
T⑶⑷拒取式
P
T⑸⑹合取引入

第1章 习题解答
测验。如果离散数 学课老师有事，那么没有离散数学测验。今天是星期三且离散数学老师有事。所以，
我有一次数字逻辑测 验。
证明：设 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⑸⑺析取三段论



习题 2.1
1．将下列命题符号化。
(1) 4不是奇数。
解：设A(x)：x是奇数。a：4。
“4不是奇数。”符号化为：¬A(a)
(2) 2是偶数且是质数。
解：设A(x)：x是偶数。B(x)：x是质数。a：2。
“2是偶数且是质数。”符号化为：A(a)∧B(a)
(3) 老王是山东人或河北人。
解：设A(x)：x是山东人。B(x)：x是河北人。a：老王。
“老王是山东人或河北人。”符号化为：A(a)

B(a)
(4) 2与3都是偶数。
解：设A(x)：x是偶数。a：2，b：3。
“2与3都是偶数。”符号化为：A(a)∧A(b)
(5) 5大于3。
解：设G(x,y)：x大于y。a：5。b：3。
“5大于3。”符号化为：G(a,b)
(6) 若m是奇数，则2m不是奇数。
解：设A(x)：x是奇数。a：m。b：2m。
“若m是奇数，则2m不是奇数。”符号化为：A(a)→A(b)
(7) 直线A平行于直线B当且仅当直线A不相交于直线B。
解：设C(x,y)：直线x平行于直线y。设 D(x,y)：直线x相交于直线y。a：直线A。b：直线B。
39

第1章 习题解答
“直线A平行于直线B当且仅当直线A不相交于直线B。”符号化为：C(a,b)↔¬D(x,y)
(8) 小王既聪明又用功，但身体不好。
解：设A(x)：x聪明。B(x)：x用功。C(x)：x身体好。a：小王。
“小王既聪明又用功，但身体不好。”符号化为：A(a)∧B(a)∧¬C(a)
(9) 秦岭隔开了渭水和汉水。
解：设A(x,y,z)：x隔开了y和z。a：秦岭。b：渭水。c：汉水。
“秦岭隔开了渭水和汉水。”符号化为：A(a,b,c)
(10) 除非小李是东北人，否则她一定怕冷。
解：设A(x)：x是东北人。B(x)：x怕冷。a：小李。
“除非小李是东北人，否则她一定怕冷。”符号化为：B(a)→¬A(a)
2．将下列命题符号化。并讨论它们的真值。
(1) 有些实数是有理数。
解：设R(x)：x是实数。Q(x)：x是有理数。
“有些实数是有理数。”符号化为：(x)(R(x)∧Q(x))
它的真值为：真。
(2) 凡是人都要休息。
解：设R(x)：x是人。S(x)：x要休息。
“凡是人都要休息。”符号化为：(x)(R(x)→S(x))
它的真值为：真。
(3) 每个自然数都有比它大的自然数。
解：设N(x)：x是自然数。G(x,y)：x比y大。
“每个自然数都有比它大的自然数 。”符号化为：(x)(N(x)→(y)(N(y)∧G(y,x)))
它的真值为：真。
(4) 乌鸦都是黑的。
解：设A(x)：x是乌鸦。B(x)：是黑的。
“乌鸦都是黑的。”符号化为：(x)(A(x)→B(x))
它的真值为：真。
(5) 不存在比所有火车都快的汽车。
解：设A(x)：x是汽车。B(x)：是火车。K(x,y)：x比y快。
“不存在比所有 火车都快的汽车。”符号化为：¬(x)(A(x)∧(y)(B(y)→K(x,y)))
它的真值为：真。
(6) 有些大学生不佩服运动员。
解：设S(x)：x是大学生。L(x)：是运动员。B(x,y)：x佩服y。
“有些大学生不佩服运动员。”符号化为：(x)(S(x)∧L(y)∧¬B(x,y))
它的真值为：真。
(7) 有些女同志既是教练员又是运动员。
解：设W(x)：x是女同志。J(x)：x是教练员。L(x)：x是运动员。
“有些女同志既是教练员又是运动员。”符号化为：(x)(W(x)∧J(x)∧L(x))
它的真值为：真。
(8) 除2以外的所有质数都是奇数。
解：设A(x)：x是质数。B(x)：x是奇数。C(x,y)：x不等于y。
“除2以外的所有质数都是奇数。”符号化为：(x)(A(x)∧C(x,2)→B(x))
40

第1章 习题解答
它的真值为：真。
3．指出一 个个体域，使下列被量化谓词的真值为真，该个体域是整数集合的最大子集。在以下各
题中，A(x)表 示：x＞0，B(x)表示：x=5，C(x,y) 表示：x＋y=0
(1) (x)A(x)
解：正整数集合Z
+
。
(2) (x)A(x)
解：整数集合Z。
(3) (x)B(x)
解：集合｛5｝。
(4) (x)B(x)
解：整数集合Z。
(5) (x)(y)C(x,y)
解：整数集合Z。
4．分别在全总个体域和实数个体域中，将下列命题符号化。
(1) 对所有的实数x，都存着实数y，使得x－y=0
解：设R(x)：x是实数。B(x,y)：x－y=0。
在实数个体域符号化为：(x)(y)B(x,y)
在全总个体域符号化为：(x)(R(x)→(y)(R(y)∧B(x,y)))
(2) 存在着实数x，对所有的实数y，都有x－y=0
解：设R(x)：x是实数。B(x,y)：x－y=0。
在实数个体域符号化为：(x)(y)B(x,y)
在全总个体域符号化为：(x)(R(x)∧(y)(R(y)→B(x,y)))
(3) 对所有的实数x和所有的实数y，都有x＋y=y＋x
解：设R(x)：x是实数。B(x,y)：x=y。
在实数个体域符号化为：(x)(y)B(x+y,y+x)
在全总个体域符号化为：(x)(R(x)→(y)(R(y)→B(x+y,y+x)))
(4) 存在着实数x和存在着实数y，使得x＋y=100
解：设R(x)：x是实数。B(x,y)：x＋y=100。
在实数个体域符号化为：(x)( y)B(x,y)
在全总个体域符号化为：(x)(R(x)∧(y)(R(y)∧B(x,y)))
习题 2.2
1. 指出下列公式中的约束变元和自由变元。
(1) (x)(P(x)→Q(y))
解：约束变元：x，自由变元：y
(2) (x)(P(x)∧R(x))→((x)P(x)∧Q(x))
解：约束变元：x，自由变元：x
(3) (x)(P(x)∧(x)Q(x))∨((x)R(x,y)∧Q(z))
解：约束变元：x，自由变元：y，z
(4) (x)(y) (R(x,y)∧Q(z))
解：约束变元：x，y，自由变元：z
41

第1章 习题解答
(5) (z) (P(x)∧(x)R(x,z)→(y)Q(x,y))∨R(x,y)
解：约束变元：x，y，z，自由变元：x，y
2. 对下列谓词公式中的约束变元进行换名。
(1) (x)(y)(P(x,z)→Q(x,y))∧R(x,y)
解：将约束变元x换成u：(u)(y)(P(u,z)→Q(u,y))∧R(x,y)
将约束变元y换成v：(x)(v)(P(x,z)→Q(x,v))∧R(x,y)
(2) (x)(P(x)→(R(x)∨Q(x,y)))∧(x)R(x)→(z)S(x,z)
解：将前面的约束变元x换成u，后面的约束变元x换成v：
(u)(P(u)→(R(u)∨Q(u,y)))∧(v)R(v)→(z)S(x,z) < br>将约束变元z换成w：(x)(P(x)→(R(x)∨Q(x,y)))∧(x)R(x)→(w )S(x,w)
3. 对下列谓词公式中的自由变元进行代入。
(1) ((y)Q(z,y)→(x)R(x,y))∨(x)S(x,y,z)
解：将自由变元z用 u代入：((y)Q(u,y)→(x)R(x,y))∨(x)S(x,y,u)
将自由变元 y用v代入：((y)Q(z,y)→(x)R(x,v))∨(x)S(x,v,z)
(2) (y)P(x,y)∧(z)Q(x,z)↔(x)R(x,y)
解：将自由变元x用u代入：(y)P(u,y)∧(z)Q(u,z)↔(x)R(x,y)
将自由变元y用v代入：(y)P(x,y)∧(z)Q(x,z)↔(x)R(x,v)
4. 利用谓词公式对下列命题符号化。
(1) 每列火车都比某些汽车快。
解：设A(x)：x是火车。B(x)：x是汽车。C(x,y)：x比y快。
“每列火车都 比某些汽车快。”符号化为：(x)(A(x)→(y)(B(y)∧C(x,y)))
(2) 某些汽车比所有火车慢。
解：设A(x)：x是火车。B(x)：x是汽车。C(x,y)：x比y快。
“某些汽车比所有火车慢。”符号化为： (x)(B(x)∧(y)(A(y)→C(y,x)))
(3) 对每一个实数x，存在一个更大的实数y。
解：设R(x)：x是实数。G(x,y)：x比y大。
“对每一个实数x，存在一个更大的实数y。”符号化为：(x)(R(x)→(y)(R(y)∧ G(y,x)))
(4) 存在实数x，y和z，使得x与y之和大于x与z之积。
解：设R(x)：x是实数。G(x,y)：x比y大。
“存在实数x，y和z，使得x与y之和大于x与z之积。”符号化为：
(x)(y)(z)(R(x)∧R(y)∧R(z)∧G(x+y,xz))
(5) 所有的人都不一样高。
解：设R(x)：x是人。G(x,y)：x和y一样高。
“所有的人都不一样高。”符号化为：(x)(y)(R(x)∧R(y)→¬G(x,y))
5. 自然数一共有下述三条公理：
a) 每个数都有惟一的一个数是它的后继数。
b) 没有一个数使数1是它的后继数。
c) 每个不等于1的数都有惟一的一个数是它的直接先驱数。
用两个谓词表达上述三条公理。
注：设n是不等于1的自然数，则n＋1是n的后继数，n－1是n的先驱数。
解：设A(x)：x是数。B(x,y)：x是y后继数(根据定义，也可理解为y是x先驱数)。
a) “每个数都有惟一的一个数是它的后继数。”符号化为：
42

第1章 习题解答
(x)(A(x)→(y)(A(y)∧B(y,x) )∧((z)(A(z)∧B(z,x))→(z=y)))
b) “没有一个数使数1是它的后继数。”符号化为：¬(x)(A(x)∧B(1,x))
c) “每个不等于1的数都有惟一的一个数是它的直接先驱数。”符号化为：
(x)(A(x)∧¬(x =1)→(y)(A(y)∧B(x,y))∧((z)(A(z)∧B(x,z))→(z=y)))
6. 取个体域为实数集R，函数f在a点连续的定义是：对每个ε＞0，存在一个δ＞0，使得对所< br>有x，若|x－a|＜δ，则|f(x)－f(a)|＜ε。试把此定义用符号化的形式表达出来。
解：(ε) ((ε＞0)→(δ)( (δ＞0)∧(x) ((|x－a|＜δ)→(|f(x)－f(a)|＜ε))))
7.若定义惟一性量词(!x) 为“存在惟一的一个x”，则(!x)P(x)表示“存在惟一的一个x使P(x)为真”。
试用量词 ，谓词及逻辑运算符表示(!x)P(x)。
解：(!x)P(x)(x)P(x)∧((y)P(y)→(y=x))
习题 2.3
1. 设个体域为D=1,2,3，试消去下列各式的量词。
(1) (x)P(x)
解：(x)P(x)P(1)∧P(2)∧P(3)
(2) (x)P(x)→(y)Q(y)
解：(x)P(x)→(y)Q(y)(P(1)∧P( 2)∧P(3))→(Q(1)∨Q(2)∨Q(3))
(3) (x)P(x)∨(y)Q(y)
解：(x)P(x)∨(y)Q(y)(P(1)∧P( 2)∧P(3))∨(Q(1)∨Q(2)∨Q(3))
(4) (x)(P(x)↔Q(x))
解：(x)(P(x)↔Q(x))(P(1)↔Q(1))∧(P(2)↔Q(2))∧(P(3 )↔Q(3))
(5) (x)P(x)∨(y)Q(y)
解：(x)¬P(x)∨(y)Q(y) (¬P(1)∧¬P(2)∧¬P(3))∨(Q(1)∧Q(2)∧Q(3))
2. 求下列各式的真值。
(1) (x)(y)H(x,y) 其中H(x,y)：x＞y，个体域为D=4,2
解：(x)(y)H(x,y)(y)H(2,y)∧(y)H(4,y)
(H(2,2)∨H(2,4))∧(H(4,2)∨H(4,4))
(0∨0)∧(1∨0)0∧10
(2) (x)(S(x)→Q(a))∧p 其中S(x)：x＞3，Q(x)：x=5，a：3，p：5＞3，个体域为D=-1,3,6
解 ：(x)(S(x)→Q(a))∧p((S(-1)→Q(3))∨(S(3)→Q(3))∨(S(6) →Q(3)))∧(5＞3)
((0→0)∨(0→0)∨(1→0))∧1
(1∨1∨0)∧11∧11
(3) (x)(x
2
-2x+1=0) 其中个体域为D=-1,2
解：( x)(x
2
-2x+1=0)(((－1)
2
－2×(－1)＋1=0)∨ (2
2
－2×2＋1=0)
((4=0)∨(1=0)0∨00
3. 证明下列各式。其中：B是不含变元x的谓词公式。
(1) (x)(S(x)→R(x))(x)S(x)→(x)R(x)
证明：(x)(S(x)→R(x))(x)(¬S(x)∨R(x))
(x)¬S(x)∨(x)R(x)
¬(x)S(x)∨(x R(x)
(x)S(x)→(x)R(x)
43

第1章 习题解答
(2) (x)(y)(S(x)→R(y))(x)S(x)→(y)R(y)
证明：(x)(y)(S(x)→R(y))(x)(y)(¬S(x)∨R(y))
(x)¬S(x)∨(y)R(y)
¬(x)S(x)∨(y)R(y)
(x)S(x)→(y)R(y)
(3) (x)(A(x)→B)(x)A(x)→B
证明：(x)(A(x)→B)(x)(¬A(x)∨B)(x)¬A(x)∨B
¬(x)A(x)∨B(x)A(x)→B
(4) (x)(B→A(x))B→(x)A(x)
证明：(x)(B→A(x))(x)(¬ B∨A(x))¬B∨(x)A(x)B→(x)A(x)
(5) (x)(A(x)→B(x))(x)A(x)→(x)B(x)
证明：因为(x)(A( x)→B(x))，所以对于任意个体c，A(c)→B(c)和A(c)，从而有B(c)，由c的任意
性有(x)B(x)，根据CP规则，(x)(A(x)→B(x))(x)A(x)→(x)B( x)
(6) (x)(A(x)B(x))(x)A(x)(x)B(x)
证 明：(x)(A(x)B(x))(x)((A(x)→B(x))∧(B(x)→A(x)))
(x)(A(x)→B(x))∧(x)(B(x)→A(x))
(x)(A(x) →B(x))∧(x)(B(x)→A(x))(x)(A(x)→B(x))(x)A(x)→( x)B(x)
同理，(x)(A(x)→B(x))∧(x)(B(x)→A(x))(x) B(x)→(x)A(x)
所以，(x)(A(x)→B(x))∧(x)(B(x)→A(x ))((x)A(x)→(x)B(x))∧((x)B(x)→(x)A(x))
而(( x)A(x)→(x)B(x))∧((x)B(x)→(x)A(x))(x)A(x)(x )B(x)
故有(x)(A(x)B(x))(x)A(x)(x)B(x)
4. 判断下列证明是否正确。
(x) (A(x)→B(x))(x) (¬A(x)∨B(x))(x)(A(x)∧¬B(x))
¬(x) (A(x)∧¬B(x))¬((x) A(x)∧(x)¬B(x))
¬((x) A(x)∧¬(x)B(x))¬(x) A(x)∨(x)B(x))
(x) A(x)→(x)B(x))
解：下列的推理是错的：¬(x) (A(x)∧¬B(x))¬((x)A(x)∧(x)¬B(x))
习题 2.4
1. 求下列各式的前束范式。
(1) (x)P(x)∧(x)Q(x)
解：(x)P(x)∧(x)Q(x)(x)P(x)∧(x)Q(x)(x)(P(x)∧ Q(x))
(2) (x)P(x)∨(x)Q(x)
解：(x)P(x)∨(x)Q(x)(x)P(x)∨(x)Q(x)
(x)P(x)∨(y)Q(y)
(x)(y) (P(x)∧Q(y))
(3) (x)(y)(((z)A(x,y,z)∧(u)B(x,u))→(v)B(x,v))
解：(x)(y)(((z)A(x,y,z)∧(u)B(x,u))→(v)B(x,v))
(x)(y)((z)(u)(A(x,y,z)∧B(x,u))→(v)B(x,v) )
(x)(y)(z)(u)(v)((A(x,y,z)∧B(x,u))→B(x, v))
(4) (x)(y)((z)(A(x,z)∧B(x,z))→(u)R(x,y,u))
44

第1章 习题解答
解：(x)(y)((z)(A(x,z)∧B(x,z))→(u)R(x,y,u))
(x)(y)(z)(u)((A(x,z)∧B(x,z))→R(x,y,u))
(5) (x)((y)A(x,y)→(x)(y)(B(x,y)∧(y)(A(y, x)→B(x,y))))
解：(x)((y)A(x,y)→(x)(y)(B(x,y)∧(y)(A(y, x)→B(x,y))))
(x)((y)A(x,y)→(x)(y)(B(x,y) ∧(z)(A(z,x)→B(x,z))))
(x)((y)A(x,y)→(u)( v)(z)(B(u,v)∧(A(z,u)→B(u,z))))
(x)(y)(u )(v)(z)(A(x,y)→(B(u,v)∧(A(z,u)→B(u,z))))
( x)(y)(u)(v)(z)(A(x,y)→(B(u,v)∧(A(z,u)→B(u,z)) ))
2. 求下列各式的前束合取范式。
(1) (x)(P(x)∨(z)Q(z,y)→(y)R(x,y))
解：(x)(P(x)∨(z)Q(z,y)→(y)R(x,y))
(x)((z)(P(x)∨Q(z,y))→(y)R(x,y))
(x)((z)(P(x)∨Q(z,y))→(u)R(x,u))
(x)(z)(u)((P(x)∨Q(z,y))→R(x,u))
(x)(z)(u)((P(x)∨Q(z,y))∨R(x,u))
(x)(z)(u)((P(x)∧Q(z,y))∨R(x,u))
( x)(z)(u)((P(x)∨R(x,u))∧(Q(z,y))∨R(x,u)))
(2) (x)(y)(P(x,y)∧Q(y,z))∨(x) R(x,y)
解：(x)(y)(P(x,y)∧Q(y,z))∨(x) R(x,y)
(x)(u)(P(x,u)∧Q(u,z))∨(v)R(v,y)
(x)(u)(v)((P(x,u)∧Q(u,z))∨R(v,y))
(x )(u)(v)((P(x,u)∨R(v,y))∧(Q(u,z))∨R(v,y)))
(3) ((y)Q(z,y)→(x)R(x,y))∨(x)S(x,y,z)
解：((y)Q(z,y)→(x)R(x,y))∨(x)S(x,y,z)
((u)Q(z,u)→(x)R(x,y))∨(v)S(v,y,z)
(u)(x)(v)((Q(z,u)→R(x,y))∨S(v,y,z))
(u)(x)(v)(Q(z,u)∨R(x,y)∨S(v,y,z))
3. 求下列各式的前束析取范式。
(1) (x)(P(x)→(y)((x)Q(x,y)→(z)R(x,y,z)))
解：(x)(P(x)→(y)((x)Q(x,y)→(z)R(x,y,z)))
(x)(P(x)→(y)((x)Q(x,y)→(z)R(x,y,z)))
(x)(P(x)→(y)(u)(z)(Q(u,y)→R(x,y,z)))
(x)(y)(u)(z)(P(x)→(Q(u,y)→R(x,y,z)))
(x)(y)(u)(z)(P(x)∨Q(u,y)∨R(x,y,z))
(2) (x)(y)(P(x,y)∨Q(y,z))∧(x)R(x,y)
解：(x)(y)(P(x,y)∨Q(y,z))∧(x)R(x,y)
(x)(u)(P(x,u)∨Q(u,z))∧(v)R(v,y)
(x)(u)(v)((P(x,u)∨Q(u,z))∧R(v,y))
(x )(u)(v)((P(x,u)∧R(v,y))∨(Q(u,z))∧R(v,y)))
(3) ((y)Q(z,y)∧(x)R(x,y))∨(x)S(x,y,z)
解：((y)Q(z,y)∧(x)R(x,y))∨(x)S(x,y,z)
((u)Q(z,u)∧(x)R(x,y))∨(x)S(x,y,z)
45

第1章 习题解答
(u)(x)(Q(z,u)∧R(x,y))∨(x)S(x,y,z)
(u)(x)(Q(z,u)∧R(x,y))∨(v)S(v,y,z)
(u)(x)(v)((Q(z,u)∧R(x,y))∨S(v,y,z))
习题 2.5
1．证明下列各式。
(1) (x)(F(x)→(G(y)∧R(x)))，(x)F(x)(x)(F(x)∧R(x))
证明：
⑴ (x)F(x) P
⑵ F(c) ES⑴
⑶ (x)(F(x)→(G(y)∧R(x))) P
⑷ F(c)→(G(y)∧R(c)) US⑶
⑸ G(y)∧R(c) T⑵⑷假言推理
⑹ R(c) T⑸化简律
⑺ F(c)∧R(c) T⑵⑹合取引入
⑻ (x)(F(x)∧R(x)) EG⑺
(2) (x)(F(x)→G(x))，(x)(R(x)→G(x))(x)(R(x)→ F(x))
证明：
⑴ (x)(R(x)→G(x)) P
⑵ R(c)→G(c) US⑴
⑶ (x)(F(x)→G(x)) P
⑷ F(c)→G(c) US⑶
⑸ G(c)→F(c) T⑷假言易位式
⑹ R(c)→F(c) T⑵⑸假言三段论
⑺ (x)(R(x)→F(x)) UG⑹
(3) (x)(F(x)∨G(x))，(x)(G(x)→R (x))，(x)R(x)(x)F(x)
证明：
⑴ (x)R(x) P
⑵ R(c) US⑴
⑶ (x)(G(x)→R(x)) P
⑷ G(c)→R(c) US⑶
⑸ G(c) T⑵⑷拒取式
⑹ (x)(F(x)∨G(x)) P
⑺ F(c)∨G(c) US⑹
⑻ F(c) T⑸⑺析取三段论
⑼ (x)F(x) UG⑻
(4) (x)F(x)→(y)((F(y)∨G(y))→R(y))，(x)F(x)(x)R(x)
证明：
⑴ (x)F(x) P
⑵ F(c) ES⑴
⑶ (x)F(x)→(y)((F(y)∨G(y))→R(y)) P
46

第1章 习题解答
⑷ (y)((F(y)∨G(y))→R(y)) T⑴⑶假言推理
⑸ (F(c)∨G(c))→R(c) US⑷
⑹ F(c)∨G(c) T⑵附加律
⑺ R(c) T⑸⑹假言推理
⑻ (x)R(x) UG⑺
2．用CP规则证明下列各式。
(1) (x)(F(x)→R(x))(x)F(x)→(x)R(x)
证明：
⑴ (x)F(x) P(附加前提)
⑵ F(c) US⑴
⑶ (x)(F(x)→R(x)) P
⑷ F(c)→R(c) US⑶
⑸ R(c) T⑵⑷假言推理
⑹ (x)R(x) UG⑸
⑺ (x)F(x)→(x)R(x) CP
(2) (x)(F(x)∨G(x))，(x)(G(x)∧R(x))(x)R(x)→(x)F(x)
证明：
⑴ (x)R(x) P(附加前提)
⑵ R(c) US⑴
⑶ (x)(G(x)∧R(x)) P
⑷ (x)(G(x)∧R(x)) T⑶量词否定等价式
⑸ (G(c)∧R(c)) US⑷
⑹ G(c)∨R(c) T⑸德摩根律
⑺ G(c) T⑵⑹析取三段论
⑻ (x)(F(x)∨G(x)) P
⑼ F(c)∨G(c) US⑻
⑽ F(c) T⑺⑼析取三段论
⑾ (x)F(x) UG⑽
⑿ (x)R(x)→(x)F(x) CP
(3) (x)(F(x)→G(x))，(x)(G(x)∨R(x)) (x)R(x)→(x)F(x)
证明：
⑴ (x)R(x) P(附加前提)
⑵ (x)R(x) T⑴量词否定等价式
⑶ R(c) ES⑵
⑷ (x)(G(x)∨R(x)) P
⑸ G(c)∨R(c) US⑷
⑹ G(c) T⑶⑸析取三段论
⑺ (x)(F(x)→G(x)) P
⑻ F(c)→G(c) US⑺
⑼ F(c) T⑹⑻拒取式
⑽ (x)F(x) EG⑼
⑾ (x)R(x)→(x)F(x) CP
3．用归谬法证明下列各式。
(1) (x)(F(x)∨G(x))(x)F(x)∨(x)G (x)
47

第1章 习题解答
证明：
⑴ ((x)F(x)∨(x)G (x)) P(附加前提)
⑵ (x)F(x)∧(x)G (x)) T⑴德摩根律
⑶ (x)F(x)∧(x)G (x)) T⑵量词否定等价式
⑷ (x)F(x) T⑶化简律
⑸ F(c) ES⑷
⑹ (x)G(x)) T⑶化简律
⑺ G(c) US⑹
⑻ (x)(F(x)∨G(x)) P
⑼ F(c)∨G(c) US⑻
⑽ F(c) T⑺⑼析取三段论
⑾ F(c)∧F(c)(矛盾) T⑸⑽合取引入
(2) (x)(F(x)∨G(x))，(x)(G(x)→R (x))，(x)R(x)(x)F(x)
证明：
⑴ (x)F(x) P(附加前提)
⑵ (x)F(x) T⑴量词否定等价式
⑶ F(c) ES⑵
⑷ (x)(F(x)∨G(x)) P
⑸ F(c)∨G(c) US⑷
⑹ G(c) T⑶⑸析取三段论
⑺ (x)(G(x)→R(x)) P
⑻ G(c)→R(c) US⑺
⑼ R(c) T⑹⑻假言推理
⑽ (x)R(x) P
⑾ R(c) US⑽
⑿ R(c)∧R(c)(矛盾) T⑼⑾合取引入
(3) (x)(F(x)→G(x))，(x)(G(x)∨R(x))， (x)R(x) (x)F(x)
证明：
⑴ (x)R(x) P
⑵ R(c) ES⑴
⑶ (x)F(x) P(附加前提)
⑷ (x)F(x) T⑶量词否定等价式
⑸ F(c) US⑷
⑹ (x)(F(x)→G(x)) P
⑺ F(c)→G(c) US⑹
⑻ G(c) T⑸⑺假言推理
⑼ (x)(G(x)∨R(x)) P
⑽ G(c)∨R(c) US⑼
⑾ R(c) T⑻⑽析取三段论
⑿ R(c)∧R(c)(矛盾) T⑵⑾合取引入
4．证明下面推理。
(1) 每个有理数都是实数。有的有理数是整数。因此，有的实数是整数。
解：首先将命题符号化：
Q(x)：x是有理数。 R(x)：x是实数。
48

第1章 习题解答






Z(x)：x是整数。
本题要证明：(x)(Q(x)→R(x)), (x)(Q(x)∧Z(x))(x)(R(x)∧Z(x))
证明：
⑴ (x)(Q(x)∧Z(x)) P
⑵ Q(c)∧Z(c) ES⑴
⑶ Q(c) T⑵化简律
⑷ Z(c) T⑵化简律
⑸ (x)(Q(x)→R(x)) P
⑹ Q(c)→R(c) US⑸
⑺ R(c) T⑶⑹假言推理
⑻ R(c)∧Z(c) T⑷⑺合取引入
⑼ (x)(R(x)∧Z(x)) EG⑻
(2) 有理数，无理数都是实数。虚数不是实数。因此，虚数既不是有理数，也不是无理数。
解：首先将命题符号化：
Q(x)：x是有理数。 R(x)：x是实数。
W(x)：x是无理数。 X(x)：x是虚数。
本题要证明：(x)(Q(x)→R(x)), (x)(W(x)→R(x))，(x)(X(x)→R(x))
 (x)(X(x)→Q(x))∧(x)(X(x)→W(x))
证明：
⑴ (x)(X(x)→R(x)) P
⑵ X(c)→R(c) US⑴
⑶ R(c)→X(c) T⑵假言易位式
⑷ (x)(W(x)→R(x)) P
⑸ W(c)→R(c) US⑷
⑹ W(c)→X(c) T⑶⑸假言三段论
⑺ X(c)→W(c) T⑹假言易位式
⑻ (x)(X(c)→W(c)) UG⑺
⑼ (x)(Q(x)→R(x)) P
⑽ Q(c)→R(c) US⑼
⑾ Q(c)→X(c) T⑶⑽假言三段论
⑿ X(c)→Q(c) T⑾假言易位式
⒀ (x)(X(x)→Q(x)) UG⑿
⒁ (x)(X(x)→Q(x))∧(x)(X(x)→W(x)) T⑻⒀合取引入
(3) 不存在能表示成分数的无理数。有理数都能表示成分数。因此，有理数都不是无理数。
解：首先将命题符号化：
Q(x)：x是有理数。 W(x)：x是无理数。
F(x)：x能表示成分数。
本题要证明：(x)(W(x)∧F(x)), (x)(Q(x)→F(x))(x)(Q(x)→W(x))
证明：
⑴ (x)(W(x)∧F(x)) P
⑵ (x)(W(x)∧F(x)) T⑴量词否定等价式
⑶ (W(c)∧F(c)) US⑵
49

第1章 习题解答
⑷ W(c)∨F(c) T⑶德摩根律
⑸ F(c)→W(c) T⑷条件等价式
⑹ (x)(Q(x)→F(x)) P
⑺ Q(c)→F(c) US⑹
⑻ Q(c)→W(c) T⑸⑺假言三段论
⑼ (x)( Q(x)→W(x)) UG⑻
(4) 每个 喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不
喜欢乘汽车。所以 有的人不喜欢步行。(个体域为人类集合)
解：首先将命题符号化：
P(x)：x喜欢步行。 Q(x)：x喜欢骑自行车。
R(x)：x喜欢乘汽车。
以全体人类为个体域(全总个体域也可类似证明)本题要证明：
(x)(P(x)→Q (x))，(x)(Q(x)∨R(x))，(x)R(x)(x)P(x)
证明：
⑴ (x)R(x) P
⑵ R(c) ES⑴
⑶ (x)(Q(x)∨R(x)) P
⑷ Q(c)∨R(c) US⑶
⑸ Q(c) T⑷析取三段论
⑹ (x)(P(x)→Q(x)) P
⑺ P(c)→Q(c) US⑹
⑻ P(c) T⑸⑺拒取式
⑼ (x)P(x) UG⑻

习题 3.1
1.用列举法表示下列集合。
⑴大于10小于15的自然数。
⑵八进制数的8个数码组成的集合。
⑶使一元二次方程ax
2
+4x+1=0有实数解的非负整数a的集合。
⑷S
1
=x| x=3∨x=7
⑸S
2
=x| xN∧yN∧x+y=10 ,其中，N为自然数。
⑹S
3
=x| xN∧x
2
-1=0∧x＞2 
解：⑴11,12,13,14
⑵0,1,2,3,4,5,6,7
4
⑶依题意由4－4a≥0得a≤4，所求集合为0,1,2,3。
⑷3,7
⑸0,1,2,3,4,5,6,7,8,9,10
⑹
2.用描述法表示下列集合。
⑴能被2整除的正整数集合。
50

第1章 习题解答
⑵大于10小于15的自然数集合。
⑶奇数集合。
⑷直角坐标系中，单位圆内(不包括单位圆圆周)点的集合。
⑸极坐标系中，单位圆外(不包括单位圆圆周)点的集合。
⑹a
1
,a< br>2
,a
3
,…,a
100

⑺100,101,102,…,200
解：⑴x|xZ
+
∧x能被2整除
⑵x|xN∧10＜x
＜
15
⑶x|x是奇数
⑷x,y|xR∧yR∧x
2
+y
2
＜1
⑸

,

|

R∧

R∧1＜

∧0≤

＜2π
⑹a
i
|iZ∧1≤i
≤
100
⑺x|xZ∧100≤x
≤
200
3.确定下列命题哪些是真的。
⑴
⑵
⑶
⑷
⑸aa
⑹aa,a
⑺aa
⑻aa,a
解：⑴假
⑵真
⑶真
⑷真
⑸真
⑹真
⑺假
⑻真
4.确定下列集合的幂集合。
⑴a,b
⑵a,b,c
⑶a,b,a,c
⑷P()
⑸P(P())
解：⑴ ,a,b,a,b
⑵ ,a,b,c
⑶,a,b,a,c,a,b,a,c
⑷,
⑸,,,
5.设A=，B=P(P(A))，回答下列问题。
51

第1章 习题解答
⑴B?
⑵B?
⑶B?
⑷B?
⑸B?
⑹B?
解：⑴真
⑵真
⑶真
⑷真
⑸真
⑹真
6.可以用下述方法表示有限集合的子集和它的幂集合：设A=a,b, a,b的 位置暂时固定，它们分
别为第一、第二元素。A的子集表示为A
00
，A的下标中左 起第一个0表示子集中无第一元素a(1表
示子集中有第一元素a)。下标的左起第二个0表示子集中无 第二元素b（1表示子集中有第二元素b）。
按这种表示办法，A的子集a,b,a,b分 别表示为A
10
，A
01
，A
11
。于是
P(A )=A
i
|iJ，J=i|i是2进制数∧(00)
2
≤i≤(11 )
2
= i | i是10进制数∧0≤i≤3
一般地，若A有n个元素，则A的幂集合表示为：
P(A)=A
i
|iJ，J= i | i是10进制数∧0≤i≤2
n
－1
设S= a
1
,a
2
,…,a
8
，使用这种表示法完成下列习题。
⑴S
18
所表示的子集是什么？
⑵S
33
所表示的子集是什么？
⑶a
2
,a
6
,a
7
如何表示？
⑷a
1
,a
8
如何表示
解：⑴18=(000100 10)
2
，S
18
表示成为a
4
,a
7

⑵ 33=(00100001)
2
，S
33
表示成为a3
,a
8

⑶ (01000110)
2
=70， a
2
,a
6
,a
7
表示成为S
70

⑷ (10000001)
2
=129，a
1
,a
8表示成为S
129

习题 3.2
1.设 A=x| x=2n∧nN，B=x| x=2n＋1∧nN，求A∩B和A∪B。
解： A∩B=，A∪B= N。
2.确定下列各式结果。
⑴∩
⑵∩
⑶,－
⑷,－
⑸,－
解：⑴
⑵
⑶
52

第1章 习题解答
⑷
⑸ 3.设全集E=1,2,3,4,5,6，A=1,4，B=1,2,5，C=2,4。求 下列各集合。
⑴ A∩~B
⑵ (A∩B)∪~C
⑶ ~ (A∩B)
⑷ A

B
⑸ P(A)∩P(B)
⑹ P(A)∪P(B)
⑺ P(A)－P(B)
解：⑴A∩~B=1,4∩3,4,6=4
⑵(A∩B)∪~C=(1,4∩1,2,5)∪1,3,5,6=1∪1,3,5,6= 1,3,5,6
⑶~ (A∩B)=~1=23,4,5,6
⑷A

B=(A∪B)－(A∩B)=1,2,4,5－1=2,4,5
⑸P(A)∩P(B) =1,41,4∩1,25, 1,2,1,5,2,5,1,2,5
=1
⑹P(A)∪P (B)=1,41,4∪1,25,1,2,1,5, 2,5,1,2,5
=1,2,4,5,1,2,1,4, 1,5,2,5,1,2,5
⑺P(A)－P(B)=1,41, 4－1,25,1,2,1,5,2,5,1,2,5
=41,4
4. 设A,B,C,D是正整数集合Z
＋
的子集。其中
A=1,2,7,8，B= x|x
2
＜50∧xZ
＋
，C=x | xZ
＋
∧x≤30∧x可被3整除
D=x |x=2
k
∧kZ
＋
∧k≤6，E=Z
＋

用列举法表示下列集合。
⑴A∩B∩C∩D
⑵A∪B∪C∪D
⑶B－(A∪C)
⑷(~A∩B)∪D
⑸(A

B)∩(C

D)
解：A=1,2,7,8 ，B=1,2,3,4,5,6,7，C=3,6,9,12,15,18,21,24,27，D= 2,4,8,16,32,64
⑴A∩B∩C∩D
⑵A∪B∪C∪D =1,2,3,4,5,6,7,8,9,12,15,16,18,21,24,27,32,64
⑶B－(A∪C) = 1,2,3,4,5,6,7－1,2,3,6,7,8,9,12,1 5,18,21,24,27=4,5
⑷(~A∩B)∪D=(B－A)∪D=3,4,5, 6∪2,4,8,16,32,64=2,3,4,5,6,8,16,32,64
⑸(A

B)∩(C

D)=3,4,5,6,8∩2,3,4,6,8,9 ,12,15,16,18,21,24,27,32,64=3,4,6,8
5. 某班有2 5个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球
和网球，还有2 人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。
解：E：全班同学，则|E|=25
A：会打篮球的人的集合，则|A|=14
B：会打排球的人的集合，则|B|=12
C：会打网球的人的集合。
由题意：|A∩B|=6，|A∩C|=5，|A∩B∩C|=2，如图3.10所示。
53

第1章 习题解答
25-(5+4+2+3)-5-1=25-14-5-1=5
不会打球的人共5人
6.在1～300的整数中(包括1和300)分别求满足以下条件的整数个数：设E=x|xZ∧1＜x ＜300
⑴同时能被3，5和7整除。
⑵不能被3和5整除，也不能被7整除。
⑶可以被3整除，但不能被5和7整除。
⑷可以被3或5整除，但不能被7整除。
⑸只被3，5和7中的一个数整除。
解：设A=x | xZ∧x可被3整除
B=x | xZ∧x可被5整除
C=x | xZ∧x可被7整除
|A|=INT(3003)=100
|B|=INT(3005)=60
|C|=INT(3007)=57
|A∩B|=INT(300LCM(3,5))=INT(30015)=20
|A∩C|=INT(300LCM(3,7))=INT(30021)=14
|B∩C|=INT(300LCM(5,7))=INT(30035)=8
|A∩B∩C|=INT(300LCM(3,5,7))=INT(300105)=2
其中，LCM(3,5)是3和5的最小公倍数。
⑴将上述数字填入文氏图得图3.11。同时能被3，5和7整除的数有2个。
⑵300-( 100+34+6+37)=300-177=123，不能被3和5整除，也不能被7整除有123个。
⑶可以被3整除，但不能被5和7整除有68个。
⑷100+34+6=140，可以被3或5整除，但不能被7整除有140个。
⑸68+34+37=139，只被3，5和7中的一个数整除有139个。



习题 3.3
1.设A,B,C,D是任意集合。证明：
⑴A∪(B∩C)=(A∪B)∩(A∪C)
证明： xA∪(B∩C) xA∨xB∩C
 xA∨(xB∧xC)
 (xA∨xB)∧(xA∨xC)
 (xA∨xB)∧(xA∨xC)
 xA∪B∧xA∪C
 x(A∪B)∩(A∪C)
54

第1章 习题解答
所以A∪(B∩C)=(A∪B)∩(A∪C)
⑵A∩(B∪C)= (A∩B)∪(A∩C)
证明： xA∩(B∪C) xA∧xB∪C
xA∧(xB∨xC)
(xA∧xB)∨(xA∧xC)
xA∩B∨xA∩C
x(A∩B)∪(A∩C)
所以A∩(B∪C)=(A∩B)∪(A∩C)
⑶ ~ (~A)=A
证明： x~ (~A)(x~A)(xA)xA
所以~ (~A)=A
⑷ A∪E=E
证明：xA∪ExA∨xExA∨TTxE
所以A∪E=E
⑸ A∩~A=
证明：xA∩~AxA∧x~AxA∧(xA)F x
所以A∩~A=
⑹ A∪(A∩B)=A
证明：xA∪(A∩B) xA∨xA∩BxA∨(xA∧xB)xA (吸收律)
所以A∪(A∩B)= A
⑺ ~(A∩B)=~A∪~B
证明：x~(A∩B)(xA∩B)(xA∧xB)xA∨xB
x~A∨x~Bx~A∪~B
所以~ (A∩B)=~A∪~B
2.设A,B,C是任意集合。利用集合恒等式，证明下列结论。
⑴ A∪B=A-B 当且 仅当B=
证明：设A∪B=A-B，以下证明B=
B=B∩(A∪B)=B∩(A- B)=B∩(A∩~B)=(B∩~B)∩A=∩A=
设B=，以下证明A∪B=A-B
A∪B=A∪=A=A-=A-B
⑵ A∩B=A-B 当且仅当A=
证明 ：设A∩B=A-B，以下证明A=
A-B=A∩B=(A∩B)∩B=(A-B)∩B=，又 由A,B的任意性得A=
设A=，以下证明A∩B=A-B
A∩B=∩B==-B=A-B
⑶ A∪B=A∩B 当且仅当A=B
证明：设A∪B=A∩B，以下证明A=B
A=A∩(A∪B)=A∩(A∩B)=A∩B ，所以AB，又由A∪B=A∩B=A，BA。所以A=B。
设A=B，以下证明A∪B=A∩B
A∪B=A=A∩B
⑷ A－B=B－A当且仅当A=B
证明：设A－B=B－A，以下证明A=B
55

第1章 习题解答
A=A∪(A－B)=A∪(B－A)=A∪(B∩~A) =(A∪B)∩(A∪~A)=(A∪B)∩(B∪~B)
=B∪(A∩~B) =B∪(A－B)=B∪(B－A)=B
设A=B，以下证明A－B=B－A
A-B==B-A
3.设A,B,C是任意集合。证明：(A∩B )∪C=A∩(B∪C)当且仅当CA
证明：设(A∩B )∪C=A∩(B∪C)，以下证明CA
xCxA∩B∨xCx(A∩B )∪CxA∩(B∪C)xA∧x B∪CxA，所以CA
设CA，以下证明(A∩B )∪C=A∩(B∪C)
(A∩B )∪C=(A∪C )∩(B∪C )=A∩(B∪C)
4.设A,B,C是任意集合。证明下列集合恒等式。
⑴ (A－B)－C= A－(B∪C)
证明：(A－B)－C=(A∩~ B)∩~ C=A∩(~ B∩~ C) =A∩~ (B∪C)=A－(B∪C)
⑵ (A－B)－C=(A－C)－B
证明：(A－B)－C=(A∩~ B)∩~ C=(A∩~ C)∩~ B =(A－C)－B
⑶ (A－B)－C=(A－C)－(B－C)
证明：(A－C)－(B－C)=(A∩~ C)∩~ (B∩~ C)=(A∩~ C)∩(~ B∪C)
=(A∩~ C∩~ B)∪(A∩~ C∩C) =(A∩~ C∩~ B)∪
=(A∩~ B)∩~C=(A－B)－C
5.判断下列结论是否正确。
⑴ 若A∪B=A∪C，则B=C
解：不正确。反例，令A=1,2,3，B=1,2 ，C=1。A∪B=1,2,3=A∪C，但B≠C。
⑵ 若A∩B=A∩C，则B=C
解：不正确。反例，令A=1，B=1,2，C=1,2,3。A∩B=1=A∩C， 但B≠C。
6.证明：
⑴ P(A)∩P(B)=P(A∩B)
证明：xP( A)∩P(B)xP(A)∧xP(B)xA∧xBxA∩BxP(A∩B)
所以P(A)∩P(B)=P(A∩B)
⑵ P(A)∪P(B)P(A∪B)
证明：xP(A)∪P(B)xP(A)∨xP(B)xA∨xBxA∪BxP(A∪B )
所以P(A)∪P(B)P(A∪B)
7.证明：
⑴ 若CA且CB当且仅当CA∩B
证明：设CA且CB，以下证明CA∩B
C=C∪C=(C∩A)∪(C∩B)= C∩(A∪B)，所以CA∩B
设CA∩B，以下证明CA且CB
xC，而CA∩B，xA且xB，所以CA且CB
⑵ 若对一切集合A都有A∪ B=A，则B=
证明：设B≠，xB，令A=y，y≠x，xA∪B但xA，所以A ∪B≠A，矛盾。
⑶ 若AB，则~A∪B=E
证明：~A∪B=~A∪(A∪B)=(~A∪A)∪B=E∪B=E
⑷ 若AB，则P(A)P(B)
证明：xP(A)xAxBxP(B)，所以P(A)P(B)
56

第1章 习题解答
⑸ 若A∪B= A∪C且A∩B= A∩C，则B=C
证明：先证BC
xBxA∪BxA∪CxA∨xC
当xA时，xA∧xBxA∩BxA∩CxA∧xCxC，即BC
当xC时，此时也有BC
类似的可以证明CB
习题 3.4
1. 4个元素的集合共有多少个不同的划分？试给出这些划分。
2
12
解：1+
C
4
+
C
4
+
C
4
+1=1+4+6+3 +1=15种，令A=1,2,3,4,其划分有：
1
2
⑴一个划分块的有划分1个：1,2,3,4
⑵两个划分块的 划分有7个：1,2,3,4，1,3,2,4，1,4,2,3，
1,2,3,4，1,2,4,3，1,3,4,2，
2,3,4,1
⑶三个划分块的划分有6个：1,2,3,4 ，1,3,2,4，1,4,2,3，
2,3,1,4，2,4,1,3，3,4,1,2
⑷四个划分块的划分有1个：1,2,3,4
2. 设是正整数集合Z
+
的子集构成的集合。判断是否是Z
+
的划分。
⑴S
1
=x| xZ
+
∧x是素数，S
2
= Z
+
-S
1
，= S
1
，S
2

⑵ =x | xZ
+

解：⑴是
⑵是
3 .对于任意非空集合A，P(A)-是A的非空子集构成的集合，P(A)-是否构成A的划分？
解：不能，例如：A=1,2，P(A)-=1,2,1,2，P(A)- 不是A的划分。
4.设A
1
，A
2
，…，A
n< br>是集合A的划分，若A
i
∩B≠, i＝1,…,n，试证明A
1
∩B,A
2
∩B,…,A
n
∩B
是集合A∩B的划分。
证明：⑴因为A
i
A，所以A
i
∩BA∩B
⑵ (A
1
∩B)∪(A
2
∩B)∪…∪(A
n
∩B)=(A
1
∪A
2
∪…∪A
n
)∩B=A∩B
⑶ 因为A
i
∩A
j
=，A
i
∩B)∩(A
j
∩B)= A
i
∩A
j
)∩B=∩B=
所以A
1
∩ B,A
2
∩B,…,A
n
∩B 是集合A∩B的划分。
习题 3.5
1. 设A=a,b，B=1,2,3，求：A×B，B×A，A×A，B×B和(A×B)∩( B×A)。
解：A×B=a,1,a,2,a,3,b,1,b,2,b,3
B×A=1,a,1,b,2,a,2,b,3,a,3,b
A×A=a,a,a,b,b,a,b,b
B×B=1,1, 1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3
(A×B)∩(B×A)=
2. 设A=1,2，求：A×P(A)
57

第1章 习题解答
解：A×P(A)=1,,1,1,1 ,2,1,1,2,2,,2,1,2,2,2,1,2
3. 设A，B，C，D为任意集合，判断下列结论是否为真？并说明理由。
⑴如果A×B＝A×C，那么B＝C
解：不真。反例：A=，B=1，C=2，A×B=A×C，但A≠C
⑵ A－(B×C)＝(A－B)×(A－C)
解：不真。当A不是笛卡尔积时，A-B×C不是笛卡尔积，而(A－B)×(A－C)是笛卡尔积。
⑶ 如果A＝B且C＝D，那么A×C＝B×D
解：真。
a,bA×CaA∧bCaB∧bDa,bB×D，所以A×C＝B×D
⑷ 存在集合A使得AA×A
解：真，例如空集×
4.证明下列各题。
⑴ 如果A×A＝B×B，那么A＝B
证明：xAxA∧xAx,xA×A x,xB×BxB∧xBxB，所以A＝B
⑵ 如果A×B＝A×C且A≠，那么B＝C
因为A≠，xA，以下证明B＝C
yB xA∧yBx,yA×Bx,yA×CxA∧yCyC，所以B＝C
⑶ (A∩B)×(C∩D)＝(A×C)∩(B×D)
证明：x,y(A∩B)×(C∩D)xA∩B∧yC∩D
xA∧xB∧yC∧yD
xA∧yC∧xB∧yD
x,yA×C∧x,yB×D
x,yA×C∩B×D
所以 (A∩B)×(C∩D)＝(A×C)∩(B×D)
5.下列等式中哪些成立?哪些不成立?对于成立的给出证明，对于不成立的举出反例。
⑴ (A∪B)×(C∪D)＝(A×C)∪(B×D)
解：不成立。反例为：A＝1，B＝2，C＝a，D＝b
(A∪B)×(C ∪D)＝1,2×a,b＝1,a,1,b,2,a,2,b
(A×C)∪(B×D)＝1,a∪2,b＝1,a,2,b
所以，(A∪B)×(C∪D)≠(A×C)∪(B×D)
⑵ (A－B)×(C－D)＝(A×C)－(B×D)
解：不成立。反例为：A＝1,2，B＝1，C＝a,b，D＝a
(A－B)×(C－D)＝2×b＝2,b
(A×C)－(B×D)＝ 1,a,1,b,2,a,2,b－1,a＝1,b,2,a,2,b 
所以，(A－B)×(C－D)≠(A×C)－(B×D)


习题 4.1
1.设A=a,b，列出A上的所有二元关系。
解：A×A=a,a,a,b,b,a,b,b
58

第1章 习题解答
A上的二元关系有2
|
A
×A
|
=2
|
A
||
A
|
=2
2
×
2
=2
4
=16。其中：
①空集1个
② 含有1个元素的子集4个：a,a，a,b，b,a，b,b。
③ 含有2个元素的子集
C
4
=
2
43
=6个：a,a ,a,b，a,a,b,a，a,a,b,b，
21
 a,b,b,a，a,b,b,b，b,a,b,b
④含有3个元 素的子集
C
4
3
=
432
=4个：a,a,a ,b,b,a，a,a,a,b,b,b，
321
a,a ,b,a,b,b，a,b,b,a,b,b
⑤含有4个元素的子集1个：a,a,a,b,b,a,b,b
2.设A和B是有限集，A到B的二元关系有多少种？
||||
解：A到B的二元关系有|P(A×B)|=2
AB
种。
3.用列举法表示A到B的二元关系R，写出关系矩阵，画出关系图。
⑴ A=1,2,3 ,4,5，B=a,b,c，R=

1,a

,

1,b

,

2,b

,

3,a


⑵ A=a,b,c，B=1,2,3,4,5，R=
a,2 ,c,4,c,5

⑶ A=0,1,2，B=0,2,4，R=

a,b

| aA∧bB∧a×bA∩B，其中×是普通乘法。
⑷ A=1,2,3,4,5，B=1,2,3，R=

a,b

| aA∧bB∧a=b
2

⑸ A=P(0,1)，B= P(0,1,2)－P(0)，R=

a,b

| aA∧bB∧a-b＝

1


0
解：⑴ M< br>R
=

1


0


0< br>1
1
0
0
0
0


0
< br>0



0


0

R关系图如图4.20所示。

01000


⑵ M
R
=

00000



00011


R关系图如图4.21所示。

111


⑶ M
R
=

1 10


100



R关系图如图4.22所示。

1


0
0
⑷ M
R
=



0


0
00

00

00



10


00

R关系图如图4.23所示。
⑸ A=P(0,1)=0,1,0,1
59

第1章 习题解答
B=P(0,1,2)－P(0)
= 0,1,2,0,1,0,2,1,2,0,1,2－0
=1,2,0,1,0,2,1,2,0,1,2

1


0
M
R
=

1


0

11111


01101

< br>01011


01001


R关系图如图4.2 4所示。
4.写出A上二元关系R的关系矩阵，画出关系图。
⑴ A=0,1,2,3，
R=0,0,0,3,2,0,2,1,2,3,3,2
⑵ A=1,2,4,6，R=

a,b

| aA∧bA∧b为素数
⑶ A=0,1,2,3,4，R=

a,b

| aA∧bA∧a为奇数∧b≤3
⑷ A=0,1,2,3,4，R=

a,b

| aA∧bA∧0≤a－b＜3
⑸ A=2,3,4,5,6，R=

a,b

| aA∧bA∧a和b是互质的

1


0
解：⑴ M
R
=

1


0

001

000


101


010< br>

R关系图如图4.25所示。


0


0
⑵ M
R
=

0


0

1
1
1
1
0
0
0
0
0


0


0


0


R关系图如图4.26所示。


0


1
0
⑶ M
R
=



1


0
0000


1110

0000



1110< br>

0000

R关系图如图4.27所示。

1


1
1
M
R
=



0


0
0000


1000

1100



1110


0111

⑷
R

关系图如图4.28所示。
60

第1章 习题解答

0


1
⑸ M
R
=

0


1


0
1010


0110

1010



1101< br>

0010

R关系图如图4.29所示。












5.设A=0,1,2,3,4,5,6，A上二元关系R=

a,b

| aA∧bA∧(a＜b∨b为素数)，写出R的关系矩
阵。

0


0

0

解：M
R
=
0


0

0


0
111111


011111

011111

011111



011011
011011


011010


习题 4.2
1.A=1,2,3,4，A上二元关系R和S分别为：
R=1,2,2,4,3,3 S=1,3 ,2,4,4,2
⑴ 求 R∩S，R∪S，R-S，~R，~S，R

S
⑵ 求dom R，ran R，FLD R，dom S，ran S，FLD S
⑶ 求dom ~R，ran ~R，FLD ~R
⑷ 求dom R

S，ran R

S，FLD R

S
⑸ 求R
C
，S
C
，(R∩S)
C
，验证(R∩S)
C
=R
C
∩S
C
解：⑴R∩S=2,4
R∪S =1,2,1,3,2,4,3,3,4,2
R-S =1,2,3,3
~R=1,1,1,3,1,4,2,1,2, 2,2,3,3,1,3,2,3,4,4,1,4,2,4,3,4,4 
~S=1,1,1,2,1,4,2,1,2,2,2,3,3,1 ,3,2,3,3,3,4,4,1,4,3,4,4
R

S =1,2,1,3,3,3,4,2
61

第1章 习题解答
⑵ dom R =1,2,3
dom S =1,2,4
⑶ dom ~R =1,2,3,4
⑷ dom R

S =1,3,4
⑸ R
C
=2,1,3,3,4,2
ran R =2,3,4
ran S =2,3,4
ran ~R=1,2,3,4
ran R

S =2,3
FLD R =1,2,3,4
FLD S =1,2,3,4
FLD ~R =1,2,3,4
FLD R

S =1,2,3,4
S
C
=2,4,3,1,4,2
R
C
∩S
C
=4,2
(R∩S)
C
=4,2=R
C
∩S
C

2.A=0,1,2,3，A上二元关系R和S分别为：
R=

a,b

| aA∧bA∧(b＝a＋1∨b＝a2) 
S=

a,b

| aA∧bA∧a＝b＋2 
⑴ 求 R

S，S

R，R

S
R，R
3
⑵ 验证M
R

S
=M
R

M
S
⑶ 求R
C
，S
C
，R
C

S
C
，( S

R)
C
，验证(S

R)
C
= R
C

S
C
⑷ 验证
M
R
C
=M
R
T
解：R=0,0, 0,1,1,2,2,1,2,3，S=2,0,3,1。
⑴R

S=1,0,2,1
S

R=2,0,2,1,3,2
R

S

R =1,0,1,1,2,2
R
3
=0,0,0,1,0,2,0,3,1,2,2,1, 2,3
~S=0,0,0,1,0,2,0,3,1,0,1,1, 1,2,1,3,2,1,2,2,2,3,
3,0,3,2,3,3
R

S =0,0,0,1,1,2,2,1,2,3,2,0,3,1

1100

0000

000

0000


00100000

100

1000


⑵ M
R

S
=

，MM=
RS

1000

=

010
0100

0101



00 00


0000

0100

000


⑶ R
C
=0,0,1,0,2,1,1,2,3,2
S
C
=0,2,1,3
R
C

S
C
=0,2,1,2,2,3
(S

R)
C
=0,2,1,2,2,3=RC

S
C


110

1000


1010

001

M
⑷
M
R
C



R

01 0
0100




0010

000


0


0

= M
R

S

0


0


0


10


0


10
T

M
R

01
1



00

0


00


10

M
R
C

00

10


3.设R，S，T是A上的二元关系, 证明：
⑴ R

(S∪T)=R

S∪R

T
⑵ (R∪S)

T= R

T∪S

T
证明：⑴ x,yR

(S∪T))(z)(x,zR∧z,yS∪T)
(z)(x,zR∧(z,yS∨z,yT))
(z)((x,zR∧z,yS)∨(x,zR∧z,yT))
62

第1章 习题解答
(z)(x,zR∧z,yS)∨(z) (x,zR∧z,yT)
x,yR

S∨x,yR

T
x,yR

S∪R

T
所以R

(S∪T)=R

S∪R

T
⑵ x,y(R∪S)

T (z)(x,zR∪S∧z,yT)
(z)((x,zR∨x,zS)∧z,yT)
(z)((x,zR∧z,yT)∨(x,zS∧z,yT))
(z) (x,zR∧z,yT)∨(z) (x,zS∧z,yT)
x,yR

S∨x,yS

T
x,yR

S∪R

T
所以R

(S∪T)=R

S∪R

T
4.设R，S，T是A上的二元关系, RS，证明：
⑴ R

TS

T
⑵ T

RT

S
⑶ ~S~R
证明：⑴x,y R

T(z)(x,zR∧z,yT)(z)(x,zS∧z, yT)x,yS

T
所以R

TS

T
⑵ x,yT
R(z)(x,zT∧z,yR)(z)(x,zT∧z,yS)x ,yT

S
所以T

RT

S
⑶ x,y~S(x,yS)(x,yR) x,y~R，所以~S~R

5.证明A是二元关系当且仅当Adom A×ran A
证明：设A是二元关系，下证Adom A×ran A
x,yAxdom A∧yran Ax,yom A×ran A，所以Adom A×ran A
设Adom A×ran A，下证A是二元关系。
由二元关系的定义知，A是dom A到ran A的二元关系。
6. 设S是X到Y的二元关系，T是Y到Z的二元关系。AX，定义 S(A) = y|x,yS∧
x
A，证
明：
⑴ S(A)Y
⑵ (S

T)(A)=T(S(A))
⑶ S(A∪B)=S(A)∪S(B)
⑷ S(A∩B)S(A)∩S(B)
证明：⑴yS(A) x,yS∧x
A
x
X∧yY∧
x
AyY，所以S(A)Y
⑵ y(S

T)(A)x,yS

T∧
x< br>Ax,zS∧
x
A∧z,yT
 zS(A)∧z,yTyT(S(A))
所以，(S

T)(A)=T(S(A))
⑶ yS(A∪B) x,yS∧
x
A∪B
x,yS∧(
x
A∨
x
B)
(x,yS∧
x
A)∨(x,yS∧
x
B)
 yS(A)∨yS(B)
 yS(A)∪S(B)
所以 S(A∪B)=S(A)∪S(B)
⑷ yS(A∩B) x,yS∧
x
A∩B
63

第1章 习题解答
x,yS∧(
x
A∧
x
B)
(x,yS∧
x
A)∧(x,yS∧
x
B)
 yS(A)∧yS(B)
 yS(A)∩S(B)
所以 S(A∪B)=S(A)∪S(B)
习题 4.3
1.设A=1,2,3，A上二元关系定义为：
R=1,1,1,2,1,3,3,3
S=1,1,1,2,2,1,2,2,3,3
T=1,1,1,2,2,2,2,3
 (空关系)
A×A(全域关系)
判断上述关系是否是⑴自反的，⑵对称的，⑶传递的，⑷反对称的。
解：各关系的自反性、对称性、传递性和对称性如表4.2所示。
表4.2

R
S
T

A×A
自反
否
是
否
否
是
对称
否
是
否
是
是
传递 反对称
是
是
否
是
是
是
否
是
是
否

2.设R和 S是A上的任意关系，说明以下命题的真假，若为真命题，则给出证明。若为假命题，
举一反例。
(1) 若R和S是自反的，则R

S也是自反的。
(2) 若R和S是反自反的，则R

S也是反自反的。
(3) 若R和S是对称的，则R

S也是对称的。
(4) 若R和S是传递的，则R

S也是传递的。
(5) 若R是自反的，则R
C
也是自反的。
(6) 若R是反自反的，则R
C
也是反自反的。
(7) 若R是对称的，则R
C
也是对称的。
(8) 若R是传递的，则R
C
也是传递的。
解：(1)真。
证明：xA  x,xR∧x,xS，所以x,xR

S，所以R

S也 是自反的。
(2) 假。
反例，令A=1,2，R=1,2，S=2,1 ，R

S=1,1
(3) 假。
反例，令A=1,2,3 ，R=1,2,2,1，S=2,3,3,2，R

S=1, 3
(4) 假。
64

第1章 习题解答
反例， 令A=1,2,3,4，R=1,2,3,4，S=2,3,4,4，R

S=1,3,3,4
(5) 真。
证明：xA  x,xRx,xR
C
，所以R
C
也是自反的。
(6) 真。
证明：反证法。设R
C
是不是反自反的，xA使x,x R
C
x,xR，与R是反自反的矛盾。
所以R
C
也是反自反的。
(7) 真。
(R
C
)
C
=R= R
C
，所以R
C
也是对称的。
(8) 真。
证明：x,yR
C
∧y,zR
C
y,xR∧z,yR
z,xRx,zR
C

所以R
C
也是传递的。
3.R是集合X上的自反关系，证明：R是对称的和 传递的当且仅当如果a,bR和a,cR时，则
有b,cR
证明：设R是对称的和传递的，下证如果a,bR和a,cR时，则有b,cR
a,bR∧a,cRb,aR∧a,cR (R是对称的)
b,cR (R是传递的)
设如果a,bR和a,cR时，则有b,cR，下证R是对称的和传递的。
先证R是对称的，
a,bRa,bR∧a,aR (R是自反的)
b,aR
再证R是传递的，
a,bR∧b,cR b,aR∧b,cR (R是对称的)
a,cR
4. R是集合X上的二元关系，证明若R是自反的和传递的，则R

R=R
证明：因为R是传递的，所以R

RR
a,bRa,bR∧b,bR (R是自反的)
a,bR

R
所以RR

R，这就证明了R

R=R
5. R是集合X上的二元关系，R在X上是反传递定义为：
(x)(
y
)(z)( xX∧
y
X∧zX∧x,yR∧y,z R→x,zR)
证明R是反传递的当且仅当(R

R)∩R=
证明：设R是反传递的，下证(R

R)∩R=
反证法，设(R

R)∩R≠，
存在a,b(R

R)∩Ra,bR< br>
R∧a,bR
(a,cR∧c,bR)∧a,bR 与反传递矛盾
所以 (R

R)∩R=
设(R

R )∩R=，下证R是反传递的。
a,bR∧b,cRa,cR

R
a,cR (因为(R

R)∩R=)
所以，R是反传递的。
65

第1章 习题解答
习题 4.4
1.设A=1,2,3,4，A上二元关系R定义为：
R=1,2,2,1,2,3,3,4
⑴ 求R的自反闭包、对称闭包和传递闭包。
⑵ 用R的关系矩阵和四阶单位阵求R的自反闭包、对称闭包 和传递闭包的关系矩阵。再由关系矩
阵写出它们的集合表达式。
⑶ 根据R的关系图，画出R 的自反闭包，对称闭包和传递闭包的关系图，再由关系图写出它们的
集合表达式。总结出用R的关系图求 出R的自反闭包，对称闭包和传递闭包关系图的一般方法。
解：⑴r(R)=1,2,2,1 ,2,3,3,4,1,1,2,2,3,3,4,4
s(R)=1,2,2,1,2,3,3,4,3,2,4,3
R
2
=R

R=1,1,1,3,2,2,2,4
R
3
=R
2

R=1,2,1,4,2,1 ,2,3
R
4
=R
2

R=1,1,1, 3,2,2,2,4=R
2

t(R)=R∪R
2
∪R
3
∪R
4
= 1,1 ,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,4
⑵解：

0


1
M
R
=
0


0

100

01

010

10
M
M= M∨=
r(R)R< br>I

00
A
001



000 00



1
00



10


0
∨

0
01




0
00



000

< br>1


100


1
=
0
010





001



0
100


110


011


001


r(R)=1,2,2,1,2,3 ,3,4,1,1,2,2,3,3,4,4

0

T

1
M
s(R)
= M
R
∨
M
R
=

0


0


0


1

M
R

M
R
=

0


0


0
100



010


1< br>∨

0
001





0
000


100


010

001


000



0

1



0


0

100

0


000


1
=
0
100





010
< br>

0
100


1


010


0
=
001


0



000



0
10
01< br>00
00
100


010


101


010


s(R)= 1,2,2,1,2,3,3,4,3,2,4,3
010


101


000


000


0


0101




1010
0


=
1


0000




0000
< br>0



010


101
< br>
000


000


M
R2

1


0
M
R
3
=M
R
2

M
R
=

0

0


0


1
M
R4
=
M
R
3

M
R
=
0


0

010


0


101


1

0
000
< br>



000



0
101


0


010


1

0
000





000< br>


0
100


1


010


0
=
001


0



000



0
66

第1章 习题解答
M
t(R)
= M
R
∨
M
R
2
∨
M
R
3
∨
M
R
4

1


1


0


0

111


111


001


000


t(R)= 1,1 ,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,4
⑶R的关系图如图4.30所示，R的自反闭包、对称闭包和传递闭包的关系图如图4.31、图4.3 2和
图4.33所示。










检查R的关系图，哪一个结点没有自回路就加一个自回路，得到R自反 闭包的关系图。将R的关
系图中任何一对结点间的单向边，添一个相反方向边，得到R对称闭包的关系图 。对于传递闭包的关
系图，只要依次检查R的关系图的每一个结点x，把从x出发的长度不超过n(n是 图中的结点个数)的
所有路径的终点找到。如果x到这样的终点没有边，就加上一条边。
2.设R是A上的二元关系，证明：
⑴ R是对称的当且仅当s(R)=R
⑵ R是传递的当且仅当t(R)=R
证明：⑴设R是对称的，下证s(R)=R
令R′=R
① R′=R是对称的。
② 因为RR=R′，所以RR′。
③ 有任意对称二元关系R′′且RR′′，下证R′R′′
因为R′=RR′′，所以R′R′′
设s(R)=R，下证R是对称的。
由对称闭包的定义，显然R是对称的。
⑵设R是传递的，下证t(R)=R
令R′=R
① R′=R是传递的。
② 因为RR=R′，所以RR′。
③ 有任意传递二元关系R′′且RR′′，下证R′R′′
因为R′=RR′′，所以R′R′′
设t(R)=R，下证R是传递的。
由传递闭包的定义，显然R是传递的。
3.设R和S是A上的二元关系，RS，证明：
⑴ r(R)r(S)
67

第1章 习题解答
⑵ s(R)s(S)
⑶ t(R)t(S)
证明：⑴方法1
r(R)=I
A
∪R I
A
∪S

=r(S

)，即r(R)r(S)。
方法2
证明：RS r(S)，r(S)是包含R的自反关系，而r(R) 是包含R的最小的自反关系。所以r(R)r(S)
⑵方法1
先证R
C
S
C
，a,bR
C< br>b,aRb,aSa,b S
C
，所以R
C
 S
C

s(R)=R∪R
C
S∪S
C
=s(S) ，所以s(R)s(S)。
方法2
RSs(S)，s(S)是包含R的对称关系，而s(R) 是包含R的最小的对称关系。所以，s(R)s(S)。
⑶方法1
a,bt(R) kZ
+
使a,bR
k
(Z
+
是正整数集合)
a,x
1
R∧x1
,x
2
R∧…∧x
k
-1
,bR

a,x
1
S∧x
1
,x
2
S∧…∧ x
k
-1
,bS

a,bS
k
t(S)a,bt(S)
所以t(R)t(S)
方法2
RSt(S)，t(S)是包含R的传递关系，而t(R) 是包含R的最小的传递关系。所以t(R)t(S)
4. 设R和S是A上的二元关系，证明：
⑴ r(R∪S)=r(R)∪r(S)
⑵ s(R∪S)=s(R)∪s(S)
⑶ t(R)∪t(S)t(R∪S)
证明：⑴r(R∪S)=R∪S∪I
A=(R∪I
A
)∪(S∪I
A
)=r(R)∪r(S)
⑵s(R∪S)= (R∪S)∪(R∪S)
C
=(R∪R
C
)∪( S∪S
C
)=s(R)∪s(S)
⑶由习题4.4的第3题的第⑶小题知t(R) t(R∪S)和t(S)t(R∪S)，所以t(R)∪t(S)t(R∪S)
5.设R是A上的二元关系，证明：
⑴ 若R是自反的，则s(R)和t(R)也是自反的。
⑵ 若R是对称的，则r(R)和t(R)也是对称的。
⑶ 若R是传递的，则r(R)也是传递的。
证明：⑴I
A
RR∪R
C=s(R)，即I
A
s(R)，所以s(R)是自反的。I
A
Rt (R)，即I
A
t(R)，所以t(R)
也是自反的。
⑵r(R)C
=(R∪I
A
)
C
=R
C
∪I
A< br>=R∪I
A
=r(R)，所以r(R)是对称的。
a,bt(R) kZ
+
使a,bR
k
(Z
+
是正整数集合)
a,x
1
R∧x
1
,x
2
R∧…∧x
k
-1
,bR

b, x
k
-1
R∧…∧x
2
,x
1< br>R∧x
1
, aR

b,aR
k
t(R)b,at(R)
所以t(R)是对称的。
⑶r(R)

r(R)=(R∪I
A
)

(R∪I
A
)=(R

R)∪R∪I
A
R∪R∪I
A
=R∪I
A
=r (R)，即r(R)

r(R)r(R)
所以r(R)也是传递的。
6.设R是A上的二元关系，证明st(R) ts(R)
证明：由对称闭包的定义知R s(R)，由习题4.4的第3题的第⑶小题知t(R)ts(R)和st(R)sts(R)。
68

第1章 习题解答
因为s(R)是对称的，由习题4.4的第5题的第 ⑵小题知ts(R)也是对称的，再由习题4.4的第2题知：
sts(R)=ts(R)。
所以st(R)ts(R)
7.设R是A上的二元关系，证明：
⑴ (R
+
)
+
=R
+
⑵ (R*)*=R*
⑶ R*

R=R

R*=R
+

证明：⑴因为t(R )是传递的，所以tt(R)=t(R)，即(R
+
)
+
=R
+
⑵ R*=rt(R)=tr(R)，所以R*是自反的和传递的。所以t(R*)=R*。rt (R*)=r(R*)=R*，即(R*)*=R*
⑶R*

R=rt(R)

R=( I
A
∪R∪R
2
∪R
3
∪…)

R=R∪R
2
∪R3
∪…=t(R)=R
+
R

R*=R

rt(R)=R

( I
A
∪R∪R
2
∪R
3
∪…)=R∪R
2
∪R
3
∪…=t(R)=R
+

习题 4.5
1.设A有4个元素，A上等价关系有哪几个？
解：A有15种划分，故有15个等价关系。令A= 1,2,3,4
R
1
= 1×1∪2×2∪3×3∪4×4
R
2
= 1×1∪2×2∪3,4×3,4
R
3
= 1×1∪3×3∪2,4×2,4
R
4
= 1×1∪4×4∪2,3×2,3
R
5
= 2×2∪3×3∪1,4×1,4
R
6
= 2×2∪4×4∪1,3×1,3
R
7
= 3×3∪4×4∪1,2×1,2
R
8
= 1,2×1,2∪3,4×3,4
R
9
= 1,3×1,3∪2,4×2,4
R
10
= 1,4×1,4∪2,3×2,3
R
11
= 1,2,3×1,2,3∪4×4
R
12
=1,2,4×1,2,4∪3×3
R
13
=1,3,4×1,3,4∪3×3
R
14
=2,3,4×2,3,4∪1×1
R
15
=1,2,3,4×1,2,3,4
2.设R是A上的二元关系，判断R是否为A上的等价关系。
⑴ A是实数集合，R=x,y| xA∧yA∧x－y=2 
⑵ A=1,2,3，R=x,y| xA∧yA∧x＋y≠3 
⑶ A= Z
+
(正整数集合)，R=x,y| xA∧yA∧x×y是奇数
⑷ A=P(X)，|X|≥2，R=x,y| xA∧yA∧(xy∨yx)
解：⑴R 不是A上的等价关系。xA，x
－
x=0≠2，所以x,xR
，
R 不是自反的。
⑵R不是A上的等价关系。1+3≠3且3+2≠3，即1,3R且3,2 R，但1+2=3，即1,2R，所
以R不是传递的。
⑶R不是A上的等价关系。2 A=Z
+
，2×2=4不是奇数，所以2,2R，R不是自反的。
⑷R不是A上的等价关系。令X=1,2，A=P(X)=,1,2,1,2
11,2，所以1,1,2R，但1,2⊈2，所以1,2, 1R
69

第1章 习题解答
R不是对称的。
3.设A=1,2,3,4,5，A上的等价关系R定义为：
R=1,2,2,1,3,4,4,3∪I
A
画出关系图，找出所有等价类，总结等价类和关系图的关系。
解：R的关系图如图4.34所示。
[1]
R
=[2]
R
=1,2，[3]
R
=[4]
R
=3,4，[5]
R
=5
关系图每一个连通分支的结点构成的集合是一个等价类。或者说，每一
个等价类导 出了关系图的一个连通分支。
4.设R是A上的二元关系，
S=a,b| aA∧ bA∧(c)(a,cR∧c,bR)，证明若R是A上的等
价关系，则S也是A上 的等价关系。
证明：①证明S是自反的。
xA，因为R是自反的，故有x,xR∧x,xR，所以x,xS
②证明S是对称的。
x,ySx,cR∧c,yRc,xR∧y,cR (R是对称的)
y,xS (S的定义)
③证明S是传递的。
x,y S∧y,zSx,cR∧c,yR∧y,dR∧d,zR
x,yR∧y,zR (R是传递的)
x,zS (S的定义)
S也是A上的等价关系。
5.设AZ
+
×Z
+
( Z
+
是正整数集合)， R是A上的二元关系，定义为：
R=x,y,u,v| x,yA∧u,vA∧x＋v =y＋u)
证明R是A上的等价关系。

证明：①x,yA，因为x＋y=y＋x,所以x,y，x,yR
②x,y,u,vR，x＋v=y＋uu＋y= v＋x, 所以u,v,x,yR
③x,y,u,vR∧u,v,a,b R，x＋v=y＋u,u+b=v+a,两端相加，化简得x＋b=y＋a，
所以有x,y ,a,bR
R是A上的等价关系。
6.设R是A上的对称和传递关系，证明如果 aA，bA，使a,bR，则R是A上的等价关系。
证明：aA，bA，使a ,bR，因为R是对称的，b,aR，又因为R是传递的，所以a,aR。
R是A上的 自反关系。即R是是A上的等价关系。
7.设C*是实数部分非零的全体复数组成的集合。R是C*上的二元关系，定义为：
R=(a＋bi),(c＋di)|
(a＋bi)
C*∧
(c＋d i)
C*∧
ac
＞
0

证明R是等价关系。给出关系R的等价类的几何解释。
证明：C*=a＋bi| a≠0
①a＋biC* a≠0a
2
＞0(a＋bi),( a＋bi)R，所以R是自反的。
②(a＋bi),(c＋di)R
ac
＞
0

ca
＞
0
(c＋di), (a＋bi)R，所以R是对称的。
③(a＋bi),(c＋di)R∧(c＋di), (e＋fi)R
ac
＞
0
∧ce＞
0

a与 c同号且a不等于0
∧e
与c同号
且
e
不等于0

ae
＞
0
(a＋bi),(e＋fi)R，所以R是传递的。
这就证明了R是等价关系。
70

第1章 习题解答
几何解释为：
C*=a＋bi| a≠0是除了y轴以外的全平面。
 a+biC*。
当a＞
0时，
[a+bi]
R
=x＋yi| ax＞0=x＋yi| x＞0是第1，4象限(不含y轴)。
当a＜
0时，
[a+bi]
R
=x＋yi| ax＞0=x＋yi| x＜0是第2，3象限(不含y轴)。

8.设
1< br>和
2
是非空集合A上的划分，并设R
1
和R
2
分别 是由
1
和
2
导出的等价关系，证明 
1
是
2
的细分的充要条件是R
1
R
2
。
证明：设
1
是
2
的细分，下证R
1
R
2
x,y R
1
y[x]
R1
存在[x′]
R2

2
，[x]
R1
[x′]
R2
x[x′]
R2
[x]
R2
=[x′]
R2
[x]
R1
[x]
R2
y[x]
R2
x,yR
2
所以R
1
R
2
设R< br>1
R
2
，下证
1
是
2
的细分，
 [x]
R1

1
，下证[x]
R1
[x]
R2

2
y[x]
R1
x,yR
1
R
2
x,yR
2
 y[x]
R2
， 所以[x]
R1
[x]
R2

2

9.设R< br>j
表示整数集合Z上的模j等价关系，R
k
表示整数集合Z上的模k等价关系。 证明 ZR
k
是
ZR
j
的细分的充要条件是k是j的整数倍。
证明： ZR
k
是ZR
j
的细分，下证k是j的整数倍。
由习题4.5的第8题得R
k
R
j
。

k
≡
0 mod kk
,
0R
k
 k
,
0R
j
k
≡
0 mod jk
－
0=mjk=mj，即k是j的整数倍。
设k是j的整数倍，下证ZR
k
是ZR
j
的细分。
令k=mj。
x,yR
k
x
≡
y mod k x
－
y=nk=nmj x
≡
y mod jx,yR
j
，故R
k
R
j
由习题4.5的第8题得ZR
k
是ZR
j
的细分。

习题 4.6
1.设A=a,b,c,d,e，R是A上的二元关系，定义为：
R=a,b,a,c,a,d,b,a, b,c,c,a,c,b,d,a∪I
A

验证R是A上的相容关 系，写出关系矩阵，画出关系图和简化关系图，利用简化关系图找出所有
最大相容类，写出完全覆盖C< br>R
(A)。
解：验证R是A上的相容关系。
I
A
R，所以R是自反的。
R中有a,bR和b,aR， a,cR和c,aR，a,dR和d,aR，b,cR和c,bR，所以R是对称的。
R是A上的相容关系。
R关系矩阵是：
71

第1章 习题解答

1


1
M
R
=

1


1


0
1110


1100

1100

< br>
0010


0001

图4.35和图4.36 分别是R关系图和简化关系图。
最大相容类如下：a,b,c、a,d和e
完全覆盖C
R
(A)=a,b,c,a,d,e











2.设X=1,2,3,4,5,6，S=1,2,3,1,3,6,3,5,6, 3,4,5是X的覆盖，求S导出的相容关系R，写
出关系矩阵，画出关系图和简化关系图，利用 简化关系图找出所有最大相容类，写出完全覆盖C
R
(X)。
解：S导出的相容关系R是：
R=1,2,3×1,2,3∪1,3,6×1 ,3,6∪3,5,6×3,5,6∪3,4,5×3,4,5
=1,1, 1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3∪
1,1,1,3,1,6,3,1,3,3,3,6,6,1,6, 3,6,6∪
3,3,3,5,3,6,5,3,5,5,5,6 ,6,3,6,5,6,6∪
3,3,3,4,3,5,4,3 ,4,4,4,5,5,3,5,4,5,5
=1,2,1,3, 1,6,2,1,2,3,3,1,3,2,3,4,3,5,3,6, < br>4,3,4,5,5,3,5,4,5,6,6,1,6,3,6,5 ∪I
X
R的关系矩阵是：

1


1

1
M
R
=


0


0

1

11001


11000

11111



01110


011 11

01011


R关系图和简化关系图如图图4.37和图4 .38所示。
最大相容类如下：1,2,3、1,3,6、3,5,6和3,4,5
完全覆盖C
R
(A)=1,2,3,1,3,6,3,5,6,3, 4,5
72

第1章 习题解答












3.设R是A上的二元关系，证明rs(R) 是A上的相容关系。
证明：方法1：
根据自反闭包的定义rs(R)是自反的，根据对称闭包的定义sr(R)=rs(R)是对称的。所以，rs (R) 是A
上的相容关系。
方法2：
因为I
A
s(R)∪I
A
=rs(R)，即I
A
rs(R)，所以rs(R)是自反的。
又因为(rs(R))
C
=(R∪R
C
∪I
A
)
C
=R
C
∪(R
C
)
C
∪I
A
= R∪R
C
∪I
A
= rs(R) ，所以rs(R)是对称的。
所以，rs(R) 是A上的相容关系。
4.设R是A上的相容关系，证明t(R)= R∪R
2
∪R
3
∪…是A上的等价关系。
证明：①因为I
A
Rt(R)，即I
A
t(R)，所以t(R)是自反的。
② x ,yt(R)，kZ
+
使x,yR
k
，而(R
k)
C
=(R
C
)
k
=R
k
，故有x ,y(R
k
)
C
y xR
k
t(R)，于是y
xt(R)，所以t(R)是对称的。
③ 根据传递闭包的定义t(R)是传递的。
所以t(R)是A上的等价关系。
5.设R和S是A上的相容关系，回答下列问题。
⑴ 复合关系R

S是A上的相容关系吗？
⑵ R∪S是A上的相容关系吗？
⑶ R∩S是A上的相容关系吗？
解：⑴不一定。
反例：设A=1,2,3 ，R=1,2,2,1∪I
A
，S=2,3,3,2∪I
A
，R和S是A上的相容关系。而

R

S=1,2,1,3,2,1∪I
A
R

S不是对称的，因而不是A上的相容关系。
⑵是。
因为I< br>A
R且I
A
S，所以I
A
R∪S，故R∪S是自反的； 又因为(R∪S)
C
=R
C
∪S
C
=R∪S，故R∪S是< br>对称的。于是R∪S是A上的相容关系。
⑶是。
因为I
A
R且I
A
S，所以I
A
R∩S，故R∩S是自反的；又因为(R∩S)
C
=R
C
∩S
C
=R∩S，故R∩S是
对称的。于是R∩S 是A上的相容关系。
6.证明集合X上的相容关系R与集合X的完全覆盖C
R
(X)是一一对应的。
此题改写为：设R和S是X上的相容关系。集合C
R
(X) 和C
S
(X)是集合X的两个完全覆盖，则R=S
73

第1章 习题解答
的充分必要条件是C
R
(X)=C
S
(X)。
证明：设R=S，下证C
R
(X)=C
S
(X)
先证C
R
(X)C
S
(X)。CC
R
(X)，以下证明C C
S
(X)
①aC且bC，a,bR=S，a,bS，所以C是S形成的相容类。
②aX－C，由于C是R形成的最大相容类，bX使得a,bR=S，所以a,bS。故C 是S
形成的最大相容类。即CC
S
(X)。于是C
R
(X)C< br>S
(X)；同理可证C
S
(X)  C
R
(X)。
所以C
R
(X)=C
S
(X)
设C
R
(X)=C
S
(X)，下证R=S
a,b R，C
j
C
R
(X)使得a,bC
j
，由于C
R
(X)=C
S
(X)，所以C
j
C
S
(X) ，a,bS。即RS；同理可
证SR。
所以R=S。
习题 4.7
1.集合A是自然数集合的子集，A上的整除关系R是偏序关系。定义为R=x,y| xA∧yA∧x
整除y。求出下列集合A上的盖住关系COV A，画出哈斯图，指出该偏序关系是否为全
序关系。
⑴ A=3,9,27,54
⑵ A=1,2,3,4,6,8,12,24
⑶ A=1,3,5,9,15,18,27,36,45,54
⑷ A=1,2,3,4,5,6,7,8,9,10,11,12
解：⑴R=3,9,3, 273,54,9,27,9,5427,54∪I
A

集合A上的盖住关系COV A=3,9,9,2727,54
哈斯图如图4.39所示。
R是全序关系。
⑵ R=1,2,1,3, 1,4,1,6,1,8,1,12,1,24,2,4,
2,6, 2,8,2,12,2,24,3,6,3,12,3,24,4,8,
4,12,4,24,6,12,6,24,8,24,12,24∪I
A

COV A=1,2,1,3,2,4,2,6,3,6,4,8,4,12,
6,12,8,24,12,24
哈斯图如图4.40所示。
R不是全序关系。
⑶ R=1,3,1,5,1,9,1,15,1 ,18,1,27,1,36,1,45,1,54,
3,9,3,15 ,3,18,3,27,3,36,3,45,3,54,
5,15,5 ,45,9,18,9,27,9,36,9,45,9,54,
15,45,18,36,18,54,27,54∪I
A

COV A=1,3,1,5,3,9,3,15,5,15,9,18, 9,27,9,45,15,45,18,36,
18,54,27,54
哈斯图如图4.41所示。
不是全序关系。
⑷ R=1,2,1,3,1,4,1,5,1,6,1,7,1,8 ,1,9,1,10,1,11,1,12,
2,4,2,6,2,8 ,2,10,2,12,3,6,3,9,3,12,4,8,4,12,
74

第1章 习题解答
5,10,6,12∪I
A

COV A=1,2,1, 3,1,5,1,7,1,11,2,4,2,6,3,6,3,9,
4,8,4,12,5,10,6,12
哈斯图如图4.42所示。
不是全序关系。












2.求出下列各偏序集A,≼的盖住关系COV A，画出哈斯图，找出A 的子集B
1< br>、B
2
和B
3
的极大
元、极小元、最大元、最小元、上界、下 界、上确界和下确界。
⑴ A=a,b,c,d,e，≼=a,b,a,c,a,d a,e,b,e,c,ed,e∪I
A

B
1
=b,c,d ，B
2
=a,b,c,d ，B
3
=b,c,d,e
⑵ A=a,b,c,d,e，≼=c,d∪I
A

B
1
=a,b,c,d,e，B
2
=c,d ，B
3
=c,d,e
⑶ A=P(a,b,c)，≼=

x,y

 xP(A)∧yP(A)∧xy 
B
1
=,a,b，B2
=a,c，B
3
=a, c,a,b,c
解：⑴COV A=a,b,a,c,a,d,b,e,c,e,d,e
哈斯图如图4.43所示。
A 的子集B
1
、B
2
和B< br>3
的极大元、极小元、最大元、最小元、上界、下界、
上确界和下确界如表4.3所示。



表4.3

B
1

B
2

B
3

极大
元
b,c,d
b,c,d
e
极小
元
b,c,d
a
b,c,d
最大
元
无
无
e
最小
元
无
a
无
上界
e
e
e
下界
a
a
a
上确
界
e
e
e
下确
界
a
a
a

⑵COV A=c,d
哈斯图如图4.44所示。

75

第1章 习题解答




A 的子集B
1
、B
2
和B
3
的极大元、极小元、最大元、最小元、上界 、下界、上确界和下确界如表
4.4所示。
表4.4

B
1

B
2

B
3


⑶A=P(a,b,c)=,a,b,c,a, b,a, c,b, c,a,b,c
≼=,a,,b,,c,,a,b ,,a,c,,b,c,,a,b,c,
a,a,b ,a,a,c,a,a,b,c,b,a,b,b,b,c ,b,a,b,c,
c,a,c,c,b,c,c, a,b,c,a,b,a,b,c,a,c,a,b,c,
b,c,a,b,c∪I
A

COV A=,a ,,b,,c,a,a,b,a,a,c,b,a,b ,
b,b,c,c,a,c,c,b,c,a,b ,a,b,c,a,c,a,b,c,b,c,a,b,c
哈斯图如图4.45所示。
A 的子集B
1
、B
2
和B< br>3
的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界如表
4.5所示。
表4.5

B
1

B
2

B
3


极大
元
a,b

a,c

a,b,c

极小
元

a,c

a,c
最大
元
无
无
a,b,c

最小
元

无
a,c
上界
a,b,c,
a,b
a,b,c,
a,c
a,b,c
下界


a,c
上确
界
a,b
a,c
a,b,c

下确
界


a,c
极大
元
d
d,e
极小
元
c
c,e
最大
元
无
d
无
最小
元
无
c
无
上界
无
d
无
下界
无
c
无
上确
界
无
d
无
下确
界
无
c
无
a,b,d,e a,b,c,e
76

第1章 习题解答















3.设R是A上的二元关系，如果R是传递的和反自反的，称R是A上的拟序关系。证明
⑴ 如果R是A上的拟序关系，则r(R)=R∪I
A
是A上的偏序关系。
⑵ 如果R是A上的偏序关系，则R－I
A
是A上的拟序关系。
证明：⑴设R是A上的拟序关系，下证r(R)=R∪I
A
是A上的偏序关系。
①由自反闭包的定义知r(R)=R∪I
A
是自反的。
②证明r(R)=R∪I
A
是反对称的。
反证法。设x,yR∪I< br>A
∧y,xR∪I
A
，而x≠y。因为x≠y，所以x,yIA
∧y,xI
A
。于是x,yR
∧y,xR，由R的 传递性得x,xR，与R的反自反性矛盾。所以x=y。r(R)=R∪I
A
是反对称的 。
③证明r(R)=R∪I
A
是传递的。
(R∪I
A
)

(R∪I
A
)=R

R∪R∪I
A
R ∪R∪I
A
=R∪I
A
，即(R∪I
A
)

(R∪I
A
)R∪I
A
，r(R)=R∪I
A
是传递的 。
r(R)=R∪I
A
是A上的偏序关系。
⑵设R是A上的偏序关系，则R－I
A
是A上的拟序关系。
①xA， x,xI
A
，x,xR－I
A
，R－I
A
反自反 的。
②证明R－I
A
是传递的。
设x,yR－I
A
∧y,zR－I
A
，则x,yR∧x≠y∧y,zR∧y≠z，因为R是 传递的，所以x,zR，
以下证明x≠z。
反证法。设x=z，则由x,yR∧ y,zR可推出x,yR∧y,xR，因为R是反对称的，所以x=y，
与x≠y矛 盾。从而x,zR∧x≠z，x,zR－I
A
。
这就证明R－I
A
是传递的。
4.设R是集合S上的二元关系，S′S，定义S′上的二元关系R′如下：
R′=R∩(S′×S′)
确定下述每一断言是真还是假？如果是真，给出证明，否则举一反例。
⑴ 如果R在S上是自反的，那么R′在S′上是自反的。
⑵ 如果R在S上是反自反的，那么R′在S′上是反自反的。
⑶ 如果R在S上是对称的，那么R′在S′上是对称的。
⑷ 如果R在S上是反对称的，那么R′在S′上是反对称的。
⑸ 如果R在S上是传递的，那么R′在S′上是传递的。
77

第1章 习题解答
⑹ 如果R是S上的偏序关系，那么R′是S′上的偏序关系。
⑺ 如果R是S上的拟序关系，那么R′是S′上的拟序关系。
⑻ 如果R是S上的线序关系，那么R′是S′上的线序关系。
⑼ 如果R是S上的良序关系，那么R′是S′上的良序关系。
证明：⑴因为R在S上是自反的，所以I< br>S
R，显然I
S′
S′×S′，又因为S′S，所以I
S′I
S
R，所以
I
S′
R∩(S′×S′)=R′，故R′ 在S′上是自反的。
⑵ xS′S，xS，因为R在S上是反自反的，x,xR，x ,xR∩(S′×S′)=R′，所以x,xR′。
故R′在S′上是反自反的。
⑶ (R′)
C
=(R∩(S′×S′))
C
=R
C∩(S′×S′)
C
=R∩(S′×S′)=R′，故R′在S′上是对称的。
⑷ a,bR′=R∩(S′×S′)∧a≠ba,bR∧a,bS′×S′∧a≠b
a,bR∧a≠bb,aR
b,aR∩(S′×S′)=R′
b,aR′
故R′在S′上是反对称的。
⑸ a,bR′∧ b,cR′a,bR∧a,bS′×S′∧b,cR∧b,cS′×S′
a,bR∧b,cR∧a,bS′×S′∧b,cS′×S′
a,cR∧a,cS′×S′
a,cR∩(S′×S′)=R′
a,cR′
故R′在S′上是传递的。
⑹ 由⑴、⑷和⑸知R′是S′上的偏序关系。
⑺由⑵和⑸知R′是S′上的拟序关系。
⑻ 由⑴、⑷和⑸知R′是S′上的偏序关系。
x,yS′，x,yS，x,yS′×S′且 y,xS′×S′，因为R是S上的线序关系，所以x,yR或y,xR。
当x,yR时，x,yR∩(S′×S′)=R′，即x,yR′
当y,xR时，y,xR∩(S′×S′)=R′，即y,xR′
故R′是S′上的线序关系。
⑼ 由⑴、⑷和⑸知R′是S′上的偏序关系。
设S ′′是S′的非空子集，≠S′′S′，而S′S，所以S′′是S的非空子集。因为R是S上的良序关系 ，
所以S′′有最小元a。aS′′且xS′′有a,xR且a,xS′×S′，于 是a,xR∩(S′×S′)=R′，a,xR′，
所以a是R′关于集合S′′的最小元 。故R′是S′上的良序关系。
习题 5.1
1.设A=a,b,c，B=1,2, 3，试说明下列A到B二元关系，哪些能构成A到B的函数？
⑴ f
1
=a,1, a,2,b,1,c,3
⑵ f
2
=a,1,b,1,c,1
⑶ f
3
=a,2,c,3
⑷ f
4
=a,3,b,2,c,3,b,3
⑸ f
5
=a,2,b,1,b,2
解：⑴不能构成函数。因为a,1f
1
且a,2f
1

⑵能构成函数
78

第1章 习题解答
⑶不能构成函数。因为domf
3
≠A
⑷不能构成函数。因为b,2f
4
且b,3f
4

⑸能构成函数。
2.试说明下列A上的二元关系，哪些能构成A到A的函数？
⑴ A=N(N为自然数集合)，f
1
=a,b| aA∧bA∧a＋b＜10
⑵ A=R(R为实数集合)，f
2
=a,b| aA∧bA∧b=a
2

⑶ A=R(R为实数集合)，f
3
=a,b| aA∧bA∧b
2
=a
⑷ A=N(N为自然数集合)，f
4
=a,b| aA∧bA∧b为小于a的素数的个数
⑸ A=Z(Z为整数集合)，f
5
=a,b| aA∧bA∧b=|2a|＋1 < br>解：⑴不能构成函数。由于1+1＜10且1+2＜10，所以1,1f
1
且1 ,2f
1
。
⑵能构成函数。
⑶不能构成函数。由于1
2=1且(-1)
2
=1，所以1,1f
3
且1,-1f3
。
⑷能构成函数。
⑸能构成函数。
3. 回答下列问题。
⑴ 设A=a,b，B=1,2,3。求B
A
，验证|B
A
|= |B|
|
A
|
。
××
⑵ 设A=a,b，B=1, 2。求B
AA
，验证|B
AA
|=|B|
|
A
| ×|
A
|
。
解：⑴f
0
=a,1,b,1
f
1
=a,1,b,2
f
2
=a,1,b,3
f
3
=a,2,b,1
f
4
=a,2,b,2
f
5
=a,2,b,3
f
6
=a,3,b,1
f
7
=a,3,b,2
f
8
=a,3,b,3
B
A
=f
0,
f
1,
f
2,
f
3,
f
4,
f
5,
f
6,
f
7,
f
8

|B
A
|=9=3
2
= |B|
|
A
|

⑵ A×A=a,a,a,b,b,a,b,b
f
0
=a, a,1,a,b,1,b,a,1,b,b,1
f
1
=a,a,1,a,b,1,b,a,1,b,b,2
f< br>2
=a,a,1,a,b,1,b,a,2,b,b,1
f
3
=a,a,1,a,b,1,b,a,2,b, b,2
f
4
=a,a,1,a,b,2,b,a, 1,b,b,1
f
5
=a,a,1,a,b,2, b,a,1,b,b,2
f
6
=a,a,1,a ,b,2,b,a,2,b,b,1
f
7
=a,a ,1,a,b,2,b,a,2,b,b,2
f
8
= a,a,2,a,b,1,b,a,1,b,b,1
f
9
=a,a,2,a,b,1,b,a,1,b,b,2 < br>f
10
=a,a,2,a,b,1,b,a,2,b, b,1
f
11
=a,a,2,a,b,1,b,a ,2,b,b,2
f
12
=a,a,2,a,b,2 ,b,a,1,b,b,1
79

第1章 习题解答
f
13
=a,a,2,a,b,2,b,a,1,b ,b,2
f
14
=a,a,2,a,b,2,b,a ,2,b,b,1
f
15
=a,a,2,a,b, 2,b,a,2,b,b,2

×
B
AA
=f
0,
f
1,
f
2,
f
3,
f
4,
f
5,
f
6,
f
7,
f
8,
f
9
f
10,
f
11,
f
12,
f
13,
f
14,
f
15

×
|B
AA
|=16=2
4
=|B|
|
A
|×|
A
|

4.下列函数中，哪些是单射？哪些是满射？哪些是双射？为什么？
⑴ f：N→N，f(x)= x
2
＋1
⑵ f：Z→Z， f(x)=(x mod 3)(函数值为x除以3的余数)
⑶ f：N→N，
f(x)


1

0

1

0
若x为奇数
若x 为偶数
若x为奇数
若x为偶数

⑷ f：N→0,1，
f(x)

⑸ f：Z
＋
→R，f(x)=3
x

⑹ f：R→R，f(x)=x
3
解：⑴是单射，不是满射，不是双射。
当x,yA ，x≠y，x
2
≠y
2
，x
2
＋1≠y
2
＋1，f(x)≠f(y)。所以f：N→N是单射。
因为xN，f(x)≠0N。所以f：N→N不是满射。
因为不是满射，所以不是双射。
⑵不是单射，不是满射，不是双射。
因为6≠9，而f(6)=(6 mod 3)=0=(9 mod 3)=f(9)。所以f：Z→Z不是单射。
因为xZ，f(x)≠3Z。所以f：Z→Z不是满射。
因为不是单射且不是满射，所以不是双射。
⑶不是单射，不是满射，不是双射。
因为1≠3，而f(1)=f(3)。所以f：N→N不是单射。
因为xZ，f(x)≠2N。所以f：N→N不是满射。
因为不是单射和不是满射，所以不是双射。
⑷不是单射，是满射，不是双射。
因为1≠3，而f(1)=1=f(3)。所以f：N→0,1不是单射。
显然，f：N→0,1是满射。
因为不是满射，所以不是双射。
⑸是单射，不是满射，不是双射。
f：Z
＋
→R，f(x)=3
x
是单调递增函数，所以是单射。
因为xZ
＋
，f(x)≠0R。所以f：Z
＋
→R不是满射。
因为不是满射，所以不是双射。
⑹是单射，是满射，是双射。
f：R→R，f(x)=x
3
是单调递增函数，所以是单射。
因为yR，有x=
3
y
R，使f(x)= f(
3
y
)=(
3
y
)
3
=y。所以f：R→R，f(x)=x3
是满射。

因为是单射和满射，所以是双射。
5.设A=1,2,3,4，A上的等价关系R为：
R=1,4,4,1,2,3,3,2∪I
A

80

第1章 习题解答
求自然映射f：A→AR
解：AR=1,4,2,3
f=1,1,4,2,2,3,3,2,3,4,1,4
6.设f: Z×Z→Z(Z为整数集合)，f(x,y)= x＋y；g: Z×Z→Z，g(x,y)= x×y。 试证明f 和g是满射函
数，但不是单射函数。
证明：xZ，0,xZ×Z，f (0,x)= 0＋x=x，所以f: Z×Z→Z，f(x,y)=x＋y是满射。
1,xZ×Z，f (1,x)= 1×x=x，所以g: Z×Z→Z，g(x,y)=x×y是满射。
对于1,2Z×Z，2 ,1Z×Z，f(1,2)=3=f(2,1)，但1,2≠2,1，所以f: Z×Z→Z，f(x,y)= x＋y
不是单射函数。
对于3,2Z×Z，2,3Z×Z，g(3,2)=6= g(2,3)，但3,2≠2,3，所以g: Z×Z→Z，g(x,y)= x×y
不是单射函数。
7.设A和B是有限集合，|A|=n，|B|=m。
⑴有多少个不同的单射函数f：A→B。
解：要使f：A→B是单射函数，必须n≤m，因此 ，当n＞m时，无A到B的单射函数。当n≤m
n
时，共有
P
m
=n (n-1)…(n-m+1)
⑵有多少个不同的双射函数f：A→B。
解：要使f：A→B是双射函数，必须n=m，此时共有m!个双射函数。请参看习题5.2的第6题。
8.设f：A→B，CA，证明f(A)－f(C)f(A－C)
证明：f(x)f( A)－f(C)f(x)f(A)∧f(x)f(C)xA∧xCxA－C f(A－C)
所以, f(A)－f(C)f(A－C)
9.设A=a
1
,a
2
,…,a
n
，试证明任何从A到A的函数，如果它是单射，则它必是满射。反之 亦真。
证明：设f：A→A是单射，下证f是满射。
反证法，设f不是满射，至少有一个元素不是f的像，设这个元素为a
j
，则ran fA-a
j
，所以ran
fA，从而有|ran f|<|A|，与f是单射矛盾。
设f：A→A是满射，下证f是单射。
反证法，设f不是 单射，a
i
A，a
j
A，使f(a
i
)=f(aj
)，而a
i
≠a
j
，构造函数
f
1
：A-a
i
→A，f
1
(x)=f(x)
因为f：A→A是满射，所以f
1
：A-a
i
→A也是满射。故 有|A-a
i
|≥|A|。又因为a
i
A， A-a
iA，
|A-a
i
|＜|A|，所以，|A|≤|A-a
i|＜|A|，即|A|＜|A|，矛盾。
10.设f：A→B，CA，DA，试证明：
⑴ f(C∪D)= f(C)∪f(D)
⑵ f(C∩D) f(C)∩f(D) 证明：⑴f(x)f(C∪D)xC∪DxC∨xDf(x)f(C)∨f(x)f(D )
f(x)f(C)∪f(D)
即f(C∪D)= f(C)∪f(D)
⑵ f(x)f(C∩D)xC∩DxC∧xDf(x)f(C)∧f(x)f(D)f(x) f(C)∩f(D)
即f(C∩D) f(C)∩f(D)
11.设f：A→B。
g：B→P(A)，定义为：对于bB，g(b)= x|xA∧f(x)=b。
证明：如果f是A到B的满射，则g是B到P(A)的单射。
证明：以下证明g：B→P(A)的单射。g(b)=x|xA∧f(x)=b。
81

第1章 习题解答
设x
1
B，x
2
B且x
1
≠x
2
，因为f是A到B的满射，y
1
A ，使f(y
1
)=x
1
，y
2
A，使f(y
2
)=x
2
。因为
x
1
≠x
2
，所以f(y
1
)≠f(y
2
)，又因为f是函数，故有y
1
≠y
2
。由g的定义有，y
1
g(x
1
)，y
2
 g(x
2
)。因为f(y
2
)=x
2
≠x
1
，所以y
2
g(x
1
)，故有g(x
2
)⊈g(x1
)，即g(x
1
)≠g(x
2
)。
这就证明了g是B到P(A)的单射。
12.设

A,≼

是偏序集，xA，令f(a)= x|xA∧x≼a ，证明：
⑴ f：A→P(A) 是单射。
⑵ 若 a≼b 时，必有 f(a)f(b)
证明：⑴aA，bA且a≠b
当a≼b时，因为a ≠b，则无b≼a，bf(a)。又由偏序关系的自反性知b≼b，从而bf(b)。f(a)≠f(b)
当b≼a时，类似的可以证明f(a)≠f(b)
⑵设a≼b，xf(a)xA∧x≼ a，由a≼b和偏序关系的传递性xA∧x≼bxf(b)。即f(a)f(b)。
习题 5.2
1.设X=x
1
,x
2
, x
3
, x
4
，Y= y
1
,y
2
, y
3
, y
4
, y
5
，Z= z
1
,z
2
, z
3

f：X→Y，定义为f= x
1
,y
2
,x
2
,y
1
, x
3
,y
3
,x
4
,y
5
 g：Y→Z，定义为g=y
1
,z
1
,y
2
, z
2
,y
3
,z
3
,y
4
,z< br>3
,y
5
,z
2

试求函数g在函数f左边 的复合关系g

f，验证复合关系g

f是X到Z的函数。
解：g

f=x
1
,z
2
,x
2
,z< br>1
,x
3
,z
3
,x
4
,z
2

mod g

f=x
1,
x
2
,x
3
,x
4
=X。当x
1
= x
2
时，f(x
1
)=f(x
2
)
g

f：X→Z
2.设f,g,hR
R
，且f(x) =x
2
-2，g(x) =x＋4，h(x) =x
3
-1
⑴ 试求g

f和f

g
⑵ g

f和f

g是单射？满射？双射？
⑶ f,g,h中哪些有反函数？若有，求出反函数。
解：⑴ g

f(x)= x
2
+2
f

g(x)=x
2
+8x+14
⑵ g

f不是单射，不是满射，不是双射。
f

g不是单射，不是满射，不是双射。
⑶ f不是单射，不是满射，不是双射。无反函数。
g是单射，是满射，是双射。有反函数。g
-1
(x)= x-4
h是单射 ，是满射，是双射。有反函数。h
-1
(x)=
3
x1

3.设f：A→B，g：B→C，g和f的复合函数g

f：A→C，试证明:
⑴ 如果g

f是单射，那么f是单射。
⑵ 如果g

f是满射，那么g是满射。
82