2012《离散数学》A卷

2012级 离散数学 课程试题（A卷）

题号 分数 一 二 三 四 五 六 七 总分 合分人： 复查人：

分数 一、

1．设谓词A.C.

是实数，

,则语句“没有最小的实数”可符号化为( )。 B. D.

评卷人 选择题：（每题1分，共15分）

2.下列语句是真命题的是（ ）。

A.雪是黑色的，当且仅当5<0 B. 自然数中存在最大素数 C.今天天气真好呀 D. 只有5<0，雪才是白色的 3．设A.4.设A.5.设

B.，则（ ）。 B.

，则其幂集

C.

D.

，则下列陈述正确的是（ ）。

C.

D.

的元素总个数为（ ）。

A.2 B.3 C.4 D.8 6.设

，A上的等价关系

，则对应

于R的A的划分是（ ）。

A．{{a},{b,c},{d}} B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}

共 8 页 第 1 页

7．是一个偏序集，其中A是正整数12的正因子的集合，为整除关系，则能盖住

元素3的元素是（ ）。

A.1 B.3 C.6 D.12 8．在整数集Z上，下列定义的运算满足结合律的是（ ）。 A. C.9.设

B.

D.

是群，则下列陈述不正确的是（ ）。

n（ab）?anbn A.n（a-1ba）?a?1bna B.

m（an）?anm D.anam?an?m C.

10. 设X?{0}，下列关于代数系统?P(X),??的陈述正确的是（ ）。

A. 0是幺元 B.

?是幺元 C.｛0｝是幺元

D.没有幺元

11.设Z是整数集，+，?分别是普通加法和乘法，则（Z，+，?）是（ ）。 A．域

B．整环和域 C．整环 D．含零因子环

12．设简单图G所有顶点的度数之和为36，则G的边数为（ ）。 A.12 B.18 C.36 13.下列无向图不一定是树的是（ ）。

A. 有n个结点，n-1条边的图 B. 无回路的连通图 C. 连通但删去一条边则不连通的图 D.无回路但添加一条边则有一个回路的连通图 14．下列必为欧拉图的是（ ）

A.有回路的连通图 B.不可以一笔画的图 C.有1个奇数度顶点的连通图 D.无奇数度顶点的连通图

15．在简单无向图G??V,E?中，如果V中的每个顶点都与其余的所有顶点邻接，则该图称为（ ）。

A.正则图 B.完全图 C.连通图 D.强连通图

共 8 页 第 2 页

D.72

分数 二、填空题：（每空2分，共28分）

1．公式((p?q)?(q?r))?(p?r)的主析取范式中的极小项有_________________，其

成

真

赋

值

为

_______________________________,

成

假

赋

值

为评卷人 ________________________。 2．公式

________________。

3．设R=｛＜1，2＞，＜2，3＞，＜4，5＞｝和S=｛＜3，2＞，＜4，3＞，＜5，1＞｝是集合A=｛1，2，3，4，5｝上的两个关系，则R?S?_____________,S?R=________________。 4．若集合A中有三个元素，则A上的关系有___________个，其中__________个是等价关系，___________个是偏序关系。

5．设Q为有理数集，笛卡尔集S=Q×Q，*是S上的二元运算，??a,b?,?x,y??S,

的约束变元为_____________, 自由变元为

?a,b?*?x,y???ax,y?b?, 则*运算的幺元是________________。??a,b??S,

若a≠0，则?a,b?的逆元是________________。

6．一个连通平面图共有7个顶点，3个面，则G的边数为_______________。

7.设简单无向图G有15条边，有3个4度顶点，4个3度顶点，其余顶点的度数均为2，则G中的顶点个数为________________。

分数 三、计算题：（每题分数见题后，共27分）

1．（4分）设解释I如下：

共 8 页 第 3 页

评卷人 D={2，3}，a=3，F(2,2)=F(3,3)=0，F(2,3)=F(3,2)=1，f(2,2)=f(2,3)=2，f(3,2)=f(3,3)=3。

求谓词公式

2.（7分） 设R=｛是A=｛1,2,3,4｝上的二元<1,4>,<2,1>,<2,3>,<3,1>,<4,2>,<4,3>｝关系，

（1）画出R的关系图； （2）写出R的关系矩阵； （3）说明在

共 8 页 第 4 页

在I下的真值。

A上R是否具有自反、反自反、对称、反对称性质。

2. （8分）在

域中解方程组，其中+为模5加法，*为模5乘法。

4．（8分）某城市拟在六个城区之间架设有线电视网，其网点间的距离如下列的无向有权图矩阵给出，给出架设线路的最优方案，请画出图，并计算出最优方案下的线路的长度。

共 8 页 第 5 页

分数 四、证明题：（每题分数见题后，共30分）

1.（10分）当且仅当

共 8 页 第 6 页

评卷人 分别是集合S、T上的关系，定义

。证明：若

上的关系

为等价关系。

为等价关系，则

2.（12分）

是群，其中为模n加法。

）：对任意

。

，

定义代数系统（

证明：若m、n互质，（

）是循环群，生成元是<1,1>。

共 8 页 第 7 页

3.（8分）有下列命题：

(1)参加展览的人中，每个N大学的男生都背K牌书包。 (2)参观展览的人中，每个背K牌书包的都是来自N大学的男生。 (3)每个背K牌书包的N大学男生都参观了该展览。

写出相关的逻辑表达式，并证明（1）（2）不能推出（3），方法任选。

共 8 页 第 8 页

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