Relacje

W wielu sytuacjach spotykamy si¦ relacjami typu:

•

. . . jest mniejsze od . . . 

•

. . . jest równolegªa do . . . 

•

. . . jest podzbiorem . . . 

Jakie cechy posiada relacja a jest mniejsze od b?
Co zrobi¢ je±li ró»ne elementy pewnego zbioru, które s¡

podobne, chcieliby±my traktowa¢ jako takie same?
Czy mo»emy porównywa¢ elementy innych zbiorów (innych

ni» N, R, itp.)?

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

1

Para uporz¡dkowana

Par¦ uporz¡dkowan¡ elementów a i b, gdzie a jest

pierwszym elementem, natomiast b jest drugim elementem

oznaczam jako (a, b). W szczególno±ci

(a, b) = (c, d)

wtedy i tylko wtedy, gdy a = c i b = d. Oczywi±cie,
(a, b) 6= (b, a)

z wyj¡tkiem sytuacji, gdy a = b.

W przypadku zbiorów

{a, b} = {b, a}

Poj¦cie pary uporz¡dkowanej mo»na uogólni¢ na tzw.

krotk¦ (n-krotk¦) czyli uporz¡dkowany zbiór n elementów:

(a

1

, a

2

, . . . , a

n

)

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

2

Zbiór produktowy

Dane s¡ dowolne dwa zbiory A i B. Zbiór wszystkich

uporz¡dkowanych par (a, b), gdzie a ∈ A oraz b ∈ B

nazywamy zbiorem produktowym A i B. Oznaczamy ten

zbiór jako A × B. Z denicji

A × B = {(a, b)|a ∈ A

i b ∈ B}

Zapis A

2

b¦dziemy interpretowa¢ jako A × A.

Przykªad. Niech A = {1, 2} oraz B = {a, b, c}. Wtedy

A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}

B × A = {(a, 1), (b, 1), (c, 1), (a, 2), (b, 2), (c, 2)}

Uwagi. Zauwa»my, »e A × B 6= B × A oraz »e liczba

elementów w zbiorze A × B wynosi

n(A × B) = 6 = n(A)n(B)

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

3

Relacje binarne

Def.: Niech A i B b¦d¡ dowolnymi zbiorami. Relacj¡

binarn¡ (relacj¡) ze zbioru A do B nazywamy dowolny

podzbiór zbioru A × B.
Niech R b¦dzie relacj¡ z A do B. R jest zatem zbiorem par

uporz¡dkowanych, w których pierwszy element pochodzi ze

zbioru A natomiast drugi element pochodzi ze zbioru B.

Zatem dla ka»dej pary (a, b), a ∈ A, b ∈ B dokªadnie

jedno z poni»szych stwierdze« jest prawdziwe:

• (a, b) ∈ R

; czyli a jest w R-relacji z b, co zapisujemy

jako aRb

• (a, b) /

∈ R

; czyli a nie jest w R-relacji z b, co

zapisujemy jako aRb

Je»eli R jest relacj¡ ze zbioru A do zbioru A, to R jest

podzbiorem A

2

= A × A

i relacja R jest relacj¡ na A.

Dziedzin¡ relacji R jest zbiór wszystkich pierwszych

elementów par, które nale»¡ do relacji R. Zakresem relacji

jest zbiór drugich elementów par.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

4

Przykªady relacji

•

Dla zbiorów A = {1, 2, 3}, B = {x, y, z},

R = {(1, y), (1, z), (3, y)}

,

R

jest relacj¡ z A do B, gdy» jest podzbiorem A × B.

Zgodnie z t¡ relacj¡:

1Ry, 1Rz, 3Ry

, ale 1Rx, 2Rx, 2Ry, 2Rz, 3Rx, 3Rz

Dziedzin¡ relacji R jest zbiór {1, 3}, natomiast zakresem

relacji R jest zbiór {y, z}.

•

Zawieranie ⊆ jest relacj¡ dla dowolnej kolekcji zbiorów.

Dla dowolnej pary zbiorów A i B, albo A ⊆ B albo
A * B.

•

m dzieli n jest relacj¡ na zbiorze liczb caªkowitych Z.

Zwykle relacj¦ t¦ zapisujemy jako m | n.
Np.: 3 | 15 ale 3

| 11

.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

5

Przykªady relacji

•

Rozwa»my zbiór L prostych na pªaszczy¹nie.

Prostopadªo±¢, zapisywana jako ⊥, jest relacj¡ na L.

Dla dowolnej pary linii a i b, albo a ⊥ b albo a⊥b.

Podobnie jest równolegªa do, zapisywana jako k, jest

relacj¡ na L, gdy» a k b albo a

kb

.

•

Dla dowolnego zbioru A wa»n¡ relacj¡ na A jest równo±¢

{(a, a)|a ∈ A}

któr¡ zwykle zapisujemy jako =. Relacja ta nazywana

jest równie» identyczno±ci¡ albo relacj¡ diagonaln¡ na
A

i jest równie» oznaczana jako ∆

A

lub po prostu ∆.

•

Oczywi±cie dla ka»dego zbioru A, zbiory A × A oraz ∅

s¡ podzbiorami zbioru A × A, zatem s¡ relacjami na A.

Relacje te nazywamy odpowiednio relacj¡ uniwersaln¡ i

relacj¡ pust¡.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

6

Relacja odwrotna

Def.: Niech R b¦dzie dowoln¡ relacj¡ ze zbioru A do B.

Relacj¡ odwrotn¡ do R, oznaczan¡ jako R

−1

, jest relacja

ze zbioru B do A, która zawiera pary uporz¡dkowane, które

po odwróceniu nale»¡ do R, czyli

R

−1

= {(b, a)|(a, b) ∈ R}

Na przykªad niech A = {1, 2, 3} i B = {x, y, z}. Relacj¡

odwrotn¡ do

R = {(1, y), (1, z), (3, y)}

jest

R

−1

= {(y, 1), (z, 1), (y, 3)}

Uwagi. Dla dowolnej relacji R, R

−1

−1

= R

.

Dziedzina i zakres relacji R

−1

jest równa odpowiednio

zakresowi i dziedzinie relacji R.
Je»eli R jest relacj¡ na A, to R

−1

jest równie» relacj¡ na

A

.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

7

Graczna reprezentacja relacji

1. Relacja na R.
Niech S b¦dzie relacj¡ na zbiorze liczb rzeczywistych R, tj.
S

jest podzbiorem R

2

= R×R. Relacja S jest zbiorem par

uporz¡dkowanych liczb rzeczywistych. Pary punktów mog¡

by¢ przedstawione na pªaszczy¹nie w postaci wykresu.
Wykres przykªadowej relacji S, takiej »e xSy wtedy i tylko

wtedy, gdy y

2

+ x

2

= 4

, przedstawia poni»szy rysunek:

2

2

−2

−2

y

x

2

2

y + x =

4

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

8

Graczna reprezentacja relacji

2. Skierowany graf relacji R na zbiorze sko«czonym A.
Wypisujemy wszystkie elementy zbioru A, a nast¦pnie

rysujemy strzaªk¦ od ka»dego elementu x do ka»dego

elementu y je»eli xRy. Na przykªad relacj¦ R na zbiorze
A = {1, 2, 3, 4}

okre±lon¡ jako:

R = {(1, 2), (2, 2), (2, 4), (3, 2), (3, 4), (4, 1), (4, 3)}

mo»na przedstawi¢ za pomoc¡ nast¦puj¡cego grafu:

1

2

3

4

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

9

Reprezentacja relacji na zbiorach

sko«czonych

Je»eli A i B s¡ zbiorami sko«czonymi, to relacj¦ R z A do
B

mo»na przedstawi¢ za pomoc¡:

•

macierzy, której kolejne wiersze odpowiadaj¡ elementom

zbioru A, natomiast kolumny odpowiadaj¡ elementom

zbioru B; je»eli a ∈ A jest w relacji z b ∈ B (aRb)

to na przeci¦ciu wiersza odpowiadaj¡cego elementowi a

i kolumny odpowiadaj¡cej elementowi b stawiamy 1; w

przeciwnym przypadku stawiamy 0

•

diagramu strzaªkowego, który otrzymujemy wypisuj¡c

wszystkie elementy zbioru A w jednej grupie i wszystkie

elementy zbioru B w drugiej grupie i prowadz¡c strzaªki

od elementu a ∈ A do elementu b ∈ B je»eli aRb

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

10

Reprezentacja relacji na zbiorach

sko«czonych

Na przykªad macierz relacji R = {(1, y), (1, z), (3, y)}

ze zbioru A = {1, 2, 3} do zbioru B = {x, y, z} jest

nast¦puj¡ca:

x y z

1 0 1 1

2 0 0 0

3 0 1 0

natomiast diagram strzaªkowy tej relacji ma posta¢:

1

2

3

x

y

z

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

11

Zªo»enie relacji

Niech A, B i C b¦d¡ dowolnymi zbiorami oraz R b¦dzie

relacj¡ z A do B i S b¦dzie relacj¡ z B do C. Czyli R jest

podzbiorem A × B, natomiast S jest podzbiorem B × C.

Z relacji R i S mo»na utworzy¢ now¡ relacj¦, oznaczan¡

jako R ◦ S, zdeniowan¡ jako:

a(R ◦ S)b

je»eli dla pewnego b mamy aRb i bRc

Czyli R ◦ S = {(a, c)| istnieje b ∈ B

dla którego (a, b) ∈ R i (b, c) ∈ S}

Przykªad: Niech A = {1, 2, 3, 4}, B = {a, b, c, d},

C = {x, y, z}

R = {(1, a), (2, d), (3, a), (3, b), (3, d)}

S = {(b, x), (b, z), (c, y), (d, z)}

Wtedy: R ◦ S = {(2, z), (3, x), (3, z)}

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

12

Rodzaje relacji

Def.: Relacja R na zbiorze A jest zwrotna je»eli aRa dla

ka»dego a ∈ A. Je»eli R nie jest zwrotna, wtedy istnieje

takie a ∈ A, »e (a, a) /∈ R.
Def.: Relacja R na zbiorze A jest symetryczna wtedy,

je»eli z tego »e aRb wynika bRa. Czyli R nie jest

symetryczna, je»eli istnieje takie a, b ∈ A, »e aRb i bRa.
Def.: Relacja R na zbiorze A jest antysymetryczna wtedy,

je»eli z tego »e aRb i bRa wynika a = b. Czyli R nie jest

antysymetryczna je»eli istniej¡ ró»ne elementy a, b ∈ A,

takie, »e aRb i bRa.
Uwaga. Relacja mo»e jednocze±nie nie by¢ symetryczna i

antysymetryczna, np.:R = {(1, 3), (3, 1), (2, 3)} lub by¢

jednocze±nie symetryczna i antysymetryczna, np.: R

0

=

{(1, 1), (2, 2)}

(dla A = {1, 2, 3}).

Def.: Relacja R na zbiorze A jest przechodnia wtedy,

je»eli z tego »e aRb i bRc wynika aRc. Czyli R nie jest

przechodnia je»eli istniej¡ takie a, b, c ∈ A, »e aRb i bRc

i aRc.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

13

Rodzaje relacji

Przykªad.

Które z poni»szych relacji, okre±lonych na

zbiorze A = {1, 2, 3, 4}, s¡ zwrotne, symetryczne,

antysymetryczne, przechodnie?

• R

1

= {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)}

• R

2

= {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}

• R

3

= {(1, 3), (2, 1)}

• R

4

= ∅

• R

5

= A × A

Odp.:

Z:

R

2

, R

5

S:

R

2

, R

4

, R

5

AS: R

1

, R

3

, R

4

P:

R

1

, R

2

, R

4

, R

5

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

14

Rodzaje relacji

Przykªad.

Które z poni»szych relacji s¡ zwrotne,

symetryczne, antysymetryczne, przechodnie?

1. Relacja ≤ na zbiorze liczb caªkowitych Z.

2. Relacja zawierania ⊆ na pewnej kolekcji C zbiorów.

3. Relacja ⊥ na zbiorze L prostych na pªaszczy¹nie.

4. Relacja k na zbiorze L prostych na pªaszczy¹nie.

5. Relacja | (m | n) na zbiorze liczb naturalnych N\ {0}.

Odp.:

Z:

1,2,5

S:

3,4

AS: 1,2,5

P:

1,2,5

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

15

Relacja równowa»no±ci

Def.: Niech dany b¦dzie niepusty zbiór A. Relacja R

na A jest relacj¡ równowa»no±ci je»eli R jest zwrotna,

symetryczna i przechodnia, czyli

•

dla ka»dego a ∈ A, aRa

•

je»eli aRb to bRa

•

je»eli aRb i bRc to aRc

Przykªady.

•

jest równolegªa do lub jest identyczna z jest relacj¡

równowa»no±ci na zbiorze L prostych na pªaszczy¹nie

•

relacja zawierania ⊆ nie jest relacj¡ równowa»no±ci, cho¢

jest zwrotna i przechodnia to nie jest symetryczna

•

dla ustalonego m kongruencja modulo m jest jest relacj¡

równowa»no±ci (a ≡ b (mod m) je»eli m | (a − b))

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

16

Klasy równowa»no±ci

Def.: Podziaªem P zbioru A jest kolekcja zbiorów {A

i

}

,

które s¡ niepustymi podzbiorami A i maj¡ dwie wªasno±ci:
1. Ka»dy element a ∈ A nale»y do pewnego A

i

2. Je»eli A

i

6= A

j

wtedy A

i

∩ A

j

= ∅

Niech R b¦dzie relacj¡ równowa»no±ci na A. Dla ka»dego
a ∈ A

, niech [a] oznacza zbiór tych elementów A z którymi

a

jest w relacji R, czyli

[a] = {x|(a, x) ∈ R}

Zbiór [a] nazywamy klas¡ równowa»no±ci (klas¡ abstrakcji,

warstw¡) elementu a w A. Ka»dy element b ∈ [a] jest

reprezentantem tej klasy równowa»no±ci.
Kolekcj¦ wszystkich klas równowa»no±ci elementów zbioru
A

przy relacji R, któr¡ oznaczamy jako A/R, tj.

A/R = {[a] |a ∈ A}

nazywamy przestrzeni¡ ilorazow¡.

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

17

Klasy równowa»no±ci

Twierdzenie: Niech R b¦dzie relacj¡ równowa»no±ci na
A

. Wtedy A/R jest podziaªem A, czyli

(i) Dla ka»dego a ∈ A, a ∈ [a]

(ii) [a] = [b] wtedy i tylko wtedy, gdy (a, b) ∈ R

(iii) Je»eli [a] 6= [b] to [a] ∩ [b] = ∅

Przykªady.
1. Rozwa»my relacj¦ R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}

na zbiorze A = {1, 2, 3}.

Relacja R jest zwrotna,

symetryczna i przechodnia, czyli jest relacj¡ równowa»no±ci,

oraz

[1] = {1, 2} , [2] = {1, 2} , [3] = {3}

Zauwa»my, »e [1] = [2] oraz, »e A/R = {[1] , [3]}

jest podziaªem zbioru A. Jako zbiór reprezentantów klas

równowa»no±ci mo»emy wybra¢ {1, 3} albo {2, 3}.
2. Kongruencja modulo 5 na zbiorze liczb caªkowitych Z.

(poda¢ klasy abstrakcji i zbiór reprezentantów)

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

18

Cz¦±ciowy porz¡dek

Def.: Relacja R na A jest nazywana cz¦±ciowym

porz¡dkiem zbioru A je»eli jest zwrotna, antysymetryczna

i przechodnia. Zbiór A z cz¦±ciowym porz¡dkiem R

nazywamy zbiorem cz¦±ciowo uporz¡dkowanym.
Przykªady.

•

relacja zawierania ⊆ jest cz¦±ciowym porz¡dkiem na

dowolnej kolekcji zbiorów, gdy» jest
zwrotna: A ⊆ A
antysymetryczna: je»eli A ⊆ B i B ⊆ A to A = B
przechodnia: je»eli A ⊆ B i B ⊆ C to A ⊆ C

•

relacja ≤ na zbiorze liczb rzeczywistych R jest

cz¦±ciowym porz¡dkiem

•

relacja a dzieli b (a|b) jest cz¦±ciowym porz¡dkiem na
N\ {0} ale nie jest cz¦±ciowym porz¡dkiem na Z

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

19

Porz¡dek liniowy

Def: Cz¦±ciowy porz¡dek R na zbiorze A jest porz¡dkiem

liniowym, je»eli dla ka»dego a, b ∈ A, zachodzi aRb lub
bRa

.

Przykªady.

•

relacja ≤ na zbiorze liczb rzeczywistych R jest

porz¡dkiem liniowym

•

relacja zawierania ⊆ nie jest porz¡dkiem liniowym

•

cz¦±ciowy porz¡dek na liczbach zespolonych C,

okre±lony jako a + bi 4 c + di wtedy i tylko wtedy, gdy
a ≤ c ∧ b ≤ d

, nie jest porz¡dkiem liniowym

Matematyka Dyskretna, Mariusz Dom»alski, Katedra Systemów Decyzyjnych

20