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

离 散 数 学 考 试 试 题 (A 卷 及 答 案 ） 一、证明题（10 分） 1) (P∧Q∧AC)∧(AP∨Q∨C) (A∧(PQ))C。P<->Q=(p->Q)合取（Q->p） 证明: (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 使（非 P 析取 Q 析取 R）为 0 所赋真值，即 100，二进制为 4 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 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 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)...