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

大连海事大学离散数学期末复习纲要大连海事大学离散数学期末复习纲要大连海事大学离散数学期末复习纲要（2）掌握基本的等价式和蕴涵式，并掌握常用的等价式和蕴涵式的证明方法（替换规则和推论规则）。第1章命题逻辑重点（续）”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；大连海事大学离散数学期末复习纲要大连海事大学离散数学期末复习1（2）掌握基本的等价式和蕴涵式，并掌握常用的等价式和蕴涵式的证明方法（替换规则和推论规则）。第1章命题逻辑重点（续）（2）掌握基本的等价式和蕴涵式，并掌握常用的等价式和蕴涵式的2（3）要能准确地求出命题公式的主析取范式和主合取范式。掌握主析取范式和主合取范式与真值表的对应关系，主析取范式和主合取范式的关系。第1章命题逻辑重点（续）（3）要能准确地求出命题公式的主析取范式和主合取范式。掌握主3（4）掌握命题符号化的原则；（5）熟练掌握四个推论规则（P、T、CP、F）进行有效性论证。第1章命题逻辑重点（续）（4）掌握命题符号化的原则；第1章命题逻辑重点（续）4第2章 谓词逻辑重点（1）需要熟练掌握的知识点包括：谓词、全称量词(

x)、存在量词(

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

、真子集

）、元素与集合的关系（属于

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

一、主要内容1、函数的基本概念111、函数的基本概念

设f是从集合X到Y上关系，若对任意的x

X都存在唯一的y

Y，使<x，y>

f，则称关系f为函数（或映射），记作：f:X→Y。(1)对于函数f:X→Y，如果﹤x，y﹥

f，也写成y=f(x),

并称x为自变量，y称为函数在x处的值，或称y为在函数f的作用下x的像点，相应地称x为y的原像。(2)对于函数f:X→Y，则称X为函数f的定义域，Y称为f的陪域；Rf是f的值域。1、函数的基本概念 设f是从集合X到Y上关系，若对任意的x122、函数的性质

设函数f:X→Y,则f满足下面两个性质：(1)任意性：函数的定义域必须是集合X，即：Df=X；(2)唯一性：对任意的x

X，必存在唯一的y

Y，使<x，y>

f，即：对任意的x

X，y，z

Y，有：<x，y>

f∧<x，z>

f

y=z。2、函数的性质 设函数f:X→Y,则f满足下面两个性质：133、特种函数

设函数f:X→Y,则：(1)若f(X)=Rf=Y,则称f是滿射的；(2)对任意x1,x2

X，如果:x1≠x2

f(x)≠f(y),或:f(x1)=f(x2)

x1=x2；

则称f是单射的；(3)若f是既是满射的，又是单射的，则称f是双射的。

3、特种函数设函数f:X→Y,则：144、复合函数

给定函数f:X→Y，g:X→Z，则：gｏf=｛<x，z>│x

X∧z

Z∧(

y)(<x，y>f∧<y，z>g)｝则称gｏf为f和g的合成函数（或复合函数）。4、复合函数 给定函数f:X→Y，g:X→Z，则：155、逆函数

如果f是个双射函数，则f的逆关系称为f的逆函数（或反函数），并记作：f–1。

5、逆函数 如果f是个双射函数，则f的逆关系称为f的逆函数16相关定理定理1

设函数f:A→B，所有从A到B的函数的集合{f|f:A→B}，记作BA，如果|A|＝m,|B|=n,则|BA|＝nm。

定理2

设函数f:X→Y，g:Y→Z，则复合函数gｏf是从X→Z上的函数，并对任意的xX，都有：（gｏf）（x）=g(f(x))。

相关定理定理1设函数f:A→B，所有从A到B的函数的集合17相关定理（续）定理3

函数的复合运算是可结合的，即如果f、g和h都是函数，则有：

（gｏf）ｏh=gｏ(fｏh)=gｏfｏh定理4

设函数f:X→Y，f的逆关系f–1是从Y→X上函数，当且仅当f是个双射函数。

相关定理（续）定理3函数的复合运算是可结合的，即如果f、g18二、本章要点1、掌握函数的定义（任意性、唯一性）:

设f是从集合X到Y的关系，即f:X→Y，若对任意的x

X都存在唯一的y

Y，使<x，y>

f，或y=f(x)，则称关系f为函数（或映射）注意：函数和关系的联系和区别。二、本章要点1、掌握函数的定义（任意性、唯一性）:19本章要点（续）2、掌握合成函数的概念：设函数f:X→Y,g:Y→Z,则:g◦f={<x,z>|x∈X∧z∈Z∧(

y)(y∈Y∧y=f(x)∧z=g(y))}称为f和g的合成函数（复合函数）。注意：合成关系和合成函数书写格式的区别。本章要点（续）2、掌握合成函数的概念：20本章要点（续）3、掌握反函数的概念及其存在的条件： 设f:X→Y是双射函数，则f的逆关系称f的反函数，记作f-1注意：只有双射函数才有反函数。本章要点（续）3、掌握反函数的概念及其存在的条件：21本章要点（续）4、掌握特种函数的定义（单射、满射、双射）及证明：①滿射函数：设函数f:X→Y，若f(X)=Rf=Y（值域＝陪域）。 ②单射函数：设函数f:X→Y，对任意x1，x2

∈X，如果：x1≠x2

f(x1)≠f(x2)或f(x1)=f(x2)

x1=x2；本章要点（续）4、掌握特种函数的定义（单射、满射、双射）及证22第五章 代数结构一、主要内容二、本章要点第五章 代数结构一、主要内容23一、主要内容1.代数运算2.二元运算的性质3．二元运算的特异元4.可约的或可消去的5.代数系统的概念6.同态与同构的概念7.代换性质和同余关系8.商代数与积代数9.半群和群一、主要内容1.代数运算241.代数运算

设X集合，f是从Xn→X上映射，则称f为集合X中的n元运算。特别是：(1)当n=1时，f：X

→X称为集合X中的一元运算；(2)当n=2时，f：X×X

→X称为集合X中的二元运算。 如果对给定的集合中的元素进行运算，从而产生了像点，而该像点又是该集合中的元素，则称给定的运算对该集合封闭。在上述的代数运算的定义中蕴含着对集合的封闭性。1.代数运算 设X集合，f是从Xn→X上映射，则称f为252.二元运算的性质

设∘和*为集合X上的二元运算，与这些运算相关的性质有：(1)交换律：x，y

Ｘ，有x∘y=y∘x；(2)结合律：x,y,z

Ｘ，有:(x∘y)∘z=x∘(y∘z)；(3)等幂律：x

Ｘ有x∘x=x；

(4)分配律：x,y,z

Ｘ有:x∘(y*z)=(x∘y)*(x∘z)2.二元运算的性质 设∘和*为集合X上的二元运算，与这些263．二元运算的特异元(1)幺元(2)零元(3)逆元3．二元运算的特异元(1)幺元27(1)幺元设*为Ｘ上的二元运算，则:(1)如果(

el)(el

X∧(

x)(x

X→el*x=x))，则称el为集合X关于运算*的左幺元；(2)如果(

er)(er

X∧(

x)(x

X→x*er=x))，则称er为集合X关于运算*的右幺元；(3)如果运算的左幺元和右幺元同时存在，则必有el=er=e，使得对任意的x

X，有:x*e=e*x=x并称e为运算*的幺元且幺元e是惟一的。(1)幺元设*为Ｘ上的二元运算，则:28(2)零元(1)如果(

0l)(0l

X∧(

x)(x

X→0l*x=0l))，则称0l为集合X关于运算*的左零元；(2)如果(

0r)(0r

X∧(

x)(x

X→x*0r=0r))，则称0r为集合X关于运算*的右零元；

(3)如果运算的左零元和右零元同时存在，则必有0l=0r=0，使得对任意的x

X，有:x*0=0*x=0并称0为运算*的零元。(2)零元(1)如果(0l)(0lX∧(x)(xX29(3)逆元

设*为Ｘ上的二元运算，且X中对于运算存在幺元e。令x

X。(1)如果(

xl)(xl

X∧xl*x=e)，则称xl是x的左逆元，并称x是左可逆的；(2)如果(

xr)(xr

X∧x*xr=e)，则称xr是x的右逆元，并称x是右可逆的；(3)如果元素x既是左可逆的，又是右可逆的，则称x是可逆的。(3)逆元设*为Ｘ上的二元运算，且X中对于运算存在幺元e。304.可约的或可消去的

设<X,*>为代数系统，且a

X，如果对任意的x，y

X有：

（a*x=a*y）∨（x*a=y*a）

x=y则称a是可约的或可消去的。4.可约的或可消去的设<X,*>为代数系统，且aX，如315.代数系统

设X是一个非空集合，

为X上的代数运算构成的非空集合，则称序偶<X,

>为一个代数系统（或代数结构），其中：(1)集合X为代数系统<X,

>的定义域。如果X是个有限集合，则称<X,

>为有限代数系统，│X│=n为代数系统的阶；否则称<X,

>为无限代数系统。(2)

=

1，

2，…

n｝为X中的n元运算（n=1，2，3，…）构成的集合，如果

为有限集合，则可将<X,

>表示为：<X,

1，

2，…

n>。5.代数系统 设X是一个非空集合，为X上的代数运算构成326.同态与同构的概念设U＝<X，ｏ>，V＝<Y，*>是两个代数系统，ｏ和*是二元运算，函数f：X→Y，如果对任意的x，yX有:f(xｏy)=f(x)*f(y)(运算的像=像的运算)则称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的自同构。6.同态与同构的概念设U＝<X，ｏ>，V＝<Y，*>是两个337.代换性质和同余关系代换性质：给定代数系统<X，*>，其中是个二元运算。设R是X中的等价关系，如果对任意的x1，x2

X和y1，y2

X有：

(x1Rx2)∧(y1Ry2)

(x1*y1)R(x2*y2)则称等价关系E对于运算具有代换性质。同余关系：给定代数系统U=<X，*>，且R是集合X中的等价关系。如果等价关系R对运算具有代换性质，则称R是代数系统U中的同余关系。7.代换性质和同余关系代换性质：给定代数系统<X，*>，其348.商代数与积代数

给定代数系统U=<X，ｏ>，其中ｏ是个二元运算，R是U中的同余关系。试构成一个新的代数系统W=<X/R，

>，其中

(1)X/R=｛[x]R│x

X｝；

(2)对任意的x1,x2

X,有[x1]R

[x2]R=[x1ｏx2]R则称代数系统W为U的商代数，简称商代数，并记作U/R。8.商代数与积代数 给定代数系统U=<X，ｏ>，其中ｏ是35商代数与积代数（续）设U＝<X，ｏ>，V＝<Y，*>是代数系统，试构成一个新的代数系统：U×V=<X×Y，

>其中X×Y是X和Y的笛卡儿乘积，且运算

的定义为：对任意的x1，x2

X和y1，y2

Y有<<x1,y1>,<x2,y2>>＝<x1ｏx2，y1*y2>则称U×V是U和V的积代数，U和V是U×V的因子代数。商代数与积代数（续）设U＝<X，ｏ>，V＝<Y，*>是代数系369.半群和群半群：设<S,*>是代数系统，*运算是S上的二元运算，若*运算是可结合的，则称<S,*>为一个半群。群：（1）<S，*>是代数系统；（2）“*”运算满足结合律；（3）<A，*>中存在幺元e；（4）<A，*>中任意一个元素都有逆元素；则称代数系统<A，*>是群。9.半群和群半群：设<S,*>是代数系统，*运算是S上的二元37子群

设<A，*>是一个群，H是A的非空子集，若<H，*>也是一个群，则称<H，*>是<A，*>的子群。子群 设<A，*>是一个群，H是A的非空子集，若<H，*>38阿贝尔群和循环群

若群<A，*>对运算“*”满足交换律，则称<A，*>是阿贝尔群（交换群）。

若群<A，*>中每个元素均是它的某个元素a的整数幂，则称<A，*>是由a生成的循环群。a称为<A，*>的生成元素。阿贝尔群和循环群 若群<A，*>对运算“*”满足交换律，则39二、本章要点(1)理解代数运算以及代数运算的性质（结合律、交换律、分配律、等幂律、消去律）。(2)掌握代数系统和子代数系统的定义，理解运算的封闭性。(3)给定集合和运算，会判别运算对该集合是否封闭。二、本章