华南理工大学网络教育学院 《离散数学》练习题参考答案
第一章命题逻辑
一填空题
（1）设：p ：派小王去开会。q ：派小李去开会。则命题：
“派小王或小李中的一人去开会” 可符号化
为： (p ∨⌝q ) ∧ (⌝p ∨q ) 。 （2）设A ，B 都是命题公式，A ⇒B ，则A →B 的真值是 T 。 （3）设：p ：刘平聪明。q ：刘平用功。在命题逻辑中，命题：
“刘平不但不聪明，而且不用功” 可符号化为： p ∧ q （4）设A , B 代表任意的命题公式，则蕴涵等值式为
→ B⇔⌝A ∨ B
（5）设，p ：径一事；q ：长一智。在命题逻辑中，命题：
“不径一事，不长一智。” 可符号化为： ⌝ p→⌝q 。 （6）设A , B 代表任意的命题公式，则德 ∙ 摩根律为
⌝（A ∧ B）⇔A ∨ ⌝B ）
（7）设，p ：选小王当班长；q ：选小李当班长。则命题：“选小王或小李中的一人当班长。” 可符号化为： (p ∨⌝q ) ∧ (⌝p ∨q ) 。 （8）设，P ：他聪明；Q ：他用功。在命题逻辑中，命题：
“他既聪明又用功。” 可符号化为： P ∧ Q 。
（9）对于命题公式A ，B ，当且仅当 A → B 是重言式时，称“A蕴含B”，
并记为A ⇒B 。
（10）设：P ：我们划船。Q ：我们跑步。在命题逻辑中，命题：
“我们不能既划船又跑步。” 可符号化为： ⌝ (P ∧ Q ) 。 （11）设P , Q 是命题公式，德·摩根律为：
⌝（P ∨ Q ）⇔P ∧⌝ Q ）
（12）设 P ：你努力。Q ：你失败。在命题逻辑中，命题：“除非你努力，否则你将失败。” 可符号化为： ⌝P →Q 。
（13）设 p ：小王是100米赛跑冠军。q ：小王是400米赛跑冠军。在命题逻
辑中，命题：“小王是100米或400米赛跑冠军。” 可符号化为： p ∨q
（14）设A ，C 为两个命题公式，当且仅当 A →C 为一重言式
时，称C 可由A 逻辑地推出。
二．判断题
1. 设A ，B 是命题公式，则蕴涵等值式为A →B ⇔⌝A ∧B 。 （ ⨯ ） 2. 命题公式⌝p ∧q ∧⌝r 是析取范式。 （ √ ） 3. 陈述句“x + y > 5” 是命题。 （ ⨯ ） 4. 110 (p=1,q=1, r=0)是命题公式 ((⌝(p∧q)) →r) ∨q 的成真赋值。 （ √ ） 5. 命题公式 p →(⌝p ∧q) 是重言式。 （ ⨯ ） 6. 设A ，B 都是合式公式，则A ∧B →⌝B 也是合式公式。 （ √） 7. A ∨(B∧C) ⇔( A∨B) ∨(A∨C) 。 （ ⨯） 8. 陈述句“我学英语，或者我学法语” 是命题。 （√ ） 9. 命题“如果雪是黑的，那么太阳从西方出”是假命题。 （ ⨯ ） 10. “请不要随地吐痰！” 是命题。 （ ⨯ ） 11. P → Q ⇔ ⌝ P ∧ Q 。 （ ⨯ ） 12. 陈述句“如果天下雨，那么我在家看电视” 是命题。 （ √ ） 13. 命题公式（P ∧Q ）∨（⌝R →T ）是析取范式。 （ ⨯ ） 14. 命题公式 (P ∧⌝Q ) ∨ R ∨ (⌝P ∧Q ) 是析取范式。 （ √ ） 三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。
1．设：P ：天下雪。Q ：他走路上班。则命题“只有天下雪，他才走路上班。”可符号化为 （2） 。 （1）P →Q （2）Q → P （3）⌝ Q →⌝ P （4）Q ∨⌝P
2．(1 ) 明年国庆节是晴天。
(2 ) 在实数范围内，x+y〈3。 (3 ) 请回答这个问题！ (4 ) 明天下午有课吗？
在上面句子中，是命题的只有 (1 ) 。 3．命题公式A 与B 是等值的，是指 。 （1） A 与B 有相同的命题变元 （2） A B 是可满足式 （3） A →B 为重言式 （4） A B 为重言式 4．(1 ) 雪是黑色的。
(2 ) 这朵花多好看呀！。 (3 ) 请回答这个问题！ (4 ) 明天下午有会吗？
在上面句子中，是命题的是 (1 ) 。
5．设：P ：天下大雨。Q ：他乘公共汽车上班。则命题“只要天下大雨，他就乘公共汽车上班。” 可符号化为 （2） 。 （1）Q →P （2）P → Q （3）⌝ Q →⌝ P （4）Q ∨⌝P
6．设：P ：你努力；Q ：你失败。则命题“除非你努力，否则你将失败。”
在命题逻辑中可符号化为 （3） 。 （1）Q →P （2）P → Q （3）⌝ P →Q （4）Q ∨⌝P 7．(1 ) 现在开会吗？
(2 ) 在实数范围内，x+y >5。 (3 ) 这朵花多好看呀！
(4 ) 离散数学是计算机科学专业的一门必修课。 在上面语句中，是命题的只有 (4 ) 。
8．设：P ：天气好。Q ：他去郊游。则命题“如果天气好，他就去郊游。”
可符号化为 （1）
（1）P →Q （2）Q → P （3）⌝ 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．设命题公式为（⌝p →q ）→（q →⌝p ）。 （1）求此命题公式的真值表； （2）给出它的析取范式； （1）
（2）（⌝p →q ）→（q →⌝p ）
⇔﹁（⌝p →q ）∨（q →⌝p ） ⇔﹁（p ∨q ）∨（⌝q ∨⌝p ）
⇔（﹁p ∧﹁q ）∨⌝q ∨⌝p
2．设命题公式为（p → q）∧（p ∨ r）。（1）求此命题公式的真值表； （2）给出它的析取范式； （1）
（2） （p → q）∧（p ∨ r）
⇔（⌝p ∨q ）∧（p ∨ r） ⇔((⌝p ∨q) ∧p )∨((⌝p ∨q) ∧r)
⇔((⌝p ∧p ) ∨(q∧p)) ∨((⌝p ∧r) ∨(q∧r)) ⇔ (q∧p) ∨(⌝p ∧r) ∨(q∧r)
3．设命题公式为 (⌝ Q ∧（P → Q ）) → ⌝ P 。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； (1)
(2)
解：(⌝ Q ∧（P → Q ）) → ⌝ P ⇔(⌝ Q ∧（﹁P ∨Q ））→ ⌝ P ⇔﹁(⌝ Q ∧（﹁P ∨Q ））∨⌝ P ⇔（﹁⌝ Q ∨﹁（﹁P ∨Q ））∨⌝ P ⇔Q ∨（P ∧﹁Q ）∨⌝ P
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 ））→ Q 。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （1）
（2）
解：（P ∧（P →Q ））→Q ⇔（P ∧（﹁P ∨Q ））→Q ⇔﹁（P ∧（﹁P ∨Q ））∨Q ⇔（﹁P ∨﹁（﹁P ∨Q ））∨Q ⇔﹁P ∨（﹁﹁P ∧﹁Q ）∨Q ⇔﹁P ∨（P ∧﹁Q ）∨Q
6．设命题公式为（（P ∨ Q）∧⌝P ）→ Q 。（1）求此命题公式的真值表； （2）给出它的析取范式； （1）
（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 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）E
8．用直接证法证明
前提：P → (Q ∨ R ) ，S → ⌝ Q ，P ，S 。 结论：R
证明： 1）P → (Q ∨ R ) P 2） P P
3）(Q ∨ R ) T 2）3）I 4）S → ⌝ Q P 5）S P
6）⌝ Q T 4）5）I 7）R T 3）6）E
第二章谓词逻辑
一填空题
（1）若个体域是含三个元素的有限域{a，b ，c}，则
∃xA(x)⇔ A(a) ∨ A(b) ∨（2）取全总个体域，令F(x)：x 为人,G(x)：x 爱看电影。则命题“没有不爱
看电影的人。”可符号化为___⌝(∃x(F(x) ∧ G(x))) ____。 （3）若个体域是含三个元素的有限域{a，b ，c}，则
∀xA(x)⇔ ∧ A(b) ∧。
（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 是广州人。
在一阶逻辑中，命题“在广州工作的人未必都是广州人。”可符号化为_______﹁∀x(F(x) → G(x))_____。
（6）P (x ) ：x 是学生，Q (x ) ：x 要参加考试。在谓词逻辑中，命题： “每个学生都要参加考试” 可符号化为： ∀x(P (x ) → Q (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 A⌝B 也是谓词公式。 （ √ ）
2. 设c 是个体域中某个元素，A 是谓词公式，则A(c)⇒ ∀xA(x)。 （ ⨯ ） 3. ∀x ∀yA(x,y)⇔ ∀y ∀xA(x,y) 。 （ √ ） 4. ∀x ∃yA(x,y)⇔ ∃y ∀xA(x,y) 。 （ ⨯ ） 5. 取个体域为整数集，则谓词公式∀x ∀y(x ⨯ y = y ) 是假命题。 （√ ） 6. (∀x) （P(x)→Q(x)）⇔ (∀x) （⌝P(x) ∨Q(x)）。 （ √ ） 7. 命题公式 (P∧⌝Q ∨ R) ∨ (⌝P ∧Q) 是析取范式。 （ ⨯ ） 8. 谓词公式(∀x)(A (x) → B(x, y)) ∧R(x) 的自由变元为x, y。 （ √ ） 9. （（∀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） ∃y （G （y ）→∀x （F （x ）∧H （x ，y ））） （2） ∃y （G （y ）∧∀x （F （x ）→H （x ，y ））） （3） ∀x ∃y （G （y ）→（F （x ）∧H （x ，y ））） （4） ∃y （G （y ）→∀x （F （x ）→H （x ，y ）））
2．设个体域为整数集，下列真值为真的公式是3）。
（1）∃y ∀x (x – y =2) （2）∀x ∀y(x – y =2) （3）∀x ∃y(x – y =2) （4）∃x ∀y(x – y =2)
3．设F （x ）：x 是人，G （x ）：x 早晨吃面包。命题“有些人早晨吃面包”在谓词逻辑中的符号化公式是4）。 （1） （∀x ）（F （x ）→ G （x ）） （2） （∀x ）（F （x ）∧ G （x ）） （3） （∃x ）（F （x ）→ G （x ）） （4） （∃ x ）（F （x ）∧ G （x ）） 5．下列式子中正确的是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 ）
6．下面谓词公式是永真式的是
a) P （x ）→ Q （x ）
b) （∀x ）P （x ）→（∃x ）P （x ）
c) P （a ）→（∀x ）P （x ）
d) ⌝ P （a ）→（∃x ）P （x ）
5．设S （x ）：x 是运动员，J （y ）：y 是教练员，L （x ，y ）：x 钦佩y 。命题“所有运动员都钦佩一些教练员”的符号化公式是 c) 。
a) ∀x （S （x ）∧ ∀ y （J （y ）∧ L （x ，y ）））
b) ∀x ∃y （S （x ）→（J （y ）→ L （x ，y ）））
c) ∀x （S （x ）→ ∃y （J （y ）∧ L （x ，y ）））
d) ∃y ∀x （S （x ）→（J （y ）∧ L （x ，y ）））
6．下列式子是合式公式的是2）。
（1）（P ∨ → Q ） （2） ⌝（P ∧（Q ∨ R ））
（3）（P ⌝ Q ） （4）∧ Q → ∧ 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 ））→ R（y ）），
∃ x F（x ）。
结论：∃ x R（x ）。
证明：
（1） ∃ x F（x ）→∀y （（F （y ）∨ G（y ））→ R（y ）） 前提引入
（2）∃ x F（x ） 前提引入
（3）∀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 喜欢骑自行车。 前提： ∀x （F （x ）→ ⌝G （x ））, ∀x （G （x ）∨ H （x ））,
∃ x (⌝ H （x ）)
结论：∃ x (⌝ F （x ）)
证明
（1）∃ x (⌝ H （x ）) 前提引入
（2） ⌝ H （c ） （1）EI
（3）∀x （G （x ）∨ H （x ）） 前提引入
（4）G （c ）∨ H （c ） （3）UI
（5）G （c ）
（6）∀x （F （x ）→ ⌝G （x ）） 前提引入
（7）F （c ）→ ⌝G （c ） （6）UI
（8）⌝ F （c ）
（9）∃ x (⌝ F （x ）) （8）EG
3．在命题逻辑中构造下面推理的证明：
如果他是理科学生，他必须学好数学。如果他不是文科学生，他必是理科学生。他没学好数学，所以他是文科学生。
令F (x ) ：x 是理科学生，G (x ) ：x 学好数学，H (x ) ：x 是文科学生。
前提： ∀x （F （x ）→ G （x ））, ∀x （⌝ H (x ) → F （x ））,
∃ x (⌝G （x ）)
结论：∃ x (H (x ))
证明
（1）∀x （F （x ）→ G （x ）） 前提引入
（2）∃ x (⌝G （x ）) 前提引入
（3）∃ x (⌝F （x ）) T （1）（2）I
（4）∀x （⌝ H (x ) → F （x ）） 前提引入
（5）∃ 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 |＝ n 2 。A 上的二元关系有____2n _____2个。
（2）集合A 上关系R 的自反闭包r （R ）=_______R⋃I____________。
（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={，，，}，
S={，，，}，则R ◦S =
（6）设集合E ={a , b , c }，E 的幂集P (E ) ＝ ___________________________。
（7）设R 是定义在集合X 上的二元关系，如果对于每个x , y∈X ，
，则称集合X 上的关系R 是对称的。
（8）设关系R 和S 为，R ={，，}，S={，，
，}，则R ◦S =_______________。
（9）设R 是定义在集合X 上的二元关系，如果对于每个x , y∈X ，
，则称集合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}上的关系{,,,}是一个函数。 （ × ）
4．集合A={1，2，3，4}上的整除关系是等价关系。 （ × ）
5．集合A 的幂集P (A)上的包含关系是偏序关系。 （ √ ）
6．设A={a, b, c}, R∈ A×A 且R={,}, 则R 是传递的。 （ √ ）
6．设A ，B 是任意集合，如果B ≠ ∅，则A – B ≠ A。 （ × ）
7．集合A={1,2,3}上的关系{,,,}是传递的。 （ √ ）
8．集合A={1，2，3，4}上的小于关系是等价关系。 （ × ）
9．关系{∣x 1, x2∈N, x1+x2
10．集合A 上的恒等关系是偏序关系。 （ √ ）
11．集合A={1,2,3}上的关系S={,,,}是自反的。 （ × ）
12．设X={1, 2, 3}, Y={a, b, c}。函数F={,,}是双射。 （ √ ）
13．集合A 上的关系R 的自反闭包r(R)=R∪I A 。 （ √ ）
14．集合A 上的偏序关系R 是自反的、对称的、传递的。 （ ×）
15. 设A ，B 是任意集合，则A ⊕ B ＝(A-B) ∪(B-A)。 （ √ ）
三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入
下列叙述中的 内。
1．设A={a，b ，c}，B={a，b}，则下列命题不正确的是 。
a) A －B={a，b}
b) A ∩B={ a，b }
c) A ⊕B={c}
d) B ⊆A
2．设 A = {a, b, c, d}, A 上的关系R = {, , , }，则它的对称闭包为 c) 。
a) R = {, , , , , , }，
b) R = {, , , , }，
c) R = {, , , , , }，
d) R = {, , , , , }，
3．对于集合{1, 2, 3, 4}上的关系是偏序关系的是
a) R={,,,,, ,,,,} b) R={,,,,, ,,,,} c) R={,,,,, ,,,,} d) R={,,,,, ,,,,}
4．设A={1，2，3，4，5}，B={6，7，8，9，10}，以下哪个关系是从A 到B 的单射函数 b) 。
a) f ={，，，，}
b) f ={，，，，}
c) f ={，，，}
d) f ={，，，，}
5．设 A = {a, b, c}，要使关系{, , , }∪R 具有对称性，则 d) 。
a) R = {, }
b) R = {, }
c) R = {, }
d) R = {, }
6．设S={Φ，{1}，{1，2}}，则S 的幂集P （S ）有个元素
（1）3 （2）6 （3）7 （4）8
7．设R 为定义在集合A 上的一个关系，若R 是2，则R 为等价关系 。
（1）反自反的，对称的和传递的 （2）自反的，对称的和传递的
（3） 自反的，反对称的和传递的 （4）对称的，反对称的和传递的
8．设S ，T ，M 为任意集合，下列命题正确的是。
a) 如果S ∪T = S ∪M ，则T = M
b) 如果S -T = Φ，则S = T
c) S -T ⊆ S
d) S ⊕ S = S
9．设 A = {a , b , c }，要使关系{, , , }∪R 具有对 性，则 （4） 。
（1）R = {, } （2）R = {, }
（3） R = {, } （4）R = {, }
10．设A ={1，2，3，4，5}，B ={a ，b ，c ，d ，e }，以下哪个函数是从A 到B 的入射函数 b) 。
a) F ={，，，，}
b) F ={，，，，}
c) F ={，，，}
d) F ={，，，，}
四、解答题
1．已知偏序集（A ，≦），其中A={a，b ，c ，d ，e}，“≦”为{（a ，b ），
（a ，c ），（a ，d ），（c ，e ），（b ，e ），（d ，e ），（a ，e ）}∪I A 。
（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={, , , , , , , , , , , , , , , , , , , , , , }
(2)
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={, , , , , , , , , , , , , , , , , }
(2) COV A ={ , ,, , , }
(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。 （ ⨯ ）
三、填空题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入
下列叙述中的 内。
1．下列群一定为循环群的是 e) 。
e) （运算“＋”是整数集I 上的普通加法）
f) （R 是实数集，“×”是普通乘法）
g) （运算“＋”是有理数集Q 上的普通加法）
h)
（P （S ）是集合S 的幂集，“⊕”为对称差）
2．运算“－”是整数集I 上的普通减法，则代数系统 满足下列 性质3）。
（1）结合律 （2）交换律 （3）有零元 （4） 封闭性
3．设I 是整数集，N 是自然数集，P （S ）是S 的幂集，“×，＋，∩”是普通的乘法，加法和集合的交运算。下面代数系统中 （2） 是群。
（1） （2） （3）
（4）
4．下列代数系统不是群的是2）
（1） （运算“＋”是整数集I 上的普通加法）
（2）
（P （S ）是集合S 的幂集，“∩”为交运算）
（3） （运算“＋”是有理数集Q 上的普通加法）
（4）
（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 '）是两个图，若 V ′= V 且 E ′⊆ E ，
称G '是G 的生成子图。
（8）经过图中 每个结点 一次且仅一次的回路，称为哈密尔顿回路。
二．判断题
1．5个顶点的有向完全图有20条边。 （ √ ）
2．连通无向图的欧拉回路经过图中的每个顶点一次且仅一次。 （ ⨯ ）
3．图中的初级通路都是简单通路。 （ √ ）
4．已知n (n≥2) 阶无向简单图G 有n – 1条边，则G 一定为树。 （ ⨯ ）
5．n 阶无向完全图K n 的每个顶点的度都是n 。 （ ⨯ ）
6．一个无向图是二部图当且仅当它没有奇数度的顶点。 （ ⨯ ）
7．任何图都有一棵生成树。 （ ⨯ ）
8．连通无向图的哈密尔顿回路经过图中的每条边一次且仅一次。 （ ⨯ ）
9．图中的初级回路都是简单回路。 （ √ ）
10．任一图G=（V ，E ）的顶点的最大度数必小于G 的顶点数。 （ ⨯ ）
11．欧拉图一定是汉密尔顿图。 （ ⨯ ）
12．无向连通图G 的任意两结点之间都存在一条路。 （ √）
13．根树中除一个结点外，其余结点的入度为1。 （ √ ）
三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。
1．下列为欧拉图的是 。
2．下列各图为简单图的是
(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 = 的生成子图是指____（3）____.
（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．在下列关于图论的命题中，为真的命题是。
a) 完全二部图Kn, m (n ≥1, m ≥1) 是欧拉图 b) 欧拉图一定是哈密尔顿图
c) 无向完全图Kn （n ≥3）都是欧拉图 d) 无向完全图Kn （n ≥3）都是哈密尔顿图 8．下列各图为平面图的是 (3) 。
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） （2） （3） （4）
四、解答题
1．给定边集：{（1，2），（1，3），（2，3），（2，4），（2，5），（3，4），
（3，5），（4，5）}，
(1) 画出相应的无向图G （设G 无孤立点）； (2) 画出顶点子集V 1 = { 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 算法) 求一棵最小生成树并计算它的权
值。
4
2
4
它的权值为：1+2+4+4=11
3．如图所示带权图，用避圈法(Kruskal 算法) 求一棵最小生成树，并计算它的
权值。
3 2
它的权值为：1+2+3+5+7=18
4．求带权图G 的最小生成树，并计算它的权值。
1 它的权值为：1+1+2+3=7
5．给定权为2，6，3，9，4；构造一颗最优二叉树，并求此最优二叉树的权。
27 1
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=64