离散数学期末测验试题（有几套带答案1)
———————————————————————————————— 作者:
———————————————————————————————— 日期:
ﻩ
离散数学试题(A卷及答案）
一、证明题（10分）
１)(P∧(Q∧Ｒ)）∨(Q∧R）∨(P∧R）Ｒ
证明： 左端(P∧Q∧R)∨（(Q∨Ｐ)∧R)（(P∧Q)∧R))∨((Ｑ∨Ｐ)∧R）
２)x（P(x)Q(x))∧xＰ(x）ｘ(Ｐ（x）∧Q(x))
证明ｘ（P(x)Q(x))∧xP（ｘ)x((Ｐ(x)Q(x)∧P(x)）x（(P（ｘ)∨Q(x)∧P(x)）ｘ（P(x)∧Q(x))xＰ（ｘ)∧xQ（x)x(P（ｘ）∧Ｑ(x))
二、求命题公式（ＰQ)(P∨Q） 的主析取范式和主合取范式（10分)
七、若ｆ:A→B和ｇ:B→C是双射，则(gf)－１＝f－1g-1(1０分）。
证明：因为ｆ、ｇ是双射,所以ｇf:A→C是双射，所以ｇf有逆函数(gf）-１：C→Ａ。同理可推f-1g－1：Ｃ→Ａ是双射。
因为<x,y>∈ｆ-1g-1存在ｚ(<x,ｚ>∈g-1<z,ｙ＞∈f-1)存在ｚ(<y,z>∈f<ｚ,ｘ>∈g)<y，x>∈ｇf＜x,y＞∈（gf）-1,所以(gf)-1＝f-１g-1。
证明:(1) (C∨D）E
(２)E（A∧Ｂ) ﻩﻩ
(3） （C∨D）（A∧Ｂ)
（４) （Ａ∧B)(R∨Ｓ) ﻩﻩ
(5) （C∨D）（R∨Ｓ)ﻩ
(6) C∨Ｄ ﻩﻩ
(7) R∨S
2)x(P(ｘ)Q(ｙ）∧R(x)），xP(x)Q(y）∧x（P(x)∧R(x))
证明（1)xP(ｘ)
(2）P(a)
（3)ｘ(P(x)Q(y）∧R(x))
解:(ＰＱ)(P∨Q)（PQ）∨（P∨Q）（P∨Q)∨（Ｐ∨Q)(P∧Ｑ)∨(Ｐ∨Q)(P∨P∨Q）∧(Q∨P∨Ｑ)（Ｐ∨Q）Ｍ1m0∨m2∨m３
三、推理证明题（10分)
证明:(P∨（Ｑ∧Ｒ））(P∧Q∧R)(P∨(Ｑ∧Ｒ）)∨（P∧Q∧R))
（P∧（Q∨R)）∨(Ｐ∧Q∧Ｒ）
(P∧Ｑ)∨(P∧R)）∨(Ｐ∧Q∧R)
(P∧Q∧R)∨(P∧Ｑ∧R）∨(Ｐ∧Q∧R)）∨(P∧Q∧R)）∨(Ｐ∧Ｑ∧R)
m0∨ｍ1∨m2∨ｍ７
Ｍ3∨M4∨M5∨M6
三、推理证明题(10分)
1）Ｃ∨D， (C∨D)E,Ｅ(A∧B), (A∧B)(R∨S)R∨S
六、已知R、S是N上的关系，其定义如下：Ｒ=｛＜x，ｙ>| x，yN∧y=x2｝，Ｓ={<x,y＞| x,yN∧ｙ=x+1}。求R-1、R*Ｓ、S*R、R {1,2｝、S［｛１，２｝]（10分）
解:R－1={＜ｙ,ｘ>| x,yＮ∧ｙ=x2｝，R*S=｛<x,y>｜ ｘ,ｙN∧y=x2+1},S＊R={<x,ｙ>| x,yＮ∧ｙ=(x+１)2},
R {１，２}＝{<1,1＞，<２,4>},S[{1，２}]＝｛１,４}。
离散数学试题(B卷及答案）
一、证明题（10分)
1)(（Ｐ∨Ｑ)∧(P∧(Q∨R)）)∨(P∧Q)∨(P∧R）T
证明左端（(Ｐ∨Q)∧（P∨(Q∧R)))∨((P∨Q）∧（P∨R）)(摩根律)((Ｐ∨Q)∧(P∨Ｑ)∧（P∨Ｒ))∨((P∨Q)∧(P∨Ｒ))（分配律）((P∨Ｑ)∧（P∨R）)∨((P∨Q)∧(P∨R)) (等幂律)Ｔ(代入)
(4）P（a)Q(y)∧R(a)
(５)Q(y)∧Ｒ(a)
a)
(9)P(ａ)∧R(a)
（10)x(Ｐ(x)∧R(ｘ))
(11)Q（ｙ)∧x(P（x）∧R(x)）
五、已知Ａ、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) （１5分)
证明∵xA-（Ｂ∪C)xA∧x（Ｂ∪C)xA∧(xＢ∧ｘC）(xA∧xB)∧（xA∧xC）x（Ａ-B)∧ｘ(A－C）x(A－B）∩（A-Ｃ)∴A-(B∪Ｃ）=（A-B)∩(A-C）
((P∨Q）∧R)∨((Q∨P)∧Ｒ)((P∨Q)∨(Ｑ∨Ｐ))∧R
((P∨Q)∨(Ｐ∨Ｑ))∧RT∧R(置换）R
2）x(Ａ（ｘ)B(x)）xＡ(x）xB(x)
证明 :x(A(x)Ｂ(x））x（A（x)∨B(x))xA(x)∨xB(x)xA（x)∨xB(x)xA(x)xＢ(ｘ）
二、求命题公式(P∨(Q∧Ｒ))(Ｐ∧Q∧R）的主析取范式和主合取范式(１０分)