(完整版)《离散数学》同步练习答案

华南理工大学网络教育学院 《离散数学》练习题参

第一章命题逻辑

一填空题

（1)设：p：派小王去开会。q：派小李去开会.则命题：

“派小王或小李中的一人去开会\" 可符号化 为： （pq) (pq） 。

（2）设A,B都是命题公式，AB，则A

B的真值是 T 。

（3）设:p：刘平聪明。q：刘平用功。在命题逻辑中，命题：

“刘平不但不聪明，而且不用功” 可符号化为： p q .

（4）设A , B 代表任意的命题公式，则蕴涵等值式为

A B

A B 。

（5）设，p：径一事;q：长一智。在命题逻辑中,命题:

“不径一事，不长一智。\" 可符号化为：

pq 。

（6）设A , B 代表任意的命题公式，则德 摩根律为

（A

B）Û

A

B） 。

（7）设，p：选小王当班长;q：选小李当班长.则命题：“选小王或小李中的一人当班长。”符号化为: （pq） （pq） .

（8）设，P：他聪明；Q：他用功。在命题逻辑中，命题:

“他既聪明又用功。\" 可符号化为： P Q .

（9）对于命题公式A,B,当且仅当 A

B 是重言式时，称“A蕴含B”，并记为A

（10)设:P：我们划船.Q:我们跑步.在命题逻辑中，命题:

可B。

(完整版)《离散数学》同步练习答案

“我们不能既划船又跑步.” 可符号化为： （11）设P ， Q 是命题公式,德·摩根律为：

（P

Q）

（P Q) 。

P Q) 。

（12）设 P:你努力.Q：你失败。在命题逻辑中，命题：“除非你努力，否则你将失败。” 可符号化为：

PQ .

（13）设 p：小王是100米赛跑冠军。q:小王是400米赛跑冠军。在命题逻辑中，命题：“小王

是100米或400米赛跑冠军.” 可符号化为： p

q 。

C 为一重言式时,称C可由A逻

（14）设A，C为两个命题公式，当且仅当 A辑地推出。

二．判断题

1. 设A，B是命题公式，则蕴涵等值式为A2. 命题公式

BAB。 （ ）

pqr是析取范式。 ( √ )

）

3. 陈述句“x + y > 5” 是命题。 ( 4. 110 (p=1,q=1， r=0）是命题公式 （（5. 命题公式 p

（pq））r)q 的成真赋值. （ √ )

）

（pq） 是重言式。 （

B

6. 设A，B都是合式公式，则A7. A

B也是合式公式。 （ √）

）

(BC)( AB）（AC)。 （

8. 陈述句“我学英语，或者我学法语” 是命题。 （√ ） 9. 命题“如果雪是黑的,那么太阳从西方出”是假命题。 ( 10. “请不要随地吐痰！” 是命题。 （ 11. P ） ） ）

Q P Q . (

(完整版)《离散数学》同步练习答案

12. 陈述句“如果天下雨，那么我在家看电视” 是命题。 （ √ ） 13. 命题公式（P14. 命题公式 (PQ）(RT)是析取范式. （ ）

Q) R (PQ) 是析取范式。 （ √ )

三、选择题:在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内.

1．设：P：天下雪。Q：他走路上班。则命题“只有天下雪,他才走路上班。”可符号化为 （2） 。

(1）PQ

（2）Q P (3） （4)Q

Q

P

P

2．（1 ) 明年国庆节是晴天。

（2 ） 在实数范围内，x+y〈3。 （3 ) 请回答这个问题！ (4 ) 明天下午有课吗？

在上面句子中，是命题的只有 (1 ） 。

3．命题公式A与B是等值的，是指 （4 ） 。 （1） A与B有相同的命题变元 （2） A（3） A（4） A

B是可满足式 B为重言式 B为重言式

4．(1 ) 雪是黑色的。

(2 ) 这朵花多好看呀！。 (3 ) 请回答这个问题！

(完整版)《离散数学》同步练习答案

（4 ） 明天下午有会吗?

在上面句子中,是命题的是 (1 ） 。

5．设：P：天下大雨。Q：他乘公共汽车上班。则命题“只要天下大雨，他就乘公共汽车上班。”

可符号化为 （2） 。 （1）Q

P

（2）P Q (3） （4)Q

Q

P

P

6．设：P：你努力；Q：你失败。则命题“除非你努力，否则你将失败.”

在命题逻辑中可符号化为 （3） . （1）Q （3）

P （2）P Q

P

Q (4）Q P

7．（1 ) 现在开会吗？

（2 ） 在实数范围内,x+y （3 ) 这朵花多好看呀!

5.

(4 ) 离散数学是计算机科学专业的一门必修课。 在上面语句中，是命题的只有 (4 ) 。

8．设：P：天气好。Q：他去郊游。则命题“如果天气好，他就去郊游.”

可符号化为 (1） （1)P （3)

Q （2）Q P Q

P （4）Q

P

9．下列式子是合式公式的是 （2） 。

（1）(P Q) (2） (P （Q

R））

(完整版)《离散数学》同步练习答案

(3)（P Q) （4） Q R

10．

(1）1＋101＝110 （2） 中国人民是伟大的。

（3） 全体起立！ （4) 计算机机房有空位吗？ 在上面句子中，是命题的是 (2） 。

11．

设：P：他聪明；Q：他用功。则命题“他虽聪明但不用功.”

在命题逻辑中可符号化为 (3) 。 (1)P Q （2）P Q

（3）P

Q (4）P Q

12．

（1 ） 如果天气好，那么我去散步。 （2 ） 天气多好呀!

(3 ） x=3. （4 ） 明天下午有会吗？ 在上面句子中 （1 ) 是命题。

13．

设：P：王强身体很好；Q:王强成绩很好。命题“王强身体很好，成绩也很好。逻辑中可符号化为 （4) 。

（1）P Q （2）P Q （3)P

Q （4）P Q

四、解答题

在命题

\"(完整版)《离散数学》同步练习答案

1．设命题公式为（pq)（qp）。

(1）求此命题公式的真值表； （2）给出它的析取范式；

（1）

p q ﹁p ﹁p→q q→﹁p (pq）(qT T F T F F T F F T T T F T T T T T F F T F T T

（2）(pq)(qp)

﹁(p

q）∨（q

p)

﹁（p∨q）∨（q∨

p）

（﹁p∧﹁q）∨

q∨p

2．设命题公式为（p q）（p r）。 (1）求此命题公式的真值表; (2)给出它的析取范式; （1）

p q r p→q pr （p q）(p T T T T T T T T F T T T T F T F T F T F F F T F F T T T T T F T F T F F

p）

r)(完整版)《离散数学》同步练习答案

F F F F T F T T T F T F

(2） （p q）

（p

(（p（p （p p )

r） r) (（pq)r) q)q）

（(pp )

（q

p））

（（

p

（q

p)（p

r） （qr)

3．设命题公式为 ( Q （P Q)） （1）求此命题公式的真值表； (2)求此命题公式的析取范式；

（1）

P Q ﹁Q P→Q ﹁P ﹁Q ∧ (P→Q） T T F T F F T F T F F F F T F T T F F F T T T T

(2) 解：（ Q （P

Q））

P

（ Q （﹁P∨Q)） P

﹁（ Q

（﹁P∨Q））∨

P （﹁

Q ∨﹁（﹁P∨Q））∨

P

Q ∨（P﹁Q）∨ P

r)

（q

r））

P。

（﹁Q∧（P→Q)）→﹁P T T T T

(完整版)《离散数学》同步练习答案

4．完成下列问题 求命题公式（P∧(Q→R））→S的析取范式. 解：(P∧（Q→R））→S （P∧(﹁Q∨R））→S ﹁（P∧（﹁Q∨R)）∨S (﹁P∨﹁（﹁Q∨R））∨S ﹁P∨（﹁﹁Q∧﹁R）∨S

﹁P∨（Q∧﹁R）∨S

5．设命题公式为（P （P Q)）（1）求此命题公式的真值表； （2)求此命题公式的析取范式；（1）

P Q P→Q P ∧ （P→Q） T T T T T F F F F T T F F F T F （2）

解：（P∧（P→Q））→Q (P∧（﹁P∨Q））→Q ﹁（P∧(﹁P∨Q））∨Q （﹁P∨﹁(﹁P∨Q）)∨Q

﹁P∨（﹁﹁P∧﹁Q)∨Q

.

（P （P T T T T

）） Q Q Q

﹁P∨(P∧﹁Q）∨Q

6．设命题公式为（（P Q）P）（1）求此命题公式的真值表； （2）给出它的析取范式； （1） P Q P∨Q ﹁P （P∨Q)∧﹁P T T T F F T F T F F F F F T F F T T T T

（2)

解：(（P Q）P） Q ﹁（（P Q）P）∨Q

（﹁（P Q）∨(﹁﹁P）)∨Q ﹁P∨﹁Q)∨P∨Q

T

7．用直接证法证明 前提：P

Q，P

R,Q S

结论：S∨ R

证明： 1)P∨Q P 2） ﹁P→Q T 1)E(完整版)《离散数学》同步练习答案

Q。

（（P∨Q)∧﹁P）→Q T T T T

(完整版)《离散数学》同步练习答案

3）Q→S P

4）﹁P→S T 2）3）I 5）﹁S→P T 4）E 6)P→R P

7)﹁S→R T 5)6）I 8）S∨R T 7

8．用直接证法证明

前提：P （Q R)，S 结论:R

证明： 1)P (Q 2） P P 3）(Q R） 4)S

Q P 5）S 6） Q T 4)5 7)R T 3

一填空题

）E

Q，P，S。

R) P

）

）I）6）E 第二章谓词逻辑

T 2)3I P (完整版)《离散数学》同步练习答案

（1）若个体域是含三个元素的有限域｛a，b，c}，则

xA（x)

A(a)

A（b） A(c）

（2）取全总个体域，令F（x)：x为人，G(x）：x爱看电影.则命题“没有不爱看电影的人.\"可

符号化为___

（x(F(x）

G（x)）)____。

（3）若个体域是含三个元素的有限域{a，b,c｝，则

xA(x)Û A(a）

A（b） A（c） 。

（4）取全总个体域，令M（x）：x是人，G(y）：y是花, H（x，y)：x喜欢y。则命题“有些人

喜欢所有的花.”可符号化为 x(M（x）

（

y(G（y）

H（x,y)))）。

（5）取个体域为全体人的集合。令F(x）:x在广州工作,G(x)：x是广州人.在一阶逻辑中，命

题“在广州工作的人未必都是广州人.\"可符号化为_______﹁（6）P(x)：x是学生，Q(x）：x要参加考试.在谓词逻辑中，命题: “每个学生都要参加考试” 可符号化为：

x（P（x）

Q（x）) .

x(F(x）

G（x））_____.

（7)M（x)：x是人，B(x）:x勇敢。则命题“有人勇敢，但不是所有的人都勇敢”谓词符号化

为 ____

x(M(x)

B(x）） ﹁x（M（x） B(x）)_______。

（8）P（x）：x是人,M（x)：x聪明。则命题“尽管有人聪明，但不是一切人都聪明”谓词符号

化为 ______

x（P（x)

M(x)） ﹁x（P(x） M（x))___。

（9）I(x)：x是实数，R(x):x是正数，N(x）：x是负数.在谓词逻辑中，命题：

“任何实数或是正的或是负的\" 可符号化为：

x(I（x)

(R(x）

N（x)） 。

（10）P（x）：x是学生，Q(x):x要参加考试。在谓词逻辑中，命题：

“每个学生都要参加考试\" 可符号化为:

x(P(x）

Q（x）) 。

(11)令M（x)：x是大学生,P（y）：y是运动员, H（x， y)：x钦佩y。则命题“有些大学生不

钦佩所有运动员。”可符号化为____

x(M(x)(y(P(y) H（x，y)））___。

(完整版)《离散数学》同步练习答案

二．判断题

1. 设A，B都是谓词公式，则

x AB也是谓词公式。 ( √ ）

xA（x)。 （

）

2. 设c是个体域中某个元素,A是谓词公式,则A(c)3. 4.

xx

yA(x,y)yA(x,y）

y

y

xA(x，y） . （ √ ） xA(x,y） 。 （

x

y(x

）

5. 取个体域为整数集，则谓词公式6. （

y = y ) 是假命题。 (√ ）

Q（x))。 （ √ ）

）

x）（P（x)Q（x））Q

R）

（x）（ （

P(x)

7. 命题公式 （P8. 谓词公式(9. （（

PQ) 是析取范式。 （

x）（A (x） B（x, y)) R（x） 的自由变元为x, y。 （ √ )

x）A（x） B)（x）（A(x） B）. （ ）

）

10. R（x)：“x是大学生。” 是命题。 （

三、选择题：在每小题的备选答案中只有一个正确答案,将正确答案序号填入下列叙述中的

内。

1．设F(x）：x是火车，G(x）：x是汽车,H（x，y）:x比y快。命题“某些汽车比所有火车慢”的符号化公式是 (2） .

（1） （2） （3） （4）

y（G（y）y（G（y）x y（G（y）y（G(y)

x(F（x）H（x,y)）） x(F（x）H（x，y））) （F（x）

H（x，y))）

x（F（x)H（x，y)）)

2．设个体域为整数集,下列真值为真的公式是 （3） 。

（1)（2）

yx

x (x – y =2） y（x – y =2）

(完整版)《离散数学》同步练习答案

（3）（4）

xx

y(x – y =2） y(x – y =2)

3．设F（x)：x是人,G（x)：x早晨吃面包。命题“有些人早晨吃面包\"在谓词逻辑中的符号化公式是 (4) 。

（1） （（2） （（3） （（4） （

x）(F（x） G(x）） x）（F(x） G（x）) x）（F(x） G（x））

x)(F(x）

G(x））

5．下列式子中正确的是 （1） 。

（1）（2）(3)（4）

（

（x)P（x）（x)P(x）

（（

x）P（x) x） P(x）

x）P（x）(x） P(x）

（x）P(x）

（

x) P（x）

6．下面谓词公式是永真式的是 b) .

a) P（x）b) （

Q（x）

x）P（x）（x）P（x）

（x）P（x）

（

c) P(a）d)

P(a）x）P（x）

5．设S（x）：x是运动员，J（y）：y是教练员，L(x,y）：x钦佩y。命题“所有运动员都钦佩一

些教练员”的符号化公式是 c） 。

a) b) c)

x（S(x） y(J（y） L（x，y))） x y（S（x）(J(y) L（x，y)）） x（S（x） y（J(y) L（x，y）)）

(完整版)《离散数学》同步练习答案

d)

yx（S(x）（J(y) L（x，y）））

6．下列式子是合式公式的是 （2） 。

（1)（P （3）（P Q) （2) Q） （4)

（P Q

（Q R）） R

7．下列式子中正确的是 （1） 。

（1）（x）P（x）(x）P（x）

(2）（x）P（x）(x） P（x） （3)(

x)P(x）（x） P(x)

（4）

（x）P（x）（x） P(x）

四、解答题

1．构造下面推理的证明： 前提：

x F（x）y（（F（y) G（y）) x F（x).

结论： x R（x）。

证明：

）），

R(y(完整版)《离散数学》同步练习答案

(1） （2)（3）

x F(x）y（（F(y） G（y）） R(y）） 前提引入

x F（x） 前提引入 y（（F（y)

G(y））

R(y）） （1）（2）假言推理

（4）F(c） （2）EI （5）F（c) G（c） （4）附加 (6）(F（c) G（c）)

R(c） （3)UI

（7)R（c） （5）（6)假言推理 (8）

x R（x） (7）EG

2．在一阶逻辑中构造下面推理的证明

每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。

令F（x）:x喜欢步行，G（x)：x喜欢坐汽车,H(x)：x喜欢骑自行车。 前提： 结论：证明

（1） x ( H（x)） 前提引入 （2）

H（c） （1）EI

H（x）） 前提引入

x（F（x） G（x)）， x（G(x） H（x））,

x ( x (

H(x）) F（x))

（3）x（G（x）

（4）G（c） H（c） （3）UI （5）G（c） (6）

x（F(x) G（x）） 前提引入

(完整版)《离散数学》同步练习答案

（7）F（c) （8)

F（c)

G（c) (6）UI

（9） x （ F（x）) (8）EG

3．在命题逻辑中构造下面推理的证明:

如果他是理科学生，他必须学好数学.如果他不是文科学生，他必是理科学生.他没学好数学,所以他是文科学生。

令F（x）:x是理科学生，G（x):x学好数学，H(x)：x是文科学生。 前提: 结论：证明 (1）（2)

x（F(x） G（x））， x（ H（x) F（x）），

x (

G（x））

x (H(x))

x（F(x） G(x）) 前提引入

x （G（x）) 前提引入

（3） x (F（x)） T（1）（2）I (4)（5)

x（ H(x) F(x）） 前提引入

x (H(x)） T（3）（4）I

4．用直接证法证明：

前提:(”x)(C（x）→ W(x)∧R(x）），（＄x）(C（x）∧Q(x)) 结论：（＄x）（Q（x）∧R(x））。

推理: 1) （\"x）(C(x) →W（x） ∧R(x）） P 2） （＄x）（C（x) ∧Q（x）) p 3） C(a) ∧Q(a) ES2)

(完整版)《离散数学》同步练习答案

4） C（a） →W（a) ∧R（a) US1） 5) C（a） T3）I 6) W（a) ∧R(a） T4)5)I 7） Q（a） T3)I 8) R(a) T6）I 9） Q(a） ∧R(a） T7)8）I 10) ($x)（Q（x） ∧R(x）) EG9）

第三章集合与关系

一填空题

(1）如果|A|＝n，那么｜A×A｜＝ n2 。A上的二元关系有____2n_____个。

2

（2）集合A上关系R的自反闭包r（R）=_______RI____________。

（3）设集合A上的关系R和S，R={（1，2），（1，3)，（3，2）}，S={（1， 3),（2，1)，（3，

2）｝，则S◦R= ｛(1,2)， （2，2)， （2，3)｝ . （4)如果｜A｜＝n，那么|P(A）|＝ 2n .

（5）设集合A上的关系R和S，R=｛<1,2〉,<2,1>，〈3，4>,<4,3〉}，S={〈1，3>，〈3，1〉，

〈2，4〉,<4，2〉｝,则R◦S= ｛〈1,4〉， 〈2,3〉， 〈3,2>， <4，1〉｝ 。 （6）设集合E=｛a, b， c},E的幂集P(E)＝ ___________________________。 （7)设R是定义在集合X上的二元关系,如果对于每个x, yX，

______ ____ ____________ ，则称集合X上的关系R是对称的.

（8）设关系R和S为，R=｛〈1，2〉，<3，4〉，〈2，2>｝，S={<4，2〉，〈2，5〉,〈3，1〉，〈1,3〉}，

则R◦S =______ ___ __ _______________。

(完整版)《离散数学》同步练习答案

（9）设R是定义在集合X上的二元关系，如果对于每个x， yX，

______ ____ ____________ ,则称集合X上的关系R是自反的.

二．判断题

1．设A、B、C为任意的三个集合，则A×(B×C）=A×（B×C）。 （ × ） 2．设S，T是任意集合，如果S

T =

，则S = T。 ( × ）

3．集合A={1,2,3,4｝上的关系｛<1,2〉，<2，3>，〈2，4〉,<3,4>}是一个函数. ( × ） 4．集合A=｛1，2，3，4｝上的整除关系是等价关系。 （ × ) 5．集合A 的幂集P（A)上的包含关系是偏序关系。 （ √ ） 6．设A={a， b, c}, R

A×A且R={〈 a， b〉，〈 a， c>｝, 则R是传递的. （ √ ）

，则A – B

A. （ × ）

6．设A，B是任意集合,如果B

7．集合A={1，2，3｝上的关系{〈1,1〉,<2，2>,〈3，3〉，<1,2>}是传递的。 （ √ ） 8．集合A={1，2,3，4｝上的小于关系是等价关系。 （ × ） 9．关系{〈x1， x2>

x1, x2

N， x1+x2<6｝能构成一个函数。 ( ×）

10．集合A 上的恒等关系是偏序关系。 （ √ )

11．集合A=｛1，2,3｝上的关系S=｛<1，1>,<1，2〉,〈3，2〉，〈3,3>}是自反的。 （ × ） 12．设X={1， 2, 3}， Y=｛a, b， c}。函数F=｛<1， a>,<2， c〉,<3, b〉｝是双射。 ( √ ） 13．集合A上的关系R的自反闭包r（R)=R∪IA。 （ √ ） 14．集合A上的偏序关系R是自反的、对称的、传递的。 （ ×)

15. 设A，B是任意集合，则A

B ＝(A—B) ∪(B—A)。 ( √ ）

三、选择题：在每小题的备选答案中只有一个正确答案,将正确答案序号填入下列叙述中的

内。

1．设A=｛a，b,c｝,B=｛a，b}，则下列命题不正确的是 a) 。

(完整版)《离散数学》同步练习答案

a) A－B=｛a，b｝ b) A∩B={ a，b } c) Ad) B

B=｛c} A

2．设 A = {a， b， c, d｝, A 上的关系R = ｛〈a, b〉, 〈b, a>， 则它的对称闭包为 c) 。

a) R = ｛, 〈a， b〉, ， ， ， }， b) R = ｛〈a， b〉， ， 〈b, c〉， , 〈c， d〉}，

c) R = {〈a, b>， ， ， 〈c, d>， 〈c, b>， 〈d, c〉｝， d) R = ｛, 〈a, b〉， 〈b, a〉, 〈b， c>, 〈c, d〉, 3．对于集合｛1, 2， 3， 4｝上的关系是偏序关系的是 a) .

a) R=｛<1,1>,〈1，2〉，〈1,3>，<1,4〉，〈2,2〉， <2，3〉,<2,4>，〈3,3>,<3,4〉,〈4，

4>}

b) R={<1，1〉，〈1，2〉,〈1,3>，〈1，4〉,<2，2〉， 〈2,1〉,〈2，4>,<3，1>,〈3,4>，

<4，4>}

c) R={<1，1>,<1，2〉，<1,3〉,〈1，4>，<2,2〉, <2,1>,<3,1〉,<3,3〉，〈4，1>,<4,4>｝ d) R={〈2,1〉，<1，2〉，<1,3〉，<1，4〉，〈2，2〉, <4，3〉，<2,4〉,<3,3〉,〈3，4〉,<4，

4>}

4．设A=｛1，2,3，4，5}，B=｛6，7,8，9,10｝,以下哪个关系是从A到B的单射函数 b) 。

a) f ={<1，7〉，〈2，6>,<3,5>，〈1，9>，〈5,10>｝ b) f ={〈1，8〉，<2,6>，〈3，7〉，〈4，9>，〈5，10〉｝ c) f =｛<1，7>，<2,6>，〈3,5>，〈4，6〉｝

d) f ={<1，10>,〈2，6〉，<3,7>，<4,8〉,<5，10>｝

(完整版)《离散数学》同步练习答案

5．设 A = ｛a, b， c}，要使关系｛， , ｝∪R 具有对称性，则 d) 。

a) R = {〈c， a>, 〈a, c〉｝ b) R = {, ｝ c) R = {， 〈b， a〉｝ d) R = {6．设S={，｛1｝，{1，2｝}，则S的幂集P（S）有 (4) 个元素

（1)3 （2）6 （3）7 （4)8

7．设R为定义在集合A上的一个关系，若R是 （2） ,则R为等价关系 。

（1）反自反的，对称的和传递的 （2）自反的，对称的和传递的 （3） 自反的，反对称的和传递的 （4)对称的，反对称的和传递的 8．设S，T，M为任意集合，下列命题正确的是 c) 。

a) 如果S∪T = S∪M，则T = M b) 如果S—T = c) S—T d) S

，则S = T

S

S = S

9．设 A = {a, b， c｝，要使关系｛, ｝∪R 具有对

性，则 (4) .

（1）R = {〈c， a〉， 〈a， c〉｝ （2）R = ｛｝ (3) R = {〈c, a〉, 〈b, a〉｝ （4）R = {｝

10．设A={1，2，3，4，5}，B=｛a，b，c,d，e},以下哪个函数是从A到B的入射函数 b) 。

a) F ={<1，b>，<2，a〉，〈3，c>，<1,d>，〈5，e>}

(完整版)《离散数学》同步练习答案

b) F=｛〈1,c〉，〈2,a>，<3，b>,〈4,e>，<5，d>} c) F =｛〈1，b〉，<2，a〉,<3，d〉，<4，a〉} d) F=｛〈1,e〉，<2，a>,〈3，b>，〈4,c>，〈5,e〉｝

四、解答题

1．已知偏序集（A，≦）,其中A=｛a，b，c，d，e｝，“≦”为{（a，b）,

（a，c)，（a，d），（c，e），（b，e），（d，e),（a，e）}∪IA。

（1)画出偏序集（A，≦）的哈斯图。

(2）求集合A的极大元，极小元，最大元,最小元。 (1）

e

b

c

d

a

（2）集合A的极大元是e，极小元a，最大元e，最小元a.

2．设R是集合A = ｛1， 2， 3, 4, 5, 6， 7, 8, 9｝上的整除关系.

（1） 给出关系R;（2）画出关系R的哈斯图；

（3）指出关系R的最大、最小元，极大、极小元。

（1）R=｛〈1，1〉，<1，2> , <1，3>， 〈1，4〉， 〈1,5>， <1，6〉, <1，7>， <1，8〉， 〈1,9>， <2，2〉, <2,4>, 〈2，6>, <2,8>， 〈3,3〉, 〈3,6>, 〈3，9>, <4,4>, 〈4,8>,

(完整版)《离散数学》同步练习答案

〈5，5>, <6，6>， 〈7,7〉, 〈8,8>, 〈9，9〉} （2）

8 4 2

9 6 3

5

7

1

（3）关系R的无最大，最小元是1，极大元是8和

9,极小元是1。

3．设R是集合A = ｛1， 2, 3， 4， 6, 12}上的整除关系。

（2） 给出关系R；

(2） 给出COV A

（3） 画出关系R的哈斯图；

（4） 给出关系R的极大、极小元、最大、最小元。

（1)R={〈1，1〉,<1，2> , <1,3〉, 〈1,4〉, 〈1，6>, <1，12〉， 〈2，2〉, <2,4>, <2,6>， 〈2，12>, <3,3〉, <3,6〉， 〈3,12〉， 〈4,4〉, 〈4,12>， <6，6〉, <6,12>， 〈12，12〉} （2） COV A={〈1，2〉 ， 〈1，3>,〈2,4>, <2,6〉 〈3,6> 〈4，12〉, <6，6〉， <12,12>} （3）

12

6 3

4 2

1

(完整版)《离散数学》同步练习答案

（4）关系R的极大、最大元是12，极小元、最小元是1.

第五章代数结构

一填空题

（1）集合S的幂集P（S）关于集合的并运算“∪”的零元为 ____S___。 （2）集合S的幂集P(S)关于集合的并运算“∩”的零元为 ____(3）集合S的幂集P(S）关于集合的并运算“∪”的么元为 ____

____。 ______。

（4）一个代数系统＜S, * ＞，其中S是非空集合。＊是S上的一个二元运算，如果 * 在

S上是封闭的 ,则称代数系统＜S, * ＞为广群。

二．判断题

1．含有零元的半群称为独异点。 (

）

）

2．运算“＋”是整数集I上的普通加法，则群三、填空题:在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的

(完整版)《离散数学》同步练习答案

内。

1．下列群一定为循环群的是 e） 。

e) 〈I,＋> （运算“＋”是整数集I上的普通加法) f) 〈R－｛0｝，×〉 (R是实数集，“×\"是普通乘法） g) （运算“＋”是有理数集Q上的普通加法） h) > (P（S）是集合S的幂集，“”为对称差）

2．运算“－”是整数集I上的普通减法,则代数系统 〈I, －> 满足下列 性质 （3） .

(1）结合律 （2）交换律 (3）有零元 （4) 封闭性

3．设I是整数集,N是自然数集,P（S）是S的幂集，“×,＋，∩”是普通的乘法，加法和集合的交运算.下面代数系统中 （2) 是群。

（1） （2） (4）〈N,+〉 4．下列代数系统不是群的是 （2) 。

（1）〈I，＋> （运算“＋”是整数集I上的普通加法） （2) （P（S）是集合S的幂集,“∩”为交运算) （3) （运算“＋”是有理数集Q上的普通加法） （4) 〈P（S），

〉 （P（S）是集合S的幂集,“\"为对称差)

第七章图论

一填空题

（1）一个无向图G=（V，E）是二部图当且仅当G中无 奇数 长度的回路. （2)任何图（无向的或有向的）中，度为奇数的顶点个数为 偶数 .

（3）设D是一个有向图,若D中任意一对顶点都是相互可达的,则称D是________双向连通的

(完整版)《离散数学》同步练习答案

_______。

（4）既不含平行边，也不含环的图称为 简单图 。

（5）经过图中 每条边 一次且仅一次并的回路，称为欧拉回路。 （6）一棵有n个顶点的树含有_______n－1________边。 （7）设G =（V，E)，G =（V,E

是G的生成子图.

(8）经过图中 每个结点 一次且仅一次的回路，称为哈密尔顿回路.

）是两个图，若 V′= V 且 E′Í E ，称G

二．判断题

1．5个顶点的有向完全图有20条边。 ( √ ) 2．连通无向图的欧拉回路经过图中的每个顶点一次且仅一次。 （

）

3．图中的初级通路都是简单通路。 （ √ ） 4．已知n (n

2）阶无向简单图G有n – 1条边,则G一定为树。 （

) )

)

5．n阶无向完全图Kn的每个顶点的度都是n。 (

6．一个无向图是二部图当且仅当它没有奇数度的顶点。 （ 7．任何图都有一棵生成树. （ 8．连通无向图的哈密尔顿回路经过图中的每条边一次且仅一次。 (

） ）

9．图中的初级回路都是简单回路. （ √ ） 10．任一图G=（V，E)的顶点的最大度数必小于G的顶点数。 (

） ）

11．欧拉图一定是汉密尔顿图。 （

12．无向连通图G的任意两结点之间都存在一条路。 （ √) 13．根树中除一个结点外,其余结点的入度为1。 ( √ )

三、选择题:在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的

(完整版)《离散数学》同步练习答案

内。

1．下列为欧拉图的是 （4） .

2．下列各图为简单图的是 （3） 。

（1

(2)

（3

（4

3．设无向图G有12条边，已知G中3度顶点有6个，其余顶点的度数都小于3，则该图至少有

(3） 个顶点。

(1）6 (2）8 （3）9 （4） 12 4．下列四个有6个结点的图 (3） 是连通图.

(1)

（2(3） (4）

5．称图G′=为图G = (1）V′Í V (2）V′Í V且E′Í E （3）V′= V且E′Í E （4）V′Ì V且E′Ì E 6．有向图中结点之间的可达关系是______（2)________.

（1） 自反的，对称的 (2） 自反的，传递的

(完整版)《离散数学》同步练习答案

(3) 自反的，反对称的 (4） 反自反的，对称的 7．在下列关于图论的命题中,为真的命题是 d） 。

a) 完全二部图Kn, m (n

1, m 1）是欧拉图

b) 欧拉图一定是哈密尔顿图 c) 无向完全图Kn(nd) 无向完全图Kn(n

3）都是欧拉图 3）都是哈密尔顿图

8．下列各图为平面图的是 (3） 。

（1（2（3(4)

9．设G为任意的连通的平面图，且G有n个顶点，m条边，r个面，则平面图的欧拉公式为

(1） .

（1）n – m + r = 2（2）m – n + r = 2（3）n + m – r =2（4）r + n + m = 2

10．

下列四个图中与其余三个图不同构的图是 （3） .

(1） （2) （3） (4)

(完整版)《离散数学》同步练习答案

四、解答题

1．给定边集:{（1，2）,(1，3），（2，3），（2,4），（2，5），（3,4）,

（3，5)，（4，5）}，

(1) 画出相应的无向图G（设G无孤立点）;

(2） 画出顶点子集V1 = ｛ 2， 3， 4, 5}导出的导出子图； （3） 画出图G的一棵生成树. (1） (2）

1

2

5

2

5

3

4

1

（3)

3 4

2 5

3 4

2．如图所示带权图，用避圈法(Kruskal算法)求一棵最小生成树并计算它的权值。

(完整版)《离散数学》同步练习答案

1 4

2

4

它的权值为：1+2+4+4=11

3．如图所示带权图，用避圈法(Kruskal算法）求一棵最小生成树，并计算它的权值。

1

3 2 7 5

它的权值为：1+2+3+5+7=18

(完整版)《离散数学》同步练习答案

4．求带权图G的最小生成树，并计算它的权值。

1 3 2 它的权值为：1+1+2+3=7

1

5．给定权为2，6，3，9，4；构造一颗最优二叉树，并求此最优二叉树的权。

27

9

5

15

2

3 4 6 9

最优二叉树的权：2×3+3×3+4×2+6×2+9×2=53

6．给定权为1,9,4，7，3；构造一颗最优二叉树，并求此最优二叉树的权。

(完整版)《离散数学》同步练习答案

27

15

8

4

9

1 3 4 7

最优二叉树的权:1×4+3×4+4×3+7×2+9×1=51

7．给定权为2，6,5，9，4，1；构造一颗最优二叉树，并求此最优二叉树的权。

27

16

7

3

11

1 2 4 9 5 6

最优二叉树的权：1×4+2×4+4×3+5×2+6×2+9×2=