离散数学复习要点.doc

《离散数学复习要点.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学复习2018.1.3第1章数学语言与证明方法知识点1：幂集的定义幂集的元素个数计算，如果A有n个元素，那么P（A）有2的n次方个元素例1的幂集P（）的元素个数为1，因为2的0次方为1.即{}。{}的幂集P（{}）元素个数为2，其幂集为{，{}}知识点2：集合的运算P8的公式，特别要注意下面的公式：A-B=A~B~~A=A~(AB)=~A~B~(AB)=~A~BAB=（A-B）(B-A)知识点3文氏图P7用文氏图表达集合运算第2章命题逻辑1成真赋值，成假赋值例1：求(pq)r的成假赋值若上式子成假，必须(pq)为1，r为0故成假赋值为110，10

2、0，0102可满足式，矛盾式，永真式的定义3合取范式，析取范式的定义4极大项，极小项的定义。例2求(pq)r的合取范式的极大项，析取范式的极小项解成假赋值为110，100，010，故此有三项极大项，(pq)rM2M4M6成真赋值为000，001，011，101，111，故此析取范式有五项极小项(pq)rm0m1m3m5m75联接词完备集{，，}是完备的，因为和都可以用前三个符号来表达例如pq（pq）（qp）（pq）pq{，}也是完备的因为pq((pq))(pq)但{，}就不是完备的6命题符号化和定理证明例如小王学过英语或者日语。如果小王学过英语，则他去

3、过英国，如果他去过英国，他也去过日本。所以小王学过日语或者去过日本。证明：1）p：小王去过英语；q：小王学过英语r:小王去过英国s：小王去过日本2）前提：pq，pr，rs结论：qs3）构造证明过程：1pr前提引入2rs前提引入3ps1，2假言三段伦4pq前提引入5pq4置换6qp5置换7qs6，3假言三段8qs7置换7归结法证明：例子：用归结法证明上述命题1）p：小王去过英语；q：小王学过英语r:小王去过英国s：小王去过日本2）前提：pq，pr，rs结论：qs用归结法改写为下述形式：前提：pq，pr，rs，q，s结论0证明：1rs前提引入2s前提引入3

4、r1，2归结4pr前提引入5p3，4归结6pq前提引入7q6，7归结8q前提引入907，8归结第3章一阶逻辑知识点1公式符号化例如所有的汽车比飞机慢例如有的汽车比有的飞机慢例如有的汽车比所有的飞机慢知识点2前束范式的定义，及转换例：将上述转换为前束范式P853.32第四章关系1笛卡尔积的定义例子：求{1，2，3}×{4，5}2二元关系的矩阵表示与图表示3关系的传递性，对称性，反对称性，自反性。（判断法则）4关系的交，并，关系的合成，关系的幂运算。5传递闭包，对称闭包，自反闭包，tsr闭包4等价关系，偏序关系与哈斯图，集合的划分例1{1，2，3}有多少种

5、划分{1,2,3,4}有多少种划分例2A={1，2，3，4，5，6，7，8，9，10}如果整除关系为偏序关系，画出哈斯图。并求{2，3}在该偏序关系的上界和下界第5章函数知识点1：函数，恒等函数，单射，满射，双射函数例子判断下列映射是否是函数，是否是双射函数例子

6、A

7、=m

8、B

9、=n,求A到B上函数的个数，A到B上双射函数的个数A到B上函数有n^m个，因为每个自变量都有n种选择。A到B的双射函数，如果当n不等于m时，为0.因为双射函数必须一一对应。如果m=n，则有n!知识点2函数的像，完全原像。知识点3函数的合成，的定义第6章图1握手定理2完全图Kn圈图

10、Cn，轮图Wn，各有多少顶点，多少边3生成子图的定义和性质。4初级通路和简单通路的定义，初级回路和简单回路的定义。例子：给定一个无向图，计算初级通路和简单通路的条数5平面图的定义，欧拉公式n-m+r=2，平面图的判断6染色问题，四色定理7欧拉图，欧拉通路，哈密尔顿图，哈密尔顿通路，欧拉图的判断，哈密尔顿图的判断。8二部图的定义，二部图的判断