PODSTAWOWE INFORMACJE O 

RELACJACH

• PRZYKŁAD 1
• Wnioskowania 
• Jan lubi Marię a wiec Maria lubi Jana
• nie uznamy za poprawne ponieważ relacja lubienia nie jest 

symetryczna – z tego, że X lubi Y nie wynika, że Y lubi X.

• PRZYKŁAD 2
• Wnioskowanie
• Jeśli  Jan  jest  potomkiem  Pawła,  a  Paweł  jest  potomkiem 

Stefana, to Jan jest potomkiem Stefana.

•   jest  poprawne  ponieważ  relacja  bycia  potomkiem  jest 

przechodnia.

•  PROBLEM
• Czy  wierzyciele  naszych  wierzycieli  są  naszymi 

wierzycielami?

• Odpowiedź 

na 

to 

pytanie 

sprowadza 

się 

do 

rozstrzygnięcia,  czy  relacja  bycia  wierzycielem  jest 
przechodnia

CO TO JEST RELACJA?

•

INTUICJA

•

Relacja  to  związek,  jaki  zachodzi  między 
obiektami.

•

Relacja  dwuargumentowa  to  związek,  który  jest 
opisywany przez predykat dwuargumentowy.

 

•

DEFINICJA

•

Relacja R określona na zbiorach A i B to zbiór par 
uporządkowanych <x,y>, takich że x  A, y  B.

•

Formalnie:

•

R  A x B

•

R = {<x,y> : x  A, y  B}

 

• PRZYKŁAD 4
• Niech dana będzie relacja bycia matką określona na 

zbiorze  ludzi.  Dziedziną  tej  relacji  jest  zbiór  kobiet 
posiadających  dzieci,  a  przeciwdziedziną  cały  zbiór 
ludzi (bo każdy człowiek ma matkę).

• Niech dana będzie relacja bycia wyższym. Dziedziną 

tej relacji są ludzie, którzy są od kogoś wyżsi (a więc 
wszyscy  ludzie  z  wyjątkiem  tych  najniższych).  A 
przeciwdziedziną ludzie, od których ktoś jest wyższy 
(a więc wszyscy z wyjątkiem tych najwyższych).

• DEFINICJA
• Niech  R    A  x  B.  Dziedzina  relacji  R  (symbolicznie: 

D(R))  to  zbiór  tych  elementów  zbioru  A,  które  z 
jakimś elementem zbioru B są w relacji R.

• D(R) = {x  A: y  B R(x,y)}

 

• DEFINICJA
• Niech  R    A  x  B.  Przeciwdziedzina  relacji  R 

(symbolicznie:  D’(R))  to  zbiór  tych  elementów 
zbioru B, z którym jakiś element zbioru B jestą w 
relacji R.

• D’(R) = {y  B: x  A R(x,y)}

• Dziedzina i przeciwdziedzina relacji tworzą w 

sumie jej pole: P(R) = D(R)  D’(R)

WŁASNOŚCI RELACJI

• ZWROTNOŚĆ
• Relacja 

R 

określona 

o 

dziedzinie 

i 

przeciwdziedzinie  w  zbiorze  A  jest  zwrotna 
zawsze i tylko wtedy, gdy 

• x  A R(x,x)
• tzn.  relacja  ta  zachodzi  między  dowolnym 

elementem zbioru A a nim samym.

• PRZYKŁAD 5
• Relacja  posiadania  tych  samych  rodziców 

(określona  na  zbiorze  ludzi)  jest  zwrotna,  bo 
każdy posiada tych samych rodziców co on sam.

 

• NIEZWROTNOŚĆ
• Relacja  R  określona  o  dziedzinie  i 

przeciwdziedzinie 

w 

zbiorze 

A 

jest 

niezwrotna zawsze i tylko wtedy, gdy  x  

A R(x,x)

• tzn.  relacja  ta  –  przynajmniej  dla  jednego 

elementu zbioru A nie zachodzi między tym 
elementem a nim samym.

• PRZYKŁAD 6
• Relacja  lubienia  określona  na  zbiorze  ludzi 

nie  jest  zwrotna,  bo  nie  każdy  sam  siebie 
lubi.

 

• PRZECIWZWROTNOŚĆ
• Relacja  R  określona  o  dziedzinie  i 

przeciwdziedzinie 

w 

zbiorze 

A 

jest 

przeciwzwrotna zawsze i tylko wtedy, gdy 

• x  A R(x,x)
• tzn.  relacja  ta  nie  zachodzi  między 

dowolnym  elementem  zbioru  A  a  nim 
samym.

• PRZYKŁAD 7
• Relacja  bycia  starszym  jest  przeciwzwrotna 

na  zbiorze  ludzi,  bo  żaden  człowiek  nie  jest 
starszy od samego siebie

 

• SYMETRYCZNOŚĆ
• Relacja  R  określona  o  dziedzinie  i 

przeciwdziedzinie 

w 

zbiorze 

A 

jest 

symetryczna zawsze i tylko wtedy, gdy x, 

y   A [R(x, y)  R(y,x)]

• tzn.  jeśli  relacja  ta  zachodzi  między 

dowolnymi elementami zbioru A w jednym 
kierunku, to zachodzi również w drugim.

• PRZYKŁAD 8
• Relacja  bycia  rówieśnikiem  jest  relacją 

symetryczną w zbiorze ludzi.

 

• NIESYMETRYCZNOŚĆ
• Relacja  R  określona  o  dziedzinie  i 

przeciwdziedzinie 

w 

zbiorze 

A 

jest 

niesymetryczna zawsze i tylko wtedy, gdy  

x, y   A [R(x, y)  R(x,y)]

• tzn.  relacja  ta  dla  przynajmniej  dwóch 

elementów  zbioru  A  nie  zachodzi  w  obie 
strony.

• PRZYKŁAD 9
• Relacja kochania jest relacją niesymetryczną 

w zbiorze ludzi.

 

 

• PRZECIWSYMETRYCZNOŚĆ
• Relacja 

R 

określona 

o 

dziedzinie 

i 

przeciwdziedzinie 

w 

zbiorze 

A 

jest 

przeciwsymetryczna zawsze i tylko wtedy, gdy 

•  x, y   A [R(x, y)  R(y,x)]
• tzn. jeśli relacja ta zachodzi między dowolnymi 

elementami zbioru A w jednym kierunku, to nie 
zachodzi w drugim.

• PRZYKŁAD 10
• Relacja 

bycia 

starszym 

jest 

relacją 

przeciwsymetryczną w zbiorze ludzi.

 

 

• ANTYSYMETRYCZNOŚĆ
• Relacja  R  określona  o  dziedzinie  i 

przeciwdziedzinie 

w 

zbiorze 

A 

jest 

antysymetryczna zawsze i tylko wtedy, gdy 

•  x, y   A [(R(x, y)  R(x,y))  x = y]
• tzn.  jeśli  relacja  ta  zachodzi  między 

dowolnymi elementami zbioru A w jednym i 
drugim  kierunku,  to  oznacza,  że  jest  to  ten 
sam element. 

• PRZYKŁAD 11
• Relacja  bycia  podzbiorem  jest  relacją 

antysymetryczną  na  zbiorach  tzn.  jeśli  A   

B i B  A, to A = B.

 

• PRZECHODNIOŚĆ
• Relacja 

R 

określona 

o 

dziedzinie 

i 

przeciwdziedzinie w zbiorze A jest przechodnia 
zawsze i tylko wtedy, gdy   x, y, z   A [[R(x, 

y)  R(y,z)]  R(x,z)]

• tzn. jeśli relacja ta zachodzi między dowolnymi 

trzema  elementami  zbioru  A  tak,  że    zachodzi 
między pierwszym i drugim i drugim i trzecim, 
to  zachodzi  również  w  między  pierwszym  i 
trzecim

• PRZYKŁAD 12
• Relacja  bycia  rówieśnikiem  jest  relacją 

przechodnią w zbiorze ludzi 

 

• NIEPRZECHODNIOŚĆ
• Relacja 

R 

określona 

o 

dziedzinie 

i 

przeciwdziedzinie 

w 

zbiorze 

A 

jest 

nieprzechodnia zawsze i tylko wtedy, gdy 

•  x, y, z   A [R(x, y)  R(y,z)  R(x,z)]
• tzn.  relacja  ta  zachodzi  pewnymi  trzema 

elementami  zbioru  A  tak,  że    zachodzi  między 
pierwszym  i  drugim  i  drugim  i  trzecim,  a  nie 
zachodzi między pierwszym i trzecim.

• PRZYKŁAD 13
• Relacja 

bycia 

przyjacielem 

jest 

relacją 

nieprzechodnią w zbiorze ludzi.

 

 

• PRZECIWPRZECHODNIOŚĆ
• Relacja 

R 

określona 

o 

dziedzinie 

i 

przeciwdziedzinie 

w 

zbiorze 

A 

jest 

przeciwprzechodnia zawsze i tylko wtedy, gdy 

•  x, y, z   A [[R(x, y)  R(y,z)]  R(x,z)]
• tzn.  jeśli  dla  dowolnych  trzech  elementów 

zbioru  A  relacja  ta  zachodzi  między 
pierwszym i drugim, i  drugim i trzecim, to nie 
zachodzi między pierwszym i trzecim.

• PRZYKŁAD 14
• Relacja  bycia  o  rok  starszym  jest  relacją 

nieprzechodnią w zbiorze ludzi 

WAŻNE KOMBINACJE WŁASNOŚCI

• Relacje,  które  są  zarazem  zwrotne,  symetryczne  i 

przechodnie 

są 

nazywane 

relacjami 

RÓWNOWAŻNOŚCI.

• PRZYKŁAD 15
• Relacja posiadania tego samego koloru włosów jest na 

zbiorze  ludzi  relacją  równoważności.  Wyznacza  ona 
klasy  ludzi  posiadających  ten  sam  kolor  oczu.  Każdy 
człowiek należy do dokładnie jednej takiej klasy. 

• Relacje,  które  są  niesymetryczne  i  przechodnie  – 

relacjami PORZĄDKUJACYMI.

• PRZYKŁAD 16
• Relacja  bycia  starszym  jest  na  zbiorze  ludzi  relacją 

porządkującą. Wyznacza kolejność ludzi według wieku.