离散数学定义定理(下)

定义4.1.1 设A，B为任意集合，一个从An到B的映射，称为集合A上的一个n元运算。如果B A，则称该n元运算时封闭的。

定义4.1.2 一个非空集合A，连同若干个定义在该集合上的运算f1，f2，…，fk所组成的系统，称为一个代数系统，记作：。

定义4.1.3 设A为任意非空集合，*是集合A上的二元运算。

（1）封闭性：对任意a，b∈A，若有a*b∈A，则称运算*关于集合是封闭的。

（2）结合律：对任意a，b，c∈A，若有a*（b*c）=（a*b）*c，则称运算*在集合A是可结合的，或称运算*在A上满足结合律。

（3）交换律：对任意a，b∈A，若有a*b=b*a，称为运算*在A上市可交换的，或称*运算在A上满足交换律。

（4）幂等率：若对 a∈A，有a*a=a，则称运算*在Ａ上市幂等的，或称运算×在Ａ上满足幂等率。

（５）分配律：若对 a，b，c∈A有 ： a (b*c)=(a b)*(a c) 和（b*c）

a=（b a）*（c a）成立，则称运算 对*时可分配的，或称运算*满足分配律。 （6）吸收率：若 和*满足交换律而且有： a，b∈A，并有a (b*c)=a和a* (b c)=a，则称 和*运算时可吸收的，或称 和*运算满足吸收率。

定义4.1.4 设*为集合Ａ上的二元运算，若存在 （或 ），使得对于 x∈A，都有 （或 ），则称 （或 ）是A中关于*运算的左（或右）幺元（或单位元）。如果A中一个元素e，它既是左幺元，又是右幺元，则成e是A中关于运算* 的遥远。

显然对于任一x∈A，e*x=x*e=x。

定义4.1.5 设*式定义在集合A上的二元运算，如果有一个元素 ，对于任意元素 都有 ，则称 为A中关于运算*的左零元；如果有一个元素 ，对于任意元素 都有 ，则称 为Ａ中关于运算*的右零元。如果A中的一个元素 ，他既是左零元，又是右零元，则称 为A上关于运算*的零元。

定理4.1.1 设*是集合A上的二元运算，且在A中有关于运算*的左幺元 和右幺元 ，则 ，且A中幺元是惟一的。

定理4.1.2 设*是定义在集合A上的二元关系，在A中有关于运算*的左零元 和右零元 那么 ，且A中零元是惟一的。

定理4.1.3 设有代数系统中，A的元素个数多于1，若其存在关于运算*的单位元e与零元O，则。 定义4.1.6 设代数系统中，e是关于*的单位元，若对A中某个元素a，存在A的一个元素b，使得b*a=e，则称b为a 的一个左逆元；若a*b=e，则称b为a的一个右逆元。若一个元素b，既是a 的左逆元，又是a的右逆元，则称b是a的一个逆元，记作 。

定理4.1.4 设代数系统，这里*是定义在A上的二元运算，A中存在幺元e，且每一个元素都有左逆元，如果*是可结合运算，那么这个代数系统中，任何一个元素的左逆元必定也是该元素的右逆元，且每个元素的逆元是惟一的。

定义4.1.7 如果两个代数系统中运算的个数相同，对应运算的元数也相同，且代数常数的个数也相同，则称这两个代数系统具有相同的构成成分，也称它们是同类型的代数系统。

同类型的代数系统仅仅是构成成分相同，不一定具有相同运算性质。

定义4.1.8 设 是代数系统，，且B对 都是封闭的，B和S还含有相同的代数常数，则称 是V的子代数系统，简称子代数。

定义4.2.1 设*是集合S上的二元运算，若运算*时封闭的，并且*是可结合的，则称代数系统

（1） ，

（2）(a*b)*c=a*(b*c) 定理4.2.1 设是一个半群，，且*在B上封闭，那么也是一个半群，通常称是半群的子半群。

定义4.2.2 若半群中存在一个幺元则称为独异点（或含幺半群）。

定理4.2.2 设是独异点，对于，且a， b均有逆元，则：

（1） ，（2）若a*b有逆元，则 。

定义4.3.1 设是一个代数系统，其中G是非空集合，*是G上一个二元运算，

（1）如果*是封闭的；

（2）运算*时可结合的；

（3）存在幺元e；

（4）对于每一个元素 ，存在它的逆元；则称是一个群。

定义4.3.2 设是一个群，如果G是有限群，那么称为有限群，G中元素的个数统称称为该有限群的阶数，记为 。

定义4.3.3 若群G中，只含有一个元素，即G=|e|，|G|=1，则称G为平凡群。

，G关于*运算，构成一个群，这个群称为Klein四元群。 定义4.3.4 设是一个群，若运算*在G上满足交换律，则称G为交换群或Abel群（阿贝尔群）。

定义4.3.5 设是群，若 ，使得成立的最小正整数k称为a的阶，记作|a|。

定理4.3.1 设为群， 有：

（1） ； （2） ； （3） ；（4）；（5）若G为Abel群 ， 。

定理4.3.3 对|G|>1的群不可能有零元。

定理4.3.4 设是一个群，对于 。必存在惟一的，使a*x=b。

定义4.3.7 设为群，若在G中存在一个元素a，使得G中存在一个元素a，使得G中的任意元素都由a的幂组成，则称该群为循环群，元素a称为循环群G的生成元。

定义4.3.8 设是一个群，S是G的非空子集，如果也构成群，则称是的一个子群，记作S≤G。

子群判别定理：

定理4.3.5 设是群，H是G的非空子集，则H≤G iff。

（1） a，b∈H，有a*b∈H；

（2） a∈H，有a-1∈H。 定理4.3.6 设是群，H是G的非空子集，iff a，b∈H，则a*b-1∈H。

定理4.3.7设是群，H是G的有穷非空子集，则H是G的子群iff a，b∈H，有a*b∈H。

设是群，C={a|a∈G，且对 x∈G有a*x=x*a}，C又称CentG.

定义4.4.1 设是一个代数系统，如果满足

（1）是阿贝尔群；

（2）是半群；

（3）运算*对于运算☆是可分配的；

则称是环。

定理4.4.1 设是一个环，则对任意a，b∈A有

（1） ；（2） ；（3） ；

（4） ；（5）

其中 是加法幺元，-a是a的加法逆元，a+（-b）记为a-b，注意上面各式中不能只理解是实数上的加法与乘法。 定义4.4.2 设是环，对a，b∈R，a≠0，b≠0，但a·b=0；则称a是R中的一个左零因子，b是R中一个右零因子；若一个元素既是左零因子，又是右零因子，则称它是一个零因子。

定义4.4.3 设R是一个环，对于任意的a，b∈R，若a·b=0，则a=0或b=0，就称R是一个无零因子环。

（整数环、有理环、实数环、复数环都是无零因子环。）

定理4.4.2 设是环， R是无零因子环的充分必要条件，是在R中乘法适合消去律，即对任意a，b，c∈R，a≠0，若有a·b=a·c（或b·a=c·a），则有b=c。

定义4.4.4 设是环。如果是可交换的，则称是可交换环。

如果含幺元，则称是含幺元。

定义4.4.5 设是一个代数系统，如果满足：

（1）是阿贝尔群；

（2）是可交换独异点，且无零因子，即对任意a，b∈A，a≠ ，b≠ 必有a·b≠ ；

（3）运算 对于运算+是可分配的。 则称是整环。

定义4.4.6 设是一个环，且|R|≥2，（1）R有幺元；（2）每个非零元有逆元；则称这个环是除环。如果一个除环是可交换的，称为域。

当为域时，及是阿贝尔群，其中R*=R-|0|。

定义4.5.1 设是一个偏序集，如果A中任意两个元素都有最小上界和最大下界，则称为格。

定义4.5.2 设是一个格，P是由格中元素及≤，=，≥，∧，∨等符合所表示的命题，如果将P中的分别换成≥，≤，∨，∧得到的命题P*，称P*为P的对偶命题，简称对偶。

格的对偶原理：如果命题P对一切格L为真，则P的对偶命题业对一切格为真。

定义4.5.3 设是一个格，如果在A上定义两个二元运算∨和∧，使得对任意a，b∈A，a∨b等于a和b的最小上界，a∧b等于a和b的最大下界。称为由格所诱导的代数系统。二元运算∨和∧分别称为并运算和交运算。

定理4.5.1 在格中，对任意a，b∈A，都有：

a≤a∨b，b≤a∨b， a∧b≤a，a∧b≤b。 定理4.5.2 设是格， a，b∈A，（1）a≤b，且a≤c=>a≤b∧c；（2）a≥b且a≥c =>b∨c。

定理4.5.3 在格中，对于a，b，c，d∈A，如果a≤b，c≤d，则 a∨c≤b∨d，a∧c≤b∧d。

定理4.5.4 设是一个格，由所诱导的代数系统为，则对于任意a，b，c，d∈A，有：

（1） ；（交换律）

（2） ；结合律

（3）a∨a=a；a∧a=a（幂等律）

（4）a∨(a∧b)=a；a∧ (a∨b)=a；（吸收律）

定理4.5.5 设是一个代数系统，其中∨和∧都是二元运算，且满足交换性，结合性和吸收性，则A上存在偏序关系≤，使是一个格。

定义4.5.4 设是代数系统，其中∧和∨是二元运算，若∧和∨运算满足交换律，结合律，吸收律，则称是一个格。

定理4.5.6 设是格，则 （1） a，b，c∈L有a≤b=>a∧c≤b∧c，且a∨c≤b∨c； （2） a，b，c，d∈L有a≤b且c≤d=>a∧c≤b∧d，且a∨c≤b∨c；

定理4.5.5 设是格，S是L的非空子集，若S关于运算∧和∨是封闭的，则称是格L的子格。

定义4.6.1 设是由格所诱导的代数系统，如果对任意a，b，c∈A满足：，称是分配格。

定义4.6.2 设和是两个格，由它们分别诱导的代数系统为和，如果存在着一个从A1到A2的映射f，使得对任意a，b∈A1有：

，称f为从到格同态，也可称是的格同态象。当f是双射时，格同态也称为格同构。

定理4.6.1 格L是分配格，当且仅当L既不含有与五角格同构的子格，也不含有与钻石格同构的子格。

（1）每一条链都是分配格。（2）小于五个元素的格都是分配格。

定义4.6.3 设是一个格，如果存在元素a∈A对于任意x∈A，都有a≤x（或x≤a），则称a为格的全下界（全上界）。记作0（全下界为1）。

存在全上界和全下界的格称为有界格，记作。