ZNAKI !

Kwantyfikator egzystencjalny „ ဤ “

ဤy჎ Y CZYT. „dla pewnego y należącego do zbioru Y”

Kwantyfikator ogólny „ ဢ ”

ဢx჎X CZYT. „dla każdego x należącego do zbioru X”

Implikacja „პ” czyt. Wynika z…

Relacja rownowaznosci „მ” czyt. „wtedy i tylko wtedy, gdy”

x R a czyt. „ x jest w relacji (R) z a”

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

Rozważmy relację RჍXႴX

- R jest zwrotna w X, jeśli ဢx჎X <x,x>჎R

- R jest przeciwzwrotna w X, jeśli ဢx჎X <x,x>჏R

- R jest symetryczna w X, jeśli ဢx,y჎X <x,y>჎R პ<y,x>჎R

- R jest antysymetryczna w X, jeśli ဢx,y჎X <x,y>჎R კ <y,x>჎R პ x=y

- R jest przeciwsymetryczna w X, jeśli ဢx,y჎X <x,y>჎R პ<y,x>჏R

- R jest przechodnia w X, jeśli ဢx,y,z჎X <x,y>჎R კ <y,z>჎R პ <x,z> ჎R

- R jest spójna w X, jeśli ဢx,y჎X <x,y>჎R ლ <y,x>჎R ლ x=y

Odwracanie i składanie relacji

Definicja odwracanie

Jeżeli R jest relacją binarną w X Ⴔ Y, to R ^-1 jest relacją binarną w

Y Ⴔ X, zdefiniowaną następująco: R ^-1={<y,x> : <x,y>჎R }.

Definicja skladanie

Jeśli RჍXႴY oraz SჍYႴZ, to relację

T={<x,z> : ဤy <x,y>჎R კ <y,z>჎S} nazywamy złożeniem relacji R i S (zamiast T można zapisać SႰR).

Relacja równoważności

Relację RჍXႴX nazywamy relacją równoważności wttw R jest relacją zwrotną, symetryczną i przechodnią. Np.: 3. L - zbiór samochodów RჍLႴL ဢl, h჎L

l R h მ l został wyprodukowany przez tę samą firmę co h

Klasa abstrakcji

Definicja

Niech R będzie relacją równoważności w zbiorze X, wtedy dla dowolnego x ჎X, zbiór [x]_R= {y ჎ X : x R y} nazywamy klasą abstrakcji relacji R o reprezentancie x.

Funkcja jako relacja

Definicja

Niech X i Y będą dowolnymi zbiorami. Relację RჍXႴY nazywamy

Funkcją, jeśli spełnia ona następujące warunki:

1. ဢx჎X ဤy჎Y x R y

2. ဢx჎X ဢy₁,y₂ ჎Y ( x R y₁ კ x R y₂ ) პ y₁=y₂

Twierdzenie Każda relacja równoważności R w zbiorze XႹ჆ ustala podział tego zbioru. Podział ten tworzą klasy abstrakcji tej relacji (relacji R).

Obraz i przeciwobraz zbioru

Definicja

Załóżmy, że A჌X oraz fჍXႴY (f:XႮY) jest funkcją.

Obrazem zbioru A przez funkcję f nazywamy zbiór f(A)={y : ဤx჎A y=f(x) }

([ x ] Obraz (f-obraz) zbioru przez funkcję może być zbiorem jednoelementowym. )

Definicja

Załóżmy, że Z჌Y oraz fჍXႴY (f:XႮY) jest funkcją.

Przeciwobrazem zbioru Z przez funkcję f nazywamy zbiór f^-1(Z)={x : ဤy჎Z f(x)=y }

([ x ] Przeciwobraz (f-przeciwobraz) zbioru co najmniej dwuelementowego przez funkcję nie może być zbiorem jednoelementowym.)

Relacje porządkujące

Definicja

Relację binarną R w zbiorze X nazywamy porządkiem(częściowym porządkiem) wttw R jest relacją zwrotną,

antysymetryczną i przechodnią.

*********************Elementy wyróżnione*********************

Definicja

Niech <X, R> jest zbiorem uporządkowanym

1. Element a჎ X nazywamy maksymalnym w zbiorze <X, R> wttw

ဢx჎X, (a R x პ x=a)

2. Element a჎ X nazywamy minimalnym w zbiorze <X, R> wttw

ဢx჎X, (x R a პ x=a)

Definicja

Niech <X, R> jest zbiorem uporządkowanym

1. Element a჎ X nazywamy największym w zbiorze <X, R> wttw

ဢx჎X, x R a

2. Element a჎ X nazywamy najmniejszym w zbiorze <X, R> wttw

ဢx჎X, a R x

Twierdzenie

W zbiorze uporządkowanym <X, R> istnieje co najwyżej jeden element największy (najmniejszy).

Element największy (najmniejszy) jest maksymalny (minimalny).

Definicja

Jeśli relacja R spełnia warunki porządku częściowego oraz jest relacją spójną, to R nazywamy relacją liniowo porządkującą .

Definicja

Niech dany jest zbiór uporządkowany <X, R>Podzbiór A჌X, nazywamy łańcuchem jeśli,

ဢx,y჎A, ( x R y ლ y R x )

**********************************************************************

Kresy

Niech A჌X, gdzie <X, R> zb. up. Element x₀ nazywamy ograniczeniem górnym (dolnym) zbioru A, jeśli

ဢ x჎A, x R x₀ ( x₀ R x )

Najmniejsze ograniczenie górne zbioru A (jeśli istnieje) nazywamy kresem górnym zbioru A (sup A).

Największe ograniczenie dolne zbioru A (jeśli istnieje) nazywamy kresem dolnym zbioru A (inf A).

Twierdzenie

W każdym niepustym skończonym zbiorze liniowouporządkowanym istnieje element największy (ostatni) i element najmniejszy (pierwszy)

PORZADEK: alt, altuk, barok, burak jest porządkiem leksykograficznym

---