离散数学练习题.doc

离散数学练习题(一)
一、填空 20% (每小题2分)
A B
C
(N:自然数集,E+ 正偶数) 则{0,1,2,3,4,6} 。
,B,C表示三个集合,文图中阴影部分的集合
表达式为。
,Q 的真值为0,R,S的真值为1,则
的真值= 1 。
。
,
则在I下真值为 1 。
={1,2,3,4},A上关系图为
则 R2 = {<1,1>, <1,3>, <2,2>, <2,4> } 。
={a,b,c,d},其上偏序关系R的哈斯图为
则 R= {<>,<a,c>,<a,d>,<b,d>,<c,d>} IA 。
。
={a,b,c,d} ,A上二元运算如下:
*
a b c d
a
b
c
d
a b c d
b c d a
c d a b
d a b c
那么代数系统<A,*>的幺元是 a ,有逆元的元素为 a , b , c ,d ,它们的逆元分别为 a , b , c ,d 。
二、选择 20% (每小题 2分)
1、下列是真命题的有( C D )
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 )个。
A. 23 ; B. 32 ; C. ; D. 。
4、设R,S是集合A上的关系,则下列说法正确的是( A )
,S 是自反的, 则是自反的;
,S 是反自反的, 则是反自反的;
,S 是对称的, 则是对称的;
,S 是传递的, 则是传递的。
5、设A={1,2,3,4},P(A)(A的幂集)上规定二元系如下
则P(A)/ R=( D )
; (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 )
: IE , f (x) = 2x ; : NNN, f (n) = <n , n+1> ;
: RI , f (x) = [x] ; :IN, f (x) = | x | 。
(注:I—整数集,E—偶数集, N—自然数集,R—实数集)
8、图中从v1到v3长度为3 的通路有( D )条。
A. 0; B. 1; C. 2; D. 3。
9、下图中既不是Eular图,也不是Hamilton图的图是( B )
10、在一棵树中有7片树叶,3个3度结点,其余都是4度结点则该树有( A )个4度结点。 ; ; ; 。
三、证明 26%
R是集合X上的一个自反关系,求证:R是对称和传递的,当且仅当
< a, b> 和<a , c>在R中有<.b , c>在R中。(8分)
证:“”若由R对称性知,由R传递性得“”若,有任意,因若所以R是对称的。若, 则即R是传递的。
f和g都是群<G1 ,★>到< G2, *>的同态映射,证明<C , ★>是<G1, ★>的一个子群。其中C= (8分)
证,有,又
★★
★< C , ★> 是< G1 , ★>的子群。
四、逻辑推演 16%
用CP规则证明下题(每小题 8分)
1、
证明:
① P(附加前提)
② T①I
③ P
④ T②③I
⑤ T④I
⑥ T⑤I
⑦ P
⑧ T⑥⑦I
⑨ CP
2、
证明
① P(附加前提)
② US①
③ P
④ US③
⑤ T②④I
⑥ UG⑤
⑦ CP
五、计算 18%
1、设集合A={a,b,c,d}上的关系R={<a , b > ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。(9分)
解: ,
t (R)={<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c , d > }
离散数学练习题(二)
一、填空 20% (每小题2分)
P:你努力,Q:你失败。“除非你努力,否则你将失败”的翻译为;“虽然你努力了,但还是失败了”的翻译为。
P (1,1)
P (1,2