离散数学题目大汇总

35．符合化下列命题，并构造推理证明：三角函数都是周期函数，有些三角函数是连续函数，所以有些

周期函数是连续函数。

36．两个等价关系的并集不一定是等价关系，试举例说明。

一、单项选择题：（每小题1分，本大题共10分）

1．命题公式P?(Q?P)是（ ）。

A、 矛盾式； B、可满足式； C、重言式； D、等价式。 2．下列各式中哪个不成立（ ）。 A、?x(P(x)?Q(x))??xP(x)??xQ(x) ； B、?x(P(x)?Q(x))??xP(x)??xQ(x)； C、?x(P(x)?Q(x))??xP(x)??xQ(x)； D、?x(P(x)?Q)??xP(x)?Q。

3．谓词公式?x(P(x)??yR(y))?Q(x)中的 x是（ ）。 A、自由变元； B、约束变元；

C、既是自由变元又是约束变元； D、既不是自由变元又不是约束变元。4．在0 ?之间应填入（ ）符号。 A、= ； B、? ； C、? ； D、? 。 5．设< A ，

? > 是偏序集，B?A，下面结论正确的是（ ）。

A、B的极大元b?B且唯一； B、B的极大元b?A且不唯一；C、B的上界b?B且不唯一； D、B的上确界b?A且唯一。 6．在自然数集N上，下列（ ）运算是可结合的。

（对任意a,b?N）

A、a?b?a?b ； B、a?b?max(a,b) ； C、a?b?a?5b ； D、a?b?a?b。

7．Q为有理数集N，Q上定义运算*为a*b = a + b – ab ,则的幺元为（ A、a； B、b； C、1； D、0。

8．给定下列序列，（ ）可以构成无向简单图的结点次数序列。 A、（1，1，2，2，3）； B、（1，1，2，2，2）；

C、（0，1，3，3，3）； D、（1，3，4，4，5）。

9

。 ）9．设G是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。

A、点与边； B、边与点； C、点与点； D、边与边。

10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。

A、5； B、7； C、9； D、8。

二、填空：（每空1分，本大题共15分）

1．在自然数集中，偶数集为N1、奇数集为N2，则N1?N2= ；

N1?N2 = 。

2．设X?{1,2,3,4},R?{?1,2?,?2,4?，?3,3?}，则

r (R) = ；s (R) = ；t (R) = 。 3．设R为集合A上的等价关系，对?a?A，集合[a]R= ， 称为元素a形成的R等价类，[a]R??，因为 。 4．任意两个不同小项的合取为 ，全体小项的析取式为 。 5．设Q(x):x为偶数，P(x):x为素数，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：（1） ；

（2） 。

6．设T为根树，若 ，则称T为m元树；

若 则称T为完全m叉树。

7．含5个结点，4条边的无向连通图（不同构）有 个，

它们是 。

三、判断改正题：（每小题2分，本大题共20分）

1．命题公式(A?(A?B))?B是一个矛盾式。 （ ） 2．任何循环群必定是阿贝尔群，反之亦真。 （ ） 3．根树中最长路径的端点都是叶子。 （ ） 4．若集合A上的关系R是对称的，则R?1也是对称的。 （ ）

5．数集合上的不等关系（≠）可确定A的一个划分。 （ ） 6．设集合A、B、C为任意集合，若A×B = A×C，则B = C。 （ ） 7．函数的复合运算“。”满足结合律。 （ ） 8．若G是欧拉图，则其边数e合结点数v的奇偶性不能相反。 （ ）

10

9．图G为（n , m）图，G的生成树TG必有n个结点。 （ ） 10．使命题公式P?(Q?R)的真值为F的真值指派的P、Q、R值分别是T、F、F。 （ ）

四、简答题（每小题5分，本大题共25分）

1．设?H,??和?K,??都是群?G,??的子群，问?H?K,??和?H?K,??是否是?G,??的子并说明理由

2．设A?{2，3，4，9}，B?{2，4，7，10,12}，从A到B的关系

R?{?a,b?a?A,b?B,且a整除b}，试给出R的关系图和关系矩阵，并说明此关系是否为函

数？为什么？

3．设?S,??是半群，OL是左零元，对任x?S,x?OL是否是左零元？为什么？

4．某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）

5．通过主合取范式，求出使公式?(?P?Q)?R的值为F的真值指派。

五、证明题：（共30分）

1．设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。

2．试证明若?G,??是群，H?G，且任意的a?H，对每一个x?G，有a?x?x?a，则?H,??是?G,??的子群。

3．设G是每个面至少由k（k?3）条边围成的连通平面图，试证明e?为边数。

4．符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。

离散数学试题<二>

一、选择题（10×2） 1．下述说法错误的是（ ）

A．若a?A则a?A?B B．若a?A则a?A?B C．若a?A?B，则a?A D．若A?B，则A?B?A

11

k(v?2)，其中v为结点数，ek?22．设G是连通平面图，G中有11个结点，5个面，则G中边的条数是（ ） A．10 B．12 C．16 D．14 3．以下关系中能构成函数的是（ ）

A．?(1.2),(2.1),(3.4),(4.3)? B．?(1.2),(1.1),(2.2),(3.2)? C．?(1.2),(2.3),(3.4),(4.1)? D．?(1.4),(3.1),(2.3),(4.1),(3.2)? 4．图G如下图所示，则G是（ ）

A．欧拉图，非哈密顿图 B．哈密顿图，非欧拉图 C．非欧拉图，非哈密图 D．欧拉图且哈密顿图

5．下列代数系统能够构成群的是（ ）

A．（Q；+） B．（Q，-） C．（R；·） D．（I，+） 6．关于有补格的描述不正确的是（ ）

A．有补格必有界 B．有补格中每个元素的补元一定存在 C．有补格满足德摩根定律 D．有补格的元素不一定有限 7．若图G的所有回路均为偶数长，则G（ ）

A．G是欧拉图 B．G是哈图 C．G是平面图 D．G是二部图 8．下述公式正确的是（ ）

A． P?Q?Q?P B．P?Q?Q?P C．P?Q??Q??P D．P?Q??P??Q 9．设A=｛a,b,c,d｝，A上的关系ρ=｛（a,b),(b,a),(c,a),(c,b),(a,a),(b,b)｝,则 ρ是（ ）

A．自反的 B．对称的 C．反对称的 D．传递的 10．复合语句“他工作很努力；但是思想僵化”中的逻辑联结词为（ ） A．∨ B．∧ C．→ D．? 二、填空（10×2）

12