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

院系：专业班级：姓名院系：专业班级：姓名：学号：装订线专业：考试日期：时间：总分：分闭卷一大题：选择题（共10小题，每小题2分，共20分）1．下列是两个命题变元P，Q的小项是（

）A．P∧┐P∧Q

B．┐P∨QC．┐P∧Q

D．┐P∨P∨Q2．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（

）A．P→┐Q

B．P∨┐QC．P∧Q

D．P∧┐Q3．下列等值式不正确的是（

）A．┐(x)A(x)┐AB．(x)(B→A(x))B→(x)A(x)C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)D．(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y)4．设R为实数集，函数f：R→R，f(x)=2x，则f是（

）A．满射函数

B．入射函数

C．双射函数

D．非入射非满射5．设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，则对应于R的A的划分是（

）A．{{a},{b,c},{d}}

B．{{a,b},{c},{d}}

C．{{a},{b},{c},{d}}

D．{{a,b},{c,d}}6．设X，Y，Z是集合，“-”是集合相对补运算，下列等式不正确的是（

）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)7．设*是集合A上的二元运算，称Z是A上关于运算*的零元，则（

）A．对所有x属于A，有x*Z=Z*x=ZB．Z属于A，且对所有x属于A，有x*Z=Z*x=ZC．Z属于A，且对所有x属于A，有x*Z=Z*x=xD．Z属于A，且存在x属于A，有x*Z=Z*x=Z8．在自然数集N上，下列定义的运算“*”中不可结合的只有（

）A．a*b=min(a,b)B．a*b=a+bC．a*b=D．a*b=a/b9．下列说法正确的是（

）A．整环必为域

B.交换环必为整环C．整环必为交换环

D.交换环必为含幺环10．下列各图是欧拉图的是（

）A.B.C.D.二大题：填空题（共10空，每空2分，共20分）1．“如果雪是黑的，太阳从西边出”是命题。2．集合A={1,2,3}上的二元关系R具有对称性，反对称性，自反性，则R=。3．设R是实数集，在R上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统<R,*>的幺元是，3的逆元是。4．对称关系具有性和性。5．无向图G具有一条欧拉回路，当且仅当G是，并且所有结点的度数都是。6．在下图中，度数为3的结点有个，出度为2的结点有个。三大题：计算证明题（共8小题，共60分）1．（8分）如果论域是集合{a,b,c}，试消去给定公式中的量词：(y)(x)(x+y=0)。2．（10分）设A={a,b,c

}，P(A)是A的幂集，是集合对称差运算。已知<P(A),>是群。在群<P(A),>中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}x={b}3．（8分）求公式┐(P→Q)(P→┐Q)的主合取范式。4．（8分）在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，求Z的极大元，极小元，最大元，最小元，并求集合D={2,3,4,6}的最小上界和最大下界。5．（8分）证明((Q∧S)→R)∧(S→(P∨R))(S∧(P→Q))→R6．（8分）证明:下列两个图同构。7．（10分）在谓词逻辑中构造下面推理的证明：每个人在学校读书的就能获得知识。所以如果没有人获得知识就没有人在学校读书。（个体域：所有人的集合）

院系：专业班级：姓名：院系：专业班级：姓名：学号：装订线专业：考试日期：时间：总分：分闭卷一大题：选择题（共10小题，每小题2分，共20分）1．下列是两个命题变元P，Q的小项是（

C

）A．P∧┐P∧Q

B．┐P∨QC．┐P∧Q

D．┐P∨P∨Q2．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（

D

）A．P→┐Q

B．P∨┐QC．P∧Q

D．P∧┐Q3．下列等值式不正确的是（

C

）A．┐(x)A(x)┐AB．(x)(B→A(x))B→(x)A(x)C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)D．(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y)4．设R为实数集，函数f：R→R，f(x)=2x，则f是（

C

）A．满射函数

B．入射函数

C．双射函数

D．非入射非满射5．设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，则对应于R的A的划分是（

D

）A．{{a},{b,c},{d}}

B．{{a,b},{c},{d}}

C．{{a},{b},{c},{d}}

D．{{a,b},{c,d}}6．设X，Y，Z是集合，“-”是集合相对补运算，下列等式不正确的是（

A

）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)7．设*是集合A上的二元运算，称Z是A上关于运算*的零元，则（

B

）A．对所有x属于A，有x*Z=Z*x=ZB．Z属于A，且对所有x属于A，有x*Z=Z*x=ZC．Z属于A，且对所有x属于A，有x*Z=Z*x=xD．Z属于A，且存在x属于A，有x*Z=Z*x=Z8．在自然数集N上，下列定义的运算“*”中不可结合的只有（

D

）A．a*b=min(a,b)B．a*b=a+bC．a*b=D．a*b=a/b9．下列说法正确的是（

C

）A．整环必为域

B.交换环必为整环C．整环必为交换环

D.交换环必为含幺环10．下列各图是欧拉图的是（

D

）A.B.C.D.二大题：填空题（共10空，每空2分，共20分）1．“如果雪是黑的，太阳从西边出”是真命题。2．集合A={1,2,3}上的二元关系R具有对称性，反对称性，自反性，则R={<1,1>,<2,2>,<3,3>}。3．设R是实数集，在R上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统<R,*>的幺元是0，3的逆元是-3/4。4．对称关系具有自反性和对称性。5．无向图G具有一条欧拉回路，当且仅当G是连通图，并且所有结点的度数都是偶数。6．在下图中，度数为3的结点有2个，出度为2的结点有1个。三大题：计算证明题（共8小题，共60分）1．（8分）如果论域是集合{a,b,c}，试消去给定公式中的量词：(y)(x)(x+y=0)。2．（10分）设A={a,b,c

}，P(A)是A的幂集，是集合对称差运算。已知<P(A),>是群。在群<P(A),>中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}x={b}解:①因为,且对任意,,所以为幺元.(3分)②对任意,因为,所以.(3分)③因为,所以x={a,b}.并且由题可知x的取法唯一.所以x有唯一解:x={a,b}.(4分)3．（8分）求公式┐(P→Q)(P→┐Q)的主合取范式。4．（8分）在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，求Z的极大元，极小元，最大元，最小元，并求集合D={2,3,4,6}的最小上界和最大下界。

解:此偏序关系的哈斯图如下.极大元:8,12,14,(3分)极小元:1.(1分)最大元:无.最小元:1.(2分)D的最小上界:12.最大下界：１.(2分)5．（8分）证明((Q∧S)→R)∧(S→(P∨R))(S∧(P→Q))→R证明:原式左边6．（8分）证明:下列两个图同构。证明:图中结点如上标示.建立映射:f:i.(3分)易见f为双射.(1分)又因左图的边为(1,2),(2,3),