09-10年计算机离散数学试题1

成都信息工程学院考试试卷

2009—2010学年第1学期

课程名称：离散数学使用班级：计算机、网络、信安08级本科

试卷形式：闭卷

试题—三四五六七八九十总分

-

-

-

-

-得分

-

-

-

-

-

-一、单项选择题（在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号

号

学填在题干的括号内。每小题2分，共28分）

二

二1.下列语句是命题的有（b）

二

题

二

二

答A.你是北京人吗？B.明天下雨C.x=3D.好冷啊!

一

不

名2.设A={1,2,3,4,5},下面(c）集合等于A

姓

内

二

线A.{1,2,3,4,5,6)B.{x|x是整数且x?W25}

二

二

封

C.{x|x是正整数且x<5}D.{x|x是正有理数且xW5}

二

密

二

一3.公式A=^(P(x)-Q(x))的解释I为：个体域D={2},P(x)：x>3,Q(x)：x=4则A的真

级值为(a)

班

二A.1B.0C.可满足式D.无法判定

二

二4.设集合A={a,b,c},R是A上的二元关系,R={<a,a>,<a,b>,<b,a>,<c,a>,<c,b8^R

二

是(c)

二

一

名A.自反的B.对称的C.传递的D.反对称的

系

5.六阶群的子群的阶数可以是（d）

A.1,2,5B.2,4C.3,6,7D.2,3

6.下列等价关系正确的是（b）

A.冈<(P(x)&(x))冈欧P(x)冈欧(x)B.冈(P(x)&(x))冈四P(x)冈磔(x)

C.冈<(P(x)冈Q)冈冈<(P(x))冈QD.瓯P(x)冈Q)冈区(P(x))冈Q

/vA-

——弟1页----

7.一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（a）个

4度结点

A.1B.2C.3D.4

8.设G是n个结点、m条边和r个面的连通平面图，则m等于（a）

A.n+r-2B.n-r+2C.n-r-2D.n+r+2

9.设R是集合A上的偏序关系，R是R的逆关系，则RUR是（b)

A.偏序关系B.等价关系C.拟序关系D.都不是

10.下列运算中，哪种运算关于整数集不能构成半群（d）

A.aS>=max{a,b}B.a^?=bC.a冈D=2abD.a冈)=|a-b|

11.设G=〈V,E>为有向图，V={a,b,c,d,e,f),E={〈a,b>,<b,c>,<a,d>,<d,e>,<f,e^}贝！I

G是(c)

A.强连通图B.单向连通图C.弱连通图D.不连通图

12.下面哪个命题公式是重言式（）

A.(P冈Q)区Q冈P)B.(P&)冈PC.「P欧D.「（P画

13.谓词公式冈<（P（x）冈区Q（y））冈R（x）中量词冈（的辖域是（)

A.冈<(P(X)冈MQ(y))B.P(x)C.P(x),R(x)D.P(x)冈区|Q(y)

14.欧拉回路是（）

A.基本回路B.简单回路C.既是基本回路也是简单回路

D.既不是基本回路也不是简单回路

二、填空题（每题2分，共12分）

1.设F（x）：x是人，H（x）：x呼吸。则命题“凡人都呼吸"符号化为.

2.集合A={a,{b,c}}的鬲集耶）=.

3.设二元关系S={<1,3>,<2,2><3,4>},则定义域D（S）=，值域

R（S）=.

---第2页---

4.设s是非空有限集，区s）为s的鬲集，在代数系统〈国s）,n＞中，区s）对c运算的幺元

7E____________2_零兀7E.

5.n个顶点的无向完全图中共有条边.

6.I是整数集，I上模3等价类是.

--

--

--

--三.（本题8分）求命题公式（P&）冈（Q除）的主析取范式和主合取范式.

-

--

--

--

--

--

--

号-

学-

二-

二-

二

题

二

答

二

一

不

名

内

姓

二

线

二

四.（本题8分）构造下面的命题推理证明：如果小张和小王去看电影，则小李也去看电

封

二

二

密影；小赵不去看电影或小张去看电影；小王去看电影.所以，当小赵去看电影时，小李

二

一.也去.

级.

班.

二.

二.

二.

二.

二.

一.

名.

系.

---第3页---

五.(本题8分)用逻辑恒等式证明：(P冈Q)区区P冈Q)冈冈P冈Q).

六.(本题10分)设集合A={l,2,3,6,15,30},R是A上的整除关系.

(1)画出偏序集＜A,R＞的哈斯图.

(2)求A的最大元、最小元.

(3)求A的子集{2,3,6}的上界、下界、最小上界及最大下界.

---第4页---

七.(本题5分)设人={1,2,3,4},Ri与R2都是A上的二元关系，其中

><求逆关系及合成关系

RI={<1,2><2,3>,<2,4,3,3>},R2={<2,2><2,3>,<3,4>}.Ri

R1'R2.

二-

-

二-

-

二-

-

二-

-

二-

一-

-

号-

-

学-

-

二-八.体题分)设代数系统因，其中冈如下表所定义，问:

-8VS,S={a,b,c,d},

二-

题

二(1)冈是否可交换？

二

答是否有么元？如果有，指出哪些元素是可逆的，并给出它们的逆元.

二(2)S

不

一⑶代数VS,因是否构成群？

名

内冈abcd

姓

线

二

二aabcd

封

二

二

密bbeda

二

.

一.ccdab

.

级.

.

班.ddabc

.

二.

.

二.

.

二.

.

二.

.

二.

.

一.

.

名.

.

系.

---第5页---

九.(本题8分