离散数学（本科）

《离散数学》复习资料 2014年12月

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

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

A． A?B，且A?B B．B?A，且A?B C．A?B，且A?B D．A?B，且A?B 2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

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

C．（c）是强连通的 D．（d）是强连通的 3．设图G的邻接矩阵为

?01100??10011???

?10000???01001????01010??则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( C )为重言式．

A．?P??Q?P?Q B．(Q?(P?Q)) ?(?Q?(P?Q))

C．(P?(?Q?P))?(?P?(P?Q)) D．(?P?(P?Q)) ?Q

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

A．R1和R2 B．R2 C．R3 D．R1和R3

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

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

8．若集合A的元素个数为10，则其幂集的元素个数为（ A ）． A．1024 B．10 C．100 D．1

9．设完全图Kn有n个结点(n≥2)，m条边，当（ C ）时，Kn中存在欧拉回路．

A．m为奇数 B．n为偶数

1

C．n为奇数 D．m为偶数 10．已知图G的邻接矩阵为

，

则G有（ D ）．

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

11.无向完全图K3的不同构的生成子图的个数为（ C ） (A) 6 (B) 5 (C) 4 (D) 3

12 n阶无向完全图Kn中的边数为（ A ）

(A)

n(n?1)n(n?1) (B) (C) n (D)n(n+1) 2213.在图G＝中，结点总度数与边数的关系是( C )

A deg(vi)=2?E? (B) deg(vi)=?E? C

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

v?Vv?V

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

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

2．若A={1,2}，R={|x?A, y?A, x+y<4}，则R的自反闭包为 {<1,1>,<2,2>,<1,2>,<2,1>} ．

3．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 ． 4．(?x)(P(x)→Q(x)∨R(x，y))中的自由变元为 R(x，y )中的y ． 5．设集合A＝{a，b}，那么集合A的幂集是 {?,{a,b},{a},{b }} 6．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个． 7．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树．

8．无向图G存在欧拉回路，当且仅当G所有结点的度数全为偶数且 连通 9．设连通平面图G的结点数为5，边数为6，则面数为 3 ．

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

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

1．将语句“雪是黑色的．”翻译成命题公式．

设P：雪是黑色的， （2分）

2

则命题公式为：P．

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

解：设P：他去学校， 则命题公式为： ? P．

3．将语句“小王是个学生，小李是个职员，而小张是个军人．”翻译成命题公式．

设P：小王是个学生，Q：小李是个职员，R：小张是个军人． （2分） 则命题公式为：P∧Q∧R．

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

Q：明天的会议取消， 则命题公式为： P? Q．

5．将语句“他去旅游，仅当他有时间．”翻译成命题公式． 解：设 P：他去旅游，Q：他有时间，

则命题公式为： P ?Q．

6．将语句“41次列车下午五点开或者六点开．”翻译成命题公式．

解：设P：41次列车下午五点开，Q：41次列车下午六点开， （2分）

命题公式为：（P∧?Q）∨（?P∧Q） 7．将语句“小张学习努力，小王取得好成绩．”翻译成命题

设P：小张学习努力，Q：小王取得好成绩， （2分） 则命题公式为：P?Q．

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

解：设P(x)：x是人，Q(x)：x去上课， （1分） (?x)(P(x) ?Q(x)

9．将语句“所有的人都学习努力．”翻译成命题公式． 解：设P(x)：x是人，Q(x)：x学习努力，

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

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

1．设集合A={1, 2, 3, 4}，B={2, 4, 6, 8}，，判断下列关系f是否构成函数f：A?B，并说明理由．

(1) f={<1, 4>, <2, 2,>, <4, 6>, <1, 8>}； (2)f={<1, 6>, <3, 4>, <2, 2>}；

(3) f={<1, 8>, <2, 6>, <3, 4>, <4, 2,>}．

答：（1）不构成函数 因为3?A，但f?3?没有定义，所以不构成函数 （2）不构成函数 因为4?A，但f?4?没有定义，所以不构成函数 （3）满足。 因为任意x?A，都有f?x??B且结果唯一。 2．若集合A = {1，2，3}上的二元关系R={<1, 1>，<2, 2>，<1, 2>}，则

3

(1) R是自反的关系； (2) R是对称的关系． 答：（1）错误 因为3，3?R，所以R不是自反的

（2）错误 因为1，2?R，但是2，1?R，所以R不是对称的

3．如果R1和R2是A上的自反关系，判断结论：“R11、R1∪R2、R1∩R2是自反的” 是否成立？并说明理由．

-

答：成立 因为任意a?A，有a,a?R1,a,a?R2 所以a,a?R?1，a,a?R1R2，a,a?R1R2 R-11、R1∪R2、R1∩R2是自反的

a ?

? c g ?

b ? d ? 4．若偏序集的哈斯图如图一所示， 则集合A的最大元为a，最小元不存在． 答：错误，集合A没有最大元，也没有最小元

? h

? f e ?

图一

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

其中a是极大元

解：正确

对于集合A的任意元素x，均有?R（或xRa），所以a是集合A中的最大元．按照最小元的定义，在集合A中不存在最小元．

6．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．

答：错误 如果图G是无向图，且图G是连通的，同时结点度数都是偶数 7．设G是一个连通平面图，且有6个结点11条边，则G有7个面．

答案：正确

定理，连通平面图G的结点数为v，边数是e，面数为r，则欧拉公式v-e+r=2

成立

所以r=2-v+e=2-6+11=7

则G存在一条欧拉回路

8．设G是一个有6个结点14条边的连通图，则G为平面图． 解：错误，不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．” 9．命题公式?P?(P??Q)?P为永真式．

解：正确 因为，由真值表 P 0

Q 0 ?P 1 ?Q 1 P??Q 1 4

?P∧(P→?Q)∨P 1 0 1 1 1 0 1 1 0 0 0 1 0 1 1 0 1 1 1 可知，该命题公式为永真式．

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

1．设集合A={a, {b}, c}，B={{a}, c}，试计算

（1）（A∩B）； （2）（B ? A）； （3）（A∩B）×B． 解（1）（A∩B）={c}；

（2）（B ? A）={{a}}； （3）（A∩B）×B={, < c，c >}

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

解：R={<0,0>} S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} R?S={<0,0>,<0,1>,<0,2>,<0,3>}

R-1={<0,0>} S-1= S ） r(R)=IA．

3．图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权最小的生成树及其权值．

解：（1）G的图形表示为：

（3分）

（2）邻接矩阵：

?0?1??1??0??11101?0011??0011? （6分）

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

5

权为7：

4．设图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) 求出每个结点的度数； (3) 画出图G的补图的图形． 解：（1）关系图

v1 ?

v2 ? v5

? ? v4 v3

（2）deg(v1)=2 deg(v2)=3 deg(v3)=4

deg(v4)=3 deg(v5)=2

（3）补图 v1

? v5 v2

? ?

?

v3

?

?

v4

5．设集合A={1，2，3，4}，R={|x, y?A；|x?y|=1或x?y=0}，试

（1）写出R的有序对表示； （2）画出R的关系图；

（3）说明R满足自反性，不满足传递性．

解:（1）R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>} （3分） （2）关系图为

1 ? 2 3 ? ?

4 ?

（3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。

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

6

6．设集合A={1, 2, 3}，R={<1，1>, <2，1>,<3，1>}，S={<1，2>, <2，2>}试计算 （1）R?S； （2）R ?1； （3）r（R）．

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

（2）R ?1={<1，1>, <1，2>, <1，3> }； （8分） （3）r（R）={<1，1>, <2，2> , <3，3>, <2，1>,<3，1>}

7、求出如图一所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树

的权．

解 用Kruskal算法求产生的最小生成树．步骤为：

w(v1,v7)?1 选e1?v1v7 w(v3,v4)?3 选e2?v3v4 w(v2,v7)?4 选e3?v2v7 w(v3,v7)?9 选e4?v3v7

w(v4,v5)?18 选e5?v4v5

w(v1,v6)?22 选e6?v1v6 最小生成树如图四所示：

图四

最小生成树的权为：w(T)=22+1+4+9+3+18=57．

8．试画一棵带权为2, 3, 3, 4, 5,的最优二叉树,并计算该最优二叉树的权． 解： 最优二叉树如图二所示．

?17

10 ? ? 7 5 ? ?5 ?? 3 4 2 ? ? 3 图二

7

（6分）

（9分）

12分） 10分）

（ （ 权为2?3+3?3+3?2+4?2+5?2=39

9．设谓词公式?x(A(x,y)??zB(x,y,z))??yC(y,z)，试

（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元．

（1）?x量词的辖域为(A(x,y)??zB(x,y,z))， （2分）

?z量词的辖域为B(x,y,z), （4分） ?y量词的辖域为C(y,z)． （6分） （2）自由变元为(A(x,y)??zB(x,y,z))中的y，以及C(y,z)中的z （9分） 约束变元为(A(x,y)??zB(x,y,z))中的x与B(x,y,z)中的z，以及C(y,z)中的y． 10．设谓词公式(?x)P(x,y)?(?z)Q(x,y,z)，试

（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元． （1）?x量词的辖域为P(x,y)， （3分）

?z量词的辖域为Q(x,y,z), （6分） （2）自由变元为公式中的y与Q(x,y,z)中的x， （9分）

约束变元为P(x,y)的x与Q(x,y,z)z．

11．求命题公式(P?Q)?(R?Q) 的主析取范式、主合取范式． 解：

P Q R P?Q R?Q 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 (P?Q)?(R?Q) 1 1 1 1 0 1 1 1 极小项 ?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

12．求（P∨Q）→（R∨Q）的析取范式，合取范式．

解：（P∨Q）→（R∨Q）

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

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

8

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

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

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

证明：设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．

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

（2）P（a）∧R（a） ES(1) （3）P（a） T(2)I （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

9

本文来源：https://www.bwwdw.com/article/8cz8.html