离散数学—2

一、运算

1.运算的定义

定义 设A是非空集合，称映射

f1:AA 为集合A上的一元运算，称映射

f2:AAA

为集合A上的二元运算。通常用,,等表示运算，称为运算符。 当为A上的一元运算时，对aA进行运算，记作a ， 当为A上的二元运算时，对a,bA进行运算，记作ab. 类似地可定义A上的n元运算，下面只讨论一元和二元运算。 A上二元运算的特点：

⑴ A中任两个元素都可运算，结果唯一；

⑵ A对该运算封闭,即a,bA,闭，因此不是Z上的二元运算。

当A是有限集a1,a2,,an时，通常用运算表表示A上的运算。 一元运算

abA。例如：整数集合Z上的除法对Z不封

a a1 a2  a a1 a2  an

二元运算

an  a1 a2  an a1 a2  a1a1 a1a2  a1an a2a1 a2a2  a2an    an ana1 ana2  anan 例 设A0,1，布尔加法，布尔乘法的运算表为

1

布尔加法

 0 1 布尔乘法

0 1 0 1 1 1 0 1 0 0 0 1  0 1 例 设Im{0,1,2,3,,m1}，记m为模m加法，m为模m乘法。

m:ImImIm，imj(ij)modm，i,jIm m:ImImIm，imj(ij)modm，i,jIm

如：I20,1,2,2为I2上的二元运算，运算表为

模2加法

0 1 0 1 1 0 0 1 0 0 0 1 2 0 1 模2乘法

2 0 1 I30,1,2,3,3的运算表；

3 0 1 2

0 1 2 0 1 2 1 2 0 2 0 1 0 1 2 0 0 0 0 1 2 0 2 1 3 0 1 2

2. 运算律

（1）交换律 设为集合A上的二元运算，如果对任意x,yA，都有 xyyx

2

则称满足交换律，或称在A上是可交换的。

（2）结合律 设为集合A上的二元运算，如果对任意的x,y,zA，都有 xyzxyz 则称满足结合律，或称在A上是可结合的。

注：若A上的二元运算满足结合律，则对a1,a2,,anA，有

a1a2a3a4an(((a1a2)a3)a4)an(a1a2)(a3a4)an 当a1a2ana时，可定义幂次 aaaaa （n个a） 且有 aaamnmnn，(am)namn， m,n为正整数。

（3）幂等律 设为集合A上的二元运算，如果对任意的xA，都有 xxx 则称满足幂等律。x称为幂等元。

（4）分配律 设和是集合A上的两个二元运算，对任意的x,y,zA，有

xyzxyxz

yzxyxzx则称对满足分配律，或称对是可分配的。 注：分配律要指明哪个运算对哪个运算满足分配律。

（5）吸收律 设和是集合A上的两个二元运算，对任意的x,yA，有

xxyxxxyx

则称和满足吸收律。 3.特殊元素 （1）单位元

定义 设为集合A上的二元运算，如果存在eA，使得对任意的xA，都有

xeexx 则称e为集合A关于的单位元。

对任意集合A来说，关于运算的单位元不一定存在。 定理 若单位元存在，则一定唯一。 （2）零元

定义 设为集合A上的二元运算，如果存在A，使得对任意的xA，有 xx 则称为集合A关于的零元。

对任意集合A的来说，关于运算的零元不一定存在。

3

定理 若零元存在，则一定唯一。 （3）可逆元

定义 设为集合A上的二元运算，且有单位元e，如果对aA，存在bA，使得

abbae 则称a是关于的可逆元，称b为a关于的逆元。当a的逆元唯一时，记作a。 事实上，a与b互为逆元。

注：①集合A中的元素未必都有逆元，如：实数集R上的乘法运算，0不可逆。 ②设为集合A上的二元运算且满足结合律，则有 ⑴ aA是可逆元，则a的逆元是唯一的。 ⑵ aA是可逆元，则a也可逆，且a1111a。

1 ⑶ 若a、b均为可逆元，则ab也可逆，且ab例 实数集R上的加法、乘法均为二元运算

b1a1。

关于加法：单位元是0，无零元，任一元素均可逆，xR,x1x；

x11。 x关于乘法：单位元是1，零元是0，任意非零元有逆元，xR(x0),例 设A为非空集合，幂集2上的“”、“”均为二元运算

A

AA关于：单位元是（因B2，BBB），零元是A（因B2，

BAABA）

AA关于：单位元是A（因B2，BAABB，零元为（因B2，

BB）

例 设Q是有理数集合，运算:QQQ，对任意a,b,x,yQ，有 a,bx,yax,ayb 求的单位元和每个可逆元的逆元。

2解 （1）设x,y为单位元，则对任意a,bQ，有

2222a,bx,yax,ayba,b

所以 解得 x1,axa

aybby0；即对任意a,bQ2，有

a,b1,0a,b

4

1,0a,ba,b 所以 1,0为单位元。 （2）对任意a,bQ2，令

a,bx,yax,ayb1,0

得方程组 ax1

ayb01b,y，即对任意a,bQ2，存在唯一的aa①a0时，方程组有唯一解 x1b,Q2，有 aaa,b1b,1,0 aa1b,a,b1,0 aa1b1所以 a,b,

aa②a0时，方程组无解，因此0,b不可逆。 二、代数系统、子代数与积代数

定义 集合A与A上的k个运算（一元或二元运算）1,2,,k所组成的系统称为代数系统，简称代数，记为A,1,2,,k.

由定义可知，代数系统就是将集合赋予了运算。

定义 设VA,1,2是代数系统，A0A，如果A0对运算1,2都是封闭的，则

V0A0,1,2也是代数系统，称为V的子代数系统，简称子代数，如果A0A，则称子

代数V0为V的真子代数。

对于代数系统A,的子代数也可类似定义。

例 N,是Z,的子代数，Z,,是R,,的子代数。

两个代数系统可以生成一个新的代数系统—积代数。 定义 设ViAi,i2定义A1A2上的运算i1,2都是代数系统，1和2为二元运算，

如下： :(A1A2)A1A2，对任意x1,y1,x2,y2A1A2，有

5

x1,y1x2,y2x11x2,y12y2

则A1A2,是代数系统，称为V1,V2的积代数系统，简称积代数，记为V1V2。

对于1,2同为一元运算的情形可类似定义。

同样可定义有两个运算的代数系统的积代数（见书P94定义2.1.11）。 积代数的性质 定理 设ViAi,ii1,2都是代数系统，1和2为二元运算，它们的积代数为

V1V2A1A2,，

（1）如果1,2都是可交换的，则也是可交换的； （2）如果1,2都是可结合的，则也是可结合的； （3）如果1,2都是幂等的，则也是幂等的；

（4）如果e1,e2分别是关于1,2的单位元（或分别称为V1,V2的单位元），则e1,e2是关于的单位元（或称为V1V2的单位元）；

（5）如果1,2分别是关于1,2的零元（或分别称为V1,V2的零元），则1,2是关于的零元（或称为V1V2的零元）；

（6）如果xiAi关于i的逆元为xi(i1,2)，则x1,x2是关于的可逆元，且

1x1,x21x1,x2三、代数系统的同态与同构（略）

§2.2 群

本节介绍只有一个二元运算的代数系统：群。 一、群的基本概念

11

定义 设G,为代数系统，是G上的二元运算，如果 ⑴ 运算是可结合的； ⑵ 存在单位元e；

⑶ G中每个元素都是可逆的 则称G,为群。

由定义可知，

⑴ 群中没有零元（零元不可逆）；

6

⑵ 群中每个元素的逆元都是唯一的。

定义 设G,为群，如果G中含有无限个元素，则称G,是无限群，如果G中含有有限个元素，则称G,为有限群。称#G（G中所含元素的个数）为群G,的阶数。 下面介绍两类重要的群。 交换群

定义 设G,是群，如果·是可交换的，则称G,为交换群或阿贝尔群。 循环群

定义 设G,为群，如果存在aG，使得

GakZ

则称G,为循环群，称a为循环群G,的生成元。 例 I3,3 是3阶循环群。 例 Z,是无限阶循环群。

kZ,只有两个生成元1和-1.

注：循环群一定是交换群，但反之不成立。 二、群的性质

性质1 设G,是群，则对于任意的a,bG

1（1） 方程axb有唯一解xab

1（2） 方程yab有唯一解yba

性质2 （消去律）设G,是群，对任意a,b,cG （1） 如果abac,，则bc; （2） 如果baca，则bc. 性质3 设G,是群，则对任意的a,bG有

ab1b1a1

2性质4 设G,是群，则只有单位元是幂等元，即ee 群中元素的周期

定义 设G,是群，aG如果对于任意的正整数n，都有

7

ae

则称元素a的周期为无限。如果存在正整数n，使得 ae

则称元素a的周期为有限。 称使ae 成立的最小的正整数n为元素a的周期。 由定义可知

（1）只有单位元的周期为1，即ee

n （2）若元素a的周期是无限的，则对于任意的正整数n，有 ae，从而只有当n0n01nnn时，aae.

性质5 设G,是群，aG的周期为r，则a的周期也为r.

1性质6 设G,为群，如果aG(ae)，满足ake(kZ)，则a的周期是k的正因子。 子群

前面讲代数系统时介绍了子代数系统，群是一种代数系统，下面讨论群的子代数系统——子群的问题。

定义 设G,为群，非空集合HG，如果H,是群，则称H,为群G,的子群。 例 设G{1,1,i,i},则H,是G,的子群。

注：（1）显然{e},,G,都是G,的子群，称为平凡子群。 （2）子群H,的单位元就是G,的单位元e，即eH。 （3）交换群的子群仍为交换群，循环群的子群仍为循环群。 判断H,是否G,的子群的判定定理。

定理 设G,为群，则H,是G,的子群的充分必要条件是：对任意的x,yH，都有

为数的乘法，i1，则G,是一个交换群，设H{1,1}，

xy1H。

例 设G,是群，aG 令HakZ，则H,是G,的子群，称为由a生成的子群。

例 求I5,5的所有子群

8

kI5,5只有两个平凡子群{0},5和I5,5而无其他子群。

群的同态（略）

§2.3格和布尔代数

格是与偏序集密切相关的、具有两个二元运算的代数系统，布尔代数是一种特殊的格，本节将介绍这两个代数系统。 一、格

1.格的基本概念

定义 设L,,是具有两个二元运算和的代数系统，如果,都满足交换律，结合律，并且和满足吸收律，则称L,,是格。 由定义可知，对于格L,,的任意元素a,b,c，有 （Ⅰ）abba,abba（交换律） （Ⅱ）abcabc

abcabc（结合律）

(Ⅲ)

aabaaaba（吸收律）

定理 设L,,是格，则,都满足幂等律。 格的子代数—子格

定义 设L,,是格，非空集合L0L，如果运算,对于L0是封闭的，则称L0,,是L,,的子格。 2.格与偏序集

定理 设L,,是格，则可在L上定义偏序关系，使L,为偏序集，且L,中每对元素都存在最小上界与最大下界。

定理 设L,为偏序集，如果对任意的a,bL，a,b都有最小上界和最大下界， 则可在L上定义二元运算和，使得L,,是格。

由以上两个定理可知

设L,,是格，则可以确定一个偏序集L,，称为由格诱导的偏序集,满足任一对元素都有最小上界和最大下界。

设L,是偏序集，如果它的任一对元素都有最小上界和最大下界，对任意a,bL，

9

定义

abluba,b,abglba,b 则L,,是格，称为由偏序集诱导的格。

所以，格与偏序集的关系为

ababb(aba) L,是偏序集且

L,,是格

ablub(a,b),abglb(a,b)

任两个元素有最小上界、最大下界

定义 设L,是偏序集，如果L中任意两个元素都有最小上界和最大下界在L中存在，则称L,是一个格。 例 偏序集的哈斯图如下:

由于它的任意两个元素都存在最小上界和最大下界，因此L,是格。 例 设集合Aa,b,c,d,e,f,g，偏序集A,的哈斯图为

由于元素c,d有上界e,f,g，但无最小上界，故A,不是格。 例 偏序集的哈斯图如下，判断是否为格

10

(1) (2) (3) 解：

(1)是格，(2),(3)不是格。

3.格的性质

性质1 设L,,是格，对任意a,b,c,dL，如果

ab,cd 则

acbd,

acbd

性质2 设L,,是格，则对任意a,b,cL，有

(1) abcabac (2) abacabc

性质3 设L,,是格，对任意a,b,cL，如果ac，则

abcabc

二、布尔代数

布尔代数是一种特殊的格，是具有两个二元运算、一个一元运算的代数系统。 定义 设B,,,是代数系统（其中,都是二元运算，ˉ是一元运算），且满足

⑴ ,都满足交换律；

⑵ 对，及对都满足分配律；

⑶ 运算和都有单位元，记为0和1；即对任意aB，有a0a,a1a； ⑷ 对于任意aB，有aB（a称为a的补元），使 aa1,则B,,,称为布尔代数。 定理 设B,,,是布尔代数，a,bB，如果

aa0

ab1,ab0 则 ab,ba 设B,,,是布尔代数，则对任意的a,b,cB，有

（Ⅰ）abba,abba （交换律）

11

（Ⅱ）

abcabacabcabac （分配律）

（Ⅲ）a0a,a1a （同一律） （Ⅳ）aa1,aa0 （互补律） 此外，还可以证明：

（Ⅴ）

abcabcabcabc （Ⅵ） aa （Ⅶ） aaa,aaa （Ⅷ） a11,a00 （Ⅸ）aaba,aaba （Ⅹ）abab,abab

12

（对合律） （吸收律）

（德摩根律）（结合律）（幂等律）（零一律）