集合论
一、基本概念
集合(set)：做为整体识别的、确定的、互相区别的一些对象的总体。
规定集合的三种方式：列举法、描述法、归纳法
集合论的三大基本原理
外延公理：两个集合A和B相等当且仅当它们具有相同的元素（无序性）
概括公理：对于任意个体域U，任一谓词公式P都确定一个以该域中的对象为元素的集合S（确定性）
正规公理：不存在集合A1,A2,A3,…使得…∈A3∈A2∈A1（有限可分，集合不能是自己的元素）
注意：隶属、包含的判断（有时两者兼有）
定理1：对于任意集合A和B，A=B当且仅当A ? B且B ? A
?传递性，对全集、空集的?关系等
定理5：空集是唯一的
子集、真子集、子集个数等
运算：并、交、补、差、幂集，及一些运算性质、公式
幂集：对任意集合A，ρ(A)称作A的幂集，定义为：ρ(A)={x|x?A}，所有子集的集合
设A,B为任意集合，A A B当且仅当ρ(A) ?ρ(B)
集合族：如果集合C中的每个元素都是集合，称C为集合族
集合族的标志集：如果集合族C可以表示为某种下标的形，C={Sd|d∈D}，那么这些下标组成的集合称作集合族C的标志集
广义并、广义交，及相关运算性质、公式
归纳定义：
基础条款：规定某些元素为待定义集合成员，集合其它元素可以从基本元素出发逐步确定
归纳条款：规定由已确定的集合元素去进一步确定其它元素的规则
终极条款：规定待定义集合只含有基础条款和归纳条款所确定的成员
基础条款和归纳条款称作“完备性条款”，必须保证毫无遗漏产生集合中所有成员
终极条款又称“纯粹性条款”，保证集合中仅包含满足完备性条款的那些对象
例：自然数的归纳定义、数学归纳法等……（建议看一下课件例子了解一下思路）
二、关系
有序组（二元）：设a,b为任意对象，称集合族{{a},{a,b}}为二元有序组，简记为
称a为
递归定义：n=2时，
n>2时，
集合的笛卡儿积：对任意集合A,A2,…,A，A1×A2称作集合A1，A2的笛卡儿积，定义如下：A1×A2 = {
A1×A2×…×An =(A1×A2×…×An-1) ×An
定理：对于任意有限集合A1,…,An，有|A1×…×An|=|A1|*…*|An|
一些运算性质
关系是各个对象之间的联系和对应
R称为集合A1,A2,…,An-1到An的n元关系，如果R是A1×A2×…×An的一个子集。当A1=A2=…=An-1=An时，也称R为A上的n元关系
几个特殊二元关系：空关系、全关系、相等关系
定义：设R为A到B的二元关系(R?A×B)
xRy表示
定义域domain：Dom(R)={x|x∈A∧?y(
R的值域range：Ran(R)={y|y∈B∧?x(
称A为R的前域，B为R的陪域
注意：前域与定义域，陪域与值域的差别。尤其是定义域与前域，与函数的差别
关系表示法：
集合表示法
关系图表示法（有向箭头，主要是前域陪域相同的关系图）
关系矩阵（mij=1当且仅当aiRbj；mij=0当且仅当?aiRbj）
关系相等：相同前域陪域，且?x?y(xRy?xSy)
运算：要有相同前域、陪域。但总可以对关系的前域和陪域做适当的扩充，使之满足条件并（矩阵分量析取）
交（矩阵分量合取）
差（前一个关系和后一个关系的补矩阵做合取）
补（矩阵做否定）
逆运算：R~={
合成：R?A×B，S?B×C，R和S的合成关系R?S定义为：
R?S={
矩阵乘法，其中乘法用合取，加法用析取
幂运算：定义为自身的n次合成Rn=R?…?R（n个R合成），R0=EA
幂关系有限定理：设集合A的基数为n，R是A上的二元关系，则存在自然数i,j使得0 ≤i＜j≤2n2，有Ri=Rj（鸽笼原理，A×A有n2个元素，子集个数为2n^2个）
自反关系：（就是每个元素都和自己有关系）
?x(x∈A→xRx)
关系图：每个节点都有环
关系矩阵：对角线全为1
反自反关系：（每个元素都和自己没关系）
?x(x∈A→?xRx)
关系图：每个节点都没有环
关系矩阵：对角线全为0
对称关系：（每对关系都是相互的）
?x?y(x,y∈A∧xRy→yRx)
关系图：两个节点之间有边的就有反向边
关系矩阵：对称矩阵
反对称关系：（若有相互关系则只能是同一个元素，不同元素间不能有相互关系）
?x?y(x,y∈A∧xRy∧yRx→x=y)
关系图：两个节点之间只能有一条单向边
关系矩阵：ci,j=1(i≠j)时cj,i=0
传递关系：
?x?y?z(x,y,z∈A∧xRy∧yRz→xRz)
关系图：如果有边v1v2,…,vn-1vn，则有边v1vn
注意：A上的空关系?是反自反的，不是自反的（此外是对称的、反对称的、传递的）如果A=?，那么A上的空关系就是自反的，同时也是反自反的，因为注意定义谓词的前件x∈A始终为假
A上的相等关系EA既是对称的，又是反对称的
即对于特殊集合、关系的判断要从定义式出发，注意前件的真假
R自反当且仅当EA?R
R反自反当且仅当EA∩R??
R对称当且仅当R?R~
R反对称当且仅当R∩R~?EA
R传递当且仅当R2?R
运算的封闭性：如果关系R的某个性质经过关系运算后仍然保持，则称该性质对这个运算封闭（以上5个特性对交和求逆运算都封闭，自反对合成封闭）
等价关系：等价关系R为A上的自反、对称、传递的二元关系
等价类：设R为A上的等价关系，对于每个a∈A，a的等价类记做[a]R(简记[a])，定义为：[a]R={x|x∈A ∧xRa}，a称作[a]R的代表元素
划分：满足下列条件的集合A的子集族π
?B(B∈π→B≠?) （划分单元里没有空集）
∪π=A （所有划分单元合起来是全集）
?B ?B’(B∈π∧B’∈π∧B≠B’→B ∩B’=?) （划分单元两两不相交）
π中的元素称为划分的单元
特别约定A=?时只有划分?
A上的等价关系R的所有等价类的集合，构成A的一个划分，称作等价关系R对应的划分反过来，集合A的一个划分π，也对应A上的一个等价关系R，称作划分π对应的等价关系
等价关系和划分的一一对应
划分的“粗细”概念：如果π1的每一个单元都包含于π2的某个单元，称π1细于π2，表示为π1≤π2；如果π1≤π2而且π1≠π2 ，则表示为π1＜π2，称作“真细于”
定理：π1，π2分别是等价关系R1，R2对应的划分，那么R1?R2 ? π1≤π2
定理说明，越“小”（包含二元组较少）的等价关系对应越细的划分；最小的等价关系是相等关系EA；最大的等价关系是全关系
划分的运算：（结合图来很好理解）
积划分运算：划分π1和π2的积划分π1?π2是满足如下条件的划分：π1?π2细于π1和π2；如果某个划分π细于π1和π2，则π一定细于π1?π2；也就是说，π1?π2是细于π1和π2的最粗划分（”最小公倍数”）
积划分对应于等价关系交运算
和划分运算：划分π1和π2的和划分π1+π2是满足如下条件的划分：π1和π2均细于π1+π2；如果有划分π，π1和π2均细于π，则π1+π2细于π。也就是说，π1+
π2是粗于π1和π2的最细划分（“最大公约数”）
和划分不对应于等价关系的并运算，而是对应于等价关系并运算结果的传递闭包
二元关系R的传递闭包t(R)：t(R) 是传递的，R?t(R)，对于A上的任意一个具有传递性质且包含R的关系R’，t(R)?R’
商集：R是A上的等价关系，称A的划分{[a]R|a∈A}为A的R商集，记做A/R A/(R1∩R2 )=A/R1?A/R2
A/t(R1∪R2)=A/R1+A/R2
序关系：R为集合A上的自反、反对称、传递的二元关系
存在序关系R的集合A称作有序集（ordered set），用二元有序组
哈斯图：对序关系关系图的一种简化画法
由于序关系自反，各结点都有环，省去；
由于序关系反对称且传递，所以关系图中任何两个不同的结点直接不会有双向的边或通路，所以省去边的箭头，把向上的方向定为箭头方向
由于序关系传递，所以省去所有推定的边，即a≤b,b≤c有a≤c，省去ac边
元素排序：a≤b，称a先于或等于b；a小于或等于b；如果?(a≤b)，则称a,b不可比较或者不可排序
最大（小）元、极大（小）元（必须是B中元素）：
B的最小元b：b∈B∧?x(x∈B→b≤x) （必须比每个B的元素都小于或等于）
B的最大元b：b∈B∧?x(x∈B→x≤b) （必须每个B的元素都比它小于或等于）
B的极小元b：b∈B∧??x(x∈B∧x≠b∧x≤b) （比B中每个可比元都小于或等于）
B的极大元b：b∈B∧??x(x∈B∧x≠b∧b≤x) （B中每个可比元都比它小于或等于）
极大和最大的差别在于B中是否包含不可比较的元素
最大（小）元必为极大（小）元；最大（小）元若有则唯一；极大（小）元恒存在未必唯一上（下）界，上（下）确界（只要是A中元素）：
B的上界a：a∈A∧?x(x∈B→x≤a) （必须每个B的元素都比它小于或等于）
B的下界a：a∈A∧?x(x∈B→a≤x) （必须比每个B的元素都小于或等于）
B的上确界a：a是B的所有上界的集合最小元
B的下确界a：a是B的所有下界的集合最大元
最大（小）元是上（下）确界；属于B的上（下）界为最大（小）元；都未必存在
链、反链
半序关系：R为集合A上的反自反、反对称、传递的二元关系（即序关系除去每个元素与自己的关系）
三、函数
定义：如果X到Y的二元关系f?X×Y，对于每个x∈X，都有唯一的y∈Y，使得
前域和定义域重合；单值性：
y=f(x)，称x为自变元，y为函数在x处的值，y为x的像点，x为y的源点（基于映射）
X≠?时，空关系?不是函数，当X＝?时，空关系?是函数，称作空函数
函数的规定方法：列表法、图标法、解析法、递归定义
函数相等与包含
函数个数：如果|X|=m，|Y|=n，则{f|f:X→Y}的基数为n m，共有n m个X到Y的函数。X到
Y的全体函数集合表示为Y X
定义域子集的映象：f’(A)={y|?x(x∈A∧y=f(x))}（即定义域的一个子集A的值域）
函数合成（恩，不写了。。。）
单射：如果任意x1≠x2有f(x1)≠f(x2)。如果f和g都是单射函数，则其合成g?f也是单射函数。如果g?f是单射函数，则f是单射函数
满射：如果任意y都有x使得y=f(x)，即Ran(f)=Y。如果f和g都是满射函数，则其合成g?f 也是满射函数。如果g?f是满射函数，则g是满射函数
双射函数：如果f既是单射函数又是满射函数，称作双射函数。如果f和g都是双射函数，则其合成g?f也是双射函数。如果g?f是双射函数，则f是单射函数，g是满射函数
逆函数：只有双射函数存在逆函数
左逆函数：如果g ?f=EX，则称g为f的左逆函数
右逆函数：如果f ?g=EY，则称g为f的右逆函数
f可逆当且仅当f既有左逆函数，又有右逆函数，而且左逆函数和右逆函数相等
图论
图：由结点和联结结点的边所构成的离散结构G=
结点集V（非空），边集E（多重集，可以有多个相同边）
有向边：结点的二元有序组表示
无向边：结点的两元素多重集表示
有限图：V,E都有限集
重边：重数大于1的边
有重边的为重图，否则为单图
简单图：无环无重边的无向图
完全图：任意两个不同结点间都有边，Kn
孤立结点、零图（只有孤立结点）
赋权图：G=
结点的度：d(v)定义为关联端点v的边的数目
注意对有向图来说度d(v)=d+(v)+d-(v)
度的总和为偶数，边数目的两倍；有向图出度等于入度
悬挂点：一度的顶点
正则图：所有顶点的度均相同的图称为正则图，按照顶点的度数k称作k-正则图，Kn是n-1正则图
子图、真子图：边集结点集都必须为子集
生成子图：结点集相同的子图
补图：结点集相同，边集交集为空，并集为完全图
图的同构：可以将V1中所有的结点一一对应地置换为V2中的结点名后得到的图等于G2 （同分异构体）
拟路径：v1,e1,v2,e2,v3,…,vl-1,el-1,vl，其中ei=
路径：拟路径中的边各不相同
闭路径：v1=vl的路径
通路：路径中的顶点各不相同
回路：v1=vl的通路
路径和通路定理：在有n个顶点的图G中，如果有顶点u到v的拟路径，那么u到v必有路径，并且必有长度不大于n-1的通路
闭路径和回路定理：在有n个顶点的图G中，如果有顶点v到v的闭路径，那么必定有一条从v到v的长度不大于n的回路
可达：u=v，或者存在一条u到v的路径
连通的无向图：无向图中任意两个顶点都是可达的
强连通的有向图：有向图中任意两个顶点都是互相可达的
单向连通的有向图：任意两个顶点，至少从一个顶点到另一个是可达的
弱连通的有向图：将有向图看作无向图时是连通的
连通分支：图G的连通子图G’，而且G’不是任何其它连通子图的真子图（最大性）
欧拉图：如果图G上有一条经过所有顶点、所有边的闭路径（允许顶点重复）
–无向图：G连通，所有顶点的度都是偶数
–有向图：G弱连通，每个顶点的出度与入度相等
欧拉路径：如果图G上有一条经过所有顶点、所有边的路径（非闭）（允许顶点重复）–无向图：G连通，恰有两个顶点的度是奇数
–有向图：G连通，恰有两个顶点出度与入度不相等，其中一个出度比入度多1，另一个入度比出度多1
哈密顿图：如果图G上有一条经过所有顶点的回路（不要求经过所有边）
哈密顿通路：如果图G上有一条经过所有顶点的通路（非回路）
判定定理（充分非必要）：如果具有n个顶点的图G的每一对顶点的度数之和都不小于n-1，那么G中有一条哈密顿通路。如果G的每一对顶点度数之和不小于n，且n>=3，则G为一哈密顿图
邻接矩阵：无重边的有向图G=
注意：与关系矩阵的联系。
拟路径，邻接矩阵自乘L次：A L，则乘积结果矩阵中每个分量aij(L)的含义为G中顶点vi 到vj的长度为L的拟路径条数
路径矩阵B=A ∨A(2) ∨A(3) ∨…∨A(|V|)，其中A(m)=A ∧ A ∧…∧A
B的每个分量bij表示vi到vj是否有路径
可达性矩阵：P=I ∨B，加上顶点的自身可达性
关联矩阵（简单无向图）：表示顶点和边的关联关系，n*m矩阵。通过矩阵的秩来判定图的连通分支个数
二分图：满足如下条件的无向图G=
有非空集合X,Y, X ∪Y=V, X ∩Y= ?
每个{vi,vj}∈E，都有vi∈X∧vj∈Y或者vi∈Y∧vj∈X
可以用G=
如果X,Y中任意两个顶点之间都有边，则称为完全二分图。记作K|X|,|Y|
二分图的等价条件：G至少要有两个顶点，而且G中所有回路的长度都是偶数
匹配：将E的子集M称作一个匹配，如果M中的任意两条边都没有公共端点。
边数最多的匹配称作最大匹配。
如果X(Y)中的所有的顶点都出现在匹配M中，则称M是X(Y)-完全匹配。
如果M既是X-完全匹配，又是Y-完全匹配，称M是完全匹配
**匈牙利算法：任取一个匹配，取非饱和点走交错路（边交替属于不属于已有匹配），若终点是非饱和点，则令匹配为原匹配和增广路的?（即属于这两个集合但不属于交集部分）；若终点是饱和点，则将起点去掉不再考虑（我猜不会考）
平面图：如果无向图G可以在一个平面上图示出来，并且各边仅在顶点处相交，称作平面图。K5和K3,3都不是平面图，K5是顶点数最少的非平面图，K3,3是边数最少的非平面图平面图等价条件：G或者G的子图作任何同胚操作（在原图的边上增加或者删除二度节点）后得到的图均不能以K5及K3,3为子图
树：连通无回路的无向图称为树
树中的悬挂点称作树叶
非树叶节点称作分支点
仅有单个孤立节点的树称作空树
每个连通分支都是树的图称作森林（树也是森林）
性质：简单、二分、平面
顶点数比边数多1
删去任意一条边就不连通
生成树：如果图T是G的生成子图，且T是树。任意连通图G都至少有一棵生成树
根树rooted tree递归定义
一个孤立节点v0是根树，v0称为树根
如果T1,T2,…Tk是根树，其树根分别是v1,v2,…,vk，则
V=V(T1) ∪V(T2) ∪…∪V(Tk) ∪{v0}；
E=E(T1) ∪E(T2) ∪…∪E(Tk) ∪{v0,,v1} ∪{v0,,v2}…∪{v0,,vk}
T=
Tn称为T的子树subtree，树根称为父节点parent，而子树的树根称为子节点child
v1,v2,…,vk互称兄弟节点sibling
根树中每个节点都是某个子树的根
n元树：每个节点都至多有n个子节点的根树称作n元树
二元有序树可以用来表示任何n元有序树：左子节点表示第一个子节点，右子节点表示下一个兄弟节点
二元树的遍历：先根、中根、后根
应用：表达式树、排序搜索树等
抽象代数
算术：研究整数、有理数、实数和复数的加、减、乘、除等运算
代数：算术的一般化，允许用字母等符号来代替数进行运算
代数结构：在一个对象集合上定义若干运算，并设定若干公理描述运算的性质非空集合S，称作代数结构的载体
载体S上的若干运算
一组刻画载体上各运算性质的公理
抽象代数：抛弃代数结构中对象集合与运算的具体意义，研究运算的一般规律（交换、结合、
分配），并对代数结构进行分类，研究其一般性质
运算：Sn到S的一个函数，称为n元运算，常用*表示二元运算，常用Δ表示一元运算
运算的基本性质：（必须要满足）
普遍性：S中的所有元素都可参加运算
单值性：相同的元素运算结果也相同且唯一
封闭性：任何元素参加运算的结果也是S中的元素
二元运算一般性质：（可以不满足）
结合律：?x?y?z(x,y,z∈S →x*(y*z)=(x*y)*z)
交换律：?x?y(x,y∈S →x*y=y*x)
*运算对#运算满足分配律：?x?y?z(x,y,z∈S →x*(y#z)=(x*y)#(x*z))
幺元：
右幺元：?x(x*er=x)
左幺元：?x(el*x=x)
一般情况下，左右幺元可能是不同元素，也可能有多个
如果存在幺元，那么幺元是唯一的，而且同时是左右幺元
零元：
右零元：?x(x*or=or)
左零元：?x(ol*x=ol)
如果存在零元则唯一
逆元：
如果x*y=y*x=e，那么x,y互称逆元
多于1个元素的载体集上零元没有逆元
满足结合律的代数结构中，逆元唯一
可约cancelable元素：
a*x=a*y蕴涵x=y（左可约）
x*a=y*a蕴涵x=y（右可约）
那么a称为可约的
满足结合律的代数结构中，有逆元的元素可约
同类型代数结构：|S|=|S’|；运算的元数相同
同构的代数结构：存在S->S’的一一映射h；S中运算的像等于运算数像在S’的运算结果h(x*y)= h(x)*’h(y)
同态映射：对于代数结构
如果h是单射函数，称作单一同态
如果h是满射函数，称作满同态
如果h是双射函数，称做同构映射
同余关系：代数结构
半群：运算满足结合律的代数结构
独异点：含有幺元的半群
群：半群；有幺元；每个元素都有逆元
交换群：满足交换律的群
环：
a*(b+c)=a*b+a*c
域：
形式语言与自动机
语言的定义：Chomsky:按照一定规律构成的句子和符号串的有限或者无限的集合
形式语言主要研究语言描述的问题
穷举法：只适合句子数目有限的语言
语法描述：通过有限的替换规则，生成语言中合格的句子
自动机：对输入的句子进行检验，区别哪些是语言中的句子，哪些不是语言中的句子字符串：
设V是有限集合，其中元素称为“字符”
由V中字符相连而成的有限序列称为“字符串”
不含任何字符的串称为“空串”，记做ε
字符串所包含的字符个数称为“长度”，记做|s|，|ε|=0
包括空串的V上的字符串全体记做V*
字符串连接：s=ab,t=gg连接st=abgg
字符串n次幂：s自身连接n次，s0=ε
字符串集合的运算：
乘积：AB={st|s∈A,t∈B}
幂运算：A0={ε}，An=An-1A=AAn-1
闭包：A*=A0∪A1∪A2…
正闭包：A+=A1∪A2…=A*-{ε}
正则表达式：
–RE1:ε是正则式，正则集{ε}
–RE2:x∈V，x是正则式，正则集{x}
–RE3:如果α、β是正则式，则αβ是正则式，正则集AB（字符串集合乘积）
–RE4:如果α、β是正则式，则(α|β)是正则式，正则集A∪B
–RE5:如果α是正则式，则(α)*是正则式，正则集A*
V上的正则表达式对应了V*的一个子集（正则子集）
短语结构语法：是一个四元组G(V,S,v0,┠)
V是字符集
S V，称作终结符，N=V-S称作非终结符
┠称作产生式关系，由w┠w’这样的产生式构成，表示w可以替换成w’，分别称为左部和右部
v0∈N，称作初始符（句子符），是替换的起点
直接导出关系（x→y）：x=lwr, y=lw’r, 且w┠w’是产生式, l,r∈V*
→关系的传递闭包→∞，w∈S*是语法正确的句子当且仅当v0 →∞w
导出的结果称作符合语法G的句子
利用语法G产生的所有的正确构造的句子的集合称作为G的语言，记做L(G)
导出树：用多元有向树表示语言导出过程。起始符v0作为树根，每个子树的树根是某个生成式的左部，子节点分别是生成式右部包含的符号，适合所有产生式的左部仅有一个非终结
符情形
乔姆斯基形式语法分类：
0型语法：如果对产生式没有任何约束（无限制语法，短语结构语法PSG）产生递归可枚举语言，被图灵机识别
1型语法：如果所有产生式形如αAβ┠αγβ（A是非终结符，α,β,γ是任意串，但γ不能为空串）（上下文相关语法CSG）
产生上下文相关语言，被线性有界自动机识别
2型语法：如果所有产生式左部是一个非终结符，形如A┠γ（γ可以是任意串），（上下文无关语法CFG）
产生上下文无关语言，被下推自动机识别
为大多数程序设计语言的语法提供理论基础
3型语法：如果所有产生式左部是一个非终结符，右部最多有一个非终结符，而且只能在最右端（正则语法RG）
产生正则语言，被有限状态自动机识别，也可以用正则表达式表示
通常用来定义检索模式或者程序设计语言中的词法结构
如果某个语言可以用某型语法产生，则称作某型语言。L3 ? L2 ? L1 ? L0
语言导出的逆过程：从一个句子得到导出树或导出过程
BNF（Backus-Naur Form）范式：
形式简单，仅包含三个符号：“::=”，定义为；“|”，或；“<>”，用来区分非终结符
可以表示2、3型语法（上下文无关、正则）
产生式左部仅有一个非终结符
相同左部的产生式合并用“|”隔开
非终结符用“<>”标记
注意：课件上的例子，便于直接记忆
递归出现一次，并在最右，称为正规的，3型语法中的递归产生式都是正规的
BNF例子：“十进制数”
–<十进制数>::=<无符号整数> | <小数> | <无符号整数><小数>
–<无符号整数>::=<数字> | <数字><无符号整数>
–<小数>::=.<无符号整数>
–<数字>::=0|1|2|3|4|5|6|7|8|9
扩展BNF：
可选项：用“[]”表示，如
重复项：用“{}”表示重复0次或者多次，如<标识符>::=<字母>{<字母>|<数字>}
便于区分单个符号的终结符，加引号，如<语句序列>::=<语句> { “;” <语句> }
有时也用粗体字表示终结符，非终结符不加尖括号，可读性更好
语法图：
用方框表示非终结符，用圆表示终结符
用带箭头线表示连接关系和连接顺序
也注意看课件上例子
右图：十进制数的例子
正则语法和正则表达式：
S是有限集合，L?S*。则L是正则集合，
当且仅当对某个正则语法G，有L=L(G)
从正则语法G构造对应正则集合的正则表达式
主导图：将G的语法组合为一个大图，其中仅包含v0和终结符。图中终结符对应正则表达式中的终结符
?串联子图，对应子表达式α1α2
?并联子图，对应子表达式α1|α2
?回路子图，对应子表达式α*
有限状态机FSM：机器是一个系统，接受输入，改变自身的状态，产生输出。状态指为了完成机器的任务而对输入序列进行的归类，如果状态的数目有限，称为有限状态机
有限状态机FSM是一个五元组M(A,S,Y,s0,F)
–A:输入字符串的字母表
–S:机器的有限状态集合
–Y S:被称作“接受”的一些状态
–s0∈S:初始状态
–F:S×A→S：状态转移函数，指明在某个状态下接受输入字符所引起的状态变迁
状态图：状态图D=D(M)是带标记的有向图，
节点为状态，转移函数决定边的走向和标记
接受状态用双圈表示
如果F(sj,a)=sk，则从节点si做标记为a
的有向边到节点sk
初始状态s0用一个特殊的无源箭头标
识
有限状态机M决定的语言L：M所识别的A上的所有字符串。也就是确定拟路径P=(s0,a1,s1,a2,s2,…,am,sm)，如果sm∈Y则称M识别w
Kleen定理：字母表A上的形式语言L是正则的当且仅当存在一个有限状态机M使得L=L(M)
泵Pumping引理：长度超过状态数目的接受串w，都可以表示成w=xyz形式，而xy n z都会被M接受（鸽笼原理）
*应用：证明：L={a m b m:m>0}不是正则语言
–假设L是正则语言，则有有限状态机M接受L，假设M状态个数为k
–令w=a k b k，则一定有|w|>k，根据泵引理，w=xyz，其中y非空，而且xy2z也被M接受
–如果y仅含有a或仅含有b，那么xy2z中a,b的个数就不相等了，应该不属于L –如果y同时含有a和b那么y2中一定会出现a在b之后的情况，xy2z也应该不属于L
–两个矛盾说明假设错误，L不是正则语言
机器同余：是一个等价关系R
对于任意的s,t∈S，如果sRt，能导出对于任意的输入符号x∈A，都有F(x,s)RF(x,t)。即：
同一个等价类的状态对于任意的输入都转移到属于同一个等价类的状态。机器同余表现了状态之间的某种等效性
商机器：相对于有限状态机M(A,S,F)和M上的机器同余R。S’=S/R={[s]|s∈S}是S关于等价关系R的划分，F’={ <[s], [F(x,s)]> | s∈S,x∈A}。M’(A,S’,F’)称为M关于R的商机器M/R
机器化简：状态数目最少的机器为最简，通过构造机器同余及商机器来合并这些冗余状态，减少状态数目。
字符串相容的状态：s,t∈S，w∈A*，如果F(s,w)∈Y并且F(t,w)∈Y；或者F(s,w)?Y并且F(t,w)?Y，称s,t是关于w相容的
等价关系：S上的关系R，如果s,t∈S对于任何w∈A*都相容，则sRt，说明s,t其实是等效的状态
R是机器同余，M/R即M化简的结果
R的迭代算法：
S的初始划分P0={Y, Y~}
假设目前已有划分Pk={S1,S2,…Sm}，考察每个等价类Si，如果Si中的两个状态s,t在所有的输入x作用下都转移到同一个状态分块Aj（取决于x），则据此构造Si的进一步细分将所有Si的细分合在一起，成为新的划分Pk+1
如果Pk+1=Pk，算法停止，否则回到第2步
注意课件例子，有助理解
计算的实现：带输出的机器：
在有限状态机M(A,S,Y,s0,F)的基础上，去掉接受状态集合Y，增加
–输出字符的有限集合Z
–输出函数G:S×A→Z（在状态转移的同时，输出一个字符）
M的工作方式：输入字符串u=a1a2…a m印在一条输
入带上，机器M逐个读入输入带的字符，进行状态转
移V=s0s1s2…s m，同时在输出带上逐个打印输出字符
w=z1z2…z m
例：二进制加法有限状态机
有限状态机的局限：
不存在能作二进制乘法的有限状态机
计算机的内存有限，属于一种有限状态机
如果宇宙是有限的，理论上也是有限状态机
图灵机：（计算概论讲过）
基本结构
–一条分格的无限长的纸带，每格可容纳一个字符
–一个读写头，可以在纸带上移动，读出当前格子的字符，重写格子上的内容，改变自己的内部状态
–一系列关于读写头动作的规则（程序）
输入、计算和输出
–纸带上的内容（包括空白B）是计算前的输入和计算完成后的输出
–计算从读写头的初始状态s0、初始位置和输入的纸带格局开始
–按照规则进行读写头的移动、纸带字符的修改，直到进入停机状态（SH/SY/SN）
–在停机状态时纸带的内容就是输出
计算规则
规则q={si,ak,al,sj,d}，si,sj∈S（内部状态），ak,al∈A（纸带字符），d∈{L,R,N}（左移，右移，不动）。表示如果读写头当前状态为si，读到当前格子字符为ak，则：?改写格子内容为al
?转变状态为sj
?进行d指定的动作（读写头左移、右移或不动）
计算规则的限制
有限条规则
任意两条规则前两项不能相同（动作的确定性）
没有规则第一项是SH/SY/SN（保证这三个状态是停机状态）
形式语言与图灵机
当W?A*，将W中的任意字符串w作为输入，M都停止在接受状态SY，A-W的字符串M 停止在拒绝状态SN或者永不停机，称M接受/识别语言W=L(M)
形式语言L能被图灵机M识别，当且仅当L是一个0型形式语言
*图灵机例子：a m b m课件
识别与判定
识别：属于语言的串在有限步被接受，不属于语言的串被拒绝或者永不停机
枚举：枚举生成所有属于语言的串，对于无限集合语言，这个生成过程可能永不停止，可识别＝可枚举
判定：属于语言的串被接受，且不属于语言的串被拒绝（只有L和L的补语言都是图灵可识别的情况下，L才是图灵可判定的。）
存在语言是图灵机可识别但不可判定的
可计算函数：函数f:N→N是可计算的，如果存在一个图灵机M使得对每个自然数n停机，输出为f(n)
如果f,g都是可计算的，那么复合函数h=g°f也是可计算的
可计算函数＝递归函数
保证能停机并得到结果
原始递归函数包括了多数可形式化的计算
从0函数、后继函数、投影函数进行有限次的复合、原始递归
存在非原始递归的可计算函数
可计算函数?图灵可计算函数（存在图灵可计算但不是递归函数，和停机问题相关）
哥德尔编码：将任何形式语言L编码为自然数的集合（将语言上的运算变换为自然数的运算，形式系统的问题变换为数论问题）
哥德尔编码过程：
定义p(n)=第n个素数，n>0
L?A*，A={a1,a2,…an}，任意w={am1am2..amk}∈L，G(w)=∏i=1k p(i)mi
通用图灵机：能模拟任意图灵机的执行，对相应的输入得到相应的结果
图灵机的编码：
图灵机的定义包含有限字符集A、有限状态集S和读写头的运动规则
对图灵机的描述就是一个A∪S∪{L,R,N}上的字符串
将这个字符串进行哥德尔编码，得到哥德尔数G(M)
输入、输出的编码：
对图灵机的输入、输出是A上的字符串，也可以进行哥德尔编码
通用图灵机U存在：
接受两个输入整数a, k（a是图灵机的哥德尔数，k是图灵机输入的哥德尔数）
计算结果是M(a)在输入I(k)下的输出结果的哥德尔数G(o)
U所计算的函数是U(a,k)→N
有趣的是，U本身也可以进行哥德尔编码，作为输入参数在U中进行计算（可以产生能够自我复制的图灵机）
停机问题：是否有算法能够判定某个图灵机M在输入I下是否停机？答案是否定的，不存在这样的算法，停机问题是不可计算问题
哥德尔不完备定理：任何包含自然数定义的形式系统都是不完全的，也就是存在不能证明为真也不能证明为假的命题
重点是证明，一个开始于公理，结束于此命题的公理-定理有限序列
也就是，系统可能存在一些命题，它们是定理，却无法给出证明序列
可证明v.s. 计算停机
不可判定的命题v.s. 永不停机的计算
华南农业大学期末考试试卷（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
离散数学复习要点第一章命题逻辑 一、典型考查点 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．无
《离散数学》课程考试大纲 课程名称：离散数学 教学时数：56 考试对象： A08、C08计算机 一、考试内容及要求 1．考试范围： 命题演算及其形式系统、谓词演算及其形式系统、集合及其运算、关系、函数、群论、格和布尔代数。 2．考试要求： （一）命题演算及其形式系统 掌握命题的概念掌握命题公式的概念；熟练掌握利用求任意命题公式的析取范式、主析取范式、合取范式和主合取范式的方法。 （二）谓词演算及其形式系统 掌握两种量词及其用法；掌握谓词公式的定义；掌握基本的谓词演算的等价式和蕴涵式。 （三）集合及其运算 掌握集合的概念及表示法；理解两个集合相等的定义和充分必要条件；掌握子集、真子集、空集、全集、幂集的定义；熟练掌握集合的五种基本运算：并、交、补、差及其满足的性质。 （四）关系 掌握笛卡儿积的概念；深刻理解关系的两个定义；深刻理解关系的五种性质：自反、对称、传递、反对称和反自反；能够判断任给的关系具有哪些性质；熟练掌握关系的三种特殊运算：复合运算、逆运算和闭包运算；掌握二种特殊的关系：等价关系、序关系。 （五）函数 掌握函数的概念；特殊函数类；函数的合成；了解逆函数。 （六）群论 掌握代数系统的定义和有关基本概念；熟练掌握群的定义和群的性质；掌握子群及其陪集概念和性质；掌握同态与同构的概念和性质；熟练掌握群同态和同构的证明方法。 （七）格与布尔代数 掌握格和代数格的基本概念；掌握格的基本性质；掌握几种特殊格的基本概念和性质；能够判断分配格和有余格；利用格的概念和性质证明一些基本定理；熟练掌握布尔代数的基本概念和有关性质。 二、考试形式 闭卷考试
三、试卷结构 第一篇集合论约占25％ 第二篇数理逻辑约占30％ 第三篇群论15％ 第四篇格和布尔代数 30% 题型比例： 判断题30分占30%，命题的符号化表示18分占18%，改错题12分占12%，证明和应用题40分占40%。 四、说明 试题由任课教师出A、B卷随机抽取。
《离散数学》期末复习题 一、填空题（每空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、设
《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???.
2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
离散数学 一、逻辑和证明 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. 设︱A ︱=5, ︱P(B)︱=512, ︱P(A ∩B)︱=8, 则︱A ⊕B ︱＝ , ︱A ∪B ︱＝ 。 2. 设p :选小王当班长，q ：选小李当班长，则选小王或小李中的一人当班长可符号化为____。 3. 命题公式根据赋值可分为________________、________________和______________三类。 4. 含N 个个命题变项的命题公式有______________组赋值，有_____________个真值。 5. ()A A B ∨∧=______________，()A A B ∧∨=__________________。 6. 设{|3,,14}A x x k k N k ==∈≤≤，则用列举法表示A =________________________。 7. 集合A ={1，2}的幂集P (A )与A 的笛卡尔积()P A A ?=____________________________ ____________________________________________________________________________。 8. 某无向图G 中，共有边15条，该图中共有5度顶点2个，4度顶点3个，剩下的均为2度顶 点，则该图中共有顶点 个。 9. 一个结点为n 的无向完全图，其边的数目为 。 10．已知
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={
安徽大学20 09 — 20 10 学年第 1 学期 《离散数学（上）》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 题 号 一 二 三 四 五 总分 得 分 一、单选题（每小题2分，共20分） 1. 设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( ) A.R ∪I A B.R C.R ∪{〈c,a 〉} D.R ∩I A 2. 设X={a,b,c},I x 是X 上恒等关系，要使I x ∪{〈a,b 〉，〈b,c 〉，〈c,a 〉，〈b,a 〉}∪R 为X 上的等 价关系，R 应取( ) A. ｛〈c,a 〉，〈a,c 〉｝ B.{〈c,b 〉，〈b,a 〉} C. {〈c,a 〉，〈b,a 〉} D.{〈a,c 〉，〈c,b 〉} 3. 下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 4. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x 离散数学期末复习要点与重点 离散数学是中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的一门统设必修学位课程，共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．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算． 有序对就是有顺序二元组，如离散数学期末复习要点与重点
相关主题
文本预览