《离散数学期末复习(20170907201151)》由会员分享，可在线阅读，更多相关《离散数学期末复习(20170907201151)（14页珍藏版）》请在金锄头文库上搜索。
1、离散数学内容总结第一篇数理逻辑第 1 章 命题逻辑求命题公式的主析取范式及主合取范式例 求prqp的主析取范式及主合取范式。主析取范式11 010001011110101 010010111 0111()()()()()()()pqrpprqrppqrpqrpqrpqrpqrmmmmmmmmmm主合取范式000001011()()()()()()()()()pqrppqpprpqprpqrpqrpqrpqrMMM例 求(PQ)R 的主析取范式及主合取范式。()()()()pqrpqrprqr例 求命题公式RQP)(的主析取范式和主合取范式。()()()PQRPRQR例 求公式A=(pq)r的主
2、析取范式与主合取范式。()()()()()pqrpqrpqrprqr例 求rqp的主析取范式。()()()()pqrpqrpqrprqr判断公式类型例 用等值演算法判断公式q (pq)的类型()()()0qpqqpqqpq例 判断下列命题公式的类型（永真式、永假式、可满足式），方法不限。(1) ()()()()()()1pqpqpqpqpqpq(2) ()()()()1(0)000ppqqrpppqqrprp证明例 证明：rqrprqppqrpqrpqrprqrprqr例 证明：rqprqp)()()()()()()pqrpqrpqrpqrpqr例 推证：Q(PQ)P ()()()()qpqq
3、pqqpqqqpp例 前提：qpsqrp,，结论：sr。该结论是否有效？请说明原因。证明：rp前提引入sq前提引入qp前提引入sr构造二难在命题逻辑中构造下面推理的证明：例 如果小张守第一垒并且小李向B 队投球，则 A 队获胜。或者A 队未获胜，或者 A 队成为联赛的第一名。小张守第一垒。A 队没有成为联赛的第一名。因此小李没有向 B 队投球。解：先将简单命题符号化。P：小张守第一垒；Q：小李向B 队投球； R：A 队取胜； S：A队成为联赛第一名。前提： (PQ)R ，RS，P，S 结论：Q 证明：(1) RS 前提引入(2) S 前提引入(3) R (1)(2)析取三段论(4) (PQ)R
4、 前提引入(5) (PQ) (3)(4) 拒取式(6) PQ (5)置换(7) P 前提引入(8) Q (6)(7)析取三段论例 一个公安人员审查一件盗窃案，已知下列事实：（1）甲或乙盗窃了录像机； （2）若甲盗窃了录像机，则作案时间不能发生在午夜前； （3）若乙的证词正确，则午夜时屋里灯光未灭； （4）若乙的证词不正确，则作案时间发生在午夜前； （5）午夜时屋里灯光灭了。 根据以上事实，推断谁是盗窃犯。 （在命题逻辑中构造推理证明。 ）解：分析如下。首先将元素符号化：P：甲偷了录像机；Q ：乙偷了录像机；R ：作案时间在午夜；S：乙的正词正确；T：午夜时灯光未灭。前提： PQ,P R, ST
5、,SR,T 推演：(1) T 前提引入(2) ST前提引入(3) S (1)(2)拒取式(4) SR前提引入(5) R (3)(4)假言推理(6) P R 前提引入(7) P (5)(6)拒取式(8) PQ前提引入(9) Q (7)(8)析取三段论所以乙偷了录像机。例 如果今天是周一，则要进行离散数学或C语言程序设计两门课中一门课的考试。如果 C语言程序设计课的老师有会，则不考C语言程序设计。今天是周一，C语言程序设计课的老师有会，所以进行离散数学课的考试。解：设p：今天是星期一，q：进行C语言程序设计考试，r：进行离散数学考试，s：C语言程序设计老师有会。前提：rqp,qs,p,s结论：r证
6、明rqp前提引入p前提引入rq假言推理qs前提引入s前提引入q假言推理r析取三段论例 若明天是星期一或星期三，我就有课。若有课，今天必须备课。我今天没备课。所以，明天不是星期一和星期三。解：设p：明天是星期一，q：明天是星期三，r：我有课， s：我备课，形式结构为前提： (pq)r, rs, s 结论：pq 证明 rs 前提引入s 前提引入r 拒取式 (pq)r 前提引入(pq) 拒取式pq 置换例 若明天是周一或周二，小华就要考试。若要考试，今天必须复习。小华今天没复习。所以，明天不是周一和周二。解：设p：明天是周一，q：明天是周二，r：小华要考试，s：今天必须复习，形式结构为前提： (pq
7、)r, rs, s 结论：pq 证明 rs 前提引入s 前提引入r 拒取式 (pq)r 前提引入(pq) 拒取式pq 置换例 如果 A 工作努力， B 或 C 将生活愉快。如果B 生活愉快，那么 A 将不努力工作。如果 D 愉快，则 C 将不愉快。所以，如果A 工作努力， D 将不愉快。解（ P25） ：设 A： A 工作努力；B： B 将愉快；C： C 将愉快；D：D 将愉快；形式结构为前提：()ABC，BA，DC结论：AD第 2 章 谓词逻辑求谓词公式的前束范式例 求谓词公式)()(xxQxxP的前束范式()()()()()()()()xPxxQxxPxxQxxPxxQxxP xQx例 求
8、公式 ? x F(x)? x G(x)的前束范式。()()()()()()xFxxGxxFxxG xx FxG x证明例 证明：x(A(x) B(x)x(A(x) B(x)()()()()()()()()()()()()x A xB xx A xB xx A xB xxA xB xxA xB xx A xBx在一阶逻辑中符号化下述命题，并推证之。例 凡人必有一死，苏格拉底是人，所以苏格拉底会死的。解令 F(x): x 是人 , G(x): x 是要死的 , a: 苏格拉底前提 : x(F(x)G(x), F(a) 结论 : G(a) 证明 : F(a) 前提引入x(F(x)G(x) 前提引入
9、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)
10、G(x) 前提引入F(a) G(a) UI规则F(a) 拒取非洲人都不怕热，玛丽怕热。所以玛丽不是非洲人。凡奇数均不能被 2 整除， 8 能被 2 整除。所以 8不是奇数。凡奇数均不能被 2 整除， 36能被 2 整除。所以 36 不是奇数。英语系学生都不学离散数学，小刘学离散数学。因此，小刘不是英语系学生。海南人都不怕热，小赵怕热。所以小赵不是海南人。无理数都不能表示成分数，3.1415能表示成分数。所以3.1415不是无理数。例 鸟都会飞，麻雀是鸟，所以麻雀会飞。 例 乌鸦都不是白色的，北京鸭是白色的。因此，北京鸭不是乌鸦。解: 设F(x): x是乌鸦, G(x): x白色, a:北京鸭前
11、提 : x(F(x) G(x), G(a) 结论 : F(a) 证明 : G(a) 前提引入x(F(x) G(x) 前提引入F(a) G(a) UI规则F(a) 拒取第二篇 集合论第 3 章 集合计算例 设1, 2, 3,2, 3, 4, 5 ,2, 3 ,ABZ求 （ AB）Z. 1, 2, 3, 4, 5,1, 4, 5（ AB） =（ AB）Z=例 设 A=a,b,c,c,a,b，B=a,b,b，计算 (1)A B，(2)AB，(3)P(B) （ AB） =a,b（ AB） =a,b,c,c,bP(B)=,a,b,b,a,b,b集合恒等式的证明例 设 A、B、C是三个集合，证明： AB=
12、A(B-A) 例 设 A、B、C是三个集合，证明： A(BC)(AB)C 例 设 A、B、C是三个集合，证明： A(BC)(AB)(AC) 例 设 A、B、C是三个集合，证明： (AB)(AC)=A(BC) 例 设 A、B、C是任意三个集合，证明：(A(BC)A)(B(BA) A。 例 设 A、B、C 是任意三个集合，证明： (A(BC)A)(B(BA)A例 设 A，B，C为集合，证明： A(BC)=(AC)(BC) 例 已知 AB=A C，且AB=AC，证明 B=C 。包含排斥原理（即容斥原理）的简单应用例 假设某班有 20 名学生，其中有 10 人英语成绩为优，有8 人数学成绩为优，又知有
13、 6 人英语和数学成绩都为优。问两门课都不为优的学生有几名？解：A=英语成绩为优 ，B=数学成绩为优 。|A|=10,|B|=8,|AB|=68| AB| =| A| +| B| - | AB| =1220- | AB|例 有 100 名程序员，其中47 名熟悉 C+语言， 35 名熟悉 JAVA 语言， 23 名熟 悉这两种语言。问有多少人对两种语言都不熟悉？例 在一个班级的 50 名学生中，有 26 人在第一次考试中得到A，21 人在第二次考试中得到 A，假如有 17 人两次考试都没得到A，问有多少学生两次考试都得到 A？第 4 章 关系第 5 章 函数例 设集合 A=1,2,3,4,5，
14、A上的关系 R和 S为：R=|x+y=5,x,yA,S=|x， ，S=， R S=， 例 设 A=0,1,2,3 ，A 上的两个关系：R = (a,b)a=b+1或 a=b/2，S = (a,b)b=a+2 ，求(1)R S，(2) S R。R = (1,0)，(2,1)，(3,2)，(1,2) S = (0,2)，(1,3) (1)R S=(1,2)，(2,3) (2) S R= (0,1)，(1,2) 例 设 B=1,2,3,4，B上的关系 R 1,2 , 2,1 , 2,3 , 3,4 ，求(1)RR (2) R-1R 1,1 , 2,2, 2,4 R-1=2,1 , 1,2, 3,2 , 4,3 例 设 A=a,b,c,d，A上的关系 R,，求 (1)RR (2)R-1例 设集合 A2,4,6,8,10,12 ，B=2,4,6 ，从 A 到 B 的关系 R |x=2y ，求 R 和 R-1 例 设集合 A 1,2,3,4,5,6 ， B=1,2,3 ， 从 A到 B的关系 R x,y |x=2y ，求(1)R,(2)R-1例 设 R1=, , R2=, ，求 (1) R1-1，(2) R1R2 例 R1=, , R2=, , (1) 求 R1-1 (2) 求 R2R1(3) R1是函数吗？例 设
