离散数学试题及解答

离散数学

2^m*n

一、 选择题（2*10）

1．令P：今天下雨了，Q：我没带伞，则命题“虽然今天下雨了，但是我没带伞”可符号化为（

（A）P→?Q （C）P∧Q

）。

（B）P∨?Q （D）P∧?Q

2．下列命题公式为永真蕴含式的是（ ）。

（A）Q→（P∧Q） （B）P→（P∧Q） （C）（P∧Q）→P （D）（P∨Q）→Q

3、命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死的”的否定是（

）。

（A）所有人都不是大学生，有些人不会死 （B）所有人不都是大学生，所有人都不会死 （C）存在一些人不是大学生，有些人不会死 （D）所有人都不是大学生，所有人都不会死 4、永真式的否定是（ ）。

（A）永真式 （B）永假式 （C）可满足式 （D）以上均有可能 5、以下选项中正确的是（ ）。

（A）0= ?

（B）0 ? ? （C）0∈?

（D）0??

6、以下哪个不是集合A上的等价关系的性质？（ ）

（A）自反性

（B）有限性

（C）对称性

（D）传递性

7、集合A={1,2,…,10}上的关系R={|x+y=10,x,y∈A}，则R的性质为（ ）。

（A）自反的

（B）对称的

（C）传递的，对称的 （D）传递的

8．设D=为有向图，V={a, b, c, d, e, f}, E={, , , , }是（

）。

（A）强连通图 （B）单向连通图

（C）弱连通图 （D）不连通图

9、具有6个顶点，12条边的连通简单平面图中，每个面都是由（ ）条边围成？

（A）2

（B）4

（C）3

（D）5

10．连通图G是一棵树，当且仅当G中（ ）。

（A）有些边不是割边 （B）每条边都是割边 （C）无割边集

（D）每条边都不是割边

二、 填空题（2*10）

1、命题“2是偶数或-3是负数”的否定是________。

2、设全体域D是正整数集合，则命题?x?y(xy=y)的真值是______。

3、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为________。

4、公式(?P?Q)?(?P??Q)化简为________。 5、设A∩B=A∩C，A∩B=A∩C，则B________C。

6、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点中，单位元是________，零元是________。

7、任一有向图中，度数为奇数的结点有________(奇数/偶数)个。 8．如下无向图割点是________，割边是________。

三、（10分）设A、B和C是三个集合，则A?B??(B?A)。

。四、（15分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下

五、（15分）设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：

六、（20分）画一个图使它分别满足： （1）有欧拉回路和哈密尔顿回路； （2）有欧拉回路，但无条哈密尔顿回路； （3）无欧拉回路，但有哈密尔顿回路； （4）既无欧拉回路，又无哈密尔顿回路。

A C

B A C

B A C B 答案： 一、

选择题：

2、C 7、B

3、A 8、C

4、B 9、C

5、D 10、B

1、D 6、B 二、填空：

1、2不是偶数且-3不是负数 2、F

3、??x(R(x)?Q(x)) 4、?P 5、等于 6、2，6 7、偶数 8、d，e5

三、证明：

A?B??x(x∈A→x∈B)∧?x(x∈B∧x?A)??x(x?A∨x∈B)∧?x(x∈B∧x?A) ???x(x∈A∧x?B)∧??x(x?B∨x∈A)???x(x∈A∧x?B)∨??x(x∈A∨x?B) ??(?x(x∈A∧x?B)∧?x(x∈A∨x?B))??(?x(x∈A∧x?B)∧?x(x∈B→x∈A)) ??(B?A)。

四、解 设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据

题意应有：A?C?D，?(B∧C)，C??D必须同时成立。因此 (A?C?D)∧?(B∧C)∧(C??D)

?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D)

?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D)) ?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D) ∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D)

∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D)

?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F

?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D) ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D) ?T

故有三种派法：B∧D，A∧C，A∧D。 五、

?000???（1）R={<2,1>,<3,1>,<2,3>};MR=?101?;它是反自反的、反对称的、传递的；

?100????011???（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=?101?;它是反自反的、

?110???对称的；

?011???（3）R={<1,2>,<2,1>,<1,3>,<3,3>};MR=?100?;它既不是自反的、反自反的、

?001???也不是对称的、反对称的、传递的。 六、