2011-2012 2 离散数学(A 卷)
高密校区 2011级计专、软专 (答案写在答题纸上,写在试题纸上无效)
一、单项选择题(每小题2分,共20分)
1.下列为两个命题变元p,q的最小项的是( )
A .p∧q∧⎤ p
B .⎤ p∨q
C .⎤ p∧q
D .⎤ p∨p∨q
2.下列语句中是真命题的是( )
A .我正在说谎
B .严禁吸烟
C .如果1+2=3,那么雪是黑的
D .如果1+2=5,那么雪是黑的
3.在公式x ∀F (x ,y )→∃ y G (x ,y )中变元x 是( )
A .自由变元
B .约束变元
C .既是自由变元,又是约束变元
D .既不是自由变元,又不是约束变元
4.集合A={1,2,…,10}上的关系R={(x ,y )|x +y =10,x ∈A ,y ∈A},则R 的性质是(
)
A .自反的
B .对称的
C .传递的、对称的
D .反自反的、传递的
5.设论域为{l ,2},与公式)(x xA ∃等价的是( )
A.A (1)∨A (2)
B. A (1)→A (2)
C.A (1)
D. A (2)→A (1)
6. 下列关系矩阵所对应的关系具有反自反性的是( )
A .⎥⎥⎥⎦⎤
⎢⎢⎢⎣⎡001110101 B .⎥⎥
⎥⎦
⎤
⎢⎢⎢⎣⎡1011000
01
C .⎥⎥⎥⎦⎤
⎢⎢⎢⎣⎡001100100 D .⎥⎥⎥⎦
⎤
⎢⎢⎢
⎣⎡001010101
7. 在自然数集N 上,下列运算是可结合的是( )
A b a b a 2*-=
B .},min{*b a b a =
C b a b a --=*
D b a b a -=*
8..设A 是奇数集合,下列构成独异点的是( )
A.<A ,+>
B.<A ,->
C.<A ,×>
D.<A ,÷> 课程考试试题
学期 学年 拟题人: 校对人
:
拟题学院(系): 适 用 专 业:
拟题学院(系): 高密校区 适用专业: 2011级计专、软专
2011-2012 学年 2学期 离散数学 (A 卷) 试题标准答案
9. 右图的最大入度是( )
A .0
B .1
C .2
D .3
第9题图
10. 设G 为有n 个结点的简单图,则有( )
A .Δ(G)<n
B .Δ(G)≤n
C .Δ(G)>n
D .Δ(G)≥n
二、填空题(每空2分,共20分)
1.设A ={1,2,3,4},B ={2,4,6},则A -B =________,A ⊕B =________。
2.设S 是非空有限集,代数结构(P (S ),∪)中,其中P (S )为集合S 的幂集,则P (S )
对∪运算的单位元是________,零元是________。
3.设f ∶R →R,f(x)=x+3,g ∶R →R,g(x)=2x+1,则复合函数____________))(g (f =x ,
__________________)x )(f (g = 。
4.设有向图G=(V, E ),V={v 1,v 2,v 3,v 4},若G 的邻接矩阵⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎣⎡=0001001111011010A ,则deg -(v 1)=_ ________,deg +(v 4)=____________。
5.给定集合A={1,2,3,4,5},在集合A 上定义两种关系:R={(1,2),(3,4),(2,2)},
S={(4,2),(2,5),(3,1),(1,3)},则_______________S R = ,_______________R S = 。
三、解答题(6个小题,共60分)
1.(10分)设A={1,2,3,6,9,18},≤为整除关系。
(1)画出(A ,≤)的哈斯图;
(2)求子集B={3,6,9}的极大元、极小元、最大元、最小元。
2.(10分)构造命题公式((P ∧Q )→P )∨R 的真值表。
3.(10分)求命题公式A=P →((Q →P )∧(⎤P ∧Q ))的主析取范式和主合取范式。
4.(10分)证明:⎤(A ∧B),B ∨C, ⎤C ⇒⎤A.
5.(10分)设图G 有n 个结点,n +1条边,证明:G 中至少有一个节点度数≥3。
6.(10分)用矩阵的方法求下图中节点u 1,u 5之间长度为2的路的数目。
(答案要注明各个要点的评分标准)
拟 题 人:
书写标准答案人:
一、单项选择题(每小题2分,共20分)1.(C)2. (D);3.(C );4.(B);5. (A) 6.(C)
7. (B);8.(C);9.(D);10. (A).
二、填空题(每空2分,共20分)
1.{1,3},{1,3,6}; 2.Φ, S;
3.2x+7, 2x+4; 4.3,1; 5.{(1,5),(3,2), (2,5)},{(4,2),(3,2), (1,4)}
三、解答题(6个小题,共60分)
1.解:(1) 哈斯图: ……5分
(2)B={3,6,9}的极大元:6,9。
极小元:3。
最大元:无。
最小元:3
……10分
2. P Q P ∧Q P ∧Q →P ((P ∧Q )→P )∨R
1 1 1 1 1 1
1 1 0 1 1 1
1 0 1 0 1 1
1 0 0 0 1 1
0 1 1 0 1 1
0 1 0 0 1 1
0 0 1 0 1 1
0 0 0 0 1 1
………10分
3.解:A= P →((Q →P )∧(⎤P ∧Q ))
=⎤P ∨((⎤Q ∨P )∧(⎤P ∧Q ))
=⎤P ∨((⎤Q ∧⎤P ∧Q )∨(P ∧⎤P ∧Q ))
=⎤P ∨(0∨0)
=⎤P ………5分
所以A 的主析取范式A=⎤P ∧(Q ∨⎤Q )=(⎤P ∧Q )∨(⎤P ∧⎤Q ) ………7分
A 的主合取范式A=⎤P ∨(Q ∧⎤Q )=(⎤P ∨Q )∧(⎤P ∨⎤Q ) ………10分
4.证明: (1)B ∨C P ………1分
(2)⎤C P (1) ………3分 (3)B T (1) (2)I ………5分
(4)⎤(A ∧B) P ………6分
(5)⎤A ∨⎤B T(4)E ………8分
(6)⎤A T (3) (5)I ………10分
5.证明: 设图),(E V G =有n 个节点,,21n v v v 边数为n+1 ………1分
假设任意节点其度数2deg ≤i v ,则n v
n i i 2deg 1
≤∑= ………5分 又因为节点度数总和等于边数两倍,即)1(2deg 1+=∑=n v n
i i ………8分
所以n n 2)1(2≤+,这是个矛盾。
故不可能每个节点度数小于等于2,即至少有一
节点度数大于等于3 ………10分
6.解: 邻接矩阵
⎥⎥
⎥
⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢⎢⎢⎣⎡=0111110001100111010111110A
………4分
⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡
=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=41223
12221
22322
22232
31224
011111000110011
1010111110
01111100011001110101111102A ………8分
所以,图中节点u 1,u 5之间长度为2的路有3条。
………10分。