« poprzedni punkt   następny punkt »


15.3. Generatory algebr

Niech będzie dana pewna algebra A, której uniwersum stanowi zbiór A. Operacje tej algebry zawsze dają wyniki należące do uniwersum algebry. Jeśli a = o(a1, a2, ...,an), to możemy traktować wyrażenie o(a1, a2, ...,an), jako definicję elementu a. Z kolei element a może być użyty do zdefiniowania elementu a', jako wyniku pewnej operacji określonej w A, np. a' = o'(a, a'1, a'2, ...,a'm), itd.

Możemy postawić pytanie, jakie elementy zbioru A są konieczne, by zdefiniować (wygenerować) przy ich pomocy i przy pomocy operacji algebry A wszystkie inne elementy uniwersum algebry? Najmniejszy podzbiór A, który wystarczy do określenia wszystkich innych obiektów, nazywa się zbiorem generatorów algebry.

Jeśli sprawa nie jest jeszcze jasna, to zauważmy że wiele zbiorów tworzymy niejako od podstaw: definiując najpierw "najprostsze" elementy, a potem z nich, przy pomocy pewnych określonych operacji, konstruujemy inne obiekty tego zbioru. Tak właśnie postąpiliśmy ze zbiorem formuł rachunku zdań: ustaliliśmy zbiór zmiennych i opisaliśmy, jak przy pomocy operacji alternatywy, koniunkcji, implikacji i negacji utworzyć inne elementy zbioru formuł. Podobnie zresztą postępujemy w informatyce. Definicja zbioru obiektów tworzonych przez programistę polega na ogół na określeniu jednego albo kilku najprostszych obiektów i zdefiniowaniu procesu tworzenia innych (konstruktor w klasie). Ten najprostszy zbiór obiektów, służący do zdefiniowania innych obiektów zbioru to właśnie zbiór generatorów algebry.

Definicja tego pojęcia jest dość skomplikowana i wymaga wprowadzenia pojęcia podalgebry.

Definicja 15.3.1

Niech A = < A, o1, o2,..., on > będzie algebrą i A' niepustym podzbiorem zbioru A. Wówczas A' = <A',o1, o2,..., on> nazywamy podalgebrą algebry A, jeżeli zbiór A' jest zamknięty ze względu na operacje o1, o2,..., on.

Jeśli w zbiorze A określone są relacje r1, r2, ..., rm , to są one też określone w podzbiorze A'. Zatem definicję podalgebry możemy rozszerzyć na systemy relacyjne przyjmując, że A' = <A',o1, o2,..., on; r1, r2, ..., rm > jest podsystemem systemu A =< A, o1, o2,..., on ; r1, r2, ..., rm > wtedy i tylko wtedy, gdy A' ⊆ A i zbiór A' jest zamknięty ze względu na wszystkie operacje o1, o2,..., on systemu A. W gruncie rzeczy, operacje i relacje w systemie A' są obcięciami funkcji i relacji systemu A, do zbioru A'.

W tej części wykładu będziemy się głównie zajmowali algebrami, ale przyjęte tu definicje i fakty można natychmiast uogólnić na dowolne systemy algebraiczne.

Rozważmy algebrę < R, +, * > jaką tworzy zbiór liczb rzeczywistych z operacjami dodawania i mnożenia. Systemy <R+, +, * >, <Q, +, * >, <N, +, * > , <P, + ,* > , <{3k: k ∈ N}, +, * > z operacjami dodawania i mnożenia obciętymi do odpowiednich uniwersów są różnymi podalgebrami systemu < R, +, * >.

Łatwo zauważyć, że przecięcie dwóch zbiorów zamkniętych ze względu na pewną operację jest też zamknięte na tę operację. Rzeczywiście, jeśli rozważane zbiory to A i B, i rozważana operacja n-argumentowa o ma własność :

dla dowolnych a1,... an ∈ A, o(a1,..., an) ∈ A i

dla dowolnych b1,...bn ∈ B, o(b1,..., bn) ∈ B,

to dla x1, ..., xn ∈ A ∩ B, mamy o(x1,...,xn) ∈ A i o(x1,...xn) ∈ B, czyli o(x1,...,xn) ∈ A ∩ B.

Następujący lemat uogólnia nieco tę obserwację.

Lemat 15.3.1

Przecięcie dowolnego zbioru podalgebr dowolnej algebry albo jest puste, albo samo jest podalgebrą tej algebry.

Definicja 10.4

Niepusty podzbiór G zbioru A nazywamy zbiorem generatorów algebry <A, o1, o2, ..., on > wtedy i tylko wtedy, gdy najmniejszą podalgebrą zawierającą G jest sama algebra <A, o1, o2, ..., on >. O zbiorze G mówimy, że generuje zbiór A.

Przedstawiona definicja może nastręczać nieco trudności. Zastanówmy się nad jej sensem. Z lematu 15.3.1 wynika, że jeśli rozważymy rodzinę podalgebr pewnej algebry zawierających jakiś ustalony niepusty zbiór G, to ich przecięcie też zawiera zbiór G i jest podalgebrą A. Przecięcie wszystkich podalgebr zawierających G jest najmniejszą podalgebrą zawierającą G. Jeżeli ta najmniejsza podalgebra zawierająca G ma być identyczna z A, to znaczy, że każdy element zbioru A da się otrzymać jako wynik działania pewnej operacji systemu na argumentach z G. Każdy element algebry A można wygenerować z elementów zbioru G stosując odpowiednie operacje systemu.

Przykład 15.3.1

  1. Zbiorem generatorów algebry <N, suc, 0 >, gdzie suc jest operacją następnika w N, jest zbiór {0}. Rzeczywiście, każda liczba naturalna może być otrzymana z zera przez dodawanie jedynki. Mamy suc(0)= 1, suc(suc(0))= 2, suc(suc(suc(0))) = 3 itd.

  2. Zbiorem generatorów algebry < N,+, * > jest zbiór {0,1}. Zauważmy, że samo zero ani sama jedynka nie wystarczą.

  3. Zbiorem generatorów algebry < Z, +, * > jest zbiór {-1}. Rzeczywiście, +1 otrzymamy w wyniku mnożenia (-1)*(-1) , a 0 w wyniku dodawania (-1) + (+1). Każdą dodatnią liczbą całkowitą otrzymamy z zera przez dodawanie 1. Każdą liczbę całkowitą ujemną otrzymamy z 0 przez dodawanie (-1).

  4. Zbiorem generatorów dla struktury stosów <S ∪ E, push, pop, top, empty, = > jest zbiór {empty} ∪ E, bo każdy stos możemy utworzyć ze stosu pustego przez włożenie przy pomocy operacji push odpowiednich elementów.

Pytanie 15.3.1 Rozważymy instrukcję "while y ≠ x do x:= x+1; od" w strukturze liczb naturalnych. Jaki warunek konieczny i dostateczny muszą spełniać na początku x i y, aby ta pętla zakończyła działanie?

Zobacz odpowiedź


« poprzedni punkt   następny punkt »