离散数学试题60学时Word文档下载推荐.docx
《离散数学试题60学时Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《离散数学试题60学时Word文档下载推荐.docx（18页珍藏版）》请在冰点文库上搜索。
（1）画出R的关系图;
（2）写成R的关系矩阵;
（3）说明R是否具有自反、反自反、对称、反对称、传递性质.
4.求命题公式（P（Q∧R））∧（P（QR））的主合取范式.
5.设集合A={1,2,3,6,9,18},≤为整除关系.
（1）画出A,≤的哈斯图;
（2）求子集B={3,6,9}的极大元、极小元、最大元、最小元.
三、证明题（本大题共2小题,每小题10分,共20分）
1.设（G1,
）,（G2,
）都是群（G,
）的子群.
（1）证明:
（G1∩G2,
）也是（G1,
）及（G,
（2）若|G1|=5,|G2|=6,问|G1∩G2|是多少？
2.给定集合A={a,b,c},（A）是A的幂集,（（A）,∪）为代数系统,在（A）上又定义二元关系R如下:
XRY当且仅当X∩{b}=Y∩{b},X,Y（A）.
∩、∪分别为集合的并、交运算,求证:
（1）R是（A）上的等价关系;
（2）R是（A）上的关于∪的同余关系;
（3）求商集（A）/R.
四、应用题（本大题共2小题,每小题10分,共20分）
1.对下面推理进行符号化,并构造其证明.
会操作计算机的人都认识26个英文字母;
文盲都不认识26个英文字母;
有的文盲是很聪明的.所以有的很聪明的人不会操作计算机.
（个体域D:
所有人的集合.设F（x）:
x会操作计算机,G（x）:
x认识26个英文字母,H（x）:
x是文盲,R（x）:
x是很聪明的）
2.设有n个人P1,P1,…,Pn,其中某些人在做决策时能够互相影响,而这种影响一般是单方面的,即如果Pi影响Pj,那么Pj不一定影响Pi.并且每个人不影响他自己.另外可以考虑二级影响,即如果存在一条从Pi到Pj长度为2的路径,则Pi对Pj有二级影响.类似地,如果存在一条从Pi到Pj长度为r的路径,那么Pi对Pj有r级影响.
如图给出了一个设计组中6个成员之间描述影响关系的有向图.问设计组中哪些不同成员之间有二级影响?
保证设计组中成员没有影响的最小级数是多少？
离散数学答案A
1.设P:
你走,Q:
我留,R:
她留.则两命题分别符号化为：
PQ∧R,Q∨RP.
由于PQ∧RP∨（Q∧R）
P∨（Q∨R）
（Q∨R）P.
故二者具有相同的逻辑含义.
2.
（1）x（R（x）P（x））∨G（5）（R（3）P（3））∧（R（6）P（6））∧（R（9）P（9））∨G（5）
（T∧F∧F）∨F
F.
（2）x（P（x）∨G（x））（P（3）∨G（3））∨（（P（6）∨G（6））∨（（P（9）∨G（9））
（T∨F）∨（F∨T）∨（F∨T）
T.
3.由于MR=
.
故当m=2,n=3时,Rm=Rn.其传递闭包对应的矩阵为：
=
+
对称闭包对应的矩阵为:
Ms=
4.
（1）f（xy）=（xy）2=x2y2=f（x）f（y）,因而是同态.
（2）f（xy）=xy≠（x）（y）=f（x）f（y）,不是同态.
（3）f（xy）=[xy]≠[x][y]=f（x）f（y）,不是同态.
5.
（1）由握手定理可得,3n=2m,与条件2n−3=m联立解得n=6,m=9.
（2）在同构的意义下能画出G的一个二部图K3,3.
6.
（1）f既不是单射，也不是满射；
g是单射，但不是满射,h是满射，但不是单射，f,g,h都不是双射。
（2）h
f:
AD,且h
f（x）=
既不是单射，也不是满射,当然不是双射,从而无反函数。
7.画出G的对偶图G*如图所示。
由于G*中有4个3度结点,故G*不是欧拉图.
而在G*中,任意两个结点的度数之和大于结点数5,由奥尔定理可知,G*是哈密顿图.
1.（A）={,{},{{a,b}},{,{a,b}}},
（B）={,{a},{{}},{a,{}}},（A）∩（B）={}.
2.在群（G,）中,元素a为单位元，故其阶为1，逆元为a;
而b2=a,故元素b的阶为2,逆元为b;
由于c2=b,c3=d,c4=a,故元素c的阶为4,逆元为c3=d;
由于d2=b,d3=c,d4=a,故元素d的阶为4,逆元为d3=c.
G的全部子群:
{a},<
b>
<
c>
=<
d>
（1）略;
（2）MR=
;
（3）R具有自反性、反对称、不具有反自反、对称、传递性质.
4.（P（Q∧R））∧（P（QR））（P∨（Q∧R））∧（P∨（Q∨R））
（P∨Q）∧（P∨R））∧（P∨（Q∨R））
（P∨Q）∨（R∨R）∧（P∨R））∨（Q∨Q）∧（P∨（Q∨R））
（P∨Q∨R）∧（P∨Q∨R）∧（P∨Q∨R）∨（P∨Q∨R）∧（P∨Q∨R）
（0,4,5,6）.
5.
（1）画出A,≤的哈斯图;
（2）子集B={3,6,9}的极大元为9,6、极小元3、
无最大元、最小元为3.
1.
（1）a,bG1∩G2,则a,bG1,a,bG2,由于（G1,
）的子群,则
a
b1G1,G2,故a
b1G1∩G2.
（G1∩G2,
（2）由于（G1∩G2,
）是（G1,
）的子群,故有|G1∩G2|1,又
|G1∩G2|||G1|,|G1∩G2|||G2|
故|G1∩G2|=1.
2.
（1）R在（A）上自反性、对称性显然.其传递性为:
若XRY且YRZ,则有X∩{b}=Y∩{b},Y∩{b}=Z∩{b},从而有X∩{b}=Z∩{b},故XRZ.
（2）由于R是（A）上的等价关系,若XRY,则X∩{b}=Y∩{b}.对于任意的Z（A）,由集合的分配律,有
（X∪Z）∩{b}=（X∩{b}）∪（Z∩{b}）=（Y∩{b}）∪（Z∩{b}）=（Y∪Z）∩{b}.
故（X∪Z）R（Y∪Z）.因为集合满足交换律,类似地,有（Z∪X）R（Z∪Y）,故R是（A）上的关于∪的同余关系.
（3）由（A）={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}},按等价关系R可得其等价类为:
{,{a},{c},{a,c}}，{{b},{a,b},{b,c},{a,b,c}},故商集
（A）/R={[{a}],[{b}]}.
四、应用题（本大题共2小题,每小题10分,共20分）
1.符号化：
设F（x）:
x是很聪明的。
前提：
x（F（x）G（x））,x（H（x）G（x））,x（H（x）∧R（x））,
结论：
x（R（x）∧F（x））.
证明：
序号
断言
依据
1
x（H（x）∧R（x））
P
2
H（c）∧R（c）
T,1,ES
3
H（c）
T,2,简化式
4
R（c）
5
x（H（x）G（x））
6
H（c）G（c）
T,5,US
7
G（c）
T,3,6,假言推理
8
x（F（x）G（x））
9
F（c）G（c）
T,8,US
10
F（c）
T,7,9,拒取式
11
R（c）∧F（c）
T,4,10,合取式
12
x（R（x）∧F（x））
T,11,EG
2.图的邻接矩阵为
A＝
则A2＝
A3＝
A4＝0.
故设计组中不同成员之间有二级影响的有序对是:
P3,P5,P4,P5,P6,P2,P6,P5.设计组中成员没有影响的最小级数是:
r＝4.
离散数学试题B
1.将下列自然语言按要求进行符号化.
（1）人不犯我,我不犯人;
人若犯我,我必犯人.（用命题逻辑）
（2）会叫的狗未必咬人.（用谓词逻辑）
2.如果个体域是集合{a,b,c},试消去公式xy（x+y=0）中的量词.
3.设A={a,b,c},A上二元关系R={a,a,a,c,b,a},求关系R的自反闭包、对称闭包和传递闭包.
4.设A＝{a,b},S是A上的所有函数集合,S＝{f1,f2,f3,f4},其中
f1:
a
a,b
b;
f2:
a,b
a;
f3:
b,b
f4:
bb
a.
于是（S,
）是一个代数系统,
是函数的合成运算,试构造出运算表,考察运算
是否有单位元,哪些元素有逆元.
5.在有21条边的无向图G中,有3个4度结点,其余均为3度结点,问无向图共有多少个结点.
6.在整数集Z上定义下列运算:
（1）a
b=2ab;
（2）a
b=a+b+2;
（3）a
b=a+2b.问整数集Z关于哪些运算构成代数系统？
哪些运算能构成半群？
哪些运算能构成群？
（对每种情况给出具体的理由）
7.分别构造满足下列条件的图.
（1）画一个有一条欧拉回路和一条汉密顿回路的图.
（2）画一个有一条欧拉回路但没有汉密顿回路的图.
（3）画一个没有欧拉回路但有一条汉密顿回路的图.
1.设P表示“今天天气好”，Q表示“我们去旅游”.试用最简单明了的汉语描述下面公式所表达的含义:
（¬
P∨Q）→（P∧¬
Q）∨¬
Q→¬
P）.
2.设S=Q×
Q,其中Q为有理数集合,定义S上的二元运算*,
a,b,x,y∈S,a,b*x,y=ax,ay+b,
（1）求3,4*1,2.
（2）已知1,3*a,b=5,1,求a,b.
（3）*是可交换的吗？
是可结合的吗？
3.设集合A={1,2,3,4,5},A上的等价关系R的等价类为:
M1={1,2,3},M2={4,5}.
（1）写出等价关系R;
（2）写出R的关系矩阵;
（3）画出关系图.
4.求公式（P∨Q）（Q∧R）的主析取范式.
5.设A={a,b,c,d,e},R为A上的关系,R={a,d,a,c,a,b,a,e,b,e,c,e,d,e}∪IA,试画（A,R）的哈斯图,并求A中的最大元,最小元,极大元,极小元.
1.设G={2m3n|m,nQ}（Q是有理数集合）,“*”是数的乘法.
（1）证明（G,*）是群;
（2）设映射f:
GG,f（2m3n）=2m,证明f是群（G,*）上的自同态映射.
2.
（1）若函数f:
TU,f是单射;
函数g,h:
ST,满足f
g=f
h,证明：
g=h.
（2）给出函数f,g,h的实例,f:
TU,g,h:
ST,f
h,但g≠h.
没有不守信用的人是可信赖的;
有些可以信赖的人是受过教育的人;
因此有些受过教育的人是守信用的.
（个体域D:
x是守信用的人;
G（x）:
x是可信赖的人;
H（x）:
x是受过教育的人.）
2.给定图D如图所示.
（1）用矩阵的方法确定D中长度为4的路径的数目,其中有几条回路？
（2）写出D的可达矩阵.
离散数学答案B
（1）设P:
人犯我,Q:
我犯人,则命题符号化为：
（PQ）∧（PQ）.
（2）设特性谓词D（x）:
x是狗,F（x）:
x会叫,G（x）:
x咬人.则命题符号化为
x（D（x）∧F（x）∧G（x））.
2.xy（x+y=0）（（a+a=0）∨（a+b=0）∨（a+c=0））∧（（b+a=0）∨（b+b=0）∨（b+c=0））
∧（（c+a=0）∨（c+b=0）∨（c+c=0））.
3.R的自反闭包为：
r（R）={a,a,b,b,c,c,a,c,b,a}.
对称闭包s（R）={a,a,a,c,c,a,b,a,a,b}.
传递闭包t（R）={a,a,a,c,b,a,b,c}.
4.运算表为：
f1
f2
f3
f4
其中：
f1是单位元,f4有逆元，且f4的逆元为f4。
5.由握手定理可得
34+3（n3）=221
解得n=13.
6.整数集Z关于这三类运算都构成代数系统。
能构成半群的运算为：
，*。
*。
7.
（1）
（2）（3）
1.化简命题公式
（¬
P）¬
P∨Q）∨（P∧¬
（Q∨¬
P）
（P∧¬
Q）∨（P∧¬
Q）∨（¬
Q∧P）
Q）。
简单汉语描述：
今天天气好,我们不去旅游。
2.3,4*1,2=31,32+4=3,10.
（2）因为1,3*a,b=1a,1b+3=5,1,故a=5,b=2.
（3）易于验证*是不可交换的；
但却是可结合的。
3.
（1）等价关系为
R=M1M1∪M2M2
={1,1,2,2,3,3,1,2,1,3,2,1,2,3,3,1,3,2}
∪{4,4,5,5,4,5,5,4}
=IA∪{1,2,1,3,2,1,2,3,3,1,3,2,4,5,5,4}
（2）R的关系矩阵为：
MR=
。
（3）关系图：
4.（P∨Q）（Q∧R）（P∨Q）∨（Q∧R）
（P∧Q）∨（Q∧R）
（（P∧Q）∧（R∨R））∨（（P∨P）∧（Q∧R））
（P∧Q∧R）∨（P∧Q∧R）∨（P∧Q∧R）∨（P∧Q∧R）
m0∨m1∨m3∨m7
5.（A,R）的哈斯图如图所示。
A中的最大元与极大元都为e,最小元与极小元都为a.
1.
（1）验证（G,*）满足群的条件.由于有理数满足结合律,故（G,*）满足结合律;
单位元为:
1;
对于G的任意元素2m3n,逆元为:
2m3n.故（G,*）是群。
（2）对于G的任意元素2m3n,2k3r,有
f（2m3n2k3r）=f（2m+k3n+r）=2m+k=2m2k=f（2m3n）f（2k3r）,
故f是群（G,*）上的自同态映射.
2.
（1）对于任意的xS,f
g（x）=f
h（x）,即f（g（x））=f（h（x））,由于f是单射,故g（x）=h（x）.从而有g=h.
设S={1},T={a,b},U={0},f（X）=0;
g
（1）=a,h
（1）=b.则f
g（x）=f（g（x））=0，f
h（x）=f（h（x））=0,但g≠h.
1.设F（x）:
x是受过教育的人.符号化为
x（F（x）∧G（x））,x（G（x）∧H（x））,
x（H（x）∧F（x））.
x（G（x）∧H（x））
G（c）∧H（c）
x（F（x）∧G（x））
P
x（F（x）∨G（x））
T,5,置换
F（c）∨G（c）
T,6,US
T,3,7析取三段论
F（c）∧H（c）
T,4,8,合取式
x（H（x）∧F（x））
T,9,EG
2.图D的邻接矩阵为：
A=
，易于计算A2=
，A3=
，A4=
D中长度为4的路径的数目为：
46；
其中回路有：
13.
可达矩阵为：
P=
升级会员 