大连海事大学离散数学期末复习纲要教材

《大连海事大学离散数学期末复习纲要教材》由会员分享，可在线阅读，更多相关《大连海事大学离散数学期末复习纲要教材（46页珍藏版）》请在金锄头文库上搜索。

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

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

3、合的关系 （属于 ）、全集、空集、幂集、笛卡尔乘积 等概念。 (2)能熟练地证明集合中的相等关系、包含关系。 (3)掌握集合的五种基本运算： A、A B、A B、A-B、A B 及集合运算的基本定律。 第四章二元关系 (1)掌握关系矩阵和关系图的表示方法。 (2)掌握合成运算、逆运算、闭包运算的概 念。 (3)熟练掌握关系的性质（自反性、反自反 性、对称性、反对称性、可传递性）及其 判别方法。 第四章二元关系（续） (4)掌握等价关系（自反、对称、可传递） 和偏序关系（自反、反对称、可传递）的 概念及证明。 (5)掌握等价关系和划分之间的相互关系。 (6)掌握偏序关系和哈斯图，并会求极大（ 小

4、）元、最大（小）元、上（下）界、上 （下）确界。 第四章函数 一、主要内容 二、本章要点 一、主要内容 1、函数的基本概念 2、函数的性质质 3、特种函数 4、复合函数 5、逆函数 1、函数的基本概念 设f是从集合X到Y上关系，若对任意的xX都 存在唯一的yY，使f，则称关系f为函数 （或映射），记作：f: XY。 (1)对于函数f: XY，如果 x，y f，也写成 y=f(x), 并称x为自变量，y称为函数在x处的值 ，或称y为在函数f的作用下x的像点，相应地称x 为y的原像。 (2)对于函数f: XY，则称X为函数f的定义域， Y称为f的陪域；Rf是f的值域。 2、函数的性质质 设函数f:

5、 XY,则f满足下面两个性质 ： (1)任意性：函数的定义域必须是集合X，即 ：Df = X； (2)唯一性：对任意的xX，必存在唯一的 yY，使f，即： 对任意的xX，y，zY，有：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

6、、逆函数 如果f是个双射函数，则f的逆关系称为 f的逆函数（或反函数），并记作：f1。 相关定理 定理1 设函数f: AB，所有从A到B的函数 的集合 f | f: AB，记作BA，如果 |A|m, |B|=n,则|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、

7、掌握函数的定义（任意性、唯一性）: 设f是从集合X到Y的关系，即f:XY， 若对任意的xX都存在唯一的yY，使 f，或y=f(x)，则称关系f为函数（ 或映射） 注意：函数和关系的联系和区别。 本章要点（续） 2、掌握合成函数的概念： 设函数f: XY ,g: YZ,则: gf=|xXzZ(y)(yYy =f(x)z=g(y) 称为f和g的合成函数（复合函数）。 注意：合成关系和合成函数书写格式的区别。 本章要点（续） 3、掌握反函数的概念及其存在的条件： 设 f: XY是双射函数，则f的逆关系称 f的反函数，记作f-1 注意：只有双射函数才有反函数。 本章要点（续） 4、掌握特种函数的定义（

8、单射、满射、双 射）及证明： 滿射函数：设函数f: XY，若 f(X)=Rf=Y（值域陪域）。 单射函数：设函数f: XY，对任意x1 ，x2 X，如果： x1x2 f(x1)f(x2) 或 f(x1)=f(x2) x1=x2； 第五章代数结构 一、主要内容 二、本章要点 一、主要内容 1. 代数运算 2. 二元运算的性质 3二元运算的特异元 4. 可约的或可消去的 5. 代数系统的概念 6. 同态与同构的概念 7. 代换性质和同余关系 8. 商代数与积代数 9.半群和群 1. 代数运算 设X集合，f是从Xn X上映射，则称f为集合 X中的n元运算。特别是： (1)当n=1时，f：X X称为集

9、合X中的一元运算； (2)当n=2时，f：XX X称为集合X中的二元运 算。 如果对给对给 定的集合中的元素进进行运算，从而 产产生了像点，而该该像点又是该该集合中的元素， 则则称给给定的运算对该对该 集合封闭闭。在上述的代数 运算的定义义中蕴蕴含着对对集合的封闭闭性。 2. 二元运算的性质 设和*为集合X上的二元运算，与这些 运算相关的性质有： (1)交换律：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)逆元

10、(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)如果(0l)(0l X(x)(xX0l*x=0l)，则 称0l为集合X关于运算*的左零元； (2)如果(0r)(0r X(x)(xXx*0r=0r)，则 称0r为集合X关于运算*的右零元； (3)如果运算的左零

11、元和右零元同时存在，则必有 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. 可约的或可消去的 设设为为代数系统统，且aX，如果对对任 意的x，yX有： （a*x=a*y）（x*a=y*a）x = y 则则称a是可约约的或可消去的。 5. 代数系统 设X是

12、一个非空集合，为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) (运算的像=像的运算) 则称f是代数系统U到V同态映射(简称同态)，并称代数系 统U与V同态。 (1) 如果f是满射的，则称f 是从U到V

13、的满同态； (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对运算具有代换性 质，则称R是代数系统U中的同余关系。 8. 商代数与积代数 给定代数系统U=，其中是个二元 运算，R是U中的

14、同余关系。试构成一个新的代 数系统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）是代数系统； （2） “*”运算满足结合律； （3）中存在幺元e； （4）中任意一个

15、元素都有逆元素； 则称代数系统是群。 子群 设是一个群，H是A的非空子 集，若也是一个群，则称是的子群。 阿贝尔群和循环群 若群对运算“*”满足交换律，则 称是阿贝尔群（交换群）。 若群中每个元素均是它的某个 元素a的整数幂，则称是由a生成的 循环群。a称为的生成元素。 二、本章要点 (1)理解代数运算以及代数运算的性质（结 合律、交换律、分配律、等幂律、消去律 ）。 (2)掌握代数系统和子代数系统的定义，理 解运算的封闭性。 (3)给定集合和运算，会判别运算对该集合 是否封闭。 本章要点（续） (4)给给定二元运算，说说明运算是否满满足交换换 律、结结合律、等幂幂律、分配律和消去律。 (5)掌握和理解幺元、零元、逆元的概念,给 定个集合和该集合上的二元运算，会求 该运算的幺元、零元和逆元。 (6)掌握和理解同态、满同态、单一同态和 同构的概念和性质,并会求解（证）相关问 题。 (7)掌握半群、独异点、群、子群的概念及 相关的证明。 (8)理解阿贝尔群、循环群的概念。 本章要点（续） 第七章 图论要点 1、图的基本概念： （1）无向图、有向图、简单图、子图、真子图、生成子 图、完全图、正则图、零图、平凡图、加权图、补图、 图同构。 （2）邻接结点、邻接边； （3）无向图：度的概念； （4）有向图：出度、入