离散数学试题库

1

计算机工程系 2004—2005学年第一学期期末考试

《离散数学》试卷

考试时间：120钟 考试方式：闭卷

班级 专业 姓名 学号

题号 一 二 三 四 总分

得分

登分人 核分人

一、单项选择题（本大题共10题，每小题2分，共20分。将答案填在下面的表格内）

1、 下列是两个命题变元p，q的小项是（ ）

A、p∧┐p∧q B、┐p∨q

C、┐p∧q D、┐p∨p∨q

2、 令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）

A、p→┐q B、p∨┐q

C、p∧q D、p∧┐q

3、 下列语句中是命题的只有（ ）

A、1+1=10 B．x+y=10

C、sinx+siny<0 D、x mod 3=2 得分 阅卷人

装 订 线 内 请 勿 答 题

2 4、 下列等值式不正确的是（ ）

A、┐xA  x┐A

B、(x)(B→A(x)) B→(x)A(x)

C、(x)(A(x)∧B(x))  (x)A(x)∧(x)B(x)

D、(x)( y)(A(x)→B(y))  (x)A(x)→(y)B(y)

5、 谓词公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z))中量词x的辖域是（ ）

A、(x)Q(x,z)→(x)(y)R(x,y,z))

B、Q(x,z)→(y)R(x,y,z)

C、Q(x,z)→(x)(y)R(x,y,z)

D、Q(x,z)

6、 设R为实数集，函数f：R→R，f(x)=2+x，则f是（ ）

A、满射函数 B．单射函数

C、双射函数 D、非单射非满射

7、 设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划分是（ ）

A 、{{a},{b,c},{d}} B、{{a,b},{c},{d}}

C、{{a},{b},{c},{d}} D、{{a,b},{c,d}}

8、 设A={Ø}，B=P(P(A))，以下正确的式子是（ ）

A、{Ø,{Ø}}∈B B、{{Ø,Ø}}∈B

C、{{Ø},{{Ø}}}∈B D、{Ø,{{Ø}}}∈B

9、 在自然数集N上，下列定义的运算中不可结合的只有（ ）

A、a*b=min(a,b) B、a*b=a+b

C、a*b=GCD(a,b)(a,b的最大公约数) D、a*b=a(mod b) 3 10、R为实数集，R+={x|x∈R∧x>0}，*是数的乘法运算，< R+，*>是一个群，则下列集合关于数的乘法运算构成该群的子群的是（ ）

A、{ R+中的有理数} B、{ R+中的无理数}

C、{ R+中的自然数} D、{1，2，3}

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

1、设论域是{a,b,c}，则(x)S(x)等价于命题公式 ；()S(x)等价于命题公式 。

2、某非空集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是 ，其关系矩阵是

。

3、设是一个偏序集，如果S中的任意两个元素都有 和 ，则称S关于≢构成一个格。

4、设Z是整数集，在Z上定义二元运算*为a*b=a+b其中+是数的加法，则代数系统的幺元是 ，零元是 。

5、设R为A上的关系，则R的自反闭包r(R)= ，对称闭包s(R)= 。

6、设A={a,b,c}，B={1,2,3}，则A到B共可产生_______个不同的双射函数。

7、设F(x): x是人，G(x): 张着绿色的头发，命题“没有人长着绿色的头发”在一阶逻辑中符 号化的形式为_______________。

8、设A={1,2},B={2,3},C={a,b,c}，则(A∪B)×C=___ _。

9、A、B是集合，A={1,4},B={2,4},则P(A)-P(B)= .

10、.图4中结点V6的度数为____。

得分 阅卷人

装 订 线 内 请 勿 答 题

„„„„„„„„„„„„„„„„„„„„„„..装„„„„„„„.订„„„„„„„..线„„„„„„„„„„„„„„„„„„„„„ 4

三、 计算题 （本大题共6题，共34分）

1、 用等值演算法求公式┐(p∨q)∧(p→r)的主合取范式,并判断公式的类型。（6分）

2、．（7分）在偏序集中，其中Z={1,2,3,4,6,8,12,24}，≢是Z中的整除关系，画出的哈斯图,求集合D={2,3,4,6}的极大元，，最小元，最小上界和最大下界。

3设二元关系R={, <{a}, b>,<{φ}, {φ}>, <{φ}, {φ}>}求：(6分)

（1）domR

（2）ranR

（3）R°R

（4）R-1° R-1

4、已知无向图G有11条边，2度与3度顶点各2个，其余都是4度顶点，求G中共有几 个顶点。（写出过程）（5分）

得分 阅卷人

装 订 线 内 请 勿 答 题

„„„„„„„„„„„„„„„„„„„„„„..装„„„„„„„.订„„„„„„„..线„„„„„„„„„„„„„„„„„„„„„ 5 5、.（6分）求出图5的最小生成树，并计算该树的权。

251476811121039ABCDEFGHI

6、求公式xP(x,y) →yQ(y)的前束范式。（4分）

四、证明题。(本大题共2题，共16分)

1、验证下列论证是否有效，并给出推理。

如果我学习，我的数学课就不会不及格。如果我不打篮球，我就会学习。但是我的数学课不及格。因此我肯定打篮球了。

2、（8分）设P（A）是非空集合A的幂集，是集合P（A）上的包含关系。

证明：是偏序集

得分 阅卷人

6

计算机工程系 2004—2005学年第一学期重修考试

《离散数学》试卷

考试时间：120钟 考试方式：闭卷

班级 专业 姓名 学号

题号 一 二 三 四 总分

得分

登分人 核分人

一、判断题(每小题2分，共12分)

题号 1 2 3 4 6

答案

1、设A、B为任意的命题公式，则吸收律为(A∧B)∨A。

2、x(F(y) →G(x))F(y)→xG(x)。

3、图中的初级回路都是简单的回路。

4、设R非空集合A上的关系，R是A上可传递的，当且仅当R○RR。

5、设A、B、C为任意的三个集合，则A×(B×C)=A×(B×C)。

6、设A={a,b,c}，RA×A且R={},则R是传递的。 得分 阅卷人

装 订 线 内 请 勿 答 题

„„„„„„„„„„„„„„„„„„„„„„..装„„„„„„„.订„„„„„„„..线„„„„„„„„„„„„„„„„„„„„„ 7

二、填空题(每空3分，共30分)

1、设p:天下雨，q：天刮风，r：我去书店，则命题“如果天不下雨并且不刮风，我就去书店”的符号化形式为_______________。

2、设F(x)：x是人，G(x)：x用右手写字，命题“有的人并不用右手写字”在一阶逻辑中符号化的形式为______________。

3、p→q的主合取范式为____ ________。

4、设个体域D＝{1,2},那么谓词公式消去量词后的等值式为

。

5、在有向图的邻接矩阵中，第i行元素之和与第j列元素之和分别为________________。

6、设}},2{,1{A，则A的幂集有元素_____________个。

7、设A={a，b}，则A上共有__________个不同的偏序关系。

8、设A={a,b,c}，B={1,2,3}，则A到B共可产生_____________个不同的双射函数。

9、设,,G是群a,bG，则（a-1）-1= 。

10、设A={1, 2, 3}，在A上定义二元运算如下：x,yA, x*y=min{x,y}则*的运算表为___________。

三、计算题(共43分)

1、求((p→q)p)→q的主析取范式（写出过程）。（6分）

2、求公式)(G)(Fyyxx的前束范式。（6分）

得分 阅卷人

得分 阅卷人

8 3、已知无向图G有11条边，2度与3度顶点各2个，其余都是4度顶点，求G中共有几个顶点。（写出过程）(6分)

4、求一棵带权为1，1，1，2，2，3，4，5的最优二元树T，并计算W(T)。(6分)

5、设二元关系R={, <{a}, b>,<{φ}, {φ}>, <{φ}, {φ}>}求：(8分)

（1）domR

（2）ranR

（3）R° R

（4）R-1° R-1

6、设A={a, b, c, d, e, f}, R=IA则R是A上的等价关系，(8分)

(1)求a的等价类[a]R

(2)求c的等价类[c]R

(3)求商集A/R

7、设R’为非零数集。以下各式右边的运算为普通的四则运算。（3分）

(1)a,bR’,ab=a+b

(2)a,bR’,a*b=a/b

(3)a,bR’,ab=a×b

试确定以上三个代数系统中哪些是群，是群的求其单位元。

四、证明题。(本大题共2题，共15分) 得分 阅卷人

装 订 线 内 请 勿 答 题