《离散数学ppt.ppt》由会员分享，可在线阅读，更多相关《离散数学ppt.ppt（126页珍藏版）》请在课桌文档上搜索。
1、离散数学,第一章 命题逻辑什么是逻辑学：逻辑学是一门研究思维形式及思维规律的科学。逻辑学的分类：辩证逻辑与形式逻辑。其中，辩证逻辑是以辩证法认识论的世界观为基础的逻辑学；形式逻辑主要是对人的思维形式结构和规律进行研究的类似于语法的一门工具性,学科。思维的形式结构主要包括概念、判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是判断。由一个或几个判断推出另一判断的思维形式就是推理。研究推理有很多方法，用数学的方法研究推理的规律称为数理逻辑。所谓的数学方法就是引进一套符号体系的方法，所以数理逻辑又称符号逻辑，它是从量的方面来研究思维规律的
2、。,现代数理逻辑分为证明论、模型论、递归函数论、公理化集合论等。在此我们介绍的是数理逻辑最基本的内容：命题逻辑和谓词逻辑。,第一节 命题与命题联结词什么是命题：能够判断真假的陈述语句。命题的真值：真（T或1)和假（F或0）命题的种类：简单命题（原子命题）与复合命题命题的表示：大写或小写英文字母或带下标的英文字母。表示命题的字母称为命题标识符。命题常量与命题变元：表示确定命题的标识符成为命题常量；仅仅表示命题的的位置标志的标识符称为命题变元。,注意：命题常量具有确定的真值；而命题变元可以标识任意命题，它不能确定真值，它本身也不是命题。常用的命题联结词1、否定定义：设P为一命题，P的否定是一个新的
3、命题，记为P。若P为T，P为F，若P为F，P为T。2、合取定义：设P、Q是两个命题，P与Q的合取是一个复合命题，记为PQ。当且仅当P，Q,P、Q同时为T时，PQ为T，否则PQ为F。注：合取类似于自然语言中的“与”，“且”等，但又不完全相同。合取是一个二元运算。3、析取定义：设P、Q是两个命题，P与Q的析取是一个复合命题，记为PQ。当且仅当P，Q同为F时，PQ为F，否则PQ为T。注：析取类似于自然语言中的“或”但也不完全一样。自然语言中的“或”分为二种，即：“排斥或”与“可兼或”。而析取表示的是自然语言中的“可兼或”,析取是二元运算。4、条件定义：给定两个命题P、Q，它们的条件命题是一个复合命题
4、，记为PQ。当且仅当P为T，Q为F时，PQ为F，否则PQ为T.注：在PQ中P成为前件，Q称为后件。条件联结词与自然语言中的“如果那么”类似，但也不尽相同。善意的推断,二元运算5、双条件定义：给定两个命题P、Q，它们的双条件命题是一个复合命题，记为PQ。当且仅当P、Q的真值相同时，PQ为T，否则PQ为F.注：双条件联结词与自然语言中的“当且仅当”，“充分必要”类似，但也不尽相同。二元运算,命题联结词除了上述五个之外，还有不可兼析取、条件否定、与非、或非联结词。在一个复合命题中往往含有多个命题联结词，其运算的次序是：、第二节 命题公式及其分类直观地说，由命题变元、命题常量、命题联结词、括号组成的一
5、个有意义的式子成为命题公式。,定义：命题常量、命题变元是命题公式如果A是命题公式，则A是命题公式如果A、B是命题公式，则AB、AB、AB、AB也是命题公式只有有限次地应用 产生的符号串才是命题公式。命题公式的赋值：命题公式的分类：重言式、矛盾式、可满足式,第三节 等值演算等值的概念：设A，B是两个命题公式，p1，p2，pn为出现在A，B中的所有的命题变元，如果对p1，p2，pn的任何一种真值指派，A，B的真值都相同，则称A，B是等价（或等值）的。记为AB验证命题公式等值常用的方法有：真值表法、蕴含法、公式法（直接证法）。1、真值表法：例：证明AB(AB)(BA),2、蕴含法：定理1：设A，B是
6、两个命题公式，则AB当且仅当AB为永真式。蕴含的定义：定义2：如果AB为永真式，则称A蕴含B，记为AB蕴含常见的性质：1、自反性 2、传递性 3、如果AB，AC，则ABC 4、如果AC，BC，则ABC,由前面的例子和定理1我们马上可以得到定理2：AB当且仅当AB，BA分析蕴含的验证方法例1：证明：Q(PQ)P例2：证明：(P Q)P Q3、公式法常用的等值演算公式有24个。置换规则子公式：如果X是命题公式A的一部分，且X本身也是一个命题公式，则称X是命题公式A的子公式。定理：（置换规则）设X是命题公式A的子公式，,如果X Y，则将A中的X用Y置换所得到的命题公式B与A等价。例题：1、证明：(P
7、Q)(P Q)P2、证明：(PQ)(Q R)(P Q)R对偶式：对偶的概念：对偶定理：设A，B是命题公式，如果A B，则A*B*,第四节 主析取范式与主合取范式命题公式的规范化1、命题联结的归约：最小命题联结词组2、命题范式定义1：一个命题公式称为合取范式，如果它具有如下形式：A1 A2 An，其中A1，A2，An都是由命题变元或其否定所组成的析取式。定义1：一个命题公式称为析取范式，如果它具有如下形式：A1 A2 An，其中A1，,A2，An都是由命题变元或其否定所组成的合取式。求一个命题公式的析取或合取范式的步骤：化归：将命题公式中的联结词化归为，移非：利用狄.摩根律，将求非符号移到命题变
8、元的前面。归约：利用分配律将之化为析取或合取范式。,例子：1、(pq)r)p2、（p q)(p q)注：一个命题公式的析取或合取范式并不是唯一的。主析取范式与主合取范式定义：n个命题变元的合取式，称为布尔小项或合取，如果每个命题变元或其否定不能同时出现，但二者必须出现且仅出现一个。注：n个命题变元构成的布尔小项有2n个布尔小项的编码：命题变元-1，其否定-0,布尔小项的常见性质：1、每个小项当其真值指派与编码相同时，其真值为1，在其余2n-1中指派情况下均为0。2、任意两个不同的小项合取式为0。3、全体小项的析取式为1。定义：对于给定的命题公式，如果有一个等价公式，它仅有小项的析取所组成，则该
9、等价式称为原式的主析取范式。定理：在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式,的主析取范式。证明：略命题公式的主析取范式的求法1、真值表法例1：求命题公式PQ，P Q，(PQ)的主析取范式。求命题公式(PQ)(P R)(Q R)的主析取范式2、公式法,基本步骤：1、化归为析取范式2、合并同类同类项，去掉永假项。3、对合取项补入没有出现的命题变元，即添加PP项，然后利用分配律展开公式。例子：求P(P Q)(Q P)的主析取范式。注：对于一个命题公式的主析取范式，如将其命题变元的个数及出现次序固定后，则此公式的主析取范式是唯一的。,类似于主析取范式，也有主合取范式。定义：n
10、个命题变元的析取式，称为布尔大项或析取，如果每个命题变元或其否定不能同时出现，但二者必须出现且仅出现一个。注：n个命题变元构成的布尔 大项有2n个布尔大项的编码：命题变元-0，其否定-1布尔大项的常见性质：1、每个大项当其真值指派与编码相同时，,其真值为0，在其余2n-1中指派情况下均为1。2、任意两个不同的大项析取式为1。3、全体大项的合取式为0。定义：对于给定的命题公式，如果有一个等价公式，它仅有大项的合取所组成，则该等价式称为原式的主合取范式。定理：在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。,证明：略求一个命题公式的主和取范式的方法，也有真值表法与公
11、式法。其中公式法也分为三个步骤：1、化归为合取范式2、合并同类项，去掉永真项。3、对析取项补入没有出现的命题变元，即添加PP项，然后利用分配律展开公式。,例子：1、求(PQ)(P R)的主合取范式。2、求(P Q)R的主合取范式。第五节 命题逻辑的推理理论定义：设A,C是两个命题公式，如A C为一重言式，即AC，则称C是A的有效结论，或C可以由A逻辑推出。注：通常情况下，前提可能有若干个，即：H1 H2 Hn C从定义可以看到，推理正确并不能保证结论为真，这与现实中的推理有所不同。,如何验证命题逻辑的推理，通常有以下三种方法：真值表法、直接证法、间接证法（反证法）。1、真值表法：分析验证的方法
12、例：一份统计表的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表的错误不是由于材料不可靠，所以这份统计表是由于计算有错误。,2、直接证法直接证法就是由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效结论。在推演的过程中，还需要用到以下两个规则：P规则：前提的推导过程中的任何时候都可以引入使用。T规则：在推导中，如果有一个或多个公式、重言蕴含着公式S，则公式S可以引入推导中。,例：证明：(P Q)(P R)(Q S)S R证明(W R)V,V C S,S U,C U W3、间接证法反证法欲证H1 H2 Hn C，将 C作为一个前提加以引用，推出一个矛盾式。,例：
13、证明AB,(BC)A证明：PQ,PR,QSSRCP规则：欲证H1H2Hn(RC),可以将R作为一个逻辑前提加以引用，证明C为真即可。（分析理由）例子：证明:A(BC),DA,BDC证明：AB,CBAC应用简介,第二章谓词逻辑为什么要引入谓词逻辑：第一节谓词的概念与表示在一个简单命题中，表示主语的词称为客体或个体，表示谓语的词称为谓词。通常客体是可以独立存在的对象，它可以是一个具体的事物，也可以是抽象的概念。谓词一般是用来刻划个体的性质或个体之间的关系。,对个体我们通常用小写字母表示，而谓词我们则用大写字母表示。一个命题我们就可以用A(b)这种形式来表示，叫做谓词填式。用来表示特定个体的小写字母
14、我们将之称为个体常量，用来表示某一些个体的小写字母称为个体变量。一个个体变量的取值范围叫做个体域或论域。将考虑的所有的事物组成的个体域，称为全总个体域。,从前面我们可以看到，在一个谓词填式中可以含有个体变元。定义：有一个谓词，若干个个体变元组成的表达式，称为命题函数或谓词变项。注：、在一个谓词变项中，根据其所含变量的个数，有一元谓词,，n元谓词。其中0元谓词是命题。、在谓词变项中，如果含有变元，则它不是命题，只有对其中的变元都取特定的个体时，它才表示确定的命题。,量词使用上述概念有时还不能用符号很好地表达日常生活中的各种命题，例如：S(x)表示x是大学生，x的个体域是某单位职工。则可以理解为某
15、单位的职工都是大学生，或某单位的有些职工是大学生。为避免这种理解上的混乱，我们引入量词，以刻划“所有”、“有一些”的不同概念。、全称量词用来表达“所有的”,“每一个”，“任一个”等,的量词。例子：所有人都要呼吸：(x)M(x)H(x)每个学生都要参加考试：(x)P(x)Q(x)2、存在量词 用以表示“有一些”，“至少有一个”等概念的量词。例子：有些人是聪明的：,有的人早饭吃面包：全称量词与存在量词统称为量词。在上面的例子中，每个由量词确定的表达式，都与个体域有关。我们通常总是在全总个体域中考虑问题，因此就要通过相应的谓词对个体变元的取值范围加以说明，这就是特性谓词。一般地，对全称量词，特性谓词
16、常做蕴含的前件；对存在量词，特性谓词常作合取项。,第二节 谓词公式及解释由一个或多个命题函数以及联结词构成的表达式，称为复合命题函数。直观地讲，由命题、命题变元、命题函数、联结词、量词及括号构成的有意义的符号串称为谓词公式。定义：命题、命题变元、命题函数是谓词公式如A是谓词公式，则A是命题公式,如A,B是谓词公式，则AB,AB,AB,AB是谓词公式如A是谓词公式，则(x)A,(x)A也是谓词公式，其中x是A中的个体变元。只有有限次地利用所产生的符号串才是谓词公式。约束变元及其辖域（作用域）：约束变元的更名规则：对约束变元可以更名，其更改的变元名,称范围是量词中的指导变元，以及该量词作用域中所出
17、现的该变元，在公式的其余部分不变。更名时一定要更改为作用域中没有出现的变元名称。例如：对(x)(P(x)R(x,y)Q(x,y)自由变元的代入规则：对谓词公式中的自由变元可以代入，代入时需对公式中出现该自由变元的每一处进行。,用以代入的变元与原公式中的所有变元的名称不能相同。注：量词的次序不能颠倒，否则将与原命题意义不符。通常在一个谓词公式中会出现各种变项，如果用指定的常项代替变项，就构成了对谓词公式的解释。一个谓词公式的解释，由四个部分组成：非空个体域DD中一部分特定元素,D上一些特定的函数D上一些特定的谓词例：给定解释I如下：D=2,3 D中特定元素a=2函数f(x),其中f(2)=3,f
18、(3)=2谓词变项F(x)为：F(2)=0,F(3)=1G(x,y)为：G(i,j)=1 i,j=2,3L(x,y)为：L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0在解释I下，求下列谓词公式的真值(x)（F(x)G(x,a)(x)(F(f(x)G(x,f(x)（x)(y)L(x,y)第三节谓词公式的等值式定义：设A,B为谓词公式，如对任意一种解释，A,B的真值都相同，则称A,B是等值的。,定义：给定谓词公式A,如对任何一种解释，A的真值都为真，则称A为永真的。如对任何一种解释，A的真值都为假，则称A为永假的。如至少有一种解释，使得A的真值为真，则称A为可满足的。命题公式的推广
19、：命题公式的等价公式和蕴含式均可推广到谓词演算中来。例如：（x)（P(x)Q(x)（x)(P(x)Q(x)等量词与联结词之间的关系：,例：设P(x)表示x今天来校上课，P(x)表示x今天没来校上课。比较可以得到：（x)P(x)(x)P(x)（x)P(x)(x)P(x)量词作用域的扩张与收缩：（x)(A(x)B)（x)(A(x)B（x)(A(x)B)（x)(A(x)B（x)(A(x)B)（x)(A(x)B（x)(A(x)B)（x)(A(x)B,量词与命题联结词之间的一些等价式：（x)(A(x)B(x)(x)(A(x)x)B(x)（x)(A(x)B(x)x)(A(x)（x)B(x)前束范式定义：一
20、个谓词公式如果量词均在全式的开头,它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式。基本形式：定理：任意一个谓词公式，均和一个前束范式等价。,例子第四节 谓词演算的推理理论常用的等值式以及牵涉到量词推理规则例子：略,第三章 集合、关系、映射第一节 集合的基本概念集合的定义：若干个确定事物的全体。注：若干个：可以是有限也可以是无限。组成集合的事物成为集合的元素。元素的确定性：集合的表示：常用集合的习惯表示法：,子集与幂集：第二节 集合的基本运算交、并、补、差、对称差。第三节 笛卡尔积与关系序偶：有序偶与无序偶定义：设A,B是两个集合，有所有序偶(a,b)，其中aA,bB，构成的集合称为集合
21、A与B的笛卡尔积，记为：AB注：,A=一般地：ABBA(AB)C A(BC)推广：A1A2 An=(a1,a2,an)/aiAiAAA(n个）记为：An关系的定义：AB的任一子集称为是A到B的一个关系。注：空关系、全关系,A上的二元关系常用关系说明关系的定义域、值域、域关系的交、并、补、差仍是关系。第四节 关系的表示与关系的性质关系的两种表示方法：1、关系的图表示设R是有限集合A到B一个关系将集合A,B中的元素在平面上用结点表示,如果集合A中的元素a与集合B中的元素b有关系R，则从a到b联结一条有向弧线。特别地：n元集合A上的一个二元关系，只需在平面上划出n个结点即可。例：略2、关系的矩阵表示
22、设A=a1,a2,am,B=b1,b2,bn是两个集合，R是A到B个一个关系，则mn矩阵MR=其中rij=称为关系R的,关系矩阵。例：略关系的性质:引入：例子定义：设R是集合A上的二元关系1)如果对任意xA，有(x,x)R，则称R是自反的2)如果对任意xA，有(x,x)R，则称R是反自反的3)对任意x,yA，如果(x,y)R(y,x)R，则称R是对称的,4)对任意x,yA，如果(x,y)R，(y,x)R x=y，则称R是反对称的5)对任意x,y,zR，如果(x,y)R，(y,z)R(x,z)R，则称R是传递的。注：1)关系有可能满足的五个性质的图、矩阵特征。2)自反与反自反并不是非此即彼的关系
23、，同样对陈与反对称也不是相互对立的。例：设A=1,2,3，,1)R=(1,1),(1,2),(3,2),(2,3),(3,3)是A上的一个二元关系，但R既不是自反的也不是反自反的。2)S=(1,2),(2,1),(1,3)是A上的一个二元关系，S既不是对称的也不是反对称的。例题：设A=1,2,3,4，A上的关系R=(1,1),(1,3),(2,2),(3,3),(3,1),(3,4),(4,3),(4,4),试讨论R的性质。（自反、对称）第五节关系的运算与闭包、求逆运算定义：设R是集合A到B的一个二元关系，则B到A的关系(b,a)/(a,b)R称为R的逆关系，记为R-1。注：1)规定空关系的逆
24、关系还是空关系。2)dom(R-1)=ran(R);ran(R-1)=dom(R)定理：设R,R1,R2均为A到B的二元关系，则,1)(R-1)-1=R2)(R1R2)-1=R1-1 R2-1(R1 R2)-1=R1-1 R2-1 3)-1=R-14)(AB)-1=BA5)(R1-R2)-1=R1-1-R2-1 6)如果R1R2，则R1-1 R2-1 证明：略、关系的复合运算,定义：设R是集合A到B关系，S是集合B到C的关系，则A到C的关系(a,c)/bB,使得(a,b)R,(b,c)S称为关系R与S的复合。记为RS注：1)R=R=例题：略定理：设R1,R2分别为有限集A到B,B到C的关系，则
25、M R1 R2=M R1M R2证明：略注：1)布尔乘,例题：略定理：设R1,R2,R3分别为集合AB,B C,CD的关系，则（R1R2)R3 R1(R2 R3)证明：注：由于关系的复合运算满足结合律，因此我们可以给出以下关系的方幂的定义，规定：Rn=RRR（n个）,、关系的闭包运算定义：设R是集合A上的二元关系，如果R是A上的一个自反关系，且满足：1)R R2)对A上的任何一个自反关系R，如果R R，必有R R，则称关系R是关系R的自反闭包，记为r(R)注：仿上可以定义一个关系的对称闭包与传递闭包s(R),t(R)定理：设R是非空集合A上的二元关系，,则：1)r(R)=RIA2)s(R)=R
26、R-13)t(R)=RR2 R3 证明：注：当A为n元集合时,t(R)=RR2 Rn例题：设A=a,b,c，R=(a,b),(a,c),(b,c),求r(R),s(R),t(R)闭包的性质定理：设R是非空集合A上的一个关系，,1)R是自反的，则r(R)=R2)R是对称的，则s(R)=R3)R是传递的，则t(R)=R定理：设R1,R2是非空集合A上的关系，且R1R2，则1)r(R1)r(R2)2)s(R1)s(R2)3)t(R1)t(R2)证明：,第六节等价关系与划分（分类）引入定义：非空集合A上的一个关系R称为是等价关系，如果R满足自反性、对称性、传递性。例题：人群中的同姓关系；整数集合上的同
27、余关系由同余关系引入集合的划分，等价类以及二者之间的关系。,商集：设R是集合A上的一个等价关系，则A关于R所产生的划分的所有的等价类做成的集合，称为集合A关于等价关系R的商集，记为：A/R例题：略第七节 偏序关系定义：设R是非空集合A上的关系，如果R满足自反性、反对称性、传递性，则称R是一个偏序关系。例题：略,注：1)一个偏序关系通常用“”符号表示。2）集合A与其上的一个偏序关系“”组成的序偶称为偏序集。例题：整除关系、小于等于关系、包含关系等偏序集的HASSE图：1)元素用结点表示2)如果元素x覆盖y，则将x画在y的上方，并且在它们之间画一线段。注：因为偏序集的每个结点都有环，所以在画Has
28、se图时，可以省略。,例题：略偏序集中的特殊元素1、极大元与极小元定义：设是偏序集，BA，bB，如果B中不存在元素x，使得xb,且bx（xb)，则称b为B的极大(小）元。例：略2、最大元与最小元定义：设是偏序集，BA，bB，如果对B中任意元素x，都有xb（bx)，,则称b为B的最大（小）元。例：略3、上界与下界定义：设是偏序集，BA，aA，如对xB，有xa(ax)，则称a是B的一个上(下)界例：略4、上确界与下确界定义：设是偏序集，BA，a是B的一个上（下）界，如对B的任意上（下）界x，,都有ax(xa)，则称a是B的上(下)确界例：略例题：集合A=a,b,c的幂集关于包含关系 分析：在Has
29、se图中，几种特殊元素所处的位置。,另外几种常见的重要的序集：定义：设A是一个非空集合，如果A上的关系R满足反自反性和传递性，则称R是A上的拟序关系。注：拟序关系通常用符号“”表示。拟序集可以表示为。例题：略定义：设是集合A上的偏序关系，如果对A中的任意二个元素a,b，总有ab或ba成立，则称是A上的全序关系或线性序关系。称是全序集。,例题：略定义：设是一偏序集，如果A的任意非空子集都含有最小元，则称为良序集。例题：略例1：设R是A上的二元关系，证明：1)如果R是A上的拟序关系，则r(R)是A上的偏序关系2)如果R是A上的偏序关系，则R-IA是A上的拟序关系。,例2：证明良序集必是全序集，反之
30、则未必第八节 函数定义：设X，Y是两个集合，f是X到Y的一个关系，如果对任意的xX，都存在唯一的yY，使得(x,y)f，则称关系f是X到Y的一个函数。记为：f:XY或XY。注：1)如果(x,y)f，则称x是自变量，y是x在f作用下的象，(x,y)f也可以记作y=f(x),且记f(X)=f(x)/xX 2)dom(f)=X;ran(f)Y,3)X到Y函数也叫做X到Y的映射。4)到的一个关系未必是函数。例题：略因为函数是序偶的集合，因此函数的相等可以利用集合相等的概念加以定义。定义：设f,g均为集合A到B的函数，如果对任意xA，都有f(x)=g(x)，则称函数f,g相等，记为f=g例题：略,思考题
31、：假设A是m元集合，B是n元集合，则A到B的函数有多少个？三种特殊的函数：定义：假设f:XY，如果ran(f)Y，则称f是满射。例题：略定义：假设f:XY，如果对任意x,yX，当xyf(x)f(y)，则称f为单射。例题：略,定义：假设f:XY，如果f既是满射又是单射，则称f为双射或一一映射。例题：略第九节逆函数和复合函数函数作为一个特殊的关系，我们可以求其逆关系，但是其逆关系未必是函数。例如：略因此，对函数求逆。要保证其逆也是一个函数，需要规定一些条件。定理：设f:XY是一个双射函数，则f-1是,YX的双射函数。证明：略定义：设f:XY是一双射函数，称YX的双射函数f-1是f的逆函数。例：略定
32、理：设f:XY是一双射函数，则(f-1)-1=f证明：略利用关系的复合我们可以给出函数的复合,定义：设函数f:XY，g:YZ，则gf=(x,z)/yY,使得y=f(x),z=g(y)称为g对f的左复合例如：略定理：设函数f:XY，g:YZ，则g对f的左复合gf是一个XZ的函数。证明：略注：根据复合函数的定义，显然有gf(x)=g(f(x),性质定理：1)若g,f是满射，则gf是满射。2）若g,f是单射，则gf是单射。3）若g,f是双射，则gf是双射。证明：略定理：设函数f:XY，则f=fIX=IYf定理：设双射函数f:XY，则f-1f=IXff-1=IY证明：略,定理：设f:XY，g:YZ均为
33、双射函数，则：(gf)-1=f-1g-1证明：略,第四章 代数系统第一节 代数运算及其性质引入定义：一个AB到D的映射，称为是AB到D的代数运算。注：代数运算的表示一般地，如果是AB到D的代数运算，未必是BA到D的代数运算一个AA到A的代数运算叫做A上的代数元算或,A上的二元运算或A对运算是封闭的凯莱运算表代数运算可能满足的运算规律：结合律、交换律、幂等律、分配律、吸收律。代数结构：一个带有运算的集合称为代数结构或代数系统代数结构中可能存在的特殊元素：零元、单位元（幺元）、可逆元,第二节 子代数与积代数定义：设为一代数系统，A1A，如果A1关于运算是封闭的，则称是的子代数。注：具有n个运算的代
34、数系统的子代数的定义例：略定义：设与是两个代数系统，在AB中规定运算：(a1,b1)(a2,b2)=(a1 a2,b1*b2)，,则也是一个代数系统，称为与的积代数注：具有多个运算的代数系统的积代数的概念。例：略积代数的性质：定理：设与是两个代数系统，是他们的积代数如果,*满足交换律，则也满足交换律,如果,*满足结合律，则也满足结合律如果,*满足幂等律，则也满足幂等律如果与都有单位元，则也有单位元。如果与都有零元，则也有零元。证明：略定理：设与是两个代数系统，是它们的积代数,如1对2，*1对*2分别满足分配律，则1对2也满足分配律如1对2，*1对*2分别满足吸收律，则1对2也满足吸收律第三节
35、代数系统的同态与同构引入定义：设与是两个代数系统，是A到B映射，如对a1,a2A,有(a1a2)=(a1)*(a2)，则称是代数系统到的同态映射。,注：具有多个运算的代数系统的同态定义特殊的同态映射定义：设与是两个代数系统，是A到B满射，如对a1,a2A,有(a1a2)=(a1)*(a2)，则称是代数系统到的同态满射。此时也称与是同态的。记为：同态满射的性质定理1：设,如满足交换律，则也满足交换律如满足结合律，则也满足结合律如满足幂等律，则也满足幂等律如有单位元，则有单位元如有零元，则有零元如有单位元，aA在A中有逆元，则a的象在B中也有逆元，且a的逆元的象就是a的象的逆元。证明：略,定理2：
36、设如1对2 满足分配律，则*1对*2也满足分配律如1对2 满足吸收律，则*1对*2也满足吸收律定义:设与是两个代数系统，是A到B双射，如对a1,a2A,有(a1a2)=(a1)*(a2)，则称是代数系统到的同构映射。此时也称与是同构的。记为：,注：同态具备的性质同构肯定具备。反之则未必自同态与自同构例:略两个同构的代数结构称之为是代数相等的。第四节 半群与独异点定义：设是一代数系统，如果运算满足结合律，则称是半群。例：略,定义：一个具有单位元的半群称为幺半群或独异点。例：略在独异点中我们可以进一步规定：a2=aa,an+1=ana,a0=e,a-n=(a-1)n定义：是半群，BS，如果也是半群
37、，则称是子半群。注：验证方法定义：是独异点，TS，如果也是半群，且eT，则称是子独异点。,第五节 群与子群定义：设为一代数系统，如果满足：1、G对运算是封闭的2、运算满足结合律3、有单位元4、对aG在G中有逆元则称是群。例：略有限群、无限群以及群的阶,定义：如果在群中交换律成立，则称是交换群或Abel群例：略循环群的引入：例子定义：设是群，aG，如果G中任意一个元素均可以表示为a的方幂，则称是由a所生成的一个循环群，记为G=(a)，其中a叫做循环群G的一个生成元。注：循环群的生成元一般不唯一。有限循环群与无限循环群的构造,群的性质：定理1：在群中，对a,bG，方程ax=b与ya=b在G中都有唯
38、一解定理2：在群中左、右消去律成立。即：ab=acb=c，ba=cab=c定理3：在群中，单位元是唯一的幂等元定理4：在群中，(a-1)-1=a，(ab)-1=b-1a-1,anam=an+m，(an)m=anm,思考：(ab)n=anbn吗？子群定义：群的非空子集H如果关于G的运算也构成一个群，则称是群的一个子群，记为：HG例子：略子群的判定定理1:设H是群的非空子集,则HG对a,bHabH 对aHa-1H,例：略定理2:设H是群的非空子集,则HG对a,bHab-H 例：略第六节环与域引入环的定义：设R,+,是一代数系统,如果 R,+是一个交换群 R,是一个半群 在R,+,中对+满足分配律,
39、则称R,+,是一个环。例：略注：在环中，关于加法：单位元我们通常用记之；元素a的逆元称为a的负元，用-a记之；a+a+ana;a+(-b)a-b环中的运算性质 a+0=0+a=a-a+a=a+(-a)=0-(-a)=a-(a+b)=-a-b,0a=a0=0a(-b)=(-a)b=-(ab)(-a)(-b)=ab a(b-c)=ab-ac;(b-c)a=ba-ca a(b1+b2+bn)=ab1+ab2+abn(b1+b2+bn)a=b1a+b2a+bna给出与数的运算不同的例子几种特殊类型的环：、交换环,、有单位元环、无零因子环、整环、除环与域第七节格与布尔代数引入偏序格的定义：设是一个偏序集
40、，如果L中任意两个元素都有上、下确界，则称偏序集是格。例：略,在格中,我们可以规定：ab=supa,b ab=infa,b则，是格的两个二元运算，即：是一个代数系统。该代数系统满足定理：在格所诱导的代数系统中，结合律、交换律、幂等律、吸收律成立。证明：略命题：设是一个代数系统，其中,都是二元运算且满足吸收律，则,都满足幂等律。证明：略定理2：设是一个代数系统，其中,都是二元运算且满足结合律、交换律、和吸收律，则L上存在偏序关系“”，使得是一个格。证明：略定义：设是一个代数系统，其中,都是二元运算且满足结合律、交换律、和吸收律，则称是一个代数格。,注：在偏序格在格中,我们可以规定：ab=supa
41、,b ab=infa,b，则是一个代数格，称为是由所诱导的代数格。如在代数格中，规定：abab=a(或ab=b)，则是一个偏序格，称为是由代数格所诱导的偏序格。格的性质：p.p1 设是一个格，对a,b,cL，如果ab,cd，则acbd,acbd,p.p2 设是一个格，对a,b,cL，有：a(bc)(ab)(ac)(ab)(ac)a(bc)p.p3设是一个格，对a,b,cL，如ac，则a(bc)(ab)c注：性质3的逆也成立。子格的定义：,子格定义：设是一个代数格，S是L的子集，如果也是一个格，则称其是格的子格。例：略注：上述定义是代数子格；对偏序格也可以定义子格；但是一个偏序子格未必是代数子格
42、。格的同态与同构定义：设与是两个代数格，f是L1到L2的映射，如果对任意的,a,bL1有f(a1b)=f(a)2f(b),f(a1b)=f(a)2f(b),则称f是到同态映射。注：当f是满射与双射时，有相应的同态满射与同构映射。命题：设格与所诱导的代数系统为到，f是到的格同态，对x,y L1,如x 1y,则f(x)2f(y)分配格与有补格定义：设是一个代数格，如果,对以及对均满足分配律，则称是一个分配格。注：一个格未必是分配格例如：钻石格与五角格都不是分配格。注：一个格L是分配格当且仅当L不含有与钻石格或五角格同构的子格。分配格的简单性质 定理1：如果在一个格中交运算对于并运算可分配，则并运算
43、对交运算也一定可分配。反之亦然。,证明：略定理2：设是一个分配格，对a,b,cL,如果ab=ac,ab=ac,则b=c证明：略,有补格定义：设是一个格，aL，如果对任意xL，有小xa（ax），则称a是格的全上（下）界注：一个格如果有全上（下）界，则必唯一。通常全上界用表示，全下界用表示定义：一个具有全上界与全下界的格称为有界格。记为例子：略,定理：设是有界格，则对任意aL，有a1=1,a1=a,a0=a,a0=0定义：设为有界格，aL，如果存在bL，使得ab=1,ab=0，则称b是a的一个补元。,注：通常在有界格中，一个元素如果有补元，未必唯一。定义：在有界格中，如果每个元素都有补元，则称是一
44、个有补格。例：略在一个有界分配格中，由前述定理2我们可以知道，如果一个元素有补元，则必唯一。定义：一个有补分配格称为布尔代数。,第五章 图论第一节 无向图与有向图定义：一个三元组G=称为图，其中1)V是一个非空集合，通常称为结点集2)E是一个集合，通常称为边集3)f是从VV到E的一个映射注：1)如果E是无向边集，则称图G是无向图；如E是有向边集，则称图G是有向图2)通常当边集给定后，映射f即可确定，所以一般情况下，一个图我们都用一个二元组G=来表示。,3)一条边我们通常可以用其端点构成的序偶加以表示。无向边用无序偶，有向边用有序偶表示。4)如果构成一条边的二个结点相同，则该边称为环。5)构成两
45、条边的结点对相同，则这两条边称为平行边。含有平行边的图称为多重图；不含平行边和环的图称为简单图。6）任何两个结点之间都有边相连的简单图,称为完全图；具有n个结点的完全图记为Kn显然 Kn有n(n-1)/2条边。7)一个具有n个结点，m条边的图称为(n,m）图。特别：(n,0)图8）如果在两个结点间有边相连，则称这两个结点是邻接的,不与任何结点邻接的结点称为孤立点。9)与结点v相关联的边的条数称为该结点的度数，记为deg(v)。对有向图而言，以该结点为起点的边的条数称为该结点的出度,记为od(v)；以该结点为终点的边的条数称为该结点的入度,记为id(v)。无向图G如果每个结点的度数均为k,则称为
46、k度正则图例：略定理（握手定理）：=2m,推论：在一个图中，度数是奇数的结点有偶数个。注：对有向图而言，显然定义：设G=与G=是两个无向图，如果VV，E E则称G是G的子图特别地：如果VV，E E则称G是G的真子图如果V=V，E E则称G是G的生成子图定义：设G=与G=是两个图，如果存在双射f:V1 V2,使得对任意,(vi,vj)E1(f(vi),f(vj)E2,则称f是图G1到G2的同构映射。此时称图G1与G2是同构的，记为G1G2注：如果G1G2，则1)它们的结点个数相同，边数相等2)保持边的关联关系3)对应的结点的度数相等第二节 路、回路与图的连通性定义：在图G中从结点vi到结点vj的
47、点与边的交替序列称为连接vi与vj的路（通路）,vi与vj分别称为起点和终点；通路中边的条数称为通路的长度。如果一条路的起点与终点相同，则称该路为回路。如果一条路中各边互不相同，则称该路为迹。如果一条路中，各结点互不相同，则称该路为初级路或路径。在一条回路中，除了起点和终点外，如果其余结点互不相同，则称为初级回路或圈。,在一个回路中，如果有边重复出现，则称为复杂回路。注：1)在一个图中，如果每个结点的度数均大于等于2，则必包含一条初级回路。2)在求路的长度时，如果有环的话，计算时，环的长度为2。如果有平行边，长度为2。定义：在无向图G中，如果结点u与v之间存在一条通路，则称结点u与v是连通的。
48、如果图G的任何两点均是连通的，则称G是连通图。,对有向图其连通性可以分为强连通、弱连通以及单连通定义：在有向图G=中，如果从结点u到v存在一条路，则称从结点u到v是可达的，也称为单向可达的。如果从结点u到v是可达的，从结点v到u也是可达的，则称为是双向可达的。定义：在简单有向图D中1）如果任何一对结点都是单向可达的，则称图D是单连通的。,2）如果任何一对结点都是双向可达的，则称图D是强连通的。3）如果在D中不考虑边的方向，D是一个无向连通图，则称D是弱连通的。注：双连通必为单连通，单连通必为弱连通。第三节 图的矩阵表示一、无向图矩阵表示1、邻接矩阵定义：设G=是n阶无向图，且,V=v1,v2,
49、vn，nn矩阵A=(aij)成为图G的邻接矩阵。其中aij表示结点vi,vj之间邻接边的条数（ij),如果（vi,vi）是环，aii=2,否则为0。例题：略邻接矩阵的性质：1、邻接矩阵是对称矩阵2、邻接矩阵的第i行元素之和是结点vi的度数定理：设简单图G的邻接矩阵为A=(aij)nn,记Al=(ailj)nn(l 为正整数），则1）当ij时，表示从结点vi到vj长度为l的通路的条数。2)当i=j时，表示经过结点vi的长度为l的回路的条数。例题：略2、连接矩阵定义：设G=为简单图，V=v1,v2,vn，则n阶矩阵C=(cij)nn称为G的连接矩阵，其中,如果vi与vj连通，则cij=1；如果vi
50、与vj不连通，则cij=0连接矩阵的性质：1、C是对称矩阵，且主对角线元素全为1。2、G是连通图当且仅当C的元素全为13、设A=(aij)nn是简单图G的邻接矩阵，则C=A0A1 An-1其中为布尔加法例题：略3、关联矩阵定义：设无向图G=，V=v1,v2,vn,E=e1,e2,em，则nm矩阵M=(mij)nm称为图G的关联矩阵，其中mij表示vi与ej的关联次数。关联矩阵的性质：1、关联矩阵每列之和为22、每行之和是该结点的度数。3、元素全为0的行，对应的点是孤立点。4、相同的两列对应一对平行边。5、M中所有元素之和等于边数的2倍。,有向图的矩阵表示1、邻接矩阵定义：设G=是有向图，V=v
