离散数学期末复习

离散数学内容 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 第一篇 数理逻辑 第1章 命 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 逻辑 求命题公式的主析取范式及主合取范式 例 求 的主析取范式及主合取范式。 主析取范式 主合取范式 例 求(P→Q) R的主析取范式及主合取范式。 例 求命题公式 的主析取范式和主合取范式。 例 求公式A=(pq)r的主析取范式与主合取范式。 例 求 的主析取范式。 判断公式类型 例 用等值演算法判断公式q (pq)的类型 例 判断下列命题公式的类型（永真式、永假式、可满足式），方法不限。 (1) (2) 证明 例 证明： 例 证明： 例 推证： Q∧(P→Q) P 例 前提： ，结论： 。该结论是否有效？请说明原因。 证明：①     前提引入 ②         前提引入 ③     　前提引入 ④     　①②③构造二难 在命题逻辑中构造下面推理的证明： 例 如果小张守第一垒并且小李向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语言程序设计课的老师有会，所以进行离散数学课的考试。 解：设 ：今天是星期一， ：进行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            ⑤置换 例 若明天是周一或周二，小华就要考试。若要考试，今天必须复习。小华今天没复习。所以，明天不是周一和周二。 解：设 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将不愉快。 解（P25）：设A：A工作努力； B：B将愉快； C：C将愉快； D：D将愉快； 形式结构为 前提： ， ， 结论： 第2章 谓词逻辑 求谓词公式的前束范式 例 求谓词公式 的前束范式 例 求公式?x F(x)∧ ?x G(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度。 所有的有理数均可以 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示成分数。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) G(x))          前提引入 ③ F(a) G(a)                ②UI 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf ④ F(a)                        ①③拒取 非洲人都不怕热，玛丽怕热。所以玛丽不是非洲人。 凡奇数均不能被2整除，8能被2整除。所以8不是奇数。 凡奇数均不能被2整除，36能被2整除。所以36不是奇数。 英语系学生都不学离散数学，小刘学离散数学。因此，小刘不是英语系学生。 海南人都不怕热，小赵怕热。所以小赵不是海南人。 无理数都不能表示成分数，3.1415能表示成分数。所以3.1415不是无理数。 例 鸟都会飞，麻雀是鸟，所以麻雀会飞。 例 乌鸦都不是白色的，北京鸭是白色的。因此，北京鸭不是乌鸦。 解: 设F(x): x是乌鸦, G(x): x白色, a: 北京鸭 前提: x(F(x) G(x)), G(a) 结论: F(a) 证明: ① G(a)                          前提引入 ② x(F(x) G(x))          前提引入 ③ F(a) G(a)                ②UI规则 ④ F(a)                        ①③拒取 第二篇 集合论 第3章 集合 计算 例 设 . 例 设A={{a,{b}},c,{c},{a,b}}，B={{a,b},{b}}，计算(1)A∩B，(2)A⊕B，(3)P(B) 集合恒等式的证明 例 设A、B、C是三个集合，证明：A B=A (B-A) 例 设A、B、C是三个集合，证明：A－(B C)＝(A－B)－C 例 设A、B、C是三个集合，证明：A (B－C)＝(A B)－(A C) 例 设A、B、C是三个集合，证明：(A－B) (A－C)=A－(B C) 例 设A、B、C是任意三个集合，证明： ((A (B－C)) A) (B－(B－A))＝A。 例 设A、B、C是任意三个集合，证明：((A (B－C)) A) (B－(B－A))＝A 例 设A，B，C为集合，证明：A∩(B－C)=(A－C)∩(B－C) 例 已知A∩B=A∩C，且 ∩B= ∩C，证明B=C。 包含排斥原理（即容斥原理）的简单应用 例 假设某班有20名学生，其中有10人英语成绩为优，有8人数学成绩为优，又知有6人英语和数学成绩都为优。问两门课都不为优的学生有几名？ 解：A={英语成绩为优}，B={数学成绩为优}。 例 有100名程序员，其中47名熟悉C++语言，35名熟悉JAVA语言，23名熟悉这两种语言。问有多少人对两种语言都不熟悉？ 例 在一个班级的50名学生中，有26人在第一次考试中得到A，21人在第二次考试中得到A，假如有17人两次考试都没得到A，问有多少学生两次考试都得到A？ 第4章 关系 第5章 函数 例 设集合A={1,2,3,4,5}，A上的关系R和S为：R={|x+y=5,x,y A},S={|x，<2,3>}， S={<1,2>，<1,3>，<1,4>，<1,5>，<2,3>，<2,4>，<2,5>，<3,4>，<3,5>，<4,5>} R S={<1,5>，<2,4>，<2,5>} 例 设A={0,1,2,3}，A上的两个关系：