离散数学试题60学时Word文档下载推荐.docx
- 文档编号:3541332
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:18
- 大小:107.18KB
离散数学试题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=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 试题 60 学时