离散数学试题(B卷答案1）
一、证明题（10分）
1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R
证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)
?((?P∧?Q)∧R))∨((Q∨P)∧R)
?(?(P∨Q)∧R)∨((Q∨P)∧R)
?(?(P∨Q)∨(Q∨P))∧R
?(?(P∨Q)∨(P∨Q))∧R
?T∧R(置换)?R
2) ?x (A(x)→B(x))??xA(x)→?xB(x)
证明：?x(A(x)→B(x))??x(?A(x)∨B(x))
??x?A(x)∨?xB(x)
???xA(x)∨?xB(x)
??xA(x)→?xB(x)
二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。
证明：(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∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R)
?m0∨m1∨m2∨m7
?M3∨M4∨M5∨M6
三、推理证明题（10分）
1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P
(2) ?E→(A∧?B) P
(3) (C∨D)→(A∧?B) T(1)(2)，I
(4) (A∧?B)→(R∨S) P
(5) (C∨D)→(R∨S) T(3)(4)， I
(6) C∨D P
(7) R∨S T(5)，I
2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x))
证明(1)?xP(x) P
(2)P(a) T(1)，ES
(3)?x(P(x)→Q(y)∧R(x)) P
(4)P(a)→Q(y)∧R(a) T(3)，US
(5)Q(y)∧R(a) T(2)(4)，I
(6)Q(y) T(5)，I
(7)R(a) T(5)，I
(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={
解：R-1={
R*S={
S*R={
七、设R={
解：r(R)={
s(R)={
R2= R5={
R3={
R4={
t(R)={ c>} 八、证明整数集I上的模m同余关系R={ 证明：1）?x∈I，因为（x-x）/m=0，所以x≡x(mod m)，即xRx。 2）?x，y∈I，若xRy，则x≡y(mod m)，即（x-y）/m=k∈I，所以（y - x）/m=-k ∈I，所以y≡x(mod m)，即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是双射。 因为 离散数学试题(B卷答案2） 一、证明题（10分） 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 三、推理证明题（10分） 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) T(1)，ES (3)?x(B(x)→?yC(y)) P (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) T(8)，EG 四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15分）。 解设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生 的集合，则命题可符号化为： ?P→?x?A(x)，?xA(x)?Q Q→P。 (1)?P→?x?A(x) P (2)?P→??xA(x) T(1)，E (3)?xA(x)→P T(2)，E (4)?xA(x)?Q P (5)(?xA(x)→Q)∧(Q→?xA(x)) T(4)，E (6)Q→?xA(x) T(5)，I (7)Q→P T(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={ 七、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。 解：r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>, <3,3>,<4,4>,<5,5>} s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R2=R5={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R3={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R4={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>} 八、设R1是A上的等价关系，R2是B上的等价关系，A≠?且B≠?。关系R满足：< 证明对任意的 对任意的 R2。由R1对称得 对任意的 综上可得，R是A×B上的等价关系。 九、设f：A→B，g：B→C，h：C→A，证明：如果h g f＝I A，f h g＝I B，g f h＝I C，则f、 g、h均为双射，并求出f－1、g－1和h－1（10分）。 解因I A恒等函数，由h g f＝I A可得f是单射，h是满射；因I B恒等函数，由f h g ＝I B可得g是单射，f是满射；因I C恒等函数，由g f h＝I C可得h是单射，g是满射。从而f、g、h均为双射。 由h g f＝I A，得f－1＝h g；由f h g＝I B，得g－1＝f h；由g f h＝I C，得h－1＝g f。 离散数学试题(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)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<3，2>，<4，3>，<4，5>} t(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<1，3>，<2，2>，<2， 4>，<1，4>} 七、（10分）设函数f：R×R→R×R，R为实数集，f定义为：f( 1)证明f是双射。 解：1）? 2）? 八、（10分） 证明：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= 4>，<3，5>，<5，1>}，求D的邻接距阵A和可达距阵P。 解：1）D的邻接距阵A和可达距阵P如下： 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 A= 0 0 0 1 1 P= 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。 解：最优二叉树为 权＝(2+4)×4+6×3+12×2+(8+10)×3+14×2＝148 离散数学试题(B卷答案4） 一、证明题（10分） 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(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) 的主析取范式和主合取范式（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 三、推理证明题（10分） 1)(P→(Q→S))∧(?R∨P)∧Q?R→S 证明：（1）R 附加前提 (2)?R∨P P (3)P T(1)(2),I (4)P→(Q→S) P (5)Q→S T(3)(4),I (6)Q P (7)S T(5)(6),I (8)R→S CP 2) ?x(P(x)∨Q(x))，?x?P(x)??x Q(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)?x Q(x) T(5),EG 四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8（10分）。 证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。五、已知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） 六、π={A1，A2，…，A n}是集合A的一个划分，定义R={ 证明：?a∈A必有i使得a∈A i，由定义知aRa，故R自反。 ?a,b∈A，若aRb ，则a,b∈A i，即b,a∈A i，所以bRa，故R对称。 ?a,b,c∈A，若aRb 且bRc，则a,b∈A i及b,c∈A j。因为i≠j时A i∩A j=Φ，故i=j，即a,b,c∈A i，所以aRc，故R传递。 总之R是A上的等价关系。 七、若f:A→B是双射，则f-1:B→A是双射（15分）。 证明:对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使 对任意的x∈A，若存在y1,y2∈B，使得 因此f-1是双射。 八、设 证明假设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个连通分支为 G、2G、…、k G。任取结点u 1 、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支 G（1 i ≤i≤k）中，在不同于 G的另一连通分支上取一结点w，则[u，w]和[w，v]都不是 i 图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） ?M1∧M3∧M4∧M5 二、（8分）叙述并证明苏格拉底三段论 解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。 命题符号化为?x（F（x）→G（x）），F（a）?G（a） 证明： （1）?x(F(x)→G(x)) P （2）F(a)→G(a) T(1),US （3）F(a) P （4）G(a) T(2)(3),I 三、（8分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) 证明：∵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） 四、（10分）已知R 和S 是非空集合A 上的等价关系，试证：1）R ∩S 是A 上的等价关系； 2）对a ∈A ，[a]R ∩S =[a]R ∩[a]S 。 解：?x ∈A ，因为R 和S 是自反关系，所以 ?x 、y ∈A ，若 ?x 、y 、z ∈A ，若 总之R ∩S 是等价关系。 2）因为x ∈[a]R ∩S ? 所以[a]R ∩S =[a]R ∩[a]S 。 五、(10分) 设A ＝{a ，b ，c ，d }，R 是A 上的二元关系，且R ＝{，，， s (R )＝R ∪R -1 ＝{，，， t (R )＝i i R ∞=1 ＝{，，， d >，} 六、(15分) 设A 、B 、C 、D 是集合，f 是A 到B 的双射，g 是C 到D 的双射，令h ：A ×C →B ×D 且? 证明：1）先证h 是满射。 ? 2）再证h是单射。 ? 综合1）和2），h是双射。 七、(12分)设 证明：??a,b∈H有b-1∈H，所以a*b-1∈H。 ??a∈H，则e=a*a-1∈H a-1=e*a-1∈H ∵a,b∈H及b-1∈H，∴a*b=a*（b-1）-1∈H ∵H?G且H≠Φ,∴*在H上满足结合律 ∴ 八、（10分）设G= 解：设G的每个结点的度数都大于等于6，则2|E|=∑d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。 九.G= （1）G是否为阿贝尔群？ （2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元 解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c) (a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b) (b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c) 所以G是阿贝尔群 （2）因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a （3）因为a*a=a 所以G 的幂等元是a （4）因为b*c=c*b=a ，所以b 的逆元是c 且c 的逆元是b 十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。 解：最优二叉树为 权＝148 离散数学试题（B 卷答案6） 一、（20分）用公式法判断下列公式的类型： (1)(?P ∨?Q )→(P ??Q ) (2)(P ↓Q )→(P ∧?(Q ∨?R )) 解：（1）因为(?P ∨?Q )→(P ??Q )??(?P ∨?Q )∨(P ∧?Q )∨(?P ∧Q ) ?(P ∧Q )∨(P ∧?Q )∨(?P ∧Q ) ?1m ∨2m ∨3m ?0M 所以，公式(?P ∨?Q )→(P ??Q )为可满足式。 （2）因为(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) 华南农业大学期末考试试卷（A 卷） 2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分） 1、下面语句是简单命题的为_____。 A 、3不是偶数 B 、李平既聪明又用功 C 、李平学过英语或日语 D 、李平和张三是同学 2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。 A 、r q p →?∧? B 、r q p ?→∧? C 、r q p →?∧ D 、r q p ∧→ 3、下列谓词公式不是命题公式P →Q 的代换实例的是______。 A 、)()(y G x F → B 、),(),(y x yG y x xF ?→? C 、))()((x G x F x →? D 、)()(x G x xF →? 4、设个体域为整数集，下列公式中其值为 1的是_____。 A 、)0(=+??y x y x B 、)0(=+??y x x y C 、)0(=+??y x y x D 、)0(=+???y x y x 2 5、下列哪个表达式错误_____。 A 、 B x xA B x A x ∧??∧?)())(( B 、B x xA B x A x ∨??∨?)())(( C 、B x xA B x A x →??→?)())(( D 、)())((x xA B x A B x ?→?→? 6、下述结论错误的是____。 A 、存在这样的关系，它可以既满足对称性，又满足反对称性 B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C 、存在这样的关系，它可以既满足自反性，又满足反自反性 D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。 A 、自反性、对称性和传递性 B 、自反性、反对称性和传递性 C 、反自反性、对称性和传递性 D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。 A 、R 是自反的，则2R 一定是自反的 B 、R 是反自反的，则2R 一定是反自反的 C 、R 是对称的，则2R 一定是对称的 D 、R 是传递的，则2R 一定是传递 9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。 A 、11--R R B 、11--S R C 、11--S S D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。 A 、c b , B 、b a , C 、b D 、c b a ,, 11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A 、1，2，2，3，4，5 离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，， 《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群 19、代数系统是指由及其上的或 组成的系统。 20、设 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统 二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={ 《离散数学》期末考试题(B) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为 ( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( ) 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 一（6%）选择填空题。 (1) 设S = {1，2，3}，R 为S 上的二元关系，其关系图如右图所示，则R 具有（ ）的性质。 A. 自反、对称、传递； B. 反自反、反对称； C. 自反、传递； D. 自反。 (2) 设A = {1, 2, 3, 4}， A 上的等价关系 R = { (4)没有不犯错的人。 五（10%）在自然推理系统Ｐ中构造下面推理的证明： 如果他是计算机系本科生或者是计算机系研究生，则他一定学过DELPHI语言且学过C++语言。只要他学过DELPHI语言或者Ｃ++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。 六（10%）在自然推理系统中构造下面推理的证明（个体域：人类）： 每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。 七（14%）下图给出了一些偏序集的哈斯图，判断其是否为格，对于不是格的说明理由，对于是格的说明它们是否为分配格、有补格和布尔格（布尔代数）。 八（12%）设S = {1, 2, 3, 4, 6, 8, 12, 24}，“ ”为S上整除关系， (1)画出偏序集> ,S的哈斯图； < (2)设B = { 2, 3, 4, 6, 12}，求B的极小元、最小元、极大元、最大元，下界，上界。 九（8%）画一个无向图，使它是： (1)是欧拉图，不是哈密尔顿图； (2)是哈密尔顿图，不是欧拉图； (3)既不是欧拉图，也不是哈密尔顿图； 并且对欧拉图或哈密尔顿图，指出欧拉回路或哈密尔顿回路，对于即不是欧拉图也不是哈密尔顿图的说明理由。 十（8%）设6个字母在通信中出现的频率如下： 12 13 :c :b% 45 :a% % :e% :f 9 5 : d% % 16 用Huffman算法求传输它们的最佳前缀码。要求画出最优树，指出每个字母对应的编码，n个按上述频率出现的字母需要多少个二进制数字。 并指出传输)2 ( n 10≥华南农业大学 离散数学 期末考试2013试卷及答案
(完整版)离散数学试卷及答案
中国石油大学大学《离散数学》期末复习题及答案
离散数学试题与答案
离散数学期末试题及答案完整版
大学离散数学期末重点知识点总结(考试专用)
【浙江工商大学】《离散数学》期末考试题(B)
离散数学期末试卷及答案
离散数学期末考试试题及答案
厦门大学离散数学2015-2016期末考试试题答案年
相关主题
文本预览