离散数学作业标准答案docx.docx
《离散数学作业标准答案docx.docx》由会员分享，可在线阅读，更多相关《离散数学作业标准答案docx.docx（78页珍藏版）》请在冰点文库上搜索。
离散数学作业标准答案docx
离散数学作业
一、选择题
1、下列语句中哪个是真命题（C）。
A．我正在说谎。
B．如果1+2=3，那么雪是黑色的。
C．如果1+2=5，那么雪是白色的。
D．严禁吸烟！
2、设命题公式
A.恒假的
G
p（p（q
B.恒真的
r）），则G是（C.可满足的
C
）。
D.析取范式
3、谓词公式
F（x,y,z）
xyG（x,y,z）中的变元
x（
C
）。
A．是自由变元但不是约束变元
B．既不是自由变元又不是约束变元
C．既是自由变元又是约束变元
D．是约束变元但不是自由变元
4、设A={1，2，3}，则下列关系R不是等价关系的是（C）
A．R={<1，1>，<2，2>，<3，3>}
B．R={<1，1>，<2，2>，<3，3>，<2，3>，<3，2>}C．R={<1，1>，<2，2>，<3，3>，<1，4>}
D．R={<1，1>，<2，2>，<3，3>，<1，2>，<1，3>，<2，3>，<2，1>，
<3，1>，<3，2>}
5、设R为实数集，映射=RR，（x）=-x2+2x-1，则是（D）。
A．单射而非满射B．满射而非单射C．双射D．既不是单射，也不是满射
6、下列二元运算在所给的集合上不封闭的是（D）
A.S={2x-1|xZ+}，S关于普通的乘法运算
B.S={0，1}，S关于普通的乘法运算
C.整数集合Z和普通的减法运算
n，n
Z+，
S
关于普通的加法运算
D.S={x|x=2
}
7、*运算如下表所示，哪个能使（{a,b}，*）成为含幺元半群（D）
ab
ab
ab
ab
aab
aa
a
aaa
aa
b
bab
bb
b
baa
bb
a
A
B
C
D
8、下列图中是欧拉图的是（
A
）。
A
B
C
D
9、下列各组数中
能构成无向图的度数列是（
D
）
A．1,1,1,2,4
B．1,2,3,4,5
C．0,1,0,2,4
D．1,2,3,3,5
10、一棵树有2个4度顶点，3个3度顶点，其余都是树叶，则该树中树叶的个
数是（B）
A.8B.9C.10D.11
11、“所有的人都是要死的。
苏格拉底是人，所以苏格拉底是要死的。
”则该
句话（B）
A．不是命题B．是真命题C．是假命题D．是悖论
12、一个公式在等价意义下，下面哪个写法是唯一的（C）。
A．析取范式B．合取范式C．主析取范式D．以上答案都不对
13、设论域E={a,b}，且P（a,a）=1P（a,b）=0P（b,a）=1P（b,b）=0则在下列公
式中真值为1的是（D）
A.$x"yP（x,y）B."x"yP（x,y）C."xP（x,x）D."x$yP（x,y）
14、设集合A={1,2,3}，A上的关系R={<1,1>,<2,2>，}则R不具有（
A
）
性质。
A.自反性
B.对称性
C.传递性
D.反对称性
15、设集合A={a,b,c,d},B={1,2,3,4},则从A到B的函数f={,,,}
是（D）。
A.双射函数
B.单射函数
C.满射函数
D.即不是满射又是不是单射函数
16、下面给出的一阶逻辑等值式中，（B
）是错的。
A.x（A（x）
B（x））
xA（x）
xB（x）;
B.x（A（x）
B（x））
xA（x）
xB（x）;
C.
xA（x）
x（
A（x））;
D.A
xB（x）
x（AB（x））.
（C
17、下列各代数系统中，不含零元素的是
）
A．
Mn（R）,，Mn（R）是全体n阶实矩阵集合，
是矩阵乘法运算。
B．
p（S）,
，p（S）是集合S的幂集合，
是集合的并运算。
C．
R,
，R是有理数集，是数的加法运算。
D．
I,
，I是整数集，
是数的乘法运算。
18、
G是有
6个点的通，度数
20，从
G中去（
B
）
后使之成。
A.10
B.5
C.3
D.2
19、在具有
n个点的无向通中，（B
）。
A.恰好有
C.最多有
n条
n条
B.恰好有
D.至少有
n-1条
n条
20、下列是欧拉的是（
C
）
21.半群、群及独异点的关系是⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（D）
（A）{群}
{独异点}
{半群}
（B）{独异点}
{半群}
{群}
（C）{独异点}
{群}
{半群}
（D）{半群}
{独异点}
{群}
22.集合A={1,2,3}，A上的关系R={<1,1>,<2,2>,<3,3>}，R不具有下列性中的⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（D）
（A）自反性（B）称性（C）性（D）反自反性
23.以下中哪个是欧拉⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（D）
24．*运算如下表所示，哪个能使<{a,b}，*>成含幺元半群⋯⋯⋯⋯（D）
a
aa
ba
b
b
b
a
aa
bb
b
a
b
a
aa
ba
b
a
a
a
aa
bb
b
b
a
（A）
（B）
（C）
（D）
25.
P：
三可以做件事，
Q：
李四可以做件事。
命“三或李四可以
做件事”符号化⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（A）
（A）PQ（B）P~Q（C）PQ（D）~（~P~Q）
26.
27.G是通的平面，有5个点，6个面，G的数⋯⋯⋯⋯⋯（C）
（A）6（B）5（C）9（D）11
28.下列句子中是命的有⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（D）
（A）上不要!
（B）我在.（C）你吃了（D）上海是中国的
首都.
29.以下命公式中，永假式的是（C）
（A）p→（p∨q∨r）
（B）（p→┐p）→┐p
（C）┐（q→q）∧p
（D）┐（q∨┐p）→（p∧┐p）
30.
的生成子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（
C）
（A）（B）（C）（D）
31.如下所示的有界格中，元素b的元是（D）
（A）a
（B）0
（C）c
（D）d
32.
A={a,b,c}，下列是集合A的划分的是（D）
（A）{{b,c},{c}}
（B）{{a,b},{a,c}}
（C）{{a,b},c}
（D）{{a},{b,c}}
33.
整数集合Z上“＜”关系的自反包是关系
（
D）
（A）=
（B）≠
（C）＞
（D）≤
34.下列式子正确的是（B）
（A）∈（B）（C）{}（D）{}∈
35.i是虚数，·是复数乘法运算，G=<{1,-1,i,-i},·>是群，下列是G的子群
是（A）
（A）<{1},·>（B）〈{-1},·〉（C）〈{i},·〉（D）〈{-i},·〉36.集合A={1，2}的集P（A）的基数是⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（D）
（A）0（B）1（C）2（D）4
37.下列哪个运算不可交⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（A）
（A）→（B）（C）∨（D）∧
38.集合A={1，2，3，⋯，10},下列定的哪种运算关于集合A是不封的（D）
（A）x*y=max{x,y}（B）x*y=（x,y）即x,y的最大公数
（C）x*y=min{x,y}（D）x*y=[x,y]即x,y的最小公倍数
39.R数集，函数f：
R→R，f（x）=2x，f是（B）
A．射函数B．射函数C．双射函数D．非射非射
40.若是一个代数系,且足合律,必⋯⋯⋯⋯⋯⋯⋯（A）
（A）半群（B）独异点（C）群（D）交群
41.R是A上的等价关系,即R是⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（D）
（A）反自反的,称的，的（B）自反的,反称的,的
（C）反自反的,反称的,的（D）自反的,称的,的
42．下列哪一命公式是等价的⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（B）
（A）
（C）
~P
~Q，PQ
（B）
A
（B
A），~A（A~B）
Q
（PQ），~Q（PQ）
（D）
~A
（A
B），B
43.S={0,1},S⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（A）
（A）在普通乘法下封，在普通加法下不封;（B）在普通加法和乘法下都封
；
（C）在普通加法下封，在普通乘法下不封；（D）在普通加法和乘法下都不封；
44.下面公式是前束范式的是
（
A）
A.
x
yz（B（x,y）
A（z））
B.
xy（B（x,y）
C.
x
yz（B（x,y）
A（z））
D.
x（B（x,y）yB（y））
45.整数集合Z上“＜”关系的自反包是关系（D）
（A）=（B）≠（C）＞（D）≤
11.下列既是欧拉,又是哈密的是⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯（C）
（A）（B）（C）（D）
46.A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，关系R的称
包S（R）是（C）
（A）R∪IA（B）R（C）R∪{〈c,a〉}（D）R∩IA
47.下列式子正确的是（B）
（A）∈（B）（C）{}（D）{}∈
48.下列句子是命的是（C）
（A）水开了
49.函数f:
A
（A）A=B
（B）花多好看呀！
（C）2是常数。
B可逆的充要条件是（D）
（B）A与B有相同的基数（C）f射
（D）我正在
（D）f双射
二、填空题
1、公式（P∧Q）→（R∨S）真表中共有16种真指派。
2、A（x）:
x是运,B（x）:
x是壮的.命“没有一个运不是壮的”可符号
化
。
3、
是公式
xF（y,x）
yG（y）的前束范式。
4、集合A={1,2,3}上两个二元关系R1={＜1,3＞，＜2,1＞，＜3,2＞}和R2={＜1,2＞，＜2,3＞，＜3,1＞}，
R1
R2=
t（R1）
。
5、集合Zm={[0],[1],[2]，⋯，[m-1]}，在Zm上定运算+m：
任意的[i]，[j]∈
Zm有：
[i]+m[j]=[（i+j）（modm）]，的幺元是
[0]
，[i]
∈Zm的逆元是
[m-i]
。
6、无向
G如
1所示，
G的点通度
1
。
图1图2
7、有向图D如图2所示，则有向图D的邻接矩阵
中长度为2的回路有2条。
A=
，D
8、设p：
1+1=5，q：
明天是阴天。
则命题“只要1+1=5，那么明天是阴天”可符
号化为_________，其真值为________1_。
9、设F（x）:
x是兔子，Gy:
y是乌龟，H（x,y）:
x比y跑得快，则“并不是所有
的兔子都比乌龟跑得快。
”可符号化为
1210
10、设有向图D的邻接矩阵A（D）=
0
0
1
0
则长度为2的通路有
10条.
0
0
0
1
0
0
1
0
11、设Z4
{0,1,2,3},x
y
x
y
x
y
4
）的生成元
{
y4
x
y
，则（Z4,
x
4
是
1
或
3
。
12、具有16个结点的完全无向图其边数一定为
120
条。
13、设集合A
{2,3,4,6,8,12,24}，R为A上的整除关系，集合A中的极大元是
24；极小元2，3；
14、整数加群的幺元是
15若A={1,2,3},x,y
_
A,x
0___。
ymin{x,y}
则*的运算表为
16.设
A={a,{a}},A的幂集
P（A）是
。
17.设
G是n阶无向完全图
则该图的边数为
。
18.在一棵根树中，仅有一个结点的入度为
0_，称为树根，其余结点的入度
均为
1
。
19.设
A、B是两个集合，其中
A={a,b,c}，B={1，2}，则
A×B=
.
20.设个体域
A={a,b},公式
xP（x）
xS（x）
在
A中消去量词后应是
21.设M（x）:
x是人，D（x）:
x是要死的，则命题“所有的人都是要死的”可符号化
为______,其中量词的辖域是_____
22.画出完全图K5
23.
设A={a,b,c},则A×A中的元素有
9
个。
24.
设集合A={1,2,3,4},R为A上的一个二元关系，R={<1,1>,<1,2>,<2,1>,<3,3>}则
R的关系矩阵为
.
25.设G是m阶有向完全图,则该图的边数为m（m-1）
26.设P（x）：
x非常聪明；Q（x）:
x非常能干；a：
小李；则命题“小李非常聪明和能干”的为谓词表达式为_______。
{1.4.5}
.
27.设A，B是两个集合，A={1,2,3,4}，B={2,3,5}，则AB=
28.公式A→（x）B（x）的前束范式为____________________。
29.一个简单连通无向图有n个节点，它的边数至少有n-1条。
30.画出完全图K3,3
三、计算题
1、求公式（pq）r的主析取范式和主合取范式。
解：
方法一（等值演算法）
（p
q）
r
（（p
q）
r）
（r
（p
q））
（
（
p
q）
r）
（（
p
q）
r）
（（p
q）r）
（
p
q
r）
（p
q
r）
（
p
r）
（q
r）
（p
m1
m3
q
m4
r）
m7
（
p
qr）
（
p
qr）
（p
q
r）
方法二（真值表法）
公式
（p
q）
r真值表如下：
p
q
r
pq
（p
q）
r
r
（p
q）
（p
q）
r
0
0
0
1
0
1
0
0
0
1
1
1
1
1
0
1
0
1
0
1
0
0
1
1
1
1
1
1
1
0
0
0
1
1
1
1
0
1
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
1
1
1
根据真值表可以得到主析取范式为：
m1
m3m4
m7
2、列出命题公式（（p
q）p）
p的真值表。
解：
p
q
p
q
（p
q）
p）
（pq）p）
p
0
0
1
0
1
0
1
1
0
1
1
0
0
1
1
1
1
1
1
1
3、设集合A=1,2,3
，R为A上的二元关系，R={＜1,2＞＜3,1＞,＜2,3＞}，求R2，
r（R），s（R），t（R）的集合表达式。
解：
因为R={<1,2>,<2,3>,<3,1>},所以
R2={<1,3>,<2,1>,<3,2>}
r（R）={<1,1>,<2,2>,<3,3>,<1,2>,<2,3>,<3,1>}
s（R）={<1,2>,<2,1>,<2,3>,<3,2>,<3,1>,<1,3>}
t（R）=EA
4、在偏序集中，其中A={1,2,3,4,6,8,12,14}，≤是A中的整除关系，求集
合D={2,3,4,6}的极大元，极小元，最大元，最小元，上界，下界,最小上界和最大下界。
解：
极大元：
4，6；极小元：
2，3；
最大元：
无；最小元：
无；
上界：
12；下界1：
最小上界：
12;最大下界:
1
5、求带权为1,3,6,7,8,11的最优二叉树,编一个最佳2元前缀码，并求其权数.
解：
最优二叉树如下图所示：
编码：
1：
0000；3：
0001
；6：
001；7：
10；
8：
11；11：
01
最小生成树的权数为其权W（T）=（1+3）*4+6*3+（11+7+8）*12=86
36
15
21
7
8
10
7
11
4
6
1
3
6、用Kruskal算法求下列权图的最小生成树,并求最小生成树的权数,要求写出解的过程.
B
7
D2
E
3
1
4
A
2
5
9
7
C4E
解:
取数的由小到大的排列为1＜2＜3＜4＜5＜7＜9
B
2
D
F
3
1
4
A
2
E
C
最小生成树如图所示：
最小生成树的权数为其权W（T）=12
7、设A={a,b,c,d},R={,,,}。
试用关系图表示R及R的传递闭包。
8、设G=＜a＞是10阶循环群，求出G的所有子群。
解：
因为10的正因子是1,2,5，10
所以G的子群有4个，
分别是
={e}
={e,a5}
={e,a2,a4,a6，a8}
=G
9、
（1）在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，应该有几片树叶
（2）画出两棵非同构的满足
（1）中顶点度数的无向树T1和T2。
解：
（1）设树有n个顶点，则有n-6片树叶
根据握手定理可知
2243（n6）2（n1）
于是n=12
因此有6片树叶。
（2）两棵非同构的树为
T1T2
10、A、B、C、D四个人中要派两个人出差，需满足如下条件：
（1）若A去，则C和D中要去一人；
（2）B和C不能都去；
（3）C去则D要留下。
问有几种派法如何派
解：
用A、B、C、D分别表示A去，B去，C去，D去出差，则命题符号化如下：
（1）A→（C⊙D）（⊙表
升级会员 