Strona główna

Wykład jedenasty


Pobieranie 99.2 Kb.
Data18.06.2016
Rozmiar99.2 Kb.




Wykład jedenasty

Temat XII.1

Teorie uporządkowania


Teoria relacji
Zbiór M nazywamy uporządkowanym, o ile wśród jego elementów m panuje (herrscht) określony ‘porządek wedle rangi’, taki, że z dowolnych dwóch elementów m1 i m2 jeden przyjmuje rangę ‘niższą’ a drugi rangę ‘wyższą, i taki, że gdy z trzech elementów m1, m2 i m3, powiedzmy m1 jest niższej rangi niż m2, zaś m2 jest niższej rangi niż m3, to wówczas m1 jest niższej rangi niż m3. (G. Cantor1932, s. 298)
Terminologia
łac. relatio - stosunek

R - relacja



xRy czytamy: x pozostaje w relacji R do y

Ważny jest kierunek relacji; w relacji dwuczłonowej wyróżniony jest człon pierwszy.


Przykłady

R - bycie żonatym; xRy - x jest mężem y

R – bycie ojcem; xRy - x jest ojcem y

R – relacja nierówności; xRy x < y - x jest liczbą mniejszą od y

R – relacja prostopadłości; xRy - x jest prostopadła do y
Relacja dwuczłonowa to funktor zdaniotwórczy o dwóch argumentach nazwowych, o indeksie: z/n, n.
C(R) - pole relacji R (campus - pole) to zbiór wszystkich tych przedmiotów, które pozostają w danej relacji, między którymi ta relacja zachodzi.

Przykład: Polem relacji bycia czyimś mężem jest zbiór tych i tylko tych osób, które pozostają w związku małżeńskim.


D(R) - dziedzina relacji R (lewa dziedzina relacji R) to zbiór wszystkich i tylko tych przedmiotów, które pozostają w relacji R do jakiegoś przedmiotu; inaczej, to zbiór wszystkich pierwszych członów relacji.
x należy do dziedziny relacji R wtedy i tylko wtedy, gdy istnieje taki y, że x pozostaje w relacji R do y.

xD(R) y xRy D(R) = {x: xRy}


PD(R) - przeciwdziedzina relacji R (prawa dziedzina relacji R) to zbiór wszystkich i tylko tych przedmiotów, do których jakiś przedmiot pozostaje w relacji R
y należy do przeciwdziedziny relacji R wtedy i tylko wtedy, gdy istnieje taki x, że x pozostaje w relacji R do y.
yPD(R)  x xRy PD(R) = {y: xRy}
Pole relacji R jest sumą mnogościową dziedziny i przeciwdziedziny relacji R
C(R) = D(R)  PD(R)
R* - konwers relacji R, inaczej relacja odwrotna do relacji R to relacja zdefiniowana następująco:
yR*x xRy
Para uporządkowana y, x należy do relacji R* wtedy i tylko wtedy, gdy para uporządkowana x, y należy do relacji R. Inaczej, konwers relacji R jest relacją, która zachodzi między tymi samymi przedmiotami, co relacja R, ale w kierunku odwrotnym.

Zachodzi: y, x R*  x, y R


Przykład: Konwersem relacji bycia czyimś mężem jest relacja bycia czyjąś żoną. Konwersem relacji bycia czyimś rodzicem jest relacja bycia czyimś dzieckiem.
Właściwości konwersu relacji R:
1) D(R*) = PD(R)

Dziedzina konwersu relacji R równa jest przeciwdziedzinie relacji R.


2) (R*)* = R

Konwers konwersu relacji R jest równy tej relacji.


Definicja relacji jako iloczynu kartezjańskiego
X, Y, Z - zbiory

x  X, y  Y, z  Z

 x, y  - para uporządkowana o pierwszym elemencie x i drugim elemencie y

Relacja dwuczłonowa R to zbiór par uporządkowanych.


xRy  x, y 
Piszemy:

 x, y   R  xRy

R (x, y) =x, y = xRy

R  X x Y

R  D(R) x PD(R); przy X = D(R), Y = PD(R)
Przykład. Funkcja matematyczna jest relacją dwuczłonową zachodzącą między elementami dziedziny funkcji a elementami przeciwdziedziny funkcji.

f - funkcja (matematyczna); f: X Y, y = f (x)

Funkcja f jako podzbiór iloczynu kartezjańskiego dziedziny i przeciwdziedziny (X x Y):

f  X x Y:  x, f (x) 

 x, f (x)   f  y = f (x); f = x, f (x)
Relacja trójczłonowa to zbiór (klasa) pewnych trójek uporządkowanych.
R (x, y, z) =  x, y, z 

x, y, z   X x Y x Z


Przykład relacja trójczłonowej S - y leży między x a z: Warszawa leży między Krakowem a Gdańskiem.

Przykład relacja czwórczłonowej T (x, y, z,v) = x, y, z,v : x jest poręczycielem (żyrantem) y wobec z na kredyt o wielkości v.


Ogólnie: relacja n-członowa to zbiór (klasa) pewnych układów uporządkowanych

n-elementowych.


R (x1, x2, …, xn) =  x1, x2, …, xn
 x1, x2, …, xn   XN = X x X x … x X (n razy)
Rodzaje relacji
1) Relacja R jest zwrotna wtedy i tylko wtedy, gdy

x  D(R) xRx


Relacja R jest zwrotna wtedy i tylko wtedy, gdy każdy element jej dziedziny pozostaje w relacji R ze sobą.

Przykłady. Relacjami zwrotnymi są relacje:

- bycia równym wiekiem w zbiorze ludzi: każdy człowiek ma ten sam wiek, co on sam

- relacja słabej nierówności (mniejszy lub równy) w zbiorze liczb

- relacja podobieństwa w zbiorze przedmiotów.
2) Relacja R jest przeciwzwrotna wtedy i tylko wtedy, gdy:
x D(R) xRx
Relacja R jest przeciwzwrotna wtedy i tylko wtedy, gdy żaden element jej dziedziny nie pozostaje ze sobą w relacji R.

Przykłady. Relacjami przeciwzwrotnymi są relacje:

- bycia czyimś dzieckiem w zbiorze ludzi - żaden człowiek nie jest swoim dzieckiem

- relacja ostrej nierówności (bycia mniejszym lub bycia większym) w zbiorze liczb - żadna liczba nie jest mniejsza ani większa od siebie samej.


3) Relacja R jest symetryczna wtedy i tylko wtedy gdy:

x, y C(R) xRy  yRx


Relacja symetryczna to taka relacja, która gdy zachodzi między dowolnymi dwoma elementami pola relacji w jednym kierunku, to zachodzi również między tymi elementami w kierunku odwrotnym.

Przykłady relacji symetrycznych:

- bycie czyimś krewnym w zbiorze ludzi

- bycie bliźniakiem w zbiorze ludzi

- stosunek krzyżowania się zakresów w zbiorze nazw

- relacja prostopadłości między odcinkami


4) Relacja R jest asymetryczna wtedy i tylko wtedy gdy:

x, y C(R) xRy  yRx


Relacja asymetryczna to taka relacja, która gdy zachodzi między dowolnymi dwoma elementami w jednym kierunku, to nie zachodzi między tymi elementami w kierunku odwrotnym.

Przykłady relacji asymetrycznych:

- stosunek bycia ojcem

- bycie starszym zbiorze ludzi

- inkluzja właściwa ( ) między zbiorami

- podrzędność zakresów nazw


Dla relacja asymetrycznej nie jest prawdziwa także implikacja odwrotna do implikacji podanej w jej definiensie: tzn., z tego, że nie zachodzi yRx nie wynika, że zachodzi xRy.

Przykład:

R – relacja mniejszości liczb x  y

Dla x  6, y  2  3

Zachodzi yRx, tj. (6  2  3), ale nie zachodzi xRy: 2  3  6
5) Relacja R jest przechodnia wtedy i tylko wtedy, gdy:

x, y, z  C(R) [xRy  yRz]  xRz


Relacja przechodnia to taka relacja, że jeśli zachodzi między pierwszym elementem z jej pola a drugim oraz między drugim a trzecim, to także zachodzi między elementem pierwszym a trzecim.

Przykłady relacji przechodnich

- bycie starszym w zbiorze ludzi

- relacje słabej/mocnej nierówności (, ) w zbiorze liczb

- relacja implikacji (p  q) w teorii zdań

- relacja inkluzji (A  B) w teorii mnogości


6) Relacja R jest relacją nieprzechodnia wtedy i tylko wtedy, gdy nie jest relacją przechodnią, tj. gdy relacja spełnia warunek:

 x, y, z  C(R) xRy  yRz  xRz


Powyższą definicję otrzymujemy z definicji relacji przechodniej przez:

1) jej zanegowanie

2) zastosowanie prawa de Morgana dla rachunku predykatów: v E  v E

3) zastosowanie do prawej strony definicji

a) jednego z praw negowania implikacji: (p  q)  (p  q) oraz

b) reguły podstawiania (RP)

Przykłady:

- relacja prostopadłości w zbiorze linii prostych

- relacja bycia matką w zbiorze ludzi

- relacja bycia czyimś bratem w zbiorze ludzi. Dla x, y z , gdzie x jest bratem y i y jest bratem z, przy x = z mamy xRz, gdyż nikt nie jest swoim bratem.


7) Relacja R spójna wtedy i tylko wtedy, gdy:

x, y C(R) x  y  xRy  yRx


Relacja spójna to taka relacja, która dla dowolnych dwóch różnych zachodzi albo w jednym albo w drugim kierunku. Przykłady:

- relacja  w zbiorze liczb. Dla każdych dwóch liczb a i b zachodzi: jeśli a  b to albo jest

a  b, albo b  a.

- relacja bycia jaśniejszym lub ciemniejszym odcieniem jednej barwy, np. niebieskiej. Z dwóch różnych odcieni tej barwy bądź pierwszy jest jaśniejszy od drugiego, bądź drugi od pierwszego.


8) Relacja R jest relacją porządkującą wtedy i tylko wtedy, gdy jest relacją:

1) asymetryczną,

2) przechodnią i

3) spójną.


Przykłady:

- relacja mniejszości  porządkuje dowolny zbiór liczbowy

- relacja zajęcia miejsca w kolejce za ostatnią ze stojących w niej w osób jest relacją porządkującą w zbiorze klientów np. w sklepie.

9) R jest relacją równoważności wtedy i tylko wtedy, gdy jest zarazem:

1) zwrotna

2) symetryczna i

3) przechodnia.
Przykłady relacji równoważności:

- równoważność zdań w rachunku zdań (p  q)

- podobieństwo trójkątów

- równoległość w zbiorze linii prostych


Dla relacji równoważności zachodzi:

DR(R) = PD(R) = C(R)



Klasy abstrakcji relacji równoważności, zbiór ilorazowy
≈ – relacja równoważności określona na C(≈)

Zachodzi: DR(≈) = PD(≈) = C(≈)


||x|| – zbiór tych wszystkich elementów C(≈), które pozostają do x w relacji ≈
||x|| = {yC(≈): x ≈ y}
Definicja
||x|| nazywamy klasą abstrakcji relacji równoważności (≈) wyznaczoną przez element x

Dla y  C(≈) mamy: y ||x||  x ≈ y


Tworzenie klas abstrakcji jest metodą utożsamiania elementów równoważnych i umożliwia definiowanie przez abstrakcję. Przedmioty, między którymi zachodzi relacja równoważności są przedmiotami mającymi pewną wspólną własność przysługującą wszystkim takim właśnie przedmiotom, a nie przysługującą przedmiotom, które do nich nie pozostają w tej relacji. Np. wszystkie trójkąty pozostające w relacji podobieństwa mają ten sam kształt. Tak więc zdanie stwierdzające, że dany trójkąt ma określony kształt jest równoważne zdaniu stwierdzającemu, że ten trójkąt należy do pewnej klasy przedmiotów, tej, do której należą wszystkie i tylko te trójkąty, które są do niego podobne. Inaczej mówiąc za pomocą pojęcia podobieństwa trójkątów – które jest relacją równoważności – można zdefiniować ogólniejsze pojęcie kształtu trójkąta. Tego rodzaj definicję nazywa się definicją przez abstrakcję.
Właściwości klas abstrakcji:

(1) x ||x||


(2) ||x|| = ||y||  x ≈ y
Klasy abstrakcji wyznaczone przez elementy x oraz y są identyczne wtedy i tylko wtedy, gdy x i y są równoważne.
(3) x, y (||x||  ||y||)  ||x||  ||y||  
Dwie różne klasy abstrakcji są rozłączne.

Ponieważ zachodzi:


(4) x, y (||x||  ||y||  )  ||x||  ||y||, mamy równoważność:
(5) x, y (||x||  ||y||)  (||x||  ||y||  )
Twierdzenie: Dowolna relacja równoważności w niepustym zbiorze X wprowadza podział tego zbioru na niepuste i rozłączne podzbiory, tj. klasy abstrakcji tej relacji.

Zbiorem ilorazowym (X/ ≈) dla zbioru X i relacji równoważności ≈ nazywamy zbiór (rodzinę zbiorów) wszystkich klasy abstrakcji tej relacji.


Zastosowania klas abstrakcji
Klasy abstrakcji stanowią logiczne uzasadnienie dla praktycznego stosowania wielu pojęć ogólnych w praktyce.
a) pojęcie to wykorzystuje się przy określaniu miar odległości i czasu.

Długość dowolnego odcinka (np. centymetra, metra) określamy jako klasy abstrakcji relacji przystawania odcinków.

Chwile czasowe w danym układzie odniesienia, tj. jednostki miary czasu (sekunda, minuta, godzina) określamy jako klasy abstrakcji relacji równoczesności zdarzeń (w danym układzie odniesienia).

b) pojęcie pojęcia klasy abstrakcji wykorzystuje się w logicznej teorii języka. Relacją równoważności w zbiorze wyrażeń danego języka (który nie zawiera wyrażeń wieloznacznych) jest relacja która zachodzi między wyrażeniami danego języka wtedy i tylko wtedy, gdy po zastąpieniu jednego z nich przez drugie z dowolnego wyrażenia sensownego otrzymujemy znowu wyrażenie sensowne. Klasami abstrakcji tej relacji są kategorie składniowe wyrażeń danego języka.


Współczesne wersje algebr Boole’a
G. Malinowski Logiki wielowartościowe, ss. 8 -9
Pierwotne intuicje Boole’a najłatwiej wyartykułować, odwołując się do teorii mno­gości. Niech U oznacza pewien zbiór uniwersalny (przestrzeń), którego elementami są wszystkie (rozważane) obiekty oraz  zbiór pusty (nie zawierający żadnego elementu). Niech ponadto P(U) oznacza rodzinę wszystkich podzbiorów U:
P(U) = {X : XU }
Wówczas dowolny zbiór XP(U), tj. dowolny podzbiór XU, można utożsamiać z funkcją z U w zbiór (klasycz­nych) wartości logicznych, X: U {0, 1}, określoną dla dowolnego

a U następująco:


X (a) = 1, jeśli aX
X (a) = 0, jeśli aX
Równość X (a) = 1(0) czytamy „aX jest prawdą (jest fałszem)”. Opisaną funkcję nazywa się często funkcją charakterystyczną zbioru X (w przestrzeni U). Zauważmy, że w przyjętej nomenklaturze U i  są funkcjami stałymi o wartościach, odpowiednio, l i 0.

Na zdefiniowanym zbiorze funkcji określmy operacje:



- dopełnienia

- sumy, oraz

 - ilo­czynu, przyjmując, że dla dowolnego a U:
X (a) = l - X(a)
XY(a)=max{X(a), Y(a)}
XY(a)=min{X(a),Y(a)}.
Jeśli następnie wprowadzimy relację częściowego porządku , kładąc

X Y wtedy i tylko wtedy, gdy X (a)  Y(a) dla dowolnego a U,
to okaże się, że XY jest kresem górnym a XY kresem dolnym zbiorów X i Y . Zatem rodzina P(U) jest kratą z elementem największym U i elementem najmniejszym . Krata ta jest dystrybutywna dla dowolnych X, Y, Z P(U) zachodzi
X  (Y  Z) = (X  Y)  (X  Z )

X  (Y  Z) = (X  Y)  (X  Z)
i wyposażona w operację uzupełnienia, bowiem
X X = U, X  X = 
We współczesnej teorii algebr abstrakcyjnych algebrę Boole’a definiuje się jako

do­wolną, uzupełnioną kratę dystrybutywna mającą element największy l („jedynkę”) i najmniejszy 0 („zero”).


Strukturę (L,, , l, 0) nazywamy algebrą Boolea wtedy i tylko wtedy, gdy spełnione są aksjomaty:
(L1) x  y = y  x

x  y = y  x

(L2) x  (y  z) = (x  y) z – łączność

x  (y  z) = (x  y) z – łączność

(L3) x  x = x

x  x = x

(L4) x  (x  y) = x

x  (x  y) = x

(L5) x  (y  z) = (x  y)  (x  z ) – rozdzielność  względem (dystrybutywność)

x  (y  z) = (x  y)  (x  z) – rozdzielność względem  (dystrybutywność)

(L6) x  0 = x, x  1 = x

(L7) x x = x, x  x = 0
(L1) - (L4) definiują kratę

(L5) są warunkami dystrybutywności

(L6) wskazuje 0 jako element najmniejszy i l jako element największy, zaś

(L7) charakteryzuje operację uzupełnienia.


Algebry Boole’a mogą być budowane z dowolnych (bliżej nieokreślonych) elemen­tów. Teoria reprezentacji podaje rozmaite metody przedstawiania ich jako pewnych „kon­kretnych" struktur algebraicznych. Na szczególną uwagę zasługuje reprezentacja algebr Boole'a przy użyciu tzw. ciał zbiorów. Ciałem zbiorów jest niepusta rodzina podzbio­rów dowolnego (niepustego) zbioru zamknięta ze względu na operacje sumy, dopełnienia i iloczynu; przykładem ciała zbiorów jest rodzina P (U) rozważana wyżej. Każda algebra Boole'a jest (izomorficzna z) pewnym ciałem zbiorów. Najprostszą algebrą Boole’a jest dwuelementowa struktura:
B2 = ({0,1}, , , , l, 0)
o operacjach określonych tabelkami alternatywy, koniunkcji i negacji.
Algebra Lindenbauma - algebra Boole’a na klasach abstrakcji tautologii krz
Rozważmy teraz binarną relację  określoną na zbiorze For formuł KRZ następująco:

Dla dowolnych  For:



 wtedy i tylko wtedy, gdy jest tautologią
(równoważnie: wtedy i tylko wtedy, gdy dla dowolnego wartościowa­nia v : For {0, 1}).

W zbiorze klas abstrakcji relacji (ozn.: For/ ) wprowadźmy operacje:



, ,  wzorami:
||||

|| ||  ||

|| ||  ||
Połóżmy ponadto: 0 = ||i 1 = ||.

Łatwo sprawdzić, że wprowadzone operacje i stałe spełniają aksjomaty (L1) - (L7), (p. wyżej) definicji algebry Boole’a.


Algebrą Lindenbauma (logiki klasycznej) nazywa się algebra Boole’a o następującej postaci:

L_= (For/ , , , , l, 0)
Tautologie równoważnościowe a równania w algebrze Lindenbauma

Dowolna tautologia logiki klasycznej będąca równoważnością wyznacza pewną równość algebry L_ i, na odwrót, dowolnej równości (równaniu) tej algebry odpowiada klasa (schemat) tautologii. Taki związek zachodzi na przykład pomiędzy formułą



α  (β  ) oraz pierwszą z równości w aksjomacie (L5):

x  (y  z) = (x  y)  (x  z ). W pewnym więc sensie teoria algebr Boole’a jest algebraiczną wersją logiki klasycznej.

-------------------


©snauka.pl 2016
wyślij wiadomość