离散数学内容总结
第一篇 数理逻辑
第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队投球。
例 一个公安人员审查一件盗窃案，已知下列事实： （1）甲或乙盗窃了录像机；
（2）若甲盗窃了录像机，则作案时间不能发生在午夜前； （3）若乙的证词正确，则午夜时屋里灯光未灭；
（4）若乙的证词不正确，则作案时间发生在午夜前； （5）午夜时屋里灯光灭了。
根据以上事实，推断谁是盗窃犯。（在命题逻辑中构造推理证明。）
例 如果今天是周一，则要进行离散数学或C语言程序设计两门课中一门课的考试。如果C语言程序设计课的老师有会，则不考C语言程序设计。今天是周一，C语言程序设计课的老师有会，所以进行离散数学课的考试。
例 若明天是星期一或星期三，我就有课。若有课，今天必须备课。我今天没备课。所以，明天不是星期一和星期三。
例 若明天是周一或周二，小华就要考试。若要考试，今天必须复习。小华今天没复习。所以，明天不是周一和周二。
例 如果A工作努力，B或C将生活愉快。如果B生活愉快，那么A将不努力工作。如果D愉快，则C将不愉快。所以，如果A工作努力，D将不愉快。
第2章 谓词逻辑
求谓词公式的前束范式
例 求谓词公式?xP(x)??xQ(x)的前束范式 例 求公式?x F(x)∧??x G(x)的前束范式。
证明
例 证明：﹁?x(A(x)∧B(x))??x(A(x)→﹁B(x))
在一阶逻辑中符号化下述命题，并推证之。
例 凡人必有一死，苏格拉底是人，所以苏格拉底会死的。 凡人都会犯错，小王是人，所以小王会犯错。
所有三角形其内角和为180度。△ABC是三角形。所以△ABC内角和为180度。 所有的有理数均可以表示成分数。0.3是有理数。所以0.3可以表示成分数。 偶数都可以被2整除，6是偶数。所以6可以被2整除。 哲学家都善于思考。柏拉图是哲学家。所以，柏拉图善于思考。 例 东北人都不怕冷，王国端怕冷。所以王国端不是东北人。 非洲人都不怕热，玛丽怕热。所以玛丽不是非洲人。 凡奇数均不能被2整除，8能被2整除。所以8不是奇数。 凡奇数均不能被2整除，36能被2整除。所以36不是奇数。
英语系学生都不学离散数学，小刘学离散数学。因此，小刘不是英语系学生。
海南人都不怕热，小赵怕热。所以小赵不是海南人。
无理数都不能表示成分数，3.1415能表示成分数。所以3.1415不是无理数。 例 鸟都会飞，麻雀是鸟，所以麻雀会飞。
例 乌鸦都不是白色的，北京鸭是白色的。因此，北京鸭不是乌鸦。
第二篇 集合论
第3章 集合
计算
例 设A??1,2,3?,B??2,3,4,5?,Z??2,3?,求（A?B）?Z.
例 设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，且A∩B=A∩C，证明B=C。
包含排斥原理（即容斥原理）的简单应用
例 假设某班有20名学生，其中有10人英语成绩为优，有8人数学成绩为优，又知有6人英语和数学成绩都为优。问两门课都不为优的学生有几名？ 例 有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={ R = {(a,b)︱a=b+1或a=b/2}，S = {(a,b)︱b=a+2 }，求(1)R?S，(2) S?R。 例 设B={1,2,3,4}，B上的关系R＝{〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉｝， 求(1)R?R (2) R-1 例 设A={a,b,c,d}，A上的关系R＝{ 例 设集合A＝{2,4,6,8,10,12}，B={2,4,6}，从A到B的关系R＝{ 例 设集合A＝｛1,2,3,4,5,6｝，B={1,2,3}，从A到B的关系R＝｛〈x,y〉|x=2y｝，求(1)R,(2)R 例 设R1={<1,2>,<2,2>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>}，求(1) R1-1 ，(2) R1?R2 例 R1={<1,2>,<1,3>,<2,3>,<3,3>}, R2={<2,2>,<2,3>,<3,4>}, (1) 求 R1-1 (2) 求R2?R1 (3)R1是函数吗？ 例 设A={a,b,c,d}，R={ R={?a,b?,?b,a?,?a,c?,?b,d?,?b,e??d,a?,?e,a?,?e,c?} （1）试画出R的关系图； （2）求R的自反闭包和对称闭包。 例 R1={<1,2>,<1,3>,<2,3>,<3,3>}, R2={<2,2>,<2,3>,<3,4>}, (1) 求 R1-1 (2) 求R2?R1 (3)R1是函数吗？ -1 例 设集合A={a,b,c,},B={b,c,d},C={d,e,f},R1={<1,2>,<2,2>,<2,3>,<3,3>}, R2={<2,2>,<2,3>,<3,4>}， 求(1)A?B，(2)A⊕B，(3) R1-1 ，(4) R1?R2 例 设A={a，b，c}，R是A幂集上的包含关系，说明R是偏序关系并画出R的哈斯图。 例 求集合A={1,2,3}的幂集，R是A幂集上的包含关系，说明R是偏序关系并画出R的哈斯图。
相关推荐：
loading