离散数学南昌大学软件学院试卷(软工)(A)Word格式.doc
《离散数学南昌大学软件学院试卷(软工)(A)Word格式.doc》由会员分享，可在线阅读，更多相关《离散数学南昌大学软件学院试卷(软工)(A)Word格式.doc（8页珍藏版）》请在冰点文库上搜索。
q）
C．（pÚ
q）D．（pÚ
q）
3．与p®
q等值的命题公式是。
D
A．Ø
pÙ
qB．pÚ
qC．pÙ
qD．Ø
q
4．在一阶逻辑中使用的量词只有个。
A．1B．2C．3D．4
5．Ø
"
xA（x）Û
。
$xA（x）B．"
xØ
A（x）C．$xØ
A（x）D．$xA（x）
6．若|A|=4，则|P（A）|=。
A．4B．8C．16D．64
7．设A、B、C为任意集合，集合的对称差运算不具有的性质是。
A．AÅ
B=BÅ
AB．（AÅ
B）Å
C=BÅ
（AÅ
C）
C．AÅ
A=Æ
D．AÅ
A=A
8．二元关系是。
A．两个集合的笛卡儿积B．序偶的集合
C．映射的集合D．以上都不是
9．下面关于函数的叙述中正确的是。
A．函数一定是满射B．函数一定是单射
C．函数不是满射就单射D．函数是特殊的关系
10．半群中的二元运算一定满足=。
A．交换律B．结合律C．分配律D．幂等律
11．环中有个二元运算。
A．一B．二C．三D．四
12．群与独异点的区别是。
A．满足交换律B．满足结合律
C．每个元素都有逆元D．满足分配律
13．九阶轮图的点色数是。
A．2B．3C．4D．9
14．设N、Q、Z、R分别表示非负整数集、有理数集、整数集和实数集，＋表示数的加法，则下面的代数系统中，不是群。
A
A．<
N，＋>
B．<
Q，＋>
C．<
Z，＋>
D．<
R，＋>
15．简单通路是没有的通路。
A．重复边B．重复顶点C．平行边D．环
16．设个体域为N（非负整数集），下列公式为真的是。
A．$y"
x（xy=1）B．$y"
x（xy=x）
C．"
x$y（x+y=0）D．"
x$y（x>
y）
17．非平凡树一定是。
A．正则图B．二部图C．欧拉图D．哈密顿图
18．环<
R，+，·
>
中的·
运算只要求满足。
A．交换律B．结合律C．分配律D．幂等律
19．集合A上的等价关系与一一对应。
A．集合A的子集B．集合A的划分
C．集合A到A的双射D．集合A与A的单射
20．全序关系一定不是。
A．等价关系B．偏序关系C．线序关系D．整除关系
二、填空题（共10题，每题2分，共20分）
11．设S（x）：
x是计算机学院的学生。
L（x）：
x学离散数学。
则“计算机学院的学生都要学离散数学。
”可符号化为：
__"
x（S（x）®
L（x））_____________________________________。
12．设A={a,b,c}，A上的等价关系R={<
a,b>
<
b,a>
}È
IA，
则商集A/R=____{{a,b},{c}}
13．设B={Æ
}，则幂集P（B）=___________{Æ
{Æ
}}。
14．"
xA（x）Ú
$yB（x,y）的前束范式是____．"
u$v（A（u）Ú
B（x,v））或"
x$y（A（x）Ú
B（u,y））
15．设集合A={0，1}，则A上可定义的二元运算有____16_______个。
16．设A={1，2，3，4}，A上关系R={<
1,3>
3,1>
4,1>
}È
则t（R）=__{<
4,3>
IA
17．设函数f：
N®
N，f=x-1，函数h：
N，h（x）=x2+1，
则复合函数foh（x）=_______（x-1）2+1
18．完全二部图Kr,s（r<
s）的最大度D（Kr,s）=______S____，
最小度d（Kr,s）=_____r___。
19．设一棵树有4个2度顶点，3个3度顶点，其余顶点都是1度顶点，
则该树有_______5___片树叶。
20．命题公式Ø
（p®
q））的成假赋值是__00，01，10，11
三、运算题（共5小题，每小题8分，共40分）
21．求命题公式Ø
（pÙ
q）Ù
（qÚ
r）的主析取范式，并指出其类型。
解：
r）Û
（Ø
pÚ
q）Ù
r）
Û
pÙ
r）Ú
qÛ
qÚ
（（Ø
pÚ
p）Ù
qÙ
rÚ
r））
Ø
r）Ú
r）
Ú
（pÙ
（pÙ
r）
该公式是可满足式
22．设A={a,b,c,d,e,f}，A上的偏序关系：
R={<
a,d>
a,c>
a,f>
a,e>
b,d>
b,e>
c,e>
c,f>
IA
画出该偏序关系的哈斯图，并求A的极大元、极小元、最大元和最小元。
极大元为d、e、f；
极小元为a；
无最大元；
最小元为a
23．设个体域D={a,b,c}，消去一阶公式"
x（F（x）®
$yG（y））中的量词，并在下述解释下求其真值：
F（a）=F（b）=1,F（c）=0，G（a）=1，G（b）=G（c）=0。
解：
$yG（y））Û
$xF（x）®
$yG（y）
（F（a）Ú
F（b）Ú
F（c））®
（G（a）Ú
G（b）Ú
G（c））
（1Ú
1Ú
0）®
0Ú
0）Û
1®
1Û
1
24．画一棵叶带权为1、2、3、3、5、6、7的最优二元树T，并计算树权W（T）。
W（T）=71
25．设Z为整数集合，V=<
Z,*>
，*是二元运算，定义为：
x*y=x+y-xy
说明V是含幺半群而不是群。
（1）*运算在Z上封闭：
（2）*运算可结合，对任意a、b、cÎ
Z
a*（b*c）=a*（b+c-bc）=a+b+c-bc-a（b+c-bc）=a+b+c-ab-ac-bc+abc
（a*b）*c=（a+b-ab）*c=a+b-ab+c-（a+b-ab）c=a+b+c-ab-ac-bc+abc
所以a*（b*c）=（a*b）*c
（3）*运算的幺元是0
（4）任意xÎ
Z，x*1=1*x=1，所以1是零元，它没有逆元。
由上述可知，故<
是含幺半群而不是群。
四、证明题（共3小题，共20分）
26（10分）．在一阶逻辑中构造下面推理的证明：
前提：
G（x）），"
x（G（x）Ú
R（x）），$xØ
R（x）
结论：
$xØ
F（x）
（10分）证:
①$xØ
R（x）前提引入
②Ø
R（c）①EI
③"
R（x））前提引入
④G（c）Ú
R（c）③UI
⑤G（c）②④析取三段论
⑥"
G（x））前提引入
⑦F（c）®
G（c）⑥UI
⑧Ø
F（c）⑤⑦拒取式
⑨$xØ
F（x）⑧EG
27（5分）．证明，若非空集合A上的关系R和S是反对称的，则RÇ
S也是反对称的。
证:
任取<
x,y>
，x≠y
<
Î
RÇ
SÞ
RÙ
y,x>
S。
故RÇ
S是对称的。
28（5分）．若无向图G中恰有两个奇度顶点，证明这两个奇度顶点必连通。
用反证法。
假设G中两个奇度顶点u和v不连通，则u和v分别处于G的两不同连通分支G1和G2中，因而G1和G2作为独立的图时，均只有一个奇度顶点，这是不可能的，故这两个奇度顶点必连通。
答案
1C2B3D4B5C6C7D8B9D10B
11B12C13B14A15A16B17B18B19B20A
11．"
L（x））12．{{a,b},{c}}
13．{Æ
}}14．"
B（u,y））
15．1616．{<
17．（x-1）2+118．s,r
19．520．00，01，10，11
21．解：
22．解：
23．解：
24．解：
25．解：
26（10分）证:
27（5分）证:
28（5分）
升级会员 