1、Lets play a game!GroupAGroupBGame 2 游戏规则：老鼠跑到哪个单词下面，学生快速读出那个单词，不会读则该同学略过，看那个小组又快又准！Game time favorite music free useful finish whyGame time where month testbusytrip festivalLets start our class!Lets review a movie first:“Kung Fu Panda”你现在太在乎过去，又太担忧未来。你现在太在乎过去，又太担忧未来。Be动词形式变化不同时期发生的动作或状态，要用动词不同的时态来表示
2、不同时期发生的动作或状态，要用动词不同的时态来表示概念概念一般现在时表示一般现在时表示习惯性或经常性的习惯性或经常性的动作动作，也可表示，也可表示现在的状态现在的状态或或主语主语具备的性格和能力具备的性格和能力，及，及普遍真理和普遍真理和自然规律自然规律。用法一、一般现在时表示习惯性、经常性的动作，通常和一、一般现在时表示习惯性、经常性的动作，通常和时间标志时间标志词（词（always、usually、often、sometimes、never、every morning/night/afternoon/day/week/month/year、once/twice a day/week/mon
3、th/year等）等）连用。连用。1）她通常在早上六点起床。）她通常在早上六点起床。She usually gets up at six oclock in the morning.2）我总是在周末玩游戏。我总是在周末玩游戏。I always play games on weekends.3）他每天早上读英语。）他每天早上读英语。He reads English every morning.v二、一般现在时表示现在的状态二、一般现在时表示现在的状态v1）我）我12岁了。岁了。v Im twelve.v2）她有三个篮球。）她有三个篮球。v She has three basketballs.v3
4、）我的书包在哪？）我的书包在哪？v Where is my schoolbag?v三、一般现在时表示主语具备的性格和能力。三、一般现在时表示主语具备的性格和能力。v1）我喜欢打篮球，但我不喜欢踢足球。）我喜欢打篮球，但我不喜欢踢足球。v I like playing basketball,but I dont like playing football.v2）他会讲汉语。）他会讲汉语。v He can speak Chinese.v四、一般现在时还可用于普遍真理和自然规律：四、一般现在时还可用于普遍真理和自然规律：v1）Two and four is six.v 2加加4等于等于6.v2）Th
5、e moon goes around the earth.v 月亮围绕着地球转。月亮围绕着地球转。v3）The sun rises（上升，升起）（上升，升起）from the east.v 太阳从东方升起。太阳从东方升起。你记住了么？你记住了么？v口诀：口诀：I用用am,you用用are,is连着连着she,he,it.单数名词单数名词v 用用is,复数名词都用复数名词都用are。一般现在时的具体运用一般现在时的具体运用 特疑：特疑：Where are you from?缩写缩写Tips:is not=isntare not=arentI am not=Im not一、含一、含Be（am/is
6、/are）动词的一般现在时）动词的一般现在时1.肯：肯：I am from America.否：否：Im not from America.疑：疑：Are you from America?回答：回答：Yes,I am./No,Im not.v练习：练习：v变下列句子的否定句、疑问句、肯否定回答并对划线部分提变下列句子的否定句、疑问句、肯否定回答并对划线部分提问。问。v1.I am thirteen years old.v2.Tom is a handsome boy.v3.My favorite subject is science.v4.They are my families.一、写出下
7、列动词的三单形式一、写出下列动词的三单形式go_ catch_ brush_ like_ have_ drink _ say_ learn_ teach _ eat_ read_ buy_study_ stay _ make _ look _ pass_ carry _ plant(种植种植)_ 二、用括号内动词的适当形式填空。二、用括号内动词的适当形式填空。1.We often_(play)in the playground.2.He _(get)up at six oclock.3._you_(brush)your teeth every morning.4.What_(do)he usu
8、ally_(do)after school?v5.Danny_(study)English,Chinese,vMaths,Science and Art at school.v6.Mike sometimes _(go)to the park with his v sister.v7.At eight at night,she often_(watch)TV withv his parents.v8._Mike_(read)English every day?v9.How many lessons_your classmatev _(have)on Monday?v10.What time_h
9、is mother_(do)the v housework?一、单选一、单选v1.I _to school at 7:00 in the morning.vA.go B.going C.goesv2.They _books every day in the library.vA.reads B.read C.readingv3.The monkey_ eating bananas very much.vA.like B.likes C.likingv4.Tom and Lily_my good friends.vA.am B.is C.arev5.I like watching TV,but
10、my mother_ like it.vA.dont B.doesnt C.does练习巩固练习巩固v6.Lily and Lucy _ from America.v A.is B.are C.amv 7.Wang Mei _ music and often _ to music.vA like;listen B likes;listens vC like;are listening D liking;listenv8.Jenny_ English every evening.vA has study B studies vC study D studiedv9._ your father d
11、rink milk every day?vA.Do B.Are C.Doesv10.-Where_she from?v -She_from China.vA.does;comes B.is;come C.is;comes v二、用括号内词的适当形式填空。二、用括号内词的适当形式填空。I _(be)a student.I _(be)from ChinaMr Wei_(be)my English teacher.He _(speak)English well and he _(work)hard a lot.I_(like)English very much.Lucy_(be)myfriend.S
12、he _(be)from America.She _(not speak)Chinese well.We _(not like)football.We _(be)good friends.v三、句型转换三、句型转换v1.I have many clothes.（变为一般疑问句）（变为一般疑问句）v_v2.Are Tom and you are good friends?（做肯定回答）（做肯定回答）v_ She lives in a small town near New York.（第一章 命题逻辑什么是逻辑学：逻辑学是一门研究思维形式及思维规律的科学。逻辑学的分类：辩证逻辑与形式逻辑。其中，
13、辩证逻辑是以辩证法认识论的世界观为基础的逻辑学；形式逻辑主要是对人的思维形式结构和规律进行研究的类似于语法的一门工具性学科。思维的形式结构主要包括概念、判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，这就是判断。由一个或几个判断推出另一判断的思维形式就是推理。研究推理有很多方法，用数学的方法研究推理的规律称为数理逻辑。所谓的数学方法就是引进一套符号体系的方法，所以数理逻辑又称符号逻辑，它是从量的方面来研究思维规律的。现代数理逻辑分为证明论、模型论、递归函数论、公理化集合论等。在此我们介绍的是数理逻辑最基本的内容：命题逻辑和谓词逻辑。第一
14、节 命题与命题联结词什么是命题：能够判断真假的陈述语句。命题的真值：真（T或1)和假（F或0）命题的种类：简单命题（原子命题）与复合命题命题的表示：大写或小写英文字母或带下标的英文字母。表示命题的字母称为命题标识符。命题常量与命题变元：表示确定命题的标识符成为命题常量；仅仅表示命题的的位置标志的标识符称为命题变元。注意：命题常量具有确定的真值；而命题变元可以标识任意命题，它不能确定真值，它本身也不是命题。常用的命题联结词1、否定定义：设P为一命题，P的否定是一个新的命题，记为P。若P为T，P为F，若P为F，P为T。2、合取定义：设P、Q是两个命题，P与Q的合取是一个复合命题，记为PQ。当且仅当
15、P，QP、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称为后件。条件联结词与自然语言中的“如果那么”
16、类似，但也不尽相同。善意的推断二元运算5、双条件定义：给定两个命题P、Q，它们的双条件命题是一个复合命题，记为PQ。当且仅当P、Q的真值相同时，PQ为T，否则PQ为F.注：双条件联结词与自然语言中的“当且仅当”，“充分必要”类似，但也不尽相同。二元运算命题联结词除了上述五个之外，还有不可兼析取、条件否定、与非、或非联结词。在一个复合命题中往往含有多个命题联结词，其运算的次序是：、第二节 命题公式及其分类直观地说，由命题变元、命题常量、命题联结词、括号组成的一个有意义的式子成为命题公式。定义：命题常量、命题变元是命题公式如果A是命题公式，则A是命题公式如果A、B是命题公式，则AB、AB、AB、A
17、B也是命题公式只有有限次地应用 产生的符号串才是命题公式。命题公式的赋值：命题公式的分类：重言式、矛盾式、可满足式第三节 等值演算等值的概念：设A，B是两个命题公式，p1，p2，pn为出现在A，B中的所有的命题变元，如果对p1，p2，pn的任何一种真值指派，A，B的真值都相同，则称A，B是等价（或等值）的。记为AB验证命题公式等值常用的方法有：真值表法、蕴含法、公式法（直接证法）。1、真值表法：例：证明AB(AB)(BA)2、蕴含法：定理1：设A，B是两个命题公式，则AB当且仅当AB为永真式。蕴含的定义：定义2：如果AB为永真式，则称A蕴含B，记为AB蕴含常见的性质：1、自反性 2、传递性 3
18、、如果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、证明：(PQ)(P Q)P2、证明：(PQ)(Q R)(P Q)R对偶式：对偶的概念：对偶定理：设A，B是命题公式，如果A B，则A*B*第四节 主析取范式与
19、主合取范式命题公式的规范化1、命题联结的归约：最小命题联结词组2、命题范式定义1：一个命题公式称为合取范式，如果它具有如下形式：A1 A2 An，其中A1，A2，An都是由命题变元或其否定所组成的析取式。定义1：一个命题公式称为析取范式，如果它具有如下形式：A1 A2 An，其中A1，A2，An都是由命题变元或其否定所组成的合取式。求一个命题公式的析取或合取范式的步骤：化归：将命题公式中的联结词化归为，移非：利用狄.摩根律，将求非符号移到命题变元的前面。归约：利用分配律将之化为析取或合取范式。例子：1、(pq)r)p2、（p q)(p q)注：一个命题公式的析取或合取范式并不是唯一的。主析取范
20、式与主合取范式定义：n个命题变元的合取式，称为布尔小项或合取，如果每个命题变元或其否定不能同时出现，但二者必须出现且仅出现一个。注：n个命题变元构成的布尔小项有2n个布尔小项的编码：命题变元-1，其否定-0布尔小项的常见性质：1、每个小项当其真值指派与编码相同时，其真值为1，在其余2n-1中指派情况下均为0。2、任意两个不同的小项合取式为0。3、全体小项的析取式为1。定义：对于给定的命题公式，如果有一个等价公式，它仅有小项的析取所组成，则该等价式称为原式的主析取范式。定理：在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。证明：略命题公式的主析取范式的求法1、真值
21、表法例1：求命题公式PQ，P Q，(PQ)的主析取范式。求命题公式(PQ)(P R)(Q R)的主析取范式2、公式法基本步骤：1、化归为析取范式2、合并同类同类项，去掉永假项。3、对合取项补入没有出现的命题变元，即添加PP项，然后利用分配律展开公式。例子：求P(P Q)(Q P)的主析取范式。注：对于一个命题公式的主析取范式，如将其命题变元的个数及出现次序固定后，则此公式的主析取范式是唯一的。类似于主析取范式，也有主合取范式。定义：n个命题变元的析取式，称为布尔大项或析取，如果每个命题变元或其否定不能同时出现，但二者必须出现且仅出现一个。注：n个命题变元构成的布尔 大项有2n个布尔大项的编码：
22、命题变元-0，其否定-1布尔大项的常见性质：1、每个大项当其真值指派与编码相同时，其真值为0，在其余2n-1中指派情况下均为1。2、任意两个不同的大项析取式为1。3、全体大项的合取式为0。定义：对于给定的命题公式，如果有一个等价公式，它仅有大项的合取所组成，则该等价式称为原式的主合取范式。定理：在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。证明：略求一个命题公式的主和取范式的方法，也有真值表法与公式法。其中公式法也分为三个步骤：1、化归为合取范式2、合并同类项，去掉永真项。3、对析取项补入没有出现的命题变元，即添加PP项，然后利用分配律展开公式。例子：1、求(
23、PQ)(P R)的主合取范式。2、求(P Q)R的主合取范式。第五节 命题逻辑的推理理论定义：设A,C是两个命题公式，如A C为一重言式，即AC，则称C是A的有效结论，或C可以由A逻辑推出。注：通常情况下，前提可能有若干个，即：H1 H2 Hn C从定义可以看到，推理正确并不能保证结论为真，这与现实中的推理有所不同。如何验证命题逻辑的推理，通常有以下三种方法：真值表法、直接证法、间接证法（反证法）。1、真值表法：分析验证的方法例：一份统计表的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表的错误不是由于材料不可靠，所以这份统计表是由于计算有错误。2、直接证法直接证法就是由一组前提，利
24、用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效结论。在推演的过程中，还需要用到以下两个规则：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作为一个前提加以引用，推出一个矛盾式。例：证明AB,(BC)A证明：PQ,PR,QSSRCP规则：欲证H1H2Hn(RC),可以将R作为一个逻辑前提加以引用，证明C为真即可。（分析理由）例子：证明:A(BC),DA,B
25、DC证明：AB,CBAC应用简介第二章谓词逻辑为什么要引入谓词逻辑：第一节谓词的概念与表示在一个简单命题中，表示主语的词称为客体或个体，表示谓语的词称为谓词。通常客体是可以独立存在的对象，它可以是一个具体的事物，也可以是抽象的概念。谓词一般是用来刻划个体的性质或个体之间的关系。对个体我们通常用小写字母表示，而谓词我们则用大写字母表示。一个命题我们就可以用A(b)这种形式来表示，叫做谓词填式。用来表示特定个体的小写字母我们将之称为个体常量，用来表示某一些个体的小写字母称为个体变量。一个个体变量的取值范围叫做个体域或论域。将考虑的所有的事物组成的个体域，称为全总个体域。从前面我们可以看到，在一个谓
26、词填式中可以含有个体变元。定义：有一个谓词，若干个个体变元组成的表达式，称为命题函数或谓词变项。注：、在一个谓词变项中，根据其所含变量的个数，有一元谓词,，n元谓词。其中0元谓词是命题。、在谓词变项中，如果含有变元，则它不是命题，只有对其中的变元都取特定的个体时，它才表示确定的命题。量词使用上述概念有时还不能用符号很好地表达日常生活中的各种命题，例如：S(x)表示x是大学生，x的个体域是某单位职工。则可以理解为某单位的职工都是大学生，或某单位的有些职工是大学生。为避免这种理解上的混乱，我们引入量词，以刻划“所有”、“有一些”的不同概念。、全称量词用来表达“所有的”,“每一个”，“任一个”等的量
27、词。例子：所有人都要呼吸：(x)M(x)H(x)每个学生都要参加考试：(x)P(x)Q(x)2、存在量词 用以表示“有一些”，“至少有一个”等概念的量词。例子：有些人是聪明的：有的人早饭吃面包：全称量词与存在量词统称为量词。在上面的例子中，每个由量词确定的表达式，都与个体域有关。我们通常总是在全总个体域中考虑问题，因此就要通过相应的谓词对个体变元的取值范围加以说明，这就是特性谓词。一般地，对全称量词，特性谓词常做蕴含的前件；对存在量词，特性谓词常作合取项。L(2,3)=L(3,2)=0在解释I下，求下列谓词公式的真值定义：给定谓词公式A,如对任何一种解释，A的真值都为真，则称A为永真的。如对任
28、何一种解释，A的真值都为假，则称A为永假的。如至少有一种解释，使得A的真值为真，则称A为可满足的。命题公式的推广：命题公式的等价公式和蕴含式均可推广到谓词演算中来。例如：例：设P(x)表示x今天来校上课，P(x)表示x今天没来校上课。比较可以得到：P(x)P(x)P(x)P(x)量词作用域的扩张与收缩：B)B B)BB)B B)B量词与命题联结词之间的一些等价式：B(x)B(x)B(x)B(x)前束范式定义：一个谓词公式如果量词均在全式的开头,它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式。基本形式：定理：任意一个谓词公式，均和一个前束范式等价。例子第四节 谓词演算的推理理论常用的等值
29、式以及牵涉到量词推理规则例子：略第三章 集合、关系、映射第一节 集合的基本概念集合的定义：若干个确定事物的全体。注：若干个：可以是有限也可以是无限。组成集合的事物成为集合的元素。元素的确定性：集合的表示：常用集合的习惯表示法：子集与幂集：第二节 集合的基本运算交、并、补、差、对称差。第三节 笛卡尔积与关系序偶：有序偶与无序偶定义：设A,B是两个集合，有所有序偶(a,b)，其中aA,bB，构成的集合称为集合A与B的笛卡尔积，记为：AB注：A=一般地：ABBA (AB)C A(BC)推广：A1A2 An=(a1,a2,an)/aiAiAAA(n个）记为：An关系的定义：AB的任一子集称为是A到B的
30、一个关系。注：空关系、全关系A上的二元关系常用关系说明关系的定义域、值域、域关系的交、并、补、差仍是关系。第四节 关系的表示与关系的性质关系的两种表示方法：1、关系的图表示设R是有限集合A到B一个关系将集合A,B中的元素在平面上用结点表示如果集合A中的元素a与集合B中的元素b有关系R，则从a到b联结一条有向弧线。特别地：n元集合A上的一个二元关系，只需在平面上划出n个结点即可。例：略2、关系的矩阵表示设A=a1,a2,am,B=b1,b2,bn是两个集合，R是A到B个一个关系，则mn矩阵MR=其中rij=称为关系R的mnmmnnrrrrrrrrr.212222111211jijiRaRaaa1
31、0?关系矩阵。例：略关系的性质:引入：例子定义：设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)自反与反自反并不是非此即彼的关系，同样对陈与反对称也不是相互对立的。例：设A=1,2,3，1)R=(1,1),(1,2),(3,2),(2,3),(
32、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,R1,R2均为A到B的二元
33、关系，则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定义：设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的关系，则M R1 R2=M R1M R2证明：略注：1)布尔乘例题：略定理：设R1,R2,R3分别为集合AB,B C,CD的关系
34、，则（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)=RR-13)t(R)=RR2 R3 证明：注：当A为n元集合时,t(R)=RR2 Rn例题：设A=a,b,c，R=(a,b),(
35、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满足自反性、对称性、传递性。例题：人群中的同姓关系；整数集合上的同余关系由同余关系引入集合的划分，等价类以及二者之间的关系。商集：设R是集合A上的一个等价关系，则A关于R所产生的划分的所有的等价类
36、做成的集合，称为集合A关于等价关系R的商集，记为：A/R例题：略第七节 偏序关系定义：设R是非空集合A上的关系，如果R满足自反性、反对称性、传递性，则称R是一个偏序关系。例题：略注：1)一个偏序关系通常用“”符号表示。2）集合A与其上的一个偏序关系“”组成的序偶称为偏序集。例题：整除关系、小于等于关系、包含关系等偏序集的HASSE图：1)元素用结点表示2)如果元素x覆盖y，则将x画在y的上方，并且在它们之间画一线段。注：因为偏序集的每个结点都有环，所以在画Hasse图时，可以省略。例题：略偏序集中的特殊元素1、极大元与极小元定义：设是偏序集，BA，b B，如果B中不存在元素x，使得xb,且bx
37、（xb)，则称b为B的极大(小）元。例：略2、最大元与最小元定义：设是偏序集，BA，b B，如果对B中任意元素x，都有xb（bx)，则称b为B的最大（小）元。例：略3、上界与下界定义：设是偏序集，BA，a A，如对x B，有xa(ax)，则称a是B的一个上(下)界例：略4、上确界与下确界定义：设是偏序集，BA，a是B的一个上（下）界，如对B的任意上（下）界x，都有ax(xa)，则称a是B的上(下)确界例：略例题：集合A=a,b,c的幂集关于包含关系 分析：在Hasse图中，几种特殊元素所处的位置。另外几种常见的重要的序集：定义：设A是一个非空集合，如果A上的关系R满足反自反性和传递性，则称R是
38、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：证明良序集必是全序集，反之则未必第八节 函数定义：设X，Y是两个集合，f是X到Y的一个关系，如果对任意的xX，都存在唯一的yY，使得(x,y)f，则称关系f是X到Y
39、的一个函数。记为：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)Y3)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是满射。例题：略定义：
40、假设f:XY，如果对任意x,yX，当xyf(x)f(y)，则称f为单射。例题：略定义：假设f:XY，如果f既是满射又是单射，则称f为双射或一一映射。例题：略第九节逆函数和复合函数函数作为一个特殊的关系，我们可以求其逆关系，但是其逆关系未必是函数。例如：略因此，对函数求逆。要保证其逆也是一个函数，需要规定一些条件。定理：设f:XY是一个双射函数，则f-1是YX的双射函数。证明：略定义：设f:XY是一双射函数，称YX的双射函数f-1是f的逆函数。例：略定理：设f:XY是一双射函数，则 (f-1)-1=f证明：略利用关系的复合我们可以给出函数的复合定义：设函数f:XY，g:YZ，则g f=(x,z)
41、/yY,使得y=f(x),z=g(y)称为g对f的左复合例如：略定理：设函数f:XY，g:YZ，则g对f的左复合g f是一个XZ的函数。证明：略注：根据复合函数的定义，显然有g f(x)=g(f(x)性质定理：1)若g,f是满射，则g f是满射。2）若g,f是单射，则g f是单射。3）若g,f是双射，则g f是双射。证明：略定理：设函数f:XY，则f=f IX=IY f定理：设双射函数f:XY，则f-1 f=IXf f-1=IY证明：略定理：设f:XY，g:YZ均为双射函数，则：(g f)-1=f-1 g-1证明：略第四章 代数系统第一节 代数运算及其性质引入定义：一个AB到D的映射，称为是A
42、B到D的代数运算。注：代数运算的表示一般地，如果 是AB到D的代数运算，未必是BA到D的代数运算一个AA到A的代数运算 叫做A上的代数元算或A上的二元运算或A对运算 是封闭的凯莱运算表代数运算可能满足的运算规律：结合律、交换律、幂等律、分配律、吸收律。代数结构：一个带有运算的集合称为代数结构或代数系统代数结构中可能存在的特殊元素：零元、单位元（幺元）、可逆元第二节 子代数与积代数定义：设为一代数系统，A1A，如果A1关于运算是封闭的，则称是的子代数。注：具有n个运算的代数系统的子代数的定义例：略定义：设与是两个代数系统，在AB中规定运算：(a1,b1)(a2,b2)=(a1 a2,b1*b2)
43、，则也是一个代数系统，称为与的积代数注：具有多个运算的代数系统的积代数的概念。例：略积代数的性质：定理：设与是两个代数系统，是他们的积代数如果,*满足交换律，则也满足交换律如果,*满足结合律，则也满足结合律如果,*满足幂等律，则也满足幂等律如果与都有单位元，则也有单位元。如果与都有零元，则也有零元。证明：略定理：设与是两个代数系统，是它们的积代数如1对2，*1对*2分别满足分配律，则1对2也满足分配律如1对2，*1对*2分别满足吸收律，则1对2也满足吸收律第三节 代数系统的同态与同构引入定义：设与是两个代数系统，是A到B映射，如对a1,a2A,有(a1a2)=(a1)*(a2)，则称是代数系统
44、到的同态映射。注：具有多个运算的代数系统的同态定义特殊的同态映射定义：设与是两个代数系统，是A到B满射，如对a1,a2A,有(a1a2)=(a1)*(a2)，则称是代数系统到的同态满射。此时也称与是同态的。记为：同态满射的性质定理1：设如满足交换律，则也满足交换律如满足结合律，则也满足结合律如满足幂等律，则也满足幂等律如有单位元，则有单位元如有零元，则有零元如有单位元，aA在A中有逆元，则a的象在B中也有逆元，且a的逆元的象就是a的象的逆元。证明：略定理2：设如1对2 满足分配律，则*1对*2也满足分配律如1对2 满足吸收律，则*1对*2也满足吸收律定义:设与是两个代数系统，是A到B双射，如对
45、a1,a2A,有(a1a2)=(a1)*(a2)，则称是代数系统到的同构映射。此时也称与是同构的。记为：注：同态具备的性质同构肯定具备。反之则未必自同态与自同构例:略两个同构的代数结构称之为是代数相等的。第四节 半群与独异点定义：设是一代数系统，如果运算满足结合律，则称是半群。例：略定义：一个具有单位元的半群称为幺半群或独异点。例：略在独异点中我们可以进一步规定：a2=aa,an+1=ana,a0=e,a-n=(a-1)n定义：是半群，BS，如果也是半群，则称是子半群。注：验证方法定义：是独异点，TS，如果也是半群，且eT，则称是子独异点。第五节 群与子群定义：设为一代数系统，如果满足：1、G
46、对运算是封闭的2、运算满足结合律3、有单位元4、对aG在G中有逆元则称是群。例：略有限群、无限群以及群的阶定义：如果在群中交换律成立，则称是交换群或Abel群例：略循环群的引入：例子定义：设是群，aG，如果G中任意一个元素均可以表示为a的方幂，则称是由a所生成的一个循环群，记为G=(a)，其中a叫做循环群G的一个生成元。注：循环群的生成元一般不唯一。有限循环群与无限循环群的构造群的性质：定理1：在群中，对a,bG，方程ax=b与ya=b在G中都有唯一解定理2：在群中左、右消去律成立。即：ab=acb=c，ba=cab=c定理3：在群中，单位元是唯一的幂等元定理4：在群中，(a-1)-1=a，(
47、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,+,中对+满足分配律则称R,+,是一个环。例：略注：在环中，关于加法：单位元我们通常用记之；元素a的逆元称为a的负元，用-a记之；a+a+a na;a+(-b)a-b环中的
48、运算性质 a+0=0+a=a-a+a=a+(-a)=0-(-a)=a-(a+b)=-a-b0a=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给出与数的运算不同的例子几种特殊类型的环：、交换环、有单位元环、无零因子环、整环、除环与域第七节格与布尔代数引入偏序格的定义：设是一个偏序集，如果L中任意两个元素都有上、下确界，则称偏序集是格。例：略在格中,我们可以规定：ab=supa,b ab=infa,b则，是格的两个二元运算，即：是一个
49、代数系统。该代数系统满足定理：在格所诱导的代数系统中，结合律、交换律、幂等律、吸收律成立。证明：略命题：设是一个代数系统，其中,都是二元运算且满足吸收律，则,都满足幂等律。证明：略定理2：设是一个代数系统，其中,都是二元运算且满足结合律、交换律、和吸收律，则L上存在偏序关系“”，使得是一个格。证明：略定义：设是一个代数系统，其中,都是二元运算且满足结合律、交换律、和吸收律，则称是一个代数格。注：在偏序格在格中,我们可以规定：ab=supa,b ab=infa,b，则是一个代数格，称为是由所诱导的代数格。如在代数格中，规定：abab=a(或ab=b)，则是一个偏序格，称为是由代数格所诱导的偏序格
50、。格的性质：p.p1 设是一个格，对a,b,cL，如果ab,cd，则acbd,acbdp.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是L1到L2的映射，如果对任意的a,bL1有f(a1b)=f(a)2f(b),f(a1b)=f(a)2f(b),则称f是
