离散数学考试试题(A、B卷及答案).doc

离散数学考试试题(A、B卷及答案)
离散数学考试试题(A卷及答案）
一、证明题（10分）
1) (P∧Q∧A®C)∧(A®P∨Q∨C)Û (A∧(P«Q))®C。P<->Q=(p->Q)合取（Q->p）GN7pqTG。
证明: (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
ÛØ( A∧((P∧Q)∨(ØP∧ØQ)))∨C再反用分配律
ÛØ( A∧(P«Q))∨C
Û(A∧(P«Q))®C
2) Ø(P­Q)Û ØP¯ØQ。
证明：Ø(P­Q)ÛØ(Ø(P∧Q))ÛØ(ØP∨ØQ))ÛØP¯ØQ。
二、 分别用真值表法和公式法求(P®(Q∨R))∧(ØP∨(Q«R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。QfhKKvR。
主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。
主析取范式可由 析取范式经等值演算法算得。
证明：
公式法：因为(P®(Q∨R))∧(ØP∨(Q«R))
Û(ØP∨Q∨R)∧(ØP∨(Q∧R)∨(ØQ∧ØR))
Û(ØP∨Q∨R)∧(((ØP∨Q)∧(ØP∨R))∨(ØQ∧ØR))分配律
Û(ØP∨Q∨R)∧(ØP∨Q∨ØQ)∧(ØP∨Q∨ØR)∧(ØP∨R∨ØQ)∧(ØP∨R∨ØR)
Û(ØP∨Q∨R)∧(ØP∨Q∨ØR)∧(ØP∨ØQ∨R)
Û∧∧使（非P析取Q析取R）为0所赋真值，即100，二进制为4
Û∨∨∨∨
所以，公式(P®(Q∨R))∧(ØP∨(Q«R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。4Oc3g5D。
真值表法：
P Q R
Q«R
P®(Q∨R)
ØP∨(Q«R)
(P®(Q∨R))∧(ØP∨(Q«R))
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1
0
0
1
1
0
0
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
0
0
0
1
由真值表可知，公式(P®(Q∨R))∧(ØP∨(Q«R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。5Ed8p3E。
三、推理证明题（10分）
1）ØP∨Q，ØQ∨R，R®SP®S。
证明：
(1)P 附加前提
(2)ØP∨Q P
(3)Q T(1)(2)，I（析取三段论）
(4)ØQ∨R P
(5)R T(3)(4)，I（析取三段论）
(6)R®S P
(7)S T(5)(6)，I（假言推理）
(8)P®S CP
2) "x(P(x)®Q(y)∧R(x))，$xP(x)ÞQ(y)∧$x(P(x)∧R(x))
证明（1）$xP(x)
(2)P(a)
(3)"x(P(x)®Q(y)∧R(x))
(4)P(a)®Q(y)∧R(a)
(5)Q(y)∧R(a)
(6)Q(y)
(7)R(a)
(8)P(a)
(9)P(a)∧R(a)
(10)$x(P(x)∧R(x))
(11)Q(y)∧$x(P(x)∧R(x))
五、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) （10分）
证明：因为
∈(A∪B)－CÛ∈(A∪B)－C
Û∈(A∪B)∧ÏC
Û(∈A∨∈B)∧ÏC
Û(∈A∧ÏC)∨(∈B∧ÏC)
Û∈(A－C)∨∈(B－C)
Û∈(A－C)∪(B－C)
所以，(A∪B)－C＝(A－C)∪(B－C)。
八、证明整数集I上的模m同余关系R={<x,y>|xºy(mod m)}是等价关系。其中，xºy(mod m)的含义是x-y可以被m整除（15分）。X(modm)=y(modm)7oYOplz。
证明：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。gcN6etO。
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。9aPZ1aS。
九、若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是双射。D2sDhMS。
因为<x,y>∈f-1g-1Û存在z（<x,z>∈g-1Ù<z,y>∈f-1）Û存在z（<y,z>∈fÙ<z,x>∈g）Û<y,x>∈gfÛ<x,y>∈（gf）-1,所以（gf）-1=f-1g-1。raZjrtm。
离散数学考试试题(B卷及答案）
一、证明题（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析取要使之为假，即赋真值001，即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）析取三段论
(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(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)ESAp2wWoz。
(3)"x(B(x)®$yC(y)) P
(4)"x(B(x)®C()) T(3)ES9J92Z78。
(5)B()®C() T(4）USke56TJu。
(6)A(a)®B() T(2)USEFFud1G。
(7)A(a)®C() T(5)(6)I假言三段论SvzPYSx。
(8)"xA(x)®C() T(7)UGEmYVvyY。
(9)"xA(x)®$yC(y) T(8)EGQqZKNyp。
四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15分）。ppluQUi。
解 ：
设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集 合，则命题可符号化为：ØP®$xØA(x)，"xA(x)«QQ®P。lTucD7S。
(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)IaUieBTm。
五、已知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）3kYsRPW。
六、A={ x1,x2,x3 }，B={ y1,y2}，R={<x1, y1>,<x2, y2>,<x3, y2>}，求其关系矩阵及关系图（10分）。有就是1，没就是0123sGco。
七、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。vD4EMPI。
r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3><5,5>}（自反闭包）Hec2vZP。
s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>}（对称闭包）4ZJTeeR。
t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}（传递闭包）Th32kwg。
九、设f：A®B，g：B®C，h：C®A，证明：如果hogof＝IA，fohog＝IB，gofoh＝IC，则f、g、h均为双射，并求出f－1、g－1和h－1（10分）。21xr8T5。
解 因IA恒等函数，由hogof＝IA可得f是单射，h是满射；因IB恒等函数，由fohog＝IB可得g是单射，f是满射；因IC恒等函数，由gofoh＝IC可得h是单射，g是满射。从而f、g、h均为双射。7vmQV84。
由hogof＝IA，得f－1＝hog；由fohog＝IB，得g－1＝foh；由gofoh＝IC，得h－1＝gof。qBs9Zge。
五. (12分)令X={x1,x2,...,xm},Y={y1,y2,...,yn},问:
(1) 有多少不同的由X到Y的关系?
(2) 有多少不同的由X到Y的影射?
(3) 有多少不同的由X到Y的单射，双射?QcYEvH4。
（12分）<G,*>是个群，u∈G，定义G中的运算“D”为aDb=a*u-1*b，对任意a,b∈G，求证：<G, D>也是个群。FKxS2fl。
证明：1）"a,b∈G，aDb=a*u-1*b∈G，运算是封闭的。
2）"a,b,c∈G，（aDb）Dc=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=aD（bDc），运算是可结合的。bTKXwKE。
3）"a∈G，设E为D的单位元，则aDE=a*u-1*E=a，得E=u，存在单位元。
4）"a∈G，aDx=a*u-1*x=E，x=u*a-1*u，则xDa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。M9zmOOd。
所以<G, D>也是个群。