离散数学内容总结离散数学内容总结第一篇数理逻辑第1章命题逻辑求命题公式的主析取范式及主合取范式求命题公式的主析取范式及主合取范式例求((p∨q)∧r)∨p的主析取范式及主合取范式。例求(P→Q)∧R的主析取范式及主合取范式。例求命题公式(P∧Q)∨R的主析取范式和主合取范式。例求公式A=(p→q)→r的主析取范式与主合取范式。例求(p→q)→r的主析取范式。判断公式类型例用等值演算法判断公式q∧(p→q)的类型例判断下列命题公式的类型（永真式、永假式、可满足式），方法不限。(1)(2)证明例证明：(p∨q)→r(p→r)∧(q→r)例证明：p→(q→r)(p∧q)→r例推证：Q∧(P→Q)P例前提：p→r,q→s,p∨q，结论：r∨s。该结论是否有效？请说明原因。在命题逻辑中构造下面推理的证明：在命题逻辑中构造下面推理的证明：例如果小张守第一垒并且小李向B队投球，则A队获胜。或者A队未获胜，或者A队成为联赛的第一名。小张守第一垒。A队没有成为联赛的第一名。因此小李没有向B队投球。解：先将简单命题符号化。P：小张守第一垒；Q：小李向B队投球；R：A队取胜；S：A队成为联赛第一名。前提：(P∧Q)→R，R∨S，P，S结论：Q证明：(1)R∨S前提引入(2)S前提引入(1)(2)析取三段论(3)R(4)(P∧Q)→R前提引入(5)(P∧Q)(3)(4)拒取式(6)P∨Q(5)置换(7)P前提引入(8)Q(6)(7)析取三段论例一个公安人员审查一件盗窃案，已知下列事实：（1）甲或乙盗窃了录像机；（2）若甲盗窃了录像机，则作案时间不能发生在午夜前；（3）若乙的证词正确，则午夜时屋里灯光未灭；（4）若乙的证词不正确，则作案时间发生在午夜前；（5）午夜时屋里灯光灭了。根据以上事实，推断谁是盗窃犯。（在命题逻辑中构造推理证明。）解：分析如下。首先将元素符号化：P：甲偷了录像机；Q：乙偷了录像机；R：作案时间在午夜；S：乙的正词正确；T：午夜时灯光未灭。前提：P∨Q,P→R,S→T,S→R,T推演：(1)T前提引入(2)S→T前提引入(3)S(1)(2)拒取式(4)S→R前提引入(5)R(3)(4)假言推理(6)P→R前提引入(7)P(5)(6)拒取式(8)P∨Q前提引入(9)Q(7)(8)析取三段论所以乙偷了录像机。例如果今天是周一，则要进行离散数学或C语言程序设计两门课中一门课的考试。如果C语言程序设计课的老师有会，则不考C语言程序设计。今天是周一，C语言程序设计课的老师有会，所以进行离散数学课的考试。例若明天是星期一或星期三，我就有课。若有课，今天必须备课。我今天没备课。所以，明天不是星期一和星期三。解设p:明天是星期一,q:明天是星期三，r:我有课，s:我备课前提:(p∨q)→r,r→s,s结论:p∧q证明①r→s②s③r④(p∨q)→r⑤(p∨q)⑥p∧q前提引入前提引入①②拒取式前提引入③④拒取式⑤置换结论有效,即明天不是星期一和星期三例若明天是周一或周二，小华就要考试。若要考试，今天必须复习。小华今天没复习。所以，明天不是周一和周二。（答案同上）例如果A工作努力，B或C将生活愉快。如果B生活愉快，那么A将不努力工作。如果D愉快，则C将不愉快。所以，如果A工作努力，D将不愉快。第2章谓词逻辑求谓词公式的前束范式例求谓词公式xP(x)→xQ(x)的前束范式解xF(x)→yG(y)xy(F(x)→G(y))换名规则量词辖域扩张例求公式xF(x)∧xG(x)的前束范式。解：xF(x)∧xG(x)xF(x)∧xG(x)(*量词否定等值式xP(x)xP(x)*)x(F(x)∧G(x))(*量词分配等值式x(A(x)∧B(x))xA(x)∧xB(x)*)证明例证明：x(A(x)∧B(x))x(A(x)→B(x))在一阶逻辑中符号化下述命题，并推证之。在一阶逻辑中符号化下述命题，并推证之。例凡人必有一死，苏格拉底是人，所以苏格拉底会死的。解令F(x):x是人,G(x):x是要死的,a:苏格拉底前提:x(F(x)→G(x)),F(a)结论:G(a)证明:①F(a)前提引入②x(F(x)→G(x))前提引入③F(a)→G(a)②UI④G(a)①③假言推理凡人都会犯错，小王是人，所以小王会犯错。所有三角形其内角和为180度。△ABC是三角形。所以△ABC内角和为180度。所有的有理数均可以表示成分数。0.3是有理数。所以0.3可以表示成分数。偶数都可以被2整除，6是偶数。所以6可以被2整除。哲学家都善于思考。柏拉图是哲学家。所以，柏拉图善于思考。例东北人都不怕冷，王国端怕冷。所以王国端不是东北人。解:设F(x):x是东北人,G(x):x怕冷,a:王国端前提:x(F(x)→G(x)),G(a)结论:F(