离散数学.doc

文档介绍：离散数学试题(A卷答案)
一、(10分)
(1)证明(P®Q)∧(Q®R)Þ(P®R)
(2)求(P∨Q)®R的主析取范式与主合取范式,并写出其相应的成真赋值和成假赋值。
解:(1)因为((P®Q)∧(Q®R))®(P®R)
ÛØ((ØP∨Q)∧(ØQ∨R))∨(ØP∨R)
Û(P∧ØQ)∨(Q∧ØR)∨ØP∨R
Û(P∧ØQ)∨((Q∨ØP∨R)∧(ØR∨ØP∨R))
Û(P∧ØQ)∨(Q∨ØP∨R)
Û(P∨Q∨ØP∨R)∧(ØQ∨Q∨ØP∨R)
ÛT
所以,(P®Q)∧(Q®R)Þ(P®R)。
(2)(P∨Q)®RÛØ(P∨Q)∨RÛ(ØP∧ØQ)∨R
Û(ØP∨(Q∧ØQ)∨R)∧((P∧ØP)∨ØQ∨R)
Û(ØP∨Q∨R)∧(ØP∨ØQ∨R)∧(P∨ØQ∨R)∧(ØP∨ØQ∨R)
Û∧∧
Û∨∨∨
所以,其相应的成真赋值为000、001、011、101、111:成假赋值为:010、100、110。
二、(10分)分别找出使公式"x(P(x)®$y(Q(y)∧R(x,y)))为真的解释和为假的解释。
解:设论域为{1,2}。
若P(1)=P(2)=T,Q(1)=Q(2)=F,R(1,1)=R(1,2)=R(2,1)=R(2,2)=F,则
"x(P(x)®$y(Q(y)∧R(x,y)))
Û"x(P(x)®((Q(1)∧R(x,1))∨(Q(2)∧R(x,2))))
Û(P(1)®((Q(1)∧R(1,1))∨(Q(2)∧R(1,2))))∧(P(2)®((Q(1)∧R(2,1))∨(Q(2)∧R(2,2))))
Û(T®((F∧F)∨(F∧F)))∧(T®((F∧F)∨(F∧F)))
Û(T®F)∧(T®F)
ÛF
若P(1)=P(2)=T,Q(1)=Q(2)=T,R(1,1)=R(1,2)=R(2,1)=R(2,2)=T,则
"x(P(x)®$y(Q(y)∧R(x,y)))
Û"x(P(x)®((Q(1)∧R(x,1))∨(Q(2)∧R(x,2))))
Û(P(1)®((Q(1)∧R(1,1))∨(Q(2)∧R(1,2))))∧(P(2)®((Q(1)∧R(2,1))∨(Q(2)∧R(2,2))))
Û(T®((T∧T)∨(T∧T)))∧(T®((T∧T)∨(T∧T)))
Û(T®T)∧(T®T)
ÛT
三、(10分)
在谓词逻辑中构造下面推理的证明:每个喜欢步行的人都不喜欢做汽车,每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车,因而有的人不喜欢步行。
解论域:所有人的集合。():喜欢步行;():喜欢坐汽车;():喜欢骑自行车;则推理化形式为:
(()®Ø()),(()∨()),Ø()Ø()
下面给出证明:
(1)Ø() P
(2)Ø() T(1),E
(3)Ø() T(2),ES
(4)(()∨()) P
(5)()∨() T(4),US
(6)() T(3)(5),I
(7)(()®Ø()) P
(8)()®Ø() T(7),US
(9)Ø() T(6)(8),I
(10)Ø() T(9) ,EG
四、(10分)
下列论断是否正确?为什么?
(1)若A∪B=A∪C,则B=C。
(2)若A∩B=A∩C,则B=C。
(3