Relacja 

równoważności.

Relacja porządku.

Logika - wykład 6

dr Tomasz Kowalski

Slajd  

2/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Relacja równoważności

Mówimy, że R jest relacją równoważności 
(równoważnością) na zbiorze X, gdy jest ona 
jednocześnie zwrotna, symetryczna i 
przechodnia. 

Relacja równoważności jest 
uogólnieniem równości.  Z tego powodu 
często oznaczana jest symbolem   

≈

 .

1.  x (xRx),

2.  x y (xRy  yRx),

3.  xyz [(xRy  yRz)  xRz].

Slajd  

3/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Relacja równoważności

 ≈  jest relacją równoważności (równoważnością) na 
zbiorze X, gdy 

1.  x (x ≈ x),

2.  x y (x ≈ y  y ≈ x),

3.  xyz [(x ≈ y  y ≈ z)  x ≈ z].

Slajd  

4/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

równoważności

Wykazać, że następująca relacja jest relacją 
równoważności:

X – zbiór ludzi

x ≈ y  x ma tyle samo lat co y

1. Badanie zwrotności:

x (x ≈ x)

Dla każdej osoby x: x ma tyle samo lat 
co x.

Tak! To jest zdanie 
prawdziwe.

Slajd  

5/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

równoważności

Wykazać, że następująca relacja jest relacją 
równoważności:

X – zbiór ludzi

x ≈ y  x ma tyle samo lat co y

2. Badanie symetrii:

x y (x ≈ y  y 

≈ x)

Dla każdych dwojga ludzi x i y zachodzi warunek:

 Jeżeli x ma tyle samo lat co y, to y ma tyle samo lat 
co x .

Tak! To jest zdanie 
prawdziwe.

Slajd  

6/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

równoważności

Wykazać, że następująca relacja jest relacją 
równoważności:

X – zbiór ludzi

x ≈ y  x ma tyle samo lat co y

3. Badanie przechodniości:

xyz [(x ≈ y  y ≈ z)  x 

≈ z].

Dla każdych trojga ludzi x, y i z zachodzi 
warunek:

Jeżeli  x ma tyle samo lat co y  oraz  y ma tyle 
samo lat co z, to x ma tyle samo lat co z.

Tak! To jest zdanie 
prawdziwe.

Slajd  

7/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

równoważności

Wykazać, że następująca relacja jest relacją 
równoważności:

X – zbiór liczb całkowitych

x ≈ y  x + y jest liczbą parzystą.

1. Badanie zwrotności:

x (x ≈ x)

Dla każdej liczby całkowitej x: x + x  jest liczbą 
parzystą.

Tak! To jest zdanie 
prawdziwe.

Slajd  

8/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

równoważności

Wykazać, że następująca relacja jest relacją 
równoważności:

X – zbiór liczb całkowitych

x ≈ y  x + y jest liczbą parzystą.

2. Badanie symetrii:

x y (x ≈ y  y 

≈ x)

Dla każdych dwóch liczb całkowitych x i y zachodzi 
warunek: Jeżeli x + y  jest liczbą parzystą, to y + x 
jest liczbą parzystą.

Tak! To jest zdanie 
prawdziwe.

Slajd  

9/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

równoważności

Wykazać, że następująca relacja jest relacją 
równoważności:

X – zbiór liczb całkowitych

x ≈ y  x + y jest liczbą parzystą.

3. Badanie przechodniości:

xyz [(x ≈ y  y ≈ z)  

x ≈ z].

Dla każdych trzech liczb całkowitych x, y i z zachodzi 
warunek: Jeżeli  x + y  oraz  y + z  są liczbami 
parzystymi, to x + z  jest liczbą parzystą.

Tak! To jest zdanie 
prawdziwe.

x + z = (x + y ) + (y + 
z ) – 2y

Slajd  

10/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

równoważności

Wykazać, że następująca relacja jest relacją 
równoważności:

X – zbiór liczb całkowitych

x ≈ y  5 jest dzielnikiem liczby x – 

y.

1. Badanie zwrotności:

x (x ≈ x)

Dla każdej liczby całkowitej x: 5 jest dzielnikiem 
liczby x – x = 0.

Tak! To jest zdanie 
prawdziwe.

Slajd  

11/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

równoważności

Wykazać, że następująca relacja jest relacją 
równoważności:

X – zbiór liczb całkowitych

x ≈ y  5 jest dzielnikiem liczby x – 

y.

2. Badanie symetrii:

x y (x ≈ y  y 

≈ x)

Dla każdych dwóch liczb całkowitych x i y zachodzi 
warunek: Jeżeli x – y  jest liczbą podzielną przez 5, to 
y – x  = –(x – y) jest również podzielne przez 5.

Tak! To jest zdanie 
prawdziwe.

Slajd  

12/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

równoważności

Wykazać, że następująca relacja jest relacją 
równoważności:

X – zbiór liczb całkowitych,  

x ≈ y  5 jest dzielnikiem liczby x – 

y.

3. Badanie przechodniości:

xyz [(x ≈ y  y ≈ z)  x 

≈ z].

Dla każdych trzech liczb całkowitych x, y i z zachodzi 
warunek: Jeżeli  x – y  oraz  y – z  są liczbami 
podzielnymi przez 5, to x – z  jest również podzielne 
przez 5.

Tak! To jest zdanie 
prawdziwe.

x – z = (x – y ) + (y – 
z )

Slajd  

13/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Klasa abstrakcji

Niech  będzie relacją równoważnościową na 

zbiorze X. 

Dla dowolnego a  X  klasą abstrakcji elementu a 

(klasą abstrakcji, której reprezentantem jest a) 
względem relacji równoważnościowej    nazywamy 

zbiór:

[a]



 = { x  X: a  

x }.

Slajd  

14/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Uwaga

W dalszym ciągu, jeśli będziemy mieli jedną 
ustaloną relację równoważności , na 

oznaczenie klasy abstrakcji elementu a 
względem  będziemy pisać [a] zamiast [a]



. 

Slajd  

15/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Klasy abstrakcji - 

własności

Niech  będzie dowolną relacją równoważności 

na zbiorze X. Wówczas dla dowolnych x,y  X  

zachodzą warunki: 

1. x  [x],

2.  x  y    [x] = [y],

3.  ~ (x  y )  [x]  [y] = ,

Slajd  

16/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Zasada abstrakcji

Dowolna relacja równoważności    w zbiorze  

X  ustala podział tego zbioru na rozłączne i 
niepuste podzbiory, będące klasami abstrakcji 
tej relacji.

Dwa elementy x, y należą 
do tej samej klasy 
abstrakcji wtedy i tylko 
wtedy gdy x 



 y.  

Dwa elementy x, y należą 
do tej samej klasy 
abstrakcji gdy mają jakąś 
wspólną cechę.

Slajd  

17/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – klasy 

abstrakcji

Wykazać, że relacja ta jest relacją 
równoważności:

W zbiorze X = { -2, -1, 0, 1, 2 } określona została 
relacja wzorem: x  y    | x | = 

| y |.

Naszkicować diagram. Wyznaczyć klasy 
abstrakcji tej relacji.

2.  x y (x ≈ y  y ≈ x)

Tak! Każda liczba ma moduł taki sam 
jak ona.

1.  x (x ≈ x)

Tak! Jeżeli liczba ma taki sam moduł jak druga, 
to druga taki sam jak pierwsza..

3. xyz [(x ≈ y  y ≈ z)  x ≈ z].

Tak! Jeżeli liczba ma taki sam moduł jak druga, a 
druga – jak trzecia, to pierwsza ma taki sam 
moduł jak trzecia.

Slajd  

18/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – klasy 

abstrakcji

0

1

-1

-2

2

[ 0 ] = { 0 } 

[ - 1 ] = [ 1 ]  = { - 1,  
1 } 

[ - 2 ] = [ 2 ]  = { - 2,  
2 } 

Otrzymane zbiory są 

rozłączne.

Sumą otrzymanych zbiorów jest cała 

przestrzeń.

Wykazać, że a relacja ta jest relacją 
równoważności:

W zbiorze X = { -2, -1, 0, 1, 2 } określona została 
relacja wzorem: x  y    | x | = 

| y |.

Naszkicować diagram. Wyznaczyć klasy 
abstrakcji tej relacji.

Slajd  

19/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – klasy 

abstrakcji

Wykazać, że relacja ta jest relacją 
równoważności:

W zbiorze prostych na płaszczyźnie określona 
została relacja wzorem:

x  y   x ||  y .

Wyznaczyć klasy abstrakcji tej relacji.

2.  x y (x ≈ y  y ≈ x)

Tak! Każda prosta jest równoległa do 
siebie.

1.  x (x ≈ x)

Tak! Jeżeli prosta jest równoległa do drugiej, to 
druga jest równoległa do pierwszej.

3. xyz [(x ≈ y  y ≈ z)  x ≈ z].

Tak! Jeżeli prosta jest równoległa do drugiej, a 
druga – do trzeciej, to pierwsza jest równoległa 
do trzeciej.

Slajd  

20/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – klasy 

abstrakcji

Wykazać, że relacja ta jest relacją 
równoważności:

W zbiorze prostych na płaszczyźnie określona 
została relacja wzorem:

x  y   x ||  y .

Wyznaczyć klasy abstrakcji tej relacji.

Klasa abstrakcji wyznaczona przez daną prostą 
jest zbiorem wszystkich prostych do niej 
równoległych.

Wspólną cechą, którą posiadają proste 
równoległe, jest ten sam kierunek.

Slajd  

21/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – klasy 

abstrakcji

Wyznaczyć klasy abstrakcji  relacji 
równoważności:

X – zbiór liczb całkowitych

x ≈ y  x + y jest liczbą parzystą.

[ 0 ] =  {

0
, 

2
, 

-2, 4

, 

-4, …}

- zbiór liczb 

parzystych.

[ 1 ] =  {

1
, 

-1, 3,  -3, 5,  …}

- zbiór liczb 

nieparzystych.

Otrzymane zbiory są 

rozłączne.

Sumą otrzymanych zbiorów jest zbiór liczb 

całkowitych.

Slajd  

22/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – klasy 

abstrakcji

Wyznaczyć klasy abstrakcji  relacji 
równoważności:

X – zbiór liczb całkowitych nieujemnych

x ≈ y  liczba x – y  jest podzielna 

przez 4.

[ 0 ] =  {

0
, 

4
, 

8,  12

, 

 
16, 

…}

- zbiór liczb podzielnych przez 4.

[ 1 ] =  {

1
, 

5, 9,  13, 

 
17, 

…}

- zbiór liczb, które przy dzieleniu 

przez 4 dają resztę 1.

Otrzymane zbiory są 

rozłączne.

Sumą otrzymanych zbiorów jest zbiór liczb 

całkowitych.

[ 2 ] =  {

2
, 

6, 10, 14, 

 
18, 

…}

- zbiór liczb, które przy dzieleniu 

przez 4 dają resztę 2.

[ 3 ] =  {

3
, 

7, 11, 15, 

 
19, 

…}

- zbiór liczb, które przy dzieleniu 

przez 4 dają resztę 3.

Slajd  

23/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – klasy 

abstrakcji

Wyznaczyć klasy abstrakcji  relacji 
równoważności:

X – zbiór liczb całkowitych

x ≈ y  x + y jest liczbą parzystą.

[ 0 ] =  {

0
, 

2
, 

-2, 4

, 

-4, …}

- zbiór liczb 

parzystych.

[ 1 ] =  {

1
, 

-1, 3,  -3, 5,  …}

- zbiór liczb 

nieparzystych.

Otrzymane zbiory są 

rozłączne.

Sumą otrzymanych zbiorów jest zbiór liczb 

całkowitych.

Slajd  

24/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – klasy 

abstrakcji

Wyznaczyć klasy abstrakcji  relacji 
równoważności:

X – zbiór liczb całkowitych nieujemnych

x ≈ y  4 jest dzielnikiem liczby x – 

y.

[ 0 ] =  {

0
, 

4
, 

8,  12

, 

 
16, 

…}

- zbiór liczb podzielnych przez 4.

[ 1 ] =  {

1
, 

5, 9,  13, 

 
17, 

…}

- zbiór liczb, które przy dzieleniu 

przez 4 dają resztę 1.

Otrzymane zbiory są 

rozłączne.

Sumą otrzymanych zbiorów jest zbiór liczb 

całkowitych.

[ 2 ] =  {

2
, 

6, 10, 14, 

 
18, 

…}

- zbiór liczb, które przy dzieleniu 

przez 4 dają resztę 2.

[ 3 ] =  {

3
, 

7, 11, 15, 

 
19, 

…}

- zbiór liczb, które przy dzieleniu 

przez 4 dają resztę 3.

Slajd  

25/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Relacja częściowego 

porządku

Mówimy, że R jest relacją (częściowego) 
porządku, gdy jest ona jednocześnie zwrotna, 
słabo asymetryczna i przechodnia. 

1.  x (xRx),

2. xy [(x 



 y  xRy)  ~ yRx],

3.  xyz [(xRy  yRz)  xRz].

Slajd  

26/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Relacja częściowego 

porządku

Warunek 2. definicji można zastąpić warunkiem 
równoważnym:

2. xy [(xRy  yRx)  x = y ],

Slajd  

27/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

porządku

Wykazać, że następująca relacja jest relacją 
porządku w zbiorze X:

X = {2, 3, 4, 5, 6 }

xRy  x jest dzielnikiem y

1. Badanie zwrotności:

x (xRx)

Każda liczba jest swoim dzielnikiem.

Tak! To jest zdanie 
prawdziwe.

Slajd  

28/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

porządku

X = {2, 3, 4, 5, 6 }

xRy  x jest dzielnikiem y

2. Badanie słabej asymetrii:

xy [(xRy  yRx)  x 

= y ],

Dla dwóch liczb podzielność „w obie strony” jest 
możliwa tylko wtedy, gdy liczby te są równe.

Tak! To jest zdanie 
prawdziwe.

Wykazać, że następująca relacja jest relacją 
porządku w zbiorze X:

Slajd  

29/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

porządku

X = {2, 3, 4, 5, 6 }

xRy  x jest dzielnikiem y

3. Badanie przechodniości:

xyz [(xRy  yRz)  

xRz].

Dla każdych trzech liczb x, y i z zachodzi 
warunek:

Jeżeli  x jest dzielnikiem y  oraz  y dzielnikiem z, 
to x jest dzielnikiem z.

Tak! To jest zdanie 
prawdziwe.

Wykazać, że następująca relacja jest relacją 
porządku w zbiorze X:

Slajd  

30/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

porządku

Wykazać, że następująca relacja jest relacją 
porządku w zbiorze X:

X = {, {1}, {2}, {1,2}}



A

 A  

A.

1. Badanie zwrotności:

x (xRx)

Każdy zbiór jest swoim podzbiorem.

Tak! To jest zdanie 
prawdziwe.

ARB  A  

B.

Slajd  

31/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

porządku

Wykazać, że następująca relacja jest relacją 
porządku w zbiorze X:

X = {, {1}, {2}, {1,2}}

ARB  A  

B.

2. Badanie słabej asymetrii:

xy [(xRy  yRx)  x 

= y ],

Dla dwóch zbiorów jest tak, że jeśli pierwszy jest 
podzbiorem drugiego i na odwrót, to zbiory są 
równe.

Tak! To jest zdanie 
prawdziwe.



A

 

B

 A  B  B  A  A 

= B.

Slajd  

32/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – relacja 

porządku

Wykazać, że następująca relacja jest relacją 
porządku w zbiorze X:

X = {, {1}, {2}, {1,2}}

ARB  A  B.

3. Badanie przechodniości:

xyz [(xRy  yRz)  

xRz].

Dla każdych trzech zbiorów A, B i C zachodzi 
warunek: Jeżeli  A jest podzbiorem B, a B podzbiorem 
C, to A jest podzbiorem C.

Tak! To jest zdanie 
prawdziwe.



A

 

B

 

C

 A  B  B  C  A  

C.

Slajd  

33/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Relacja częściowego 

porządku

Relację R będącą częściowym porządkiem 
oznacza się często symbolem  ≤ .

Slajd  

34/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Relacja częściowego 

porządku

Łącznie z relacją częściowego porządku ≤  
rozpatruje się relację  <  zdefiniowaną 
wzorem:

x < y  (x  y)  ( x ≤ 

y ).

Jeżeli x < y, to mówimy, że x poprzedza y.

Slajd  

35/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Diagram Hassego

Relację porządku w zbiorze skończonym 
ilustruje się przy pomocy diagramu Hassego.

1. Elementy zbioru nie będące ze sobą w 

relacji umieszcza się na tym samym 
poziomie.

2. Jeżeli  x poprzedza y  ( x < y ), to element 

y umieszcza się wyżej niż x.

3. Nie umieszcza się strzałek wynikających z 

przechodniości relacji.

4. Nie umieszcza się „pętelek” wynikających ze 

zwrotności.

Slajd  

36/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – diagram 

Hassego

Sporządzić diagram relacji porządku w 
zbiorze X:

X = {2, 3, 4, 5, 6 }

x ≤ y  x jest dzielnikiem y.

2

3

4

6

5

x < y  (x  y  x 

jest dzielnikiem

 y ).

Slajd  

37/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie – diagram 

Hassego

Sporządzić diagram relacji porządku w 
zbiorze X:



{1

}

{2

}

{1,2

}

X = {, {1}, {2}, {1,2}}

A ≤ B  A  

B.

A < B  ( A  B   A  

B).

Slajd  

38/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Wyróżnione elementy

W zbiorze X dana jest relacja częściowego 
porządku  ≤ .

Element a nazwiemy maksymalnym w zbiorze 
X, jeżeli nie poprzedza on żadnego elementu 
tego zbioru.

.

x X

a x

�

$

<

:

Slajd  

39/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Wyróżnione elementy

W zbiorze X dana jest relacja częściowego 
porządku  ≤ .

Element a  nazwiemy największym w zbiorze X, 
jeżeli spełniony jest warunek:

.

x X

x a

�

"

�

Slajd  

40/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Wyróżnione elementy

W zbiorze X uporządkowanym przez relację 
częściowego porządku  ≤  istnieje co najwyżej 
jeden element największy.

Element ten jest 
maksymalny.

Slajd  

41/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Wyróżnione elementy

W zbiorze X dana jest relacja częściowego 
porządku  ≤ .

Element a nazwiemy minimalnym w zbiorze X, 
jeżeli nie poprzedza go żaden element tego 
zbioru.

.

x X

x a

�

$

<

:

Slajd  

42/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Wyróżnione elementy

W zbiorze X dana jest relacja częściowego 
porządku  ≤ .

Element a  nazwiemy najmniejszym w zbiorze 
X, jeżeli spełniony jest warunek:

.

x X

a x

�

"

�

Slajd  

43/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Wyróżnione elementy

W zbiorze X uporządkowanym przez relację 
częściowego porządku  ≤  istnieje co najwyżej 
jeden element najmniejszy.

Element ten jest 
minimalny.

Slajd  

44/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie - wyróżnione 

elementy

Rozważmy częściowy porządek o następującym 
diagramie Hassego:

Wskazać wyróżnione 
elementy.

2

3

4

6

5

Elementy 
maksymalne:

4, 6, 
5.

Element największy:

Nie ma.

Elementy minimalne:

2, 3, 
5.

Element 
najmniejszy:

Nie ma.

Slajd  

45/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie - wyróżnione 

elementy

Niech X będzie zbiorem liczb naturalnych.

Rozpatrzmy w tym zbiorze jako relacje 
porządkującą relację podzielności.

Elementy 
maksymalne:

Nie ma.

Element największy:

Nie ma.

Elementy minimalne:

1.

Element 
najmniejszy:

1.

Slajd  

46/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie - wyróżnione 

elementy

Niech X będzie zbiorem liczb naturalnych 
większych od 1.

Rozpatrzmy w tym zbiorze jako relacje 
porządkującą relację podzielności.

Elementy 
maksymalne:

Nie ma.

Element największy:

Nie ma.

Elementy minimalne:

Wszystkie liczby 
pierwsze.

Element 
najmniejszy:

Nie 
ma.

Slajd  

47/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie - wyróżnione 

elementy

Rozważmy częściowy porządek o następującym 
diagramie Hassego:

Wskazać wyróżnione 
elementy.

Elementy 
maksymalne:

{1,2
}.

Element największy:

{1, 2}.

Elementy minimalne:

.

Element 
najmniejszy:

.



{1

}

{2

}

{1,2

}

Slajd  

48/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Ćwiczenie - wyróżnione 

elementy

Niech X będzie rodziną wszystkich podzbiorów 
pewnego niepustego zbioru A.

Rozpatrzmy w tym zbiorze jako relacje 
porządkującą relację inkluzji .

Elementy 
maksymalne:

A.

Element największy:

A.

Elementy minimalne:

.

Element 
najmniejszy:

.

Slajd  

49/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Relacja liniowego 

porządku

Mówimy, że R jest relacją liniowego 
porządku, gdy jest ona jednocześnie zwrotna, 
słabo asymetryczna, przechodnia i spójna. 

1.  x (xRx),

2. xy [(x 



 y  xRy)  ~ yRx],

3.  xyz [(xRy  yRz)  xRz].

4. xy [(x 



 y )  (xRy   yRx)],

Slajd  

50/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Przykład relacji liniowego 

porządku

W zbiorze liczb rzeczywistych „zwykła” relacja  
≤  jest relacją liniowego porządku. 

1.  x (x ≤ x),

2. xy [(x 



 y  x ≤ y)  ~ y ≤ x],

3.  xyz [(x ≤ y  y ≤ z)  x ≤ z].

4. xy [(x 



 y )  (x ≤ y   y ≤ x)],

Slajd  

51/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Przecież to logiczne

Idzie turysta i widzi jak baca drzewo rąbie aż 
wióry lecą. 

Pyta z podziwem:

- Baco, gdzieżeście się nauczyli tak pięknie 
drzewo rąbać?

- A na Saharze.

- Na Saharze???  Przecież to jest pustynia???!!!

- Teraz, tak. 

Slajd  

52/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.

Nasz nauczyciel

Na komisariat policji przybiegają dwaj zdyszani 
chłopcy i krzyczą:

- Nasz nauczyciel... Nasz nauczyciel...

W końcu jeden z policjantów pyta:

- Co mu jest? Miał wypadek?

- Nie. Źle zaparkował!

Slajd  

53/53

 T.Kowalski- Logika – wykład 8: Relacja równoważności. Relacja 
porządku.