离散数学考试试题(A、B卷及答案)test2

离散数学考试试题(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) 4M∧5M ∧6M 0m ∨1m ∨2m ∨3m ∨7m 所以，公式(P(Q∨ R))∧ (P∨ (QR))为可满足式，其相应的成真赋值为000、001、 010、 011、 111：成假赋值为：100、 101、 110。 真值表法： P Q R QR P(Q∨ R) P∨ (QR) (P(Q∨ R))∧ (P∨ (QR)) 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 1 由真值表可知，公式(P(Q∨ R))∧ (P∨ (QR))为可满足式，其相应的成真赋值为 000、 001、 010、 011、 111：成假赋值为：100、 101、 110。 三、推理证明题（10 分） 1） P∨ Q， Q∨ R， RS P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)...