离散数学试题(A卷答案）一、证明题（10分）1) (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⇔⌝( A∧((P∧Q)∨(⌝P∧⌝Q)))∨C⇔⌝( A∧(P↔Q))∨C⇔(A∧(P↔Q))→C2) ⌝(P↑Q)⇔⌝P↓⌝Q。

证明：⌝(P↑Q)⇔⌝(⌝(P∧Q))⇔⌝(⌝P∨⌝Q))⇔⌝P↓⌝Q。

二、分别用真值表法和公式法求(P→(Q∨R))∧(⌝P∨(Q↔R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。

证明：公式法：因为(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)⇔M∧5M∧6M4⇔m∨1m∨2m∨3m∨7m所以，公式(P→(Q∨R))∧(⌝P∨(Q↔R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。

真值表法：式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。

三、推理证明题（10分）1）⌝P∨Q，⌝Q∨R，R→S P→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 CP2) ∀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))四、某班有学生60人，其中有38人学习PASCAL语言，有16人学习C语言，有21人学习COBOL语言；有3个人这三种语言都学习，有2个人这三种语言都不学习，问仅学习两门语言的学生数是多少？(10分)解设、、分别表示学习PASCAL语言、C语言、COBOL语言的学生组成的集合，则|A|＝38，|B|＝16，|C|＝21，|A∩B∩C|＝3，|A∩B∩C|＝2。

|A∪B∪C|＝60－|A∩B∩C|＝58由容斥原理，得|A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A ∩B∩C|所以|A∩B|＋|A∩C|＋|B∩C|＝|A|＋|B|＋|C|＋|A∩B∩C|―|A ∪B∪C|＝38＋16＋21＋3―58＝20又因为|A∩B∩C|＝|A∩B|―|A∩B∩C|所以|A∩B∩C|＋|A∩B∩C|＋|A∩B∩C|＝|A∩B|＋|A∩C|＋|B ∩C|―3|A∩B∩C|＝20－9＝11仅学习两门语言的学生数是11人。

五、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) （10分）证明：因为x∈(A∪B)－C⇔x∈(A∪B)－C⇔x∈(A∪B)∧x∉C⇔(x∈A∨x∈B)∧x∉C⇔(x∈A∧x∉C)∨(x∈B∧x∉C)⇔x∈(A－C)∨x∈(B－C)⇔x∈(A－C)∪(B－C)所以，(A∪B)－C＝(A－C)∪(B－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是传递的⇔R*R⊆R（10分）。

证明若R是传递的，则<x，y>∈R*R⇒∃z(xRz∧zSy)⇒xRc∧cSy，由R是传递的得xRy，即有<x，y>∈R，所以R*R⊆R。

反之，若R*R⊆R，则对任意的x、y、z∈A，如果xRz且zRy，则<x，y>∈R*R，于是有<x，y>∈R，即有xRy，所以R是传递的。

八、证明整数集I上的模m同余关系R={<x,y>|x≡y(mod m)}是等价关系。

其中，x≡y(mod m)的含义是x-y可以被m整除（15分）。

证明：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是双射。

因为<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卷答案）一、证明题（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)↔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={<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≠∅。