Iloczyn kartezjański i relacje binarne

Wstęp

2

1. Para uporządkowana i iloczyn kartezjański zbiorów

3

2. Relacje binarne

7

3. Rodzaje relacji binarnych

14

Bibliografia

18

2

Wstęp

Moduł czwarty przedstawi podstawowe pojęcia teorii mnogości potrzebne między
innymi do opisu i modelowania systemów informatycznych.

Temat pierwszy dotyczy pojęcia pary uporządkowanej oraz definicji iloczynu kar-
tezjańskiego zbiorów. Zostaną omówione i — w większości — udowodnione pod-
stawowe własności iloczynu kartezjańskiego.

Temat drugi zaprezentuje pojęcie relacji binarnej, reprezentacji graficznej relacji
i działań na relacjach wraz z ich podstawowymi własnościami.

W temacie trzecim zawarte są definicje własności relacji binarnych, przykłady oraz
zależności między nimi.

3

1. Para uporządkowana

i iloczyn kartezjański zbiorów

Para uporządkowana

i

iloczyn kartezjański

zbiorów

są podstawowymi pojęciami nauki

o zbiorach, na których opiera się pojęcie relacji.

Para uporządkowana (a, b) to dowolny, złożony z dwóch elementów obiekt, speł-
niający poniższe założenia:



jeśli a ≠ b , to (a, b) ≠ (b, a).



jeśli (a, b) = (c, d), to a = c oraz b = d.

Jeżeli (a, b) jest parą uporządkowaną, to element a nazywamy

poprzednikiem pary

,

zaś element b

następnikiem pary

.

Jedną z popularniejszych definicji pary uporządkowanej podał w 1920 roku polski
matematyk Kazimierz Kuratowski: (a, b) =

df.

{{a}, {a, b}}. Łatwo można udowod-

nić, że tak zdefiniowana —

za pomocą pojęcia zbioru — para uporządkowana speł-

nia podane wyżej wymagania.

Pojęcie pary uporządkowanej służy do zdefiniowania pojęcia iloczynu kartezjań-
skiego zbiorów. Niech A oraz B będą dowolnymi zbiorami. Iloczynem kartezjań-
skim zbiorów A i B nazywamy zbiór wszystkich takich par uporządkowanych
(a, b), że a ∈ A oraz b ∈ B. Iloczyn kartezjański zbiorów A oraz B oznaczamy sym-
bolem A × B.

Rozważmy zbiory A = {1, 2, 3} oraz B = {a, b}. Iloczynem kartezjańskim tych
zbiorów jest, zgodnie z definicją, zbiór wszystkich par uporządkowanych (a, b) ta-
kich, że a ∈ A oraz b ∈ B. Mamy zatem A × B = {(1, a), (2, a), (3, a), (1, b),
(2, b), (3, b)}.

Jeżeli zbiór A ma n elementów, a zbiór B ma k elementów, to iloczyn kartezjański
A × B ma n ⋅ k elementów.

Przykład 1

Znanym przykładem iloczynu kartezjańskiego jest płaszczyzna, rozumiana jako
zbiór punktów o współrzędnych rzeczywistych.

Twierdzenie 1

Zachodzą następujące własności dla iloczynu kartezjańskiego:

(a)

(A × B ≠ B × A) ⇔ (A ≠ B ∧ A ≠ ∅ ∧ B ≠ ∅),

(b)

(A × B = B × A) ⇔ (A = B ∨ A = ∅ ∨ B = ∅),

(c)

A × (B ∪ C) = (A × B) ∪ (A × C) (iloczyn kartezjański jest rozdzielny względem
sumy zbiorów),

(d)

A × (B ∩ C) = (A × B) ∩ (A × C) (iloczyn kartezjański jest rozdzielny względem
iloczynu zbiorów),

(e)

A × (B – C) = (A × B) – (A × C) (iloczyn kartezjański jest rozdzielny względem
różnicy zbiorów),

4

(f)

A × B ≠ ∅ ⇔ (A ≠ ∅ ∧ B ≠ ∅)

(g)

A × B = ∅ ⇔ (A = ∅ ∨ B = ∅),

(h)

A × ∅ = ∅,

(i)

∅ × A = ∅,

(j)

∅ × ∅ = ∅.

Dowód (c)

Aby udowodnić powyższą równość, musimy — zgodnie z definicją równości zbio-
rów — wykazać prawdziwość następującego warunku:

∀

x

(x ∈ A × (B ∪ C) ⇔ x ∈ (A × B) ∪ (A × C))

Niech x będzie dowolne. Rozpatrzmy dwa przypadki: albo x nie jest parą uporządko-
waną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność jest
oczywista (obie strony fałszywe, obiekt niebędący parą uporządkowaną nie może
należeć do iloczynu kartezjańskiego).

Jeśli zaś x = (a, b), to:

L : x ∈ A × (B ∪ C) ⇔

1

(a, b) ∈ A × (B ∪ C) ⇔

2

a ∈ A ∧ b ∈ (B ∪ C) ⇔

3

⇔ a ∈ A ∧ (b ∈ B ∨ b ∈

C) ⇔

4

(a ∈ A ∧ b ∈ B) ∨ (a ∈ A ∧ b ∈

C) ⇔

⇔ (a, b) ∈ (A × B) ∨ (a, b) ∈ (A × C) ⇔

⇔ x ∈ (A × B) ∨ x ∈ (A × C) ⇔ x ∈ (A × B) ∪ (A × C) : P

Dowód (e)

Mamy wykazać, że ∀

x

(x ∈ A × (B – C) ⇔ x ∈ (A × B) – (A × C)).

Niech x będzie dowolne. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowaną, albo x jest parą uporządkowaną.

W pierwszym przypadku równoważność jest oczywista.

W drugim przypadku, jeśli x = (a, b), to:

L : x ∈ A × (B – C) ⇔

5

(a, b) ∈ A × (B – C) ⇔

6

a ∈ A ∧ b ∈ (B – C) ⇔

7

⇔ a ∈ A ∧ (b ∈ B ∧ b ∉ C) (*)

P : x ∈ (A × B) – (A × C) ⇔ x ∈ (A × B) ∧ x ∉ (A × C) ⇔

⇔ (a, b) ∈ (A × B) ∧ (a, b) ∉ (A × C) ⇔ (a, b) ∈ (A × B) ∧ ¬[ (a, b) ∈ (A × C) ] ⇔

⇔ (a ∈ A ∧ b ∈ B) ∧ ¬(a ∈ A ∧ b ∈ C) ⇔ (a ∈ A ∧ b ∈ B) ∧ (¬(a ∈ A) ∨ ¬(b ∈ C)) ⇔

⇔ (a ∈ A ∧ b ∈ B ∧ ¬(a∈ A)) ∨ (a ∈ A ∧ b ∈ B ∧ ¬(b ∈ C)) ⇔

8

⇔ a ∈ A ∧ (b ∈ B ∧ b ∉ C) (*)

1

Ponieważ założyliśmy, że x = (a, b).

2

Z definicji iloczynu kartezjańskiego.

3

Definicja sumy zbiorów.

4

Prawo rozdzielności koniunkcji względem alternatywy.

5

Ponieważ założyliśmy, że x = (a, b).

6

Z definicji iloczynu kartezjańskiego.

7

Definicja różnicy zbiorów.

8

Lewy składnik alternatywy jest fałszywy, zatem alternatywa ta jest równoważna pozosta-

łemu składnikowi.

5

W rezultacie rozpisanie obu stron równoważności dało ten sam wynik (*), zatem
L ⇔ P, czyli:

x ∈ A × (B – C) ⇔ x ∈ (A × B) – (A × C).

Dowód (h)

Mamy wykazać, że ∀

x

(x ∈ A × ∅ ⇔ x ∈ ∅).

Niech x będzie dowolne. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowaną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność
jest oczywista.

W drugim przypadku, gdy x = (a, b), mamy:

L : x ∈ A × ∅ ⇔ (a, b) ∈ A × ∅ ⇔ a ∈ A ∧ b ∈ ∅ ⇔

9

x ∈ ∅ : P

Twierdzenie 2

W ogólnym przypadku nie zachodzą następujące własności iloczynu kartezjańskiego:
(a)

A ∪ (B × C) = (A ∪ B) × (A ∪ C),

(b)

A ∩ (B × C) = (A ∩ B) × (A ∩ C),

(c)

A – (B × C) = (A – B) × (A – C).

Dowód (a)

Pokażemy, że dla zbiorów A = B = C = R nie zachodzi równość z podpunktu (a).

Mamy:

L = R ∪ (R × R).

Zbiór ten to suma zbioru liczb rzeczywistych oraz zbioru par uporządkowanych,
których elementami są liczby rzeczywiste.

Mamy na przykład 1 ∈ R, co natychmiast daje 1 ∈ R ∪ (R × R).

Rozważmy stronę prawą równości. Mamy:

P = (R ∪ R) × (R ∪ R) = R × R.

Oczywiście, do tego zbioru należą tylko odpowiednie pary uporządkowane, a za-
tem 1 ∉ R × R.

Pokazaliśmy istnienie elementu, który należy do lewej strony równości, a nie nale-
ży do prawej, zatem zbiory powyższe nie są równe.

Dowód (b)

Pokażemy, że dla zbiorów A = B = C = R nie zachodzi równość z podpunktu (b).
Mamy:

P = (R ∩ R) × (R ∩ R) = R × R.

Oczywiście R × R ≠ ∅.

9

Ta równoważność jest prawdziwa, gdyż ma obie strony fałszywe (nic nie może należeć do

zbioru pustego).

6

L = R ∩ (R × R)

Zbiór ten to iloczyn dwóch rozłącznych zbiorów (R to zbiór liczb rzeczywistych,
a R × R to zbiór par uporządkowanych), zatem jest on równy zbiorowi pustemu.

Mamy:

P ≠ ∅ oraz L = ∅.

Oczywiście L ≠ P.

7

2. Relacje binarne

Na co dzień często dokonujemy porównań między pewnymi rzeczami, osobami,
zjawiskami (elementami danego zbioru lub danych zbiorów). Mówimy, że czło-
wiek A jest wyższy od człowieka B, produkt C jest tańszy od produktu D, liczba x
jest mniejsza od liczby y. Zauważamy więc (abstrahujemy z rzeczywistości) pewne
związki (zależności) między pewnymi obiektami. Zależności takie matematyka na-
zywa relacjami.

Relacje są również jednym z podstawowych narzędzi stosowanych w informatyce
między innymi do opisu (modelowania, charakteryzowania, specyfikacji) własno-
ści szeroko pojętych różnych systemów informatycznych, a przez to również syste-
mów oprogramowania.

Przykład 2

Rozważmy zależność między żołnierzami w jednostce wojskowej, nazy-
waną relacją „bycia podwładnym”.

Niech P = {K,

C,

S,

A, B,

D} będzie patrolem wojskowym, gdzie:

K — kapitan,

C — chorąży,
S — sierżant,

A,

B,

D — szeregowi.

Oczywiste, że A jest podwładnym S, S jest podwładnym C i tak dalej. Za-
uważmy, że jeżeli zastanowimy się nad reprezentacją graficzną zależności
między elementami zbioru P, łatwo można narysować następujący dia-
gram (rysunek 1).

Nietrudno zauważyć, że każdą z elementarnych relacji między żołnierza-
mi patrolu P można reprezentować (specyfikować) przez odpowiednią parę upo-
rządkowaną. Mamy zatem pary: (A, S),

(A, C),

(A, K),

(B, S),

(B, C),

(B, K),

(D, S),

(D, C),

(D, K),

(S, C),

(S, K),

(C, K).

Możemy więc powiedzieć, że relację „bycia podwładnym” określa pewien zbiór par
uporządkowanych. Zauważmy również, że ten zbiór jest podzbiorem iloczynu kar-
tezjańskiego P

× P, przy czym jest to tylko jego podzbiór właściwy (różny od całe-

go iloczynu P × P).

Jak widać, relacje dwuargumentowe, czyli zachodzące między dwoma elementami,
można definiować jako pewne zbiory par uporządkowanych.

Relacją

określoną na iloczynie kartezjańskim A × B nazwiemy zatem dowolny pod-

zbiór tego iloczynu kartezjańskiego.

Relacją binarną

określoną na zbiorze A nazywamy dowolny podzbiór iloczynu kar-

tezjańskiego A × A.

Jeżeli przyjmujemy taką definicję, to łatwo zauważyć, że elementami niepustych re-
lacji binarnych są pary uporządkowane.

K

C

S

B

A D

K

C

S

B

A D

K

C

S

B

A D

K

C

S

B

A D

Rysunek 1

K

C

S

B

A D

K

C

S

B

A D

K

C

S

B

A D

K

C

S

B

A D

8

Relacje binarne określone na zbiorze A oznaczać będziemy symbolem

δ (δ ⊆ A × A). Fakt należenia pary uporządkowanej (a, b) do relacji δ
będziemy oznaczać przez (a, b) ∈ δ. Zamiennie będziemy też używali
zapisu „a δ b” (element a jest w relacji δ z elementem b).

Nietrudno zauważyć, że skończone relacje binarne można łatwo inter-
pretować graficznie jako zbiór (graf) odpowiednich przejść (tranzycji)
między elementami odpowiedniego zbioru.

Przykład 3

Rozważmy zbiór A = {a, b, c, d} i określoną na nim relację:

δ = {(a, a), (b, b), (a, b), (b, a), (c, d), (a, d), (d, a), (b, d)}.

Reprezentacja graficzna tej relacji jest przedstawiona na rysunku 2.

Oczywiste jest, że odpowiedni zbiór par uporządkowanych (relacja) deter-
minuje dokładnie jeden graf. Zachodzi również własność odwrotna: każdy
graf determinuje dokładnie jedną relację (odpowiedni zbiór par uporząd-
kowanych).

Relacje skończone reprezentować można również za pomocą macierzy,
wpisując w polach o odpowiednich współrzędnych jedynkę (jeżeli relacja
zachodzi między danymi współrzędnymi macierzy) lub zero (gdy relacja
nie zachodzi).

Relację z poprzedniego przykładu reprezentować można jako następującą
macierz (rysunek 3).

Oczywiste jest również w tym przypadku, że odpowiedni zbiór par uporząd-
kowanych (relacja) determinuje dokładnie jedną macierz (z dokładnością do
kolejności ustawienia elementów-współrzędnych) oraz każda macierz deter-
minuje dokładnie jedną relację (odpowiedni zbiór par uporządkowanych).

Przykład 4

Rozważmy macierz przedstawioną na rysunku 4.

Reprezentuje ona oczywiście relację:

δ = {(a, c), (a, d), (b, a), (b, b), (b, d), (c, a), (c, c), (c, d)}.

Niech δ ⊆ X

× Y będzie relacją dwuargumentową na zbiorach X, Y.

Dziedziną relacji

δ, oznaczaną przez D(δ), nazywamy zbiór wszystkich poprzedni-

ków par należących do relacji δ.

D(δ) = {x ∈

X : ∃

y∈Y

(x, y) ∈ δ}

10

.

Przeciwdziedziną relacji

δ, oznaczaną przez D*(δ), nazywamy zbiór wszystkich na-

stępników par należących do relacji δ.

D*(δ) = {y ∈ Y : ∃

x∈X

(x, y) ∈ δ}

11

.

10

W innej formie D(δ) = {x ∈ X : ∃

y

∈

Y

x δ y}.

11

Inaczej D*(δ) = {y ∈ Y : ∃

x∈X

x δ y}.

a b

c d

0

0

0

1

1

0

0

0

1

0

1

1

1

0

1

1

d

c

b

a

d

c

b

a

0

0

0

0

1

1

0

1

1

0

1

1

1

1

0

0

d

c

b

a

d

c

b

a

Rysunek 2

Rysunek 3

Rysunek 4

9

Niżej zdefiniujemy podstawowe operacje na relacjach binarnych: sumę, iloczyn,
konwers i złożenie (superpozycję relacji).

Niech A oraz B będą dowolnymi zbiorami. Niech δ

1

będzie dowolną relacją okre-

śloną na zbiorze A (δ

1

⊆ A × A), zaś δ

2

będzie dowolną relacją określoną na zbiorze

B (δ

2

⊆ B × B).

Zauważmy, że A ⊆ A ∪ B oraz B ⊆ A ∪ B.

Możemy zatem stwierdzić, że zarówno δ

1

⊆ (A ∪ B) × (A ∪ B), jak i δ

2

⊆ (A ∪ B)

× (A ∪ B). Możemy teraz dla danych relacji δ

1

oraz δ

2

zdefiniować

sumę

oraz

iloczyn

tych relacji.

Relację (δ

1

∪ δ

2

) określoną na zbiorze A ∪ B ((δ

1

∪ δ

2

)

⊆ (A ∪ B)

× (A ∪ B)) speł-

niającą zależność:

a (δ

1

∪ δ

2

) b ⇔ a δ

1

b ∨ a δ

2

b,

nazywamy

sumą relacji

δ

1

oraz δ

2

.

Inaczej możemy zapisać:

(δ

1

∪ δ

2

) =

df.

{(a, b) ∈ (A ∪ B) × (A ∪ B) : (a, b) ∈ δ

1

∨ (a, b) ∈ δ

2

}.

Relację (δ

1

∩ δ

2

) określoną na zbiorze A ∪ B ((δ

1

∩ δ

2

)

⊆ (A ∪ B) × (A ∪ B)), speł-

niającą zależność:

a (δ

1

∩ δ

2

) b ⇔ a δ

1

b ∧ a δ

2

b,

nazywamy

iloczynem relacji

δ

1

oraz δ

2

.

Inaczej możemy zapisać:

(δ

1

∩ δ

2

) =

df.

{(a, b) ∈ (A ∪ B) × (A ∪ B) : (a, b) ∈ δ

1

∧ (a, b) ∈ δ

2

}.

Zauważmy, że jeżeli zbiór A ∩ B jest pusty, to i relacja (δ

1

∩ δ

2

) jest zbiorem

pustym.

Przykład 5

Relację „≤”, określoną na zbiorze liczb naturalnych, możemy traktować jako sumę
relacji „<” oraz relacji „=” określonych odpowiednio na zbiorze liczb naturalnych
(bo x ≤ y ⇔ x < y ∨ x = y).

Relację „=”, określoną na zbiorze liczb naturalnych, możemy traktować jako ilo-
czyn relacji „≤” oraz relacji „≥” określonych odpowiednio na zbiorze liczb natural-
nych (bo x = y ⇔ x ≤ y ∧ x ≥ y).

Zachodzą następujące własności dotyczące dziedziny i przeciwdziedziny sumy
i iloczynu relacji.

Twierdzenie 3

Dla dowolnych relacji δ

1

, δ

2

⊆ A × B:

(a)

D (δ

1

∪ δ

2

) = D(δ

1

) ∪ D(δ

2

),

(b)

D*(δ

1

∪ δ

2

) = D*(δ

1

) ∪ D*(δ

2

),

(c)

D(δ

1

∩ δ

2

) ⊆ D(δ

1

) ∩ D(δ

2

),

(d)

D*(δ

1

∩ δ

2

) ⊆ D*(δ

1

) ∩ D*(δ

2

).

10

Szkic dowodu (a)

x ∈ D(δ

1

∪ δ

2

) ⇔ ∃

y∈B

(x, y) ∈ (δ

1

∪

δ

2

) ⇔ ∃

y∈B

(x δ

1

y ∨ x δ

2

y) ⇔

⇔ ∃

y∈B

x δ

1

y ∨ ∃

y∈B

x δ

2

y ⇔ x ∈ D(δ

1

) ∨ x ∈ D(δ

2

) ⇔

⇔ x ∈ D(δ

1

) ∪ D(δ

2

).

Stąd:

x ∈ D(δ

1

∪ δ

2

) ⇔ x ∈ D(δ

1

) ∪ D(δ

2

).

Szkic dowodu (c)

x

∈ D(δ

1

∩ δ

2

) ⇔ ∃

y∈B

(x, y) ∈ (δ

1

∩

δ

2

) ⇔ ∃

y∈B

(x δ

1

y ∧ x δ

2

y) ⇒

12

⇒ ∃

y∈B

x δ

1

y ∧ ∃

y∈B

x δ

2

y ⇔ x ∈ D(δ

1

) ∧ x ∈ D(δ

2

) ⇔

⇔ x ∈ D(δ

1

) ∩ D(δ

2

).

Stąd:

x

∈ D(δ

1

∩ δ

2

) ⇒ x

∈ D(δ

1

) ∩ D(δ

2

).

Rozważmy relację δ określoną na zbiorze A(δ

⊆ A × A).

Relację δ

–1

określoną na zbiorze A, spełniającą zależność:

a δ

–1

b ⇔ b δ a

13

nazywamy

konwersem (odwrotnością) relacji

δ.

Inaczej możemy zapisać:

δ

–1

=

df.

{(a, b) ∈ A × A : (b, a) ∈ δ}.

Interpretację graficzną konwersu relacji przedstawia rysunek 5.

Przykład 6

Relacją odwrotną do relacji „< ”, określonej na zbiorze liczb naturalnych, jest relacja
„>” (określona na tym samym zbiorze), zachodzi bowiem zależność y < x ⇔ x > y
(możemy też zapisać („<”)

–1

= „>”).

Relacją odwrotną do relacji „być żoną”, określonej na zbiorze ludzi, jest relacja „być
mężem”, określona na tym samym zbiorze, zachodzi bowiem zależność: „x jest
żoną y” ⇔ „y jest mężem x”.

Twierdzenie 4

Dla dowolnych relacji δ, δ

1

, δ

2

⊆ A × B jest:

(a)

(a, b) ∉ δ

–1

⇔ (b, a) ∉ δ,

(b)

D(δ

–1

) = D*(δ) (dziedzina konwersu jest równa przeciwdziedzinie danej relacji),

(c)

D*(δ

–1

) = D(δ) (przeciwdziedzina konwersu jest równa dziedzinie danej relacji),

(d)

(δ

–1

)

–1

= δ (konwers konwersu jest równy danej relacji),

(e)

(δ ’)

–1

= (δ

–1

)‘ (dopełnienie konwersu równe jest konwersowi dopełnienia),

12

Korzystamy z odpowiedniego prawa rozkładu kwantyfikatora szczegółowego względem

koniunkcji: ∃

x

[

Φ(x) ∧ Ψ(x)] ⇒ ∃

x

Φ(x) ∧ ∃

x

Ψ(x).

13

Inaczej: (a, b)

∈ δ

–1

⇔

(

b

, a)

∈

δ

.

Rysunek 5

d -1

d

a b

δ

δ

–1

11

(f)

(δ

1

∪ δ

2

)

–1

= δ

1

–1

∪ δ

2

–1

(konwers sumy relacji równy jest sumie konwersów),

(g)

(δ

1

∩ δ

2

)

–1

= δ

1

–1

∩ δ

2

–1

(konwers iloczynu relacji równy jest iloczynowi kon-

wersów).

Dowód (d)

Trzeba wykazać, że ∀

x

(x

∈ (δ

–1

)

–1

⇔ x

∈ δ).

Niech x będzie dowolny. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowaną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność
jest oczywista.

W drugim przypadku, jeśli x = (a, b), to:

L : x

∈ (δ

–1

)

–1

⇔ (a, b) ∈ (δ

–1

)

–1

⇔ (b, a) ∈ (δ

–1

) ⇔ (a, b) ∈ δ ⇔ x ∈ δ : P

Szkic dowodu (e)

L

:

x

∈ (δ’)

–1

⇔ (a, b) ∈ (δ’)

–1

⇔ (b, a) ∈ δ’ ⇔ (b, a) ∉ δ ⇔

⇔ (a, b) ∉ δ

–1

⇔ (a, b) ∈ (δ

–1

)’ ⇔ x ∈ (δ

–1

)’ : P

Szkic dowodu (f)

L :

x

∈ (δ

1

∪ δ

2

)

–1

⇔ (a, b) ∈ (δ

1

∪ δ

2

)

–1

⇔ (b, a) ∈ (δ

1

∪ δ

2

)

⇔

⇔ (b, a) ∈ δ

1

∨ (b, a) ∈ δ

2

⇔ (a, b) ∈ δ

1

–1

∨ (a, b) ∈ δ

2

–1

⇔

⇔ (a, b) ∈ δ

1

–1

∪ δ

2

–1

⇔ x ∈ δ

1

–1

∪ δ

2

–1

: P

Szkic dowodu (g)

L : x ∈ (δ

1

∩ δ

2

)

–1

⇔ (a, b) ∈ (δ

1

∩ δ

2

)

–1

⇔ (b, a) ∈ (δ

1

∩ δ

2

)

⇔

⇔ (b, a) ∈ δ

1

∧ (b, a) ∈ δ

2

⇔ (a, b) ∈ δ

1

–1

∧ (a, b) ∈ δ

2

–1

⇔

⇔ (a, b) ∈ δ

1

–1

∩ δ

2

–1

⇔ x ∈ δ

1

–1

∩ δ

2

–1

: P

Niech δ

1

⊆ A

× B oraz δ

2

⊆ B

× C.

Złożeniem relacji (superpozycją)

δ

1

oraz δ

2

nazywamy relację (δ

2

ο δ

1

) ⊆ A

× C taką, że:

a (δ

2

ο δ

1

) c ⇔ ∃

b∈B

(a δ

1

b ∧ b δ

2

c)

14

.

Symbolicznie:

δ

2

ο δ

1

= {(a, c) ∈ A × C : ∃

b∈B

[(a, b) ∈ δ

1

∧ (b, c) ∈ δ

2

]}.

Interpretację graficzną superpozycji relacji przedstawia rysunek 6.

Zachodzą poniższe własności operacji złożenia relacji.

14

Zwróćmy uwagę na „odwrotną notację”. Jeżeli a δ

1

b ∧ b δ

2

c, to powiemy, że a jest w re-

lacji (δ

2

ο

δ

1

) z elementem c.

12

Twierdzenie 5

Dla dowolnych relacji δ

1

, δ

2

, δ

3

⊆ A × A spełnione są warunki:

(a)

(δ

2

ο δ

1

)

–1

= δ

1

–1

ο δ

2

–1

,

(b)

δ

3

ο (δ

2

ο δ

1

) = (δ

3

ο δ

2

) ο δ

1

(operacja superpozycji relacji jest

łączna),

(c)

D*(δ

1

) = D(δ

2

) ⇒ D(δ

2

ο δ

1

) = D(δ

1

),

(d)

D*(δ

1

) = D(δ

2

) ⇒ D*(δ

2

ο δ

1

) = D*(δ

2

).

Dowód (a)

Trzeba pokazać, że ∀

x

(x

∈ (δ

2

ο δ

1

)

–1

⇔ x ∈ (δ

1

–1

ο δ

2

–1

)).

Niech x będzie dowolny. Rozpatrzmy dwa przypadki: albo x nie jest parą uporząd-
kowaną, albo x jest parą uporządkowaną. W pierwszym przypadku równoważność
jest oczywista.

W drugim przypadku mamy dla pewnej pary (a, b) : x = (a, b).

L : x ∈ (δ

2

ο δ

1

)

–1

⇔ (a, b) ∈ (δ

2

ο δ

1

)

–1

⇔ (b, a) ∈ δ

2

ο δ

1

⇔

⇔ ∃

c

(b δ

1

c ∧ c δ

2

a) ⇔ ∃

c

(c δ

1

–1

b ∧ a δ

2

–1

c) ⇔

⇔ ∃

c

(a δ

2

–1

c ∧ c δ

1

–1

b) ⇔ (a, b) ∈ δ

1

–1

ο δ

2

–1

⇔ x ∈ δ

1

–1

ο δ

2

–1

: P

d

1

d

2

a c

b

d

2

d

1

o

d

1

–1

a c

b

d

2

-1

d

2

d

1

o

( )

-1

d

2-1

d

1-1

o

=

δ

2

–1

δ

1

–1

d

1

d

2

a c

b

d

2

d

1

o

d

1

–1

a c

b

d

2

-1

d

2

d

1

o

( )

-1

d

2-1

d

1-1

o

=

d

1

d

2

a c

b

d

2

d

1

o

d

1

–1

a c

b

d

2

-1

d

2

d

1

o

( )

-1

d

2-1

d

1-1

o

=

d

1

d

2

a c

b

d

2

d

1

o

d

1

–1

a c

b

d

2

-1

d

2

d

1

o

( )

-1

d

2-1

d

1-1

o

=

d

1

d

2

a c

b

d

2

d

1

o

d

1

–1

a c

b

d

2

-1

d

2

d

1

o

( )

-1

d

2-1

d

1-1

o

=

Finalnie:

x

∈ (δ

2

ο δ

1

)

–1

⇔ x

∈ (δ

1

–1

ο δ

2

–1

).

Intuicję graficzną dowodu przedstawia rysunek 7.

Szkic dowodu (c)

Załóżmy, że

D*(δ

1

) = D(δ

2

).

L : a ∈ D(δ

2

ο δ

1

) ⇔ ∃

c

a(δ

2

ο δ

1

)c ⇔

⇔ ∃

c

∃

b

(a δ

1

b ∧ b δ

2

c) ⇒ ∃

c

∃

b

(a δ

1

b) ∧ ∃

c

∃

b

(b δ

2

c) ⇔

⇔ ∃

b

(a δ

1

b) ∧ ∃

c

(b δ

2

c) ⇒ ∃

b

(a δ

1

b) ⇔ a ∈ D(δ

1

) : P

Rysunek 6

Rysunek 7

d

1

d

2

a b

c

d

2

d

1

o

d

1

d

2

a c

b

d

2

d

1

o

d

1

–1

a c

b

d

2

-1

d

2

d

1

o

( )

-1

d

2-1

d

1-1

o

=

d

1

d

2

a c

b

d

2

d

1

o

d

1

–1

a c

b

d

2

-1

d

2

d

1

o

( )

-1

d

2-1

d

1-1

o

=

13

Finalnie:

a ∈ D(δ

2

ο δ

1

) ⇒ a ∈ D(δ

1

), zatem D(δ

2

ο δ

1

) ⊆ D(δ

1

).

P : a ∈ D(δ

1

) ⇔ ∃

b

(b ∈ D*(δ

1

) ∧ aδ

1

b) ⇔

⇔

15

∃

b

(b ∈ D(δ

2

) ∧ a δ

1

b) ⇒ ∃

b

(aδ

1

b ∧ ∃

c

bδ

2

c) ⇔

⇔ ∃

c

∃

b

(aδ

1

b ∧ bδ

2

c) ⇔ ∃

c

a(δ

2

ο δ

1

)c ⇔ a ∈ D(δ

2

ο δ

1

) : L

Zatem a ∈ D(δ

1

) ⇒ a ∈ D(δ

2

ο δ

1

), czyli D(δ

1

) ⊆ D(δ

2

ο δ

1

).

Finalnie — przy założeniu, że D*(δ

1

) = D(δ

2

) — mamy D(δ

1

) = D(δ

2

ο δ

1

).

15

Wykorzystujemy tutaj założenie, że D*(

δ

1

) = D(

δ

2

).

14

3. Rodzaje relacji binarnych

Podamy teraz różne rodzaje

relacji binarnych.

Rozważmy dowolną relację δ określoną na zbiorze A (δ

⊆ A

× A).

1.

Jeżeli każdy element zbioru A jest w relacji sam ze sobą, to powiemy, że rela-
cja δ jest

zwrotna

. Można to zapisać symbolicznie:

Relacja δ jest zwrotna wtw, gdy ∀

x∈A

(x δ x)

16

.

Przykład 7

Przykładem relacji zwrotnej jest relacja równoległości prostych na płaszczyź-
nie: każda prosta jest równoległa do samej siebie.

W reprezentacji graficznej relacja jest zwrotna, jeżeli z każdego elementu istnieje
przejście (tranzycja) do niego samego (tzw. tranzycja identycznościowa) (rysunek
8). Inne tranzycje nie mają tu znaczenia.

W reprezentacji macierzowej relacja jest zwrotna, jeżeli na głównej przekątnej są same
jedynki. Macierz dla powyższej relacji została przedstawiona na rysunku 9.

2.

Jeżeli żaden element zbioru A nie jest w relacji sam ze sobą, to powiemy, że rela-
cja δ jest

przeciwzwrotna

. Można to zapisać symbolicznie:

Relacja δ jest przeciwzwrotna wtw, gdy ∀

x∈A

¬(x δ x)

17

.

Przykład 8

Przykładem relacji przeciwzwrotnej jest relacja prostopadłości prostych na płasz-
czyźnie: żadna prosta nie jest prostopadła do samej siebie.

W reprezentacji graficznej relacja jest przeciwzwrotna, jeżeli żaden element zbio-
ru nie ma tranzycji do samego siebie (rysunek 10). Inne tranzycje nie mają zna-
czenia.

3.

Jeżeli dla każdych dwóch elementów x i y zbioru A z faktu, że element x jest
w relacji z elementem y wynika, że również y jest w relacji z x, to powiemy, że
relacja δ jest

symetryczna.

Symbolicznie:

Relacja

δ jest symetryczna wtw, gdy ∀

x,y∈A

(x δ y ⇒ y δ x).

Przykład 9

Przykładem relacji symetrycznej jest także relacja równoległości prostych na płasz-
czyźnie: jeżeli prosta p jest równoległa do prostej q, to prosta q jest również rów-
noległa do prostej p.

16

Inaczej ∀

x∈A

(x, x) ∈ δ.

17

Inaczej ∀

x∈A

(x, x)∉ δ.

a b

c d

Rysunek 8

Rysunek 9

a b

c d

Rysunek 10

1

0

0

0

1

1

0

0

1

0

1

0

1

0

1

1

d

c

b

a

d

c

b

a

1 1 0 1
0 1 0 1
0 0 1 1
0 0 0 1

15

W reprezentacji graficznej relacja jest symetryczna, jeżeli każda tranzycja
ma tranzycję przeciwną (rysunek 11).

4.

Jeżeli dla każdych dwóch elementów x i y zbioru A z faktu, że element x
jest w relacji z elementem y wynika, że y nie jest w relacji z x, to powie-
my, że relacja δ jest

asymetryczna.

Symbolicznie:

Relacja

δ jest asymetryczna wtw, gdy ∀

x,y∈A

[x

δ y ⇒ ¬(y

δ x)].

Przykład 10

Przykładem relacji asymetrycznej jest relacja mniejszości liczb rzeczywi-
stych: jeżeli liczba x jest mniejsza od liczby y, to liczba y nie jest mniejsza od
liczby x.

W reprezentacji graficznej relacja jest asymetryczna, jeżeli żadna tranzycja
nie ma tranzycji przeciwnej, nie ma też tranzycji identycznościowych (rysu-
nek 12).

5.

Jeżeli dla każdych dwóch elementów

x i y zbioru A, z faktu, że element x jest

w relacji z elementem y oraz y jest w relacji z x, wynika, że elementy x i y są
identyczne, to powiemy, że relacja δ jest

antysymetryczna.

Symbolicznie:

Relacja

δ jest antysymetryczna wtw, gdy ∀

x, y ∈ A

[(x δ y ∧ y δ x) ⇒ x = y].

Przykład 11

Przykładem relacji antysymetrycznej jest relacja „mniejsze lub równe”
określona na liczbach rzeczywistych: jeżeli liczba x jest mniejsza lub rów-
na od liczby y oraz y jest mniejsze lub równe od x, to wynika z tego, że
x = y.

W reprezentacji graficznej relacja jest antysymetryczna, jeżeli żadna tranzy-
cja nie ma tranzycji przeciwnej. Tranzycje identycznościowe są dopuszczalne
(rysunek 13).

6.

Jeżeli dla każdych trzech elementów x, y i z

zbioru A, z faktu, że element

x jest w relacji z elementem y oraz y jest w relacji z elementem z wyni-
ka, że element x jest w relacji z elementem z, to powiemy, że relacja δ jest

przechodnia.

Symbolicznie:

Relacja

δ jest przechodnia wtw, gdy ∀

x,y,z∈A

[(x δ y ∧ y δ z) ⇒ x δ z].

Przykład 12

Przykładem relacji przechodniej jest relacja równoległości prostych na
płaszczyźnie: jeżeli prosta p jest równoległa do prostej q oraz prosta q jest
równoległa do prostej s, to prosta p jest również równoległa do prostej s.

a b

c d

Rysunek 11

a b

c d

Rysunek 12

a b

c d

Rysunek 13

Rysunek 14

a b

c d

a b

c d

a b

c d

a

b

c

d

a

b

c

d

a

b

c

d

16

Na rysunku 14 pokazana jest reprezentacja graficzna relacji przechodniej. Rysunek
powstał z rysunku 13 przez dodanie odpowiednich (przerywanych) tranzycji, tak
aby finalna relacja spełniała warunek przechodniości.

7.

Jeżeli dla każdych dwóch elementów x i y zbioru A, element x jest w relacji
z elementem y lub y jest w relacji z elementem x, to powiemy, że relacja δ jest

spójna.

Można to zapisać symbolicznie:

Relacja

δ jest spójna wtw, gdy ∀

x,y∈A

(x δ

y ∨ y δ x).

Przykład 13

Przykładem relacji spójnej jest relacja „mniejsze lub równe” określona na
zbiorze liczb rzeczywistych: dla dowolnych dwóch liczb rzeczywistych x
i y liczba x jest mniejsza lub równa od liczby y lub liczba y jest mniejsza
lub równa od liczby x.

W reprezentacji graficznej relacja jest spójna, jeżeli między dwoma do-
wolnymi elementami istnieje co najmniej jedna tranzycja (w dowolną
stronę). Wszystkie tranzycje identycznościowe są również konieczne
(rysunek 15).

Oznaczmy przez id(A) relację identyczności na zbiorze A. Symbolicznie:

id(A) = {(x, x) : x

∈ A}

.

Twierdzenie 6

Niech δ ⊆ A × A będzie relacją niepustą. Zachodzą następujące własności:
(a)

δ jest zwrotna wtedy i tylko wtedy, gdy id(A) ⊆ δ,

(b)

δ jest przeciwzwrotna wtedy i tylko wtedy, gdy id(A) ∩ δ = ∅,

(c)

δ jest symetryczna wtedy i tylko wtedy, gdy δ = δ

-1

,

(d)

δ jest przechodnia wtedy i tylko wtedy, gdy δ ο δ ⊆ δ.

Dowód (a)

Należy wykazać, że jeżeli relacja δ jest zwrotna, to id(A) ⊆ δ, oraz odwrotnie — że
jeżeli relacja δ spełnia własność id(A) ⊆ δ, to jest zwrotna.

⇒

Jeśli relacja jest zwrotna, to na podstawie definicji mamy: ∀

x∈A

(x δ x). Zatem dla

dowolnego elementu x ze zbioru A mamy (x δ x), czyli (x, x) ∈ δ, zatem id(A) ⊆ δ.

⇐

Załóżmy, że id(A) ⊆ δ. Dla dowolnego x ∈ A mamy: (x, x) ∈ δ, czyli relacja jest
zwrotna.

Rysunek 15

a b

c d

a b

c d

a b

c d

a b

c d

a b

c d

17

Szkic dowodu (b)

⇒

Załóżmy nie wprost, że id(A) ∩ δ ≠ ∅. Dla pewnej pary (x

1

, x

1

) mamy (x

1

, x

1

) ∈ δ,

czyli x

1

δ x

1

. Otrzymujemy sprzeczność.

⇐

Załóżmy nie wprost, że id(A) ∩ δ = ∅ oraz to, że relacja nie jest przeciwzwrotna.
Mamy dla pewnej pary: x

1

δ x

1

, czyli (x

1

, x

1

) ∈ δ. Zatem id(A) ∩ δ ≠ ∅. Otrzymuje-

my sprzeczność.

Szkic dowodu (c)

⇒

Załóżmy, że relacja δ jest symetryczna. Niech (x, y) ∈ δ, mamy x δ y. Z własności
symetrii otrzymujemy y δ x, czyli (y, x) ∈ δ. Zatem (x, y) ∈ δ

-1

. Mamy δ ⊆ δ

-1

. In-

kluzji odwrotnej dowodzi się analogicznie.

⇐

Załóżmy, że δ = δ

-1

.

Niech (x, y) ∈ δ, wtedy z założenia (x, y) ∈ δ

-1

, czyli (y, x) ∈ δ.

Szkic dowodu (d)

⇒

Załóżmy, że δ jest przechodnia. Niech (x, y) ∈ δ ο δ, mamy x (δ ο δ) y. Z własno-
ści złożenia relacji dla pewnego z mamy (x δ z ∧ z δ y). Z założonej przechodniości
mamy x δ y, czyli (x, y) ∈ δ. A więc δ ο δ ⊆ δ.

⇐

Załóżmy, że δ ο δ ⊆ δ. Niech x δ y oraz y δ z. Wtedy x(δ ο δ) z, a więc (x, z) ∈ δ ο δ.
Z założenia (x, z) ∈ δ, czyli x δ z. Relacja δ jest więc przechodnia.

Twierdzenie 7

Prawdziwe są następujące własności niepustych relacji binarnych:
(a)

zwrotność i przeciwzwrotność wykluczają się wzajemnie,

(b)

symetria i asymetria wykluczają się wzajemnie,

(c)

każda relacja asymetryczna jest antysymetryczna,

(d)

każda relacja spójna jest zwrotna,

(e)

żadna relacja zwrotna nie jest asymetryczna.

Twierdzenie 8

Prawdziwe są następujące własności charakteryzujące związki między działaniami
na relacjach a ich rodzajami:



suma i iloczyn dwóch relacji zwrotnych jest relacją zwrotną,



suma i iloczyn dwóch relacji symetrycznych jest relacją symetryczną,



suma i iloczyn dwóch relacji spójnych jest relacją spójną.

18

Bibliografia

1. Gubareni N., 2001: Logika dla studentów, Wydawnictwo Politechniki

Częstochowskiej.

2. Kuratowski K., 2004: Wstęp do teorii mnogości i topologii, PWN, Warszawa.

3. Kuratowski K., Mostowski A., 1978: Teoria mnogości, PWN, Warszawa.

4. Marek W., Onyszkiewicz J., 2003: Elementy logiki i teorii mnogości

w zadaniach, PWN, Warszawa.

5. Rasiowa H., 2004: Wstęp do matematyki współczesnej, PWN, Warszawa.

6. Słupecki J., Hałkowska K., Piróg-Rzepecka K., 1994: Logika i teoria mnogości,

Warszawa.

Bibliografia stron WWW

7. Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.

Witryna internetowa. http://www.mimuw.edu.pl/~tiuryn/skrypt-98.ps.gz, stan
z 21.09.2005 (J. Tiuryn, Wstęp do teorii mnogości i logiki).