离散数学复习要点.doc

离散数学复习 2018.1.3第1章 数学语言与证明方法知识点1：幂集的定义幂集的元素个数计算，如果A有n个元素，那么P（A）有2的n次方个元素例1的幂集 P（）的元素个数 为1，因为2的0次方为1.即 。的幂集P（）元素个数为2，其幂集为，知识点2： 集合的运算P8的公式，特别要注意下面的公式：A-B=ABA=A(AB)= AB(AB) = ABAB=（A - B）(B - A)知识点3 文氏图P7 用文氏图表达集合运算第2章 命题逻辑1 成真赋值，成假赋值例1：求 (pq)r的成假赋值若上式子成假，必须(pq)为1，r为0故成假赋值为 110 ，100，0102可满足式，矛盾式，永真式的定义3 合取范式，析取范式的定义4 极大项，极小项的定义。例2 求(pq)r的合取范式的极大项，析取范式的极小项解 成假赋值为110，100，010，故此有三项极大项，(pq)r M2M4M6 成真赋值为000，001，011，101，111，故此析取范式有五项极小项 (pq)rm0m1m3m5m75 联接词完备集 ，是完备的，因为 和 都可以用前三个符号来表达例如 pq（pq）（q p） （pq） pq ，也是完备的因为pq (pq) (pq)但， 就不是完备的6 命题符号化和定理证明 例如 小王学过英语或者日语。如果小王学过英语，则他去过英国，如果他去过英国，他也去过日本。所以小王学过日语或者去过日本。证明： 1）p：小王去过英语； q：小王学过英语r : 小王去过英国 s：小王去过日本2）前提： pq，pr，rs结论 ：qs3）构造证明过程： 1 pr 前提引入 2 rs 前提引入 3 ps 1，2假言三段伦4 pq 前提引入 5 pq 4置换 6 qp 5置换 7 qs 6，3假言三段 8 qs 7置换7 归结法证明：例子：用归结法证明上述命题1）p：小王去过英语； q：小王学过英语r : 小王去过英国 s：小王去过日本2）前提： pq，pr，rs结论 ：qs用归结法改写为下述形式：前提：pq，pr，rs，q，s结论 0证明：1 rs 前提引入 2 s 前提引入3 r 1，2归结4 pr 前提引入5 p 3，4归结6 pq 前提引入7 q 6，7归结8 q 前提引入9 0 7，8归结 第3章 一阶逻辑知识点1 公式符号化例如 所有的汽车比飞机慢例如 有的汽车比有的飞机慢例如 有的汽车比所有的飞机慢知识点2 前束范式的定义，及转换 例：将上述转换为前束范式P85 3.32第四章 关系1 笛卡尔积的定义例子：求1，2，34，52二元关系的矩阵表示与图表示3 关系的传递性，对称性，反对称性，自反性。（判断法则）4 关系的交，并，关系的合成，关系的幂运算。5 传递闭包，对称闭包，自反闭包，tsr闭包4 等价关系，偏序关系与哈斯图，集合的划分例11，2，3有多少种划分1,2,3,4有多少种划分例2 A=1，2，3，4，5，6，7，8，9，10如果整除关系为偏序关系，画出哈斯图。并求2，3在该偏序关系的上界和下界第5章 函数知识点1：函数，恒等函数，单射，满射，双射函数例子 判断下列映射是否是函数，是否是双射函数例子 |A|=m |B|=n,求A到B上函数的个数，A到B上双射函数的个数A到B上函数有 nm个，因为每个自变量都有n种选择。A到B的双射函数，如果当n不等于m时，为0.因为双射函数必须一一对应。如果m=n，则有n!知识点2 函数的像，完全原像。知识点3 函数的合成，的定义第6章图1 握手定理2 完全图Kn 圈图Cn，轮图Wn，各有多少顶点，多少边3 生成子图的定义和性质。4 初级通路和简单通路的定义，初级回路和简单回路的定义。例子：给定一个无向图，计算初级通路和简单通路的条数5 平面图的定义，欧