完整版离散数学期末考试试题及答案推荐文档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）
⇔
升级会员 