离散数学期末复习.pdf

离散数学内容总结第一篇数理逻辑第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前提引入(3)R(1)(2)析取三段论(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:我备课前提:∨(pq)→r,→s,r﹁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)换名规则xy(F(x)G(y))量词辖域扩张例求公式∀xF(x)∧∃xG(x)的前束范式。解：∀xF(x)∧∃xG(x)∀xF(x)∧∀xG(x)(*量词否定等值式∃xP(x)∀xP(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):是人,xG(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(a)证明:①G(a)前提引入②x(F(x)