离散数学期末考试试题及答案
离散数学试题(Ｂ卷答案１）
一、证明题(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))∧R
T∧Ｒ(置换)Ｒ
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)，I
2) 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={ 解：R-1={<ｙ,x>| x,ｙN∧y=ｘ2} R*S＝｛ Ｓ*R=｛<ｘ,y>| x,ｙN∧y=(x＋1)２},R{1，２}＝{＜1，1>，＜2，４>｝,Ｓ[{1,2}]={1,4}。 七、设Ｒ={<ａ，b>, 解：r(R）=｛ s(R)=｛＜ａ，b>, R2＝Ｒ5＝{＜ａ，c>, Ｒ３＝{ R4＝{<ａ，b>, t(R)＝｛＜ａ,b＞,＜b，c>, 八、证明整数集Ｉ上的模m同余关系R=｛ 证明：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（ 离散数学试题(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） M1 m0∨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 S 2）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={ 七、设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１>， 证明对任意的 是B上的等价关系可得＜y,y>∈R2。再由R的定义,有＜ 对任意的 对任意的 综上可得,R是Ａ×Ｂ上的等价关系。 九、设f:A B，ｇ：BＣ，ｈ：C A，证明:如果h o g o f＝I A，ｆｏh o g＝IＢ，g o f o h=I C，则f、ｇ、h均为双射,并求出f－１、g-1和h-1(10分）。 解因I A恒等函数，由ｈo g o f＝IＡ可得ｆ是单射,h是满射；因ＩB恒等函数，由f o h o g ＝I B可得g是单射,ｆ是满射；因I C恒等函数,由g oｆｏｈ=ＩC可得h是单射，ｇ是满射。从而ｆ、g、ｈ均为双射。 由h o g o f=I A,得f-１＝hｏg;由f o hｏｇ＝I B，得ｇ-１=f oｈ；由g o f o h＝I C,得h－１＝g o f。 离散数学试题(Ｂ卷答案3) 一、（１0分)判断下列公式的类型（永真式、永假式、可满足式）？（写过程) 1)P(Ｐ∨Q∨Ｒ） 2)（(Q P)∨P）∧(P∨Ｒ） 3)(（P∨Q)R)((Ｐ∧Q)∨R) 解:1)重言式;2)矛盾式;３）可满足式 二、（１0分）求命题公式(Ｐ∨(Q∧R))(Ｐ∨Q∨R)的主析取范式,并求成真赋值。 解:(Ｐ∨（Q∧R))(P∨Q∨R）(P∨(Q∧R))∨P∨Ｑ∨R P∧(Ｑ∨R）∨P∨Q∨Ｒ (P∧Q)∨(P∧R)∨(P∨Q)∨R ((Ｐ∨Q)∨(P∨Q))∨(Ｐ∧R)∨Ｒ 1∨（(P∧R)∨R)1 m0∨ｍ1∨m2∨m３∨ｍ4∨ｍ5∨ｍ6∨m７ 该式为重言式,全部赋值都是成真赋值。 三、（1０分）证明 (（P∧Q∧A)C)∧(Ａ(Ｐ∨Q∨C))(Ａ∧(ＰQ)）Ｃ 证明：（(Ｐ∧Q∧A)C)∧(A(Ｐ∨Q∨C))（(Ｐ∧Ｑ∧A）∨C)∧（Ａ∨(Ｐ∨Q∨Ｃ）) (（P∨Q∨A)∨C)∧((Ａ∨Ｐ∨Q)∨C) （（P∨Q∨Ａ)∧(A∨Ｐ∨Q）)∨C （(P∨Q∨A）∧(A∨P∨Q))C ((P∨Q∨A)∨(Ａ∨P∨Q))C (（Ｐ∧Q∧A)∨(Ａ∧P∧Q))Ｃ (Ａ∧(（P∧Q）∨(P∧Ｑ））)Ｃ (A∧（(P∨Q)∧(Ｐ∨Q)）)C (A∧((ＱＰ)∧（ＰQ）))C (A∧(P Q))C 四、（１０分）个体域为{１，2},求x y(x+ｙ=4)的真值。 解：x y（ｘ+y=4）x（（ｘ+1=4)∨（x+2=4)） (（1＋１＝4）∨(1＋2=4））∧((2+1=４）∨（２＋2=４）） （0∨0)∧（０∨1）0∧１0 五、（10分）对于任意集合A,B，试证明:Ｐ(A)∩P(B)=P（A∩B) 解:x P（A）∩Ｐ(B)，x P（A)且x P(B),有x A且ｘＢ,从而xＡ∩Ｂ,x P(A∩B),由于上述过程可逆，故P(A)∩Ｐ(Ｂ)=P(A∩B) 六、（10分)已知A=｛１,２，3，4，５}和R＝｛<1,2>,<2，1>，<2，3>，<3,4>，<5，4>}，求r(R)、s(R）和t（R)。 解:r(R)={<1,2＞,＜２,１>,<2，3>，<3，4>,<5，４>,<1,１>,＜2,2>,<３，3>，<４,4>，<5，5>} s(R)=｛<1,2>,<2，１>，<2,3>,<3,４＞，＜5,4>，<3,２>,＜4,3>，<4，5>} t(R)＝｛<1,2>,<2，1>，＜2，3>，＜3，4>，<５,4＞，<１，１>,＜1，３＞,<2， 2>，<2,4＞,＜1,4>｝ 七、(1０分)设函数ｆ:Ｒ×R R×Ｒ，Ｒ为实数集,ｆ定义为:ｆ(＜x，ｙ>)=＜x+ｙ，x-ｙ>。1)证明f是双射。 解:１) １-y１>=＜x2＋y2,x２-y2＞,则ｘ１＋y１=x2+y2且x1-y1＝x2-y2得ｘ1=x２,y1=ｙ２从而f是单射。 2)＜p，q＞∈R×R,由f（<ｘ,y>)＝＜p，q>,通过计算可得x=（p+q)/２；ｙ=(p-q)/2； 从而 八、(10分）＜Ｇ,*>是个群,ｕ∈G,定义G中的运算“”为a b=ａ*u-1*b，对任意a，ｂ∈G，求证: 证明:1)a，ｂ∈Ｇ,a b＝a＊u-１*b∈Ｇ，运算是封闭的。 2）ａ,b,ｃ∈G,（a b)c=（a*ｕ-1*b)*ｕ－１*c=a＊ｕ－1*（b＊u-1*c)=ａ（b c），运算是可结合的。 3）a∈Ｇ,设E为的单位元,则ａＥ=ａ*u-1*E＝ａ,得Ｅ=u，存在单位元ｕ。 4）a∈G,a x=a*u－1*x＝E,x=ｕ*ａ-1*u,则x a=ｕ*a-1＊u*u-１*a＝u＝E，每个元素都有逆元。 所以 九、（10分)已知：D= 5>，<5,1>},求D的邻接距阵Ａ和可达距阵P。 解:1)Ｄ的邻接距阵A和可达距阵P如下: 0１01０11111 ００100１1１11 A=00０１1P=1１１1１ 0０000000００ 100０0111１１ 十、（1０分）求叶的权分别为2、4、6、８、10、12、14的最优二叉树及其权。 解:最优二叉树为 权＝(２+4)×４+6×３+1２×2+(8＋１０)×3+14×2=1４8 离散数学试题(B卷答案４) 一、证明题（10分） 1）((P∨Q)∧（P∧(Q∨Ｒ)）)∨(P∧Q)∨（P∧Ｒ)T 证明: 左端((P∨Q)∧(P∨(Ｑ∧R)))∨（(P∨Ｑ)∧(P∨Ｒ）)(摩根律）((P ∨Q)∧(P∨Q)∧(P∨R))∨((P∨Ｑ)∧(P∨R))(分配律） ((P∨Ｑ)∧(P∨R))∨((P∨Q)∧（P∨R）) (等幂律) Ｔ?(代入) 2)x(Ｐ(x）Ｑ(x))∧xP(x)x(P(x)∧Q(ｘ）) 证明：ｘ(Ｐ(x)Q(ｘ)）∧xP（x）ｘ(（P(x)Ｑ（ｘ)∧P（ｘ）)x((P （x)∨Q(x)∧Ｐ(x)）x(P(ｘ)∧Q（ｘ))xＰ（x）∧ｘQ(x)x(P(x)∧Q(x))二、求命题公式(P Q)(P∨Q) 的主析取范式和主合取范式(1０分） 解:(P Q）(P∨Ｑ)(P Q)∨(P∨Q)(Ｐ∨Q)∨(P∨Q）(P ∧Q)∨(P∨Q) (Ｐ∨Ｐ∨Q)∧（Q∨P∨Q）(P∨Q)M1m0∨m2∨ｍ3 三、推理证明题（10分） 1)(P（Q S))∧（Ｒ∨Ｐ）∧ＱR S 证明:（１）R 附加前提 （2）R∨P P （3)P T(1)(2）,I (4)P(QＳ) P (5)QＳＴ(3）（4）,Ｉ (6)Q P （７)S T(5)(６),I （8)RＳ CＰ 2）x(Ｐ(x)∨Q（x)）,x P(x)x Q(x) 证明：(1)ｘP(x) P (２)P（c） T(1)，US (３)x（P（x）∨Q(x)) P (４)P（c)∨Ｑ(c） T(３）,ＵS (5)Q（ｃ) T（2）(4）,I （6）x Q(ｘ）T(5),EG 四、例５在边长为1的正方形内任意放置九个点,证明其中必存在三个点,使得由它们组成的三角形（可能是退化的）面积不超过1/8(１0分)。 证明：把边长为1的正方形分成四个全等的小正方形,则至少有一个小正方形内有三个点,它们组成的三角形（可能是退化的)面积不超过小正方形的一半,即１／8。 五、已知Ａ、B、C是三个集合，证明A∩(B∪C)=(A∩Ｂ)∪(Ａ∩C） (10分） 证明：∵ｘＡ∩(B∪C） x A∧x（B∪C） x A∧（x B∨xＣ）( x A∧x B）∨（ｘＡ∧x C） x（Ａ∩Ｂ）∨x A∩C x(Ａ∩Ｂ)∪(A∩C）∴A∩（B∪C）=(A∩Ｂ)∪(A∩C） 六、={A1,A2，…,Ａn｝是集合Ａ的一个划分，定义R={ 证明:a∈Ａ必有i使得a∈Ａi，由定义知aRa，故R自反。 a,ｂ∈Ａ，若aRb ，则a,ｂ∈Ａｉ,即b,a∈A i，所以bＲa,故R对称。 a,b,c∈A,若aRb 且bRｃ，则a，b∈A i及b,c∈A j。因为ｉ≠j时A i∩Ａj=，故i=j，即a，b,c∈A i，所以aRｃ,故R传递。 总之Ｒ是A上的等价关系。 七、若f:A→B是双射,则ｆ-１：Ｂ→A是双射(15分)。 证明:对任意的x∈Ａ，因为f是从Ａ到Ｂ的函数,故存在y∈B,使 对任意的x∈A，若存在y１,y2∈B,使得＜y1,ｘ>∈f－1且 因此f-1是双射。 八、设 证明假设A≠Ｇ且B≠G,则存在ａＡ，aＢ，且存在b B,bＡ(否则对任意的a A，ａＢ,从而ＡB,即Ａ∪B=B，得B＝G，矛盾。) 对于元素a*bＧ,若a*b A,因Ａ是子群，ａ－1A,从而a－1* (a*b）=b A，所以矛盾，故ａ*ｂA。同理可证a*ｂB，综合有a＊ｂA∪B=G。 综上所述,假设不成立，得证A=G或B=G。 九、若无向图G是不连通的,证明G的补图G是连通的（10分)。 证明设无向图G是不连通的,其k个连通分支为1G、2G、…、k G。任取结点u、v∈G,若u和v不在图G的同一个连通分支中，则[u，v］不是图G的边，因而[u,v]是图G的边；若u和v在图G的同一个连通分支中,不妨设其在连通分支i G（１≤i≤k)中,在不同于 G的另一连通分支上取一结点w，则[u,w]和［w,v］都不是图G的边，， i 因而［u，w］和[w,v]都是G的边。综上可知,不管那种情况,u和v都是可达的。由u 和v的任意性可知,G是连通的。 离散数学试题(B卷答案５） 一、(10分)求命题公式(P∧Q)（PＲ)的主合取范式。 解：(P∧Q)(P R）((P∧Ｑ)（PＲ))∧(（PＲ)(Ｐ∧Q)) （(P∧Q)∨(P∧R))∧（(Ｐ∨R）∨（P∨Q)） (P∧Ｑ)∨(P∧R) (P∨Ｒ)∧(Q∨P）∧（Q∨Ｒ) (Ｐ∨Q∨R)∧(Ｐ∨Ｑ∨Ｒ)∧（P∨Q∨R)∧（P∨Q∨Ｒ） M1∧M3∧M4∧M5 二、(8分）叙述并证明苏格拉底三段论 解:所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 符号化:F（x)：x是一个人。G（x):x要死的。A：苏格拉底。 命题符号化为ｘ（F（ｘ）Ｇ(x)),F(a)G(a) 证明： （1)x(F(ｘ)Ｇ(ｘ)) P （2）F（a)G(a) T（１)，UＳ （3）F(a） P （４）Ｇ(a) T(2)（3）,I