离散数学试题(Ｂ卷答案１）一、证明题(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))∧RT∧Ｒ(置换)Ｒ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)，I2) 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={<x,y＞｜ x,y N∧y=x2}，S={<x,y＞| x,yＮ∧y=x+1}。
求R－1、R*Ｓ、S*R、R{1，2｝、Ｓ[{1,2}］(10分)。
解：R-1={<ｙ,x>| x,ｙN∧y=ｘ2}R*S＝｛<x，ｙ>| x，y N∧y＝x２+1}Ｓ*R=｛<ｘ,y>| x,ｙN∧y=(x＋1)２},R{1，２}＝{＜1，1>，＜2，４>｝,Ｓ[{1,2}]={1,4}。
七、设Ｒ={<ａ，b>,<b，c>,＜c，ａ>}，求ｒ(R)、s(Ｒ)和t(Ｒ) （１5分）。
解：r(R）=｛<a,b>,<b，c>，<c，a>,<a，a>,<ｂ,b＞，<c，c>｝s(R)=｛＜ａ，b>,<b，c>，<ｃ,a>，＜ｂ，a>，<c,b>，＜ａ,c＞}R2＝Ｒ5＝{＜ａ，c>,<b，a＞，<c，b>}Ｒ３＝{<a，a>,<b,b＞，<ｃ,b>｝R4＝{<ａ，b>,<b，c＞,＜ｃ，ｃ>}t(R)＝｛＜ａ,b＞,＜b，c>,<c，a＞，<a，c＞，＜b，a>，，<a,a>，<b,b>，<c,b>,<ｃ,c＞}八、证明整数集Ｉ上的模m同余关系R=｛<x,y>|x y(mod m)}是等价关系。
其中,x y(mod m)的含义是x-y可以被ｍ整除(１５分)。
证明：1)x∈I,因为（x-x)/m=０,所以ｘx（mod m)，即xRx。
２)x,y∈I，若xRy,则x y(mｏd m)，即（ｘ－y)／m=ｋ∈I,所以（ｙ - x）/m=-k ∈I,所以y x(mod m)，即yRx。
3)x，ｙ，ｚ∈I，若xRｙ，ｙRz，则(x-y)／m＝u∈I,(y-z)/ｍ＝v∈I,于是(ｘ-z)/m=（x-y+y-ｚ)／m＝u+v ∈I，因此xＲz。
九、若ｆ:A→Ｂ和g:Ｂ→C是双射,则(gf)－１=ｆ-1g－1（１0分）。
证明:因为f、g是双射，所以ｇf：A→C是双射,所以gf有逆函数(gｆ）-1:Ｃ→A。
同理可推f-1ｇ-1:C→A是双射。
因为<ｘ,y>∈f-１g-1存在z（<x，z＞∈g-1<z，ｙ>∈f-1)存在z（<y，z>∈f<z,ｘ＞∈g)<y,ｘ>∈gf＜x,y>∈(ｇf）-1,所以(gｆ)-1=f-1g-1。
离散数学试题(B卷答案2）一、证明题(10分）1）((P∨Q）∧（P∧(Ｑ∨R)))∨（P∧Q)∨(P∧Ｒ)Ｔ证明: 左端((Ｐ∨Ｑ)∧(P∨(Q∧R)))∨（（P∨Q)∧（P∨R))(摩根律)(（P∨Q)∧（Ｐ∨Q）∧(P∨Ｒ)）∨((Ｐ∨Q）∧(P∨R))(分配律)((P∨Ｑ)∧(P∨R）)∨((P∨Q）∧(P∨R)) （等幂律）T （代入)2）x y(Ｐ(ｘ)Q(y))（xP(ｘ)yＱ(y))证明:x y(Ｐ(x)Q(y))ｘy(Ｐ(ｘ)∨Ｑ(ｙ))x（P（x)∨yQ（y）)ｘP(ｘ)∨yQ（y)xＰ(x)∨yQ（y)（xP（x）yQ(y））二、求命题公式(P Q)（Ｐ∨Q) 的主析取范式和主合取范式（10分）解:（P Q）（P∨Ｑ)（ＰQ）∨(Ｐ∨Q)(Ｐ∨Q)∨(P∨Q)(P∧Ｑ)∨(P∨Ｑ)(P∨P∨Q）∧(Ｑ∨P∨Q)(P∨Q）M1m0∨m２∨m3三、推理证明题(10分)1)(P（ＱS))∧（R∨P）∧Q RＳ证明:(１)R(2)R∨P(3)Ｐ(4)P(Q S)(5）ＱS(6)Ｑ(7）Ｓ(8)R S2）x(A(ｘ)yB(ｙ))，x(B(x)yＣ（y）)xA（x)yＣ(y)。
证明：(１)x(A(x)ｙB(y）) P（2)Ａ(a)ｙB(ｙ) Ｔ(１)，ES(3)x(B(x)yＣ(y）) Ｐ(４)x（Ｂ(ｘ）C（c）) Ｔ（3)，EＳ(5)B(b)C(c) Ｔ(４），US（6)A(a)B(b) T(2），US(７)A(ａ)C(c) T(5)(6),I(8)xA(x)C(c） T(7),ＵG(9)xA(ｘ)yC(y) T(8)，EG四、只要今天天气不好,就一定有考生不能提前进入考场,当且仅当所有考生提前进入考场，考试才能准时进行。
所以，如果考试准时进行，那么天气就好（１5分)。
解设P:今天天气好,Ｑ:考试准时进行,A（e):e提前进入考场,个体域:考生的集合，则命题可符号化为:P xＡ(x),ｘA（x)Q Q P。
(1）P x A(x) P(2)PｘA(x) T(1),E(3)ｘA(ｘ)PＴ(２)，Ｅ（4）xＡ(ｘ)ＱP（５)(xA(x）Q）∧（Q xＡ(x)) T（４)，E（6)QｘＡ(x) T(5)，Ｉ（7)Q P T(6)(3），Ｉ五、已知A、B、C是三个集合，证明Ａ∩(B∪C)=(A∩B)∪(A∩C）（1０分）证明：∵x A∩(Ｂ∪C)x A∧ｘ（Ｂ∪C)x A∧(xＢ∨x Ｃ)( x A∧ｘＢ）∨(x A∧ｘC) x（A∩B)∨xＡ∩C x(A∩B）∪(A∩Ｃ)∴A∩（B∪Ｃ）=（A∩B）∪（A∩C）六、A＝｛ｘ１，x2，ｘ3 },Ｂ＝{ y１,y2}，R={<x１, y1>,<x2, y2>,<x３, y2>},求其关系矩阵及关系图(10分)。
七、设R={<2,1>，<2,５>,<2,4>,<３,４＞，＜4，4>,<５,2＞},求r(R)、ｓ（Ｒ）和t(Ｒ)，并作出它们及R的关系图(1５分）。
解：r(R)={<２，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,５>,<2,4>,<3,4>,<４，４>，＜5,2＞,<１,２＞,＜４，２>,＜4,3>}R２=R5=｛<2，２>,<2，4>,<３,４>,<4,4＞,＜5,1＞，＜5,5＞,＜5,4＞}Ｒ3＝{<2,1>,<2,5>,<2,４＞,<3,4>，<４,4>,<５,2>，＜５,4＞}R4={＜２,２>，<２,4>,＜3,4＞,<4,4＞,＜5,1>,<５,５＞,<5,4＞}t(R)=｛<２，1>,＜2,5>，<2,4>,<3,4>,＜４,4>,＜5,2>，＜2，２>，＜５，１>,<5,4>，<５,５＞}八、设R1是A上的等价关系，R２是B上的等价关系，A≠且B≠。
关系R满足：＜＜x１,y１>，<x２,y2>>∈R＜ｘ１,x2>∈R1且<y1,y2>∈R2,证明Ｒ是A×B上的等价关系(１0分）。
证明对任意的<x，y＞∈A×Ｂ,由R1是Ａ上的等价关系可得＜ｘ，x>∈Ｒ１，由R2是B上的等价关系可得＜y,y>∈R2。