离散数学知识点总结
离散数学知识点总结 一、各章复习要求与重点
第一章 集 合
[复习知识点]
1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集
2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（V enn ）图
3、序偶与迪卡尔积
本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求]
1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。
2、掌握集合的表示法和集合的交、并、差、补等基本运算。
3、掌握集合运算基本规律，证明集合等式的方法。
4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 [本章重点习题]
P5~6，4、6； P14~15，3、6、7； P20，5、7。 [疑难解析] 1、集合的概念
因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。 2、集合恒等式的证明
通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 [例题分析]
例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。 解
}}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A
}}2,1{},2{},1{,{)(φρ=B
于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ
例2 设{}{}Φ=,,,,b a b a A ，试求：
(1){}b a A ,-； (2)Φ-A ； (3){}Φ-A ； (4){}{}A b a -,； (5)A -Φ； (6){}A -Φ。
解 (1){}{}{}Φ=-,,,b a b a A (2)A A =Φ- (3){}{}{}b a b a A ,,,=Φ- (4){}{}Φ=-A b a , (5)Φ=-ΦA (6){}Φ=-ΦA 例3 试证明()()()()B A B A B A B A ~~~~???=??? 证明
()()()()()()
()()()()()()
()()()()()()
B A B A B A B A B B B A A B A A B B A A B A B A B A ~~~~~~~~~~~~~???=Φ?????Φ=???????=?????=???
第二章 二元关系
[复习知识点]
1、关系、关系矩阵与关系图
2、复合关系与逆关系
3、关系的性质（自反性、对称性、反对称性、传递性）
4、关系的闭包（自反闭包、对称闭包、传递闭包）
5、等价关系与等价类
6、偏序关系与哈斯图（Hasse ）、极大/小元、最大/小元、上/下界、最小上界、最大下界
7、函数及其性质（单射、满射、双射）
8、复合函数与反函数
本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念 [复习要求]
1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。
2、掌握求复合关系与逆关系的方法。
3、理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、图）。
4、掌握求关系的闭包 （自反闭包、对称闭包、传递闭包）的方法。
5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/
小元、上/下界、最小上界、最大下界的求法。
6、理解函数概念：函数、函数相等、复合函数和反函数。
7、理解单射、满射、双射等概念，掌握其判别方法。 [本章重点习题]
P25，1；P32~33，4，8，10； P43，2，3，5； P51~52，5，6； P59，1，2； P64，3； P74~75，2，4，6，7； P81，5，7； P86，1，2。 [疑难解析] 1、关系的概念
关系的概念是第二章全章的基础，又是第一章集合概念的应用。因此，学生应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。 2、关系的性质及其判定
关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定，可以依据教材中P49上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法”，即若
()()()R a a R a a R a a i i ∈∈∈-,,
,
,,,13221 ，则()R a a i ∈,1。如若()()R a b R b a ∈∈,,,，则有
()R a a ∈,，且()R b b ∈,。
３、关系的闭包
在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论：定理2，
()A I R R r ?=；定理3， ()1
-?=R R R s ；定理4，推论 () n
i i R R t 1
==。
４、半序关系及半序集中特殊元素的确定
理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。 ５、映射的概念与映射种类的判定
映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。 [例题分析]
例1 设集合{}d c b a A ,,,=，判定下列关系，哪些是自反的，对称的，反对称的和传递的：
()(){}()()(){}(){}()()(){}
()(){}
d b c a R c c b b a a R d c R a d c b a a R a b a a R ,,,,,,,,,,,,,,,,,,54321=====解：均不是
自反的；R 4是对称的；R 1 ,R 2 ,R 3 , R 4 ,R 5是反对称的；R 1 ,R 2 ,R 3 , R 4 ,R 5是传递的。
例2 设集合{
}5,4,3,2,1=A ，A 上的二元关系R 为 ()()()()()()()(){}5,5,4,5,3,5,4,4,4,3,3,3,2,2,1,1=R （１）写出R 的关系矩阵，画出R 的关系图； （２）证明R 是A 上的半序关系，画出其哈斯图；
（３）若A B ?，且{}5,4,3,2=B ，求B 的最大元，最小元，极大元，极小元，最小上界和最大下界。 解 （1）R 的关系矩阵为
???
??
?
?
?
??=111000100001100
00010
00001
R M R 的关系图略
（2）因为R 是自反的，反对称的和传递的，所以R 是A 上的半序关系。(A,R)为半序集， (A,R)的哈斯图如下
(3) 当{}5,4,3,2=B ，B 的极大元为2，4；极小元为2，5；B 无最大元与最小元；B 也无上界与下界，更无最小上界与最大下界。
第三章 命题逻辑
[复习知识点]
１、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题
２、命题公式与解释，真值表，公式分类（恒真、恒假、可满足），公式的等价 ３、析取范式、合取范式，极小（大）项，主析取范式、主合取范式
。4 。1
。3 。2
。5
４、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法） ５、公式的蕴涵与逻辑结果 ６、形式演绎
本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、形式演绎 [复习要求]
１、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。
２、理解公式与解释的概念；掌握求给定公式真值表的方法，用基本等价式化简其他公式，公式在解释下的真值。
３、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等价式或真值表将公式化为主析取（合取）范式的方法。
４、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价的方法。 ５、理解公式蕴涵与逻辑结果的概念，掌握基本蕴涵式。 6、掌握形式演绎的证明方法。 [本章重点习题]
P93，1； P98，2，3； P104，2，3； P107，1，3； P112，5； P115，1，2，3。 [疑难解析]
1、公式恒真性的判定
判定公式的恒真性，包括判定公式是恒真的或是恒假的。具体方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为0），就可以判定该公式是否恒真（或恒假），若不全为0，则为可满足的。二是推导法，即利用基本等价式推导出结果为1，或者利用恒真（恒假）判定定理：公式G 是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定。
这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范式也同样。 2、范式
求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前一步适当使用等幂律，使相同的短语（或子句）只保留一个。
另外，由已经得到的主析取（合取）范式，根据()G G G G =??=?∨,1原理，参阅《离散数学学习指
导书》P71例15，可以求得主合取（析取）范式。 3、形式演绎法
掌握形式演绎进行逻辑推理时，一是要理解并掌握14个基本蕴涵式，二是会使用三个规则：规则P 、规则Q 和规则D ，需要进行一定的练习。 [例题分析]
例1 求()()P R Q P G →?∨∧=的主析取范式与主合取范式。 解 （1）求主析取范式， 方法1：利用真值表求解
因此
()()()()()()
R Q P R Q P R Q P R Q P R Q P R Q P G ∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧∧?∨∧?∧?= 方法2：推导法
()()()()()()()()()()()()()()
()()()
()()()()()()()()()()()()()()
R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R Q P R R Q Q P P P R Q Q Q R P P R Q R P P R Q P P
R Q P P R R Q P G ?∧?∧∨?∧∧∨∧∧∨∧?∧∨∧?∧?∨∧∧?=?∧?∧∨∧?∧∨?∧∧∨∧∧∨∧?∧?∨∧?∧∨∧?∧?∨∧∧?=?∨∧?∨∧∨?∨∧∧?∨∨?∧∧?=∨∧?∨∧?=∨∧?∨?=∨?∨∧?=→?∨∧=
（2）求主合取范式 方法1：利用上面的真值表
()()P R Q P →?∨∧为0的有两行，它们对应的极大项分别为R Q P R Q P ∨?∨∨∨,
因此，()()()()R Q P R Q P P R Q P ∨?∨∧∨∨=→?∨∧ 方法2：利用已求出的主析取范式求主合取范式
已用去6个极小项，尚有2个极小项，即 R Q P ?∧?∧?与R Q P ?∧∧? 于是
()()
()()()()()()
R Q P R Q P R Q P R Q P G G R Q P R Q P G ∨?∨∧∨∨=?∧∧?∨?∧?∧??=??=?∧∧?∨?∧?∧?=? 例2 试证明公式()()()()R P R Q Q P G →→→∧→=为恒真公式。 证法一： 见〈离散数学学习指导书〉P60例6（4）的解答。（真值表法） 证法二 ：
G=?（（?P ∨Q ）∧（?Q ∨R ））∨（?P ∨R ） =（P ∧?Q ）∨（Q ∧?R ）∨?P ∨R
=（（（P ∨Q ）∧（P ∨?R ）∧（?Q ∨Q ）∧（?Q ∨?R ））∨?P ）∨R =（（P ∨Q ∨?P ）∧（P ∨?R ∨?P ）∧（?Q ∨?R ∨?P ））∨R =（1∧（?Q ∨?R ∨?P ））∨R =?Q ∨?R ∨?P ∨R =1
故G 为恒真公式。
例3 利用形式演绎法证明 { P →（Q →R ），?S ∨P ，Q}蕴涵S →R 。 证明：
（1）?S ∨P 规则P （2）S 规则D
（3）P 规则Q ，根据（1），（2） （4）P →（Q →R ） 规则P
（5）Q →R 规则Q ，根据（3），（4） （6）Q 规则P
（7）R 规则 Q ，根据（5），（6） （8）S →R 规则D ，根据（2），（7）
第四章 谓词逻辑
[复习知识点]
1、谓词、量词、个体词、个体域、变元（约束变元与自由变元）
2、谓词公式与解释，谓词公式的类型（恒真、恒假、可满足）
3、谓词公式的等价和蕴涵
4、前束范式
本章重点内容：谓词与量词、公式与解释、前束范式 [复习要求]
1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。
2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。
3、理解用解释的方法证明等价式和蕴涵式。
4、掌握求公式前束范式的方法。 [本章重点习题]
P120，1，2； P125~126，1，3； P137，1。 [疑难解析] 1、谓词与量词
反复理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则。 2、公式与解释
能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释I 中的数值代入公式，求出真值。 3、前束范式
在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式（一阶逻辑中），将给定公式中量词提到母式之前称为首标。 [典型例题]
例1 设I 是如下一个解释：{}3,2=D
F(2) F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(3,3) 3 2 0 1 1 1 0 1 求()()()()y ,x F Q x P y x ∧??的真值。 解
()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()()()()()()()()()1
10111110003,3F Q 3P 2,3F Q 3P 3,2F Q 2P 2,2F Q 2P 3,x F Q x P 2,x F Q x P x y ,x F Q x P y x =∨=∧∧∧∨∧∧∧=∧∧∧∨∧∧∧=∧∧∧?=∧??
例2 试将一阶逻辑公式化成前束范式。 解
()()()()()()()()()()()()()()()()()()
x R z Q y x P z y x x R z Q z y x yP x x R y Q y y x yP x x R y yQ y x yP x G ∨?∨???=∨??∨??=∨??∨??=∨??∨??=,,,,
第五章 图论
[复习知识点]
1、图、完全图、子图、母图、支撑子图、图的同构
2、关联矩阵、相邻矩阵
3、权图、路、最短路径，迪克斯特拉算法（Dijkstra ）
4、树、支撑树、二叉树
5、权图中的最小树，克鲁斯卡尔算法（Kruskal ）
6、有向图、有向树
本章重点内容： 权图的最短路、二叉树的遍历、权图中的最优支撑树 [复习要求]
1、理解图的有关概念：图、完全图、子图、母图、支撑子图、图的同构。
2、掌握图的矩阵表示（关联矩阵、相邻矩阵）。
3、理解权图、路的概念，掌握用Dijkstra 算法求权图中最短路的方法。
4、理解树、二叉树与支撑树的有关概念；掌握二叉树的三种遍历方法，用Kruskal 算法求权图中最小树的方法。
5、理解有向图与有向树的概念。 [本章重点习题]
P221，2；P225，1；P231，2，3；P239，5；P242，1，2。 [疑难解析]
1.本章的概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图、权图；树、支撑树、二叉树、有向树；路、简单路、回路等，这些都是图的基本概念，今后将在数据结构、数据库、计算机网
络等课程中用到。
2、权图中的最短路
严格执行迪克斯特拉（Dijkstra）算法步骤，从起点起，到每一点求出最短路，然后进行仔细比较，最后到达终点，算出最小权和。
3、权图中的最优支撑树
权图中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔（Kruskal）算法。
[典型例题]
例1在具有n个顶点的完全图K n中删去多少条边才能得到树？
解：n个顶点的完全图K n中共有n?（n-1）/2条边，
n个顶点的树应有n-1条边，
于是，删去的边有：n?（n-1）/2-（n-1）=（n-1）?（n-2）/2
例2求下面有限图中点u到各点间的最短路。（图上数字见教材P231，第3题。）
解u→u1 ，d(u, u1)=1, 路(u, u1)
u→ u2 , d(u, u2)=9, 路(u, u4, u3, u7, u2)
u→ u3 , d(u, u3)=5, 路(u, u4, u3 ,)
u→ u4 , d(u, u4)=3, 路(u, u4 )
u→ u5 , d(u, u5)=11, 路(u, u1, u5)或路(u, u4, u3 , u7 , u2 , u5)
u→ u6 , d(u, u6)=13, 路(u, u1, u5, u6)
u→ u7 , d(u, u7)=8, 路(u, u4 , u3 , u7)
u→ u8 , d(u, u8)=11, 路(u, u4, u8)
u→v, d(u, v)=15, 路(u, u1, u5 , u6 ,v) 或路(u, u4 , u3 , u7 , u6 ,v)
二、考核说明
本课程的考核实行形成性考核和终结性考核的形式。形成性考核占总成绩的20%，以课程作业的形式进行（共三次，由中央电大统一布置）；终结性考核即期末考试，占总成绩的80%。总成绩为100分，60分及
格。
期末考试实行全国统一闭卷考核，试卷满分为100。由中央电大统一命题，统一评分标准，统一考试时间（考试时间为120分钟）。
1、试题类型
试题类型有填空题（分数约占20%）、单项选择题（分数约占14%）、计算题（分数约占50%）和证明题（分数约占16%）。
填空题和单项选择题主要涉及基本概念、基本理论，重要性质和结论、公式及其简单计算。计算题主要考核学生的基本运算技能，要求书写计算、推论过程或理由。证明题主要考查应用概念、性质、定理及主要结论进行逻辑推理的能力，要求写出推理过程。
2、考核试卷题量分配
试卷题量在各部分的分配是：集合论约占40%，数理逻辑约占40%，图论约占20%。
具体课程考核情况见课程考核说明。
附录：试题类型及规范解答举例
[填空题]
1.设R 是集合A上的二元关系，如果关系R同时具有性、对称性和性，则称R是等价关
系。
2.命题公式G=（P∧Q）→R，则G共有个不同的解释；把G在其所有解释下所取真值列成
一个表，称为G的；解释（?P，Q，?R）或（0，1，0）使G的真值为。
3.设G=（P，L）是图，如果G是连通的，并且，则G是树。如果根树T的每个点v最多
有两棵子树，则称T为。
[单项选择题]（选择一个正确答案的代号，填入括号中）
1.由集合运算定义，下列各式正确的有（）。
A．X?X?Y B.X?X?Y C.X?X?Y D.Y?X?Y
2.设R1，R2是集合A={a，b，c，d}上的两个关系，其中R1={（a，a），（b，b），（b，c），（d，d）}，
R2={（a，a），（b，b），（b，c），（c，b），（d，d）}，则R2是R1的（）闭包。
A．自反B．对称C．传递D．以上都不是
3.设G是由5个顶点组成的完全图，则从G中删去（）条边可以得到树。
A．4 B．5 C．6 D．10
[计算题]
1.化简下式：
（A -B -C ）?（（A -B ）?C ）?（A ?B -C ）?（A ?B ?C ） 2. 通过求主析取范式判断下列命题公式是否等值。 （1）（P ∧Q ）∨（?P ∧Q ∧R ）；
（2）（P ∨（Q ∧R ））∧（Q ∨（?P ∧R ））；
3. 求图中A 到其余各顶点的最短路径，并写出它们的权。
[证明题]
1. 利用基本等价式证明下面命题公式为恒真公式。 （（P →Q ）∧（Q →R ））→（P →R ）
2. 用形式演绎法证明：{P →Q ， R →S ，P ∨R }蕴涵Q ∨S 。 试题答案及评分标准 [填空题] 1、自反；传递 2、8；真值表；1 3、无回路；二叉树
[单项选择题]（选择一个正确答案的代号，填入括号中） 1、 A 2、 B 3、C [计算题] 1. 解：
（A -B -C ）?（（A -B ）?C ）?（A ?B -C ）?（A ?B ?C ） =（A ?~B ?~C ）?（A ?~B ?C ）?（A ?B ?~C ）?（A ?B ?C ） =（（A ?~B ）?（~C ?C ））?（（A ?B ）?（~C ?C ）） =（（A ?~B ）?E ）?（（A ?B ）?E ） E 为全集 =（A ?~B ）?（A ?B ）
B 7 C
A D
E 1 F
= A?（~B?B）
= A?E
= A
2.解：
（P∧Q）∨（?P∧Q∧R）
?（P∧Q∧（?R∨R））∨（?P∧Q∧R）
?（P∧Q∧?R）∨（P∧Q∧R）∨（?P∧Q∧R）
?m6∨m7∨m3
?m3∨m6∨m7
（P∨（Q∧R））∧（Q∨（?P∧R））
?（P∧Q）∨（Q∧R）∨（P∧?P∧R）∨（?P∧ Q ∧R）（分配律）?（P∧Q∧（?R∨R））∨（（?P∨P）∧Q∧R）∨（?P∧ Q ∧R）
?（P∧Q∧?R）∨（P∧Q∧R）∨（?P∧Q∧R）∨（P∧Q∧R）∨（?P∧ Q ∧R）
?m6∨m7∨m3∨m7∨m3
?m3∨m6∨m7
由此可见（P∧Q）∨（?P∧Q∧R）?（P∨（Q∧R））∧（Q∨（?P∧R））
3.解：
A到B的最短路径为AB，权为1；
A到E的最短路径为ABE，权为3；
A到F的最短路径为ABEF，权为4；
A到C的最短路径为ABEFC，权为7；
A到D的最短路径为ABEFCD，权为9。
[证明题]
1.证明：
（（P→Q）∧（Q→R））→（P→R）
?（（?P∨Q）∧（?Q∨R））→（?P∨R）
??（（?P∨Q）∧（?Q∨R））∨（?P∨R）
?（P∧?Q）∨（Q∧?R）∨?P∨R
?（（P∧?Q）∨?P ）∨（（Q∧?R）∨R）
?（1∧（?Q∨?P ））∨（（Q∨R）∧1）
??Q∨?P∨Q∨R
? （?Q ∨Q ） ∨?P ∨R ? 1 ∨?P ∨R
? 1 2. 证明：
（1） P ∨R 规则P （2） ?R →P 规则Q ，根据（1） （3） P →Q 规则P （4） ?R →Q 规则Q ，根据（2）（3） （5） ?Q →R 规则Q ，根据（4） （6） R →S 规则P （7） ?Q →S 规则Q ，根据（5）（6） （8） Q ∨S 规则Q ，根据（7）
三、 综合练习及解答
（一）填空题
1、集合的表示方法有两种： 法和 法。请把“大于3而小于或等于7的整数集合”用任一种集合的表示方法表示出来A={ }。
2、 A ，B 是两个集合，A={1，2，3，4}，B={2，3，5}，则B-A= ，ρ（B ）-ρ（A ）
= ，ρ（B ）的元素个数为 。 3、 设，则从A 到B 的所有映射是
。 4、 设命题公式)(R Q P G →?→=，则使公式G 为假的解释是 、 和 。
5、设G 是完全二叉树，G 有15个点，其中8个叶结点，则G 的总度数为 ，分枝点数为 。
6、全集E={1，2，3，4，5}，A={1，5}，B={1，2，3，4}，C={2，5}， 求A ?~B= ，ρ（A ）?ρ（C ）= ， ~C= 。
7、设A 和B 是任意两个集合，若序偶的第一个元素是A 的一个元素，第二个元素是B 的一个元素，则所有这样的序偶集合称为集合A 和B 的 ，
}2,1{},
,{==B b a A
记作A ?B ，即A ?B= 。A ?B 的子集R 称为A ，B 上的 。
8、将几个命题联结起来，形成一个复合命题的逻辑联结词主要有否定、 、 、 和等值。
9、表达式?x ?yL （x ，y ）中谓词的定义域是{a ，b ，c}，将其中的量词消除，写成与之等价的命题公式为 。
10、一个无向图表示为G=（P ，L ），其中P 是 的集合，L 是 的集合，并且要求 。
（二）单项选择题（选择一个正确答案的代号，填入括号中） 1. 设命题公式))(()(P R Q P P G ∨∧→?∨=，则G 是（ ）。 A.恒真的 B.恒假的 C.可满足的 D.析取范式
2、设集合},,{c b a A =，A 上的关系)},(),,(),,{(c b b a a a R =，则2R =（ ）。
)}.
,(),,(),,{()()};,(),,(),,{()()};
,(),,(),,{()()};,(),,(),,{()(c c b a a a D b b c a b a C c b c a b a B c a b a a a A
3、一个公式在等价意义下，下面哪个写法是唯一的（ ）。
A ．析取范式
B ．合取范式
C ．主析取范式
D ．以上答案都不对 4、设命题公式G=?（P →Q ），H=P →（Q →?P ），则G 与H 的关系是（ ）。 A ．G ?H B ．H ?G C ．G=H D ．以上都不是
5、已知图G 的相邻矩阵为???
??
?
?
?
??011111010111000
10001
11010
，则G 有（ ）
。 A.5点，8边 B. 6点，7边 C. 5点，7边 D. 6点，8边 6、下列命题正确的是（ ）。
A ．φ?{φ}=φ
B ．φ?{φ}=φ
C ．{a}∈{a ，b ，c}
D ．φ∈{a ，b ，c}
7、设集合A={a ，b ，c}，A 上的关系R={（a ，b ），（a ，c ），（b ，a ），（b ，c ），（c ，a ），（c ，b ），（c ，c ）}，则R 具有关系的（ ）性质。
A ．自反
B ．对称
C ．传递
D ．反对称 8、设R 为实数集，映射σ=R →R ，σ（x ）= -x 2+2x-1，则σ是（ ）。
A ．单射而非满射
B ．满射而非单射
C ．双射
D ．既不是单射，也不是满射 9、下列语句中，（ ）是命题。
A ．下午有会吗？
B ．这朵花多好看呀！
C ．2是常数。
D ．请把门关上。 10、下面给出的一阶逻辑等价式中，（ ）是错的。
A ． ?x （A （x ）∨
B （x ））=?xA （x ）∨?xB （x ） B ． A →?xB （x ）=?x （A →B （x ））
C ． ?x （A （x ）∨B （x ））=?xA （x ）∨?xB （x ）
D ． ??xA （x ）=?x （?A （x ）） （三）计算题
1、设R 和S 是集合}4,3,2,1{=A 上的关系，其中)}
4,4(),4,2(),3,2(),2,1{()}4,3(),3,2(),3,1(),1,1{(==S R ，试求： （1）写出R
和S 的关系矩阵； （2）计算111,,,
---???R S R S R S R 。
2、 设A={a ，b ，c ，d}，R 1，R 2是A 上的关系，其中R 1={（a ，a ），（a ，b ），（b ，a ），（b ，b ），（c ，c ），
（c ，d ），（d ，c ），（d ，d ）}，R 2={（a ，b ），（b ，a ），（a ，c ），（c ，a ），（b ，c ），（c ，b ），（a ，a ），（b ，b ），（c ，c ）}。
（1）画出R 1和R 2的关系图；
（2）判断它们是否为等价关系，是等价关系的求A 中各元素的等价类。 3、 用真值表判断下列公式是恒真？恒假？可满足？ （1）（P ∧?P ）?Q （2）?（P →Q ）∧Q
（3）（（P →Q ）∧（Q →R ））→（P →R ） 4、 设解释I 为：
（1）定义域D={-2，3，6}； （2）F （x ）：x ≤3； G （x ）：x >5。
在解释I 下求公式?x （F （x ）∨G （x ））的真值。
5、 求下图所示权图中从u 到v 的最短路，画出最短路并计算它们的权值。
6、 化简下式：
（（A ?B ?C ）?（A ?B ））-（（A ?（B -C ））?A ）
7、 已知A={1，2，3，4，5}，B={1，2，3}，R 是A 到B 的二元关系，并且R={（x ，y ）|x ∈A 且y ∈B
且2≤ x+y ≤4}，画出R 的关系图，并写出关系矩阵。
8、 画出下面偏序集（A ，≤）的哈斯图，并指出集合A 的最小元、最大元、极大元和极小元。其中A={a ，
b ，
c ，
d ，e}，≤={（a ，b ），（a ，c ），（a ，d ），（a ，
e ），（b ，e ），（c ，e ），（d ，e ）}?I A 。 9、 求命题公式?（P ∨Q ）?（P ∧Q ）的析取范式与合取范式。 10、给定解释I 如下： 定义域D={2，3}；
f （2） f （3） F （2，2） F （2，3） F （3，2） F （3，3） 3 2 0 0 1 1 求?x ?y （F （x ，y ）→F （f （x ），f （y ）））。
11、设有5个城市v 1，v 2，v 3，v 4，v 5，任意两城市之间铁路造价如下：（以百万元为单位）
w （v 1，v 2）=4， w （v 1，v 3）=7， w （v 1，v 4）=16， w （v 1，v 5）=10， w （v 2，v 3）=13， w （v 2，v 4）=8， w （v 2，v 5）=17， w （v 3，v 4）=3， w （v 3，v 5，）=10， w （v 4，v 5）=12 试求出连接5个城市的且造价最低的铁路网。 （四）证明题
1、证明等价式R R P R Q R Q P =∧∨∧∨∧?∧?)()())((。
2、 利用形式演绎法证明：蕴涵Q 。
3、 A ，B ，C 为任意的集合，证明： （A -B ）-C=A -（B ?C ）
4、 利用一阶逻辑的基本等价式，证明： ?x ?y （F （x ）→G （y ））=?xF （x ）→?yG （y ）
},,,,{T R S T S R P Q P ?→?→?→∨ V 1 7 V 3
1
2
U 2 5 3 V
4
6
V 2 1 V 4
练习解答
（一）填空题
1、列举；描述；A={4，5，6，7}或A={x|3 2、{5}；{{5}，{2，5}，{3，5}，{2，3，5}}；8 3、σ1={（a ，1），（b ，1）}；σ2={（a ，2），（b ，2）}；σ3={（a ，1），（b ，2）}；σ4={（a ，2），（b ，1）} 4、（1，0，1）； （1，1，1）； （1，0，0） 5、 28； 7 6、{5}；{φ，{5}}；{1，3，4} 7、笛卡尔积（或直乘积）；{（x ，y ）|x ∈A 且y ∈B}；二元关系 8、并且（或合取）；或者（或析取）；蕴涵 9、（L （a ，a ）∨L （a ，b ）∨L （a ，c ））∧（L （b ，a ）∨L （b ，b ）∨L （b ，c ））∧（L （c ，a ）∨L （c ，b ）∨L （c ，c ）） 10、点；连接某些不同点对的边；一对不同点之间最多有一条边 （二）单项选择题（选择一个正确答案的代号，填入括号中） 1、C 2、A 3、C 4、A 5、C 6、A 7、B 8、D 9、C 10、A （三）计算题 1、解：（1） ? ? ??? ???? ???=? ? ??????? ???=1000000011000010,0000100001000101 S R M M （2）S R ?={（1，2），（3，4）} S R ?={（1，1），（1，2），（1，3），（2，3），（2，4）， （3，4），（4，4）} 1 -R ={（1，1），（3，1），（3，2），（4，3）} 11 --?R S ={（2，1），（4，3）} 2、解： R 1和R 2的关系图略。 由关系图可知，R 1是等价关系。R 1不同的等价类有两个，即{a ，b}和{c ，d}。 由于R2不是自反的，所以R2不是等价关系。 3、解： （1）真值表 因此公式（1）为可满足。 （2）真值表 因此公式（2）为恒假。 （3）真值表 因此公式（3）为恒真。 4.解： ?x（F（x）∨G（x）） ?（F（-2）∨G（-2））∨（F（3）∨G（3））∨（F（6）∨G（6）） ?（1∨0）∨（1∨0）∨（0∨1） ? 1 5.解： 从U到V的最短路为U→V1→V2→V4→V3→V。最短路权值为9。 图中圆圈中的数字为使用迪克斯特拉算法添加边的次序。 6、解： （（A?B?C）?（A?B））-（（A?（B-C））?A） =（A?B）- A （利用两次吸收律） =（A?B）?~ A =（A?~ A）?（B?~ A） = φ?（B?~ A） = B- A 7、解： R={（1，1），（1，2），（1，3），（2，1），（2，2），（3，1）} R的关系图为 关系矩阵M R= 1 1 1 1 1 0 1 2 2 3 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.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 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的基数为mn，A到B上可以定义m n 2种不同的关系； 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 离散数学复习要点第一章命题逻辑 一、典型考查点 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．无 8．设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也是可数的。 第二章谓词逻辑 2—1基本概念 例题1. 所有的自然数都是整数。 设N(x):x是自然数。I(x):x是整数。此命题可以写成?x(N(x)→I(x)) 例题2. 有些自然数是偶数。 设E(x):x是偶数。此命题可以写成?x(N(x)∧E(x)) 例题3. 每个人都有一个生母。 设P(x):x是个人。M(x,y):y是x的生母。此命题可以写 成:?x(P(x)→?y(P(y)∧M(x,y))) 2-2 谓词公式及命题符号化 例题1. 如果x是奇数,则2x是偶数。 其中客体x与客体2x之间就有函数关系,可以设客体函数g(x)=2x, 谓词O(x):x是奇数,E(x):x是偶数, 则此命题可以表示为:?x(O(x)→E(g(x))) 例题2 小王的父亲是个医生。 设函数f(x)=x的父亲,谓词D(x):x是个医生,a:小王,此命题可以表示为D(f(a))。 例题3 如果x和y都是奇数,则x+y是偶数。 设h(x,y)=x+y ,此命题可以表示为:?x?y((O(x)∧O(y))→E(h(x,y)) 命题的符号表达式与论域有关系 两个公式:一般地,设论域为{a1,a2,....,an},则有 (1). ?xA(x)?A(a1)∧A(a2)∧......∧A(an) (2). ?xB(x)?B(a1)∨B(a2)∨......∨B(an) 1.每个自然数都是整数。该命题的真值是真的。 表达式?x(N(x)→I(x))在全总个体域的真值是真的, 因?x(N(x)→I(x))?(N(a1)→I(a1))∧(N(a2)→I(a2))∧…∧(N(an)→I(an)) 式中的x不论用自然数客体代入,还是用非自然数客体代入均为真。例如(N(0.1)→I(0.1))也为真。 而?x(N(x)∧I(x))在全总个体域却不是永真式。 数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n≥2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x≥y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词?: 表示任意的, 所有的, 一切的等 如?x 表示对个体域中所有的x 存在量词?: 表示存在, 有的, 至少有一个等 如?x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a) 例2 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解：(a) (1) 设G(x)：x爱美, 符号化为?x G(x) (2) 设G(x)：x用左手写字, 符号化为?x G(x) (b) 设F(x)：x为人，G(x)：同(a)中 集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y，按照一定的顺序组成的 二元组称为有序对，记作 不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集，则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取 数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令p：是有理数，则p 的真值为 0 q：2 + 5 = 7，则q 的真值为 1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题，复合命题“非p”（或“p的否定”）称 为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学，t 是简单命题 . 说明: 离散数学部分概念和公式总结 命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。 命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。 命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。 （2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。 （3）若A至少存在一组赋值是成真赋值，则A是可满足式。 主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。 主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。 命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B是等值的，记作A<=>B。 约束变元和自由变元：在合式公式?x A和?x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。 前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。集合的基本运算：并、交、差、相对补和对称差运算。 笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。 二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。特殊关系：（1）、空关系：Φ（2）全域关系：EA={ 离散数学笔记 第一章命题逻辑 合取 析取 定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句 定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句 定义 1.2.1合式公式 (1)单个命题变元、命题常元为合式公式，称为原子公式。 (2)若某个字符串A 是合式公式，则?A、(A)也是合式公式。 (3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A?B 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 1.3等值式 1.4析取范式与合取范式 将一个普通公式转换为范式的基本步骤 1.6推理 定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。（用等值演算或真值表） 第二章 谓词逻辑 2.1、基本概念 ?：全称量词 ?：存在量词 一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"?x(H(x)→B(x))，即量词的后面为条件式，带“存在量词”的谓词公式形如?x(H(x)∨WL(x))，即量词的后面为合取式 例题 R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快表示为： ?x ?y(R(x)∧T(y)→H(x,y)) 有的兔子比所有的乌龟跑得快表示为：?x ?y(R(x)∧T(y)→H(x,y)) 2.2、谓词公式及其解释 定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22 y x 的 f(x,y))、 谓词常元(如表示人 类的 H(x))。 定义 2.2.2、逻辑符号：个体变元、量词(??)、联结词(﹁∨∧→?)、逗号、括号。 定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。 定义 2.2.4、原子公式：设 R(n x x ... 1)是 n 元谓词，n t t ...1是项，则 R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。 定义 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，则(﹁A)也是合式公式；(3)若 A,B 合式，则 A ∨B, A ∧B, A →B , A ?B 合式(4)若 A 合式，则?xA 、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。 定义 2.2.6 量词辖域：?xA 和?xA 中的量词?x/?x 的作用范围，A 就是作用范围。 定义 2.2.7 约束变元：在?x 和?x 的辖域 A 中出现的个体变元 x ，称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。 定义 2.2.8 自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。 注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。 定义 2.2.9 闭公式是指不含自由变元的谓词公式 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={离散数学必备知识点总结
离散数学必备知识点总结
离散数学复习要点
离散数学知识点整理
离散数学谓词逻辑课后总结
离散数学第二章一阶逻辑知识点总结
离散数学第四章二元关系和函数知识点总结
离散数学第一章命题逻辑知识点总结
离散数学部分概念和公式总结
(完整word版)离散数学知识汇总,推荐文档
大学离散数学期末重点知识点总结(考试专用)