ZACHODNIOPOMORSKI UNIWERSYTET TECHNOLOGICZNY
W SZCZECINIE

2012

MATEMATYKA DYSKRETNA

Wykład 9: Struktury algebraiczne

Prowadzący wykłady: dr inż. Larisa Dobryakova

2

Działania (1)

Działaniem nazywamy każdą funkcję:



 





1

2

:

...

n

A A

A

B

,

która

uporządkowanemu

n

–elementowemu

ciągowi

elementów

zbioru



 

1

2

...

n

A A

A

przyporządkowuje pewien element zbioru

B

,





n

.

Zbiory

i

A

nazywa

się dziedzinami działania, zbiór

B

nosi nazwę przeciwdziedziny

działania. Ustalona liczba

n

(liczba

argumentów) nazywa się argumentowością

(typem, arnoscią) działania.

Działaniem wewnętrznym

n

–argumentowym (operacją

n

–argumentową)

w niepustym zbiorze

A

nazywamy każdą funkcję:





:

n

A

A

,

która uporządkowanemu

n

–elementowemu ciągowi elementów zbioru

A

przyporządkowuje pewien element zbioru

A

,





n

.

3

Działania (2)

Szczególnie ważny przypadek stanowi funkcja:

 



:

A A

A,

czyli dla



2

n

, którą nazywamy działaniem wewnętrznym dwuargumentowym

(operacją binarną).

Zbiór z działaniem wewnętrznym oznaczamy







,

A

, a wynik działania na parze

elementów

,

a b

zapisujemy



a b , zamiast pisać







,

a b

.

Często działania oznaczamy symbolami:

    

, , ,*, ,

.

Przykład

 

  



:





 



,

n k

n k

,











n k

, czyli piszemy









, .

4

Działania (3)

Działaniem zewnętrznym w niepustym zbiorze

A

nad niepustym zbiorem

B

nazywamy każdą funkcję:



 

:

B A

A

.

Działanie zewnętrzne oznaczamy







,

b a

, gdzie





,

b B a A

.

Przykład

Niech

A

– zbiór wektorów na płaszczyźnie, a





B

. Działaniem zewnętrznym w

zbiorze

A

nad zbiorem

B

jest mnożenie wektora przez liczbę rzeczywistą, wynikiem

działania jest wektor.

UWAGA.

Ponieważ zbiory

A

i

B

nie muszą być różne, to działanie wewnętrzne jest

szczególnym przypadkiem działania zewnętrznego.

5

Wybrane własności działania wewnętrznego



Łączność

d

ziałanie



nazywamy łącznym w zbiorze

A

, jeżeli:















 

 

, ,

:

a b c A a b c a b c

.



Przemienność

d

ziałanie



nazywamy przemiennym w zbiorze

A

, jeżeli:











,

:

a b A a b b a

.

Na przykład, dodawanie w zbiorze liczb naturalnych



jest działaniem łącznym

i

przemiennym, a odejmowanie w zbiorze liczb całkowitych



nie jest ani łączne, ani

przemienne.

6

Element neutralny i element odwrotny (1)

Element



e A

nazywamy elementem neutralnym

(względem działania



) , jeżeli:

 









:

a A a e e a a

.

Element



b A

nazywamy elementem odwrotnym do elementu

a

, jeżeli:









a b b a e .

Element odwrotny do elementu

a

oznaczamy symbolem



1

a

.

Na przykład, elementem neutralnym dodawania w zbiorach    

, , , jest 0, zaś

elementem neutralnym mnożenia w zbiorach    

, , , jest 1.

7

Element neutralny i element odwrotny (2)

Twierdzenie 1.

W zbiorze

A

, w którym określone jest działanie



, istnieje co najwyżej jeden element

neutralny.

Twierdzenie 2.

Jeżeli działanie łączne



w zbiorze

A

posiada element neutralny, to do danego

elementu

istnieje co najwyżej jeden element odwrotny.

8

Podstawowe struktury algebraiczne (1)

Najprostszą „strukturą algebraiczną” jest półgrupa.
Zbiór

A

wraz z działaniem wewnętrznym łącznym



, nazywamy

półgrupą

i oznaczamy







,

A

.

Nieco bardziej skomplikowaną strukturą, która jednak jest często wykorzystywana,
jest grupa.

Zbiór

G

wraz działaniem wewnętrznym



nazywamy

grupą i oznaczamy







,

G

,

jeżeli:





jest działaniem łącznym;

 w zbiorze

G

istnieje element neutralny działania



;



 

g G

istnieje element odwrotny





1

g

G

.

Warunki te

nazywa się aksjomatami grupy.

E

lement neutralny w grupie nazywa się jednością grupy.

Jeżeli dodatkowo działanie wewnętrzne



jest przemienne w

G

, to grupę tę

nazywamy

przemienną lub abelową.

9

Podstawowe struktury algebraiczne (2)

Twierdzenie. W dowolnej grupie







,

G

dla

 

g G

istnieje dokładnie jeden element

odwrotny w

G

.

Niech







,

G

będzie grupą i niech



,

a b G

, wtedy zachodzą następujące własności

grupy:







1

;

e

e



 







1

1

;

a

a



















1

1

1

;

a b

b

a



każde z równań





a x b oraz





y a b

posiada jednoznaczne rozwiązanie

w

.

G

10

Zapis multiplikatywny i addytywny (1)

Jeżeli mamy do czynienia z grupami nieabelowymi oraz z grupami w ogóle, działanie



oznacza się symbolem



i nazywa się mnożeniem, wówczas zamiast pisać



a b

piszemy często

ab

. Element neutralny oznaczamy wtedy przez



1

e

, a element

odwrotny do

a

przez



1

.

a

Wyrażenie

   





...

n razy

a a a

a

oznaczamy

n

a

i nazywamy

n

–tą potęgą elementu

a

. Taki

sposób zapisu nazywa się multiplikatywnym.
W grupach abelowych przyjmuje się oznaczenie działania



przez



i nazywa je

dodawaniem

. Element neutralny oznacza się wtedy przez



0

e

, a element odwrotny

do

a

przez



a

(element przeciwny), wtedy zamiast pisać

 

 

a

b

piszemy



a b

.

Wyrażenie

   







...

n razy

a a a

a

oznaczamy



n a

i nazywamy

n

–tą wielokrotnością

elementu

a

. Taki sposób zapisu nazywa się addytywnym.

Przykład.
Zbiór







0,1,2,3

A

, działanie



jest określone jako:



 



,

:

reszta z dzielenia

przez 4

a b A a b

a b

. Sprawdzić, czy







,

A

jest grupą.

11

Rząd grupy, grupy cykliczne

Jeśli







,

G

jest grupą i zbiór

G

jest skończony, to liczbę elementów zbioru

G

nazywamy

rzędem grupy

G

i oznaczamy

G

.

Jeśli zbiór

G

jest nieskończony to mówimy, że rząd grupy

G

jest nieskończony i

piszemy

 

G

.

Grupę







,

G

,

której wszystkie elementy można wyrazić przy pomocy pewnego jej

elementu

a

nazywa się grupą cykliczną. Równoważnie, jest to grupa generowana

przez jeden z jej elementów (elementów które generują tę grupę może być wiele).

Element

a

nazywa się wtedy generatorem grupy cyklicznej, co zapisujemy



G

a

.

Korzystając z logiki predykatów można zapisać:



    

 





:

.

n

G

a

a G g G n

g a

Przy wykorzystaniu terminologii addytywnej:

 

g n a

.

Każda grupa cykliczna jest abelowa, ale nie na odwrót. Na przykład,

 









\ 0 ,

jest

grupą abelową, ale nie jest to grupa cykliczna.

12

Podgrupa

Niech







,

G

będzie grupą. Podzbiór

H

zbioru

G

(



H G

), taki, że







,

H

jest grupą

nazywamy

podgrupą grupy

G

i oznaczamy



H G

.

Każda grupa zawiera jako podgrupy siebie samą i grupę zawierającą tylko jedność,
są to tak zwane podgrupy niewłaściwe. Pozostałe podgrupy nazywamy
właściwymi.

13

Pierścień (1)

Zbiór

P

, z dwoma działaniami wewnętrznymi



i



nazywamy

pierścieniem i

oznaczamy





 

, ,

P

, jeśli:









,

P

jest grupą abelową,



działanie



jest łączne w zbiorze

P

, tzn.















  



, ,

:

a b c P a b

c a

b c

.



działanie



jest rozdzielne względem działania



, tzn.







 









 







, ,

:

a b c P a b

c

a c

b c

oraz







 



















, ,

:

a b c P c

a b

c a

c b

14

Pierścień (2)

Działanie



nazywamy dodawaniem i oznaczamy zwykle symbolem



. Element

neutralny względem działania



nazywamy zerem

pierścienia.

Działanie



nazywamy

mnożeniem i oznaczamy zwykle symbolem



.

Jeżeli w

P

istnieje element neutralny względem działania



, to nazywamy go

jedynką pierścienia i oznaczamy symbolem 1, a sam pierścień





 

, ,

P

nazywamy

pierścieniem z jedynką.

Jeżeli działanie



jest przemienne w

P

, to pierścień





 

, ,

P

nazywamy

przemiennym.

15

Ciało (1)

C

iałem intuicynie nazywamy zbiór , w którym potrafimy wykonywać 4 podstawowe

działania:

  

, , ,/. Ponieważ odejmowanie to dodawanie elementu przeciwnego, a

dzielenie to mnożenie przez odwrotność wystarczy rozważyć dwa działania

 

,

.

Zbiór

K

, z dwoma działaniami wewnętrznymi

 

,

nazywamy ciałem i oznaczamy





 

, ,

K

, jeśli:







 

, ,

K

jest pierścieniem przemiennym z jedynką, gdzie jedynka nie jest równa 0,



dla każdego niezerowego elementu zbioru

K

istnieje element odwrotny

względem działania



, tzn.:

 

 

 

 

\ 0

:

1

a K

b K a b

Drugi warunek oznacza, że zbiór

 







\ 0 ,

K

jest grupą. Nazywamy ją grupą

multiplikatywną ciała





 

, ,

K

.

Grupę







,

K

nazywamy grupą addytywną ciała





 

, ,

K

.

16

Ciało (2)

Jeśli zbiór

K

jest skończony, to ciało





 

, ,

K

nazywamy

skończonym i odpowiednio

gdy zbiór

K

jest nieskończony to ciało nazywamy nieskończonym.

Ciałami nieskończonymi są



 

 



 

 

 







, , ,

, , , , , .

Ciała skończone nazywane są ciałami Galois. Przykładem takich ciał mogą być
ciała





 



, ,

p

, gdzie

p

jest liczbą pierwszą.