您的当前位置：首页离散数学复习题(专升本)

离散数学复习题(专升本)

来源：爱go旅游网

《离散数学》复习题（专升本）

一、填空题

1、设

（N：自然数集，E+ 正偶数）则

AB 。

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

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

(P(Q(RP)))(RS)的真值= 。

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

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、下图所示的偏序集中，是格的为。

11、选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A= 。

12、集合A={,{}}的幂集P(A) = 。

13、设A={1，2，3，4}，A上二元关系R={<1，2>，<2，1>，<2，3>，<3，4>}画出R的关系图

。 14、设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>},

则AB= 。

AB= 。

15、设|A|=3，则A上有个二元关系。

16、A={1，2，3}上关系R= 时，R既是对称的又是反对称的。

17、偏序集A,R的哈斯图为

，

则R= 。

18、设|X|=n，|Y|=m则（1）从X到Y有个不同的函数。

（2）当n , m满足时，存在双射有个不同的双射。

19、2是有理数的真值为。 20、Q：我将去上海，R：我有时间，公式(QR)(RQ)的

自然语言为。 21、公式(QP)(PQ)的

主合取范式是。

22、若S{S1 ,S2 ,, Sm}是集合A的一个分划，

则它应满足。

二、选择题

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上的二元关系有（）个。 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图的图是（）

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

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

11、设全集为I，下列相等的集合是（）。 A、A{x|x是偶数或奇数 }； B、B{x| y(yIx2y)}； C、C{x| y(yIx2y1)}； D、D{x|0,1,1,2,2,3,3,4,4,}。12、设S={N，Q，R}，下列命题正确的是（）。 A、2N,NS 则2S； B、NQ,QS 则NS； C、NQ,QR 则NR； D、N,S 则NS。 13、设C={{a},{b},{a,b}}，则S与S分别为（）。SCSCA、C和{a,b}；B、{a,b}与；C、{a,b}与{a,b}；D、C与C 14、下列语句不是命题的有（）。

A、x=13； B、离散数学是计算机系的一门必修课； C、鸡有三只脚；D、太阳系以外的星球上有生物； E、你打算考硕士研究生吗？ 15、(PQ)R的合取范式为（）。

A、(PQ)R ；B、(PR)(QR) ；

4度

10 ）个

C、(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) D、(PQR)(PQR)(PQR)(PQR)。 16、设|A|=n，则A上有（）二元关系。

A、2n ； B、n2 ； C、2n； D、nn ； E、2n。 17、设r为集合A上的相容关系，其简化关系图（如图），

则 [I] r产生的最大相容类为（）；

A、{x1,x2}； B、{x1,x2,x3}； C、{x4,x5}； D、{x2,x4,x5} [II] A的完全覆盖为（）。

A、{x1,x2,x3,x4,x5}； B、{{x1,x2},{x1,x2,x3},{x4,x5}}； C、{{x1,x2,x3},{x2,x4,x5}}； D、{{x1,x2},{x3},{x4,x5}} 。 18、集合A={1，2，3，4}上的偏序关系图为

则它的哈斯图为（）。

19、下列关系中能构成函数的是（）。

A、{x,y|(x,yN)(xy10)}；B、{x,y|(x,yR)(yx2)}； C、{x,y|(x,yR)(y2x)}； D、{x,y|(x,yI)(xymod3)}。 20、N是自然数集，定义f:NN, f(x)(x) mod3（即x除以3的余数），

则f是（）。

A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。三、证明题

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

< a, b> 和在R中有<.b , c>在R中。

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

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

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

面图，则ek(v2)，由此证明彼得森图（Peterson）图是非平面图。 k2４、 1、每一有限全序集必是良序集。

５、 2、设gf是复合函数，如果gf满射，则g也是满射。

四、逻辑推演

一、用CP规则证明下题

1、ABCD,DEFAF 2、x(P(x)Q(x))xP(x)xQ(x)