大连海事大学离散数学期末复习纲要课件

1、（1）需要熟练掌握的知识点包括：命题的定义、逻辑联结词、命题变元、命题公式（合式公式）、永真式、永假式、可满足式、等价式、蕴涵式、极小项、极大项、主析取范式、主合取范式。第1章命题逻辑重点（2）掌握基本的等价式和蕴涵式，并掌握常用的等价式和蕴涵式的证明方法（替换规则和推论规则）。第1章命题逻辑重点（续）（3）要能准确地求出命题公式的主析取范式和主合取范式。掌握主析取范式和主合取范式与真值表的对应关系，主析取范式和主合取范式的关系。第1章命题逻辑重点（续）（4）掌握命题符号化的原则；（5）熟练掌握四个推论规则（P、T、CP、F）进行有效性论证。第1章命题逻辑重点（续）第2章谓词逻辑重点（1）需要

2、熟练掌握的知识点包括：谓词、全称量词(x)、存在量词 (x) 、个体、个体域、个体变元（约束变元和自由变元）、谓词公式的解释（永真、永假、可满足）、谓词公式的基本的等价式和蕴涵式。第2章谓词逻辑重点（续）（2）在符号化时要特别注意量词和逻辑联结词的搭配：全称量词对应逻辑联结词“”，存在量词对应逻辑联结词“”。（3）在谓词逻辑推理的证明中，要特别注意US，ES，UG，EG规则成立的条件（用ES规则指定的个体不能用UG规则加以推广）。第三章集合(1)掌握集合的基本概念及其表示，集合之间的关系（子集 、真子集 ）、元素与集合的关系（属于 ）、全集、空集、幂集、笛卡尔乘积等概念。(2)能熟练地证明集合

3、中的相等关系、包含关系。(3)掌握集合的五种基本运算：A、A B、A B、A-B、A B及集合运算的基本定律。第四章二元关系(1)掌握关系矩阵和关系图的表示方法。(2)掌握合成运算、逆运算、闭包运算的概念。(3)熟练掌握关系的性质（自反性、反自反性、对称性、反对称性、可传递性）及其判别方法。第四章二元关系（续）(4)掌握等价关系（自反、对称、可传递）和偏序关系（自反、反对称、可传递）的概念及证明。(5)掌握等价关系和划分之间的相互关系。(6)掌握偏序关系和哈斯图，并会求极大（小）元、最大（小）元、上（下）界、上（下）确界。第四章函数一、主要内容二、本章要点一、主要内容1、函数的基本概念2、函数

4、的性质3、特种函数4、复合函数5、逆函数 1、函数的基本概念设f是从集合X到Y上关系，若对任意的xX都存在唯一的yY，使f，则称关系f为函数（或映射），记作：f: XY。(1)对于函数f: XY，如果x，yf，也写成y=f(x), 并称x为自变量，y称为函数在x处的值，或称y为在函数f的作用下x的像点，相应地称x为y的原像。(2)对于函数f: XY，则称X为函数f的定义域，Y称为f的陪域；Rf是f的值域。2、函数的性质设函数f: XY,则f满足下面两个性质：(1)任意性：函数的定义域必须是集合X，即：Df = X；(2)唯一性：对任意的xX，必存在唯一的yY，使f，即：对任意的xX，y，zY，

5、有：ff y = z。3、特种函数 设函数f: XY,则：(1)若f(X)=Rf=Y, 则称f是滿射的；(2)对任意x1,x2X，如果:x1x2f(x)f(y),或:f(x1)=f(x2)x1 =x2； 则称f是单射的；(3)若f是既是满射的，又是单射的，则称f是双射的。 4、复合函数给定函数f: XY，g: XZ，则：gf=xXzZ(y) (fg)则称gf为f和g的合成函数（或复合函数）。5、逆函数如果f是个双射函数，则f的逆关系称为f的逆函数（或反函数），并记作：f1。 相关定理定理1 设函数f: AB，所有从A到B的函数的集合 f | f: AB，记作BA，如果|A|m, |B|=n,则

6、|BA|nm 。 定理2 设函数f: XY，g: YZ，则复合函数gf是从XZ上的函数，并对任意的xX，都有：（gf）（x）= g (f (x) )。 相关定理（续）定理3 函数的复合运算是可结合的，即如果f、g和h都是函数，则有： （gf）h = g(fh) = gfh定理4 设函数f: XY，f的逆关系f 1是从YX上函数，当且仅当f是个双射函数。 二、本章要点1、掌握函数的定义（任意性、唯一性）:设f是从集合X到Y的关系，即f:XY，若对任意的xX都存在唯一的yY，使 f，或y=f(x)，则称关系f为函数（或映射）注意：函数和关系的联系和区别。本章要点（续）2、掌握合成函数的概念：设函数

7、f: XY ,g: YZ,则: gf=|xXzZ(y)(yYy=f(x)z=g(y)称为f和g的合成函数（复合函数）。注意：合成关系和合成函数书写格式的区别。本章要点（续）3、掌握反函数的概念及其存在的条件：设 f: XY是双射函数，则f的逆关系称f的反函数，记作f-1注意：只有双射函数才有反函数。本章要点（续）4、掌握特种函数的定义（单射、满射、双射）及证明：滿射函数：设函数f: XY，若f(X)=Rf=Y（值域陪域）。单射函数：设函数f: XY，对任意x1，x2X，如果： x1x2 f(x1)f(x2)或 f(x1)=f(x2) x1=x2；第五章代数结构一、主要内容二、本章要点一、主要内

8、容1. 代数运算2. 二元运算的性质 3二元运算的特异元 4. 可约的或可消去的 5. 代数系统的概念 6. 同态与同构的概念 7. 代换性质和同余关系8. 商代数与积代数9.半群和群1. 代数运算设X集合，f是从Xn X上映射，则称f为集合X中的n元运算。特别是：(1)当n=1时，f：X X称为集合X中的一元运算；(2)当n=2时，f：XX X称为集合X中的二元运算。如果对给定的集合中的元素进行运算，从而产生了像点，而该像点又是该集合中的元素，则称给定的运算对该集合封闭。在上述的代数运算的定义中蕴含着对集合的封闭性。2. 二元运算的性质设和*为集合X上的二元运算，与这些运算相关的性质有：(1

9、)交换律：x，y，有 xy=yx；(2)结合律：x,y,z，有:(xy)z=x(yz)；(3)等幂律：x有xx=x； (4)分配律：x,y,z有:x(y*z)=(xy)* (xz) 3二元运算的特异元(1)幺元(2)零元(3)逆元(1)幺元设*为上的二元运算，则:(1)如果(el)(elX(x)(xXel*x=x)，则称el为集合X关于运算*的左幺元；(2)如果(er)(erX(x)(xXx*er=x)，则称er为集合X关于运算*的右幺元；(3)如果运算的左幺元和右幺元同时存在，则必有el=er=e，使得对任意的xX，有:x*e=e*x=x并称e为运算*的幺元且幺元e是惟一的。(2)零元(1)

10、如果(0l)(0l X(x)(xX0l*x=0l)，则称0l为集合X关于运算*的左零元；(2)如果(0r)(0r X(x)(xXx*0r=0r)，则称0r为集合X关于运算*的右零元；(3)如果运算的左零元和右零元同时存在，则必有0l=0r=0，使得对任意的xX，有:x*0=0*x=0并称0为运算*的零元。(3)逆元 设*为上的二元运算，且X中对于运算存在幺元e。令xX。(1)如果(xl)(xlXxl*x=e)，则称xl是x的左逆元，并称x是左可逆的；(2)如果(xr)(xrXx*xr=e)，则称xr是x的右逆元，并称x是右可逆的；(3)如果元素x既是左可逆的，又是右可逆的，则称x是可逆的。4.

11、 可约的或可消去的 设为代数系统，且aX，如果对任意的x，yX有： （a*x=a*y）（x*a=y*a）x = y则称a是可约的或可消去的。5. 代数系统设X是一个非空集合，为X上的代数运算构成的非空集合，则称序偶为一个代数系统（或代数结构），其中：(1)集合X为代数系统的定义域。如果X是个有限集合，则称为有限代数系统，X=n为代数系统的阶；否则称为无限代数系统。(2)=1，2，n为X中的n元运算（n=1，2，3，）构成的集合，如果为有限集合，则可将表示为：。6. 同态与同构的概念设U，V是两个代数系统，和*是二元运算，函数f：XY，如果对任意的x，yX有: f(xy)=f(x)*f(y) (

12、运算的像=像的运算)则称f是代数系统U到V同态映射(简称同态)，并称代数系统U与V同态。(1) 如果f是满射的，则称f 是从U到V的满同态；(2) 如果f是单射的，则称f 是从U到V的单一同态；(3) 如果f是双射的，则称f 是从U到V的同构。(4) 如果U=V，则称f是从U到U的自同构。7. 代换性质和同余关系代换性质：给定代数系统，其中是个二元运算。设R是X中的等价关系，如果对任意的x1，x2X和y1，y2X有： (x1Rx2)(y1Ry2)(x1*y1)R(x2*y2)则称等价关系E对于运算具有代换性质。同余关系：给定代数系统U=，且R是集合X中的等价关系。如果等价关系R对运算具有代换性

13、质，则称R是代数系统U中的同余关系。8. 商代数与积代数给定代数系统U=，其中是个二元运算，R是U中的同余关系。试构成一个新的代数系统W=，其中(1)X/R=xR xX；(2)对任意的x1,x2X,有x1Rx2R=x1x2R则称代数系统W为U的商代数，简称商代数，并记作U/R。商代数与积代数（续）设U，V是代数系统，试构成一个新的代数系统：UV = 其中XY是X和Y的笛卡儿乘积，且运算的定义为：对任意的x1，x2X和y1，y2Y有,则称UV是U和V的积代数，U和V是UV的因子代数。9.半群和群半群：设是代数系统，*运算是S上的二元运算，若*运算是可结合的，则称为一个半群。群：（1）是代数系统；

14、（2） “*”运算满足结合律；（3）中存在幺元e；（4）中任意一个元素都有逆元素； 则称代数系统是群。子群设是一个群，H是A的非空子集，若也是一个群，则称是的子群。阿贝尔群和循环群若群对运算“*”满足交换律，则称是阿贝尔群（交换群）。若群中每个元素均是它的某个 元素a的整数幂，则称是由a生成的循环群。a称为的生成元素。二、本章要点(1)理解代数运算以及代数运算的性质（结合律、交换律、分配律、等幂律、消去律）。(2)掌握代数系统和子代数系统的定义，理解运算的封闭性。(3)给定集合和运算，会判别运算对该集合是否封闭。本章要点（续）(4)给定二元运算，说明运算是否满足交换律、结合律、等幂律、分配律和

15、消去律。 (5)掌握和理解幺元、零元、逆元的概念,给定个集合和该集合上的二元运算，会求该运算的幺元、零元和逆元。(6)掌握和理解同态、满同态、单一同态和同构的概念和性质,并会求解（证）相关问题。(7)掌握半群、独异点、群、子群的概念及相关的证明。(8)理解阿贝尔群、循环群的概念。本章要点（续）第七章图论要点1、图的基本概念：（1）无向图、有向图、简单图、子图、真子图、生成子图、完全图、正则图、零图、平凡图、加权图、补图、图同构。（2）邻接结点、邻接边；（3）无向图：度的概念；（4）有向图：出度、入度、度；（5）奇结点、偶结点；（6）任何一个(n,m)图，其度之和等于边数的两倍；（7）任何一个图G，度为奇数的结点个数一定为偶数个。图论要点（续）2、路径、回路和图的连通性：（1）路径（简单路径、基本路径），回路（简单回路、基本回路）；（2）可达的概念、连通图与非连通图、分支（极大连通子图）；（3）强连通图、单向连通图和弱连通图，强分支、单