离散数学(本)2016年10月份试题

离散数学（本）2016年10月份试题

一、单项选择题（每小题3分，本题共15分）

1．若集合A＝{1,2,3,4}，则下列表述不正确的是 ( )． A．1?A B．{1,2,3}?A

C．{1,2,3}?A D．? ?A

2．设A＝｛1, 2, 3｝，B={1, 2, 3, 4}，A到B的关系R＝｛〈x, y〉|x=y｝，则R为 ( ) ． A. {<1, 2>, <2, 3>} B. {<1, 1>, <1, 2>, <1, 3>, <1, 4>, <1, 5>} C. {<1, 1>, <2, 1>} D. {<1, 1>, <2, 2>, <3, 3 >} 3．无向图G的边数是10，则图G的结点度数之和为（ ）． A. 10 B. 20 C. 30 D. 5

4．设连通平面图G有v个结点，e条边，r个面，则（ ）． A．r + v - e =2 B．v + e - r=4 C．v + e – r = – 4 D．v + e - r=2

5．设个体域D是整数集合，则命题?x?y (x = y+2)的真值是（ ）． A. 不确定 B. T C. 由y的取值确定 D. F

二、填空题（每小题3分，本题共15分）

6．设集合A={a, b, c}，B={b, c, d }，C={c, d, e}，则(B?C) – A等于 ． 7．设A={2, 3}，B={1, 2}，C={3, 4}，从A到B的函数f={<2, 2>, <3, 1>}，从B到C的函数g={<1，3>, <2，4>}，则Dom(g? f)等于 ．

8．若图G=，其中V={ a, b, c, d }，E={ (a, b), (a, d), (b, c), (b, d)}，则该图中的割边为 ．

9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为6，则在G -S中的连通分支数不超过 ．

10．设个体域D＝{1,2, 3, 4}，A(x)为“x小于10”，则谓词公式(?x)A(x)的真值为 ．

三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“小明是学生，小张是飞行员．”翻译成命题公式．

12．将语句“当大家都进入教室，则讨论会开始进行．”翻译成命题公式．

四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）

13．空集的幂集是空集．

14．(?x)(P(x)→Q(y)∨R(z))中的约束变元有x与y．

五．计算题（每小题12分，本题共36分）

15．设A={1, 2, 3}，R={|x?A，y?A且x+y=4}，S={|x?A，y?A且x=y}，试求R，S，R-1，r(S)．

16．图G=，其中V={ a, b, c, d, e }，E={ (a, b), (a, c) , (a, d), (b, c) , (b, d) , (c, d) , (c,

1

e) , (d, e)}，对应边的权值依次为2、3、4、5、6、7，6及2，试

（1）画出G的图形； （2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

17．试画一棵带权为1, 2, 4, 5, 6的最优二叉树,并计算该最优二叉树的权．

六、证明题（本题共8分）

18．试证明：P→Q ? P→（? (?P∨?Q)）．

2

离散数学（本）2016年10月份试题

参考解答

一、单项选择题（每小题3分，本题共15分） 1．C 2．D 3．B 4．A 5．B

二、填空题（每小题3分，本题共15分） 6．{d} 7．{2，3} 8．(b, c) 9．6

10．真（或T，或1）

三、逻辑公式翻译（每小题6分，本题共12分）

11．设P：小明是学生， Q：小张是飞行员． 则命题公式为： P∧Q． 12．设P：大家都进入教室， Q：讨论会开始进行． 则命题公式为：P→Q．

四、判断说明题（每小题7分，本题共14分）

13．错误． 空集的幂集不为空，为{?} 14．错误． 约束变元仅有x．

五．计算题（每小题12分，本题共36分）

15．解：R={<1,3>,<2,2>,<3,1>} S={<1,1>,<2,2>,<3,3>} R-1={<3,1>,<2,2>,<1,3>} r(S)={ <1,1>,<2,2>,<3,3>} 说明：对于每一个求解项，如果基本求出了解，可以给对应1分．16．解：（1）G的图形表示为：

3

2分） （6分）

（2分）

（6分） （3分）

（7分） （3分） （7分） （3分） （6分） （9分）

12分） （3分） （ （

?0?1?（2）邻接矩阵： ?1??1??01110?0110??1011? （6分）

?1101?0110??（3）粗线表示的图是最小生成树，

（10分）

权值为11 （12分） 17．解： 18 ?

7

? 11 ?

3 ? ? ? ? 6 4 5 ? ? （10分）

1 2

权为1?3+2?3+4?2+5?2+6?2=39． （12分）

六、证明题（本题共8分） 18．证明：

（1）P→Q P （1分） （2）P P（附加前提） （3分） （3）Q T（1）（2）I （5分） （4）P∧Q T（2）（3）I （6分） （5）? (?P∨?Q) T（4）E （7分） （6）P→? (?P∨?Q) CP规则 （8分） 另证：

设P→（? (?P∨?Q)）为F， （1分） 则P为T，? (?P∨?Q)为F， （3分） 即P∧Q为F． （4分） 所以P为T，Q为F ， （5分） 从而P→Q也为F． （6分） 所以P→Q?P→(? (?P∨?Q))． （8分）

说明：1、因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分。

另，可以用真值表验证。

4

离散数学（本）2016年7月份试题

一、单项选择题（每小题3分，本题共15分）

1．若集合A＝{1,2,3,4}，B＝{1,3,5}，则下列表述正确的是 ( )． A．A＝B B．B ?A

C．B ?A D．B ? A

2．设A＝｛1,2,3｝，B={2,4,6}，A到B的关系R＝｛〈x, y〉| 2x=y｝，则R= ( )． A. {<1,3>,<2,4>,<3,5>} B. {<2,1 >,<4,3>,<6,5>} C. {<1,1>,<2,2>,<3,3>} D. {<1,2>,<2,4>,<3,6>} 3．无向图G是棵树，边数是10，则G的结点度数之和是（ ）． A. 20 B. 9 C. 10 D. 11

4．下面的推理正确的是（ ）．

A．(1) （?x）F（x）→G（x） 前提引入 (2) F（y）→G（y） US（1）． B．(1) （?x）F（x）→G（x） 前提引入

(2) F（y）→G（y） US（1）．

C．(1) （?x）(F（x）→G（x）） 前提引入 (2) F（y）→G（x） ES（1）．

D．(1) （?x）（F（x）→G（x）） 前提引入 (2) F（y）→ G（y） US（1）．

5．设个体域为整数集，则公式?x?y(x+y=2)的解释可为 ( )．

A. 任一整数x，对任意整数y满足x+y=2 B. 对任一整数x，存在整数y满足x+y=2 C. 存在一整数x，对任意整数y满足x+y=2 D. 存在一整数x，有整数y满足x+y=2

二、填空题（每小题3分，本题共15分）

6．设集合A={1, 2, 3}，B={2, 3, 4}，C={3, 4, 5}，则B∪(A–C)等于 ． 7．设A={1, 2}，B={2, 3}，C={3，4}，从A到B的函数f ={<1, 2>, <2, 3>}，从B到C的函数g={<2, 3>, <3, 4>}，则Ran(g? f)等于 ．

8．两个图同构的必要条件包括结点数相等、边数相等与 ． 9．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，v值为5，e值为4则r的值为 ．

10．设个体域D＝{1, 2, 3, 4}，则谓词公式(?x)A(x)消去量词后的等值式为 ．

三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“昨天下雨，今天仍然下雨．”翻译成命题公式． 12．将语句“若不下雨，我们就去参加比赛．”翻译成命题公式．

四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）

13．若图G是一个欧拉图，则图G中存在欧拉路．

5

14．无向图G的结点数比边数多1，则G是树．

五．计算题（每小题12分，本题共36分） 15．设集合A={1, 2, 3, 4}上的关系：

R={<1，2>, <2，3>, <3，4>}，S={<1，1>, <2，2>, <3，3>}，

试计算（1）R?S； （2）R ?1； （3）r（R?S）．

16．图G=，其中V={a, b, c, d}，E={ (a, b), (a, c), (a, d), (b, c), (b, d), (c, d) }，对应边的权值依次为1、1、5、2、3及4，请画出G的图形、写出G的邻接矩阵并求出G权最小的生成树及其权值．

17．求?（P∨Q）∨R的析取范式与主合取范式．

六、证明题（本题共8分）

18．设A，B，C均为任意集合，试证明：A ?( B ? C ) = (A? B ) ?(A ?C )．

6

离散数学（本）2016年1月份试题

参考解答

一、单项选择题（每小题3分，本题共15分） 1．C 2．D 3．A 4．D 5．B

二、填空题（每小题3分，本题共15分） 6．{1,2,3, 4} 7．{3, 4}

8．度数相同的结点数相等 9．1

10．A(1 ) ∨A(2) ∨ A(3) ∨ A(4)

三、逻辑公式翻译（每小题6分，本题共12分）

11．设P：昨天下雨，Q：今天下雨． （2分） 则命题公式为：P∧Q． （6分）

12．设P：下雨，Q：我们去参加比赛． （2分）

则命题公式为：?P→Q． （或 ? Q→P） （6分）

四、判断说明题（每小题7分，本题共14分）

13．正确． （3分） 因为若图G是一个欧拉图，则图中存在欧拉回路． （5分） 按定义知，欧拉回路也是欧拉路． （7分） 14．错误． （3分） 反例：如图G的结点数比边数多1，但不是树．

（或：按定义有：无向图G是树当且仅当无向图G是连通图且边数比结点数少1．）

（7分）

说明：举出符合条件的反例均给分．

五．计算题（每小题12分，本题共36分）

15．解：（1）R?S =={<1，2>，<2，3>}； （4分）

（2）R ?1={<2，1>, <3，2>, <4，3>}； （8分） （3）r（R?S）={<1，1>, <2，2> , <3，3>, <4，4>} （12分） 16．解：G的图形表示为：

7

（3分）

邻接矩阵：

??0111??1011??101?? ?1?1110??粗线表示的图是最小的生成树，权为5： 17．解：?（P∨ Q）∨R ?(?P∧?Q)∨R 析取范式 ?(?P∨R)∧(?Q∨R) ?((?P∨R )∨(Q∧?Q))∧ (?Q∨R) ?((?P∨R )∨(Q∧?Q))∧ ((?Q∨R)∨(P∧?P)) ?(?P∨R ∨Q) ∧ (?P∨R ∨?Q) ∧ (?Q∨R∨P) ∧ (?Q∨R∨?P ) ? (P∨?Q∨R)∧(?P∨Q∨R)∧(?P∨?Q∨R) 主合取范式

六、证明题（本题共8分）

18．证明：

设S= A ?( B ? C )，T=(A? B ) ?(A ?C )，

若x∈S，则x∈A且x∈B ?C，即 x∈A，并且x∈B 且 x?C， 所以x∈(A? B )且x?(A ?C )，得x∈T， 所以S?T． 反之，若x∈T，则x∈(A?B ) 且 x?(A ?C )， 即x∈A，x∈B ，且x ?C，则得x∈B ?C， 即得x∈A ?( B ? C )，即x∈S，所以T?S． 因此T=S．

另，可以用恒等式替换的方法证明． 8

6分） （9分）

（12分） （5分） （7分） （9分） （10分） （11分） （12分） （2分） （3分） （4分） （5分） （6分）

（7分） （8分）

（

离散数学数理逻辑部分综合练习

本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是数理逻辑部分的综合练习。

一、单项选择题

1．设P：我将去市里，Q：我有时间．命题“我将去市里，仅当我有时间时”符号化为( )

A．Q?P B．P?Q C．P?Q D．?P??Q 2．设命题公式G：?P?(Q?R),则使公式G取真值为1的P，Q，R赋值分别是 ( ) A．0, 0, 0 B．0, 0, 1 C．0, 1, 0 D．1, 0, 0 A．?P??Q?P?Q B．(Q?(P?Q)) ?(?Q?(P?Q)) C．(P?(?Q?P))?(?P?(P?Q)) D．(?P?(P?Q)) ?Q 4．下列等价公式成立的为( )．

A．?P??Q?P?Q B．P?(?Q?P) ??P?(P?Q) C．Q?(P?Q) ??Q?(P?Q) D．?P?(P?Q) ?Q 5．命题公式?(P?Q)的主析取范式是( A )．

A．P??Q B．?P?Q C．?P?Q D．P??Q 6．命题公式（P∨Q）→R的析取范式是 ( B ) A．?（P∨Q）∨R B．（P∧Q）∨R

C．（P∨Q）∨R D．（?P∧?Q）∨R

7．设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( )．

A．??x(C(x)??G(x)) B．??x(C(x)??G(x))

C．??x(C(x)??G(x)) D．??x(C(x)??G(x))

8．设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（ ）． A．(?x)(A(x)∧B(x)) B．┐(?x)(A(x)∧B(x)) C．┐(?x)(A(x) →B(x)) D．┐(?x)(A(x)∧┐B(x))

9．表达式?x(P(x,y)?Q(z))??y(R(x,y)??zQ(z))中?x的辖域是( )． A．P(x, y) B．P(x, y)?Q(z) C．R(x, y) D．P(x, y)?R(x, y)

二、填空题

1．命题公式P?(Q?P)的真值是 ．

2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 则命题“如果他生病或

9

3．下列公式 ( )为重言式．

出差了，我就同意他不参加学习”符号化的结果为 ．

3．含有三个命题变项P，Q，R的命题公式P?Q的主析取范式是 ． 4．设F(x)：x是鸟，G(x)：x会飞翔．则命题“鸟会飞”符号化为 ．

5．设个体域D={1, 2},那么谓词公式?xA(x)??yB(y)消去量词后的等值式为 ．

6．设个体域D＝{a, b, c}，则谓词公式(?x)A(x)消去量词后的等值式为 ．

7．设个体域D＝{a, b}，则谓词公式(?x)A(x)∧（?x）B（x）消去量词后的等值式为 ．

A (a)∧A (b))∧(B（a）∨B（b）

8．设个体域D＝{1, 2}，则谓词公式?xA(x)消去量词后的等值式为 ． A(1)?A(2)

9．谓词命题公式(?x)(P(x)→Q(x)∨R(x，y))中的约束变元为 ．

10．(?x)(P(x)→Q(x)∨R(x，y))中的自由变元为 ．

三、公式翻译题

1．请将语句“今天不是天晴”翻译成命题公式．

2．将语句“今天没有下雨．”翻译成命题公式． 3．将语句“今天没有人来．” 翻译成命题公式．

4．将语句“他不去学校．”翻译成命题公式．

5．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．

6．将语句“小王去旅游，小李也去旅游．”翻译成命题公式．

7．将语句“他去旅游，仅当他有时间．”翻译成命题公式．

8．请将语句“我去书店，仅当天不下雨”翻译成命题公式．

9．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．

10．将语句“如果你去了，那么他就不去．”翻译成命题公式．

11．请将语句 “有人不去工作”翻译成谓词公式．

12．将语句“有人去上课．” 翻译成谓词公式．

13．请将语句“所有人都努力工作．”翻译成谓词公式．

14．将语句“所有人都去工作．”翻译成谓词公式． 15．将语句“所有的人都学习努力．”翻译成命题公式．

10

四、判断说明题（判断下列各题，并说明理由．） 1．命题公式?(Q?P)?P为永假式．

2．命题公式┐P∧（P→┐Q）∨P为永真式．

3．下面的推理是否正确，试予以说明．

(1) （?x）F（x）→G（x） 前提引入

(2) F（y）→G（y） US（1）．

五．计算题

1．（1）求命题公式?(P?Q)?(P??Q)的主析取范式、主合取范式； （2）求该命题公式的成假赋值．

2．求公式(P?Q)?R的析取、合取、主析取、主合取范式． 3．求P?Q?R的析取范式，合取范式、主析取范式，主合取范式． 4．试求出（P∨Q）→R的析取范式，合取范式，主合取范式． 5．求（P∨Q）→（R∨Q）的合取范式．

6．设谓词公式?x(P(x,y)??zQ(y,x,z))??yR(y,z)?F(y)．试 （1）写出量词的辖域；

（2）指出该公式的自由变元和约束变元．

六、证明题

1．试证明命题公式 (P?(Q??R))??P?Q与?（P??Q）等价．

2．试证明（?x）（P（x）∧R（x））? （?x）P（x）∧（?x）R（x）．

参考解答

一、单项选择题

1．B 2．D 3．C 4．B 5．A 6．D 7．D 8．C 9．B

二、填空题

1．T （或1）

2． (P?Q)?R

3． (P?Q?R)? (P?Q??R)

4． (?x)(F(x)? G(x))

5． (A(1)? A(2))? (B(1)? B(2))

6．A (a) ∧A (b)∧A（c）

11

7．A (a)∧A (b))∧(B（a）∨B（b）

8．A(1)?A(2) 9．x

10．R(x，y )中的y

三、公式翻译题

1．解：设P：今天是天晴；

则 ? P．

2．解：设P：今天下雨，

则 ? P．

3．解：设 P：今天有人来， 则 ? P．

4．解：设P：他去学校，

则 ? P．

5．解：设P：他接受了这个任务，Q：他完成好了这个任务， 则 P?? Q．

6．解：设P：小王去旅游，Q：小李去旅游，

则 P?Q．

7．解：设 P：他去旅游，Q：他有时间，

则 P ?Q．

8．解：设 P：我去书店，Q：天不下雨，

则 P ?Q．

9．解：设P：所有人今天都去参加活动，Q：明天的会议取消，

则 P? Q． 10．解：设P：你去，Q：他去，

则 P??Q．

11．解：设P(x)：x是人，Q(x)：x去工作，

则 (?x)(P(x) ?┐Q(x))．

12．解：设P(x)：x是人，Q(x)：x去上课，

则 (?x)(P(x) ?Q(x))．

13．解：设P(x)：x是人，Q(x)：x努力工作． 则 (?x)(P(x)? Q(x))．

14．解：设P(x)：x是人，Q(x)：x去工作， 则 (?x)(P(x)?Q(x))．

15．解：设P(x)：x是人，Q(x)：x学习努力，

12

则 （?x）(P(x)?Q(x))．

四、判断说明题（判断下列各题，并说明理由．） 1．解：正确 因为，由真值表

P Q Q?P ?( Q?P) 0 0 1 0 0 1 0 1 1 0 1 0 1 1 1 0 可知，该命题公式为永假式． 2．解：正确．

?( Q?P)? P 0 0 0 0 ┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式， 如果P的值为真，则┐P∧（P→┐Q）∨P为真，

如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真， 也即┐P∧（P→┐Q）∨P为真，

所以┐P∧（P→┐Q）∨P是永真式． 另种说明：

┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式， 只要其中一项为真，则整个公式为真．

可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真， 所以┐P∧（P→┐Q）∨P是永真式．

或用等价演算┐P∧（P→┐Q）∨P?T 3．解：错误． （2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆．

五．计算题

1．解：（1）?(P?Q)?(P??Q)??(?P?Q)?(?P??Q)

?(P??Q)?(?P??Q)?(P??Q??P)?(P??Q??Q)

?(P??Q) (主析取范式) ?(P?(Q??Q))?((P??P)??Q)

?(P?Q)?(P??Q)?(P??Q)?(?P??Q) ?(P?Q)?(P??Q)?(?P??Q) (主合取范式) （2）因为命题公式的成真赋值是(1, 0)， 所以它的成假赋值是(0, 0)，(0, 1)，(1, 1)． 2．解：(P?Q)?R??(P?Q)?R ?(?P??Q)?R

13

??P??Q?R （析取、合取、主合取范式） ?(┐P∧(┐Q∨Q)∧(┐R∨R))∨((┐P∨P)∧┐Q∧(┐R∨R))∨((┐P∨P) ∧(┐Q∨Q)∧R)

?(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)

∨(P∧┐Q∧┐R)∨(P∧┐Q∧R)∨(P∧Q∧R) （主析取范式） 3．解：P→（R∨Q）

?┐P∨(R∨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) （主析取范式）

4．解：（P∨Q）→R?┐(P∨Q)∨R? (┐P∧┐Q)∨R（析取范式） ? (┐P∨R)∧ (┐Q∨R)（合取范式）

? ((┐P∨R)∨(Q∧┐Q))∧ ((┐Q∨R)∨(P∧┐P)) ? (┐P∨R∨Q)∧(┐P∨R∨┐Q)∧ (┐Q∨R∨P)

∧(┐Q∨R∨┐P)

? (┐P∨Q∨R)∧(┐P∨┐Q∨R)∧ (P∨┐Q∨R) （主合取范式） 5．解：（P∨Q）→（R∨Q）

??（P∨Q）∨（R∨Q） ?(?P∧?Q)∨（R∨Q）

?(?P∨R∨Q)∧(?Q∨R∨Q)

?(?P∨R∨Q) 合取范式

6．解：（1）?x量词的辖域为(P(x,y)??zQ(y,x,z))，

?z量词的辖域为Q(y,x,z), ?y量词的辖域为R(y,z)．

（2）自由变元为(P(x,y)??zQ(y,x,z))与F(y)中的y，以及R(y,z)中的z

约束变元为(P(x,y)??zQ(y,x,z))中的x与Q(y,x,z)中的z，以及R(y,z)中的y．

六、证明题

1．证明：(P?(Q??R))??P?Q?(?P?(Q??R))??P?Q ?(?P?Q??R)??P?Q

?(?P??P?Q)?(Q??P?Q)?(?R??P?Q) ?(?P?Q)?(?P?Q)?(?P?Q??R)

??P?Q （吸收律） ??(P??Q) （摩根律） 2．证明：（1）（?x）（P（x）∧R（x）） P

（2）P（a）∧R（a） ES(1) （3）P（a） T(2)I

14

（4）（?x）P（x） EG(3)

（5）R（a） T(2)I

（6）（?x）R（x） EG(5)

（7）（?x）P（x）∧（?x）R（x） T(5)(6)I

离散数学图论部分综合练习

本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是图论部分的综合练习。

一、单项选择题

1．设图G的邻接矩阵为

?0?1??1??0??01100?0011??0000?

?1001?1010??则G的边数为( )．

A．6 B．5 C．4 D．3 2．已知图G的邻接矩阵为

则G有（ ）．

，

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边

3．设图G＝，则下列结论成立的是 ( )． A．deg(V)=2?E? B．deg(V)=?E? C．

a ? d ? b ?

? f

?deg(v)?2E D．?deg(v)?E

v?Vv?V4．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割集 C．{(d, e)}是边割集

? c

图一

? e

15

D．{(a, d) ,(a, c)}是边割集

5．如图二所示，以下说法正确的是 ( )． A．e是割点 B．{a, e}是点割集 C．{b, e}是点割集 D．{d}是点割集

6．如图三所示，以下说法正确的是 ( ) ．

A．{(a, e)}是割边 B．{(a, e)}是边割集 C．{(a, e) ,(b, c)}是边割集 D．{(d, e)}是边割集

图三

7．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是 ( )．

图四

A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 应该填写：D

8．设完全图Kn有n个结点(n≥2)，m条边，当（ ）时，Kn中存在欧拉回路． A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数 9．设G是连通平面图，有v个结点，e条边，r个面，则r= ( A )． A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 10．无向图G存在欧拉通路，当且仅当( )． A．G中所有结点的度数全为偶数 B．G中至多有两个奇数度结点 C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点

11．设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．

A．m?n?1 B．m?n C．m?n?1 D．n?m?1 12．无向简单图G是棵树，当且仅当( )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1

16

C．G的边数比结点数少1 D．G中没有回路．

二、填空题

1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 ．

2．设给定图G(如图四所示)，则图G的点割 集是 ．

3．若图G=中具有一条汉密尔顿回路， 则对于结点集V的每个非空子集S，在G中删除S 中的所有结点得到的连通分支数为W，则S中结点 数|S|与W满足的关系式为 ．

4．无向图G存在欧拉回路，当且仅当G连通 且 ．

5．设有向图D为欧拉图，则图D中每个结点的入度 ． 应该填写：等于出度

6．设完全图Kn有n个结点(n?2)，m条边，当 时，Kn中存在欧拉回路． 7．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式 ．

8．设连通平面图G的结点数为5，边数为6，则面数为 ． 9．结点数v与边数e满足 关系的无向连通图就是树．

10．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 条边后使之变成树．

11．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 ．

12．设G＝是有6个结点，8条边的连通图，则从G中删去 条边，可以确定图G的一棵生成树．

13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 ，则该序列集合构成前缀码．

三、判断说明题

1．如图六所示的图G存在一条欧拉回路．

v4 v5 d

e g v1 n f h a v2

b 图六

v3 e ? ? d

a? b

? f ? ? c

图四

c

2．给定两个图G1，G2（如图七所示）：

17

（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由． （2）若是欧拉图，请写出一条欧拉回路．

v1

v6

v5

v4

图七

3．判别图G(如图八所示)是不是平面图， 并说明理由．

4．设G是一个有6个结点14条边的连 通图，则G为平面图．

四、计算题

1．设图G??V，E?，其中V??a1, a2, a3, a4, a5?,

E???a1, a2?，?a2, a4?，?a3, a1?，?a4, a5?，?a5, a2??

（1）试给出G的图形表示； （2）求G的邻接矩阵；

（3）判断图G是强连通图、单侧连通图还是弱连通图？

2．设图G=，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) }，试

（1）画出G的图形表示； （2）写出其邻接矩阵；

（2）求出每个结点的度数； （4）画出图G的补图的图形．

3．设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试

（1）给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形．

v6 ? ? v3

? v4

图八

v3

v1 ? v2 ? v2

? v5

4．图G=，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试

（1）画出G的图形； （2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

5．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试

（1）画出相应的最优二叉树； （2）计算它们的权值． 6．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它的权．

五、证明题

1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的．

18

2．设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的补图G中的奇数度顶点个数相等．

3．设连通图G有k个奇数度的结点，证明在图G中至少要添加拉图．

参考解答

一、单项选择题

1．B 2．D 3．C 4．C 5．A 6．D 7．D 8．C 9．A 10．D 11．A 12．A

二、填空题

1．15 2．{f}，{c，e} 3．W?|S| 4．所有结点的度数全为偶数 5．等于出度 6．n为奇数 7．v-e+r =2 8．3

k条边才能使其成为欧2 9．e=v-1 10．4 11．5

12．3 13．0

三、判断说明题

1．解：正确．

因为图G为连通的，且其中每个顶点的度数为偶数． 2．解：（1）图G1是欧拉图．

因为图G1中每个结点的度数都是偶数．

图G2是汉密尔顿图．

因为图G2存在一条汉密尔顿回路（不惟一）： a(a, b)b(b, e) e(e, f) f (f, g) g(g, d) d(d, c) c(c, a)a

问题：请大家想一想，为什么图G1不是汉密尔顿图，图G2不是欧拉图。

（2）图G1的欧拉回路为：（不惟一）：

v1(v1, v2) v2 (v2, v3) v3 (v3, v4) v4 (v4, v5)v5 (v5, v2) v2 (v2, v6)v6 (v6, v4) v4 (v4, v1)v1 3．解：图G是平面图．

因为只要把结点v2与v6的连线(v2, v6)拽 到结点v1的外面，把把结点v3与v6的连线 (v3, v6)拽到结点v4, v5的外面，就得到一个平 面图，如图九所示．

19

v1 ? v6 ? v2

? ? v3

? v5

? v4 图九

4．解：错误．

不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”

四、计算题

1．解：（1）图G是有向图： a2

a（2）邻接矩阵如下：

? 3 ? ??0100A(D)???a4 ? ? a5

?a ?101

?00??01（3）图G是单侧连通图，也是弱连通图．

2．解：（1）图G如图十

v?1

v2 ? ? v5

? ?

v3

v4 （2）邻接矩阵为 图十

??01100?10110? ????11011?

?01101????00110??（3）deg(v1)=2

deg(v2)=3 deg(v3)=4 deg(vv4)=3

?1

deg(v5)=2

v2 ? ? v5

（4）补图如图十一 v?

?3

v 4

图十一

3．解：（1）G的图形如图十二

（2）邻接矩阵： 图十二

20

000?010?000??,

001??000??

?0?0??1??0??00100?0110??1011?

?1101?0110??（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2

（4）补图如图十三：

图十三 4．解：（1）G的图形表示如图十四：

图十四 （2）邻接矩阵：

?0?1??1??0??11101?0011??0011?

?1101?1110??（3）粗线表示最小的生成树，如图十五

如图十五

21

最小的生成树的权为1+1+2+3=7：

5．解：（1）最优二叉树如图十六所示：

方法（Huffman）：从2,3,5,7,11,13,17 ,19,23,29,31中选2,3为最低层结点，并 从权数中删去，再添上他们的和数，即 5,5,7,11,13,17,19,23,29,31；

再从5,5,7,11,13,17,19,23,29,31中选 5,5为倒数第2层结点，并从上述数列中 删去，再添上他们的和数，即7,10,11,13, 17,19,23,29,31；

然后，从7,10,11,13,17,19,23,29,31中 上述数列中删去，再添上他们的和数，即 17,17,24,19,23,29,31； ??

65 ? 160

?

? 95

42 ? ? 34 ? ? 53

31 ? 17 ? ? ? 24 ? ? 17 23 29 19

? 10 ? ? ? 7 11 13 5 ? ?

5

? ? 2 3

选7,10和11,13为倒数第3层结点，并从 如图十六

（2）权值为：2?6+3?6+5?5+7?4+11?4+13?4+17?3+19?3+23?3+29?3+31?2 =12+18+25+28+44+52+51+57+69+87+62=505

6．解：最优二叉树如图十七

3 ? 12 ? 7 ? ? ? 4 2

? 5

? 3

? ? 1 2 如图十七 它的权为：1?3+2?3+2?2+3?2+4?2=27

五、证明题

1．证明：用反证法．设G中的两个奇数度结点分别为u和v．假设u和v不连通，即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点．这与定理3.1.2的推论矛盾．因而u和v一定是连通的．

2．证明：设G??V,E?，G??V,E??．则E?是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结点u?V，u在G和G中的度数之和等于u在Kn中的度数．由于n是大于等于2的奇数，从而Kn的每个结点都是偶数度的（n?1 (?2)度），于是若u?V在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点

22

个数相等．

3．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．

又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．

故最少要加

k条边到图G才能使其成为欧拉图． 2离散数学集合论部分综合练习

本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。

一、单项选择题

1．若集合A={a，b}，B={ a，b，{ a，b }}，则（ ）． A．A?B，且A?B B．A?B，但A?B C．A?B，但A?B D．A?B，且A?B

2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )．

A．{a，{ a }}?A B．{ a }?A C．{2}?A D．??A

3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}?A B．{2}?A

C．{a}?A D．??A

4．若集合A={a，b，{ 1，2 }}，B={ 1，2}，则（ ）． A．B ? A，且B?A B．B? A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )．

A．{{1}, {a}} B．{?,{1}, {a}}

C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（ ）．

A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x, y?A}，则R的性质为（ ）．

A．自反的 B．对称的 C．传递且对称的 D．反自反且传递的

8．设集合A = {1，2，3，4，5，6 }上的二元关系R ={?a , b??a , b?A , 且a +b = 8}，则R具有的性质为（ ）．

A．自反的 B．对称的

23

C．对称和传递的 D．反自反和传递的

9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（ ）个．

A．0 B．2 C．1 D．3 10．设集合A={1 , 2 , 3 , 4}上的二元关系

R = {?1 , 1?，?2 , 2?，?2 , 3?，?4 , 4?}，

S = {?1 , 1?，?2 , 2?，?2 , 3?，?3 , 2?，?4 , 4?}，

则S是R的（ ）闭包．

A．自反 B．传递 C．对称 D．以上都不对 11．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系 的哈斯图如图一所示，若A的子集B = {3 , 4 , 5}， 则元素3为B的（ ）．

A．下界 B．最大下界 C．最小上界 D．以上答案都不对

2 4 图一 1 3 5

12．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 ( )．

A．8、2、8、2 B．无、2、无、2 C．6、2、6、2 D．8、1、6、1

13．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={, }，R2={, , }，R3={, }，则（ ）不是从A到B的函数． A．R1和R2 B．R2 C．R3 D．R1和R3

二、填空题

1．设集合A有n个元素，那么A的幂集合P(A)的元素个数为 ． 2．设集合A＝{a，b}，那么集合A的幂集是 ． 应该填写：{?,{a,b},{a},{b }}

3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，

R?{?x,y?x?A且y?B且x,y?A?B}

则R的有序对集合为 ．

4．设集合A={0, 1, 2}，B={0, 2, 4},R是A到B的二元关系，

R?{?x,y?x?A且y?B且x,y?A?B}

则R的关系矩阵MR＝

． 5．设集合A={a,b,c}，A上的二元关系

R={,}，S={,,}

则(R?S)1= ．

－

6．设集合A=｛a,b,c｝，A上的二元关系R={, , , }，则二元关系R

24

具有的性质是 ．

7．若A={1,2}，R={|x?A, y?A, x+y=10}，则R的自反闭包为 ． 8．设集合A={1, 2}，B={a, b}，那么集合A到B的双射函数是 ．

9．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为 ．

三、判断说明题（判断下列各题，并说明理由．）

1．设A、B、C为任意的三个集合，如果A∪B=A∪C，判断结论B=C 是否成立？并说明理由．

2．如果R1和R2是A上的自反关系，判断 结论：“R11、R1∪R2、R1?R2是自反的” 是否

-

成立？并说明理由．

3． 若偏序集的哈斯图如图一所示，

则集合A的最大元为a，最小元不存在．

4．若偏序集的哈斯图如图二所示， 则集合A的最大元为a，最小元不存在．

图一

5．设N、R分别为自然数集与实数集，f：N →R，f (x)=x+6，则f是单射．

四、计算题

1．设集合A＝{a, b, c}，B={b, d, e}，求

（1）B?A； （2）A?B； （3）A－B； （4）B?A．

图二

2．设A={{a, b}, 1, 2}，B={ a, b, {1}, 1}，试计算

（1）（A?B） （2）（A∪B） （3）（A∪B）?（A∩B）． 3．设集合A={{1},{2},1,2}，B={1,2,{1,2}}，试计算

（1）（A?B）； （2）（A∩B）； （3）A×B．

4．设A={0，1，2，3，4}，R={|x?A，y?A且x+y<0}，S={|x?A，y?A且x+y?3}，试求R，S，R?S，R-1，S-1，r(R)．

5．设A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，R是A上的整除关系，B={2, 4, 6}． （1）写出关系R的表示式； （2）画出关系R的哈斯图； （3）求出集合B的最大元、最小元．

6．设集合A＝{a, b, c, d}上的二元关系R的关系图 如图三所示．

（1）写出R的表达式； （2）写出R的关系矩阵；

（3）求出R2．

7．设集合A={1，2，3，4}，R={|x, y?A；|x?y|=1或x?y=0}，试 （1）写出R的有序对表示； （2）画出R的关系图； （3）说明R满足自反性，不满足传递性．

25

a b 图三

d c

五、证明题

1．试证明集合等式：A? (B?C)=(A?B) ? (A?C)．

2．试证明集合等式A? (B?C)=(A?B) ? (A?C)．

3．设R是集合A上的对称关系和传递关系，试证明：若对任意a?A，存在b?A，使得?R，则R是等价关系．

4．若非空集合A上的二元关系R和S是偏序关系，试证明：R?S也是A上的偏序关系．

参考解答

一、单项选择题

1．A 2．B 3．C 4．B 5．C 6．A 7．B

9．B 10．C 11．C 12．B 13．B

二、填空题 1．2n

2．{?,{a,b},{a},{b }}

3．{<2, 2>，<2, 3>，<3, 2>}，<3, 3>

?114．?0??000? ?110???? 5．{, } 6．反自反的

7．{<1, 1>, <2, 2>}

8．{<1, a >, <2, b >}，{<1, b >, <2, a >}

9．8

三、判断说明题（判断下列各题，并说明理由．） 1．解：错．

设A={1, 2}，B={1}，C={2}，则A∪B=A∪C，但B?C． 2．解：成立．

因为R1和R2是A上的自反关系，即IA?R1，IA?R2。

由逆关系定义和IR-A?1，得IA? R11；

由IA?R1，IA?R2，得IA? R1∪R2，IA? R1?R2。

所以，R-11、R1∪R2、R1?R2是自反的。

3．解：正确．

对于集合A的任意元素x，均有?R （或xRa），所以a是集合A中的最大元．

按照最小元的定义，在集合A中不存在最

26

8．B 小元．

4．解：错误．

集合A的最大元不存在，a是极大元．

5．解：正确．

设x1，x2为自然数且x1?x2，则有f(x1)= x1+6? x2+6= f(x2)，故f为单射．

四、计算题

1．解：（1）B?A={a, b, c}?{b, d, e}={ b } （2）A?B={a, b, c}?{b, d, e}={a, b, c, d, e } （3）A－B={a, b, c}－{b, d, e}={a, c}

（4）B?A= A?B－B?A={a, b, c, d, e }－{ b }={a, c, d, e }

2．解：（1）（A?B）={{a, b}, 2}

（2）（A∪B）={{a, b}, 1, 2, a, b, {1}}

（3）（A∪B）?（A∩B）={{a, b}, 2, a, b, {1}} 3．解：（1）A?B ={{1},{2}}

（2）A∩B ={1,2} （3）A×B={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>，

<{2},{1,2}>，<1,1>，<1,2>，<1, {1,2}>，<2,1>，<2,2>,

<2, {1,2}>}

4．解：R=?,

S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>}

R?S=?，

R-1=?， S-1= S， r(R)=IA．

5．解：（1）R=I?{<1,2>, <1,3>, ?, <1,12> , <2,4>, <2,6>, <2,8>, <2,10>, <2,12>, <3,6>, <3,9> , <3,12>, <4,8>, <4,12>, <5,10>, <6,12>} （2）关系R的哈斯图如图四

（3）集合B没有最大元，最小元是：2 6．解：R＝{, , , }

10 8 4 5 2 12 6 3 9 7 11

1 图四：关系R的哈斯图

?1?0MR???0??0000011000?0?? 0??1?R2 = {, , , }?{, , , } ={, , }

7．解：（1）R={<1,1>,<2,2>,<3,3>,<4,4>, <1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}

（2）关系图如图五

（3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，

27

? 4 2 1 ? 3 ? ? 图五

即A的每个元素构成的有序对均在R中，故R在 A上是自反的。

因有<2,3>与<3,4>属于R，但<2,4>不属于R， 所以R在A上不是传递的。

五、证明题

1．证明：设，若x∈A? (B?C)，则x∈A或x∈B?C，

即 x∈A或x∈B 且 x∈A或x∈C． 即x∈A?B 且 x∈A?C ， 即 x∈T=(A?B) ? (A?C)，

所以A? (B?C)? (A?B) ? (A?C)．

反之，若x∈(A?B) ? (A?C)，则x∈A?B 且 x∈A?C， 即x∈A或x∈B 且 x∈A或x∈C，

即x∈A或x∈B?C， 即x∈A? (B?C)，

所以(A?B) ? (A?C)? A? (B?C)． 因此．A? (B?C)=(A?B) ? (A?C)．

2．证明：设S=A∩(B∪C)，T=(A∩B)∪(A∩C)， 若x∈S，则x∈A且x∈B∪C，即 x∈A且x∈B 或 x∈A且x∈C，

也即x∈A∩B 或 x∈A∩C ，即 x∈T，所以S?T． 反之，若x∈T，则x∈A∩B 或 x∈A∩C， 即x∈A且x∈B 或 x∈A且x∈C

也即x∈A且x∈B∪C，即x∈S，所以T?S． 因此T=S．

3．设R是集合A上的对称关系和传递关系，试证明：若对任意a?A，存在b?A，使得?R，则R是等价关系．

证明：已知R是对称关系和传递关系，只需证明R是自反关系． ?a?A，?b?A，使得?R，因为R是对称的，故?R； 又R是传递的，即当?R，?R ??R；

由元素a的任意性，知R是自反的． 所以，R是等价关系．

4．若非空集合A上的二元关系R和S是偏序关系，试证明：R?S也是A上的偏序关系．

证明：.① ?x?A,?x,x??R,?x,x??S??x,x??R?S，所以R?S有自反性； ②?x,y?A,因为R，S是反对称的，

?x,y?R?S??y,x?R?S?(?x,y??R??x,y??S)?(?y,x??R??y,x??S)?(?x,y??R??y,x??R)?(?x,y??S??y,x??S)?x?y?y?x?x?y所以，R?S有反对称性．

③ ?x,y,z?A，因为R，S是传递的， ?x,y??R?S??y,z??R?S

??x,y??R??x,y??S??y,z??R??y,z??S ??x,y??R??y,z??R??x,y??S??y,z??S ??x,z??R??x,z??S??x,z??R?S

28

所以，R?S有传递性． 总之，R是偏序关系．

离散数学（本）2016年3月份试题

一、单项选择题（每小题3分，本题共15分）

1．设A={1, 3, 5, 7｝，B={2, 4, 6}，A到B的关系R={ | y=x+3}，则R为 ( )． A. {<3, 2>, <5, 4>, <7, 6>} B. {<1, 4>, <3, 6>}

C. {<1, 2>, <3, 4>, <5, 6>} D. {<1, 3>, <3, 3>, <5, 3>, <7, 3>} 2．若集合A＝{a, b, c}，则下列表述不正确的是( )． A．? ?A B．a?A

C．{a}?A D．{a, b, c}?A

3．设A（x）：x是学生，B（x）：x是大学生，则命题“不是所有的学生都是大学生”可符号化为（ ）．

A．┐(?x)(A(x)∧B(x)) B．(?x)(A(x)∧B(x)) C．┐(?x)(A(x)∧┐B(x)) D．┐(?x)(A(x) →B(x))

4．设G为连通无向图，则（ ）时，G中存在欧拉回路．

A．G不存在奇数度数的结点 B．G存在偶数度数的结点 C．G存在一个奇数度数的结点 D．G存在两个奇数度数的结点 5．n阶无向完全图Kn的边数是（ ）．

A. n(n-1), B. n(n-1)/2 C. n-1 D. n(n-1)

二、填空题（每小题3分，本题共15分）

6．设集合A={1, 2, 3}，B={2, 3, 4}，C={3, 4, 5}，则A∪(C?B )等于 ． 7．设A={a, b}，B={1, 2}，C={a, b}，从A到B的函数f={, }，从B到C的函数g={<1, b>, <2, a >}，则g? f等于 ．

8．对于任意的无向图，其所有结点的度数之和等于该图的边数的 ． 9．设G是具有n个结点m条边k个面的连通平面图，则n+k ?2等于 ． 10．设个体域D＝{1, 2, 3, 4}，A(x)为“x等于4”，则谓词公式(?x)A(x)真值为 ．

三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“如果小王来学校，则他会参加比赛．”翻译成命题公式． 12．将语句“今天天晴，昨天下雨．”翻译成命题公式．

四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）

13．设A={1，2，3 }，R={<1，1 >, <1，2 >，<2，1 >, <3，3 >}，则R是等价关系． 14．(?x)P(x)∧Q(y)→R(x)中量词?的辖域为P(x)∧Q(y)． 五．计算题（每小题12分，本题共36分） 15．设集合A={a, b, c}，B={{a, b }, b}，试计算 （1）A?B； （2）A ? B； （3）A×B．

16．设G=，V={v1, v2, v3, v4, v5}，E={(v1,v3) , (v1,v5) , (v2,v3) , (v3,v4) , (v4,v5) }，试

29

（1）给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形．

17．试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．

v1 ? 2 v6 ? 7

5 ? v5

1

1 9 6 ? v2 5 4 ? v3

2 ? v4

3

六、证明题（本题共8分）

18．试证明：┐┐(P?Q)∧┐R ∧（Q?R）? ┐P．

30

离散数学（本）2016年3月份试题

参考解答

一、单项选择题（每小题3分，本题共15分） 1．B 2．C 3．D 4．A 5．B 二、填空题（每小题3分，本题共15分） 6．{1, 2, 3, 5} 7．{, } 8．两倍 9．m

10．真（或T，或1）

三、逻辑公式翻译（每小题6分，本题共12分）

11．设P：小王来学校， Q：他会参加比赛． （2分） 则命题公式为： P ? Q． （6分）

12．设P：今天天晴， Q：昨天下雨． （2分）

则命题公式为：P∧Q． （6分） 四、判断说明题（每小题7分，本题共14分）

13．错误． （3分）

R不是等价关系，因R中不包含<2，2 >，故不满足自反性． （7分） 14．错误． （3分） 辖域为紧接与量词?之后的最小子公式P(x)． （7分） 五．计算题（每小题12分，本题共36分）

15．解：（1）A?B={ b}； （4分）

（2）A ? B={ a, c}； （8分） （3）A×B={, , , , , < c, b>} (12分） 16．解：（1）G的图形表示如图一所示：

图一

（3分）

?0?0?（2）邻接矩阵： ?1??0??10101?0100??1010? （6分）

?0101?0010??（3）v1，v2，v3，v4，v5结点的度数依次为2，1，3，2，2． （9分） （4）补图如图二所示：

31

（12分）

图二

17．解：用Kruskal算法求产生的最小生成树。步骤为： w(v2,v6) =1，选(v2,v6) w(v4,v5) =1，选(v4,v5) w(v1,v6) =2，选(v1,v6) w(v3,v5) =2，选(v3,v5)

w(v2,v3) =4，选(v2,v3) （6分） 最小生成树如图三所示： v1 6 ? ? v2

42 1 5

9 v6 ? ? v3

2 3 5

7

? ? v （9分）

1 4 v5

图三

最小生成树的权w(T)=1+1+2+2+4=10． （12分） 六、证明题（本题共8分） 18．证明：

（1）┐┐(P?Q) P （1分） （2）P?Q T（1）E （3分） （3）（Q?R） P （4分） （4）┐R P （5分） （5）┐Q T（3）（4）I （6分） （6）┐P T（2）（5）I （8分） 说明：

1．因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分． 2．另，可以用真值表验证．

离散数学（本）2016年1月份试题

一、单项选择题（每小题3分，本题共15分）

32

1．若集合A＝{1, 2, 3, 4}，则下列表述正确的是 ( )． A．{1, 2}?A B．{1, 2, 3 } ? A

C．{1, 2, 3 }?A D．{1, 2, 3}?A

2．已知无向图G 的结点度数之和为10，则G的边数为（ ）． A．10 B．20 C．30 D．5

3．无向图G是棵树，结点数为10，则G的边数是（ ）． A. 5 B. 10 C. 9 D. 12

4．设A（x）：x是人，B（x）：x是学生，则命题“有的人是学生”可符号化为（ ）． A．(?x)(A(x)∧B(x)) B．┐(?x)(A(x) →B(x)) C．(?x)(A(x)∧B(x)) D．┐(?x)(A(x)∧┐B(x))

5．下面的推理正确的是（ ）．

A．(1) （?x）（F（x）→G（x）） 前提引入 (2) F（y）→ G（y） ES（1）． B．(1) （?x）F（x）→G（x） 前提引入 (2) F（y）→G（y） US（1）． C．(1) （?x）F（x）→G（x） 前提引入

(2) F（y）→G（y） US（1）．

D．(1) （?x）(F（x）→G（x）） 前提引入 (2) F（y）→G（x） ES（1）．

二、填空题（每小题3分，本题共15分）

6．设A={1，2}，B={ a, b, c }，则A?B的元素个数为 ． 7．有n个结点的无向完全图的边数为 ．

8．设无向图G中存在欧拉路，则G的奇数度数的结点数为 ． 9．设G是有10个结点的连通图，边数为20，则可从G中删去 条边后使之变成树．

10．设个体域D＝{1, 2, 3, 4}，则谓词公式(?x)A(x)消去量词后的等值式为 ．

三、逻辑公式翻译（每小题6分，本题共12分） 11．将语句“小明是个学生．”翻译成命题公式．

12．将语句“他上午去教室上课，下午去体育馆参加比赛．”翻译成命题公式．

四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）

13．存在集合A与B，可以使得A?B与A?B同时成立． 14．完全图K4不是平面图．

五．计算题（每小题12分，本题共36分） 15．设关系R的关系图如下，试

d

33

b

c

（1）写出R的关系表达式；

（2）判断R是否为等价关系，并说明理由．

16．设图G=，V={ v1，v2，v3，v4}，E={ (v1, v2)，(v1, v4)，(v2, v4)}，试 （1）画出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出图G的补图的图形．

17．求?P∨（Q∧R）的合取范式与主合取范式．

六、证明题（本题共8分）

18．对任意集合A，B和C，试证明A? ( B?C ) =( A? B) ? ( A? C )．

34

离散数学（本）2016年1月份试题

参考解答

一、单项选择题（每小题3分，本题共15分） 1．B 2．D 3．C 4．C 5．A

二、填空题（每小题3分，本题共15分） 6．6 7．n(n-1)/2

8．两个或零个 （注：答“两个”也给3分） 9．11

10．A(1 ) ∧A(2) ∧ A(3) ∧ A(4)

三、逻辑公式翻译（每小题6分，本题共12分）

11．设P：小明是个学生． 则命题公式为：P． 12．设P：他上午去教室上课，

Q：他下午去体育馆参加比赛． 则命题公式为：P∧Q

四、判断说明题（每小题7分，本题共14分）

13．正确． 例：设A={a}，B={a，{a}} 则有A?B且A?B． 说明：举出符合条件的实例均给分．

14．错误． 完全图K4是平面图， 如K4可以如下图示嵌入平面．

五．计算题（每小题12分，本题共36分）

15．解：（1）R={< a, b >,< b, a >,< a, c >,< c, a >,< c, d >,< d, c >}．（2）不是等价关系 因为该关系不满足自反性（或答：不满足传递性） 16．解：（1）关系图

35

2分） 6分）

2分） 6分） 3分） 5分） 7分） 3分） 5分） 7分）

（4分） （8分）（12分） （ （ （ （ （ （ （ （ （ （

（3分） （2）邻接矩阵

?0? ?1?0??1（3）deg(v1)=2

deg(v2)=2 deg(v3)=0

101?001?? （6分） 000??100?deg(v4)=2 （9分）

（4）补图

（12分）

17．解：?P∨(Q∧R) ?(?P∨Q)∧(?P∨R) 合取范式 （2分）

?(?P∨Q) ∨(R∧?R) ∧ (?P∨R) （5分） ?(?P∨Q) ∨(R∧?R) ∧ (?P∨R) ∨(Q∧?Q) （7分） ?(?P∨Q∨R )∧(?P∨Q∨?R) ∧ (?P∨R∨Q )∧(?P∨R∨?Q) （10分） ?(?P∨Q∨R )∧(?P∨Q∨?R)∧(?P∨?Q∨R) 主合取范式 （12分）

六、证明题（本题共8分）

18．证明：设S= A? ( B?C )，T=( A? B) ? ( A? C )，

若∈S，则有x∈A且y∈( B?C )，即x∈A且y∈B或y∈C， （1分） 即有 x∈A且y∈B，或x∈A且y∈C， （2分） 可得∈( A? B)，或∈( A? C)， （3分） 则有∈( A? B) ? ( A? C )，即 ∈T， （4分） 所以S?T． （5分） 反之，若∈T，则有∈( A? B)，或∈( A? C)，

则有x∈A且y∈B，或x∈A且y∈C，即有x∈A且y∈B或y∈C， （6分） 则有x∈A且y∈( B?C )， 即有∈S，

所以T?S． （7分） 得证 A? ( B?C )=( A? B) ? ( A? C )． （8分）

36

离散数学（本）2015年10月份试题

一、单项选择题（每小题3分，本题共15分） 1．若集合A＝{1,2,3}，则下列表述正确的是 ( )． A．{1}?A B．{1}?A

C．{1, 2, 3}?A D．??A

2．设A={1, 2, 3｝，B ={1, 2, 3, 4}，A到B的关系R ={ | x大于y｝，则R = ( )． A．{<2, 1>, <3, 1>, <3, 2 >} B．{<1, 1>, <1, 2>, <1, 3>, <1, 4>, <1, 5>} C．{<1, 1>, <2, 1>} D．{<1, 2>, <2, 3>} 3．无向图G的结点的度数之和是10，则图G的边数为（ ）． A．10 B．15 C．20 D．5

4．设连通平面图G有v个结点，e条边，r个面，则（ ）． A．v + e - r=2 B．v + e - r=4 C．r + v - e =2 D．v + e – r = – 4

5．设个体域D是整数集合，则命题?x?y (x?y = y)的真值是（ ）． A．不确定 B．由y的取值确定 C．F D．T

二、填空题（每小题3分，本题共15分）

6．设集合A={a, b, c}，B={b, c}，C={c, d}，则A∩(B∪C)等于 ． 7．设A={2，3}，B={1，2}，C={3，4}，从A到B的函数f={<2, 2>, <3, 1>}，从B到C的函数g={<1，3>, <2，4>}，则Dom(g? f)等于 ．

8．若图G=，其中V={ a, b, c, d }，E={ (a, b), (b, c) , (b, d)}，则该图中的割点为 ．

9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为4，则在G -S中的连通分支数不超过 ．

10．设个体域D＝{1,2, 3, 4}，A(x)为“x大于5”，则谓词公式(?x)A(x)的真值为 ．

三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“雪是白色的，但天是蓝色的．”翻译成命题公式． 12．将语句“如果下雨，则活动取消．”翻译成命题公式．

四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）

13．集合的元素可以是集合．

14．(?x)(P(x)→Q(y)∧R(z))中的自由变元为x．

五．计算题（每小题12分，本题共36分）

15．设A={1，2，3}，R={|x?A，y?A且x +y >4}，S={|x?A，y?A且x

37

试求R，S，R-1，s(S)．

16．图G=，其中V={ a, b, c, d }，E={ (a, b), (a, c) , (a, d), (b, c) , (b, d) , (c, d)}，对应边的权值依次为2、3、4、5、6及7，试

（1）画出G的图形； （2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

17．试画一棵带权为1, 1, 3, 4, 4的最优二叉树,并计算该最优二叉树的权．

六、证明题（本题共8分）

18．试证明：?P∨Q ? P→（? (?P∨?Q)）

38

．离散数学（本）2015年10月份试题

参考解答

一、单项选择题（每小题3分，本题共15分） 1．B 2．A 3．D 4．C 5．D

二、填空题（每小题3分，本题共15分） 6．{b，c }

7．{2，3} （或A） 8．b 9．4

10．假（或F，或0）

三、逻辑公式翻译（每小题6分，本题共12分）

11．设P：雪是白色的，Q：天是蓝色的． 则命题公式为： P∧Q． 12．设P：下雨，Q：活动取消． 则命题公式为：P→Q．

四、判断说明题（每小题7分，本题共14分）

13．正确． 例：集合{{1}}中的元素{1}是集合． 14．错误． (?x)(P(x)→Q(y)∧R(z))中的约束变元为x，自由变元为y与z．

五．计算题（每小题12分，本题共36分） 15．

R={<2, 3>, <3, 2>, <3, 3>} S={<1, 2>, <1, 3>, <2, 3>} R-1={<2, 3>, <3, 2>, <3, 3>} s(S)={ <1, 2>, <1, 3>, <2, 3>, <2, 1>, <3, 1>, <3, 2>}

．（1）G的图形表示为： a ? 4

? d

2 3 7

6 b ? 5

? c 39

（2分） （6分） （2分） （6分） （3分） （7分） （3分） （7分） （3分） （6分） （9分） （12分）3分）

16

（

?0?1（2）邻接矩阵： ??1??1111?011?? （6分） 101??110?（3）粗线与结点表示的是最小生成树， a 4 ? ? d

3 2 7 （10分）

6 b ? ? c 5

权值为9 （12分） 17．

13 ? 5 ? 2 ? ? 8

? ? ? 4 3 4

? 1 ? （10分）

1

权为1?3+1?3+3?2+4?2+4?2=28 （12分）

六、证明题（本题共8分） 18．证明：

（1）?P∨Q P （1分） （2）P P（附加前提） （3分） （3）Q T（1）（2）I （5分） （4）P∧Q T（2）（3）I （6分） （5）? (?P∨?Q) T（4）E （7分） （6）P→? (?P∨?Q) CP规则 （8分）

说明：1、因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分．

另，可以用真值表验证．采用反证法可参照给分．

离散数学（本）2015年7月份试题

一、单项选择题（每小题3分，本题共15分） 1．若集合A＝{1,2,3}，则下列表述正确的是 ( )． A．{1, 2, 3 }?A B．A ? {1, 2 }

C．{1, 2, 3 }?A D．{1, 2}?A

2．已知无向图G 有10条边，则G的结点度数之和为（ ）． A．10 B．20

40

本文来源：https://www.bwwdw.com/article/0f26.html