06離散數(shù)學(xué)課件資料

2023/10/22離散數(shù)學(xué)1

第六章幾個(gè)典型的代數(shù)系統(tǒng)

§6.1

半群與群

§6.2

格與布爾代數(shù)2023/10/22離散數(shù)學(xué)2可交換半群：如果半群V=<S,

>中的二元運(yùn)算

是可交換的，則稱V為可交換半群。一、半群的概念半群：設(shè)V=<S,

>是代數(shù)系統(tǒng)，

是二元運(yùn)算。如果

在S上是可結(jié)合的，則稱V為半群。即對(duì)

x,y,z

S，有(x

y)

z=x

(y

z)。§6.1半群與群如：<Z+,+>,<N,+>,<Z,+>,<R,

>,<P(S),∪>,<P(S),∩>,<Zn,

n>都是半群，但<Z,－>不是半群。2023/10/22離散數(shù)學(xué)3一、半群的概念（續(xù)）含幺半群（獨(dú)異點(diǎn)）：如果半群V=<S,

>的二元運(yùn)算

含有幺元，則稱V為含幺半群(獨(dú)異點(diǎn))。即

e

S，使得對(duì)

x

S都有e

x=x

e

=x。獨(dú)異點(diǎn)亦可記為

<S,

,e>。

如：<N,+,0>,<Z,+,0>,<R,

,1>,<P(S),∪,

>,<P(S),∩,S>,<P(S),

,

>,<Zn,

n,0>都是獨(dú)異點(diǎn)，但<Z+,+>不是獨(dú)異點(diǎn)(?)。獨(dú)異點(diǎn)的性質(zhì)：<A,>是獨(dú)異點(diǎn),則的運(yùn)算表中沒(méi)有任何兩行或兩列相同。2023/10/22離散數(shù)學(xué)4一、半群的概念（續(xù)）子半群：半群的子代數(shù)。即設(shè)V=<S,

>是半群，B

S且B

，若B對(duì)

運(yùn)算封閉，則<B,

>是V的子半群。子獨(dú)異點(diǎn)：含幺元的子半群。即設(shè)V=<S,

,e>是獨(dú)異點(diǎn)，B

S且B

，若B對(duì)

運(yùn)算封閉，且e

B，則<B,

,e>是V

的子獨(dú)異點(diǎn)。如：<Z+,+>和<N,+>是<Z,+>的子半群，且<N,+>是<Z,+>的子獨(dú)異點(diǎn)，但<Z+,+>卻不是。2023/10/22離散數(shù)學(xué)5一、半群的概念（續(xù)）半群中的冪：設(shè)半群V=<S,

>，則對(duì)

x

S，

x1

=x，xn+1

=xn

x，(n為正整數(shù))獨(dú)異點(diǎn)中的冪：設(shè)獨(dú)異點(diǎn)V=<S,

,e>，則對(duì)

x

S，

x0

=e，xn+1

=xn

x，(n為自然數(shù))冪運(yùn)算的性質(zhì)：xm

xn=xm+n，

(xm)n

=xmn

(m,n為正整數(shù))2023/10/22離散數(shù)學(xué)6一、半群的概念（續(xù)）半群的同態(tài)：設(shè)V1=<S1,

>，V2=<S2,

>為半群，

:S1

S2,且對(duì)

x,y

S1有

(x

y)=

(x)

(y)，則稱

是半群V1到V2的同態(tài)。獨(dú)異點(diǎn)的同態(tài)：設(shè)V1=<S1,

,e1>，V2=<S2,

,e2>

為獨(dú)異點(diǎn)，

:S1

S2,且對(duì)

x,y

S1有

(x

y)=

(x)

(y)，

(e1)=e2，則稱

是獨(dú)異點(diǎn)V1到V2的同態(tài)。2023/10/22離散數(shù)學(xué)7二、群的概念群：設(shè)V=<G,

>是代數(shù)系統(tǒng)，

是G上定義的二元運(yùn)算。如果滿足以下條件，則稱V=<G,

>為群。①運(yùn)算

在集合G上滿足封閉性;②運(yùn)算

在集合G上是可結(jié)合的;③集合G關(guān)于運(yùn)算

存在幺元e;④集合G中每個(gè)元素都存在逆元;如：<Z,+>,<R–{0},

>,是群，但<N,+>,不是。代數(shù)系統(tǒng)獨(dú)異點(diǎn)群(1)(2)(3)半群2023/10/22離散數(shù)學(xué)8二、群的概念例1：設(shè)G=R-{1/2}，對(duì)

x,y

G，x

*y=x+y

–2xy

，試證明<G,*>是否為群？證明:(1)若

x,y

G，x

*y=x+y

–2xy

G，故*運(yùn)算關(guān)于G滿足封閉性。(2)若

x,y,z

G,

(x*y)*z=x+y+z

–2xy–2xz

–2yz+4xyzx*(y*z)=x+y+z

–2xy–2xz

–2yz+4xyz

則(x*y)*z=x*(y*z),故*運(yùn)算關(guān)于G是可結(jié)合的。2023/10/22離散數(shù)學(xué)9二、群的概念例1：設(shè)G=R-{1/2}，對(duì)

x,y

G，x

*y=x+y

–2xy

，試證明<G,*>是否為群？(3)設(shè)e

是幺元，對(duì)

x

G，有

x

*e=x+e

–2xe=x

，則e=0e

*x=e+x

–2ex=x

，則e=0

故e=0為*運(yùn)算關(guān)于G的幺元。(4)對(duì)

x

G，設(shè)y是x的逆元，則x+y

–2xy=0，解得y=x/(2x–1)，即

x

G，x-1=x/(2x–1)

由上述可知，<G,*>是群。2023/10/22離散數(shù)學(xué)10二、群的概念有限群：G為有限集的群<G,

>稱為有限群，否則稱為無(wú)限群。|G|為有限群的階。交換群：若群<G,

>中的二元運(yùn)算

是可交換的，則稱群<G,

>為交換群，也稱阿貝爾群。如：<Z,+>,<R–{0},

>為無(wú)限群，<Zn,

>為有限群。如：<Z,+>,<R–{0},

>,<P(S),

>,<Zn,

>都是阿貝爾群。2023/10/22離散數(shù)學(xué)11二、群的概念設(shè)G={e,a,b,c},

為G上的二元運(yùn)算,運(yùn)算表如下：

e

a

b

ca

a

e

cbb

b

ce

ae

e

a

b

cc

c

b

ae

稱群<G,

>為Klein四元群。在含四個(gè)元素的群中,任意元素與自己運(yùn)算的結(jié)果都為幺元；除幺元外，任意兩個(gè)運(yùn)算的結(jié)果都等于另一個(gè)元素。2023/10/22離散數(shù)學(xué)12二、群的概念群中的冪：設(shè)群<G,

>，則對(duì)

x

G，

x0

=e，xn+1

=xn

x，(n為非負(fù)整數(shù))x-n=(x

-1)n=(xn)-1，(n為正整數(shù))(1)

x

G，(x-1)-1

=

x，冪運(yùn)算的性質(zhì)：(2)

x,y

G，(x

y)-1

=

y-1

x–1，(3)

x

G，xm

xn=xm+n，m,n為整數(shù)(4)

x

G，(xm)n

=xmn，

m,n為整數(shù)2023/10/22離散數(shù)學(xué)13二、群的概念設(shè)<G,*>為群，對(duì)

a,b

G，方程a*x=b和y*a=b在G中有解，且解是唯一的。定理1顯然，兩個(gè)方程的解分別是x=a-1

*b，y=b

*a–1。例2：S={1,2,3}，在群<P(S),

>中解方程

{1,2}

x={1,3}和y

{1}

={2,3}。解：∵群<P(S),

>的幺元是，∴{1,2}-1={1,2}，{1}-1={1}y=

{2,3}

{1}-1

={2,3}

{1}={1,2,3}。∴x={1,2}-1

{1,3}={1,2}

{1,3}={2,3}2023/10/22離散數(shù)學(xué)14二、群的概念群<G,

>中不存在零元

。定理2

設(shè)<G,

>為有限群，則G的運(yùn)算表中的每一行(每一列)都是G中元素的一個(gè)置換，且不同行(或列)的置換都不相同。定理4設(shè)<G,

>為群，則G中適合消去律。即對(duì)

a,b,c

G，有(1)若a

b=a

c，則b=c。(2)若b

a

=c

a，則b=c。

定理3定理5設(shè)<G,

>為群，對(duì)任意a，bG，

(a

b)–1=b–1

a–1,(a–1)–1=a2023/10/22離散數(shù)學(xué)15三、子群的概念子群：設(shè)<G,*>為群，H是G的非空子集，如果H關(guān)于G中的運(yùn)算*構(gòu)成群，則稱<H,*>為<G,*>

的子群。記作H

G如：<nZ,+>是<Z,+>的子群，其中<{0},+>和<Z,+>

是<Z,+>的平凡子群；設(shè)<G,*>是一個(gè)群，B是G的一個(gè)有限非空子集。若運(yùn)算*在集合B上封閉，則<B,*>是<G,*>的子群。有限子群判定定理設(shè)<G,*>為群，H是G的非空子集，如果對(duì)

x,y

H，x*

y-1

H，則<H,*>是<G,*>的子群。子群的判定定理2023/10/22離散數(shù)學(xué)16三、子群的概念設(shè)<G,*>為群，對(duì)

x

G，令H={xk|k

Z}，則<H,*>是<G,*>的子群。該子群稱為由元素x生成的子群，記作H=<x>。群<Z6,

>,Z6={0,1,2,3,4,5},

x,y

Z6,x

y=(x+y)mod6。

<0>={0}<1>={0,1,2,3,4,5}

<2>={0,2,4}<3>={0,3}

<4>=<2><5>=<1>因?yàn)槿我馊中的元素xm

、xn

，有xm*(xn)-1=xm-n

H2023/10/22離散數(shù)學(xué)17元素的階(周期)：設(shè)群<G,

>，a

G，使ak=e成立的最小正整數(shù)k

稱為a的階(周期)。四、兩種常用的群

任何群的幺元e的階都為1，Klein四元群中a,b,c的階都是2，群<Z6,

>中2和4的階是3，3的階是2，1和5的階是6。1、循環(huán)群：階(周期)：設(shè)<G,*>是群,若a

G有有限周期r,則(1)ak=e

當(dāng)且僅當(dāng)k是r的倍數(shù)(2)a–1的周期亦為r(3)r

|G|2023/10/22離散數(shù)學(xué)18循環(huán)群：設(shè)群<G,

>，如果

a

G，使得

G={ak|k

Z}

則稱為循環(huán)群，記G=<a>，稱a為循環(huán)群<G,

>的生成元。四、兩種常用的群如：群<Z,+>是循環(huán)群，其生成元是1或-1，性質(zhì)：循環(huán)群一定是阿貝爾群，但阿貝爾群不一定是循環(huán)群。

群<Z6,

>是循環(huán)群，其生成元是1或5。2023/10/22離散數(shù)學(xué)19四、兩種常用的群

無(wú)限階循環(huán)群G=<a>的生成元就是a和a-1，n階循環(huán)群G=<a>的生成元是at(其中t與n互質(zhì))。

循環(huán)群的子群仍是循環(huán)群。如：群<Z6,

>中，Z6=<1>，6的正因子是1,2,3,6，子群有：<16>=<0>={0}，<13>=<3>={0,3}，

<12>=<2>={0,2,4}，

<11>=<1>={0,1,2,3,4,5}。n階循環(huán)群G=<a

>的子群的階都是n

的因子。對(duì)于n的每個(gè)正因子d，an/d是G的d階子群的生成元。2023/10/22離散數(shù)學(xué)20四、兩種常用的群如：12階群G={e,a,a2,…,a11}，12的正因子是1,2,3,4,6,12,則G的子群是：<a12/1

>=<e

>={e}，1階子群<a12/2

>=<a6

>={e,a6}，2階子群<

a12/3

>=<

a4>={e,a4,

a8}

3階子群<a12/4

>=<a3>={e,a3,

a6

,a9}4階子群<a12/6

>=<a2>={e,a2,a4,

a6,a8,a10}6階子群<a12/12

>=<

a

>=G，12階子群2023/10/22離散數(shù)學(xué)21四、兩種常用的群n元置換：設(shè)S={1,2,…,n}，S上的任何雙射函數(shù)

:S

S構(gòu)成了S上n個(gè)元素的置換，稱為n元置換。記作：如：S={1,2,3}，令

:S

S且

(1)=2，

(2)=3，

(3)=1，則有一個(gè)置換：2、置換群：2023/10/22離散數(shù)學(xué)22四、兩種常用的群任何n元置換都可以用不交的輪換之積來(lái)表示。如：置換

1

=，又如：置換

2

=，則可表示為

2

=(1325)(46)則可表示為

1

=(132546)又如：置換

3

=，則可表示為

3

=(132)(4)(56)=(132)(56)

2023/10/22離散數(shù)學(xué)23四、兩種常用的群解：

1

=(14523)，例3：將置換

1和

2表成不交的輪換之積。其中

1

=，

2

=。

2

=(132)(45)，恒等置換：稱為恒等置換。記作：Is當(dāng)|S|=n時(shí)，S上共有n!種不同的n元置換，將這些置換構(gòu)成的集合記作Sn。2023/10/22離散數(shù)學(xué)24置換的運(yùn)算(1)設(shè)S={x1,x2,…,xn}上有置換：P=則稱為P的逆置換,記作:P–1.2023/10/22離散數(shù)學(xué)25(2)設(shè)S={x1,x2,…,xn}上有兩個(gè)置換：P1=則稱P=為P1與P2的合成,P2=顯然:

Is=Is

=,這說(shuō)明:Is是<Sn,

>中的幺元.記作：P=P2

P12023/10/22離散數(shù)學(xué)26四、兩種常用的群（續(xù)）(3)任何置換

=

的逆置換

-1=就是的逆元。因此，<Sn,

>構(gòu)成一個(gè)群，稱為n元對(duì)稱群。<Sn,

>的任何子群則稱為n元置換群。對(duì)于代數(shù)系統(tǒng)<Sn,

>，

是函數(shù)的合成運(yùn)算，則：(1)集合Sn對(duì)運(yùn)算

封閉，且

是可結(jié)合的。(2)Is是集合Sn關(guān)于

運(yùn)算的幺元。2023/10/22離散數(shù)學(xué)27解：(1)先寫出所有的置換,共3!=6個(gè),例6.5設(shè)S={1,2,3},寫出S上所有的置換群P4=213123P5=132123Pe=123123按

順序?qū)懀?23P1=231123P2=312123P3=3211232023/10/22離散數(shù)學(xué)28(2)再列出S3={pe，p1，p2，p3

，

p4，p5}上關(guān)于合成運(yùn)算

的運(yùn)算表pep1p2p3p4p5

pep1p2p3p4p5pep1p2p3p4p5p1p2pep4p5p3p2pep1p3p4p5p3p5p4pep2p21p4p3p5p1pep2p5p4p3p2p1pePe=123123P1=231123P2=312123P3=321123P4=213123P5=1321232023/10/22離散數(shù)學(xué)29(3)最后寫S3上的置換群(子群,檢驗(yàn)封閉性)<{pe},

><{pe,p4},

><{pe,p1,p2},

>都是S3上的子群，也是置換群.<{pe,p3},

><{pe,p5},

>

p3、p4、p5是2階元，p1,p2是3階元<S3,

>2023/10/22離散數(shù)學(xué)30通常記：{x,y}的最小上界為：x

y{x,y}的最大下界為：x

y一、格的基本概念和性質(zhì)格：設(shè)<S,≤>是偏序集，如果

x,y

S，{x,y}都有最小上界和最大下界，則稱<S,≤>是一個(gè)格?！?.3格與布爾代數(shù)<S6,R>21632023/10/22離散數(shù)學(xué)31一、格的基本概念和性質(zhì)（續(xù)）解：例4：設(shè)n為正整數(shù)，Sn是n的正因子的集合，R為整除關(guān)系，驗(yàn)證<Sn,R>是格，并舉例說(shuō)明。對(duì)于

x,y

Sn，x與y的最小公倍數(shù)[x,y]屬于Sn，x與y的最大公約數(shù)(x,y)屬于Sn，且x

y=[x,y]，x

y=(x,y)。因?yàn)?lt;Sn,R>是自反的，反對(duì)稱的，傳遞的，從而是偏序集；因此，<Sn,R>是一個(gè)格。2023/10/22離散數(shù)學(xué)32一、格的基本概念和性質(zhì)（續(xù)）例4：設(shè)n為正整數(shù)，Sn是n的正因子的集合，R為整除關(guān)系，驗(yàn)證<Sn,R>是格，并舉例說(shuō)明。如當(dāng)n=6,8,30時(shí)，分別有下圖：<

S8,R

>8421<S6,R>216313526101530<S30,R>解：2023/10/22離散數(shù)學(xué)33一、格的基本概念和性質(zhì)（續(xù)）例5：判斷下列偏序集是否構(gòu)成格，說(shuō)明原因。dbacfecbadeabecdf{e，f}沒(méi)有上界{b，d}有上界c、e，但沒(méi)有最小上界{d，e}有下界a、b、c，但沒(méi)有最大下界2023/10/22離散數(shù)學(xué)34(1)格的對(duì)偶原理：設(shè)f為含有格中的元素及符號(hào)=,≤,≥,

,

的關(guān)系式。f*是將f中的≤改成

≥,≥改成≤,

改成

,

改成

后所得的關(guān)系式,稱之為f的對(duì)偶命題。若f為對(duì)一切格為真,則f*也對(duì)一切格為真。一、格的基本概念和性質(zhì)（續(xù)）如：若格中(a

b)

c≤c成立，則(a

b)

c≥c成立。格的性質(zhì)：2023/10/22離散數(shù)學(xué)35冪等律：(2)設(shè)<L,≤>是格，a,b,c是L中任意元素，則有：一、格的基本概念和性質(zhì)（續(xù)）交換律：a

b=b

a，a

b=b

a；結(jié)合律：(a

b)

c=a

(b

c)，

(a

b)

c=a

(b

c)；冪等律：a

a=a，a

a=a；吸收律：a

(a

b)=a，a

(a

b)=a；a

a≥aa≥a

a=

a

a

a≥a

a2023/10/22離散數(shù)學(xué)36(2)設(shè)<L,≤>是格，a,b,c是L中任意元素，則有：一、格的基本概念和性質(zhì)（續(xù)）交換律：a

b=b

a，a

b=b

a；結(jié)合律：(a

b)

c=a

(b

c)，

(a

b)

c=a

(b

c)；冪等律：a

a=a，a

a=a；吸收律：a

(a

b)=a，a

(a

b)=a；結(jié)合律：(a

b)

c=a

(b

c)，

(a

b)

c=a

(b

c)；2023/10/22離散數(shù)學(xué)37格：設(shè)<L,

,

>是代數(shù)系統(tǒng)，

和

是二元運(yùn)算，若

和

運(yùn)算滿足交換律，結(jié)合律和吸收律，（隱含冪等律），則稱<L,

,

>是一個(gè)格。一、格的基本概念和性質(zhì)（續(xù)）子格：設(shè)<L,

,

>是格，S是L的非空子集，若S

關(guān)于運(yùn)算

和

是封閉的，則稱<S,

,

>是格<L,

,

>的子格。格的另一個(gè)等價(jià)定義：2023/10/22離散數(shù)學(xué)38一、格的基本概念和性質(zhì)（續(xù)）例6：格<L,

,

>如圖，<Si,

,

>是否構(gòu)成其子格。其中S1

={a,e,g,h}，S2

={a,c,e,h}，

S3

={a,b,d,f,h}abdcegfh<S1,

,

>不是子格，<S2,

,

>是子格，<S3,

,

>是子格，2023/10/22離散數(shù)學(xué)39beacd五角格1、分配格：設(shè)<L,

,

>是格，若對(duì)

a,b,c

L有

a

(b

c)

=(a

b)

(a

c)

a

(b

c)

=(a

b)

(a

c)

成立，則稱<L,

,

>為分配格。二、特殊的格dcbabadcadecb鉆石格2023/10/22離散數(shù)學(xué)40二、特殊的格（續(xù)）格<L,

,

>是分配格當(dāng)且僅當(dāng)它不含有與五角格或鉆石格同構(gòu)的子格。分配格的判定定理例6：判斷下列格是否為分配格。cafedbcaedbfcaedbgfcahefbgd2023/10/22離散數(shù)學(xué)41二、特殊的格（續(xù)）2、有界格：全下界(或全上界)：設(shè)<L,

,

>為格，若存在a

L，對(duì)

b

L有a≤b(或a≥b)，則稱a為格<L,

,

>的全下界(全上界)。有界格：具有全上界和全