离散作业答案.pdf

第一章第一章 命题逻辑命题逻辑 1 第 7 页第 3 题 2 解 此题注意 P 仅当 Q 翻译成PQ 逆命题 如果你去 那么我逗留 反命题 如果我不逗留 那么你没去 逆反命题 如果你没去 那么我不逗留 3 解 逆命题 如果方程 nnn xyz 无整数解 那么 n 是大于 2 的正整数 反命题 如果 n 不是大于 2 的正整数 那么方程 nnn xyz 有整数解 逆反命题 如果方程 nnn xyz 有整数解 那么 n 不是大于 2 的正整数 4 解 逆命题 如果我不完成任务 那么我不获得更多的帮助 反命题 如果我获得了更多的帮助 那么我能完成任务 逆反命题 如果我能完成任务 那么我获得了更多的帮助 2 第 7 页第 4 题 1 PQRQPRS TTFTTFF TFT TF T 3 PQRPQS TTFTTF TTFT TT T 3 第 7 页第 5 题 2 PQRPQPR P Q R PQR PQPR PQRPQPR F F F T F F F F T T F F F T F T F F F T T F T F T F F F T F T F T F T F T T F F T F T T T F T F 4 PPQRQR P Q R PPQR PPQRQR F F F T T F F T F F F T F T T F T T F F T F F T T T F T F F T T F F T T T T F F 4 第 7 页第 6 题 证明 P Q PQ PQ QP F F T T T F T F T F T F F F T T T T T T 由上表可知 当PQ 为T时 PQ 和QP 都是T PQ 和QP 为T时 PQ 为T 故命题得证 5 第 7 页第 7 题 P Q PQ PQ F F T T F T T T T F F F T T T T 6 第 7 页第 8 题 1 是可交换的 2 真值表如下 P Q PQ QP PQ QP PQ QP PQ QP F F F F F F T T T T F T F F T T T F F F T F F F T T F T F F T T T T T T T T T T 7 第 7 页第 9 题 1 是可结合的 2 真值表如下 P Q R PQR PQR PQR PQR F F F F F F T F F T F T T T F T F F T F T F T T F T T F T F F F T T T T F T F T T F T T F F T F F T T T T T T T P Q R PQR PQR PQR PQR F F F F F T T F F T F T T T F T F F T T T F T T F T T F T F F F T T T T F T F T T F T T F F T F F T T T T T T T 8 第 15 页第 1 题 1 重言式 PPT 3 重言式 PPT 5 重言式 PQPQPQPQT 9 重言式 PPQ FQT 10 可满足式 PQQ PQQPQQ 当Q为真时公式为真 Q为假时公式为假 故为可 满足式 14 可满足式 PQRSPRQS PQRSPRQS PRQSPRQS 当Q或S有一个为真时公式为真 当Q和S均为假时 若P和R真值相同时 公式 为真 真值不同时 公式为假 故公式是可满足式 9 第 15 页第 2 题 1 PQRP PQRPQRPP PQRPQRPP TQRPP QRPP PPQR 4 PQRP PQRP PQRP PQR PQR 5 PQP PQP PQP T 10 第 15 页第 3 题 1 PQP PQP F 2 PQQPQ PTPQ TPQ PQ PQ 3 PQRP PQRP PQRPQP PQRF PQR PQR 11 第 15 页第 5 题 1 PQPT 证明 PQP PQP PQP T 2 PQPF 证明 PQP PQP PQP PQP F 4 PPPPF 证明 PPPP PPPP PP F 12 第 15 页第 6 题 1 PQPQ 证明 PQPQ PQPQ PQPQ PQQ T 或者这么做 设PQ 为真 那么 P 为真 并且 Q 为真 因此PQ 为真 所以PQPQ 3 PQPPQ 证明 PQPPQ PQPPQ PQPPPQ PQPQ PQPQ T 5 PPQPPRQR 证明 PPQPPRQR TQTRQR FQFRQR QRQR T 13 第 15 页第 7 题 对于代入规则 1 如果是可满足式 使用代入规则后可能是重言式 可满足式或矛盾式 如 可满 足式PQ 将Q分别替换为P R分别得到重言式PP 和可满足式PR 对于可 满足式PQ 将Q替换为P 得到矛盾式PP 2 如果是矛盾式 使用代入规则后仍然是矛盾式 设P是矛盾式 则P 是重言式 而对于重言式使用代入规则后仍为重言式 即 P 是重言式 故 P 是矛盾式 对于替换规则 由于替换规则是一种对子公式逻辑上等价的替换 故对于重言式 可满足式 和矛盾式使用替换规则后其真值不变 14 第 15 页第 8 题 1 PQPP 用PQ 代P 用 PQP 代Q 解 PQPQPPQPQ 2 PQQP 用Q代P 用P 代Q 解 QPPQ 15 补充题 试证明 QACAPCAPQC 证明 QACAPC QACAPC ACQACP ACPQ 16 第 15 页 4 1 PQPQP 证明 PQPQ PQPQ PQQ PT P 对偶式 PQPQP 2 PQPQPQPQ 证明 PQPQPQ PQQPQ PPQ PPPQ PQ PQ 对偶式 PQPQPQPQ 3 QPQPT 证明 QPQP QPQP QPQP PQPQ T 对偶式 QPQPF 17 第 21 页第 2 题 1 PQPQ 合取范式 0 PQPQQP PQPQQP PQQP PQPQ PQPQ PQ 析取范式 1 2 3 2 PPQQR 合取范式 0 PPQQR PQR 析取范式 1 2 3 3 PQRPQR 合取范式 1 2 3 4 5 6 PQRPQR PQPRPQPR PQRPQRPQRPQRPQRPQR 析取范式 0 7 4 PQSPQR 析取范式 6 7 9 11 PQRSPQRSPQRSPQRS 合取范式 0 1 2 3 4 5 8 10 12 13 14 15 18 第 25 页第 3 题 证明 1 B P 规则 2 BAC P 规则 3 AC T 规则 1 2 4 ABC P 规则 5 AC T 规则 1 4 6 ACAC T 规则 5 7 AC T 规则 3 8 AC T 规则 6 7 9 AC T 规则 8 因此 AC 是题目的有效结论 AC 不是 19 第 25 页第 5 题 1 PQ QR RS PS S 证明 1 S P 规则 2 PS P 规则 3 P T 规则 1 2 11 I 4 PQ P 规则 5 Q T 规则 3 4 10 I 6 QR P 规则 7 R T 规则 5 6 10 I 8 RS P 规则 9 S T 规则 7 8 9 I 推出结论与前提矛盾 因此命题公式不能同时为真 20 第 25 页第 7 题 a PQQRRP 证明 1 R P 规则 2 QR P 规则 3 Q T 规则 1 2 4 PQ P 规则 5 PQ T 规则 4 6 P T 规则 3 5 b PQRRS SPQ 证明 1 S P 规则 2 RS P 规则 3 R T 规则 1 2 4 PQR P 规则 5 PQ T 规则 3 4 6 PQ T 规则 5 3 PQR RS QTP 由RS 得 R 为真 再由 PQR 得 PQ 真假任意 故无法推出 P 一定为真的 结论 题目有问题 21 第 25 页第 8 题 a PQQR RSPS 证明 1 P P 规则 假设前提 2 PQ P 规则 3 Q T 规则 1 2 4 QR P 规则 5 R T 规则 3 4 6 RS P 规则 7 S T 规则 5 6 8 PS CP 规则 1 7 b PQPPQ 证明 1 P P 规则 假设前提 2 PQ P 规则 3 Q T 规则 1 2 4 PQ T 规则 1 3 5 PPQ CP 规则 1 4 c PQRPQR 证明 1 PQ P 规则 假设前提 2 P T 规则 1 3 Q T 规则 1 4 PQ T 规则 2 3 5 PQR P 规则 6 R T 规则 4 5 7 PQR CP 规则 1 6 22 第 25 页第 9 题 a RQ RS SQ PQP 证明 1 P P 规则 假设前提 2 P T 规则 1 3 PQ P 规则 4 Q T 规则 2 3 5 SQ P 规则 6 S T 规则 4 5 7 RS P 规则 8 R T 规则 6 7 9 RQ P 规则 10 Q T 规则 8 9 11 QQ T 规则 4 10 12 P F 规则 1 11 b SQ RSR PQP 证明 1 P P 规则 假设前提 2 P T 规则 1 3 PQ P 规则 4 Q T 规则 2 3 5 SQ P 规则 6 S T