每周十题十五套及答案
离散数学试题与答案试卷一
一、填空20% (每小题2分)
?1.设 A?{x|(x?N)且(x?5)},B?{x|x?E且x?7}(N:自然数集,E+ 正偶
数)则 A?B? 。
2.A,B,C表示三个集合,文图中阴影部分的集合表达式为
。
3.设P,Q 的真值为0,R,S的真值为1,则
?(P?(Q?(R??P)))?(R??S)的真值= 。
4.公式(P?R)?(S?R)??P的主合取范式为
。
5.若解释I的论域D仅包含一个元素,则 ?xP(x)??xP(x) 在I 下真值为。
6.设A={1,2,3,4},A上关系图为
则 R2 = 。
7.设A={a,b,c,d},其上偏序关系R的哈斯图为
则 R= 。
8.图的补图为。
9.设A={a,b,c,d} ,A上二元运算如下:
那么代数系统的幺元是,它们的逆元分别为。
10.下图所示的偏序集中,是格的为。
二、选择 20% (每小题 2分)
1、下列是真命题的有()
A. {a}?{{a}}; B.{{?}}?{?,{?}};
C. ??{{?},?}; D. {?}?{{?}}。
2、下列集合中相等的有()
A.{4,3}??;B.{?,3,4};C.{4,?,3,3};D.
3、设A={1,2,3},则A上的二元关系有()个。
A. 23 ; B. 32 ;C. 23?3; D. 32?2。
4、设R,S是集合A上的关系,则下列说法正确的是() A.若R,S 是自反的,则R?S是自反的;
B.若R,S 是反自反的,则R?S是反自反的;
C.若R,S 是对称的,则R?S是对称的;
{3,4}。
D.若R,S 是传递的,则R?S是传递的。
5、设A={1,2,3,4},P(A)(A的幂集)上规定二元系如下
R?{?s,t?|s,t?p(A)?(|s|?|t|}则P(A)/ R=()
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上包含关系“?”的哈斯图为()
7、下列函数是双射的为()
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、图中从v1到v3长度为3 的通路有()条。
A. 0; B. 1; C. 2; D. 3。
9、下图中既不是Eular图,也不是Hamilton图的图是()
10、在一棵树中有7片树叶,3个3度结点,其余都是4度结点则该树有()个4
度结点。
A.1; B.2; C.3; D.4 。
三、证明 26%
1、R是集合X上的一个自反关系,求证:R是对称和传递的,当且仅当
< a, b> 和在R中有在R中。(8分)
2、f和g都是群到< G2, *>的同态映射,证明是的一个子
群。其中C={x|x?G1且f(x)?g(x)} (8分)
3、G= (|V| = v,|E|=e ) 是每一个面至少由k(k?3)条边围成的连通平面图,则
e?k(v?2)k?2,由此证明彼得森图(Peterson)图是非平面图。(11分)
四、逻辑推演 16%
用CP规则证明下题(每小题 8分)
1、A?B?C?D,D?E?F?A?F
离散数学试题与答案试卷一
3、设A={1,2,3},则A上的二元关系有( c )个。
A. 23 ; B. 32 ;C. 2
3?3
2?2
; D. 3。
5、设A={1,2,3,4},P(A)(A的幂集)上规定二元系如下
R?{?s,t?|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}}
试卷二试题与答案
1、设S={a1 ,a2 ,?,a8},Bi是S的子集,则由B31所表达的子集是 6、设 ?,? 为普通加法和乘法,则( a )?S,?,??是域。A.S?{x|x?a?b3,C.S?{x|x?2n?1,
a,b?Q}B.S?{x|x?2n,a,b?Z}
n?Z} D.S?{x|x?Z?x?0}= N 。
1、设R是A上一个二元关系,
S?{?a,b?|(a,b?A)?(对于某一个c?A,有?a,c??R且?c,b??R)}试证
明若R是A上一个等价关系,则S也是A上的一个等价关系。(9分)
一、证明 46%
1、(9分)
(1) S自反的
?a?A,由R自反,?(?a,a??R)?(?a,a??R),??a,a??S
(2) S对称的
?a,b?A
?a,b??S?(?a,c??R)?(?c,b??R)
?(?a,c??R)?(?c,b??R)??b,a??S
(3) S传递的
?S定义?R对称?R传递
?a,b,c?A
?a,b??S??b,c??S
?(?a,d??R)?(?d,b??R)?(?b,e??R)?(?e,c??R)?(?a,b??R)?(?b,c ??R)??a,c??S
由(1)、(2)、(3)得;S是等价关系。
?R传递?S定义
试卷三试题与答案
一、选择 20% (每小题 2分)
1、设
R
和
S
是
P
上的关系,P
是所有人的集合,
R?{?x,y?|x,y?P?x是y的父亲},S?{?x,y?|x,y?P?x是y的母亲} 则S
?1
?R表示关系(a)。