离散数学期末复习

离散数学期末复习离散数学期末复习离散数学期末复习资料仅供参考文件编号：2022年4月离散数学期末复习版本号：A修改号：1页次：1.0审核：批准:发布日期：离散数学期末复习一、选择题下列各选项错误的是A、

B、

C、

{

}D、

{

}2、命题公式

(p∧q)

→p

是A、矛盾式

B、重言式C、可满足式

D、等值式3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是

A、等价关系B、偏序关系

C、全序关系D、都不是4、下列句子中那个是假命题？

A、是无理数.

B、2+5

＝8.

C、x

+5

＞

3

D、请不要讲话！5、下列各选项错误的是？

A、

B、

{

}

C、

{

}D、{

}

6、命题公式

p→（pqr）是？

A、重言式B、矛盾式

C、可满足式

D、等值式7、函数f:N→N,f(x)=x+5,函数f是A、单射B、满射C、双射D、都不是8、设D=<V,E>,则V={a,b,c,d,e,f},R={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>},有向图D为A、强连通B、单向连通C、弱连通

D、不连通的9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是A、R1

R2B、R1-1C、R1

R2

D、R1

-R210、连通平面图G有4个结点，3个面，则G有（

）条边。A、7B、6C、5D、4二、填空题1、将下面命题符号化。设

p:天冷，q:小王穿羽绒服。

只要天冷，小王就穿羽绒服.符号化为

2、将下面命题符号化，设

p:天冷，q:小王穿羽绒服。因为天冷，所以小王穿羽绒服.

符号化为

3、将下面命题符号化，设

p:天冷，q:小王穿羽绒服。若小王不穿羽绒服，则天不冷.符号化为4、将下面命题符号化，设

p:天冷，q:小王穿羽绒服。只有天冷，小王才穿羽绒服.符号化为

5、将下面命题符号化，设

p:天冷，q:小王穿羽绒服。除非天冷，小王才穿羽绒服.符号化为

6、将下面命题符号化，设

p:天冷，q:小王穿羽绒服。除非小王穿羽绒服，否则天不冷.符号化为

7、将下面命题符号化，设

p:天冷，q:小王穿羽绒服。小王穿羽绒服仅当天冷的时候.符号化为

8、将下面命题符号化，设

p:天冷，q:小王穿羽绒服。如果天不冷，则小王不穿羽绒服.符号化为

9、设p:王蓉努力学习，q：王蓉取得好成绩。则（1）命题“只要王蓉努力学习，她就会取得好成绩。”符号化为

。（2）命题“王蓉取得好成绩，如果她努力学习。”符号化为

。（3）命题“只有王蓉努力学习，她才能取得好成绩。”符号化为

。（4）命题“除非王蓉努力学习，否则她不能取得好成绩。”符号化为

。（5）命题“假如王蓉不努力学习，她就不能取得好成绩。”符号化为

。（6）命题“王蓉取得好成绩，仅当她努力学习了。”符号化为

。10、公式∀xF(x)→∃xF(x)的类型为

11、公式∀xF(x)→(∀x∃yG(x,y)→∀xF(x))的类型为

12、公式∀xF(x)→(∀xF(x)∨∃yG(y))的类型为

13、公式(F(x,y)→R(x,y))∧R(x,y)的类型14、公式∀x∃yF(x,y)→∃x∀yF(x,y)的类型为

15、公式∃xF(x,y)的类型16、令F(x)：x是人，G(x)：x犯错误.则命题“没有不犯错误的人”符号化为

17、令F(x)：x是人，G(x)：爱看电影.则命题“不是所有的人都爱看电影”符号化为

18、公式x(M(x)F(x))的前束范式为：

19、公式xF(x)xG(x)的前束范式为：

20、公式xF(x)xG(x)的前束范式为

21、公式xF(x)y(G(x,y)H(y))的前束范式为

22、公式x(F(x,y)y(G(x,y)H(x,z)))的前束范式为

23、集合A=Ø,B={1,{a,b}},C={Ø,{Ø}},D={2,2,2,3};则幂集P(A)=

;P(B)=

;P(C)=

;P(D)=

;24、设A={1,2,3},

B={a,b,c}则

AB=

；BA

=

。25、设集合A={},

则P(A)A=

。26、设|A|=n,则|A×A|=

,

A×A的子集有

个.

集合A上有

个不同的二元关系.27、设A={1,2},

则EA=

；IA=

。28、集合A={2，3，4，5，6，10，12，24}，R是A上的整除关系，则R的极大元是

，极小元是

。29、设A={1，2，3}上的关系

R={<1，1>，<1，2>，<1，3>，<3，3>}

，则关系R具备

性质。30、设集合A={1,2,3},关系R={<1,2>,<2,1>,<2,3>，<3,3>},

则自反闭包r(R)=

,

对称闭包s(R)=

。31、已知图G有10条边,4个3度顶点,

其余顶点的度数均小于等于2,

问G至少有

个顶点。32、n阶无向完全图Kn，边数m=

。33、n阶有向完全图Kn，边数m=

。34、设无向图

G

有

10

条边,3

度与

4

度顶点各

2

个,

其余顶点的度数均小于3,

则G

中至少有

个顶点，在最少顶点的情况下,

图G

的度数列

，⊿(G)=

,

(G)=

.35、设无向图中有6

条边,3

度与

5

度顶点各一个,

其余的都是

2

度顶点,则该图有

个顶点。36、已知n阶连通平面图G有r个面，则G的边数m=

。37、设A={1，2，3}上的关系

R={<1，2>，<2，3>，<3，1>}

，则RR=

。38、

设F(x)：x是兔子，M(x)：y是乌龟，H(x,y):x比y跑得快,则命题“兔子比乌龟跑得快”符号为

三、计算题1、给出公式A=(qp)

qp的真值表。给出公式A=(qp)

qp的真值表。给出公式C=(pq)

r的真值表用等值演算法判断公式

q(pq)的类型求公式A=(pq)r的析取范式与合取范式。求公式B=(pq)r的析取范式与合取范式。求公式

A=(pq)r的主析取范式与主合取范式.8、在一阶逻辑中将下面命题符号化(1)

人都爱美;

(2)

有人用左手写字分别取(a)

D为人类集合,

(b)

D为全总个体域

.9、在一阶逻辑中将下面命题符号化(1)

正数都大于负数10、在一阶逻辑中将下面命题符号化(1)

有的无理数大于有的有理数11、试画出4阶3条边的所有非同构的无向简单图12、画出所有K4的所有非同构的生成子图。

13、给定下面的图(前两个为无向图,

后两个为有向图)的集合表示,

画出它们的图形表示G1

=

V1,

E1,

其中,

V1

=

{v1,

v2,

v3,

v4,

v5},

E1

=

{(v1,

v2),

(v2,

v3),

(v3,

v4),(v3,

v3),

(v4,

v5)};G2

=

V2,

E2,

其中

V2

=

V1,

E2

={(v1,

v2),

(v2,

v3),

(v3,

v4),

(v4,

v5),

(v5,

v1)};D1

=

V3,

E3,

其中

V3

=

V1,

E3

=

{v1,

v2,

v2,

v3,

v3,

v2,

v4,

v5,

v5,

v1};

D2

=

V4,

E4,

其中

V4

=

V1,

E4

=

{v1,

v2,

v2,

v5,

v5,

v2,

v3,

v4,

v4,

v3}.14、先将图中各图的顶点标定顺序,

然后写出各图的集合表示.15、写出图中各图的度数列,

对有向图还要写出出度列和入度列.16、画一个简单无向图，使它是欧拉图，但不是哈密顿图。17、已知集合A={a,

b,

c,

d,

e,

f}和关系R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>

}∪IA，请画出偏序集<A,R>的哈斯图。18、设A={a,b,c,d},R={<a,a>,<a,b>,<a,c>,<b,a>,<d,b>},求R的关系矩阵

MR

和关系图

GR。19、有向图D如图