完整版离散数学期末考试试题及答案推荐文档Word文档格式.docx
- 文档编号:8050120
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:43
- 大小:99.46KB
完整版离散数学期末考试试题及答案推荐文档Word文档格式.docx
《完整版离散数学期末考试试题及答案推荐文档Word文档格式.docx》由会员分享,可在线阅读,更多相关《完整版离散数学期末考试试题及答案推荐文档Word文档格式.docx(43页珍藏版)》请在冰点文库上搜索。
(8)P(a)∧R(a)
T
(2)(7),I
(9)∃x(P(x)∧R(x))
T(8),EG
(10)Q(y)∧∃x(P(x)∧R(x))
T(6)(9),I
四、某班有25名学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。
而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。
解:
A,B,C分别表示会打排球、网球和篮球的学生集合。
则
|A|=12,|B|=6,|C|=14,|A∩C|=6,|B∩C|=5,|A∩B∩C|=2。
先求|A∩B|。
∵6=|(A∪C)∩B|=|(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-
|A∩B∩C|=|(A∩B)|+5-2,∴|(A∩B)|=3。
于是|A∪B∪C|=12+6+14-6-5-3+2=20。
不会打这三种球的人数25-20=5。
五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C)(10分)。
∵x∈A-(B∪C)⇔x∈A∧x∉(B∪C)
⇔x∈A∧(x∉B∧x∉C)
⇔(x∈A∧x∉B)∧(x∈A∧x∉C)
⇔x∈(A-B)∧x∈(A-C)
⇔x∈(A-B)∩(A-C)
∴A-(B∪C)=(A-B)∩(A-C)
六、已知R、S是N上的关系,其定义如下:
R={<
x,y>
|x,y∈N∧y=x2},S={<
|x,y∈N∧y=x+1}。
求R-1、R*S、S*R、R{1,2}、S[{1,2}](10分)。
解:
R-1={<
y,x>
|x,y∈N∧y=x2}R*S={<
|x,y∈N∧y=x2+1}
S*R={<
|x,y∈N∧y=(x+1)2},R{1,2}={<
1,1>
,<
2,4>
},S[{1,2}]
={1,4}。
七、设R={<
a,b>
b,c>
c,a>
},求r(R)、s(R)和t(R)(15分)。
r(R)={<
a,a>
b,b>
c,c>
}s(R)={<
b,a>
c,b>
a,c>
}
R2=R5={<
}R3={<
}R4={<
}t(R)
={<
,<
八、证明整数集I上的模m同余关系R={<
|x≡y(modm)}是等价关系。
其中,x≡y(modm)的含义是x-y可以被m整除(15分)。
1)∀x∈I,因为(x-x)/m=0,所以x≡x(modm),即xRx。
2)∀x,y∈I,
若xRy,则x≡y(modm),即(x-y)/m=k∈I,所以(y-x)/m=-
k∈I,所以y≡x(modm),即yRx。
3)∀x,y,z∈I,若xRy,yRz,则(x-y)/m=u∈I,(y-z)/m=v∈I,于是(x-z)/m=(x-y+y-z)/m=u+v∈I,因此xRz。
九、若f:
A→B和g:
B→C是双射,则(gf)-1=f-1g-1(10分)。
因为f、g是双射,所以gf:
A→C是双射,所以gf有逆函数(gf)-1:
C→A。
同理可推f-1g-1:
C→A是双射。
因为<
∈f-1g-1⇔存在z(<
x,z>
∈g-1∧<
z,y>
∈f-1)⇔存在z(<
y,z>
∈f∧<
z,x>
∈g)⇔<
∈gf⇔<
∈(gf)-1,所以(gf)-1=f-1g-1。
离散数学试题(B卷答案2)
1)((P∨Q)∧⌝(⌝P∧(⌝Q∨⌝R)))∨(⌝P∧⌝Q)∨(⌝P∧⌝R)⇔T
左端⇔((P∨Q)∧(P∨(Q∧R)))∨⌝((P∨Q)∧(P∨R))(摩根律)
⇔((P∨Q)∧(P∨Q)∧(P∨R))∨⌝((P∨Q)∧(P∨R))(分配律)
⇔((P∨Q)∧(P∨R))∨⌝((P∨Q)∧(P∨R))(等幂律)
⇔T(代入)
2)∀x∀y(P(x)→Q(y))⇔⇔(∃xP(x)→∀yQ(y))
∀x∀y(P(x)→Q(y))⇔∀x∀y(⌝P(x)∨Q(y))
⇔∀x(⌝P(x)∨∀yQ(y))
⇔∀x⌝P(x)∨∀yQ(y)
⇔⌝∃xP(x)∨∀yQ(y)
⇔(∃xP(x)→∀yQ(y))
二、求命题公式(⌝P→Q)→(P∨⌝Q)的主析取范式和主合取范式(10分)
(⌝P→Q)→(P∨⌝Q)⇔⌝(⌝P→Q)∨(P∨⌝Q)
⇔⌝(P∨Q)∨(P∨⌝Q)
⇔(⌝P∧⌝Q)∨(P∨⌝Q)
⇔(⌝P∨P∨⌝Q)∧(⌝Q∨P∨⌝Q)
⇔(P∨⌝Q)
⇔M1
⇔m0∨m2∨m3
1)(P→(Q→S))∧(⌝R∨P)∧Q⇒R→S
(1)R
(2)⌝R∨P(3)P(4)P→(Q→S)(5)Q→S
(6)Q
(7)S
(8)R→S
2)∃x(A(x)→∀yB(y)),∀x(B(x)→∃yC(y))∀xA(x)→∃yC(y)。
(1)∃x(A(x)→∀yB(y))P
(2)A(a)→∀yB(y)
(3)∀x(B(x)→∃yC(y))
(4)∀x(B(x)→C(c))
T(3),ES
(5)B(b)→C(c)
T(4),US
(6)A(a)→B(b)
T
(2),US
(7)A(a)→C(c)
T(5)(6),I
(8)∀xA(x)→C(c)
T(7),UG
(9)∀xA(x)→∃yC(y)
四、只要今天天气不好,就一定有考生不能提前进入考场,当且仅当所有考生提前进入考场,考试才能准时进行。
所以,如果考试准时进行,那么天气就好(15分)。
解设P:
今天天气好,Q:
考试准时进行,A(e):
e提前进入考场,个体域:
考生的集合,则命题可符号化为:
⌝P→∃x⌝A(x),∀xA(x)↔QQ→P。
(1)⌝P→∃x⌝A(x)P
(2)⌝P→⌝∀xA(x)T
(1),E
(3)∀xA(x)→PT
(2),E
(4)∀xA(x)↔QP
(5)(∀xA(x)→Q)∧(Q→∀xA(x))T(4),E
(6)Q→∀xA(x)T(5),I
(7)Q→PT(6)(3),I
五、已知A、B、C是三个集合,证明A∩(B∪C)=(A∩B)∪(A∩C)(10分)
∵x∈A∩(B∪C)⇔x∈A∧x∈(B∪C)⇔x∈A∧(x∈B∨x∈C)⇔(x∈
A∧x∈B)∨(x∈A∧x∈C)⇔x∈(A∩B)∨x∈A∩C⇔x∈(A∩B)∪(A∩C)
∴A∩(B∪C)=(A∩B)∪(A∩C)
六、A={x1,x2,x3},B={y1,y2},R={<
x1,y1>
<
x2,y2>
x3,y2>
},求其关系矩阵及关系图(10分)。
2,1>
2,5>
2,4>
3,4>
4,4>
5,2>
},求r(R)、s(R)和t(R),并作出它
们及R的关系图(15分)。
1,1>
2,2>
<
3,3>
5,5>
1,2>
4,2>
4,3>
R2=R5={<
5,1>
5,4>
R3={<
R4={<
}t(R)={<
八、设R1是A上的等价关系,R2是B上的等价关系,A≠∅且B≠∅。
关系R满足:
x1,y1>
x2,y2>
>
∈R⇔<
x1,x2>
∈R1且<
y1,y2>
∈R2,证明R是A×
B上的等价关系
(10分)。
证明对任意的<
∈A×
B,由R1是A上的等价关系可得<
x,x>
∈R1,由R2是B上的等价关系可得<
y,y>
∈R2。
再由R的定义,有<
∈R,所以R是自反的。
对任意的<
、<
u,v>
B,若<
R<
,则<
x,u>
∈R1且
y,v>
由R1对称得<
u,x>
∈R1,由R2对称得<
v,y>
再由R的定义,有
∈R,即<
,所以R是对称的。
s,t>
且<
,则
∈R2,<
u,s>
v,t>
由<
∈R1、<
∈R1及R1的传递性得<
x,s>
∈R1,由<
∈R2、<
∈R2及R2的传递性得<
y,t>
∈R1。
再由R的定义,有<
,所以R是传递的。
综上可得,R是A×
B上的等价关系。
九、设f:
A→B,g:
B→C,h:
C→A,证明:
如果hgf=IA,fhg=IB,gfh=IC,则f、g、h均为双射,并求出f-1、g-1和h-1(10分)。
解因IA恒等函数,由hgf=IA可得f是单射,h是满射;
因IB恒等函数,由fhg=IB可得g是单射,f是满射;
因IC恒等函数,由gfh=IC可得h是单射,g是满射。
从而f、g、h均为双射。
由hgf=IA,得f-1=hg;
由fhg=IB,得g-1=fh;
由gfh=IC,得h-1=gf。
离散数学试题(B卷答案3)
一、(10分)判断下列公式的类型(永真式、永假式、可满足式)?
(写过程)1)P→(P∨Q∨R)2)⌝((Q→P)∨⌝P)∧(P∨R)3)((⌝P∨Q)→R)→((P∧Q)∨R)
1)重言式;
2)矛盾式;
3)可满足式
二、(10分)求命题公式(P∨(Q∧R))→(P∨Q∨R)的主析取范式,并求成真赋值。
(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)∨(P∨Q))∨(⌝P∧⌝R)∨R
⇔1∨((⌝P∧⌝R)∨R)⇔1
⇔m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7
该式为重言式,全部赋值都是成真赋值。
三、(10分)证明((P∧Q∧A)→C)∧(A→(P∨Q∨C))⇔(A∧(P↔Q))→C
((P∧Q∧A)→C)∧(A→(P∨Q∨C))⇔(⌝(P∧Q∧A)∨C)∧(⌝A∨(P∨Q∨C))
⇔((⌝P∨⌝Q∨⌝A)∨C)∧((⌝A∨P∨Q)∨C)
⇔((⌝P∨⌝Q∨⌝A)∧(⌝A∨P∨Q))∨C
⇔⌝((⌝P∨⌝Q∨⌝A)∧(⌝A∨P∨Q))→C
⇔(⌝(⌝P∨⌝Q∨⌝A)∨⌝(⌝A∨P∨Q))→C
⇔((P∧Q∧A)∨(A∧⌝P∧⌝Q))→C
⇔(A∧((P∧Q)∨(⌝P∧⌝Q)))→C
⇔(A∧((P∨⌝Q)∧(⌝P∨Q)))→C
⇔(A∧((Q→P)∧(P→Q)))→C
⇔(A∧(P↔Q))→C
四、(10分)个体域为{1,2},求∀x∃y(x+y=4)的真值。
∀x∃y(x+y=4)⇔∀x((x+1=4)∨(x+2=4)
⇔((1+1=4)∨(1+2=4)∧((2+1=4)∨(2+2=4)
⇔(0∨0)∧(0∨1)⇔0∧1⇔0
五、(10分)对于任意集合A,B,试证明:
P(A)∩P(B)=P(A∩B)
∀x∈P(A)∩P(B),x∈P(A)且x∈P(B),有x⊆A且x⊆B,从而x⊆A∩B,x∈P(A∩B),由于上述过程可逆,故P(A)∩P(B)=P(A∩B)
六、(10分)已知A={1,2,3,4,5}和R={<
1,2>
2,1>
2,3>
3,4>
5,4>
},求r(R)、s(R)和t(R)。
r(R)
2,2>
3,3>
4,4>
5
,5>
s(R)={<
3,2>
4,3>
4,5>
t(R)
1,3>
1
,4>
七、(10分)设函数f:
R×
R→R×
R,R为实数集,f定义为:
f(<
)=<
x+y,x-y>
。
1)证明f是双射。
1)∀<
∈R×
R,若f(<
)=f(<
),即<
x1+y1,x1-y1>
=<
x2+y2,x2-y2>
,则x1+y1=x2+y2且x1-y1=x2-y2得x1=x2,y1=y2从而f是单射。
2)∀<
p,q>
R,由f(<
,通过计算可得x=(p+q)/2;
y=(p-q)
/2;
从而<
的原象存在,f是满射。
八、(10分)<
G,*>
是个群,u∈G,定义G中的运算“∆”为a∆b=a*u-1*b,对任意a,b∈G,求证:
G,∆>
也是个群。
1)∀a,b∈G,a∆b=a*u-1*b∈G,运算是封闭的。
2)∀a,b,c∈G,(a∆b)∆c=(a*u-1*b)*u-1*c=a*u-1*(b*u-1*c)=a∆(b∆c),运算是可结合的。
3)∀a∈G,设E为∆的单位元,则a∆E=a*u-1*E=a,得E=u,存在单位元u。
4)
∀a∈G,a∆x=a*u-1*x=E,x=u*a-1*u,则x∆a=u*a-1*u*u-1*a=u=E,每个元素都有逆元。
所以<
九、(10分)已知:
D=<
V,E>
,V={1,2,3,4,5},E={<
1,4>
3,5>
5,1>
},求D的邻接距阵A和可达距阵P。
1)D的邻接距阵A和可达距阵P如下:
A=
P=
十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。
最优二叉树为
权=(2+4)×
4+6×
3+12×
2+(8+10)×
3+14×
2=148
离散数学试题(B卷答案4)
左端⇔((P∨Q)∧(P∨(Q∧R)))∨⌝((P∨Q)∧(P∨R))(摩根律)⇔((P∨Q)
∧(P∨Q)∧(P∨R))∨⌝((P∨Q)∧(P∨R))(分配律)⇔((P∨Q)∧(P∨R))∨⌝((P∨Q)
∧(P∨R))(等幂律)⇔T(代入)2)
∀x(P(x)→Q(x))∧∀xP(x)⇔∀x(P(x)∧Q(x))
∀x(P(x)→Q(x))∧∀xP(x)⇔∀x((P(x)→Q(x)∧P(x))⇔∀x((⌝P(x)∨Q(x)
∧P(x))⇔∀x(P(x)∧Q(x))⇔∀xP(x)∧∀xQ(x)⇔∀x(P(x)∧Q(x))
(⌝P→Q)→(P∨⌝Q)⇔⌝(⌝P→Q)∨(P∨⌝Q)⇔⌝(P∨Q)∨(P∨⌝Q)⇔(⌝P∧⌝Q)
∨(P∨⌝Q)⇔(⌝P∨P∨⌝Q)∧(⌝Q∨P∨⌝Q)⇔(P∨⌝Q)⇔M1⇔m0∨m2∨m3三、推理证明题(10分)
(1)R附加前提
(2)⌝R∨PP
(3)PT
(1)
(2),I
(4)P→(Q→S)P
(5)Q→ST(3)(4),I
(6)QP
(7)ST(5)(6),I
(8)R→SCP
2)∀x(P(x)∨Q(x)),∀x⌝P(x)⇒∃xQ(x)
(1)∀x⌝P(x)P
(2)⌝P(c)T
(1),US
(3)∀x(P(x)∨Q(x))P
(4)P(c)∨Q(c)T(3),US
(5)Q(c)T
(2)(4),I
(6)∃xQ(x)T(5),EG
四、例5在边长为1的正方形内任意放置九个点,证明其中必存在三个点,使得由它们组成的三角形(可能是退化的)面积不超过1/8(10分)。
把边长为1的正方形分成四个全等的小正方形,则至少有一个小正方形内有三个点,它们组成的三角形(可能是退化的)面积不超过小正方形的一半,即1/8。
六、π={A1,A2,…,An}是集合A的一个划分,定义
|a、b∈Ai,I=1,2,…,n},则R是A上的等价关系(15分)。
∀a∈A必有i使得a∈Ai,由定义知aRa,故R自反。
∀a,b∈A,若aRb,则a,b∈Ai,即b,a∈Ai,所以bRa,故R对称。
∀a,b,c∈A,若aRb且bRc,则a,b∈Ai及b,c∈Aj。
因为i≠j时Ai∩Aj=Φ,故i=j,即a,b,c∈Ai,所以aRc,故R传递。
总之R是A上的等价关系。
七、若f:
A→B是双射,则f-1:
B→A是双射(15分)。
对任意的x∈A,因为f是从A到B的函数,故存在y∈B,使
x,y>
∈f,<
y,x>
∈f-1。
所以,f-1是满射。
对任意的x∈A,若存在y1,y2∈B,使得<
y1,x>
∈f-1且<
y2,x>
∈f-1,则有
x,y1>
∈f且<
x,y2>
∈f。
因为f是函数,则y1=y2。
所以,f-1是单射。
因此f-1是双射。
八、设<
是群,<
A,*>
和<
B,*>
是<
的子群,证明:
若A∪B=G,则A=G
或B=G(10分)。
证明假设A≠G且B≠G,则存在a∈A,a∉B,且存在b∈B,b∉A(否则对任意的a∈A,a∈B,从而A⊆B,即A∪B=B,得B=G,矛盾。
)
对于元素a*b∈G,若a*b∈A,因A是子群,a-1∈A,从而a-1*(a*b)=b∈A,所以矛盾,故a*b∉A。
同理可证a*b∉B,综合有a*b∉A∪B=G。
综上所述,假设不成立,得证A=G或B=G。
九、若无向图G是不连通的,证明G的补图G是连通的(10分)。
证明设无向图G是不连通的,其k个连通分支为G1、G2、…、Gk。
任取结点u、
v∈G,若u和v不在图G的同一个连通分支中,则[u,v]不是图G的边,因而[u,v]是图G的边;
若u和v在图G的同一个连通分支中,不妨设其在连通分支Gi(1≤i≤k)
中,在不同于Gi的另一连通分支上取一结点w,则[u,w]和[w,v]都不是图G的边,
,因而[u,w]和[w,v]都是G的边。
综上可知,不管那种情况,u和v都是可达的。
由u和v的任意性可知,G是连通的。
离散数学试题(B卷答案5)
一、(10分)求命题公式⌝(P∧Q)↔⌝(⌝P→R)的主合取范式。
⌝(P∧Q)↔⌝(⌝P→R)⇔(⌝(P∧Q)→⌝(⌝P→R))∧(⌝(⌝P→R)→⌝(P∧Q))
⇔((P∧Q)∨(⌝P∧⌝R))∧((P∨R)∨(⌝P∨⌝Q))
⇔(P∧Q)∨(⌝P∧⌝R)
⇔(P∨⌝R)∧(Q∨⌝P)∧(Q∨⌝R)
⇔(P∨Q∨⌝R)∧(P∨⌝Q∨⌝R)∧(⌝P∨Q∨R)∧(⌝P∨Q∨⌝R)
⇔
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整版 离散数学 期末 考试 试题 答案 推荐 文档