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.