离散数学课本定义和定理Word文档下载推荐.docx

离散数学课本定义和定理Word文档下载推荐.docx

《离散数学课本定义和定理Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《离散数学课本定义和定理Word文档下载推荐.docx（20页珍藏版）》请在冰点文库上搜索。

2.1关系

定义2.1.1（序偶）：

若x和y是两个元，将它们按前后顺序排列，记为x,y，则y,x成为一个序偶。

※对于序偶x,y和a,b，当且仅当x=a并且y=b时，才称x,y和a,b相等，记为x,y=a,b

定义2.1.2（有序n元组）：

若x1,x2,…,xn是个元，将它们按前后顺序排列，记为x1,x2,…,xn，则成为一个有序n元组（简称n元组）。

定义2.1.3（直接积）：

A和B是两个集合，则所有序偶x,y的集合，称为和的直接积（或笛卡尔积），记为A×

B.

定义2.1.4（直接积）：

设A1,A2,…,An是n个集合，xi∈Ai,i=1,2,…,n，则所有n元组x1,x2,…,xn的集合，称为A1,A2,…,An的笛卡尔积（或直接积），记为A1×

A2×

…×

An.

定义2.1.5（二元关系）

若A和B是两个集合，则A×

B的任何子集都定义了一个二元关系，称为A×

B上的二元关系。

如果A=B，则称为A上的二元关系。

定义2.1.5（恒等关系）：

设Ix是X上的二元关系，Ix=x,x|x∈X，则称Ix是X上的恒等关系。

定义2.1.7（定义域、值域）：

若S是一个二元关系，则称

DS=x|存在y,使x,y∈S为S的定义域。

RS=y|存在x,使x,y∈S为S的值域。

定义2.1.8（自反）：

设R是集合上X的关系，若对于任何x∈X，都有xRx即x,x∈R则称R关系是自反的。

定义2.1.9（反自反）：

设R是集合上X的关系，若对于任何x∈X，都满足x,x∈R,即xRx对任何x∈X都不成立，则称关系R是反自反的。

定义2.1.10（对称）：

设R是集合上X的关系，若对于任何x,y∈X，只要xRy,就有yRx,那么称关系R是对称的。

定义2.1.11（反对称）：

设R是集合上X的关系，若对于任何x,y∈X，只要xRy并且yRx时,就有x=y，那么称关系R是对称的。

定义2.1.11（传递）设R是集合上X的关系，若对于任何x,y∈X，只要xRy并且yRz时，就有xRz，则称关系R是传递的。

定理2.1.1设R是集合上X的关系，若R是反自反的和传递的，则R是反对称的。

2.2关系矩阵和关系图

定义无定理无

2.3关系的运算

定义2.3.1（连接）：

设R为X×

Y上的关系，S为Y×

Z上的关系，则定义关系

R∘S=x,z|存在y,使x,y∈R且y,z∈S

R∘S称为关系R和S的连接或复合，有时也记为R∙S.

定义2.3.2（逆关系）：

Y上的关系，则定义R的逆关系为R-1为Y×

X上的关系：

R-1=y,x|y,x∈R.

定理2.3.1设R和S都是X×

Y上的二元关系，则下列各式成立

（1）R-1-1=R

（2）R∪S-1=R-1∪S-1

（3）R∩S-1=R-1∩S-1 （4）R'

-1=R-1'

（5）R-S-1=R-1-S-1

定理2.3.2 设R为X×

Z上的关系，则R∘S-1=S-1∘R-1

2.4闭包运算

定义2.4.1（自反闭包）：

设R是集合X上的二元关系，如果R1是包含R的最小自反关系，则称R1是关系R的自反闭包，记为rR.

定义2.4.2（对称闭包）：

设R是集合X上的二元关系，如果R1是包含R的最小对称关系，则称R1是关系R的对称闭包，记为sR.

定义2.4.3（传递闭包）：

设R是集合X上的二元关系，如果R1是包含R的最小传递关系，则称R1是关系R的传递闭包，记为tR或R+.

定理2.4.1设R是集合X上的二元关系，则

（1）R是自反的，当且仅当rR=R.

（2）R是对称的，当且仅当rR=R.

（3）R是传递的，当且仅当tR=R.

定理2.4.2设R是集合X上的二元关系，则rR=R∪Ix. “R∪恒等关系”

定理2.4.3设R是集合X上的二元关系，则sR=R∪R-1. “R∪逆关系”

定理2.4.4设R是集合X上的二元关系，则R+=R∪R2∪R3∪…=i=1∞Ri. “R∪幂集”

定理2.4.5设X是一个n元集，R是X上的二元关系，则存在一个正整数k≤n，使得

R+=R∪R2∪R3∪…Rk.

2.5等价关系和相容关系

定义2.5.1（覆盖、划分）：

S是一个集合，Ai⊆S,i=1,2,…,n,如果i=1nAi=S，则称a=A1,A2,…,An是S的一个覆盖。

如果i=1nAi=S，并且Ai∩Aji,j=1,2,…,n,i≠j，则称a是S的一个划分，a中的元称为S的划分块。

定义2.5.2（等价关系）：

设R是X上的一个关系，如果R具有自反性、对称性和传递性三个性质，则称R是一个等价关系。

设R是等价关系，若xRy成立，则称x等价于y.

定义2.5.3（等价类）：

设R是X上的一个等价关系，则对任何x∈X，令[x]R=y|y∈X且xRy，称[x]R为x关于R的等价类，简称为x的等价类，[x]R也可以简记为[x].

定义2.5.4（同余）：

对于整数a,b和正整数m,有关系式：

a=mk1+r10≤r1<

m

b=mk2+r20≤r2<

如果r1=r2，则称a,b对于模m同余的，记作a≡bmodm

定义2.5.5（商集）：

设R是X上的一个等价关系，由R引出的等价类组成的集合x|x∈X称为集合X上由关系R产生的商集，记为X/R. “等价类的集合”

定理2.5.1 若是X上的一个等价关系，则由R可以产生唯一的一个对X的划分。

“商集”

定义2.5.6（相容关系）：

设R是X上的一个关系，如果R是自反的和对称的，则称R是一个相容关系。

相容关系可以记为≈.

所有的等价关系都是相容关系，但相容关系却不一定是等价关系。

定义2.5.7（最大相容块）：

设X是一个集合，≈是定义在X上的相容关系。

如果A⊆X,A中的任何两个元都有关系≈，而x-A的每一个元都不能和A中所有元具有关系≈，则称A是X的一个最大相容块。

2.6偏序关系

定义2.6.1（偏序关系）：

R是定义在集合X上的一个关系，如果它具有自反性、反对称性和传递性，则称R是X上的一个偏序关系，简称为一个偏序，记为≼.更一般地讲，若X是一个集合，在X上定义了一个偏序≼，则我们用符号X,≼来表示它，并称X,≼是一个偏序集。

定义2.6.2（全序/链）：

X,≼是一个偏序集，对任何x,y∈X，如果x≼y或y≼x这两者中至少有一个必须成立，则称X,≼是一个全序集或链，而称≼是X上的一个全序或线性序。

定义2.6.3（盖住）：

X,≼是一个偏序集，x,y∈X，若x≺y，并且不存在z∈X,使x≺z并且z≺y，则称y盖住x. “紧挨着”

定义2.6.4（最小元、最大元）：

X,≼是一个偏序集，如果X中存在有元y，对任何x∈X都满足y≼x，则称y是X,≼的最小元。

如果X中存在有元z，对任何x∈X都满足x≼z，则称z是X,≼的最大元。

定义2.6.5（极小元、极大元）：

X,≼是一个偏序集，如果y∈X,而X中不存在元x，使x<

y,则称y是X,≼的极小元。

如果z∈X,而X中不存在元x,使z<

x,则称z是X,≼的极大元。

定义2.6.6（上界、下界、上确界、下确界）：

X,≼是一个偏序集，A⊆X,x,y∈X,如果对于所有的a∈A,都有a≼x,则称x是A的一个上界。

如果对于所有的a∈A,都有y≼a,则称y是A的一个下界。

如果x是A的一个上界，对于A的任一上界z,都有x≼z,则称x是A的最小上界（上确界）.如果y是A的一个上界，对于A的任一上界w,都有w≼y,则称y是A的最大下界（下确界）.

定义2.6.5（良序集）：

设X,≼是一个偏序集，对于偏序≼，如果X的每个非空子集都具有最小元，则称X,≼是一个良序集，而称≼是X上的一个良序。

每个良序集都是全序集。

第3章函数和运算

3.1函数

定义3.1.1（映射、象）：

关系f定义在X×

Y上，如果对于每一个x∈X，都有唯一的一个y∈Y，使x,y∈f，则称f是从X到Y的一个函数（或映射），记为f:

X⟶Y.x称为函数f的变元，y称为变元x在f下的值（或象），记为fx.

注意：

（1）定义域Df=X，而不是Df⊂X.

（2）每一个x，有唯一的y∈Y，使x,y∈f. 多值函数不符合定义

（3）值域Rf⊆Y.

定义3.1.2（受限、扩展）：

若f是从X到Y的一个函数，A⊆X，则f∩A×

Y也是一个函数，它定义于A到Y，我们称它是f在A上的受限。

如果f是函数g的一个受限，则称g是f的一个扩展。

★定义3.1.3（映上、映内、一对一、一一对应）：

若f:

X⟶Y，则f的值域Rf=Y时，称函数f是映上的（或满射）。

如果f的值域Rf⊂Y时，则称函数f是映内的。

如果x1,x2∈X,x1≠x2，则有fx1≠fx2,则称f是一对一的（单射）（即fx1=fx2时，有x1=x2）.

如果f映上的，又是一对一的，则称f是一一对应的（或双射）。

定义3.1.4（复合运算）：

若f:

X⟶Y,g:

Y⟶Z，则定义f和g的复合运算f∘g为：

f∘g=x,z|存在y∈Y,使y=fx,且z=gy即f∘gx=gfx.

注：

逆函数f-1若要存在需要满足以下条件：

（1）函数f是映上的

（2）函数f必须是一对一的

定义3.1.5（恒等函数）函数Ix=x,x|x∈X称为恒等函数。

定理3.1.1f:

Y⟶Z，则g=f-1的充分必要条件是g∘f=Iy，并且f∘g=Ix

3.2运算

定义3.2.1（二目运算）：

若X是一个集合，f是从X×

X到X的一个映射（函数），则称f为一个二目运算。

一般地，若f是从Xn到X的一个映射（n是正整数），则称f是一个n目运算。

运算的封闭：

运算的结果总是集合X中的一个元，因此这个定义保证了运算的施行，这种情况又称为集合X对于该种运算是封闭的。

定义3.2.2（可交换）：

X×

X⟶X是一个运算，对于任何x,y∈X，都有fx,y=fy,x，则称运算f是可交换的（或者说，f服从交换律）.

定义3.2.3（可结合）：

X⟶X是一个运算，对于任何x,y,z∈X,都有ffx,y,z=fx,fy,z，则称运算f是可结合的（或者说，f服从结合律）.

定义3.2.4（可分配）：

X⟶X是一个运算，g:

X⟶X是一个运算，对于任何x,y,z∈X，都有fx,gy,z=gfx,y,fx,z，则称运算f对于运算g是可分配的（或者说，f对于g服从分配律）

定义3.2.5（左单位元、右单位元）：

设*是X上的一个运算，如果X中存在有一个元el，对于任何x∈X，有el*x=x，则称el是运算*的左单位元；

如果X中存在有一个元er，对于任何x∈X，有x*er=x，则称er是运算*的右单位元。

定理3.2.1若*是X上的一个运算，el和er分别是它的左、右单位元，则el=er=e，并且e是唯一的（因此，称e为运算*的单位元）.

定义3.2.6（左零元、右零元）：

设*是X上的一个运算，如果X中存在有一个元Ol，对于任何x∈X，有Ol*x=Ol，则称Ol是运算*的左零元；

如果X中存在有一个元Or，对于任何x∈X，有x*Or=Or，则称Or是运算*的右零元.

定义3.2.7（等幂）：

若*是X上的一个运算，a∈X，对于运算*，有a*a=a，则称元a对于运算*是等幂的。

定义3.2.8（左逆元、右逆元）：

若*是X上的一个运算，它具有单位元e，对于任何一个a∈X,如果存在有元xl∈X，使xl*a=e，则称xl是a的左逆元；

如果存在有元xr∈X，使a*xl=e，则称xr是a的右逆元；

定理3.2.3若*是X上的一个运算，它具有单位元e，并且是可结合的，则当元a可逆时，它的左、右逆元相等，并且唯一的（此时称之为a的逆元，并且记为a-1）.

定义3.2.9（可消去）：

若*是X上的一个运算，对于任何x,y∈X，如果元a满足：

a*x=a*y则x=y；

或x*a=y*a则x=y，则称元a对于运算*是可消去的。

第4章无限集合

4.1基数

★定义4.1.1（等势）：

若A和B是两个集合，如果在A和B之间可以建立一个一一对应关系，则称集合A和B等势，并记为A~B。

定理4.1.1令α是由若干个集合为元所组成的集合，则α上定义的等势关系是一个等价关系。

定义4.1.2（有限集、无限集）：

若A是一个集合，它和某个自然数集Mn=0,1,2,…,n等势，则称A是一有限集，不是有限集的集合称为无限集。

定理4.1.2有限集的任何子集都是有限集

定理4.1.3有限集不与其任何真子集等势

定理4.1.4自然数集N=0,1,2,…是无限集

4.2可列集

定义4.2.1（可列集）：

若A是一个集合，它和所有自然数的集合N等势，则称A是一个可列集。

可列集的基数用符号ℵ0表示。

定理4.2.1若A是一个集合，A可列的充分必要条件是可以将它的元排列为a1,a2,…,an,…的序列形式。

定理4.2.2任何无限集必包含有可列子集。

定理4.2.3可列集的子集是有限集或可列集（记为：

ℵ0-n≤ℵ0）

定理4.2.4若A是可列集，B是有限集，并且A∩B=∅，则A∪B是可列集（记为：

ℵ0+n=ℵ0）.

定理4.2.5若A和B都是可列集，并且A∩B=∅，则A∪B是可列集（记为：

ℵ0+ℵ0=ℵ0）

推论4.2.1设Aii=1,2,…,n都是可列集，则i=1nAi是可列集（记为：

n∙ℵ0=ℵ0）

定理4.2.6设Aii=1,2,…,n都是可列集，并且Ai∩Aj=∅i≠j,i,j=1,2,…，则i=1∞Ai是可列集（记为：

ℵ0∙ℵ0=ℵ0）

推论4.2.1设Aii=1,2,…,n都是可列集，则i=1∞Ai是可列集.

定理4.2.7所有有理数的集合是可列集。

4.3不可列集

定理4.3.1区间0,1中所有实数构成的集合是不可列的。

定义4.3.1（连续基数）：

开区间0,1中所有数组成集合的基数记为ℵ，具有基数ℵ的集合称为连续统，ℵ称为连续基数。

推论：

集合0,1的基数也是ℵ.

定理4.3.2所有实数的集合是不可列的，它的基数是ℵ.

定理4.3.3对于任何数a,b，若a<

b，则区间a,b,a,b,a,b],a,b）以及0,∞,0,∞）都具有连续基数ℵ

定理4.3.4一个无限集A和一个可列集作并集时，并集的基数等于集A的基数。

推论4.3.2一个无限集A和一个有限集的并集，其基数等于集A的基数。

4.4基数的比较

定义4.4.1（α<

β）设集合A的基数是α=β.如果A与B的真子集等势，而A和B不等势，则称A的基数小于B的基数，记为α<

β.

定理4.4.1：

A,B是两个集合，若A与B的某一子集等势，B与A的某一子集等势，则A~B.

定理4.4.2：

A,B是任意两个集合，A的基数为α,B的基数为β，则下列三个关系：

α=β,α<

β,α>

β中必有一个且只有个成立。

定理4.4.3：

若n是有限集A的基数，则n<

ℵ0<

ℵ.

定理4.4.4：

若A是无限集合，则ℵ0≤CardA

定理4.4.5：

若A1,A2,…,An,…是可列个互不相交的集合，它们的基数都是ℵ，则n=1∞An的基数是ℵ（记为：

ℵ0∙ℵ=ℵ）

定理4.4.6：

可列集的幂集，其基数是ℵ（记为：

2ℵ0=ℵ）

定理4.4.7：

若A是一个集合，B=ρA是A的幂集，则CardA<

CardB.

此定理说明：

不存在最大的基数。

补充：

2ℵ>

ℵ,ℵℵ>

ℵ

第5章形式语言

5.1文法和语言

定义5.1.1（产生式）：

一个产生式或重写规则是一个有序对U,x，通常写成U→x,其中，U是一个符号，而x是一个符号的非空有限串，U是这个产生式的左部，而x是产生式的右部.产生式将简称为规则。

定义5.1.2（非终极符号、字母表、终极符号、开始符号）：

一个文法G是一个四元组VN,VT,P,S.其中，VN是元语言的语法类或变元的集合，它生成语言的串，这些语法类或变元成为非终极符号，VT是符号的非空有穷集合，称为字母表，VT的符号称为终极符号.S是VN之一，是词汇表的一个识别元素，称为开始符号.P是产生式的集合。

定义5.1.3（直接产生、直接推导，直接规约）：

设G是一个文法，如果V=xUy,w=xuy，而G中有规则U→u，就称串V直接产生串w，或称w是V直接推导出来的，或w直接规约到V,记为V⇒w.

定义5.1.4（产生、规约到、推导）：

设G是一个文法，如果存在产生式序列P1,P2,…,Pnn>

0,使得V→P1→P2→…→Pn-1→Pn，而Pn=w,就说V产生w（w规约到V,或w是V的推导），记为V⇒+w.

定义5.1.5（句型）：

令G是一个文法，如果串x可从开始符号S推导出来，即如果S⇒*x，则x称为一个句型。

若Σ=a,b，则Σ*=∧,a,b,aa,ab,ba,bb,aaa,…,其中∧是空串，Σ+=a,b,aa,ab,ba,bb,aaa,…（不含空串）

5.2文法的类型

定义5.2.1（0-型文法）：

在Σ上的0-型文法由以下组成：

（1）不在Σ中的不同符号的非空集合V,称为变量表，它包含一个纲符号S,S称为开始变量。

（2）产生式的有限集合。

由G产生的所有字集称为由G产生的语言。

定义5.2.2（0-型语言）：

在Σ上可由某一0-型文法产生的字集称为0-型语言。

定义5.2.3（1-型文法）：

如果在0-型文法中，对于P中的每个产生式α→β，要求α≤β,则这文法称为1-型文法或上下文敏感文法.

定义5.2.4（2-型文法）：

设文法G=VN,VT,P,S,对于P中的每一个产生式α→β有α≤β且α∈VN（有的人要求β≠ε），则此文法叫2-型文法或前后文无关文法。

定义5.2.5（3-型文法）：

设G=VN,VT,P,S为一文法，又设P中的每一个产生式都是A→aB或A→a，其中A和B都是变量，而a为终极符号，而此文法为3-型文法或正规文法。

第1章代数系统

1.1代数系统的实例和一般性质

定义1.1.1（代数系统）：

若X,θ是序偶，X是一个非空集合，θ是定义在X上的某些运算的非空集合，则称X,θ是一个代数系统，或称代数。

代数系统的类型：

（1）代数系统X,σ1,σ2,…,σm的类型是n1,n2,…,nm，其中σ1,σ2,…,σm代表1,2,…,m目运算符。

（2）X,σ1,σ2,σ3，分别为0,1,2目运算符，则X,σ1,σ2,σ3的类型为0,1,2.

1.2同态和同构

定义1.2.1（同态象、同态映射）:

X,θ1和Y,θ2是两个同类型的代数系统，映射g:

X→Y,θ1和θ2也构成一一对应.如果对于任意n目运算σ1∈θ1，及其对应的运算σ2∈θ2，当x1,x2,…,xn∈X时，都有gσ1x1,x2,…,xn=σ2gx1,gx2,…,gxn,则称代数Y,θ2是X,θ1的同态象，称g是从X,θ1到Y,θ2的一个同态映射。

定义1.2.2（同态象、同态映射）：

若X,∘和Y,*是两个同类型的代数系统，∘和*都是二目运算，映射g:

X→Y.如果对于任何x,y∈X,都有gx∘y=gx*gy，则称Y,*是X,∘的一个同态象，称g是从X,∘到Y,*的一个同态映射。

如果Y,*就是X,∘，则映射g是从X到它自身。

当上述条件仍然满足时，我们就称g是X,∘的一个自同态映射。

定义1.2.3（同构、同构映射、自同构映射）：

如果X,∘和Y,*是同态的，映射g:

X→Y不仅是同态映射，而且是一一对应的，则称Y,*和X,∘同构，称g是从X,∘到Y,*的一个同构映射。

如果Y,*就是X,∘，则称g是X,∘上的一个自同构映射

定义1.2.4（同余关系）：

设Z,∘是一个代数系统，~是Z上的一个等价关系，如果存在x1,x2,x3,x4∈Z,当x1,x2,x3,x4∈~时，x1∘x3,x2∘x4∈～成立，则称～是Z,∘上的一个同余关系。

定理1.2.1：

设～是Z上的一个等价关系，如果存在同态映射g:

Z,∘→Y,*,使得当x1,x2∈Z时，x1~x2当且仅当gx1=gx2，则～是Z,∘上的同余关系。

1.3商代数与积代数

定义1.3.1（子代数）：

设Z,∘是一个代数系统，Z1⊆Z在运算∘下封闭的，则称Z1,∘是Z,∘

的一个子代数。

定义1.3.2（直接积）：

设Z,∘到Y,*是两个同类型的代数系统，如果对任意的x1,x2∈Z和y1,y2∈Y，定义运算⨁于Z×

Y:

x1,y2⨁x2,y2=x1∘x2,y1*y2，称Z×

Y,⨁是Z,∘和Y,*的直接积，称Z,∘和Y,*为Z×

Y,⨁的因子。

第2章半群和群

2.1半群和有幺半群

定义2.1.1（半群、有幺半群）：

S是一个非空集合，如果S中定义了一个二目运算⋅，对于任何a,b,c∈S,都有a∙b∙c=a∙b∙c，则称S,∙是一个半群.如果半群S,∙中具有单位元e，使得对任何x∈S,都有e∙x=x∙e=x,则称S,∙是一个有幺半群。

（1）Σ是一个由有限个符号组成的集合，其中的元称为字母。

Σ*表示所有的字构成的集合，Σ+表示非空串组成的集合。

（2）自由半群：

半群的各元相互间没有任何关系。

Σ*,∘

说明：

半群是一个定义了二目运算，并且服从结合律的代数系统。

有幺半群则是具有单位元的半群。

2.2群和循环群

定义2.2.1（群）：

在代数系统G,*中，如果二目运算*满足

（1）对于任何a,b,c∈G,有a*b*c=a*b*c；

（2）G中存在单位元e，对任何a∈G,有a*e=e*a=a；

（3）对于任何a∈G，存在有逆元a-1∈G,使a*a-1=a-1*a=e