离散数学期末复习
离散数学内容总结
第一篇 数理逻辑
第1章 命题逻辑
求命题公式的主析取范式及主合取范式
例 求()()p r q p ∨?∧∨的主析取范式及主合取范式。 例 求(P →Q)∧R 的主析取范式及主合取范式。
例 求命题公式R Q P ∨∧)(的主析取范式和主合取范式。 例 求公式A =(p →?q )→r 的主析取范式与主合取范式。 例 求()r q p →→的主析取范式。
判断公式类型
例 用等值演算法判断公式q ∧? (p →q )的类型
例 判断下列命题公式的类型（永真式、永假式、可满足式），方法不限。
(1)
(2)
证明
例 证明：()()()r q r p r q p →∧→?→∨ 例 证明：r q p r q p →∧?→→)()( 例 推证：?Q ∧(P →Q)??P
例 前提：q p s q r p ∨→→,,，结论：s r ∨。该结论是否有效？请说明原因。
在命题逻辑中构造下面推理的证明：
例 如果小张守第一垒并且小李向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:我备课
前提: (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) 换名规则
??x?y(F(x)→G(y)) 量词辖域扩张
例求公式?x F(x)∧??x G(x)的前束范式。
解：?x F(x)∧??x G(x)
??x F(x)∧?x?G(x) (*量词否定等值式??x P(x)??x?P(x)*)
??x (F(x)∧?G(x)) (*量词分配等值式?x (A(x)∧B(x))??x A(x)∧?x B(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(a)
证明:
① G(a) 前提引入
②?x(F(x) ?→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会飞，M(x)：x是麻雀，
前提：?x(F(x)→G(x))，?x(M(x)→ F(x))
结论：?x(M(x)→ G(x))
推演：
(1) ?x (F(x )→G(x )) 前提引入 (2) ?x (M(x )→ F(x )) 前提引入 (3) F(x )→G(x ) (1)UI (4) M(x )→F(x ) (2)UI
(5) M(x )→G(x ) (3)(4)假言三段论
(4) ?x (M(x )→ G(x )) (5)UG (注意：“麻雀”不是个体，而是类属，故不能令a ：麻雀)
例 乌鸦都不是白色的，北京鸭是白色的。因此，北京鸭不是乌鸦。
第二篇 集合论
第3章 集合
计算
例 设{}{}{}1,2,3,2,3,4,5,2,3,A B Z ===?⊕求（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)－(A ?C)= (A ?B) ?C A ?=(A ?B) ?（A ?C ）
=(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 )?(A ?C ) =A ? (B ?C )
=A ?C B ?= 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 。
证明：B=B?(A?A)=(B?A)?(B?A)
=(C?A)?(C?A)=C?(A?A)
=C
包含排斥原理（即容斥原理）的简单应用
例假设某班有20名学生，其中有10人英语成绩为优，有8人数学成绩为优，又知有6人英语和数学成绩都为优。问两门课都不为优的学生有几名？
例有100名程序员，其中47名熟悉C++语言，35名熟悉JA V A语言，23名熟悉这两种语言。问有多少人对两种语言都不熟悉？
例在一个班级的50名学生中，有26人在第一次考试中得到A，21人在第二次考试中得到A，假如有17人两次考试都没得到A，问有多少学生两次考试都得到A？
第4章关系
第5章函数
例设集合A={1,2,3,4,5}，A上的关系R和S为：
R={ 解：R={<1,4>,<2,3>,<3,2>,<4,1>} 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><3,3><3,4>,<3,5>,<4,2>,<4,3>,<4,4>,<4,5>} 例设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。 例设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＝{ (2)R-1 例设集合A＝{2,4,6,8,10,12}，B={2,4,6}，从A到B的关系R＝{ 求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={<1,2>,<2,2>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>}，求(1) R1-1，(2) R1 R2 例 R 1={<1,2>,<1,3>,<2,3>,<3,3>}, R 2={<2,2>,<2,3>,<3,4>}, (1) 求 R 1-1 (2) 求R 2 R 1 (3)R 1是函数吗？ 例 设A={a,b,c,d}，R={ R={><><>><<><><><> （2）求R 的自反闭包和对称闭包。 例 R 1={<1,2>,<1,3>,<2,3>,<3,3>}, R 2={<2,2>,<2,3>,<3,4>}, (1) 求 R 1-1 (2) 求R 2 R 1 (3)R 1是函数吗？ 例 设集合A={a,b,c,},B={b,c,d},C={d,e,f},R 1={<1,2>,<2,2>,<2,3>,<3,3>}, R 2={<2,2>,<2,3>,<3,4>}， 求(1)B A ?，(2)A ⊕B ，(3) R 1-1 ，(4) R 1 R 2 例 设A={a ，b ，c}，R 是A 幂集上的包含关系，说明R 是偏序关系并画出R 的哈斯图。 例 求集合A={1,2,3}的幂集，R 是A 幂集上的包含关系，说明R 是偏序关系并画出R 的哈斯图。 例 设S={1，2,…,10},≤ 是S 上的整除关系，画出 R={<0,0>,<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>}，试用关系图验证R 是A 上的等价关系。 例 A={1,2,3}，R 为A 上关系，关系矩阵为?? ?? ? ?????101011001， (1) 画出关系图。 (2) 求R R ，R -1。 (3) 求r(R)，s(R)，t(R)； (4) 指出R 具有的性质。 (5) R 是偏序关系吗？若是画出哈斯图。 第三篇 图论 连通性判断，通路数的计算 例 有向图G 如下图所示： (1)写出此图的邻接矩阵表示。（4分） (2)v1到v3长为3的通路有多少条？v1到自身长为3的回路有多少条？（4分） (3)G 中长为3的通路共有多少条？其中回路多少条？（4分） 例 具有四个节点的有向图G 如下图所示: (1) 写出此图的邻接矩阵 1 1 0 0 0 0 1 0 1 0 0 0 1 0 2 0 (2) G 是单向连通还是强连通？（单向连通）（3分） (3) 长为4的通路共有多少条?其中有多少条回路?（4分） A 4= 3 2 1 0 1 1 0 0 2 1 1 0 4 3 1 0 通路有20条，5条回路 例 已知有向图G 的邻接矩阵为 A=????? ???? ???0111 001111001010 （1）画出图并说出此图有几条边。 （2）v4到v2长为3的通路有多少条？v1到自身长为3的回路有多少条？ （3）此图是强连通还是单向连通图？ 例 G 是具有四个节点的有向图，它的邻接矩阵表示如下 ?????? ? ? ?00 1010101100 1010 画此图并说明该图共有几条边？ G 是单向连通还是强连通？ 分别求出从v4到v4长度小于4的回路条数及从v1到v2、 从v1到v3、 v1到v4长度是3的通路数。 例 已知有向图G 的邻接矩阵为 A=????? ???????0111 001111001010 （1）画出图G 并说出此图有几条边。 （2）v1到v3，v4到v2长为3的通路有多少条？v1到自身长为3的回路有多少条？ （3）此图是强连通还是单向连通图？ 哈密尔顿图的充分条件及其简单应用 例 一次会议有10人参加，其中每个人都在其中有不下6个朋友。这10人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？ 计算 例 已知无向图G 有12条边，1度顶点有2个，2度、3度、5度顶点各1个，其余顶点度数均为4，求4度顶点的个数。 例 一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，其余结点度数均为1，问它有几个度数为1的结点？ 例 已知无向树T 中，有1个3度顶点，2个2度顶点，其余顶点全是树叶。试求树叶数。 例 无向树T 有8片树叶，2个3度分支点，其余的分支点都是4度顶点，问T 有 几个4度分支点？ 求出下图的一棵最小生成树，并计算其权。 a 求最优二元树及其权 例求以1,3,4,5,6为权的最优2元树，要求写出步骤并计算它的权。 例(1) 求以2,3,5,7,8,9为权的最优2元树T，(2) 求) (T W， （3) 求T的高度) (T h，(4) 求T的树叶有多少？(5) 求T的2度顶点，3度顶点，4度顶点各有多少？ 例给定权1，4，9，16，25，36，49，64，81，100，构造一棵最优二叉树。 利用最有二元树进行编码 例设7个字母在通信中出现的频率如下： a: 35%，b: 20%，c: 15%，d: 10%，e: 10%，f: 5%，g: 5% 用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码。并指出传输10n(n≥2)个按上述频率出现的字母，需要多少个二进制数字。例在通信中,设八进制数字出现的频率(%)如下: 0: 25, 1: 20, 2: 15, 3: 10, 4: 10, 5: 10, 6: 5, 7: 5 采用2元前缀码,求传输数字最少的2元前缀码 (称作最佳前缀码),并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的(长为3)的码字传输需要多少个二进制数字?（要求画出最优2元树） 例设7个字母在通信中出现的频率如下： a: 35%，b: 20%，c: 15%，d: 10%，e: 10%，f: 5%，g: 5% 用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码。并指出传输10n(n≥2)个按上述频率出现的字母，需要多少个二进制数字。 第四篇代数系统 例设G为群，如果?a∈G，都有 a2= e, 证明：G为Abel群（即G为交换群）。例设B是任意集合，试验证 例R为实数集,在R上定义二元运算 :3 b a b a ，证明: R关于 R a ,+ ?b + , = ∈ 运算构成群。 例整数集Z上的二元运算*定义为：?a,b∈Z，a*b=a+b-2。试证： （1）?a,b,c∈Z，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4, a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=a+b+c-4， 故(a*b)*c=a*(b*c)，从而*满足结合律。 （2）记e=2。对?a∈Z，a*2=a+2-2=a=2+a-2=2*a.。故e=2是Z关于运算*的单位元。（3）对?a∈Z，因为a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a关于运算*的逆元。 综上所述， 例 + abc+ + +。 bc bc a c ab 华南农业大学期末考试试卷（A 卷） 2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分） 1、下面语句是简单命题的为_____。 A 、3不是偶数 B 、李平既聪明又用功 C 、李平学过英语或日语 D 、李平和张三是同学 2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。 A 、r q p →?∧? B 、r q p ?→∧? C 、r q p →?∧ D 、r q p ∧→ 3、下列谓词公式不是命题公式P →Q 的代换实例的是______。 A 、)()(y G x F → B 、),(),(y x yG y x xF ?→? C 、))()((x G x F x →? D 、)()(x G x xF →? 4、设个体域为整数集，下列公式中其值为 1的是_____。 A 、)0(=+??y x y x B 、)0(=+??y x x y C 、)0(=+??y x y x D 、)0(=+???y x y x 2 5、下列哪个表达式错误_____。 A 、 B x xA B x A x ∧??∧?)())(( B 、B x xA B x A x ∨??∨?)())(( C 、B x xA B x A x →??→?)())(( D 、)())((x xA B x A B x ?→?→? 6、下述结论错误的是____。 A 、存在这样的关系，它可以既满足对称性，又满足反对称性 B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C 、存在这样的关系，它可以既满足自反性，又满足反自反性 D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。 A 、自反性、对称性和传递性 B 、自反性、反对称性和传递性 C 、反自反性、对称性和传递性 D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。 A 、R 是自反的，则2R 一定是自反的 B 、R 是反自反的，则2R 一定是反自反的 C 、R 是对称的，则2R 一定是对称的 D 、R 是传递的，则2R 一定是传递 9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。 A 、11--R R B 、11--S R C 、11--S S D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。 A 、c b , B 、b a , C 、b D 、c b a ,, 11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A 、1，2，2，3，4，5 离散数学必备知识点总 结 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT 总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系； 离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( ) A.P→P∨Q B.(┐P∧Q)∧(P∨┐Q) C.┐ (P Q) D.(P∨Q) (P→Q) 3．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 4．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的 5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式 7．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群 19、代数系统是指由及其上的或 组成的系统。 20、设 第一章，0命题逻辑 素数 = 质数，合数有因子 和或假必真同为真 (p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。若公式A是单个的命题变项，则称A为0层合式 (┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式 【例】求下列公式的真值表，并求成真赋值和成假赋值。 (┐p∧q)→┐r 公式(1)的成假赋值为011，其余7个赋值都是成真赋值 第二章，命题逻辑等值演算 （1）双重否定律??A?A （2）等幂律 A∧A?A ； A∨A?A （3）交换律 A∧B?B∧A ； A∨B?B∨A （4）结合律（A∧B）∧C?A∧（B∧C）；（A∨B）∨C?A∨（B∨C） （5）分配律（A∧B）∨C?（A∨C）∧（B∨C）；（A∨B）∧C?（A∧C）∨（B∧C） （6）德·摩根律?（A∨B）??A∧?B ；?（A∧B）??A∨?B （7）吸收律 A∨（A∧B）?A；A∧（A∨B）?A （8）零一律 A∨1?1 ； A∧0?0 （9）同一律 A∨0?A ； A∧1?A （10）排中律 A∨?A?1 （11）矛盾律 A∧?A?0 （12）蕴涵等值式 A→B??A∨B （13）假言易位 A→B??B→?A （14）等价等值式 A?B?（A→B）∧（B→A） （15）等价否定等值式 A?B??A??B??B??A （16）归缪式（A→B）∧（A→?B）??A A i(i=1,2,…,s)为简单合取式，则A=A1∨A2∨…∨A s为析取范式 (p∧┐q)∨(┐q∧┐r)∨p A=A1∧A2∧…∧A s为合取范式 (p∨q∨r)∧(┐p∨┐q)∧r 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 主范式【∧小真，∨大假】 ∧成真小写 【例】(p→q)→(┐q→┐p) = ┐(┐p∨q)∨(q∨┐p) (消去→) = (p∧┐q)∨┐p∨q (┐内移) (已为析取范式) = (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) （*） = m2∨m0∨m1∨m1∨m3 = m0∨m1∨m2∨m3 (幂等律、排序) (*)由┐p及q派生的极小项的过程如下： ┐p = ┐p∧(┐q∨q) = (┐p∧┐q)∨(┐p∧q) q = (┐p∨p)∧q = (┐p∧q)∨(p∧q) 熟练之后，以上过程可不写在演算过程中。 该公式中含n=2个命题变项，它的主析取范式中含了22=4个极小项，故它为重言式， 00，01，10，11全为成真赋值。 【例】(p→q)∧┐p = (┐p∨q)∧┐p (消去→) = ┐p∨(┐p∧q) (分配律、幂等律) 已为析取范式 离散数学 一、逻辑和证明 1.1命题逻辑 命题：是一个可以判断真假的陈述句。 联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。 谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x>0P(x)。 当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定：??xP(x) ??x?P(x)，??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。 1.6推理规则 一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证 二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。 A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。 考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。 一对一或者单射：B可能有多余的元素，但不重复指向。 映上或者满射：B中没有多余的元素，但可能重复指向。 一一对应或者双射：符合上述两种情况的函数关系。 反函数：如果是一一对应的就有反函数，否则没有。 合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。 2.4序列 无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的，则A∪B也是可数的。 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={ 离散数学期末复习要点与重点 离散数学是中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的一门统设必修学位课程，共72学时，开设一学期．该课程的主要内容包括：集合论、图论、数理逻辑等． 下面按章给出复习要点与重点． 第1章 集合及其运算 复习要点 1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法． 具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.． 集合的表示方法：列举法和描述法. 注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分． 掌握集合包含(子集)、真子集、集合相等等概念． 注意：元素与集合，集合与子集，子集与幂集，∈与?(?),空集?与所有集合等的关系. 空集?，是惟一的，它是任何集合的子集． 集合A 的幂集P (A )＝}{A x x ?， A 的所有子集构成的集合．若∣A ∣＝n ，则∣P (A )∣=2n ． 2．熟练掌握集合A 和B 的并A ?B ，交A ?B ，补集~A (~A 补集总相对于一个全集).差集A －B ，对称差⊕，A ⊕B ＝(A －B )?(B －A )，或A ⊕B ＝(A ?B )－（A ?B ）等运算，并会用文氏图表示． 掌握集合运算律(见教材第9～11页)(运算的性质). 3．掌握用集合运算基本规律证明集合恒等式的方法． 集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明． 证明方法有二：(1)要证明A ＝B ，只需证明A ?B ，又A ?B ； (2)通过运算律进行等式推导． 重点：集合概念，集合的运算，集合恒等式的证明． 第2章 关系与函数 复习要点 1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算． 有序对就是有顺序二元组，如 离散数学笔记（特级教师精心整理） 第一章命题逻辑 内容： 命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法教学目的： 1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。 2．熟练掌握常用的基本等价式及其应用。 3．熟练掌握（主）析/合取范式的求法及其应用。 4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。 5．熟练掌握形式演绎的方法。 教学重点： 1．命题的概念及判断 2．联结词，命题的翻译 3．主析（合）取范式的求法 4．逻辑推理 教学难点： 1．主析（合）取范式的求法 2．逻辑推理 1.1命题及其表示法 1.1.1 命题的概念 数理逻辑将能够判断真假的陈述句称作命题。 1.1.2 命题的表示 命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。 1.2命题联结词 （1） P↑P?﹁（P∧P）?﹁P； （2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。 （1）P↓P?﹁（P∨Q）?﹁P； （2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q； （3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。 1.3 命题公式、翻译与解释 1.3.1 命题公式 定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P 是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、 P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。 例如，下面的符号串都是公式： （（（（﹁P）∧Q）→R）∨S） （（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R 以下符号串都不是公式： （（P∨Q）?（∧Q））（∧Q） 1.3.2 命题的翻译 可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。 命题翻译时应注意下列事项： （1）确定所给句子是否为命题。 （2）句子中联结词是否为命题联结词。 （3）要正确的选择原子命题和合适的命题联结词。 例：假如上午不下雨，我去看电影，否则就在家里读书或看报。 解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。 本例可表示为：（?P→Q）∧（P→（R∨S））。 1.3.3 命题公式的解释定义 设P1，P2，…，P n是出现在命题公式G中的全部命题变元，指定P1，P2，…，P n的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作T I（G）。 例如， 是G的一个解释，在这个解释下G的真值为1，即T I（G）=1。 1.4 真值表与等价公式 1.4.1 真值表 定义将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。 构造真值表的方法如下： （1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，…，P n。华南农业大学 离散数学 期末考试2013试卷及答案
离散数学必备知识点总结
离散数学复习要点
中国石油大学大学《离散数学》期末复习题及答案
离散数学重点笔记
离散数学知识点整理
大学离散数学期末重点知识点总结(考试专用)
离散数学期末复习要点与重点
离散数学笔记(特级教师精心整理)
- 离散数学期末试卷学习资料
- 山东大学离散数学期末试题答案
- 大学离散数学期末重点知识点总结(考试专用)
- 2012年北京语言大学离散数学期末考试A卷真题附答案
- 最新大学离散数学期末重点知识点总结(考试专用)
- 中国石油大学大学《离散数学》期末复习题及答案
- 南昌大学_离散数学_期末试卷(最新)
- 离散数学期末试卷A卷及答案
- 离散数学期末试卷A卷及答案
- 离散数学期末考试题答案
- 离散数学期末试卷
- 大学《离散数学》期末考试试卷及答案-(1)
- 中国石油大学大学《离散数学》期末复习题及答案
- 离散数学期末试卷A卷
- 中国石油大学大学《离散数学》期末复习题及答案
- 离散数学(1)期末考试
- 离散数学期末试卷A卷
- 北京理工大学数学专业离散数学期末试题
- 厦门大学离散数学2015-2016期末考试试题答案年
- 离散数学期末试卷