离散数学试题及答案

离散数学试题及答案

离散数学试题(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))?C

2) ?(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) ?M4∧M5∧M6 ?m0∨m1∨m2∨m3∨m7

所以，公式(P?(Q∨R))∧(?P∨(Q?R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。

真值表法：

P Q Q?R P?(Q∨R R) 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1

?P∨(P?(Q∨R))∧(?P∨(Q?R) (Q?R)) 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1

由真值表可知，公式(P?(Q∨R))∧(?P∨(Q?R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。 三、推理证明题（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))

四、某班有学生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?N∧y=x2}，S={| x,y?N∧y=x+1}。求R-1、R*S、S*R、R{1,2}、S[{1,2}]（10分）

解：R-1={| x,y?N∧y=x2}，R*S={| x,y?N∧y=x2+1}，S*R={| 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是传递的，则∈R*R??z(xRz∧zSy)?xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*R?R。

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

八、证明整数集I上的模m同余关系R={|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是双射。

因为∈f-1g-1?存在z（∈g-1?∈f-1）?存在z（∈f?∈g）?∈gf?∈（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?S

2) ?x(A(x)??yB(y))，?x(B(x)??yC(y))?xA(x)??yC(y)。

证P

(2)A(a)??yB(y) T(1)，ES

(3)?x(B(x)??yC(y)) P

明：(1)?x(A(x)??yB(y))

(4)?x(B(x)?C(T(3)，ES

(5)B(T(4)，US

(6)A(a)?B(T(2)，US

(7)A(a)?C(T(5)(6)，I

(8)?xA(x)?C(T(7)，UG

cbbc))

)?C(

c)

)

)

c)

(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)?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={,,}，求其关系矩阵及关系图（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满足：<，>∈R?∈R1且∈R2，证明R是A×B上的等价关系（10分）。

证明 对任意的∈A×B，由R1是A上的等价关系可得∈R1，由R2是B上的等价关系可得∈R2。再由R的定义，有<，>∈R，所以R是自反的。

对任意的、∈A×B，若R，则∈R1且∈R2。由R1对称得∈R1，由R2对称得∈R2。再由R的定义，有<，>∈R，即R，所以R是对称的。

对任意的、、∈A×B，若R且R，则∈R1且∈R2，∈R1且∈R2。由∈R1、∈R1及R1的传递性得∈R1，由∈R2、∈R2及R2的传递性得∈R1。再由R的定义，有<，>∈R，即R，所以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。