离散数学试题与答案
离散数学试题一与参考答案
一、填空 20% (每小题2分)
1.设 A ={x |(x ∈N ) 且(x
集,E + 正偶数) 则 A ⋃B = 。
2.A ,B ,C 表示三个集合,文图中阴影部分的集合表达式为
(B ⊕C ) -A +
。
3.设P ,Q 的真值为0,R ,S 的真值为1,则
⌝(P ∨(Q →(R ∧⌝P ))) →(R ∨⌝S )
的真值= 1 。
4.公式(P ∧R ) ∨(S ∧R ) ∨⌝P 的主合取范式为 (⌝P ∨S ∨R ) ∧(⌝P ∨⌝S ∨R ) 。
5.若解释I 的论域D 仅包含一个元素,则 ∃xP (x ) →∀xP (x ) 在I 下真值为 1 。
6.设A={1,2,3,4},A 上关系图为 则 R 2。
7.设A={a,b ,c ,d},其上偏序关系R 的哈斯图为
则 。
8.图的补图为
。
9.设A={a,b ,c ,d} ,A 上二元运算如下:
那么代数系统,它们的逆元分别为 a , d , c , d 。
10.下图所示的偏序集中,是格的为 。
二、选择 20% (每小题 2分)
1、下列是真命题的有(C D ) A . {a }⊆{{a }};
B .{{Φ}}∈{Φ, {Φ}};
C . Φ∈{{Φ},Φ}; D . {Φ}∈{{Φ}}。 2、下列集合中相等的有( B 、C )
A .{4,3}⋃Φ; B .{Φ,3,4}; C .{4,Φ,3,3}; D . {3,4}。
3、设A={1,2,3},则A 上的二元关系有( C )个。
2⨯2
A . 23 ; B . 32 ; C . 23⨯3; D . 3。
4、设R ,S 是集合A 上的关系,则下列说法正确的是(A ) A .若R ,S 是自反的, 则R S 是自反的; B .若R ,S 是反自反的, 则R S 是反自反的; C .若R ,S 是对称的, 则R S 是对称的; D .若R ,S 是传递的, 则R S 是传递的。
5、设A={1,2,3,4},P (A )(A 的幂集)上规定二元系如下
R ={|s , t ∈p (A ) ∧(|s |=|t |}
则P (A )/ R=( D )
A .A ; B .P(A) ;
C .{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}}}; D .{{Φ},{2},{2,3},{{2,3,4}},{A}}
6、设A={Φ,{1},{1,3},{1,2,3}}则A 上包含关系“⊆”的哈斯图为( C )
7、下列函数是双射的为( A )
A .f : I→E , f (x) = 2x ; B .f : N→N ⨯N, f (n) = ; C .f : R→I , f (x) = [x] ; D .f :I→N, f (x) = | x | 。 (注:I —整数集,E —偶数集, N —自然数集,R —实数集) 8、图 中 从v 1到v 3长度为3 的通路有( D )条。
A . 0; B . 1; C . 2; D . 3。
9、下图中既不是Eular 图,也不是Hamilton 图的图是(B )
10、在一棵树中有7片树叶,3个3度结点,其余都是4度结点则该树有( A )
个4度结点。
A .1; B .2; C.3; D.4 。
三、证明 26%
1. R是集合X 上的一个自反关系,求证:R 是对称和传递的,当且仅当 和在R 中有在R 中。(8分)
证:“⇒” ∀a , b , c ∈X 若, ∈ R 由R 对称性知
“⇐” 若 ∈ R , ∈ R 有 ∈ R 任意 a , b ∈X ,因
若 ∈ R , ∈ R 则 ∈ R ∧∈R ∴ ∈ R 即R 是传递的。
3. G= (|V| = v ,|E|=e ) 是每一个面至少由k (k ≥3)条边围成的连通平面图,则
, 由此证明彼得森图(Peterson )图是非平面图。(11
1、A ∨B →C ∧D , D ∨E →F ⇒A →F 2、∀x (P (x ) →Q (x )) ⇒∀xP (x ) →∀xQ (x )
1、设集合A={a,b ,c ,d}上的关系R={ , , , }用矩阵运算求出R 的传递闭包t (R)。 (9分)
2、如下图所示的赋权图表示某七个城市v 1, v 2, , v 7及预先算出它们之间的一些直接通信线路造价,试给出一个设计方案,使得各城市之间能够通信而且总造价最小。 (9分)
“⇒” ∀a , b , c ∈X 若, ∈ R 由R 对称性知
“⇐” 若 ∈ R , ∈ R 有 ∈ R 任意 a , b ∈X ,因
若 ∈ R , ∈ R 则 ∈ R ∧∈R ∴ ∈ R 即R 是传递的。 2、证
f (a ) =g (a ), f (b ) =g (b )
) =f (a ) *f (b ) =g (a ) *g (b ) =g (a
a) 证明: ①A ②A ∨B ③A ∨B →C ∧D ④C ∧D ⑤D ⑥D ∨E ⑦D ∨E →F ⑧F 2、证明 ①∀xP (x ) ②P (c )
③∀x (P (x ) →Q (x )) ④P (c ) →Q (c ) ⑤Q (c ) ⑥∀xQ (x )
∴ t (R)={ , , , , , , ,
, }
2. 解: 用库斯克(Kruskal )算法求产生的最优树。算法略。结果如图:
树权C(T)=23+1+4+9+3+17=57即为总造价。