离散数学大二模拟试题卷

离散数学大二模拟试题卷

…………
_…__…__…__…__…__…__…__…_：…线名…姓…生…学…………………………订………………………号：

…学…生…学…_…__…_装__…__…__…__…__…__…级…班…生…考………………

内蒙古科技大学2015/2016学年第一学期《离散数学》考试试题A卷
课程号：671110300
考试方式：闭卷

使用专业：软件, 计算机, 计算机外

年级：2014-1,2

任课教

师：陈淋艳

考试时间： 年月日

一、将下列命题的真值写在括号内。（共15题，每题2分，共30分）1.（）如果3<2,则6>=5。2.( ) 公式(p?q)?p为重言式。
3.( 1 ) 公式?x?y(x?y?0)的真值为1，个体域为整数集合。

4.（）在公式?xF(x)?G(x,y)中x,y都是约束变元。5.（）公式p?q的主析取范式为?p?q。6.（）若{a}?X,则a?X。

7.（）A，B为任意集合，若A?B=B，则一定有A=?。8.（）空集没有子集。

9.（）集合A={1，2，3}上的二元关系

f={<1,1>,<2,2>,<3,3>,<1,3>}是函数。10.（0）在实数

集合上定义函数f(x)=x2?1存在反函数是。11.（1）n(n>=2)阶有向完

全图不一定是欧拉图。12.（）任意图G的度数为偶数。

13.（）在任意不含环和平行边的图是简单图。

14.（）（1，1，1，1，2，3，3，4）为一棵无向树的度数序列。15.

（）任何图G至少有一棵生成树。

二、选择填空题（共15题，每题2分，共30分）

1.公式p?q的所有成真赋值是（）。

A.00, 01 B.00,10 C.00,11 D.01,11 2.公

式?y(F(y)?G(x))?R(y)中,量词?y的辖域为（）

A.(F(y)?G(x))?R(y) B. F(y)?G(x) C. F(y)?R(y), D.

G(x)?R(y)3.公式p?q等值于（）。

A.p?q B.?p?q C.p??q D. ?p??q

4.公式(?p??q?r)?(?p?q?r)?(p?q??r)的成真赋值是（ ）

A．001,011,110 B. 001, 100,001 C. 110,010, 001 D.

101,100,110

5.?x(P(x)?Q(x))为(P(a)?Q(a))的有效结论,所使用的推理规则是（ ）

A.?? B.?? C.?? D.??

6．如果R是偏序关系，则下列为等价关系的是（ ）。A. r(R)

B. s(R) C. t(R) D.三者都不是 7.R为实数集，函数f:R→R，

f(x)=ex

是（）。

A.单射函数 B.满射函数 C.双射函数 D.三者都不是8.集合A=?，

9.（0，1）和[0，1]为实数集上的开区间和闭区间，Q为有理数集，下

列公式不正确的是（）。

A．{0，1}?（0，1）B．{0，1}?[0，1] C．(0,1)?[0,1] D．(0,1)?Q

10.关系R是传递的,R构成偏序关系应满足（） A．自反性,对称性

B.反自反性,对称性 C.自反性，反对称的 D.反自反性,反对称性

11.根树T的最大度为n,T至少为几杈树

□□□□□□□□□□□□

A. n-3

B. n-2

C. n-1

D. n

12.设图G有5个结点，度数序列为5，5，4，3，3则该图的边数为

14.连通图G有4个奇数度顶点,最少增加多少条边使所得图为欧拉图

（A）。 图1A. 2 B.3 C.4 D.5

15.具有4个结点3条边的非同构的无向简单图数目为（ C）。A.1

B.2 C.3 D.4

三、正明下列各公式（共2题，每题5分，共10分）

1.?s?p,(p?q)?r,q?s?r

2.A，B，C为任意集合，使(A?B)?C?A?(B?C)。四、解下列各题（共3

题，每题4分，共12分）
1.画公式(p?q)?(q?r)的真值表,并求出该公式的主合取范式。2.个体域为{1，2，3}消去公式?x(F(x,y)??yG(y))的量词。

3.无向树T有8片树叶，2个3度分支点，其余为4度分支点，问树T 分支点，写出树T的度数序列。五、（共10分，）集合A=P有多少个
（{a，b,c}） (1)证明<A,?>偏序集。

(2)画出<A,?>的哈斯图（即偏序集合的关系图）。

(3)求出{{a}，{b},{a,b}}的极大，极小，最大、最小元素，上界，下界，上确界，下确界。

六、（8分）写出图1所示有向图的集合表示,邻接矩阵，关联矩阵，并求出图G
的度数序列。