PAGE / NUMPAGES

贵州大学信息学院计算机专业2004级《离散数学》试卷 A

姓名 学号 班级 得分

一、判断题(每题1分，共10分)

1、在命题逻辑中，任何公式都存在与之等值的主合取和主析取范式，并且是唯一。( )

2、设是交换群，则G的所有子群是正规子群。( )

3、设

为偏序集，?1SíP，若S有上界，则S必有上确界。

4、设R为二元关系，A是集合，则R在A上的限制是R的子关系。( )

5、图G是树则G是连通的且G中任意两顶之间有不只一条路径。( )

6、对于任意非空集合A，P(A)—是A的一个划分。( )

7、任给函数F，它的逆F-1一定是函数。( )

8、不是封闭公式在任何解释下都变成命题。( )

9、R=

10、非负整数列(4，4，3，3，2，2)可简单图画。( )

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

1、设集合A={，a}，则P(A)A= 。

2、公式x F(x,y)→x G(x,y)等值的前束范式为 。

3、R是集合A上的等价关系，A={a,b,c,d}，R={,,},g是集合A到集合A/R 的自然映射，即g：AA/R。则g(a)= ，

g(d)= 。

4、在全总个体域中，设F(x)：x是人，G(x，y)：x与y一样高，命题“所有人都不一样高”符号化： 。

5、有一公式为：,该公式的类型_________________。

6、已知n阶无向简单图G有m条边，则G的补图G有__________条边。

7、设σ=(1345)(2678)是8元置换，则σ-1=___________。

8、n阶零图G的连通分支数P(G)= 。

9、已知f:RR,f(x)=2x+1,g:RR,g(x)=x2 +3x+1,则fg=_____________;

gf=_______________________。

10、设代数系统V=(Q,*)，其中Q是有理数集合，*表示对x，y∈Q有x*y=x+y-xy，则Q上关于*的幺元(或称单位元)是_________。

11、含n个命题变项的重言式的主合取范式为________________________。

12、在命题逻辑中，设p: 小明从筐中拿一个苹果，q: 小明从筐中拿一个梨子，r: 我去书店，则命题“如果小明只能从筐中拿一个苹果或一个梨子，那么我就去书店”的符号化形式为______________ _。

13、设G={e,a,b,c}是Klein四元群，H={e,b}是G的子群，则H的所有的右陪集是：

。

14、彼得松图(10阶3-正侧图)中，边数m= 。

15、根树T中，有一个顶点的入度为 ，其余的顶点的入度为 。

三、解答计算题

1、求公式((pq)批)r的主析取范式和主合取范式，并给出公式的成真赋值和成假赋值(6分)

2、构造一棵权为2,2,3,4,5,6,6,7的最优二叉树并计算树的权W(T)。

3、设G=是12阶循环群。求出(1)G的所有生成元。(2)G的所有子群。

4、如图示，是偏序集的哈斯图。(1)该偏序集是否是格，为什么？(2)分别给出集合A和偏序关系《 的集合表达式。(3)求集合A和A的子集B={a,d,e,f}的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界。(10分)

5、设A={a,b,c,d,e,f}，R={,,}是A上的关系,(1)求R′=tsr(R)。(2) R′是A上的等价关系,求A/R。(3)给出R′的关系矩阵和关系图。

6、无向树T有8片树叶，2个3度的分支点，其余的分支点都是4度顶点。(1)问T有几个顶点？(2)根据T的度数列，画出2棵非同构的无向树。

7、判断下列一阶公式的公式类型。

8、设代数系统V=< Z6, >，Z6={0,1,...,5}，为模6乘法。(1)给出运算

的运算表。(2)求出所有可逆元素关