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

1 / 6 离散数学考试试题(A 卷及答案）一、证明题（ 10 分）1) ( P∧Q∧AC) ∧( AP∨Q∨C) ( A∧( PQ))C。P<->Q=(p->Q) 合取（ Q->p）证明 : ( P∧Q∧AC) ∧( AP∨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∧( PQ)) ∨C (A∧( PQ))C2) (PQ)PQ。证明：(P Q)((P∧Q))(P∨Q))PQ。二、分别用真值表法和公式法求( P( Q∨R)) ∧(P∨( QR)) 的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15 分）。主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。主析取范式可由析取范式经等值演算法算得。证明：公式法：因为 (P( Q∨R)) ∧(P∨( QR)) (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，二进制为 40m ∨1m ∨2m ∨3m ∨7m所以，公式 ( P( Q∨ R)) ∧ (P∨( QR)) 为可满足式，其相应的成真赋值为000、001、 010、011、111：成假赋值为：100、101、110。2 / 6 真值表法：PQRQR P( Q∨ R)P∨( QR) ( P( Q∨ R)) ∧(P∨( QR)) 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∨( QR)) 为可满足式， 其相应的成真赋值为 000、001、010、011、 111：成假赋值为：100、101、110。三、推理证明题（10 分）1）P∨Q，Q∨R，RSPS。证明：(1) P附加前提(2)P∨Q P (3) Q T(1)(2)，I （析取三段论）(4)Q∨R P (5) R T(3)(4)，I （析取三段论）(6) RS P (7) S T(5)(6)， I （假言推理）(8) PS 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) (8)P(a) (9)P(a)∧R(a) 3 / 6 (10)x(P(x) ∧R(x)) (11)Q(y)∧ x(P(x)∧R(x)) 五、已知A、B...