离散数学模拟习题与解析 (1)

一、填空 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，则

A B C (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= 。

1

143183056.doc

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． {a}{{a}}；

B．{{}}{,{}}；

C． {{},}； D． {}{{}}。 2、下列集合中相等的有（ ）

A．{4，3}；B．{，3，4}；C．{4，，3，3}；D． {3，4}。 3、设A={1，2，3}，则A上的二元关系有（ ）个。

2

143183056.doc

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是对称的； 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图的图是（ ）

3

143183056.doc

10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结

点。

A．1； B．2； C．3； D．4 。

三、证明 26%

１、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当

< a, b> 和在R中有<.b , c>在R中。（8分）

２、f和g都是群到< G2, *>的同态映射，证明是的一个子群。

其中C={x|xG1且f(x)g(x)} (8分)

３、G= (|V| = v，|E|=e ) 是每一个面至少由k（k3）条边围成的连通平面图，

则e

k(v2)， 由此证明彼得森图（Peterson）图是非平面图。（11分）

k2四、逻辑推演 16%

用CP规则证明下题（每小题 8分） 1、ABCD,DEFAF 2、x(P(x)Q(x))xP(x)xQ(x)

五、计算 18%

1、设集合A={a，b，c，d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。 （9分）

4

143183056.doc

2、如下图所示的赋权图表示某七个城市v1,v2,,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （９分）

5

143183056.doc

一、填空 20% （每小题2分）

1、{0，1，2，3，4，6}； 2、(BC)A ；3、1； 4、(PSR)(PSR)； 5、1；6、{<1,1>, <1,3>, <2,2>, <2,4> }；7、{,,,,}  IA ；8、

9、a ；a , b , c ,d ；a , d , c , d ；10、c; 二、选择 20% （每小题 2分）

题目 答案

三、证明 26%

1、 证：

1 C D 2 B、C 3 C 4 A 5 D 6 C

7 A 8 D 9 B 10 A “” a,b,cX 若,  R 由R对称性知,由R传递性得  R

“” 若  R，  R 有  R 任意 a,bX，因  R

 R 所以R是对称的。 若  R   R 即R若  R，  R 则  R b,cR 是传递的。

12、 证a,bC，有 f(a)g(a),f(b)g(b)，又f(b)f1(b),g(b1)g1(b)

f(b1)f1(b)g1(b)g(b1)

f(a★b1)f(a)*f1(b)g(a)*g(b1)g(a★b1)

a★b1C < C , ★> 是 < G1 , ★>的子群。

3、 证：

6

143183056.doc

①设G有r个面，则2ed(F)rkii1r，即 r2e。而 ver2故k2vervek(v2)2e 即得 e。（8分）

k2kk(v2)②彼得森图为k5,e15,v10，这样e不成立，

k2

所以彼得森图非平面图。（3分）

二、 逻辑推演 16% 1、 证明：

①A ②AB

③ABCD ④CD ⑤D ⑥DE ⑦DEF ⑧F ⑨AF 2、证明 ①xP(x) ②P(c)

③x(P(x)Q(x)) ④P(c)Q(c)

P（附加前提） US① P US③

7

P（附加前提） T①I P T②③I T④I T⑤I P T⑥⑦I CP

143183056.doc

⑤Q(c) T②④I ⑥xQ(x)

UG⑤ ⑦xP(x)xQ(x)

CP

三、 计算 18% 1、 解：

010010M10101001R0001 ， M01R2MRMR000 0000000000101M010R3MM1R2R000000001010M01011R4MR3MR0000Mt(R)MRM1R2MR3MR4000000 t (R)={ , , < a , c> , , , < b ,b > , < b , c . > ,

< b , d > , < c , d > }

2、 解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：

树权C(T)=23+1+4+9+3+17=57即为总造价。 8

，

111111001000