淮海工学院2011-2012-2离散数学期末复习题答案 (2)
淮海工学院2011-2012-2离散数学期末复习题答案
一、选择题（每题3分）
1、下列句子中哪个不是命题？ ( C )
A、你通过了离散数学考试
B、我俩五百年前是一家
C、我说的是真话
D、淮海工学院是一座工厂
2、下列联接词运算不可交换的是( C )
A、 B、 C、 D、
3、命题公式不能表述为( B )
A、或
B、非每当
C、非仅当
D、除非，否则
4、 下列公式中为永真式的是 ( C )
A、 B、 C、 D、
5、 下列公式中为永真式的是( A)
A、 B、 C、D、
6、设个体域，则谓词公式消去量词后，可表示为为（ C ）
A、 B、
C、 D、
7、设个体域，则谓词公式去掉量词后，可表示为（ D ）
A、 B、
C、 D、
8、设：全总个体域，：是人，：犯错误，
则命题“没有不犯错误的人”的逻辑符号化为（ D ）
A、B、C、 D、
9、设：全总个体域，：是花，：是人，：喜欢，
则命题“有的人喜欢所有的花”的逻辑符号化为（ D ）
A、 B、
C、 D、
10、设为空集，则下列为假命题的是（ A ）
A、 B、C、 D、
11、设各不相同，则下述等式为真的是（ D ）
A、 B、
C、 D、
12、 设集合，为空集，为的幂集，则下列为假命题的是（ B ）
A、 B、 C、 D、
13、 设集合，为空集，为的幂集，则下列为假命题的是（ B ）
A、 B、 C、 D、
14、非空集合上的空关系不具备的性质是（ A ）
A、自反性
B、反自反性
C、对称性
D、传递性
10、设上的关系的关系图如下，则不具备的性质为（ A ）
A、自反性
B、反自反性
C、反对称性
D、传递性
15、上的关系只不具备（ C ）
A、 反自反性
B、 反对称性
C、对称性
D、传递性
16、设为上的关系，其关系图如下，则下列为真命题的是（ C ）
A、对称，但不反对称
B、反对称，但不对称
C、对称，又反对称
D、不对称，也不反对称
17、设为上的关系，其关系图如下，则下列为假命题的是（ C ）
A、不自反，也不反自反
B、不对称，也不反对称
C、传递
D、不传递
18、设，则上不同等价关系的个数为（ C ）
A、 B、 C、 D、
19、设，则上不同等价关系的个数为（ C ）
A、 B、 C、 D、
20、设分别为实数集、整数集，则下列函数为满射而非单射的是（ C ）
A、 B、
C、 D、
21、设分别为实数集、非负实数集、正整数集，下列函数为单射而非满射的是（ B ）
A、 B、；
C、 D、
22、设，则从到可以生成不同的单射个数为（ B ）．
A、 B、 C、 D、
23、设，则从到可以生成不同的满射个数为（ B ）．
A、 B、 C、 D、
24、设集合的幂集为，为集合的交、并、差、笛卡尔乘积运算，则下列系统中是代数系统的为（ D ）
A、 B、 C、 D、
25、在自然数集上定义的下列四种运算，其中满足结合律的是（C）
A、 B、 C、D、
26、设为前个自然数集，表示模加法，对代数系统，有（ A ）
A、是么元，无零元
B、是么元，无零元
C、无么元，是零元
D、无么元，无么元
27、设为前个自然数集，表示模乘法，对代数系统，有（ B ）
A、是么元，无零元
B、是么元，是零元
C、无么元，是零元
D、无零元，无么元
28、设非空有限集的幂集为，对代数系统，有（ B ）
A、是么元，是零元
B、是零元，是么元
C、唯一等幂元
D、无等幂元
29、设非空有限集的幂集为，对代数系统，有（ A ）
A、是么元，是零元
B、是零元，是么元
C、唯一等幂元
D、无等幂元
30、设Z是由所有整数组成的集合，对于下列*运算，代数系统
A、a*b=a b
B、a*b=a
C、a*b=a+ab
D、a*b=max(a,b)
31、任意具有多个等幂元的半群，它（A ）
A、不能构成群
B、不一定能构成群
C、能构成群
D、能构成阿贝尔群
32、下列命题正确的是（ B ）
A、简单回路必为基本回路
B、基本回路必为简单回路
C、简单回路必不是基本回路
D、基本回路必不是简单回路
33、欧拉回路是（ B ）
A、路径
B、简单回路
C、既是基本回路也是简单回路
D、既非基本回路也非简单回路
34、哈密尔顿回路是（ C ）
A、路径
B、简单回路
C、既是基本回路也是简单回路
D、既非基本回路也非简单回路
35、在任何有向图中，下列命题正确的是（ C ）
A、任意顶点的入度与出度都相等
B、任意顶点的入度与出度都不相等
C、所有顶点的入度之和与出度之和都相等
D、所有顶点的入度之和与
出度之和都不相等
36、设有向线图G的顶点集，邻接矩阵，则（ D ）
A、 B、 C、 D、
37、设有向线图G的顶点集，邻接矩阵，则（ C ）
A、 B、 C、 D、
38、在有n个结点的简单无向图中，其边数（ C ）
A、最多有n-1条
B、至少有n-1条
C、最多有条
D、至少有条
39、在有n个结点的简单有向图中，其边数（ C ）
A、最多有n-1条
B、至少有n-1条
C、最多有条
D、至少有条
40、在有n个结点的连通图中，其边数（ B ）
A、最多有n-1条
B、至少有n-1条
C、最多有n条
D、至少有n条
41、设，则上包含关系“”的哈斯图为（ C ）
42、集合上的偏序关系图为
则它的哈斯图为（ A ）
43、下列哪一种图不一定是树（ C ）
A、无简单回路的连通图
B、有n个顶点n-1条边的连通图
C、每对顶点间都有通路的图
D、连通但删去一条边便不连通的图
44、设是有5个结点的无向完全图，则从中删去（ C ）条边可以得到树
A、 4
B、5
C、6
D、10
二、填充题（每题4分）
1、当赋予极小项足标相同的指派时，该极小项的真值为1，当赋予极大项足标相同的指派时，该极大项的真值为0.
2、任意两个不同极小项的合取式的真值为0，而全体极小项的析取式的真值为1.
3、任意两个不同极大项的析取式的真值为1，而全体极大项的合取式的真值为0.
4、个命题变元可构造包括的不同的主析取范式类别为.
5、个命题变元可构造包括的不同的主合取范式类别为.
6、若已证为真，则可假设某一确定的个体使为真，此推理规则被称为．
7、令是公理与前提的合取，中无的自由出现，若从可推出，则从也可推出，此推理规则被称为．
8、，，．
9、，．
10、设，则．
11、设集合分别含有个不同元素，则的基数为，的基数为，
12、的基数为，的基数为，的基数为．
13、设，“”为上整除关系，则偏序集的极小元为，最小元为，极大元为、最大元为．
14、设，“”为上整除关系，则偏序集的极小元为，最小元为无，极大元为，最大元为无，既非极小元也非极大元的是．
15、设，则从到有种不同的二元关系，有种不同的函数．
16、在一个有个元素的集合上，可以有种不同的二元关系，有种不同的函数，
有种不同的双射．
17、设A={2,4,6}，A上*为：a*b=max{a,b}，则在代数系统
18、设A={3,6,9}，A上*为：a*b=min{a,b}，则在代数系统
19、设〈G,*〉是一个群，则
(1) 若a,b,x∈G，ax=b，则x= ab；(2) 若a,b,x∈G，ax=ab，则x= b．
20、群
21、设是12阶群的生成元，则是6阶元素，是4阶元素．
22、设是10阶群的生成元，则是5阶元素，是10阶元素．
23、在一个群〈G,*〉中，若G中的元素的阶是k，则的阶是k．
24、n阶无向完全图Kn 的边数是，每个结点的度数是．
25、设有向图G = < V，E >，的邻接矩阵，
则的入度= 3 ，的出度=1 ．
26、设无向图G有18条边且每个顶点的度数都是3，则图G有12个顶点．
27、一棵无向树的顶点数为n，则其边数为n-1 ，其结点度数之和是2n-2.
28、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在2片树叶.
三、问答题（每题6分）
1、若个体域，：，：,：，:，
则谓词公式为真吗？为什么？
答：为真；
.
2、谓词公式为真吗？为什么？
答：不为真；设个体域：实数域，：，
则.
3、设，问上存在一个既不是自反又不是反自反的关系吗？为什么？答：存在；如．
4、设，问上存在一个既不是对称又不是反对称的关系吗？为什么？答：存在；如．
5、设，问上存在一个既是对称又是反对称的关系吗？为什么？
答：存在；如．
6、设，，从到的关系
，试给出的关系图和关系矩阵，并说明此关系及其逆关系是否为函数？为什么？
解：，则的关系图为：
A
2
3
4
B
2
4
7
10
12
的关系矩阵为
关系不是到的函数，
因为元素2，4的象不唯一
逆关系也不是到的函数
因为元素7的象不存在．
7、设为整数集，函数：，且，问是单射还是满射？
为什么？并求．
解：, ，总有，则是满射；
对于，有，而，则非单射；
．
8、设Z为整数集合，“?”定义为：a?b=a b，问其在Z上封闭吗？可交换吗？可结合吗？
答：①取a＝2，b＝-1，a?b=2-1Z，其在Z上不封闭；
②取a＝2，b＝1时，a?b=a b=2，b?a=b a=1，a?b≠b?a，其在Z上不可交换；
③取a=2，b=1，c=2，(a?b)?c=4，a?(b?c) =2，(a?b)?c≠a?(b?c)，其
在Z上不可结合．
9、设Z为整数集合，“?”定义为：a?b=2ab，问其在Z上封闭吗？可交换吗？可结合吗？
答：①整数乘法运算在Z上封闭，
②a,bZ，a?b=2ab=2ba=b?a，其在Z上可交换；
③a,b,cZ，(a?b)?c=2(2ab)?c=4abc=2a×2bc=2a(b?c)=a?(b?c) ，其在Z 上可结合．
10、设无向图有条边，已知有个度顶点，其余顶点的度数均小于，问
中至少有多少个顶点？
答：设中度数小于的顶点有个，则由欧拉定理知，
度数小于3 的顶点度数之和为6，故当其余的顶点度数都为2时，G的顶点最少，
即G中至少有9个顶点.
11、n取怎样的值，无向完全图K n有一条欧拉回路?
答： n为奇数，v∈V，deg(v)=n-1为偶数，
所以，当n是大于或等于3的奇数时，K n有欧拉回路.
12、判断下列无向图是否存在欧拉路径？是否为欧拉图？说明理由.答：d(A)=2, d(B) =d(C)= d(D)=4 d(E) =d(F)=3
只有两个奇数度的结点, 有欧拉路径，如EDBEFCABCDF ；
由于每个结点的次数不均为偶数，所以不是欧拉图.
13、判断下列图是否为欧拉图？说明理由，是否存在哈密尔顿回路？答：一个无向图D是欧拉图D是连通的，且所有顶点的度等于偶数，
所以是欧拉图，但无哈密尔顿回路．
14、判断下列图是否存在欧拉路径？是否为欧拉图？说明理由.
答：一个有向图D是欧拉图 D是连通的，且所有顶点的入度等于出度，所以是欧拉图，存在欧拉路径．
四、填表计算题（每题10分）
1、对命题公式 ，要求
（1）用或填补其真值表的空格处；（2）求该命题公式的主析取范式与主合取范式.
解：
001000
011010
100111
111010
主析取范式 ；主合取范式.
2、对命题公式 ，要求
（1）用或填补其真值表的空格处；（2）求该命题公式的主析取范式与主合取范式.
解：
00010
00111
01010
01111
10001
10100
11010
11111
主析取范式 ；主合取范式.
3、设代数系统
?a b c
a a
b c
b b
c a
c c a b
解：
交换律幂等律么元逆元
有无a a –1= a, b –1= c, c –1= b
4、设代数系统
?a b c
a a
b c
b a b c
c a b c
解：
交换律幂等律么元逆元
有无a a –1= a, b –1= b
五、计算问答题（每题10分）
1、集合上的关系
，写出关系矩阵，画出关系图并讨论的五种性质．
解：的关系矩阵为，的关系图为
因对角元皆为，故是自反的，不是反自反的；因为对称矩阵，故是对称的；
因，故不是反对称的；
又因，但，故无传递性．
2、设是集合上的二元关系，
，
写出关系矩阵，画出关系图并讨论的五种性质．
解：的关系矩阵为，的关系图为
因对角元不全为，也不全为，故R不是自反的，也不是反自反的；
因为非对称矩阵，故是反对称的，不是对称的；因，故是传递的．
3、有向图G如图9.27所示，
⑴求G的邻接矩阵；
⑵根据邻接矩阵求各结点的出度和入度；
⑶求G中长度为3的路的总数，其中有多少条回路；
⑷求G的可达性矩阵．
解：⑴M R=；
⑵deg＋(v1)=2，deg－(v1)=1，deg＋(v2)=1，deg－(v2)=2，
deg＋(v3)=2，deg－(v3)=1，deg＋(v4)=0，deg－(v4)=1；
⑶A2= ，A3= ，
长度为3的路有8条，其中回路3条；
⑷ C3=A0+A1+A2+A3= P=．
4、有向图，其中结点集，有向边集可表示为：
（1） 求的邻接矩阵；（2）求的可达性矩阵；
（3）说明到长度为4的路径有几条？（4）到其它各顶点长度为3的路径有几条？
解：（1） ；
（2），，
， ；
（3）到长度为4的路径有2条；
（4）到其它各顶点长度为3的路径有2条．
5、有向图，其中结点集，
有向边集
（1）求的邻接矩阵；（2）求的可达性矩阵；
（3）说明中经过长度为的回路有几条？
（4）说明中到长度为4的路径有几条？
（5）说明中到所有的路径有几条？
解：（1）；
（2），，，
，；
（3）中经过长度为的回路有条；（4）中到长度为4的路径有条；（5）中到所有的路径有条.
四、证明计算题（每题10分）
1、设，在上定义，
“”为普通加法，证明：是上的等价关系，并求出．
证明：（1）即自反；
（2）
则，即对称；
（3）
有，即传递；
综上得出，是上的等价关系，
且,
．
2、设，在上定义，
“” 为普通乘法，证明：是上的等价关系，并求出．
证明：（1）即自反；
（2）
则，即对称；
（3）
，
有，即传递；
综上得出，是上的等价关系，
且,
3、设R是实数集，R上的二元运算*定义为：a*b=a+b+ab，
证明：
证明：⑴由于实数经加法和乘法运算后，其运算结果仍为实数，所以运算*对于R是封闭的；
由于a*b=a+b+ab=a(b+1)+(b+1)?1=(a +1) (b+1)?1
从而有(a*b)*c=((a +1)(b+1)?1)*c=(((a +1)(b+1)?1)+1)(c+1)?1=(a +1) (b+1)(c +1)?1
a*(b*c)=a*((b +1)(c+1)?1)=(a +1)(((b +1)(c+1)?1)+1)?1=(a +1)(b+1)(c
+1)?1
于是 (a*b)*c=a*(b*c)，所以*是可结合运算；
在
故0是
对
4、某无向连通图中有条边，二个度顶点，二个度顶点，一个度顶点，其余顶点的度数都是，求的顶点个数，并证明为树.
解：设中度数为的顶点个数为
由握手定理知
解得
于是中的顶点个数为
因为连通图，且中的边数比其顶点个数少-故为树.
五、证明题（每题10分）
1、用逻辑推理规则证明：，，.
证明: (1)
(2)
(3) (1),(2) (析取三段论)
(4) (1) (加法式)
(5)
(6) (4)，(5) (拒取式)
(7)(3)，(6) (合取式)
(8) (7) (等值表达式) .
2、用逻辑推理规则证明：， .
证明：（1） (附加前提)
(2) (1)（加法式）
(3)
(4) (2)，(3)（假言推理）
(5) (4)（简化式）
(6) (5)（加法式）
(7)
(8) (6)，(7)（假言推理）
(9).
3、用逻辑推理规则证明：．
证明：⑴
⑵⑴（）
⑶
⑷⑶（）
⑸⑵，⑷（拒取式）
⑹
⑺⑹（）
⑻⑸，⑺（析取三段论）
⑼⑻（）．
4、用逻辑推理规则证明：．
证明：⑴
⑵⑴（）
⑶
⑷⑴，⑶（假言推理）
⑸⑷（）
⑹⑵（加法式）
⑺⑸，⑹（假言推理）
⑻⑺（）．
5、用逻辑推理规则证明：.
证明：⑴（附加前提）
⑵⑴（）
⑶
⑷⑶（）
⑸⑵，⑷（假言推理）
⑹⑸（）
⑺．
6、设为集合上的二元关系，如果是反自反的和可传递的，则一定是反对称的．
证明：假设不是反对称的，则
由R的传递性知，，此与反自反矛盾，故R反对称．
7、设是上的对称和传递关系，
证明：若，则是上的等价关系．
证明：，因是对称的，有，
又因是传递的，所以，则在上自反，故是上的等价关系．
8、设是上的偏序关系，证明：是上的偏序关系．
证明：（1），因在上的自反性，则，有在上自反；
（2）设而，则因在上的反对称性，有则于是，在上是反对称的；（3）设，
则，因在上的传递性，
有,则，于是，在上是传递的；
综上所述，可证是上的偏序关系．
9、设是上的等价关系，证明：是上的等价关系．
证明：（1）因在上的自反性，有，则，有在上自反；
（2）因在上的对称性，有，则，有在上对称；
（3）因在上的传递性，有，则，有在上可传递；
则，有在上是对称的；
综上所述，可证是上的等价关系．
10、设Z是整数集，Z上的二元运算*定义为：a*b=ab+2(a+b+1)，证明：
证明：因任意两个整数经加、减、乘运算后，其结果仍然是整数。所以运算*对于是封闭的；
注意到，a*b=ab+2(a+b+1)=ab+2a+2b+2=a(b+2)+2(b+2)?2=(a+2) (b+2)?2
从而有(a*b)*c=((a +2)(b+2)?2)*c=(((a +2)(b+2)?2)+2)(c+2)?2=(a +2) (b+2)(c +2)?2
a*(b*c)=a*((b +2)(c+2)?2)=(a +2)(((b +2)(c+2)?2)+2)?2=(a +2)(b+2)(c
+2)?2
于是 (a*b)*c=a*(b*c)，则*是可结合运算，故代数系统
证明：首先证明*对于A是封闭的，由于a*b=(a +1)(b+1)?1
所以当a和b为不等于?l的实数时，a+1≠0，b+1≠0，也即有(a +1) (b+1)≠0，
由此可知a*b=(a +1)(b+1)?1≠?1，因此*对于A是封闭的；
(a*b)*c=((a +1)(b+1)?1)*c=(((a +1)(b+1)?1)+1)(c+1)?1=(a +1)(b+1)(c
+1)?1
a*(b*c)=a*((b +1)(c+1)?1)=(a +1)(((b +1)(c+1)?1)+1)?1=(a +1)(b+1)(c
+1)?1
于是 (a*b)*c=a*(b*c)，所以*是可结合运算；
在
对于A中a (a是不等于?1的实数)，都有a*(?1)=(a +1)(?1+1)?1=0
由于0是么元，所以a的逆元是?1；综上证明，
12、
求证：
证明：1）a，b∈G，ab=a*u-1*b∈G，运算是封闭的；
2）a，b，c∈G，（ab）c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）
=a（bc），运算可结合； 3）a∈G，设E为的单位元，则aE=a*u-1*E=a，得E=u，存在么元u；
4）a∈G，ax=a*u-1*x=E，x=u*a-1*u，则xa=u*a-1*u*u-1*a=u=E，各元素都有逆元；
所以
13、设图G=
点或是k+1度点，证明：= (k+1)n -2m.
证明：由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知2m==k+(k+1)(n-)=(k+1)n-，= (k+1)n -2m.
14、设G=V,E是图，|V|=n，|E|=m，证明：(G)≤≤(G) .
证明：根据最小度的定义，vV，deg(v)≥(G)，所以，2m=≥=n(G)
即n(G) ≤2m，整理后得，(G)≤
另一方面，根据最大度的定义，vV，deg(v)≤(G)，与前面推理类似的可得，2m≤n(G)
整理后得，(G)≥，,所以， (G)≤≤(G) .
15、设图G有n个结点，n＋1条边，证明：G中至少有1个结点度数大于等于3.
证明：用反证法，设G=V,E，v∈V，deg(v)≤2，
所有结点的度数之和2(n+1)小于2n。即2(n+1)≤2n，化简后，2≤0，矛盾，
所以，G中至少有1个结点度数大于等于3.
离散数学期末试题
离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。
离散数学期末试题及答案
326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ).
(完整版)离散数学试卷及答案
离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：
((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，
离散数学期末试题及答案完整版
离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).
离散数学试卷及答案一
一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 《离散数学》期末考试题(B) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为 ( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( ) 一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 离散数学期末测验试题（有几套带答案1) ————————————————————————————————作者: ————————————————————————————————日期: ? 离散数学试题(A卷及答案） 一、证明题（10分） １)(?P∧(?Q∧Ｒ)）∨(Q∧R）∨(P∧R）?Ｒ 证明：左端?(?P∧?Q∧R)∨（(Q∨Ｐ)∧R)?（(?P∧?Q)∧R))∨((Ｑ∨Ｐ)∧R） ?(?(P∨Q）∧R)∨((Q∨P)∧Ｒ)?(?(P∨Q)∨(Ｑ∨Ｐ))∧R ?(?(P∨Q)∨(Ｐ∨Ｑ))∧R?T∧R(置换）?R 2）?x(Ａ（ｘ)→B(x)）??xＡ(x）→?xB(x) 证明:?x(A(x)→Ｂ(x））??x（?A（x)∨B(x))??x?A(x)∨?xB(x)???xA（x)∨?xB(x)??xA(x)→?xＢ(ｘ） 二、求命题公式(P∨(Q∧Ｒ))→(Ｐ∧Q∧R）的主析取范式和主合取范式(１０分) 证明:(P∨（Ｑ∧Ｒ））→(P∧Q∧R)??(P∨(Ｑ∧Ｒ）)∨（P∧Q∧R)) ?（?P∧（?Q∨?R)）∨(Ｐ∧Q∧Ｒ） ?(?P∧?Ｑ)∨(?P∧?R)）∨(Ｐ∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Ｑ∧?R）∨(?Ｐ∧Q∧?R)）∨(?P∧?Q∧?R)）∨(Ｐ∧Ｑ∧R) ?m0∨ｍ1∨m2∨ｍ７ ?Ｍ3∨M4∨M5∨M6 三、推理证明题(10分) 1）Ｃ∨D， (C∨D)→?E, ?Ｅ→(A∧?B), (A∧?B)→(R ∨S)?R∨S 证明:(1) (C∨D）→?E (２) ?E→（A∧?Ｂ) ?? (3）（C∨D）→（A∧?Ｂ) （４) （Ａ∧?B)→(R∨Ｓ) ?? (5) （C∨D）→（R∨Ｓ) ? (6) C∨Ｄ?? (7) R∨S 2) ?x(P(ｘ)→Q(ｙ）∧R(x)），?xP(x)?Q(y）∧?x（P(x)∧R(x)) 证明（1)?xP(ｘ) (2）P(a) （3)?ｘ(P(x)→Q(y）∧R(x)) (4）P（a)→Q(y)∧R(a) (５)Q(y)∧Ｒ(a) (6)Q(y) （７)R(a） (8)P(a) (9)P(ａ)∧R(a) （10)?x(Ｐ(x)∧R(ｘ)) (11)Q（ｙ)∧?x(P（x）∧R(x)） 五、已知Ａ、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) （１5分) 证明∵x∈A-（Ｂ∪C)?x∈A∧x?（Ｂ∪C)?x∈A∧(x?Ｂ∧ｘ?C）?(x∈A∧x?B)∧（x∈A∧x?C）?x∈（Ａ-B)∧ｘ∈(A－C）?x∈(A－B）∩（A-Ｃ)∴A-(B∪Ｃ）=（A-B)∩(A-C） 六、已知R、S是N上的关系，其定义如下：Ｒ=｛＜x，ｙ>| x，y∈N∧y=x2｝，Ｓ={ 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统 二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 精品文档院术师范学广东技模拟试题 科目：离散数学 120 分钟考试时间: 考试形式：闭卷 姓名：学号：系别、班级： 2分，共10分）一．填空题（每小题__________。?x?y?P(x)∨Q(y) 1. 谓词公式的前束范式是 __)xxQ(?xP(x)????????____，，2. 设全集A?_{4,5}B =__则A∩ {2}__,,?E?1,2,3,4,55,A?21,,32,B_____ __ {1,3,4,5}??BA????b,c}} __________，则3. 设__ ， b?,c,b,a,A?Ba???B(A)?)(_____Φ_______。???)(AB()?4. 在代数系统（N，+）中，其单位元是0，仅有_1___ 有逆元。 ne条边，则G有___e+2-n____个面。5．如果连通平面图G有个顶点，二．选择题（每小题2分，共10分） P?(Q?R)等价的公式是（1. 与命题公式） （A）（B）（C）（D）R?P?Q)()?R)R?(QPP?(Q?R?Q)(P??????b?b,?a,aA??a,b,cR?,不具备关系( 2. 设集合上的二元关系,A)性质 （A）(A)传递性(B)反对称性(C)对称性(D)自反性 G??V,E?中,结点总度数与边数的关系是3. 在图( ) ??E?Edeg(v)deg(v)?2deg(v)?Evdeg()?2E(A)(C)(B) (D) iiiiVv?Vv?4. 设D是有n个结点的有向完全图,则图D的边数为( ) n(n?1)n(n?1)n(n?1)/2n(n?1)/2(A)(B)(D)(C) 5. 无向图G是欧拉图,当且仅当( ) (A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数 精品文档． 精品文档 (C)G连通且所有结点的度数都是偶数(D) G连通且G的所有结点度数都是奇数。 三．计算题（共43分） p?q?r的主合取范式与主析取范式。（1. 求命题公式6分） 解：主合取方式：p∧q∨r?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)= ∏0.2.4 主析取范式：p∧q∨r?(p∧q∧r) ∨(p∧q∧?r)∨(?p∧q∧r) ∨(?p∧?q∧r) ∨(p∧?q∧r)=∑1.3.5.6.7 1000????0111?????Md,A?a,b,c,的上的二元关集2. 设合系R关系矩阵为求 ??R0000????1000??)tR(),(RsRr()(),(),(rRsRtR),的关系图。R的关系矩阵，并画出分）10（， 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 离散数学-期末考试卷-A卷 东莞理工学院城市学院（本科）试卷（A卷） 2013-2014学年第一学期 开课单位：计算机与信息科学系，考试形式：闭卷，允许带入场 科目：离散数学，班级：软工本2012-1、2、3 姓名：学号： 题序一二三四总分 得分 A评 卷人 一、单项选择题（每小题2分，共20分） 在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。 1. 下述不是命题的是( ) A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 2. 命题公式P→(P∨Q∨R)是( ) A. 永假的 B. 永真的 C. 可满足的 D. 析取范式 3. 命题公式﹁B→﹁A等价于( ) A. ﹁A∨﹁ B B. ﹁(A∨B) C. ﹁A∧﹁ B D. A→B 4．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）A．?P∧Q B．P∧?Q C．P→?Q D．P∨?Q 5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）A．?x(A(x))∧B(x) B．??x( A(x)→?B(x) ) C．??x( A(x)∧B(X)) D．??x( A(x)∧?B(x) ) 6. 设有A={a,b,c}上的关系R={ 7. 设A={1,2,3,4,5,6},B={a,b,c,d,e}，以下哪一个关系是从A到B的满射函数( ) A. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>} B. f={<1,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>} C. f={<1,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>} D. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<1,b>} 8．设简单图G所有结点的度数之和为10，则G一定有（） A．3条边B．4条边C．5条边 D．6条边 9．下列不．一定是树的是（） A．每对结点之间都有通路的图 B．有n个结点，n-1条边的连通图 C．无回路的连通图D．连通但删去一条边则不连通的图 10．下列各图中既是欧拉图，又是哈密顿图的是（） 填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论 C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 A 、 x(P(x) Q(x)) xP(x) xQ(x)； B 、 x(P(x) Q(x)) xP(x) xQ(x)； C 、 x(P(x) Q) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x)【浙江工商大学】《离散数学》期末考试题(B)
离散数学试卷及答案(2)
离散数学期末考试试题及答案
离散数学期末试卷A卷及答案
离散数学期末测验试题(有几套带答案1)
离散数学试题与答案
离散数学期末考试试题及答案
离散数学期末试卷及答案
最新离散数学期末考试试题配答案
《离散数学》期末考试试题
离散数学-期末考试卷-A卷
离散数学试卷及答案
- 离散数学期末试题及答案完整版
- 离散数学期末复习试题及答案(六)
- 离散数学期末考试试题及答案
- 离散数学期末复习习题
- 最新离散数学期末考试试题(配答案)
- (完整word版)离散数学期末练习题带答案
- 2018年春季学期离散数学期末复习题
- 离散数学期末复习题(6套)
- 离散数学期末考试题
- 《离散数学》期末复习题_69521457073107968
- 离散数学期末练习试题[带答案]
- 中国石油大学大学《离散数学》期末复习题及答案
- 离散数学期末练习题 (带答案)讲课稿
- 离散数学期末复习题
- 离散数学期末练习题 (带答案)
- (完整版)离散数学期末考试试题及答案,推荐文档
- 《离散数学》期末试题及答案
- 离散数学期末考试题(附答案和含解析1) - 副本
- 离散数学期末考试试题(有几套带答案)
- 离散数学期末考试试题及答案