离散数学期末考试试题及答案

离散数学试题(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(置换)R2)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)EP(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∨DP(7)R∨ST(5)，I2)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={x，y|x，yN∧y=x2}，S={x，y|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|x，yN∧y=x2+1}S*R={x，y|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，b，b，c，c，a，a，a，b，b，c，c}s(R)={a，b，b，c，c，a，b，a，c，b，a，c}R2=R5={a，c，b，a，c，b}R3={a，a，b，b，c，b}R4={a，b，b，c，c，c}t(R)={a，b，b，c，c，a，a，c，b，a，，a，a，b，b，c，b，c，c}八、证明整数集I上的模m同余关系R={x，y|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是双射。因为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。离散数学试题(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S2)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)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分）。七、设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满足：x1，y1，x2，y2∈Rx1，x2∈R1且y1，y2∈R2，证明R是A×B上的等价关系（10分）。证明对任意的x，y∈A×B，由R1是A上的等价关系可得x，x∈R1，由R2是B上的等价关系可得y，y∈R2。再由R的定义，有x，y，x，y∈R，所以R是自反的。对任意的x，y、u，v∈A×B，若x，yRu，v，则x，u∈R1且y，v∈R2。由R1对称得u，x∈R1，由R2对称得v，y∈R2。再由R的定义，有u，v，x，y∈R，即u，vRx，y，所以R是对称的。对任意的x，y、u，v、s，t∈A×B，若x，yRu，v且u，vRs，t，则x，u∈R1且y，v∈R2，u，s∈R1且v，t∈R2。由x，u∈R1、u，s∈R1及R1的传递性得x，s∈R1，由y，v∈R2、v，t∈R2及R2的传递性得y，t∈R1。再由R的定义，有x，y，s，t∈R，即x，yRs，t，所以R是传递的。综上可得，R是A×B上的等价关系。九、设f：AB，g：BC，h：CA，证明：如果hgf＝IA，fhg＝IB，gfh＝IC，则f、g、h均为双射，并求出f－1、g－1和h－1（10分）。解因IA恒等函数，由hgf＝IA可得f是单射，h是满射；因IB恒等函数，由fhg＝IB可得g是单射，f是满射；因IC恒等函数，由gfh＝IC可得h是单射，g是满射。从而f、g、h均为双射。由hgf＝IA，得f－1＝hg；由fhg＝IB，得g－1＝fh；由gfh＝IC，得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∨m