《离散数学》期末考试题(B)

《离散数学》期末考试题(B)

《离散数学》期末考试题(B)

一、填空题(每小题3分，共15分)

1.设A {{a,b},a,b, }，则A = ( )，A { } = ( )，P(A)中的元素个数|P(A)| ( ).

2.设集合A中有3个元素，则A上的二元关系有( )个，其中有( )个是A到A的函数.

3.谓词公式 x(P(x) Q(x)) y(Q(y) P(y))中量词 x的辖域为

( ), 量词 y的辖域为( ).

4.设D24 {1,2,3,4,6,8,12,24}，对于其上的整除关系“|”，元素( )不存在补元.

5.当n( )时，n阶完全无向图Kn是平面图，当当n为( )时，Kn是欧拉图.

二、单选题(每小题3分，共15分)

1.设R是集合A上的偏序关系，R 1是R的逆关系，则R R是A上的 1

(A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立

2.由2个命题变元p和q组成的不等值的命题公式的个数有

(A)2 (B)4 (C)8 (D)16

3.设p是素数且n是正整数，则任意有限域的元素个数为

pn(A)p n (B)pn (C)p (D)n

4.设R是实数集合， 是其上的小于等于关系，则(R, )是

(A)有界格 (B)分配格 (C)有补格 (D)布尔格

5.3阶完全无向图K3的不同构的生成子图有

(A)2 (B)3 (C)4 (D)5

三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.

1.若一个元素a既存在左逆元al，又存在右逆元ar，则al ar. ( )

2.命题联结词→不满足结合律. ( )

3.在Z8 = {0，1，2，3，4，5，6，7}中，2关于“ 8”的逆元为4. ( )

4.整环不一定是域. ( )

《离散数学》期末考试题(B)

5.任何(n,m)平面图的面数r m n 2. ( )

四、(10分)设f:A B且g:B C，若f g是单射，证明f是单射，并举例说明g不一定是单射.

五、(15分)设A {a,b,c,d},A上的关系

R {(a,a),(a,b),(a,c),(c,a),(c,b),(c,c),(d,a),(d,b),(d,c)},

1.画出R的关系图GR.

2.判断R所具有的性质.

3.求出R的关系矩阵MR.

六、(10分)利用真值表求命题公式A (p (q r)) (r (q p))的主析取范式和主合取范式.

七、(10分) 边数m 30的简单平面图G，必存在节点v使得deg(v) 4.

八、(10分) 有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数.