离散数学期末复习

离散数学内容总结 第一篇 数理逻辑 第1章 命题逻辑 求命题公式的主析取范式及主合取范式 例 求prqp的主析取范式及主合取范式。 例 求(P→Q)  R 的主析取范式及主合取范式。 例 求命题公式RQP)(的主析取范式和主合取范式。 例 求公式A=(pq)r的主析取范式与主合取范式。 例 求rqp的主析取范式。 判断公式类型 例 用等值演算法判断公式q (pq)的类型 例 判断下列命题公式的类型（永真式、永假式、可满足式），方法不限。 (1) (2) 证明 例 证明：rqrprqp 例 证明：rqprqp)()( 例 推证：  Q∧(P→Q)  P 例 前提：qpsqrp,,，结论：sr 。该结论是否有效？请说明原因。 在命题逻辑中构造下面推理的证明： 例 如果小张守第一垒并且小李向 B 队投球，则 A 队获胜。或者 A 队未获胜，或者 A 队成为联赛的第一名。小张守第一垒。A 队没有成为联赛的第一名。因此小李没有向 B 队投球。 例 一个公安人员审查一件盗窃案，已知下列事实： （1）甲或乙盗窃了录像机； （2）若甲盗窃了录像机，则作案时间不能发生在午夜前； （3）若乙的证词正确，则午夜时屋里灯光未灭； （4）若乙的证词不正确，则作案时间发生在午夜前； （5）午夜时屋里灯光灭了。 根据以上事实，推断谁是盗窃犯。（在命题逻辑中构造推理证明。） 例 如果今天是周一，则要进行离散数学或C语言程序设计两门课中一门课的考试。如果C语言程序设计课的老师有会，则不考C语言程序设计。今天是周一，C语言程序设计课的老师有会，所以进行离散数学课的考试。 例 若明天是星期一或星期三，我就有课。若有课，今天必须备课。我今天没备课。所以，明天不是星期一和星期三。 例 若明天是周一或周二，小华就要考试。若要考试，今天必须复习。小华今天没复习。所以，明天不是周一和周二。 例 如果A 工作努力，B 或C 将生活愉快。如果B 生活愉快，那么A 将不努力工作。如果D 愉快，则C 将不愉快。所以，如果A 工作努力，D 将不愉快。 第2章 谓词逻辑 求谓词公式的前束范式 例 求谓词公式)()(xxQxxP的前束范式 例 求公式∀x F(x)∧ ∃x G(x)的前束范式。 证明 例 证明：﹁ x(A(x)∧B(x)) x(A(x)→﹁B(x)) 在一阶逻辑中符号化下述命题，并推证之。 例 凡人必有一死，苏格拉底是人，所以苏格拉底会死...