离散数学考试试题0.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)若A(B＝A(C，则B＝C。 解 (1)不一定。例如，令A＝{1}，B＝{1，2}，C＝{2}，则A∪B＝A∪C，但B＝C不成立。 (2)不一定。例如，令A＝{1}，B＝{1，2}，C＝{1，3}，则A∩B＝A∩C，但B＝C不成立。 (3)成立。因为若A(B＝A(C，对任意的∈B，当∈A时，有∈A∩B((A(B((A(C＝(A∪C)－(A∩C)(∈A∩C(∈C，所以B(C；当(A时，有(A∩B，而∈B(∈A∪B，所以∈A∪B－A∩B＝A(B(∈A(C，但( A，于是∈C，所以B(C。 同理可证，C (B。 因此，当A(B＝A(C时，必有B＝C。 五、（10分）若R是集合A上的自反和传递关系，则对任意的正整数n，Rn＝R。 证明 当＝1时，结论显然成立。设＝时，Rk＝R。当＝＋1时，Rk+1＝Rk*R＝R*R。下面由R是自反和传递的推导出R*R＝R即可。 由传递性得R*R(R