DOC《离散数学试题与答案试卷一》

离散数学试题与答案试卷一

一、填空 20% (每小题2分) 1.

设(N:自然数集,E+ 正偶数) 则.2.A,B,C表示三个集合,文图中阴影部分的集合表达式为 . 3.设P,Q 的真值为0,R,S的真值为1,则 的真值= 4.公式的主合取范式为 . 5.若解释I的论域D仅包含一个元素,则在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上二元运算如下: * a b c d a b c d a b c d b c d a c d a b d a b c 那么代数系统的幺元是 ,有逆元的元素为 ,它们的逆元分别为 . 10.下图所示的偏序集中,是格的为 .

二、选择 20% (每小题 2分)

1、下列是真命题的有( ) A.B.;

C.D. .

2、下列集合中相等的有( ) A.{4,3};

B.{,3,4};

C.{4,,

3,3};

D. {3,4}.

3、设A={1,2,3},则A上的二元关系有( )个. A.

23 ;

B.

32 ;

C. ;

D. .

4、设R,S是集合A上的关系,则下列说法正确的是( ) A.若R,S 是自反的, 则是自反的;

B.若R,S 是反自反的, 则是反自反的;

C.若R,S 是对称的, 则是对称的;

D.若R,S 是传递的, 则是传递的.

5、设A={1,2,3,4},P(A)(A的幂集)上规定二元系如下 则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 : IE , f (x) = 2x ;

B.f : NNN, f (n) = ;

C.f : RI , f (x) = [x] ;

D.f :IN, 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% R是集合X上的一个自反关系,求证:R是对称和传递的,当且仅当 <

a, b>

和在R中有在R中.(8分) f和g都是群到<

G2, *>

的同态映射,证明是的一个子群.其中C= (8分) G= (|V| = v,|E|=e ) 是每一个面至少由k(k3)条边围成的连通平面图,则, 由此证明彼得森图(Peterson)图是非平面图.(11分)

四、逻辑推演 16% 用CP规则证明下题(每小题 8分)

1、

2、

五、计算 18%

1、设集合A={a,b,c,d}上的关系R={ ,<

b , a >

,<

b, c >

, <

c , d >

}用矩阵运算求出R的传递闭包t (R)9分)

2、如下图所示的赋权

图表示某七个城市及预先算出它们之间的一些直接通信线路造价,试给出一个设计方案,使得各城市之间能够通信而且总造价最小. (9分) 试卷一答案:

一、填空 20% (每小题2分)

1、{0,1,2,3,4,6};

2、;

3、1;

4、;

5、1;

6、{, , , };

7、{,,

,,

} IA ;

8、

9、a ;

a , b , c ,d ;

a , d , c , d ;

10、c;

二、选择 20% (每小题 2分) 题目

1 2

3 4

5 6

7 8

9 10 答案 C D B、C C A D C A D B A

三、证明 26% 证: 若由R对称性知,由R传递性得 若,有 任意 ,因若 所以R是对称的. 若, 则即R是传递的. 证,有 ,又 <

C , >

是的子群. 证: ①设G有r个面,则,即 .而 故即得 .(8分) ②彼得森图为,这样不成立, 所以彼得森图非平面图.(3分) 逻辑推演 16% 证明: ① P(附加前提) ② T①I ③ P ④ T②③I ⑤ T④I ⑥ T⑤I ⑦ P ⑧ T⑥⑦I ⑨ CP

2、证明 ① P(附加前提) ② US① ③ P ④ US③ ⑤ T②④I ⑥ UG⑤ ⑦ CP 计算 18% 解: , , t (R)={ , , <