华东交大离散数学试题一与答案
一、填空
1．设
20% （每小题2分）
A
{x|(x
N)且(x
5)},B
{x|x
E且x
7}（N：自然数
集，E+正偶数）则
A
(B
C)
B
A
{0，1，2，3，4，6} 。
2．A，B，C表示三个集合，文图中阴影部分的集合表达式为
。
A
C B
3．设P，Q 的真值为0，R，S的真值为1，则
(P(Q(RP)))(R
S)的真值= 1 。
4．公式
(PR)(P
(SS
R)R)
P的主合取范式为(P
S
R)xP(x)
。
5．若解释I的论域D仅包含一个元素，则值为
1 。
xP(x)
在I下真
6．设A={1，2，3，4}，A上关系图为则R2 = {<1,1>, <1,3>, <2,2>, <2,4> }
。
7．设A={a，b，c，d}，其上偏序关系R的哈斯图为
R={
。
8．图的补图为
1 / 7
。
9．设A={a，b，c，d} ，A上二元运算如下：
* a b c d a a b c d b b c d a c c d a b d
d
a
b
c
那么代数系统
a , b , c ,d ，它们
的逆元分别为
a , d , c , d 。
10．下图所示的偏序集中，是格的为c 。
二、选择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 / 7
A．2；
3
B．3
2
；
C．2
33
；
D．3
22
。
A）
4、设R，S是集合A上的关系，则下列说法正确的是（A．若R，S 是自反的，则RS是自反的；B．若R，S 是反自反的，
则RS是反自反的；
C．若R，S 是对称的，则RS是对称的；D．若R，S 是传递的，则RS是传递的。
5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下
R
则P（A）/ R=（D）
{s,t|s,tp(A)(|s||t|}
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}，{1，3}，{1，2，3}}则A上包含关系“
”的哈斯图为
6、设A={（C ）
7、下列函数是双射的为（A．f : IC．f : R
E , f (x) = 2x ；I , f (x) = [x] ；
A ）
NN, f (n) =
B．f : ND．f :I
（注：I—整数集，E—偶数集，N—自然数集，R—实数集）8、图中从v1到v3长度为3 的通路有（
D
）条。
A．0；B．1；C．2；D．3。
3 / 7
9、下图中既不是Eular图，也不是Hamilton图的图是（B）
10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（A ）
个4度结点。A．1；
B．2； C．3； D．4 。
三、证明26%
1. R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当< a, b> 和在R中有<.b , c>在R中。（8分）
2.f和g都是群
子群。其中C={x|x
G1且f(x)
g(x)}
(8分)
3.G=
e
k(vk
2)
2，由此证明彼得森图（Peterson）图是非平面图。（11
面图，则分）
四、逻辑推演16%
8分）
用CP规则证明下题（每小题1、A2、
BCD,DEFAF
x(P(x)Q(x))xP(x)xQ(x)
五、计算18%
4 / 7
1、设集合A={a，b，c，d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。
（9分）
2、如下图所示的赋权图表示某七个城市
v1,v2,
,v7及预先算出它们之间的一
些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。
（９分）
三、证明
1、证：
“
26% ” a,b,cX 若 R有 R R由 R对称性知 R，由R传递性得 “ ”若 R若 R， R 任意 a,b X，因 R所以R是对称的。 R b,c R R 若 则 即R是传递的。2、证 f(b) 11 a,bf 1 C(b), ， g(b) 11 有 g(b) 1 f(a)f(b) 1 1 g(a),f(b)f 1 g(b) 1 ， g(b) 1 又 (b) 1 g(b) f(a★b)a★b 1 f(a)*f(b)g(a)*g(b) g(a★b) C < C , ★> 是< G1 , ★>的子群。 3、证： r 2ed(Fi) i1 rk ①设G有r个面，则 2 v e r v e 2ek即得 e ，即 2) 2。（8分） 5 / 7 r 2ek。而v er 2故 k(vk
华东交大离散数学试卷一试题与复习资料
