《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

第一章 命题逻辑基本概念

课后练习题答案

1、是命题的为（1）、（2）、（3）、（6）、（7）、（10）、（11）、（12）、（13） 是简单命题的为（1）、（2）、（7）、（10）、（13） 是真命题的为（1）、（2）、（3）、（10）、（11） 真值现在不知道的为（13） 2、3略

4.将下列命题符号化，并指出真值：

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；

（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1； （3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1； （4）p∧q,其中，p:3是素数，q:3是偶数,真值为0； （5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.

5.将下列命题符号化，并指出真值：

（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1； （2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1； （3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0； （4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1； （5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；

6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨； （2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.

7.因为p与q不能同时为真.

8. 设p:2<1，q:3<2 (1) p→q，真值为1 (2) p→┐q，真值为1 (3) ┐q→p，真值为0 (4) ┐q→p，真值为0 (5) ┐q→p，真值为0 (6) p→q，真值为1

9.（2）、（6）真值为0，其余为1 10. （1）、（4）真值为0，其余为1 11、12略

13.设p:今天是星期一，q:明天是星期二，r:明天是星期三： （1）p→q，真值为1（不会出现前件为真，后件为假的情况）； （2）q→p，真值为1（也不会出现前件为真，后件为假的情况）； （3）p

q，真值为1；

（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1. 14略

15、p、q为真命题，r为假命题，（4）的真值为1，其余为0 16、（4）的真值为1，其余为0 17、真

18、小王会唱歌，小李不会跳舞

19、（1）（4）（6）为重言式，（3）为矛盾式，其余为非重言式的可满足式 20、（1）01,10,11 （2）00,10,11 （3）00,01,10 （4）01,10,11

21、（1）011；（2）010,110,101,100；（3）100,101

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

22、无成真赋值 23、无成假赋值 24、均为重言式 25、均为矛盾式

26、前者为矛盾式，后者为重言式 27略；28不能；29略；30不能

返回

第二章 命题逻辑等值演算

本章自测答案

3、（1）矛盾式；（2）重言式；（3）可满足式 5.(1)：

∨

∨

,成真赋值为00、10、11；

(2)：0，矛盾式，无成真赋值； (3)： 7.(1)： (2)：

8.(1)：1 (2)： (3)： 11.(1)： (2)：

∨∨

∨∨∧

∨∧

∧∨∧

∧∨.

∧∨

∧∨

； 1；

∨∧∨ ∧∨∨∧∨∨∧

,重言式； ∨∧

∨∧

∨∧

∨

；

∨∨

∨∨

∨∨

∨

∧

∧∧

∧∧

； ；

∨

∨

∨

∨

∨

∨

∨

,重言式，000、001、010、011、100、101、110、111全部为成真赋值；

0，矛盾式.

(3)：0 12.A

∧

∧∧∧ ∨∨.

第三章 命题逻辑的推理理论

本章自测答案

6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系

(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确 (1)设p:今天是星期一，q:明天是星期三，推理的形式结构为 (p→q)∧p→q(记作*1)

在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.

可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即 (p→q)∧p→q q

(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为 (p→q)∧p→q(记作*2)

可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等 (p→q)∧q→p

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

(┐p∨q) ∧q →p q →p ┐p∨┐q

∨

∨

从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.

9.设p:a是奇数，q:a能被2整除，r:a：是偶数 推理的形式结构为

(p→q┐)∧(r→q)→(r→┐p) (记为*)

可以用多种方法证明*为重言式，下面用等值演算法证明： (p→┐q)∧(r→q)→(r→┐p)

(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律) (p∨q)∨(┐p∧r)∨┐q∨┐r (┐p∨q)∨(┐q∧┐r) ┐p∨(q∨┐q)∧┐r 1

10.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数. 推理的形式结构为

(p→q)∧┐p→(┐q∧┐r) (┐p∨q) ∧┐p→(┐q∧┐r) ┐p→(┐q∧┐r) (使用了吸收律) p∨(┐q∧┐r)

∨

∨

∨

由于主析取范式中只含有5个W极小项，故推理不正确. 11.略

14.证明的命题序列可不惟一，下面对每一小题各给出一个证明 ① p→(q→r) 前提引入 ② P 前提引入 ③ q→r ①②假言推理 ④ q 前提引入 ⑤ r ③④假言推理 ⑥ r∨s 前提引入 （2）证明：

① ┐(p∧r) 前提引入 ② ┐q∨┐r ①置换 ③ r 前提引入 ④ ┐q ②③析取三段论 ⑤ p→q 前提引入 ⑥ ┐p ④⑤拒取式 （3）证明：

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

② ┐q∨q ①置换 ③ (┐p∨q)∧(┐p∨p) ②置换 ④ ┐p∨(q∧p ③置换 ⑤ p→(p∨q) ④置换

15.(1)证明：

① S 结论否定引入 ② S→P 前提引入 ③ P ①②假言推理 ④ P→(q→r) 前提引入 ⑤ q→r ③④假言推论 ⑥ q 前提引入 ⑦ r ⑤⑥假言推理 （2）证明：

① p 附加前提引入 ② p∨q ①附加 ③ (p∨q)→(r∧s) 前提引入 ④ r∧s ②③假言推理 ⑤ s ④化简 ⑥ s∨t ⑤附加 ⑦ (s∨t)→u 前提引入 ⑧ u ⑥⑦拒取式

16.(1)证明：

① p 结论否定引入 ② p→ ┐q 前提引入 ③ ┐q ①② 假言推理 ④ ┐r∨q 前提引入 ⑤ ┐r ③④析取三段论 ⑥ r∧┐s 前提引入 ⑦ r ⑥化简 ⑧ ┐r∧r ⑤⑦合取 （2）证明：

① ┐(r∨s) 结论否定引入 ② ┐r∨┐s ①置换 ③ ┐r ②化简 ④ ┐s ②化简 ⑤ p→r 前提引入 ⑥ ┐p ③⑤拒取式 ⑦ q→s 前提引入 ⑧ ┐q ④⑦拒取式 ⑨ ┐p∧┐q ⑥⑧合取 ⑩ ┐(p∨q) ⑨置换

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

⑾①口 ┐(p∨q) ∧(p∨q) ⑩口合取

17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。 前提：(p∧┐q) →r , p ,q →s , ┐s 结论：r 证明：

① q→s 前提引入 ② ┐s 前提引入 ③ ┐q ①②拒取式 ④ p 前提引入 ⑤ p∧┐q ③④合取 ⑥（p∧┐q）→r 前提引入 ⑦ r ⑤⑥假言推理

18．（1）设 p：今天是星期六，q：我们要到颐和园玩，s：颐和园游人太多。 前提：p→(p∨r) , s→┐q , p , s 结论：r 证明：

① s→┐q 前提引入 ② s 前提引入 ③ ┐q ①②假言推理 ④ p 前提引入 ⑤ p→(q∨r) 前提引入 ⑥ q∨r ④⑤假言推理 ⑦r ③⑥析取三段论

（2）设p:小王是理科学生，q：小王数学成绩好，r：小王是文科学生。 前提：p→q ,┐r→p ,┐q 结论：r 证明：

① p→q 前提引入 ② ┐q 前提引入 ③ ┐p ①②拒取式 ④ ┐r→p 前提引入 ⑤ r ③④拒取式

第四章 (一阶)谓词逻辑基本概念

本章自测答案

4.(1)┐x(F(x)∧ ┐G(x)) x( F (x) →G (x) ),其中,F(x)：x是有理数,G(x) ：x能表示成分数； (2)┐x( F (x) →G (x) ) x(F(x)∧ ┐G(x)),其中,F (x)：x在北京卖菜,G (x) ：x是外地人； (3)x( F (x) →G (x) ),其中,F (x)：x是乌鸦,G (x) ：x是黑色的； (4)xF(x)∧ G(x)),其中,F (x)：x是人,G (x) ：x天天锻炼身体。 因为本题中没有指明个体域,因而使用全总个体域。

5.(1)xy (F(x) ∧ G( y ) → H(x,y)),其中,F(x)：x是火车,G(y) ：y是轮船,H(x,y)：x比y快；

返回

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

(2)xy (F(x) ∧ G( y ) → H(x,y)),其中,F(x)：x是火车,G(y) ：y是汽车, H(x,y)：x比y快；

(3)┐x(F(x)∧y(G (y) → H (x,y))) x(F(x) → y(G(y) ∧ ┐H(x,y))),其中,F(x)：x是汽车,G (y) ：y是火车,H(x,y)：x比y快； (4)┐x(F(x)→y(G(y) → H(x,y))) xy(F(x)∧G(y)∧┐H(x,y))),其中,F(x)：x是汽车,G(y) ：y是火车,H(x,y)：x比y慢。 6.各命题符号化形式如下： (1)xy (x ．y = 0)； (2)xy (x ．y = 0)； (3)xy (y =x+1) (4)xy(x ．y = y．x) (5)xy(x ．y =x+ y) (6)xy (x + y ＜0 )

9.(1)对任意数的实数x和y,若x ＜y,则x ≠ y； (2)对任意数的实数x和y,若x–y = 0,则x＜y； (3)对任意数的实数x和y,若x＜y,则x–y≠0； (4)对任意数的实数x和y,若x–y ＜0,则x=y. 其中,(1)(3)真值为1(2)与(4)真值为0.

11.(1)、(4)为永真式,(2)、(6)为永假式,(3)、(5)为可满足式。 这里仅对(3)、(4)、(5)给出证明。

(3)取解释I 为：个体域为自然数集合N,F(x,y)：x ≤ y,在

下,xy F(x,y)为真,而xy F(x,y)也为真(只需取x =0即可),于是(3)中公

式为真,取解释 为：个体域仍为自然数集合N,而F(x,y)：x = y。此时,xyF(x,y)为真(取y为x即可),可是xyF(x,y)为假,于是(3)中公式在 下为假,这说明(3)中公式为可满足式。

(4)设I为任意一个解释,若在I下,蕴涵式前件xy F(x,y)为假,则

xyF(x,y)→yxF(x,y)为真,若前件xyF(x,y)为真,必存在I的个体域D1中的个体常项

x0,使

yF(0,y)为真,并且对于任意

x

y∈,F(0,y)为真,由于有

xx0∈

,F(0,y)为真,所以xF(x,y)为真,又其中y是任意个体变项,所以

yxF(x,y )为真,由于I的任意性,所

x

以(4)中公式为永真式(其实,次永真式可用第五章的构造证明法证明之)。 (5)取解释可满足式。

13．（1）取解释 取解释

为：个体域为自然数集合N，F（x）：x为奇数，G（x）：x为偶数，在 下， x（F（x）∨G（x））为真命题。 为：个体域为自然数集合,F(x,y)：x = y在

下,(5)中公式为真,而将F(x,y)改为F(x,y)：x ＜ y,(5)中公式就为假了,所以它为

为：个体域为整数集合Z，F（x）：x为正整数，G（x）：x为为负整数，在 下， x（F（x）∨G（x））为假命题。

（2）与（3）可类似解答。

14．提示：对每个公式分别找个成真的解释，一个成假的解释。

返回

第五章 谓词逻辑等值演算与推理

本章自测答案

2.(1) (F(a)∧ F(b)∧ F (c)) ∧ (G (a )∨G (b)∨G (c)) (2) (F(a)∧ F(b)∧ F (c)) ∨ (G (a)∧G (b)∧G (c)) (3) (F(a)∧ F(b)∧ F (c)) → (G (a)∧G (b)∧G (c)) (4) (F(a ,y) ∨ F(b,y)∨ F (c,y)) → (G (a)∨G (b)∨G (c))

5.提示：先消去量词，后求真值，注意，本题3个小题消去量词时，量词的辖域均不能缩小，经过演算真值分别为：1,0,1 . (1) 的演算如下：

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

xyF(x,y)

x (F(x,3)∨F(x,4))

(F(3,3)∨F(3,4))∧(F(4,3)∨F(4 ,4)) 1∧1 1

6.乙说得对，甲错了。本题中，全称量词 的指导变元为x ，辖域为(F (x)→G(x,y)),其中F(x )与G(x,y)中的x都是约束变元，因而不能将量词的辖域缩小。

7.演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定联结词“ ┐”。演算的第二步，在原错的基础上又用错了等值式，即 (F(x)∧(G(y)→ H(x,y))) ≠(F(x) ∧G(y)→H (x,y))

12.公式的前束范式不唯一，下面每题各给出一个答案。 (1) xy (F(x)→ G(z,y)); (2) xt (x,y) → G(x,t,z));

(3)

(4)

(5)

13.(1)xy(F(x) ∧G(y) ∧H(x ,y)),其中，F(x):x是汽车，G(y)：y是火车，H(x，y)：x比y跑的快； (2)xy(F(x) ∧G(y)→H(x ,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快； (3)xy(F(x) ∧G(y) ∧┐H(x ,y)),其中，F(x):x是火车，G(y)：y是汽车，H(x，y)：x比y跑的快； (4)xy(F(x) ∧G(y) → ┐H(x ,y)),其中，F(x):x是飞机，G(y)：y是汽车，H(x，y)：x比y慢； 14.(1)对F(x) → xG(x)不能使用EI规则，它不是前束范式，首先化成前束范式。 F(x) → xG(x) <=> x(F(y)→G(x))

因为量词辖域(F(y)→G(x))中，除x外还有自由出现的y，所以不能使用EI规则。

(2)对 x F(x) → y G(y)也应先化成前束范式才能消去量词，其前束范式为 x y(F(x) →G(y)),要消去量词，既要使用UI规则，又要使用EI规则。

(3)在自然推理系统F中EG规则为 A(c)/∴x(x)

其中c为特定的个体常项，这里A(y) = F(y) →G(y)不满足要求。

(4)这里，使F(a)为真的a不一定使G(a)为真，同样地使G(b)为真的b不一定使F(b)为真，如，F(x):x为奇数，G(x):x为偶数，显然F(3)∧G(4)为真，但不存在使F(x)∧G(x)为真的个体。

(5)这里c为个体常项，不能对F(c)→G(c)引入全称量词。 15.(1)证明：①xF(x) 前提引入 ②xF(x)→ y((F(y)∨G(y)) →R(y)) 前提引入 ③y((F(y)∨G(y)) →R(y) ①②假言推理 ④F(c) ①EI ⑤(F(c)∨G(c))→R(c) ③UI ⑥F(c)∨G(c) ④附加 ⑦R(c) ⑤⑥假言推理 ⑧xR(x) ⑦EG (2)证明①xF(x) 前提引入 ②x((F(x)→G(a)∧R(x))) 前提引入 ③F(c) ①EI ④F(c)→G(a)∧R(a) ②UI

(F(

x4 ((F(

((F(,

)→G()→(F(

,y) →G(,

,y))∧(G(,y) →F(4,y)));

,

)));

x

)) → (H (

,

) → L())).

) → ┐G (

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

⑤G(a)∧R(c) ③④假言推理 ⑥R(c) ⑤化简 ⑦F(c)∧R(c) ③⑥合取 ⑧x(F(x)∧R(x)) ⑦EG (3)证明：①┐xF(x) 前提引入 ②x┐F(x) ①置换 ③┐F(c) ②UI ④x(F(x)∨G(x)) 前提引入 ⑤F(c)∨G(c) ④UI

⑥F(c) ③⑤析取三段论 ⑦xF(x) ⑥EG (4)证明①x(F(x)∨G(x)) 前提引入 ②F(y)∨G(y) ①UI ③x(┐G(x)∨┐R(x)) 前提引入 ④┐G(y)┐R(y) ③UI ⑤x R(x) 前提引入 ⑥R(y) ⑤UI

⑦┐G(y) ④⑥析取三段论 ⑧F（y） ②⑦析取三段论 ⑨xF(x) ⑧UG

17．本题不能用附加前提证明法.

20.(1)与(2)均可用附加前提证明法。

22.(1)设F(x)：x为偶数，G(x):x能被2整除。 前提:x(F(x)→G(x))，F(6) 结论：G(6)

(2)设F(x)：x是大学生，G(x):x是勤奋的，a：王晓山。 前提:x(F(x)→G(x))，┐G(a) 结论：┐F(a)

23.(1)设F(x)：x是有理数，G(x):x是实数，H(x)：x是整数。 前提:x( F(x)→G(x))， x(F(x)∧H(x)) 结论:x(G(x)∧H(x)) 证明提示：先消存在量词。

(2)设F(x)：x是有理数，G(x):x是无理数，H(x)：x是实数，I(x)：x是虚数。 前提:x((F(x)∨G(x)) →H(x))， x( I(x)→┐H(x)) 结论:x(I(x)→(┐F(x)∧┐G(x)))

证明①x(I(x)→(┐H(x)) 前提引入 ②I(y)→H(y) ①UI ③x((F(x)∨G(x))→H(x)) 前提引入 ④(F(y)∨G(y))→H(y) ③UI ⑤┐H(y)→(┐F(y)∧┐G(y)) ④置换 ⑥I(y)→(┐F(y)∧┐G(y)) ②⑤假言三段论 ⑦x(I(x)→(┐F(x)∧┐G(x)) ⑧UG

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

24.设F(x)：x喜欢步行，G(x)：x喜欢骑自行车，H(x)：x喜欢乘汽车。 前提:x(┐F(x)→┐G(x))， x(G(x)∨H(x))， x┐H(x) 结论:x┐F(x)

证明①x┐H(x) 前提引入 ②┐H(c) ①UI ③x(G(x)∨H(x)) 前提引入 ④G(c)∨H(c) ③UI

⑤G(c) ②④析取三段论 ⑥x(F(x) →G(x)) 前提引入 ⑦F(c)→┐G(c) ⑥UI ⑧┐F(c) ⑤⑦拒取式 ⑨x┐F(x) ⑧UG

25.设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在事业中获得成功。 前提:x(F(x)→G(x))，x(G(x)∧H(x)→I(x))，a：王大海，F(a)，H(a) 结论：I(a)

证明①F(a) 前提引入 ②x(F(x)→G(x)) 前提引入 ③F(a)→G(a) ②UI ④G(a) ①③假言推理 ⑤H(a) 前提引入 ⑥x(G(x)∧H(x)→I(x)) 前提引入 ⑦G(a)∧H(a)→I(a) ⑥UI ⑧G(a)∧H(a) ④⑤合取 ⑨I(a) ⑦⑧假言推理

第六章 集合代数

本章自测答案

4.(1) ③ (2) ④ (3) ⑤ (4) ⑦ (5) ⑧ 6.只有(2)为真，其余为假。

9.(1) {4}；(2) {1,3,5,6}；(3) {2,3,4,5,6}；(4) {, { 1 }}；(5) {{ 4 },{1,4}}. 11.(1)； (2) {1,4,5}.

22.(2)、(3)、(4)、(8)、(10)为真，其余为假。

24.(1)为真，其余为假，因为

(P-Q) = P (P-Q)∩Q = P∩Q

= P∩Q (2)(3)(4)的反例：P ={1} ，Q ={2}

26.(A–B)∪(B–A) = (A∩B)∪(B∩

A) =(A∪B)∩(B∪B)∩(A∪

A)∩(

B∪

A)

=(A∪B)∩E∩

(A∩B)=(A∪B)-(A∩B) 27.(1)(A-B)-C = A∩B∩C =A∩(B∪C) = A-(B∪C) (2)(A-C)-(B-C)A∩C∩

(B∩

C) =A∩

C∩(

B∪C) = (A∩

C∩

B)∪(A∩

C∩C)

返回

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

=A∩∩C=(A–B)- C B∩

C =A∩

C∩

B=(A–C)–B

(3)(A–B-C=A∩28.(1)A∩(B∪

A) = (A∩B)∪(A∩A) =(A∩B)∪

=A∩B=B∩A (2)

((

A∪

B)∩

A) =

(

A∪

B)∪

A

=(A∩B)∪A = A

29.由第26题有(A-B)∪(B-A)=(A∪B)–(A∩B)，故(A-B)∪(B-A)A∪B。假若x∈A∩B，那么x∈A∪B，因此x(A∪B)-(A∩B),与(A-B)∪(B-A) = (A∪B)-(A∩B) = A∪B矛盾.

30.AB x(x∈A→x∈B) x(xB→xA) x(x∈B→x∈ AB 而

A)

B

A A∪B A∪B=E反之，

A∪AA∪B E

A∪BE，因此AB A∪B = E A∩(

A∪B)= A A∩B = A AB

综合上述，AB A∪B = E

AB A-B = A-BB

反之A-BB (A-B)∪BB A∪BB A∪B = B AB 综合上述AB A-BB

31.任取x ,x∈A {x} A=>{x}∈P(A)=>{x}∈P(B)=>{x}B x∈B

32.先证CA∧CB CA∩B,任取x,x∈C x∈C∧x∈C x∈A∧x∈B x∈A∪B,从而得到CA∪B.再证CA∩B CA∧CB，这可以由CA∩BA,CA∩BB得到。 33.PQ P-Q= P-Q

P，反之，P-QP

P∩(P-Q)P∩

P P-Q= PQ

34.令X=，则有∪Y =，即Y = . 35.AB A∪

AB∪

A EB∪

A因为E为全集,B∪

AE综合上述B∪

A=E.

36.由A∩CB∩C,A-CB-C，利用A∪CB∪D有： (A∩C)∪(A-C) (B∩C)∪(B-C) (A∩C)∪(A∩ (A∩(C∪37.恒等变形法

B=B∩(B∪A)=B∩(AB)=B∩(AC) =(B∩A)∪(B∩C)=(A∩C)∪(B∩C) =(A∪B)∩C=(A∪C)∩C=C

39.任取x，有x∈P(A) x A x B x∈P(B)，因此P(A)P(B). 40.(1)任取x有

x∈P(A)∩P(B) x∈P(A)∧x∈P(B) xA∧xB xA∩B x∈P(A∩B) (2)任取x有

x∈P(A)∪P(B) x∈P(A)∨x∈P(B) xA∧xB xA∪B x∈P(A∪B)

注意与(1)的推理不同，上面的推理中有一步是“ ”符号，而不是“ ”符号。 (3)反例如下：A = {1}，B = {2}，则 P(A)∪P(B)= {,{1},{2}} P(A∪B)={,{1},{2},{1,2}}

返回

C)(B∩C)∪(B∩

C)

C)(B∩(C∪C) A∩EB∩E AB

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

第七章 二元关系

本章自测答案 3.(1) 任取< x,y >,有

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

(2)都为假,反例如下:

A ={1}, B ={1,2}, C ={2}, D ={3} 4.(1)为假,反例如下:A ={1}, B =,C = {2}; (2)为真,证明如下:任取<x,y>有

<x,y>∈A×(B∩C)×(C∩D) x∈A∩B∧y∈B∧y∈C (x∈A∧y∈B)∧(x∈A∧y∈C)

<x,y>∈A×B∧<x,y>∈A×C <x,y>∈(A×B)∩(A×C) (3)为真,令A = 即可; (4)为假,反例如下: A = 7.

={<2,2>,<3,3 >,<4,4>}

={<2 . 3>,<2,4>,<3,2>,<3,4>,<4,2>,<4,3>} ∪

LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,2>,<2,4>,<3,3>,<4,4>}

9.(1){<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4> <2,6>,<4,1>,<4,2>,<4,4>, <4,6> <6,1>, <6,2>,<6,4> <6,6>} (2){<1,2>,<2,1>};

(3){<1,1>,<2,1>,<4,1>,<6,1>,<2,2>,<4,2>,<4,4>,<6,6>} (4){<1,2>,<2,2>,<4,2>,<6,2>} 12.（略）

13.A∩B = {<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}, A ∩ B ={<2,4>} domA = {1,2,3},domB = {1,2,4},dom(A ∪ B) = {1,2,3,4}

ranA = {2,3,4},ranB = {2,3,4},ran(A ∪ B) = {4},fld(A - B) = {1,2,3}

14.RR = {<0,2>,<0,3>,<1,3>}

R= {<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>} R{0,1} = {<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}] = {2,3} 18.(1)F(G∪H) = FG∪FH 任取<x,y> ,有

<x,y>∈F (G∪H) t(<x,t>∈F∧<t,y>∈G∪H) t(<x,t>∈F∧(<t,y>∈G∨<t,y>∈H))

t((<x,t>∈F∧<t,y>∈G)∨(<x,t>∈F∧<t,y>∈H)) t(<x,t>∈F∧<t,y>∈G)∨t(<x,t>∈F∧<t,y>∈H)) <x,t>∈FG∨<x,t>∈FH <x,y>∈FG∪FH (2)和(4)类似可证

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

19.(2)任取y,有

y∈R[T∪W] x(x∈T∪W∧<x,y>∈R) x((x∈T∨x∈W)∧<x,y>∈R

x((x∈A∧<x,y>∈R)∨(x∈W∧<x,y>∈R)) x(x∈T∧<x,y>∈R)∨x(x∈W∧<x,y>∈R) y∈R[T]∨y∈R[W] y∈R[T]∩R[W] (3)任取<x,y>,有

<x,y>∈F(A∩B) x∈A∩B∈F x∈A∧x∈B∧<x,y>∈F

(x∈A∧<x,y>∈F)(x∈B∧<x,y>∈F) <x,y>∈FA∧<x,y>∈FB <x,y>∈FA∩F B 20.(1)任取<x,y>,有 <x,y>∈(

∪

) <=><y,x>∈∨

<y,x>∈

∪

<x,y>∈ <x,y>∈ <x,y>∈

∨<x,y>∈∪

(2)和(1)类似可证.

21.只有对称性,因为1+1≠10,<1,1>R,R不是自反的,又由于<5,5>∈R,因此R不是反自反的,根据xRy x+y = 10=>yRx ,可知R是对称的,又由于<1,9>,<9,1>都是属于R,因此R不是反对称的, <1,9>,<9,1>都属于R,如果R是传递的,必有<1,1>属于R.但这是不成立的,因此R也不是传递的. 22.(1)关系图如图7.15所示; (P148) (2)具有反自反性、反对称性、传递性.

26.(1)R={<3,3>,<3,1>,<3,5>}, = {<3,3>,<3,1>,<3,5>}

(2)r(R)={<1,1>,<1,5>,<2,2>,<2,5>,<3,3>,<3,1>,<4,4>,<4,5>,<5,5>,<6,6>} s(R)={<1,5>,<5,1>,<2,5>,<5,2>,<3,3>,<3,1>,<1,3>,<4,5>,<5,4>} T(R)={<1,5>,<2,5>,<3,3>,<3,1>,<3,5>,<4,5>} 31.(1)R = {<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}∪32.(1)不是等价关系，因为<1,1> R，R不是自反的；

(2)不是等价关系，因为R不是传递的，1R3，3R2但是没有1R2； (3)不是等价关系，因为<2,2> R，R不是自反的； (4)不是等价关系，因为R不是传递的。 (5)是等价关系。

33．关系图如图7.17说示 (P151) [a] = [b] ={a,b},[c] = [d] = {c,d}

；(2)R； (3)R.

38.现取x，有x∈A <x,x>∈R <x,x>∈R∧<x,x>∈R <x,x>∈R∧<x,x>∈ <x,x>∈R∩R 任取<x,y>,有<x,y>∈ R∩ <x,y>∈R∧<x,y>∈ <y,x>∈ ∧<y,x>∈R <y,x>∈R∩R

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

任取<x,y>,<y,z>,有

<x,y>∈R∩ ∧<y,z>∈R∩

<x,y>∈R∧<x,y>∈ ∧<y,z>∈R∧<y,z>∈ (<x,y>∈R∧<y,z>∈R)∧(<x,y>∈ ∧<y,z>∈ <x,z>∈R∧<x,z>∈R <x,z>∈R∩R

42.x,x∈A <x,x>∈R <x,x>∈R∧<x,x>∈R <x,x>∈T,T是自反的。 x,y∈A,<x,y>∈T <x,y>∈R∧<y,x>∈R <y,x>∈R∧<x,y>∈R <y,x>∈T,T是对称的。 x,y,z∈A,<x,y>∈T∧<y,z>∈T

<x,y>∈R∧<y,x>∈R∧<y,z>∈R∧<z,y>∈R <x,y>∈R∧<y,z>∈R∧<z,y>∈R∧<y,x>∈R <x,z>∈R∧<z,x>∈R <x,z>∈T T是传递的。 43．哈斯图如下图所示.

44.(a)偏序集<A,R>,A={1,2,3,4,5},R={<1,3>,<1,5>,<2,4>,<2,5>,<3,5>,<4,5>}∪ (b)偏序集<A,R>,A={a,b,c,d,e,f},R={<a,b>,<c,d>,<e,f>}∪

(c)偏序集<A,R>,A={1,2,3,4,5}, R={<1,2>,<1,4>,<1,5>,<1,3>,<2,4>,<2,5>,<3,4>,<3,5>,<4,5>}∪

45.(a)A={a,b,c,d,e,f,g},

={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<a,g>,<b,d>, <b,e>,<c,f>,<c,g>}∪ (b)A = {a,b,c,d,e,f,g},R口 =

{<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<d,f>,<e,f>}∪ 46.哈斯图如图7.19所示 （P153）

（1）极大元e,f；极小元a,f；没有最大与最小元。 （2）极大元a,b,d,e；极小元a,b,c,e；没有最大与最小元。

返回

5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，

(G)。 问G至少有多少个顶点？在最少顶点的情况下，写出度数列、 (G)、 解：由握手定理图G的度数之和为：2 10 20

3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。

其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2,

《离散数学》第一章至第七章 习题详解! 屈婉玲、耿素云、张立昂

所以，G至少有7个顶点, 出度数列为3,3,4,4,2,2,2, (G) 4, (G) 2. 7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求 (D), (D)，

(D), (D), (D), (D).

解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2.

(D) 3, (D) 2, (D) 2, (D) 1, (D) 2, (D) 1

14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。

(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化； (2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化；