math-chap7-7.离散数学复习.ppt

庄伯金 ,1,复习,庄伯金 ,2,答疑安排,答疑时间：周一上午、周二上午、周四下午、周一-周五中午 答疑地点：教二214 课件下载地址：,庄伯金 ,3,命题逻辑,命题逻辑的基本概念 常见联结词 命题逻辑等值演算 命题逻辑的推理,庄伯金 ,4,命题的基本概念,命题的定义 能判断真假的陈述句 命题的两个关键要素 必须是陈述句 能明确地判断真假 命题的真值 判断为正确的命题，其真值为真（1）； 判断为错误的命题，其真值为假（0）。,庄伯金 ,5,复合命题及联结,复合命题：由简单命题通过联结词联结而成的命题。 常见联结词 否定联结词 合取联结词 析取联结词 蕴涵联结词 等价联结词,庄伯金 ,6,基本复合命题真值表,庄伯金 ,7,公式的赋值,定义 设A为一命题公式，p1, p2, , pn, 为所有在A中出现的命题变项。给p1, p2, , pn指定一组真值，称其为A的一个赋值或解释。 若指定的一组赋值使A的真值为真，则称这组值为A的成真赋值。 若指定的一组赋值使A的真值为假，则称这组值为A的成假赋值。 将一个命题公式在所有赋值下的情况列成表，称为这个公式的真值表。 n个命题变项共有2n组赋值。,庄伯金 ,8,重言式（永真式）： 所有的赋值都是A的成真赋值。 矛盾式（永假式）： 所有的赋值都是A的成假赋值。 可满足式： 至少存在一组赋值使A为真。,庄伯金 ,9,基本等值规律(1),双重否定律 AA 等幂律 AAA AAA 交换律 ABBA ABBA 结合律 A(BC)(AB)C A(BC)(AB)C,庄伯金 ,10,基本等值规律(2),分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 德.摩根律 (AB)AB (AB)AB 吸收律 A(AB)A A(AB)A,庄伯金 ,11,基本等值规律(3),零律 A11 A00 同一律 A0A A1A 排中律 AA1 矛盾律 AA0,庄伯金 ,12,基本等值规律(4),蕴涵等值式 ABAB 等价等值式 AB(AB)(BA) (AB)(BA) 假言易位 ABBA 等价否定等值式 ABAB 归谬论 (AB)(AB)A,庄伯金 ,13,范式的概念,命题公式的规范表示方法 析取范式:由有限个简单合取式构成的析取式 合取范式:由有限个简单析取式构成的合取式 文字：命题变项及其否定式统称文字 简单析取式 仅有有限个文字构成的析取式 简单合取式 仅有有限个文字构成的合取式 定理： 一个简单析取式是重言式当且仅当它同时含某个命题变项及其否定式 一个简单合取式是矛盾式当且仅当它同时含某个命题变项及其否定式,庄伯金 ,14,范式存在定理,定理：任一命题公式都存在与之等值的析取范式（合取范式）。 求范式的步骤 利用蕴涵等值式和等价等值式消去联结词 、。 用双重否定律消去否定联结词，利用德.摩根律将否定联结词内移。 利用分配律求析取范式或合取范式。,庄伯金 ,15,极小项与极大项,极小项的定义 在含n个命题变项的简单合取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现1次，且第i个命题变项或否定式出现在从左起的第i位上。 每个极小项仅有一个成真赋值 每个极小项的成真赋值均不相同 极大项的定义 在含n个命题变项的简单析取式中，如果每个变项与其否定式不同时存在，但两者之一恰出现1次，且第i个命题变项或否定式出现在从左起的第i位上。 每个极大项仅有一个成假赋值 每个极大项的成假赋值均不相同 n个命题变项共可形成2n个极小项和2n个极大项。,庄伯金 ,16,主析取范式与主合取范式,主析取范式的定义 若A的命题公式由若干个极小项进行析取构成，则称该析取范式为A的主析取范式 从主析取范式中很容易得到成真赋值 主合取范式的定义 若A的命题公式由若干个极大项进行合取构成，则称该合取范式为A的主合取范式 从主合取范式中很容易得到成假赋值 定理：任何命题公式都存在与之等值的主析取（合取）范式，且唯一。,庄伯金 ,17,主析取范式的求解方法(1),用等值演算求得析取范式 依次扫描析取范式中的每个简单合取式B 若B为极小项，则继续扫描下一个 若B不为极小项，将不含的命题变项p及其否定式p用等值变换添入BB(pp) (Bp)(Bp) 消去重复出现的命题变项、极小项和矛盾式。,庄伯金 ,18,主析取范式的求解方法(2),根据公式构造真值表 写出每个公式成真赋值对应的极小项 将极小项进行析取，即得主析取范式,庄伯金 ,19,主合取范式的求解方法(1),用等值演算求得合取范式 依次扫描合取范式中的每个简单析取式B 若B为极大项，则继续扫描下一个 若B不为极大项，将不含的命题变项p及其否定式p用等值变换添入BB (pp) (Bp)(Bp) 消去重复出现的命题变项、极大项和重言式。,庄伯金 ,20,主合取范式的求解方法(2),根据公式构造真值表 写出每个公式成假赋值对应的极大项 将极大项进行合取，即得主合取范式,庄伯金 ,21,推理的形式结构,设两命题公式A、B，若AB为重言式，则称A蕴涵B，记为AB。 设A1、A2、.、An、B为命题公式，若A1A2. An B，则称B为A1、A2、.、An的逻辑结论或有效结论，也称B可由一组前提A1、A2、.、An逻辑推出。记为A1，A2，.，AnB。 正确推理的本质是A1A2. AnB为重言式。 当A1A2. An为假时，不论B是真是假， A1A2. AnB均为真。所以B为有效结论并不意味B为真。,庄伯金 ,22,推理的基本方法,简单证明法： 证明A1A2. AnB是重言式，即A1A2. AnB1。 真值表法 等值演算法 主析取范式法 例：若a能被4整除，则a能被2整除。因为a能被2整除，所以a能被4整除。,庄伯金 ,23,推理的基本方法(2),直接构造证明法 由给定的一组前提出发，利用推理规则逐步演算得到结论。 常用推理规则 前提引入规则：在证明过程的任何步骤都可以将前提引入使用 结论引入规则：在推理中，若已证出结论B，则B可以引入到以后的推理中作为前提使用 置换规则：命题公式中任何子公式都可以用等值公式置换 化简规则： AB A， AB B 附加规则： AAB,庄伯金 ,24,常用推理规则,假言推理规则：AB，AB 拒取式规则：AB，BA 析取三段论：AB，AB 假言三段推理：AB，BCAC 等价三段论：AB，BCAC 构造性二难规则：AB，CD，ACBD 破坏性二难规则： AB，CD，BDAC 合取引入规则：A，BAB,庄伯金 ,25,推理的基本方法(3),间接构造证明法 附加前提证明法 A1A2. AnBC A1A2. AnB C 归谬法 A1A2. AnB A1A2. AnB 0,庄伯金 ,26,谓词逻辑,谓词逻辑 谓词公式 谓词的解释 谓词逻辑等值式、范式,多媒体中心 庄伯金 ,27,谓词逻辑,简单命题之间的内在联系需要通过进一步分析原子命题中主、谓等之间的关系。 个体：可以独立存在的客观实体称为个体。 谓词：刻画个体具有的性质或个体之间关系的词。 量词：表示个体常项或变项之间数量关系的词。 全称量词：一切的、所有的、每一个、任意的、都.。符号化为“”。表示个体域里的所有个体关系。 存在量词：存在、有一个、有的、至少有一个.。符号化为“”。表示个体域里有的个体关系。,多媒体中心 庄伯金 ,28,量词,量词需要注意个体域的问题。在不同的个体域内，命题的真值可能不同。 例：存在x，使得x+3=2。 个体域为自然数 个体域为整数 特性谓词：将某类个体从个体域中区分出来的谓词。 M(x)：x是人； F(x)：x是鱼； Z(x)：x是整数。,多媒体中心 庄伯金 ,29,命题符号化,明确命题个体域，分别找出个体常项、个体变项、量词和谓词； 按照命题的意思用逻辑联结词将其组合； 注意： 引入特性谓词时，全称量词的特性谓词作为命题的前提引入，而存在量词的特性谓词作为命题的合取项引入； 多个量词同时出现，需要注意量词的顺序不能随意颠倒。,多媒体中心 庄伯金 ,30,合式公式和变项辖域,定义 (1)原子公式是合式公式； (2)若A是合式公式，则(A)也是合式公式 (3)若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式； (4)若A是合式公式，则xA，xA也是合式公式； (5)只有有限次的应用(1)-(4)得到的符号串才是合式公式。 定义： xF，xF中，x称为指导变项，F称为相应量词的辖域。辖域中x的所有出现称为约束出现，x称为约束变项，F中不是约束出现的其他变项称为自由变项。,多媒体中心 庄伯金 ,31,谓词公式的解释,定义：为使公式成为真值确定的命题而指定的有关规定，称为谓词公式的一个解释。 解释I的组成 特定的个体域D D中一部分特定元素 D上每个函数变项所取得的具体函数 D上每个谓词变项所取的具体谓词,多媒体中心 庄伯金 ,32,谓词公式的分类,谓词公式的分类： 如果A在任何解释下都为真，则称A为永真式（逻辑有效式）。 如果A在任何解释下都为假，则称A为永假式（矛盾式）。 若至少存在一组A的解释使A为真，则称A为可满足式。 代换实例：设A0是含命题变项p1,p2,.,pn的命题公式，A1,A2,.,An是n个谓词公式。用Ai代换A0中的每一个pi，所得的公式A称为A0的代换实例。 定理： 命题公式中的重言式的代换实例在谓词公式中为逻辑有效式； 命题公式中的矛盾式的代换实例是谓词公式中仍为矛盾式。,多媒体中心 庄伯金 ,33,谓词逻辑等值式,等值式的定义：设谓词逻辑中任意两个公式A和B，若AB是是逻辑有效式，则称A与B为等值式。记作AB。 原命题等值式的代换实例都是等值式。 消去量词等值式：设个体域Da1,a2,.,an xA(x)A(a1)A(a2).A(an) xA(x)A(a1)A(a2).A(an) 量词否定等值式 xA(x) xA(x) xA(x) xA(x),多媒体中心 庄伯金 ,34,谓词逻辑等值式,量词辖域扩张和伸缩等值式 x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x) x(BA(x)BxA(x),多媒体中心 庄伯金 ,35,谓词逻辑等值式,量词分配等值式 x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x) 量词交换等值式 xyA(x,y) yxA(x,y) xyA(x,y) yxA(x,y),多媒体中心 庄伯金 ,36,前束范式,定义：设A为谓词逻辑公式，若A具有形式Q1x1Q2x2.QnxnB，其中Qi 为或 ，B为不含量词的公式。 存在定理：任何谓词逻辑公式都存在与之等值的前束范式。,庄伯金 ,37,集合,集合的基本概念 集合之间的关系 集合的基本运算 集合中元素的计数,庄伯金 ,38,集合的基本概念,集合的描述：一些可确定的可分辨事物构成的整体。 集合常用大写字母来表示。 元素：属于集合的特定的事物。常用小写字母表示。,庄伯金 ,39,集合间的关系(1),子集：设A、B为集合，如果B中的每个元素都是A中的元素，则称B为A的子集。亦称为B包含于A，或A包含B，记作BA或AB。即有BAx(xB xA) 相等：设A、B为集合，如果AB且BA，则称A与B相等，记作AB。即有：ABABBA 真子集：设A、B为集合，若BA且BA，则称B为A的真子集，记作BA。即有BAx(xB xA)x(xAxB)。,庄伯金 ,40,集合,定义：不含任何元素的集合叫做空集，记作。 定理：空集是任意集合的子集。 推论：空集是唯一的。 推论：任意非空集合至少有两个子集。 定义：设A为集合，把A的全体子集构成的集合叫做A的幂集，记作P(A)。 定义：在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E。在文氏图中，用矩形框表示。,庄伯金 ,41,集合的基本运算,并运算：设A、B是任意两个集合，所有属于A或者属于B的元素组成的集合，称为A与B的并集，记作AB。 ABx|xAxB。 交运算：设A、B是任意两个集合，由A与B的公共元素组成的集合，称为A与B的交集，记为AB。 ABx|xAxB。 相对补集：设A、B是任意两集合，属于A而不属于B的元素组成的集合，称为B对于A的补集，也叫B对于A的相对补集，记作A-B。 A-B=x|xAxB。,庄伯金 ,42,集合的基本运算,绝对补集：设A是集合，A对于全集E的相对补集，称为A的绝对补集，记作A。 A = E-A = x|xExA = x|xA。 对称差集：设A、B是任意两集合，所有属于A或属于B，但又不同时属于A和B的元素组成的集合称为A与B的对称差集合，记作AB。 AB= x|(xAxB)xAB AB=(AB)-(AB)= (A-B)(B-A),庄伯金 ,43,集合的运算律(1),幂等律 AA=A AA=A 交换律 AB=BA AB=BA 结合律 (AB)C=A(BC) (AB)C=A(BC),庄伯金 ,44,集合的运算律(2),同一律 A=A AE=A 零律 AE=E A= 分配律 A(BC)=(AB)(AC) A(BC)= (AB)(AC),庄伯金 ,45,集合的运算律(3),吸收律 A(AB)=A A(AB)=A 双重否定律 (B)=B 排中律 A(A)=E 矛盾律 A(A)=,庄伯金 ,46,集合的运算律(3),德.摩根律 (AB)=(A)(B) (AB)=(A)(B) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) 差分运算律 A-B=A(B)=A-(AB) (A-B)B= A(B-C)=(AB)-(AC),庄伯金 ,47,集合的运算律(4),对称差运算律 AB=BA A=A AA= (AB)C=A(BC),庄伯金 ,48,集合中元素的计数,基数：集合A中元素的个数，记作|A|或card A。 有穷集：基数是有限的集合； 无穷集：基数是无限的集合。 有穷集的基数可以通过文氏图进行计算得出。 先将集合中对应的性质确定文氏图中相应集合 将已知集合的基数填入相应的区域 逐步求得其他区域的基数,庄伯金 ,49,容斥原理,定理：设有穷集合A、B，基数分别为|A|和|B|，则有|AB|=|A|+|B|-|AB|。 定理：设A1,A2,.,An为n个有穷集合，其中，集合Ai的基数为|Ai|，则有：,庄伯金 ,50,容斥原理(2),设S为有穷集合，P1,P2,.,Pn是n条性质，令Ai表示S中具有性质Pi的元素构成的集合，则S中不具有性质P1,P2,.,Pn的元素个数是：,庄伯金 ,51,关系,二元关系的基本概念 关系的运算 关系的性质 关系的闭包 等价关系与偏序关系 函数的概念与性质,庄伯金 ,52,有序对与笛卡儿积的概念,定义(有序对)：由两个元素x和y，按一定顺序排列成的二元组。称为有序对或序偶，记作。 x为第一元素，y为第二元素； 有顺序的要求：当xy时，； =x=uy=v。 定义(笛卡儿积)：设A,B为集合，用A中的元素为第一元素，B中的元素为第二元素构成有序对的集合，称为A和B的笛卡儿积，记作AB。 AB=|xAyB,庄伯金 ,53,二元关系的概念,定义(二元关系)：如果一个集合满足以下条件之一：(1)集合非空，且它的元素都是有序对；(2)集合是空集，则称该集合为一个二元关系(简称关系)，记作R。 二元关系是集合 二元关系是有序对的集合 若R，可记为xRy。 定义：设A和B为集合，AB的任何子集所定义的二元关系叫做从A到B的二元关系；若AB，则叫做A上的二元关系。,庄伯金 ,54,二元关系的域,定义域：R中所有有序对的第一元素构成的集合称为R的定义域，记作domR。 值域：R中所有有序对的第二元素构成的集合称为R的值域，记作ranR。 域：R的定义域和值域的并集称为R的域，记作fldR。 例：R=,庄伯金 ,55,关系的表示方法,集合表达式 关系矩阵 关系图,庄伯金 ,56,关系的运算,逆关系：设R为二元关系，R的逆关系(简称R的逆) 记作R-1，其中R-1=|R。 右复合：设F和G为二元关系，G对F的右复合记作FG，其中FG=|t(FG)。 左复合：设F和G为二元关系，G对F的左复合记作FG，其中FG=|t(GF)。,庄伯金 ,57,关系的运算,限制：设R为二元关系，A为集合，R在A上的限制记作RA，其中RA=|RxA。 RA的值域称为A在R下的像，记作RA，其中RA=ran(RA)。 幂：设R为A上的关系，n为自然数，则R的n次幂定义为： R0=|xA=IA Rn+1=RnR 基本的集合运算,庄伯金 ,58,关系的性质,自反性：若x(xA(x,x)R)，则称R在A上具有自反性； 反自反性：若x(xA(x,x)R)，则称R在A上具有反自反性； 对称性：若xy(x,yA(x,y)R(y,x)R)，则称R是A上的对称关系； 反对称性：若xy(x,yA(x,y)R(y,x)R x=y)，则称R是A上的反对称关系； 传递性：xyz(x,y,zA(x,y)R(y,z)R(x,z)R)，则称R是A上的传递关系。,庄伯金 ,59,五种性质成立的充要条件,定理：设R为A上的二元关系，则 R在A上自反当且仅当IAR； R在A上反自反当且仅当RIA=； R在A上对称当且仅当R=R-1； R在A上反对称当且仅当RR-1IA； R在A上传递当且仅当RRR,庄伯金 ,60,关系的闭包,定义：设R是A上的关系，R的自反（对称或传递）闭包是A上的关系R，并满足 R是自反的（对称的或传递的）； RR； 对A上任何一个包含R的自反（对称或传递）关系R，RR； R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。,庄伯金 ,61,闭包的构造,定理：设R为A上的关系，则有 r(R)=RIA； s(R)=RR-1 t(R)=RR2R3.,庄伯金 ,62,等价关系与等价类,定义：设R为非空集合A上的关系，如果R满足自反性、对称性和传递性，则称R为A上的一个等价关系。若R，则称x等价于y。 设R为非空集合A上的等价关系，xA，令xR=y|yAR，称xR为x关于R的等价类，简称为x的等价类，简记为x。 定理：设R为A上的等价关系，则 xA，x非空； x,yA，若R，则xy=； x,yA，若R，则x=y； x=A。,庄伯金 ,63,商集与集合的划分,定义：设R为非空集合A上的等价关系，以R的所有等价类为元素的集合称为A关于R的商集，记作A/R，即A/R=x|xA。 定义：设A为非空集合，若A的子集族满足： ； xy(x,y xyxy=)； =A。 则称为A的一个划分，称中的元素为A的划分块。 商集A/R是A的一个划分。,商集与集合的划分,定理：对于集合A的任何一个划分，存在A上的一个等价关系R，使得该划分为A关于R的商集A/R。反之亦然。,庄伯金 ,64,庄伯金 ,65,偏序关系,定义：设R为非空集合A上的一个关系，若R具有自反性、反对称性和传递性，则称R为A上的偏序关系，记作。如果，则称x小于或等于y。 定义：设R为非空集合A上的偏序关系，定义 x,yA，xyxyxy； x,yA，x与y可比xyyx。 定义：集合A和A上的偏序关系一起叫做偏序集，记作(A,)。 定义：设R为非空集合A上的偏序关系，如果x,yA，x与y都是可比的，则称R为A上的全序关系（或线序关系）。,庄伯金 ,66,偏序图的表示,哈斯图 排序：若xy，将x放在y的下方； 连线：x,yA，如果xy，且不存在z，使得xzy，则将x和y连线。,庄伯金 ,67,偏序集中的特殊元素,定义：设(A,)为偏序集，BA，yB， 若x(xByx)，则称y为B的最小元； 若x(xBxy)，则称y为B的最大元； 若x(xBxyx=y)，则称y为B的极小元； 若x(xByxx=y)，则称y为B的极大元。 定义：设(A,)为偏序集， BA，yA， 若x(xBxy)，则称y为B的上界； 若x(xByx)，则称y为B的下界； 令C=y|y为B的上界，则C的最小元为B的上确界； 令D=y|y为B的下界，则D的最大元为B的下确界。,庄伯金 ,68,代数系统,二元运算 代数常数 代数系统,庄伯金 ,69,二元运算,定义：设集合A，函数F:AAA称为A上的二元运算，简称为二元运算。 A上的任意两个元素都可以进行二元运算，且结果唯一； 运算的结果还在A内，即运算在A上封闭。 可以用, *, 等符号表示二元运算，称为算符。 交换律：设为集合A上的二元运算，如果对于任意的元素x,yA，都有xy=yx成立，则称运算在A上可交换。 结合律：设为集合A上的二元运算，如果对于任意的元素x,y,zA，都有(xy)z= x(yz)成立，则称运算在A上可结合。,庄伯金 ,70,二元运算的性质,分配律：设和*为集合A上的两个二元运算，如果对于任意的x,y,zA，都有x*(yz)=(x*y)(x*z)和(xy)*z=(x*z)(y*z)成立，则称运算*对可分配。 幂等律：设为A上的二元运算，如果对于任意的xA，都有xx=x，则称运算满足幂等律。 吸收律：设和*为集合A上两个可交换的二元运算，如果对于任意的x,yA，都有x(x*y)=x和x*(xy)=x成立，则称*和满足吸收律。,庄伯金 ,71,单位元,左单位元：设为A上的二元运算，元素elA，如果对任意的xA，都有elx=x，则称el为运算的左单位元或左幺元。 右单位元：设为A上的二元运算，元素erA，如果对任意的xA，都有xer=x，则称er为运算的右单位元或右幺元。 单位元：设为A上的二元运算，元素eA，如果e既为的左单位元又为的右单位元，则称e为的单位元或幺元。 定理：设为A上的二元运算，且运算存在左单位元el和右单位元er ，则运算存在单位元e，且e唯一。,庄伯金 ,72,零元,左零元：设为A上的二元运算，元素lA，如果对任意的xA，都有lx=l，则称l为运算的左零元。 右零元：设为A上的二元运算，元素rA，如果对任意的xA，都有xr=r，则称r为运算的右零元。 零元：设为A上的二元运算，元素A，如果既是左零元，又是右零元，则称为运算的零元。 定理：设为A上的二元运算，且运算存在左零元l和右零元r ，则运算存在零元，且唯一。,庄伯金 ,73,逆元,左逆元：设为A上的二元运算，e为的幺元，对于元素mA，如果存在ylA，满足ylm=e，则称yl为m的左逆元。 右逆元：设为A上的二元运算，e为的幺元，对于元素mA，如果存在yrA，满足myr =e，则称yr为m的右逆元。 逆元：设为A上的二元运算，对于元素mA，如果y既是m的左逆元又是m的右逆元，则称y是m的逆元。 定理：设为A上的可结合二元运算，A中存在幺元e且每个元素都有左逆元，则在A中，每个元素的左逆元也是该元素的右逆元，且每个元素的逆元唯一。,庄伯金 ,74,代数系统与子代数系统,定义：由非空集合A以及A上的运算*1,*2,.,*n所组成的系统称为一个代数系统，记作。 定义：设有代数系统，B是A的非空子集。如果A上的每个运算都在B上是封闭的，且A与B含有相同的代数常数，则称代数系统为代数系统的子代数系统，或称代数B为代数A的子代数。 最大的子代数：代数系统本身 最小的子代数：B为代数系统中所有代数常数构成的集合，且满足A上每个运算在B上封闭。 若BA，则代数B为代数A的真子代数。,庄伯金 ,75,积代数,定义：设V1=和V2=为两个代数系统，其中*和为二元运算，任意的,AB，AB上的二元运算定义为=，代数系统称为V1和V2的积代数或直积，记为V1V2。,庄伯金 ,76,同态与同构,定义：设两代数系统V1=和V2=，如果存在映射f:AB，对任意的x,yA，有f(x*y)=f(x)f(y)，则称f是V1到V2的同态映射，简称同态，记为。 若f为满射，则称f为满同态； 若f为单射，则称f为单一同态； 若f为双射，则称f为同构，记作。 同态的本质是映射与运算可交换顺序。 定义：设为代数系统，f为到的同态，则称f为自同态；f是到的同构，则称f为自同构。,庄伯金 ,77,同态的性质,定理：设映射f:AB是代数系统到的一个同态，则是的一个子代数，并称它为f作用下的同态象。 定理：给定代数系统和，其中*和为二元运算。设f:AB为到的满同态，则 如果*是可交换的或可结合的运算，则也是可交换或可结合的运算； 如果中具有单位元e，则具有单位元f(e)。 对运算*，如果每一个A中元素x都有逆元x-1，则对运算，每一个B中元素f(x)，都有逆元f(x-1)。,庄伯金 ,78,代数结构,半群的概念与性质 群的概念与性质 环和域的概念,庄伯金 ,79,半群的概念,定义：设代数系统V=，为A上的二元运算，若满足结合律，则称V为半群。 半群由一个集合与一个二元运算组成； 满足结合律； 若半群满足交换律，则称为可交换半群。 定义：设V=为半群，若该半群中的二元运算含有幺元e，则称V为含幺半群或幺群或独异点。记作 若含幺半群满足交换律，则称为交换幺群。 定义： 为幺群，若存在一个元素gA，使得对任意的aA，都有a=gn成立，则称为循环幺群，并且称g是A的一个生成元。 定理：循环幺群是可交换幺群。,庄伯金 ,80,群的定义,定义：设是代数系统，为二元运算。如果可结合，存在单位元eG，且对G中任何元素x，都有x-1G，则称G为群。 若群G是有穷集，则称G为有限群，否则称为无限群。群G的基数称为群G的阶； 只含单位元的群称为平凡群； 若群G中