离散数学试题十五套.docVIP

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

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

1．设（N：自然数集，E+正偶数）则。

2．A，B，C表示三个集合，文图中阴影部分的集合表达式为

ABC

AB

C

3．设P，Q的真值为0，R，S的真值为1，则

的真值=。

4．公式的主合取范式为

。

5．若解释I的论域D仅包含一个元素，则在I下真值为

。

6．设{1，2，3，4}，A上关系图为

则R2=。

7．设{a，b，c，d}，其上偏序关系R的哈斯图为

则。

8．图的补图为。

9．设{a，b，c，d}，A上二元运算如下：

*

abcd

a

b

c

d

abcd

bcda

cdab

dabc

那么代数系统A，*的幺元是，有逆元的元素为，它们的逆元分别为。

10．下图所示的偏序集中，是格的为。

二、选择20%（每小题2分）

1、下列是真命题的有（）

A．； B．；

C．；D．。

2、下列集合中相等的有（）

A．{4，3}；B．{，3，4}；C．{4，，3，3}；D．{3，4}。

3、设{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、设{1，2，3，4}，P（A）（A的幂集）上规定二元系如下

则P（A）/（）

A．A；B．P(A)；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；

D．{{}，{2}，{2，3}，{{2，3，4}}，{A}}0

6、设{，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（）

7、下列函数是双射的为（）

A．f:,f(x)=2x；B．f:,f(n)=n,1；

C．f:,f(x)=[x]；D．f,f(x)=|x|。

（注：I—整数集，E—偶数集，N—自然数集，R—实数集）

8、图中从v1到v3长度为3的通路有（）条。

A．0； B．1； C．2； D

．3。

9、下图中既不是图，也不是图的图是（）

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

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

三、证明26%

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

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

f和g都是群G1,★到G2,*的同态映射，证明C,★是G1,★的一个子群。其中(8分)

V,E(=v，)是每一个面至少由k（k3）条边围成的连通平面图，则，由此证明彼得森图（）图是非平面图。（11分）

四、逻辑推演16%

用规则证明下题（每小题8分）

1、

2、

五、计算18%

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

2、如下图所示的赋权图表