[离散数学]期末试题及答案

326《离散数学》期末考试题(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. 设D 24={1, 2, 3, 4, 6, 8, 12, 24}，对于其上的整除关系“|”，元素( ) 不存在补元. 5. 当n ( ) 时，n 阶完全无向图K n 是平面图，当当n 为( ) 时，K n 是欧拉图. 二．1. 若|A |=m , |B |=n ，则|A ⨯B |=( ) ，A 到B 的2元关系共有( ) 个，A 上的2元关系共有( ) 个.

2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( ) 是单射，( ) 是满射，( ) 是双射.

3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)p ∧(p →q ) →q ； (2)p →(p ∨q ) ； (3)p →(p ∧q ) ； (4)⌝p ∧(p ∨q ) →q ； (5)(p →q ) →q .

4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( ) ，4的补元( ) ，6的补元( ).

5. 设G 是(7, 15)简单平面图，则G 一定是( ) 图，且其每个面恰由( ) 条边围成，G 的面数为( ).

三．1. 设A ={{a , b },{c }}，B ={{a },{b , c },{c }}，则A ⋃B =(

) ，

A ⋂B =() ，P (A ) =() .

2. 集合A ={a , b , c }，其上可定义( ) 个封闭的1元运算，( ) 个封闭的2元运算，( ) 个封闭的3元运算.

3. 命题公式(p ∧q ) ↑1的对偶式为( ). 4. 所有6的因数组成的集合为( ). 5. 不同构的5阶根树有( ) 棵.

四、(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 的关系图G R . 2. 判断R 所具有的性质. 3. 求出R 的关系矩阵M R .

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

和主合取范式.

七、(10分) 边数m

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

一、1. {{a , b }, a , b , ∅}， {{a , b }, a , b }，16.

2. 2, 27.

3. P (x ) →Q (x ) , Q (y ) ∧⌝P (y ) . 4. 2, 4, 6, 12. 5. ≤4，奇数. 二、1. mn , 2m n , 2m .

2. g , g , g .

2

9

3.1,2,4.

4.8，不存在，不存在. 5. 连通，3，10.

三、1. A ⋃B ={{a },{a , b },{b , c },{c }}，A ⋂B ={{c }}，P (A ) ={∅, {{a , b }}, {{c }}, {{a , b }, {c }}}.

2. 33, 39, 327. 3. (p ∨q ) ↓0.

4. {-1，-2，-3，-6，1，2，3，6}. 5.9.

四、证 对于任意x , y ∈A ，若f (x ) =f (y ) ，则g (f (x )) =g (f (y )) ，(f g )(x ) =(f g )(y ) . 由于f g 是单射，因此x =y ，于是f 是单射.

例

如

取

A ={a , b },B =(1, 2, 3},C ={α, β, γ}，令f ={(a , 1), (b , 2)}g ={(1, α), (2, β), (3, β)}，这时f g ={(a , α), (b , β)}是单射，而g 不是单射.

五、解 1. R 的关系图G R 如下：

2.(1)由于(b , b ) ∉R ，所以R 不是自反的. (2)由于(a , a ) ∈R ，所以R 不是反自反的.

(3)因为(d , b ) ∈R ，而(b , d ) ∉R ，因此R 不是对称的. (4)因(a , c ), (c , a ) ∈R ，于是R 不是反对称的.

即

，

(5)经计算知R R ={(a , a ), (a , b ), (a , c ), (c , a ), (c , b ), (c , c ), (d , a ), (d , c )}⊆R ，进而R 是传递的.

综上所述，所给R 是传递的.

⎛1 0

3. R 的关系矩阵M R =

1 1⎝

10111011

0⎫⎪0⎪. 0⎪⎪0⎪⎭

六、解 命题公式A =(p →(q →r )) (r →(q →p )) 的真值表如下:

由表可知，A =(p →(q →r )) (r →(q →p )) 的主析取范式为

A =(p ∧q ∧r ) ∨(p ∧⌝q ∧r ) ∨(p ∧⌝q ∧⌝r ) ∨(⌝p ∧q ∧⌝r )

∨(⌝p ∧⌝q ∧r ) ∨(⌝p ∧⌝q ∧⌝r ).

A 的主合取范式为A =(⌝p ∨⌝q ∨r ) ∧(p ∨⌝q ∨⌝r ) .

七、证 不妨设G 的阶数n ≥3，否则结论是显然的. 根据推论1知，m ≤3n -6. 若G 的任意节点v 的度数均有deg(v ) ≥5，由握手定理知

2m =∑deg(v ) ≥5n .

v

于是n ≤

22

m ，进而m ≤3n -6≤3⋅m -6. 因此m ≥30，与已知矛盾. 所以必存在55

节点v 使得deg(v ) ≤4.

八、解 设满足要求的r 位数的个数有a r 种，r = 0，1，2，…，则排列计数生成函数

⎛x 2x 3⎫⎛x 2⎫E (x ) = 1+x +2! +3! ⎪⎪ 1+x +2! ⎪⎪(1+x )

⎝⎭⎝⎭

=1+3x +4x 2+

因而a 4=

1931941516

x +x +x +x , 612212

19

⋅4! =38. 12