离散数学.ppt

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,离散数学,第一章 命题逻辑,什么是逻辑学：逻辑学是一门研究思维形式及思维规律的科学。,逻辑学的分类：辩证逻辑与形式逻辑。,其中，辩证逻辑是以辩证法认识论的世界观为基础的逻辑学；,形式逻辑主要是对人的思维形式结构和规律进行研究的类似于语法的一门工具性,学科。思维的形式结构主要包括概念、判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是判断。由一个或几个判断推出另一判断的思维形式就是推理。,研究推理有很多方法，用数学的方法研究推理的规律称为数理逻辑。所谓的数学方法就是引进一套符号体系的方法，所以数理逻辑又称符号逻辑，它是从量的方面来研究思维规律的。,现代数理逻辑分为证明论、模型论、递归函数论、公理化集合论等。在此我们介绍的是数理逻辑最基本的内容：命题逻辑和谓词逻辑。,第一节 命题与命题联结词,什么是命题：,能够判断真假的陈述语句。,命题的真值：,真（,T,或,1),和假（,F,或,0,）,命题的种类,：简单命题（原子命题）与复合命题,命题的表示：,大写或小写英文字母或带下标的英文字母。,表示命题的字母称为命题标识符。,命题常量与命题变元：,表示确定命题的标识符成为命题常量；仅仅表示命题的的位置标志的标识符称为命题变元。,注意：命题常量具有确定的真值；而命题变元可以标识任意命题，它不能确定真值，它本身也不是命题。,常用的命题联结词,1,、否定,定义：设,P,为一命题，,P,的否定是一个新的命题，记为,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,，它们的条件命题是一个复合命题，记为,PQ,。当且仅当,P,为,T,，,Q,为,F,时，,PQ,为,F,，否则,PQ,为,T.,注：,在,PQ,中,P,成为前件，,Q,称为后件。,条件联结词与自然语言中的,“,如果,那么,”,类似，但也不尽相同。,善意的推断,二元运算,5,、双条件,定义：给定两个命题,P,、,Q,，它们的双条件命题是一个复合命题，记为,PQ,。当且仅当,P,、,Q,的真值相同时，,PQ,为,T,，否则,PQ,为,F.,注：,双条件联结词与自然语言中的,“,当且仅当,”,，,“,充分必要,”,类似，但也不尽相同。,二元运算,命题联结词除了上述五个之外，还有不可兼析取、条件否定、与非、或非联结词。,在一个复合命题中往往含有多个命题联结词，其运算的次序是：,、,、,、,、,第二节 命题公式及其分类,直观地说，由命题变元、命题常量、命题联结词、括号组成的一个有意义的式子成为命题公式。,定义：,命题常量、命题变元是命题公式,如果,A,是命题公式，则,A,是命题公式,如果,A,、,B,是命题公式，则,A,B,、,AB,、,AB,、,A,B,也是命题公式,只有有限次地应用,产生的符号串才是命题公式。,命题公式的赋值：,命题公式的分类：重言式、矛盾式、可满足式,第三节 等值演算,等值的概念：设,A,，,B,是两个命题公式，,p,1,，,p,2,，,，,p,n,为出现在,A,，,B,中的所有的命题变元，如果对,p,1,，,p,2,，,，,p,n,的任何一种真值指派，,A,，,B,的真值都相同，则称,A,，,B,是等价（或等值）的。记为,A,B,验证命题公式等值常用的方法有：真值表法、蕴含法、公式法（直接证法）。,1,、,真值表法,：,例：证明,A,B(AB)(BA),2,、,蕴含法,：,定理,1,：设,A,，,B,是两个命题公式，则,A,B,当且仅当,A,B,为永真式。,蕴含的定义：,定义,2,：如果,AB,为永真式，则称,A,蕴含,B,，记为,AB,蕴含常见的性质：,1,、自反性,2,、传递性,3,、如果,AB,，,AC,，则,ABC 4,、如果,AC,，,BC,，则,ABC,由前面的例子和定理,1,我们马上可以得到,定理,2,：,A,B,当且仅当,AB,，,BA,分析蕴含的验证方法,例,1,：证明：,Q(PQ)P,例,2,：证明：,(,P Q)P Q,3,、,公式法,常用的等值演算公式有,24,个。,置换规则,子公式：如果,X,是命题公式,A,的一部分，且,X,本身也是一个命题公式，则称,X,是命题公式,A,的子公式。,定理：（置换规则）设,X,是命题公式,A,的子公式，,如果,X Y,，则将,A,中的,X,用,Y,置换所得到的命题公式,B,与,A,等价。,例题：,1,、证明：,(,P,Q),(P,Q),P,2,、证明：,(,P,Q),(Q R)(P Q)R,对偶式：,对偶的概念：,对偶定理：设,A,，,B,是命题公式，如果,A B,，则,A*B*,第四节 主析取范式与主合取范式,命题公式的规范化,1,、命题联结的归约：最小命题联结词组,2,、命题范式,定义,1,：一个命题公式称为合取范式，如果它具有如下形式：,A,1,A,2,A,n,，其中,A,1,，,A,2,，,，,A,n,都是由命题变元或其否定所组成的析取式。,定义,1,：一个命题公式称为析取范式，如果它具有如下形式：,A,1,A,2,A,n,，其中,A,1,，,A,2,，,，,A,n,都是由命题变元或其否定所组成的合取式。,求一个命题公式的析取或合取范式的步骤：,化归：将命题公式中的联结词化归为,，,，,移非：利用狄,.,摩根律，将求非符号移到命题变元的前面。,归约：利用分配律将之化为析取或合取范式。,例子：,1,、,(,p,q),r),p,2,、,（,p,q),(p,q),注：一个命题公式的析取或合取范式并不是唯一的。,主析取范式与主合取范式,定义：,n,个命题变元的合取式，称为布尔小项或合取，如果每个命题变元或其否定不能同时出现，但二者必须出现且仅出现一个。,注：,n,个命题变元构成的布尔小项有,2,n,个,布尔小项的编码：命题变元,-1,，其否定,-0,布尔小项的常见性质：,1,、每个小项当其真值指派与编码相同时，其真值为,1,，在其余,2,n,-1,中指派情况下均为,0,。,2,、任意两个不同的小项合取式为,0,。,3,、全体小项的析取式为,1,。,定义：对于给定的命题公式，如果有一个等价公式，它仅有小项的析取所组成，则该等价式称为原式的主析取范式。,定理：在真值表中，一个公式的真值为,T,的指派所对应的小项的析取，即为此公式,的主析取范式。,证明：略,命题公式的主析取范式的求法,1,、真值表法,例,1,：,求命题公式,P,Q,，,P,Q,，,(P,Q),的主析取范式。,求命题公式,(,P,Q),(P R)(Q R),的主析取范式,2,、公式法,基本步骤：,1,、化归为析取范式,2,、合并同类同类项，去掉永假项。,3,、对合取项补入没有出现的命题变元，即添加,P,P,项，然后利用分配律展开公式。,例子：求,P,(,P,Q),(,Q,P),的主析取范式。,注：对于一个命题公式的主析取范式，如将其命题变元的个数及出现次序固定后，则此公式的主析取范式是唯一的。,类似于主析取范式，也有主合取范式。,定义：,n,个命题变元的析取式，称为布尔大项或析取，如果每个命题变元或其否定不能同时出现，但二者必须出现且仅出现一个。,注：,n,个命题变元构成的布尔 大项有,2,n,个,布尔大项的编码：命题变元,-0,，其否定,-1,布尔大项的常见性质：,1,、每个大项当其真值指派与编码相同时，,其真值为,0,，在其余,2,n,-1,中指派情况下均为,1,。,2,、任意两个不同的大项析取式为,1,。,3,、全体大项的合取式为,0,。,定义：对于给定的命题公式，如果有一个等价公式，它仅有大项的合取所组成，则该等价式称为原式的主合取范式。,定理：在真值表中，一个公式的真值为,F,的指派所对应的大项的合取，即为此公式,的主合取范式。,证明：略,求一个命题公式的主和取范式的方法，也有真值表法与公式法。其中公式法也分为三个步骤：,1,、化归为合取范式,2,、合并同类项，去掉永真项。,3,、对析取项补入没有出现的命题变元，即添加,P,P,项，然后利用分配律展开公式。,例子：,1,、求,(,P,Q),(,P,R),的主合取范式。,2,、求,(,P,Q),R,的主合取范式。,第五节 命题逻辑的推理理论,定义：设,A,C,是两个命题公式，如,A,C,为一重言式，即,AC,，则称,C,是,A,的有效结论，或,C,可以由,A,逻辑推出。,注：,通常情况下，前提可能有若干个，即：,H,1,H,2,H,n,C,从定义可以看到，推理正确并不能保证结论为真，这与现实中的推理有所不同。,如何验证命题逻辑的推理，通常有以下三种方法：真值表法、直接证法、间接证法（反证法）。,1,、真值表法：,分析验证的方法,例：一份统计表的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表的错误不是由于材料不可靠，所以这份统计表是由于计算有错误。,2,、直接证法,直接证法就是由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效结论。在推演的过程中，还需要用到以下两个规则：,P,规则：前提的推导过程中的任何时候都可以引入使用。,T,规则：在推导中，如果有一个或多个公式,、重言蕴含着公式,S,，则公式,S,可以引入推导中。,例：,证明：,(,P,Q),(P,R),(Q,S),S,R,证明,(,W,R),V,V,C,S,S,U,C,U,W,3,、间接证法,反证法,欲证,H,1,H,2,H,n,C,，将,C,作为一个前提加以引用，推出一个矛盾式。,例：证明,A,B,(B,C),A,证明：,P,Q,P,R,Q,S,S,R,CP,规则：欲证,H,1,H,2,H,n,(,R,C),可以将,R,作为一个逻辑前提加以引用，证明,C,为真即可。（分析理由）,例子：证明,:,A(BC),DA,BDC,证明：,AB,CBAC,应用简介,第二章谓词逻辑,为什么要引入谓词逻辑：,第一节谓词的概念与表示,在一个简单命题中，表示主语的词称为客体或个体，表示谓语的词称为谓词。通常客体是可以独立存在的对象，它可以是一个具体的事物，也可以是抽象的概念。谓词一般是用来刻划个体的性质或个体之间的关系。,对个体我们通常用小写字母表示，而谓词我们则用大写字母表示。一个命题我们就可以用,A(b),这种形式来表示，叫做谓词填式。,用来表示特定个体的小写字母我们将之称为个体常量，用来表示某一些个体的小写字母称为个体变量。一个个体变量的取值范围叫做个体域或论域。将考虑的所有的事物组成的个体域，称为全总个体域。,从前面我们可以看到，在一个谓词填式中可以含有个体变元。,定义：有一个谓词，若干个个体变元组成的表达式，称为命题函数或谓词变项。,注：、在一个谓词变项中，根据其所含变量的个数，有一元谓词,，,n,元谓词。其中,0,元谓词是命题。,、在谓词变项中，如果含有变元，则它不是命题，只有对其中的变元都取特定的个体时，它才表示确定的命题。,量词,使用上述概念有时还不能用符号很好地表达日常生活中的各种命题，例如：,S(x),表示,x,是大学生，,x,的个体域是某单位职工。则可以理解为某单位的职工都是大学生，或某单位的有些职工是大学生。为避免这种理解上的混乱，我们引入量词，以刻划“所有”、“有一些”的不同概念。,、全称量词,用来表达“所有的”,“,每一个”，“任一个”等,的量词。,例子：,所有人都要呼吸：,(,x)M(x)H(x),每个学生都要参加考试：,(,x)P(x)Q(x),2,、存在量词,用以表示“有一些”，“至少有一个”等概念的量词。,例子：,有些人是聪明的：,有的人早饭吃面包：,全称量词与存在量词统称为量词。,在上面的例子中，每个由量词确定的表达式，都与个体域有关。我们通常总是在全总个体域中考虑问题，因此就要通过相应的谓词对个体变元的取值范围加以说明，这就是特性谓词。一般地，对全称量词，特性谓词常做蕴含的前件；对存在量词，特性谓词常作合取项。,第二节 谓词公式及解释,由一个或多个命题函数以及联结词构成的表达式，称为复合命题函数。,直观地讲，由命题、命题变元、命题函数、联结词、量词及括号构成的有意义的符号串称为谓词公式。,定义：,命题、命题变元、命题函数是谓词公式,如,A,是谓词公式，则,A,是命题公式,如,A,B,是谓词公式，则,A,B,A,B,AB,AB,是谓词公式,如,A,是谓词公式，则,(,x)A,(x)A,也是谓词公式，其中,x,是,A,中的个体变元。,只有有限次地利用,所产生的符号串才是谓词公式。,约束变元及其辖域（作用域）：,约束变元的更名,规则：,对约束变元可以更名，其更改的变元名,称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，在公式的其余部分不变。,更名时一定要更改为作用域中没有出现的变元名称。,例如：对,(,x)(P(x),R(x,y),Q(x,y),自由变元的代入,规则：,对谓词公式中的自由变元可以代入，代入时需对公式中出现该自由变元的每一处进行。,用以代入的变元与原公式中的所有变元的名称不能相同。,注：量词的次序不能颠倒，否则将与原命题意义不符。,通常在一个谓词公式中会出现各种变项，如果用指定的常项代替变项，就构成了对谓词公式的解释。一个谓词公式的解释，由四个部分组成：,非空个体域,D,D,中一部分特定元素,D,上一些特定的函数,D,上一些特定的谓词,例：给定解释,I,如下：,D=2,3,D,中特定元素,a=2,函数,f(x),其中,f(2)=3,f(3)=2,谓词变项,F(x),为：,F(2)=0,F(3)=1,G(x,y),为：,G(i,j)=1 i,j=2,3,L(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,为可满足的。,命题公式的推广：命题公式的等价公式和蕴含式均可推广到谓词演算中来。例如：,（,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),前束范式,定义：一个谓词公式如果量词均在全式的开头,它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式。,基本形式：,定理：任意一个谓词公式，均和一个前束范式等价。,例子,第四节 谓词演算的推理理论,常用的等值式以及牵涉到量词推理规则,例子：略,第三章 集合、关系、映射,第一节 集合的基本概念,集合的定义：若干个确定事物的全体。,注：,若干个：可以是有限也可以是无限。,组成集合的事物成为集合的元素。,元素的确定性：,集合的表示：,常用集合的习惯表示法：,子集与幂集：,第二节 集合的基本运算,交、并、补、差、对称差。,第三节 笛卡尔积与关系,序偶：有序偶与无序偶,定义：设,A,B,是两个集合，有所有序偶,(a,b),，其中,a,A,bB,，构成的集合称为集合,A,与,B,的笛卡尔积，记为：,AB,注：,A,=,一般地：,ABBA,(,AB)C A(BC),推广：,A,1,A,2,A,n,=(a,1,a,2,a,n,)/a,i,A,i,A,A,A(n,个）记为：,A,n,关系的定义：,AB,的任一子集称为是,A,到,B,的一个关系。,注：,空关系、全关系,A,上的二元关系,常用关系说明,关系的定义域、值域、域,关系的交、并、补、差仍是关系。,第四节 关系的表示与关系的性质,关系的两种表示方法：,1,、关系的图表示,设,R,是有限集合,A,到,B,一个关系,将集合,A,B,中的元素在平面上用结点表示,如果集合,A,中的元素,a,与集合,B,中的元素,b,有关系,R,，则从,a,到,b,联结一条有向弧线。,特别地：,n,元集合,A,上的一个二元关系，只需在平面上划出,n,个结点即可。,例：略,2,、关系的矩阵表示,设,A=a,1,a,2,a,m,B=b,1,b,2,b,n,是两个集合，,R,是,A,到,B,个一个关系，则,m,n,矩阵,M,R,=,其中,r,ij,=,称为关系,R,的,关系矩阵。,例：略,关系的性质,:,引入：例子,定义：设,R,是集合,A,上的二元关系,1),如果对任意,x,A,，有,(x,x)R,，则称,R,是自反的,2),如果,对任意,x,A,，有,(x,x)R,，则称,R,是反自反的,3),对任意,x,y,A,，如果,(x,y)R(y,x)R,，则称,R,是对称的,4),对任意,x,y,A,，如果,(,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),自反与反自反并不是非此即彼的关系，同样对陈与反对称也不是相互对立的。,例：,设,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),规定空关系的逆关系还是空关系。,2)dom,(R,-1,)=ran(R);ran(R,-1,)=dom,(R),定理：设,R,R,1,R,2,均为,A,到,B,的二元关系，则,1)(,R,-1,),-1,=R,2)(R,1,R,2,),-1,=R,1,-1,R,2,-1,(R,1,R,2,),-1,=R,1,-1,R,2,-1,3),-1,=R,-1,4)(AB),-1,=BA,5)(,R,1,-R,2,),-1,=R,1,-1,-R,2,-1,6),如果,R,1,R,2,，则,R,1,-1,R,2,-1,证明：略,、关系的复合运算,定义：设,R,是集合,A,到,B,关系，,S,是集合,B,到,C,的关系，则,A,到,C,的关系,(,a,c)/,bB,使得,(a,b)R,(b,c)S,称为关系,R,与,S,的复合。记为,RS,注：,1),R=R=,例题：略,定理：设,R,1,R,2,分别为有限集,A,到,B,B,到,C,的关系，则,M,R1 R2,=M,R1,M,R2,证明：略,注：,1),布尔乘,例题：略,定理：设,R,1,R,2,R,3,分别为集合,A,B,B,C,C,D,的关系，则,（,R,1,R,2,),R,3,R,1,(R,2,R,3,),证明：,注：由于关系的复合运算满足结合律，因此我们可以给出以下关系的方幂的定义，,规定：,R,n,=RR,R,（,n,个）,、关系的闭包运算,定义：设,R,是集合,A,上的二元关系，如果,R,是,A,上的一个自反关系，且满足：,1),R,R,2),对,A,上的任何一个自反关系,R,，如果,R R,，必有,R,R,，则称关系,R,是关系,R,的自反闭包，记为,r(R),注：仿上可以定义一个关系的对称闭包与传递闭包,s(R),t(R),定理：设,R,是非空集合,A,上的二元关系，,则：,1),r(R)=R,I,A,2)s(R)=R,R,-1,3)t(R)=RR,2,R,3,证明：,注：当,A,为,n,元集合时,t(R)=RR,2,R,n,例题：设,A=a,b,c,，,R=(a,b),(a,c),(b,c),求,r(R),s(R),t(R),闭包的性质,定理：设,R,是非空集合,A,上的一个关系，,1)R,是自反的，则,r(R)=R,2)R,是对称的，则,s(R)=R,3)R,是传递的，则,t(R)=R,定理：设,R,1,R,2,是非空集合,A,上的关系，且,R,1,R,2,，则,1),r(,R,1,)r(,R,2,),2)s(,R,1,)s(,R,2,),3)t(,R,1,)t(,R,2,),证明：,第六节等价关系与划分（分类）,引入,定义：非空集合,A,上的一个关系,R,称为是等价关系，如果,R,满足自反性、对称性、传递性。,例题：人群中的同姓关系；整数集合上的同余关系,由同余关系引入集合的划分，等价类以及二者之间的关系。,商集：设,R,是集合,A,上的一个等价关系，则,A,关于,R,所产生的划分的所有的等价类做成的集合，称为集合,A,关于等价关系,R,的商集，记为：,A/R,例题：略,第七节 偏序关系,定义：设,R,是非空集合,A,上的关系，如果,R,满足自反性、反对称性、传递性，则称,R,是一个偏序关系。,例题：略,注：,1),一个偏序关系通常用“,”,符号表示。,2,）集合,A,与其上的一个偏序关系“,”,组成的序偶,称为偏序集。,例题：整除关系、小于等于关系、包含关系等,偏序集的,HASSE,图：,1),元素用结点表示,2),如果元素,x,覆盖,y,，则将,x,画在,y,的上方，并且在它们之间画一线段。,注：因为偏序集的每个结点都有环，所以在画,Hasse,图时，可以省略。,例题：略,偏序集中的特殊元素,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,的幂集关于包含关系,分析：在,Hasse,图中，几种特殊元素所处的位置。,另外几种常见的重要的序集：,定义：设,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-I,A,是,A,上的拟序关系。,例,2,：,证明良序集必是全序集，反之则未必,第八节 函数,定义：设,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,例题：略,思考题：假设,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,是,Y,X,的双射函数。,证明：略,定义：设,f:XY,是一双射函数，称,Y,X,的双射函数,f,-1,是,f,的逆函数。,例：略,定理：,设,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=fI,X,=I,Y,f,定理：设双射函数,f:XY,，则,f,-1,f=I,X,ff,-1,=I,Y,证明：略,定理：设,f:XY,，,g:YZ,均为双射函数，则：,(,gf),-1,=f,-1,g,-1,证明：略,第四章 代数系统,第一节 代数运算及其性质,引入,定义：一个,A,B,到,D,的映射，称为是,A,B,到,D,的代数运算。,注：,代数运算的表示,一般地，如果,是,A,B,到,D,的代数运算，,未必是,BA,到,D,的代数运算,一个,A,A,到,A,的代数运算,叫做,A,上的代数元算或,A,上的二元运算或,A,对运算,是封闭的,凯莱运算表,代数运算可能满足的运算规律：,结合律、交换律、幂等律、分配律、吸收律。,代数结构：一个带有运算的集合称为代数结构或代数系统,代数结构中可能存在的特殊元素：,零元、单位元（幺元）、可逆元,第二节 子代数与积代数,定义：设,为一代数系统，,A,1,A,，如果,A,1,关于运算,是封闭的，则称,是,的子代数。,注：具有,n,个运算的代数系统的子代数的定义,例：略,定义：设,与,是两个代数系统，在,AB,中规定运算,：,(a1,b1)(a2,b2)=(a1 a2,b1*b2),，,则,也是一个代数系统，称为,与,的积代数,注：,具有多个运算的代数系统的积代数的概念。,例：略,积代数的性质：,定理：设,与,是两个代数系统，,是他们的积代数,如果,*,满足交换律，则,也满足交换律,如果,*,满足结合律，则,也满足结合律,如果,*,满足幂等律，则,也满足幂等律,如果,与,都有单位元，则,也有单位元。,如果,与,都有零元，则,也有零元。,证明：略,定理：设,与,是两个代数系统，,是它们的积代数,如,1,对,2,，,*,1,对,*,2,分别满足分配律，则,1,对,2,也满足分配律,如,1,对,2,，,*,1,对,*,2,分别满足吸收律，则,1,对,2,也满足吸收律,第三节 代数系统的同态与同构,引入,定义：设,与,是两个代数系统，,是,A,到,B,映射，如对,a,1,a,2,A,有,(a,1,a,2,)=(a,1,)*(a,2,),，则称,是代数系统,到,的同态映射。,注：具有多个运算的代数系统的同态定义,特殊的同态映射,定义：,设,与,是两个代数系统，,是,A,到,B,满射，如对,a,1,a,2,A,有,(a,1,a,2,)=(a,1,)*(a,2,),，则称,是代数系统,到,的同态满射。此时也称,与,是同态的。记为：,同态满射的性质,定理,1,：设,如,满足交换律，则,也满足交换律,如,满足结合律，则,也满足结合律,如,满足幂等律，则,也满足幂等律,如,有单位元，则,有单位元,如,有零元，则,有零元,如,有单位元，,aA,在,A,中有逆元，则,a,的象在,B,中也有逆元，且,a,的逆元的象就是,a,的象的逆元。,证明：略,定理,2,：设,如,1,对,2,满足分配律，则,*,1,对,*,2,也满足分配律,如,1,对,2,满足吸收律，则,*,1,对,*,2,也满足吸收律,定义,:,设,与,是两个代数系统，,是,A,到,B,双射，如对,a,1,a,2,A,有,(a,1,a,2,)=(a,1,)*(a,2,),，则称,是代数系统,到,的同构映射。此时也称,与,是同构的。记为：,注：,同态具备的性质同构肯定具备。反之则未必,自同态与自同构,例,:,略,两个同构的代数结构称之为是代数相等的。,第四节 半群与独异点,定义：设,是一代数系统，如果运算,满足结合律，则称,是半群。,例：略,定义：一个具有单位元的半群称为幺半群或独异点。,例：略,在独异点中我们可以进一步规定：,a,2,=a,a,a,n+1,=a,n,a,a,0,=e,a,-n,=(a,-1,),n,定义：,是半群，,B,S,，如果,也是半群，则称,是,子半群。,注：验证方法,定义：,是独异点，,T,S,，如果,也是半群，且,e,T,，,则称,是,子,独异点,。,第五节 群与子群,定义：设,为一代数系统，如果满足：,1,、,G,对运算,是封闭的,2,、运算,满足结合律,3,、,有单位元,4,、对,aG,在,G,中有逆元,则称,是群。,例：略,有限群、无限群以及群的阶,定义：如果在群,中交换律成立，则称,是交换群或,Abel,群,例：略,循环群的引入：例子,定义：设,是群，,aG,，如果,G,中任意一个元素均可以表示为,a,的方幂，则称,是由,a,所生成的一个循环群，记为,G=(a),，其中,a,叫做循环群,G,的一个生成元。,注：,循环群的生成元一般不唯一。,有限循环群与无限循环群的构造,群的性质：,定理,1,：在群,中，对,a,bG,，,方程,a,x=b,与,ya=b,在,G,中都有唯一解,定理,2,：,在群,中左、右消去律成立。即：,a,b=acb=c,，,ba=cab=c,定理,3,：在群,中，单位元是唯一的幂等元,定理,4,：在群,中，,(,a,-1,),-1,=a,，,(a,b),-1,=b,-1,a,-1,a,n,a,m,=a,n+m,，,(a,n,),m,=a,nm,思考：,(,a,b),n,=a,n,b,n,吗？,子群,定义：群,的非空子集,H,如果关于,G,的运算,也构成一个群，则称,是群,的一个子群，记为：,H,G,例子：略,子群的判定,定理,1:,设,H,是群,的非空子集,则,H,G,对,a,bHa,bH,对,aHa,-1,H,例：略,定理,2:,设,H,是群,的非空子集,则,H,G,对,a,bHa,b,-,H,例：略,第六节环与域,引入,环的定义：设,R,+,是一代数系统,如果,R,+,是一个交换群,R,是一个半群,在,R,+,中,对,+,满足分配律,则称,R,+,是一个环。,例：略,注：在环中，关于加法：单位元我们通常用记之；元素,a,的逆元称为,a,的负元，用,-a,记之；,a+a+a,na,;a+(-b),a-b,环中的运算性质,a+0=0+a=a,-a+a=a+(-a)=0,-(-a)=a,-(a+b)=-a-b,0,a=a0=0,a(-b)=(-a)b=-(ab),(-a)(-b)=ab,a(b-c)=ab-ac;(b-c)a=ba-ca,a(b,1,+b,2,+,b,n,)=ab,1,+ab,2,+,ab,n,(b,1,+b,2,+,b,n,)a=b,1,a,+b,2,a,+,b,n,a,给出与数的运算不同的例子,几种特殊类型的环：,、交换环,、有单位元环,、无零因子环,、整环,、除环与域,第七节格与布尔代数,引入,偏序格的定义：设,是一个偏序集，如果,L,中任意两个元素都有上、下确界，则称偏序集,是格。,例：略,在格,中,我们可以规定：,a,b=supa,b a,b=inf,a,b,则,，,是格,的两个二元运算，即：,是一个代数系统。该代数系统满足,定理：在格,所诱导的代数系统,中，结合律、交换律、幂等律、吸收律成立。,证明：略,命题：设,是一个代数系统，其中,都是二元运算且满足吸收律，则,都满足幂等律。,证明：略,定理,2,：设,是一个代数系统，其中,都是二元运算且满足结合律、交换律、和吸收律，,则,L,上存在偏序关系,“,”,，使得,是一个格。,证明：略,定义：设,是一个代数系统，其中,都是二元运算且满足结合律、交换律、和吸收律，,则称,是一个代数格。,注：在偏序格在格,中,我们可以规定：,a,b=supa,b a,b=inf,a,b,，则,是一个代数格，称为是由,所诱导的代数格。,如在代数格,中，规定：,a,b,a,b=a(,或,a,b=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,的子集，如果,也是一个格，则称其是格,的子格。,例：略,注：上述定义是代数子格；对偏序格也可以定义子格；但是一个偏序子格未必是代数子格。,格的同态与同构,定义：设,与,是两个代数格，,f,是,L,1,到,L,2,的映射，如果对任意的,a,bL,1,有,f(a,1,b)=f(a),2,f(b),f(a,1,b)=f(a),2,f(b),则称,f,是,到,同态映射。,注：当,f,是满射