计算机数学基础离散数学部分.docx
《计算机数学基础离散数学部分.docx》由会员分享，可在线阅读，更多相关《计算机数学基础离散数学部分.docx（26页珍藏版）》请在冰点文库上搜索。
计算机数学基础离散数学部分
离散数学复习提纲
一、基本内容
数理逻辑部分
1．理解命题概念，会判别语句是不是命题．理解五个联结词：
否定、析取、合取、条件、和双条件及其真值表，会将简单命题符号化．
具有确定真假意义的陈述句称为命题．
命题必须具备：
其一，语句是陈述句；其二，语句有唯一确定的真假意义.
2．了解公式的概念（公式、赋值、成真指派和成假指派）和公式真值表的构造方法．能熟练地作公式真值表．理解永真式和永假式概念，掌握其判别方法．
判定命题公式类型的方法：
其一是真值表法，其二是等价演算法.
3．了解公式等价概念，掌握公式的重要等价式和判断两个公式是否等价的有效方法：
等价演算法、列真值表法和主范式方法．
4．理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念，熟练掌握它们的求法．
命题公式的范式不惟一，但主范式是惟一的．
命题公式A有n个命题变元，A的主析取范式有k个极小项，有m个极大项，则
求命题公式A的析取（合取）范式的步骤．
求命题公式A的主析取（合取）范式的步骤．
5．要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：
真值表法、直接证法、间接证法．
重点：
命题与联结词，公式与解释，真值表，公式的类型及判定，主析取（合取）范式，命题演算的推理理论.
6．理解谓词、量词、个体词、个体域，会将简单命题符号化．
原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项．谓词用来刻划个体词的性质或之间的关系．
量词分全称量词，存在量词.
命题符号化注意：
使用全称量词，特性谓词后用；使用存在量词，特性谓词后用．
7．了解原子公式、谓词公式、变元（约束变元和自由变元）与辖域等概念．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．
由原子公式、联结词和量词构成谓词公式．谓词公式具有真值时，才是命题．
在谓词公式中，会区分约束变元和自由变元．
在非空集合D（个体域）上谓词公式A的一个解释或赋值有3个条件．
在任何解释下，谓词公式A取真值1，A为逻辑有效式（永真式）；公式A取真值0，A为永假式；至少有一个解释使公式A取真值1，A称为可满足式．
在有限个体域下，消除量词的规则为：
设D＝{
}，则
会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名规则、代入规则等．
掌握谓词演算的等价式和重言蕴含式．并进行谓词公式的等价演算．
8．了解前束范式的概念，会求公式的前束范式的方法.
若一个谓词公式F等价地转化成
，那么
就是F的前束范式．前束范式仍然是谓词公式．
9．了解谓词逻辑推理的四个规则．会给出推理证明．
谓词演算的推理是命题演算推理的推广和扩充，命题演算中基本等价式，重言蕴含式以及P，T，CP规则在谓词演算中仍然使用．谓词逻辑的推理演算引入了US规则（全称量词指定规则），UG规则（全称量词推广规则），ES规则（存在量词指定规则），EG规则（存在量词推广规则）等.
集合论部分
1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法．
具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素．
集合的表示方法：
列举法和描述法.
注意：
集合的表示中元素不能重复出现，集合中的元素无顺序之分．
掌握集合包含（子集）、真子集、集合相等等概念．
注意：
元素与集合，集合与子集，子集与幂集，空集与所有集合的关系：
空集是惟一的，它是任何集合的子集．
集合A的幂集P（A）＝
，A的所有子集构成的集合．若|A|＝n，则|P（A）|=2n．
2．熟练掌握集合A和B的并、交，补集A补集总相对于一个全集）.差集A－B，对称差等运算，并会用文氏图表示．
掌握集合运算律（运算的性质）.
3．掌握用集合运算基本规律证明集合恒等式的方法．
集合的运算问题：
其一是进行集合运算；其二是运算式的化简；其三是恒等式证明．
证明方法有二：
（1）要证明A＝B，只需证明A是B的子集，又B是A的子集；
（2）通过运算律进行等式推导．
4．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算．
有序对就是有顺序二元组，如，x,y的位置是确定的，不能随意放置．
注意：
有序对，以a,b为元素的集合{a,b}={b,a}；有序对（a,a）有意义，而集合{a,a}是单元素集合，应记作{a}．
集合A，B的笛卡儿积A×B是一个集合，规定A×B＝{xA,yB}，是有序对的集合.笛卡儿积也可以多个集合合成，A1×A2×…×An．
5．理解关系的概念：
二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图，掌握关系的集合运算和求复合关系、逆关系的方法．
二元关系是一个有序对集合，
，记作xRy．
关系的表示方法有三种：
集合表示法，
关系矩阵：
RA×B，R的矩阵
.
关系图：
R是集合上的二元关系，若R，由结点ai画有向弧到bj构成的图形．
空关系是唯一、是任何关系的子集的关系；
全关系
；
恒等关系
，恒等关系的矩阵MI是单位矩阵．
关系的集合运算有并、交、补、差和对称差．
复合关系
；
复合关系矩阵：
（按布尔运算）；
有结合律：
（RS）T＝R（ST），一般不可交换．
逆关系
；
逆关系矩阵满足：
；
6．理解关系的性质（自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示），掌握其判别方法（利用定义、矩阵或图，充分条件），知道关系闭包的定义和求法．
注：
（1）关系性质的充分必要条件：
R是自反的；
R是反自反的；
R是对称的；
R是反对称的；
R是传递的.
（2）IA具有自反性，对称性、反对称性和传递性．EA具有自反性，对称性和传递性．故IA，EA是等价关系．具有反自反性、对称性、反对称性和传递性．IA也是偏序关系．
7．理解等价关系和偏序关系概念，掌握等价类的求法和作偏序集哈斯图的方法．知道极大（小）元，最大（小）元的概念，会求极大（小）元、最大（小）元、最小上界和最大下界．
等价关系和偏序关系是具有不同性质的两个关系.
知道等价关系图的特点和等价类定义，会求等价类．
一个子集的极大（小）元可以有多个，而最大（小）元若有，则惟一.且极元、最元只在该子集内；而上界与下界可以在子集之外．由哈斯图便于确定任一子集的最大（小）元，极大（小）元．
8．理解函数概念：
函数（映射），函数相等，复合函数和反函数．理解单射、满射和双射等概念，掌握其判别方法．
函数是一种特殊的关系．集合A×B的任何子集都是关系，但不一定是函数．函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制．
二函数相等是指：
定义域相同，对应关系相同，而且定义域内的每个元素的对应值都相同．
函数有：
单射——若
；
满射——f（A）=B或
使得y=f（x）；
双射——单射且满射．
复合函数
即
．
复合成立的条件是：
．一般
，但
.
反函数——若f：
AB是双射，则有反函数f－1：
BA，
，
重点：
关系概念与其性质，等价关系和偏序关系，函数.
图论部分
1．理解图的概念：
结点、边、有向图，无向图、简单图、完全图、结点的度数、边的重数和平行边等.理解握手定理．
图是一个有序对，V是结点集，E是联结结点的边的集合．
掌握无向边与无向图，有向边与有向图，混合图，零图，平凡图、自回路（环），无向平行边，有向平行边等概念．
简单图，不含平行边和环（自回路）的图、
在无向图中，与结点v（V）关联的边数为结点度数
（v）；在有向图中，以v（V）为终点的边的条数为入度
－（v），以v（V）为起点的边的条数为出度
＋（v），deg（v）=deg+（v）+deg－（v）．
无向完全图Kn以其边数
；有向完全图以其边数
．
了解子图、真子图、补图和生成子图的概念．
生成子图——设图G＝，若EE，则图是的生成子图．
知道图的同构概念，更应知道图同构的必要条件，用其判断图不同构.
重要定理：
（1）握手定理设G=，有
；
（2）在有向图D＝中，
；
（3）奇数度结点的个数为偶数个．
2．了解通路与回路概念：
通路（简单通路、基本通路和复杂通路），回路（简单回路、基本回路和复杂回路）．会求通路和回路的长度．基本通路（回路）必是简单通路（回路）．
了解无向图的连通性，会求无向图的连通分支．了解点割集、边割集、割点、割边等概念．了解有向图的强连通强性；会判别其类型．
设图G＝，结点与边的交替序列为通路．通路中边的数目就是通路的长度．起点和终点重合的通路为回路．边不重复的通路（回路）是简单通路（回路）；结点不重复的通路（回路）是基本通路（回路）.
无向图G中，结点u,v存在通路，u,v是连通的，G中任意结点u,v连通，G是连通图．P（G）表示图G连通分支的个数．
在无向图中，结点集VV，使得P（G－V）>P（G），而任意VV,有P（G－V）＝P（G），V为点割集.若V是单元集，该结点v叫割点；边集EE，使得P（G－V）>P（G），而任意EE，有P（G－E）＝P（G），E为边割集．若E是单元集，该边e叫割边（桥）．
要知道：
强连通
单侧连通
弱连通，反之不成立．
3．了解邻接矩阵和可达矩阵的概念，掌握其构造方法及其应用．
重点：
图的概念，握手定理，通路、回路以及图的矩阵表示．
4．理解欧拉通路（回路）、欧拉图的概念，掌握欧拉图的判别方法．
通过连通图G的每条边一次且仅一次的通路（回路）是欧拉通路（回路）．存在欧拉回路的图是欧拉图.
欧拉回路要求边不能重复，结点可以重复．笔不离开纸，不重复地走完所有的边，走过所有结点，就是所谓的一笔画．
欧拉图或通路的判定定理
（1）无向连通图G是欧拉图G不含奇数度结点（即G的所有结点为偶数度）；
（2）非平凡连通图G含有欧拉通路G最多有两个奇数度的结点；
（3）连通有向图D含有有向欧拉回路D中每个结点的入度＝出度．
连通有向图D含有有向欧拉通路D中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－（u）－deg＋（v）＝1．
5．理解汉密尔顿通路（回路）、汉密尔顿图的概念，会做简单判断．
通过连通图G的每个结点一次，且仅一次的通路（回路），是汉密尔顿通路（回路）．存在汉密尔顿回路的图是汉密尔顿图.
汉密尔顿图的充分条件和必要条件
（1）在无向简单图G=中，V3，任意不同结点
，则G是汉密尔顿图．（充分条件）
（2）有向完全图D＝,若
，则图D是汉密尔顿图.（充分条件）
（3）设无向图G=，任意V1V，则W（G－V1）V1（必要条件）
若此条件不满足，即存在V1V，使得P（G－V!
）>V1,则G一定不是汉密尔顿图（非汉密尔顿图的充分条件）．
6．了解平面图概念，平面图、面、边界、面的次数和非平面图．掌握欧拉公式的应用．
平面图是指一个图能画在平面上，除结点之外，再没有边与边相交．
面、边界和面的次数
等概念．
重要结论：
（1）平面图
．
（2）欧拉公式：
平面图
面数为r，则
（结点数与面数之和＝边数＋2）
（3）平面图
．
会用定义判定一个图是不是平面图．
7．理解平面图与对偶图的关系、对偶图在图着色中的作用，掌握求对偶图的方法．
给定平面图G＝〈V，E〉，它有面F1，F2，…，Fn，若有图G*＝〈V*，E*〉满足下述条件：
⑴对于图G的任一个面Fi，内部有且仅有一个结点vi*∈V*；
⑵对于图G的面Fi，Fj的公共边ek，存在且仅存在一条边ek*∈E*，使ek*＝（vi*，vj*），且ek*和ek相交；
⑶当且仅当ek只是一个面Fi的边界时，vi*存在一个环ek*和ek相交；
则图G*是图G的对偶图．
若G*是G的对偶图，则G也是G*的对偶图．一个连通平面图的对偶图也必是平面图．
8．掌握图论中常用的证明方法．
重点：
欧拉图和哈密顿图、平面图的基本概念及判别．
9．了解树、树叶、分支点、平凡树、生成树和最小生成树等概念，掌握求最小生成树的方法．
连通无回路的无向图是树．树的判别可以用图T是树的充要条件（等价定义）．
注意：
（1）树T是连通图；
（2）树T满足m＝n－1（即边数=顶点数-1）．
图G的生成子图是树，该树就是生成树．
每边指定一正数，称为权，每边带权的图称为带权图．G的生成树T的所有边的权之和是生成树T的权，记作W（T）．最小生成树是带权最小的生成树．
10．了解有向树、根树、有序树、二叉树、二叉完全树、正则二叉树和最优二叉树等概念．了解带权二叉树、最优二叉树的概念，掌握用哈夫曼算法求最优二叉树的方法．
有向图删去边的方向为树，该图为有向树．对非平凡有向树，恰有一个结点的入度为0（该结点为树根），其余结点的入度为1，该树为根树．每个结点的出度小于或等于2的根树为二叉树；每个结点的出度等于0或2的根树为二叉完全树；每个结点的出度等于2的根树称为正则二叉树．
有关树的求法：
（1）生成树的破圈法和避圈法求法；
（2）最小生成树的克鲁斯克尔求法；
（3）最优二叉树的哈夫曼求法
重点：
树与根树的基本概念，最小生成树与最优二叉树的求法.
代数结构部分
1.二元运算（定义，封闭性）、运算表
2.各种定律（交换、结合、幂等、分配、吸收、消去、幺元、零元、逆元）
3·代数系统、子代数、积代数（定义、特殊元素、代数常数）
4·同态与同构（同态等式、证明）
5·半群、独异点
6·群、子群、阿贝尔群、生成子群、元素的阶（周期）、循环群（定义与证明）·环、含幺环、零因子、无零因子环、整环、除环与域
7·格（两种定义）、分配格、有界格、布尔格（判断）
练习题
数理逻辑部分
（一）
1．填空题
（1）公式（pq）（pq）的成真赋值为__________________；
（2）设p,r为真命题，q,s为假命题，则复合命题（pq）（rs）的真值为________；
（3）设p,q均为命题，在_________________________条件下，p与q的排斥或也可以写成p与q的相容或；
（4）公式（pq）与（pq）（pq）共同的成真赋值为____________；
（5）设A为任意的公式，B为重言式，则AB的类型为______________.
2．将下列命题或语句符号化
（1）
不是无理数是不对的；
（2）小刘既不怕吃苦，又很钻研；
（3）只有不怕困难，才能战胜困难；
（4）只要别人有困难，老王就帮助别人，除非困难解决了；
（5）整数n是偶数当且仅当n能被2整除.
3．求复合命题的真值
p：
2能整除5，q：
旧金山是美国的首都，r：
一年分四季.
（1）（（pq）r）（r（pq））；
（2）（（qp）（rp））（（pq）r）.
4．判断推理是否正确
设y=2|x|，x为实数.推理如下：
若y在x=0可导，则y在x=0连续.y在x=0连续.所以，y在x=0可导.
5．判断公式的类型
（1）（（pq）（（pq）（pq）））r;
（2）（p（qp））（rq）;
（3）（pr）（qr）.
（二）
1．填空题．
（1）设A为含命题变项p、q、r的重言式，则公式A（（pq）→r）的类型为___________；
（2）设B为含命题变项p、q、r的矛盾式，则公式B（（pq）→r）的类型为___________；
（3）设p、q为命题变项，则（pq）的成真赋值为________________；
（4）设p、q为真命题，r、s为假命题，则复合命题（pr）（q→s）的真值为___________；
（5）矛盾式的主析取范式为_________________；
（6）设公式A含命题变项p、q、r，又已知A的主合取范式为M0M2M3M5，则A的主析取范式为_______________________________．
2．用等值演算法求公式的主析取范式或主合取范式
（1）求公式p→（（qr）（p（qr）））的主析取范式；
（2）求公式（（p→q））（q→p）的主合取范式；
（3）求公式（（pq）（p→q））（q→p）的主析取范式，再由主析取范式求出主合取范式．
3．用真值表求公式（p→q）r的主析取范式
4．将公式p→（q→r）化成与之等值且仅含{,}中联结词的公式．
5．用主析取范式判断（pq）与（（pq）（（pq））是否等值．
6.用消解原理证明p（pq）（r）（pqr）是矛盾式.
（三）
1．填空题
（1）（AB）B_____________为拒取式推理定律；
（2）（AB）B______________为析取三段论推理定律；
（3）（AB）（BC）_________________为假言三段论推理定律；
（4）（AB）A________________为假言推理定律．
2．判断推理是否正确，并证明之（方法不限）
（1）如果王红学过英语和法语，则她也学过日语．可她没有过日语，但学过法语.所以，她也没学过英语；
（2）若小李是文科学生，则他爱看电影．小李不是文科学生.所以,他不爱看电影．
（3）设y=2|x|，x为实数.推理如下：
若y在x=0可导，则y在x=0连续.y在x=0连续.所以，y在x=0可导.
3．在自然推理系统P中，用直接证明法构造下面推理的证明
（1）前提：
（pq）,q→r,r
结论：
p
（2）前提：
p→r,q→s,p,q
结论：
rs
4．在自然推理系统P中，用附加前提证明法证明下面推理．
（1）前提：
p（qr）,s→p,q
结论：
r→s
（2）前提：
p→q,pr,q→s
结论：
s→r
5．在自然推理系统P中，用归谬法证明下面推理．
前提：
p→（q→r）,pq
结论：
rs
6．在自然推理系统P中，构造下面用自然语言给出的推理．
若小张喜欢数学，则小李或小赵也喜欢数学．若小李喜欢数学，则他也喜欢物理．小张确实喜欢数学，可小李不喜欢物理.所以,小赵喜欢数学．
（四）
1.填空题
2.
（1）设F（x）：
x具有性质F，G（x）：
x具有性质G.命题“对所有的x而言，若x有性质F，则x就有性质G”的符号化形式为__________________________；
（2）设F（x）：
x具有性质F，G（x）：
x具有性质G.命题“有的x既有性质F、又有性质G”的符号化形式为__________________________；
（3）设F（x）：
x具有性质F，G（y）：
y具有性质G.命题“若所有的x都有性质F，则所有的y都有性质G”的符号化形式为__________________________；
（4）设F（x）：
x具有性质F，G（y）：
y具有性质G.命题“若存在x具有性质F，则所有的y都没有性质G”的符号化性质为__________________________；
（5）设A为任意的一阶逻辑公式，若A中_________________，则称A为封闭的公式；
（6）在一阶逻辑中将命题符号化时，若没指明个体域，则使用________________个体域.
2.用0元谓词将下列命题符号化
（1）只要4不是素数，3就是素数；
（2）只有2是偶数，4才是偶数；
（3）5是奇数当且仅当5不能被2整除.
3.在一阶逻辑中将下列命题符号化
（1）所有的整数，不是负整数，就是正整数，或者是0；
（2）有的实数是有理数，有的实数是无理数；
（3）发明家都是聪明的并且是勤劳的．王前进是发明家.所以,王前进是聪明的并且是勤劳的．
4．在一阶逻辑中，将下列命题符号化
（1）实数不都是有理数；
（2）不存在能表示成分数的无理数．
5．在一阶逻辑中，将下列命题符号化
（1）若x与y都是实数且x>y，则x+2>y+2；
（2）不存在最大的自然数．
6．证明题
（1）证明x（F（x）G（x））y（H（y）R（y））为可满足式、但不是永真式；
（2）证明（xF（x）yG（y））yG（y）xF（x）为永真式．
（五）
1．填空题．
（1）xyF（x,y）的前束范式为_______________________；
（2）由量词量词分配等值式，x（A（x）B（x））________________；
（3）缩小量词的辖域,x（F（x）B）________________；
（4）公式（（yG（x）xF（x））yG（y））xF（x）的类型为_____________________；
（5）取解释I为：
个体域为D={a}，F（x）：
x具有性质F，在I下xF（x）xF（x）的真值为_________；
（6）前提：
xyF（x,y）
结论：
yF（y,y）
以上推理是错误的，某学生却给出了如下证明：
①xyF（x,y）前提引入
②yF（y,y）①
此证明错在_____________________．
2．在有限个体域内消去量词．
（1）个体域D={1,2,3}，公式为
xy（F（x）G（y））
（2）个体域D={a,b}，公式为
xy（F（x,y）G（y,x））
3．求前束范式．
（1）x（F（x,y）y（G（x,y）zH（x,y,z）））；
（2）（xF（x,y）yG（x,y,z））zH（z）.
4．在自然推理系统NL中，构造下面推理的证明．
（1）前提：
xy（F（x）G（y））,F（a）
结论：
xG（x）
（2）前提：
x（F（x）y（G（y）H（x）））,xF（x）
结论：
x（F（x）G（x）H（x））
5．在自然推理系统F中，构造下面用自然语言描述的推理．
火车都比汽车快，汽车都比轮船快，a是火车，b是汽车，c是轮船．所以，a比b快，b比c快．
（六）
1.填空题
（1）设A={2,a,{3},4},B={,4,{a},3}，则AB=______________________________；
（2）设A={{{1,2}},{1}}，则P（A）=__________________________________________；
（3）设X,Y,Z为任意集合，且XY={1,2,3},XZ={2,3,4}，若2Y,则一定有_______；
A.1ZB.2ZC.3ZD.4Z
（4）下列命题中为真的是________________________________________________；
A.{a,{b}}{{a,{b}}}B.P（{,{}}）C.{a}XaX
D.XY=YX=E.XY=XXY
（5）设[0,1]和（0,1）分别表示实数集上的闭区间和开区间，则下列命题中为真的是
_____________________________________；
A.{0,1}（0,1）B.{0,1}[0,1]
升级会员 