Relacje binarne

Definicja
Niech X i Y będą dowolnymi zbiorami. Dowolny 
podzbiór R zbioru X  Y nazywamy relacją binarną 

(dwuargumentową, dwuczłonową) na zbiorze X  Y. 
UWAGA:  Ponieważ R XY, R jest zatem zbiorem par

                  uporządkowanych. Jeśli xX, yY oraz <x,y>R

                  to mówimy, że x jest w relacji (R) z y. Inny zapis to x R y. 

Relacją n-członową nazywamy relację, której 
wszystkie elementy są n-kami uporządkowanymi 
RX

1

X

2

..X

n

 

Definicja
Mając dowolną relację R XY, zbiór D(R)={x : yY <x,y>R}

nazywamy dziedziną relacji R, zbiór V(R)={y : xX <x,y>R}

przeciwdziedziną relacji R, a zbiór D(R)V(R) polem relacji R.  

 

 

Relacje binarne – 

przykłady

Przykład  Relacja < w zbiorze liczb rzeczywistych jest to 
podzbiór produktu 

   R  R, do którego należą wszystkie pary <x,y> takie, że 

x,yR i x<y. 

Przykład  Niech P(X) będzie niepustą rodziną zbiorów. Relacja 
inkluzji jest   

   własnością par uporządkowanych <A,B> 

takich, że

   A B oraz A, B P(X). Jest to relacja binarna w P(X)  

P(X).

UWAGA: Elementy należące do relacji posiadają 
zatem jakieś 

      szczególne własności 

(takie, jakie definiuje relacja).

Inne przykłady: 

Podzielność liczb w zbiorze liczb naturalnych

     Równoległość prostych na płaszczyźnie
     Stosunki pokrewieństwa pomiędzy ludźmi („być ojcem”)

 

 

Relacje binarne – 

reprezentacje

UWAGA: Każdą relację binarną określoną w zbiorze skończonym

      można przedstawić w postaci macierzowej lub diagramu

Niech X= {1,2,3,4} i Y = {5,7,8} oraz R 
XY

R={<1,5>, <3,7>, <2,8>, <4,5>, 
<1,7> }

  5  7  8 

1  +  +   
2      + 
3    +   
4  +     

 

5

7

1

2

3

4

8

5

7

1

2

3

4

8

 

 

Specjalne rodzaje 

relacji binarnych

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
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
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).

Przykład: L zbiór ludzi RLL 

R={<x,y> : x dzieckiem y}

 

R

-1

={<x,y> : x jest rodzicem y} 

 

 

Relacja równoważności

Definicja
Relację RXX nazywamy relacją równoważności 

wttw R jest relacją zwrotną, symetryczną i 
przechodnią.

Przykłady

1. L – zbiór wszystkich prostych na płaszczyźnie, RLL   l, hL    l R h  l || h  

2. L – zbiór chorych RLL  l, hL    

l R h  l jest chory na tę samą chorobę co h

3. L – zbiór samochodów RLL  l, hL

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

Skoda

Mazda

Toyota

Fiat

 

 

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.

Stwierdzenie
Jeżeli R jest relacją równoważności w zbiorze X, to 

dla dowolnych x,y



X, prawdziwe są następujące 

warunki: 
x 



[x]

[x] = [y]    wttw    x R y
Jeżeli [x]  [y] , to [x]  [y] = 

UWAGA:  Zbiór wszystkich klas abstrakcji relacji R w X oznacza się

       X\R i nazywa się zbiorem ilorazowym

 

 

Zasady abstrakcji

Definicja
Rodzinę P podzbiorów zbioru X nazywamy podziałem 

zbioru 

X wttw
i) F  dla każdego FP

ii) P=X

iii) i,j  F

i

F

j

   F

1

  F

2

 = 

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).
Zachodzi również twierdzenie odwrotne
Każdy podział H={ H

i 

: iI } zbioru X wyznacza relację 

równoważności R

H

 w zbiorze X, w myśl wzoru

        x, y  X    x R

H 

y  iI  ( xH

i 

 yH

i

 ) 

 

Skoda

Mazda

Toyota

Fiat

 

 

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:
i) xX  yY   x R y 

ii) xX  y

1

,y

2

 Y  ( x R y

1

  x R y

2

 )  y

1

=y

2

 

UWAGA: To jedyne y, które pozostaje w relacji z x oznaczamy 

      R(x). Zazwyczaj funkcje oznaczamy jako f, g, h itd.

Funkcja różnowartościowa (injekcja)

x,yX  [ f(x)=f(y) ]  x=y      

Funkcja „na” (surjekcja)

yY xX ( y=f(x) )

     

Odwzorowanie wzajemnie jednoznaczne (bijekcja)

injekcja + surjekcja

 

 

Przykłady funkcji

Y

X

„na”

różnowartościowa

 

Y 

X 

Y

X

odwzorowanie
wzajemnie jednoznaczne

 

 

Y

X

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) } 

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 } 

z

 

 

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ą.

Przykłady

1. R – rodzina zbiorów  <R, >  

2. Zbiór N jest uporządkowany przez relację podzielności 
              n | m  n jest dzielnikiem m

3. Każdy niepusty podzbiór zbioru R uporządkowany jest przez relację  

Zbiór  X wraz z porządkiem R nazywamy zbiorem 
uporządkowanym. Ozn.   <X, R>. 

 

 

Reprezentacja graficzna

b

a

b

a

c

b

d

c

a

a

c

b

d

f

e

Diagramy Hassego

1. a R b – a znajduje się poniżej b  
2. a

i

 R a

j  

- od a

i 

do a

j

 prowadzi łamana skierowana w górę  

UWAGA:  Skończoność zbioru X gwarantuje istnienie 
Diagramu Hassego dla <X, R>.

 

 

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 

 

 

Elementy wyróżnione 

cd.

Twierdzenie
W zbiorze uporządkowanym <X, R> istnieje co najwyżej 
jeden element największy (najmniejszy). 
Element największy (najmniejszy) jest maksymalny (minimalny)
Dowód: ćwiczenia

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 )

Czyli łańcuch

jest liniowo 

uporządkowany

 

 

Kresy

Definicja
Niech AX, gdzie <X, R> zb. up. Element x

0

 nazywamy ograniczeniem

górnym (dolnym) zbioru A, jeśli

 xA,   x R x

0 

  ( x

0

 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 liniowo
uporządkowanym istnieje element największy (ostatni)
i element najmniejszy (pierwszy)

 

 

Porządek leksykograficzny

Definicja
Niech <X

1

,R

1

>,.,<X

n

,R

n

> są zbiorami częściowo uporządkowanymi.

Relację R

*

 określoną w produkcie X

1

X

2

..X

n

:

 
<x

1

,x

2,

..,x

n

> R

* 

<y

1

,y

2

,..,y

n

>  wttw albo dla wszystkich in x

i

=y

i

albo istnieje takie k (0<kn), że dla 0<i<k, x

i

=y

i

 oraz x

k

R

k

y

k

, x

k

y

k

nazywamy porządkiem leksykograficznym w X

1

X

2

..X

n

.

Przykład

Mamy ={a,b,..,z}, na którym określamy zwykły porządek liniowy liter w alfabecie.

Wówczas R

*

 określona w 

m

, mN jest zwykłym porządkiem alfabetycznym w 

m

.

 
kos R

*

 kot R

*

 ros

 

 

Porządek słownikowy

Definicja
Niech  będzie ustalonym alfabetem uporządkowanym liniowo 

przez relację R. W zbiorze 

*

 (wszystkich słów nad alfabetem ),

definiujemy relację porządku słownikowego R

L

:

 

<x

1

,..,x

n

> R

L

 <y

1

,..,y

m

> wttw albo nm i dla wszystkich i (1<in) x

i

=y

i 

albo istnieje takie k (1<kmin(n,m)), że dla każdego i (0<i<k) x

i

=y

i

 

       oraz x

k

Ry

k

, dla x

k

y

k

Przykład

kos R

L

 kosa R

L

 ros R

L

 rosomak

Alfabet identyczny jak w poprzednim przypadku, nie zakładamy długości słów