2020-2021大学《离散数学》期末课程考试试卷A1（含答案）

10.下列各图是欧拉图的是（)

2020-2021《离散数学》期末课程试卷A1

专业：考试日期：时间:总分：分闭卷

二大题：填空题（共10空，每空2分，共20分）

一大题：选择题（共10小题，每小题2分，共20分）1.“如果雪是黑的，太阳从西边出”是命题。

2.集合A={1,2,3}上的二元关系R具有对称性，反对称性，自反性，则

I.下列是两个命题变元P，Q的小项是()

R二o

A.PA-iPAQB.-IPVQC.-|PAQD.-|PVPVQ

3.设R是实数集，在R上定义二元运算*为a*b=a+b+a-b,其中+和­是数的加法和乘法,

2.令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为

则代数系统＜R,*〉的幺元是，3的逆元是o

()A.P-1QB.PV-|Q

4.对称关系具有性和性。

C.PAQD.PA-iQ

5.无向图G具有一条欧拉回路，当且仅当G是,并且所有结点的度数都是。

3.下列等值式不正确的是()

6.在下图中，度数为3的结点有个，出度为2的结点有个。

A.-|(Vx)A<=>(3x)-|A

B.(Vx)(B-*A(x))(Vx)A(x)

C.(3x)(A(x)AB(x))<=>(3x)A(x)A(3x)B(x)

D.(Vx)(Vy)(A(x)-*B(y))«(3x)A(x)-(Vy)B(y)

4.设R为实数集，函数f：RfR,f(x)=2x,则f是(）

A.满射函数B.入射函数C.双射函数D.非入射非满射

三大题：计算证明题（共8小题，共60分）

5.设A={a,b,c,d},A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}UIA,则对应于R的A

1.（8分）如果论域是集合{a,b,c},试消去给定公式中的量词：（闩y）（Wx）（x+y=0）.

的划分是（）

2.（10分）设人二{21）3},P（A）是A的鼎集，㊉是集合对称差运算。已知＜P（A）,㊉》

A.{{a},{b,c},{d}}B.{{a,b}»{c}»{d)}C.{{a},{b}>{c},(d)}D.{{a,b

是群。在群＜P（A）,㊉〉中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足

},{c,d}}

（a）®x={b）

6.设X,Y,Z是集合，“-”是集合相对补运算，下列等式不正确的是（）

A.(x-Y)-z=x-(Ynz)B.(X-Y)-Z=(X-Z)-Y3.（8分）求公式r（P-Q）c（P--1Q）的主合取范式。

C.(X-Y)-Z=(X-Z)-(Y-Z)D.(X-Y)-Z=X-(YUZ)4.（8分）在偏序集＜Z,W＞中，其中Z={1,2,3,4,6,8,12,14},W是Z中的整除关系，求

7.设*是集合A上的二元运算，称Z是A上关于运算*的零元，则（）Z的极大元，极小元，最大元，最小元，并求集合口={2,3,4,6}的最小上界和最大下界。

A.对所有x属于A,有x*Z=Z*x=Z

B.Z属于A,且对所有x属于A,有x*Z=Z*x=Z

C.Z属于A,且对所有x属于A,有x*Z二Z*x二x

D.Z属于A,且存在x属于A,有x*Z二Z*x二Z

8.在自然数集N上，下列定义的运算中不可结合的只有（）

A.a*b=min（a,b）B.a*b=a+b

5.（8分）证明（（QAS）-R）A（S-（PVR））O（SA（P-Q））-R

C.a*b二abD.a*b二a/b

6.（8分）证明：下列两个图同构。

9.下列说法正确的是（）

A.整环必为域B.交换环必为整环C.整环必为交换环D.交换环必

为含幺环

7.（10分）在谓词逻辑中构造下面推理的证明：每个人在学校读书的就能获得知识。所以

如果没有人获得知识就没有人在学校读书。（个体域：所有人的集合）

8.在自然数集N上，下列定义的运算中不可结合的只有(D)

《离散数学》期末课程试卷答案A.a*b-min(a,b)

2020-2021AlB.a*b=a+b

C.a*b=a-b

郛专业：考试日期：时间：总分：分闭卷D.a*b=a/b

9.下列说法正确的是(C)

一大题：选择题(共10小题，每小题2分，共20分)

A.整环必为域B.交换环必为整环

1.下列是两个命题变元P，Q的小项是(C)

C.整环必为交换环D.交换环必为含幺环

A.PA-iPAQB.-]PVQ

10.下列各图是欧拉图的是(D)

C.nPAQD.-IPVPVQ

2.令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为

(D)A.P-*-|QB.PV-|Q

C.PAQD.PA-iQ

3.下列等值式不正确的是(C)

A.-|(Vx)A。(mx)iA二大题：填空题(共10空，每空2分，共20分)

B.(Vx)(B~*A(x))(Vx)A(x)i.“如果雪是黑的，太阳从西边出”是_a_命题。

C.(3x)(A(x)AB(x))«(3X)A(X)A(3X)B(X)2.集合A={1,2,3}上的二元关系R具有对称性，反对称性，自反性，则

D.(Vx)(Vy)(A(x)-B(y))<=>(3x)A(x)-*(Vy)B(y)R=(<1,1>,<2,2>,<3,3»。

4.设R为实数集，函数f：R-R,f(x)=2x,贝Ijf是(C)3.设R是实数集，在R上定义二元运算*为a*b=a+b+a-b,其中+和•是数的加法和乘法，

A.满射函数B.入射函数C.双射函数D.非入射非满射则代数系统<R,*>的幺元是3,3的逆元是-3/4°

5.设A={a,b,c,d},A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c»UIA,则对应于R的A4.对称关系具有自反性和对■称性。

的划分是(D)5.无向图G具有一条欧拉回路，当且仅当G是连通图，并且所有结点的度数都是偶

A.{{a},{b,c},{d}}B.{{a,b),{c},{d}}数.

C.{{a},{b},{c},{d)}D.{{a,b},{c,d}}6.在下图中，度数为3的结点有2个,出度为2的结点有」个。

6.设X,Y,Z是集合，“-”是集合相对补运算，下列等式不正确的是(A)

A.(X-Y)-z=x-(ynz)

B.(X-Y)-Z=(X-Z)-Y

C.(X-Y)-Z=(X-Z)-(Y-Z)

D.(X-Y)-Z=X-(YUZ)三大题：计算证明题(共8小题，共60分)

7.设*是集合A上的二元运算，称Z是A上关于运算*的零元，则(B)1.(8分)如果论域是集合{a,b,c},试消去给定公式中的量词：(三丫)(Vx)(x+y=0)。

A.对所有x属于A,有x*Z=Z*x=Z

解:原公式o(3y)(a+y=0八b+y=0八c+y=0)(2分)

B.Z属于A,且对所有x属于A,有x*Z=Z*x=Z<=>(a+a=0Ab+a=0AC+a=0)v(a+b=0Ab+b=0AC4-b=0)

C.Z属于A,且对所有x属于A,有x*Z=Z*x=xv(a+c=0Ab+c=0AC+c=0)(2分)

D.Z属于A,且存在x属于A,有x*Z二Z*x二Z

2.(10分)设庆=伍,1)人),P(A)是A的幕集，㊉是集合对称差运算。己知<P(A),㊉)

343

是群。在群<P(A),㊉》中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足

{a}㊉x={b}

解：①因为0wP(A),且对任意BwP(A),0^B=B,所以0为幺元.(3分)

②对任意BcP(A),因为B㊉B=0,所以B"=B.(3分)4

③因为{a}㊉{a,b}={b},所以产{a,b}.并且由题可知x的取法唯一.所以x有唯一解:证明：图中结点如上标示.建立映射:f：iTi1(3分)易见f为双射.(1分)又因左图的边为

x={a,b}.(4分)(1,2),(2,3),(2,4)(3,5).(4,5),(5,6).一一对应于右图的

3.(8分)求公式1(P-Q)—(P--|Q)的主合取范式。边：⑴，2'),(2',3')，(2',5')(3',4'),(4',5'),(4',6').所以两个图等价.(2分)

o(PA—>Q)c(―iPv—iQ)(l分)7.(10分)在谓词逻辑中构造下面推理的证明：每个人在学校读书的就能获得知识。所以

O((PA-iQ)A(-|PV-1Q))V(—>(PA-»Q)A-«(-iPv-»Q))(1分)如果没有人获得知识就没有人在学校读书。(个体域：所有人的集合)

<=>(PA」Q)V((「PVQ)A(PA「Q))(l分)译:P(x):x在学校读书;Q(x):x能获得知识.

A「分)

=PQ(1(Vx)(P(x)->Q(x))=Tmx)Q(x)fT")P(x)(3分)

=(Pv(QA->Q))AHQV(PA「P)(l分)

证明:⑴"X)(P(X)TQ(X)P

0(PvQ)A(Pv「Q)A(「Pv->Q)。分)

(2)P(a)fQ(a)US(I)

4.(8分)在偏序集<乙<>中，