Relacja 

równoważności.

Relacja porządku.

Logika - ćwiczenia 6

dr Tomasz Kowalski

Slajd  

2/61

 T.Kowalski- Logika – ćw.6: 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/61

 T.Kowalski- Logika – ćw.6: 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

xRy  x ma tych samych rodziców 

co y

1. Badanie zwrotności:

x (xRx)

Dla każdej osoby x:

Tak! To jest zdanie 
prawdziwe.

x ma tych samych 
rodziców co x.

Slajd  

4/61

 T.Kowalski- Logika – ćw.6: 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

2. Badanie symetrii:

x y (xRy  

yRx)

Dla każdych dwojga ludzi x i y:

Tak! To jest zdanie 
prawdziwe.

xRy  x ma tych samych rodziców 

co y

Jeżeli x ma tych samych rodziców co y, to y ma tych 
samych co x .

Slajd  

5/61

 T.Kowalski- Logika – ćw.6: 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

3. Badanie przechodniości:

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

xRz].

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

Tak! To jest zdanie 
prawdziwe.

xRy  x ma tych samych rodziców 

co y

Jeżeli  x ma tych samych rodziców co y  oraz  y 
ma tych co z, to x ma tych samych rodziców co 
z.

Slajd  

6/61

 T.Kowalski- Logika – ćw.6: 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

xRy  liczba  x – y  jest podzielna 

przez 4.

1. Badanie zwrotności:

x (xRx)

Dla każdej liczby 
całkowitej x:

Tak! To jest zdanie 
prawdziwe.

Liczba  x – x jest podzielna 
przez 4.

Slajd  

7/61

 T.Kowalski- Logika – ćw.6: 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

2. Badanie symetrii:

x y (xRy  

yRx)

Dla każdych dwóch liczb całkowitych x i y :

Tak! To jest zdanie 
prawdziwe.

xRy  liczba  x – y  jest podzielna 

przez 4.

Jeżeli x – y  jest liczbą podzielną przez 4, to y – x  jest 
również liczbą podzielną przez 4.

y – x = – (x – 
y )

Slajd  

8/61

 T.Kowalski- Logika – ćw.6: 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,  

3. Badanie przechodniości:

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

xRz].

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

Tak! To jest zdanie 
prawdziwe.

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

xRy  liczba  x – y  jest podzielna 

przez 4.

Jeżeli  x – y  oraz  y – z  są liczbami podzielnymi przez 
4, to x – z  jest również liczbą podzielna przez 4.

Slajd  

9/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – relacja 

równoważności

W zbiorze X = { 1, 2, 3, 4, 5 } dana jest relacja 
równoważności:

xRy  x – y jest liczbą podzielną 

przez 3.

Naszkicować diagram tej relacji.

1

5

2

3

4

Slajd  

10/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Klasa abstrakcji

Niech R będzie relacją równoważnościową na 
zbiorze X. 

Klasą abstrakcji wyznaczoną przez element a 
nazywamy zbiór wszystkich elementów, które są w 
relacji z tym elementem:

[a] = { x  X: aRx }.

W przypadku relacji zilustrowanej 
diagramem:

Klasa abstrakcji jest zbiorem wszystkich 
elementów połączonych ze sobą strzałkami.

Slajd  

11/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Klasy abstrakcji - 

własności

Niech R będzie relacją równoważności na zbiorze 

X. 

1. x  [x],

2.  xRy    [x] = [y],

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

Wówczas dla dowolnych x,y  X  zachodzą 

warunki: 

Slajd  

12/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Zasada abstrakcji

Dowolna relacja równoważności  R  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 jest 
w relacji z y.  

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

Slajd  

13/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – relacja 

równoważności

W zbiorze X = { 2, 3, 6, 8, 9, 10 } dana jest relacja 
równoważności:

xRy  x ma tyle samo dzielników co 

y.

Naszkicować diagram tej relacji.

Wypisać wszystkie klasy 
abstrakcji.

2

3

6

8

9

10

[ 2 ] =

[ 3 ] 
=

{ 2, 
3 } 

{ 2, 
3 } 

[ 6 ] 
=

{ 6, 8, 10 
} 

[ 8 ] 
=

{ 6, 8, 10 
} 

[ 10 ] 
=

{ 6, 8, 10 
} 

[ 9 ] 
=

{ 9 } 

(2)(2)(4)(4)(3) (4)

Slajd  

14/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – relacja 

równoważności

W zbiorze utworów literackich X = { 

„Pan Tadeusz”, „Stepy 

Akermańskie”, „Balladyna”, „Fortepian Chopina”, „Kordian”

, 

„

Świtezianka”

} wprowadzono relację równoważności:

xRy  x ma tego samego autora co 

y.

Naszkicować diagram 
relacji.

Wypisać wszystkie klasy 
abstrakcji.

PT

SA

B

FC

K

Ś

Klasa 1:

{„Pan Tadeusz”, „Stepy 

Akermańskie”,  „Świtezianka”}

Klasa 2:

{„Balladyna”, 
„Kordian”}

Klasa 3:

{„Fortepian Chopina”}

= zbiór utworów 
A.Mickiewicza

= zbiór utworów 
J.Słowackiego

= zbiór utworów 
C.K.Norwida

Slajd  

15/61

 T.Kowalski- Logika – ćw.6: 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: xRy    | x | = | 

y |.

Naszkicować diagram. Wyznaczyć klasy 
abstrakcji tej relacji.

2.  x y (xRy  yRx)

Tak! Każda liczba ma wartość bezwzględną taką samą 
jak ona.

1.  x (xRx)

Tak! Jeżeli liczba ma taką samą wartość bezwzględną 
jak druga, to druga taką samą jak pierwsza.

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

Tak! Jeżeli liczba ma taką samą wartość bezwzględną jak 
druga, a druga – jak trzecia, to pierwsza ma taką samą 
wartość bezwzględną jak trzecia.

Slajd  

16/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – klasy 

abstrakcji

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.

- 2

-1

0

1

2

[ 0 ] = { 0 } 

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

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

Otrzymane zbiory są 

rozłączne.

Sumą otrzymanych zbiorów jest cała 

przestrzeń.

Slajd  

17/61

 T.Kowalski- Logika – ćw.6: 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].

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

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

Slajd  

18/61

 T.Kowalski- Logika – ćw.6: 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  

19/61

 T.Kowalski- Logika – ćw.6: 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  

20/61

 T.Kowalski- Logika – ćw.6: 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  

21/61

 T.Kowalski- Logika – ćw.6: 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  

22/61

 T.Kowalski- Logika – ćw.6: 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  

23/61

 T.Kowalski- Logika – ćw.6: 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  

24/61

 T.Kowalski- Logika – ćw.6: 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  

25/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Relacja częściowego 

porządku

Załóżmy, że dana jest relacja częściowego 
porządku  oznaczona symbolem  ≤ .

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

y ).

Wówczas zapis  x < y oznaczać będzie, że x 
poprzedza y.

Slajd  

26/61

 T.Kowalski- Logika – ćw.6: 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 

x umieszcza się niżej niż y.

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

przechodniości relacji.

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

zwrotności.

Slajd  

27/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – diagram 

Hassego

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

X = {2, 4, 6, 8 }

x ≤ y  x jest 

dzielnikiem y.

2

4

6

8

x < y  (x  y  x 

jest 

dzielnikiem

 y ).

Slajd  

28/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – diagram 

Hassego

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

X = {2, 3, 6, 8, 24 }

x ≤ y  x jest dzielnikiem y.

2

3

6

x < y  (x  y  x 

jest 

dzielnikiem

 y ).

8

24

Slajd  

29/61

 T.Kowalski- Logika – ćw.6: 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  

30/61

 T.Kowalski- Logika – ćw.6: 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  

31/61

 T.Kowalski- Logika – ćw.6: 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  

32/61

 T.Kowalski- Logika – ćw.6: 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  

33/61

 T.Kowalski- Logika – ćw.6: 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  

34/61

 T.Kowalski- Logika – ćw.6: 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  

35/61

 T.Kowalski- Logika – ćw.6: 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  

36/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie - wyróżnione 

elementy

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

2

4

6

8

Wskazać wyróżnione 
elementy.

Elementy 
maksymalne:

6, 8.

Element największy:

Nie ma.

Elementy minimalne:

2.

Element 
najmniejszy:

2.

Slajd  

37/61

 T.Kowalski- Logika – ćw.6: 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:

24.

Element największy:

24.

Elementy minimalne:

2, 3.

Element 
najmniejszy:

Nie ma.

2

3

6

8

24

Slajd  

38/61

 T.Kowalski- Logika – ćw.6: 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  

39/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie - wyróżnione 

elementy

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



{1

}

{2

}

{1,2

}

Wskazać wyróżnione 
elementy.

Elementy 
maksymalne:

{1, 
2}.

Element największy:

{1, 2}.

Elementy minimalne:

Element 
najmniejszy:

.

.

Slajd  

40/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie - wyróżnione 

elementy

Niech X będzie zbiorem liczb naturalnych  1.

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

Elementy 
maksymalne:

Nie ma.

Element największy:

Nie ma.

Elementy minimalne:

1.

Element 
najmniejszy:

1.

Slajd  

41/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie - wyróżnione 

elementy

Niech X będzie zbiorem liczb naturalnych   2.

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  

42/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – diagram 

Hassego

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

X = {2, 3, 6, 9, 18 }

x ≤ y  x = y albo x ma mniej 

dzielników niż y.

x < y  x 

ma mniej dzielników 

niż

 y.

(2)(2)(4)(3) (6)

2

3

9

6

18

Wskazać elementy 
wyróżnione.

Elementy 
maksymalne:

18.

Element największy:

18.

Elementy minimalne:

Element 
najmniejszy:

Nie 
ma.

2, 
3.

Slajd  

43/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – diagram 

Hassego

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

X = {2, 3, 6, 9, 18 }

x ≤ y  x jest dzielnikiem y.

x < y  x 

jest właściwym 

dzielnikiem

 y.

2

3

6

9

18

Wskazać elementy 
wyróżnione.

Elementy 
maksymalne:

18.

Element największy:

18.

Elementy minimalne:

Element 
najmniejszy:

Nie 
ma.

2, 
3.

Slajd  

44/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – diagram 

Hassego

W zbiorze X = {(1,2), (2,4), (2,3), (3,2)} 
wprowadzono tzw. porządek leksykograficzny:

( , )

( , )

(

)

L

a b

c d

a c

a c b d

��<�=٣

Sporządzić diagram Hassego tej relacji.

Wskazać elementy 
wyróżnione.

(1,2)

(2,4)

(2,3

)

(3,2

)

Elementy 
maksymalne:

(3,2)
.

Element największy:

(3,2).

Elementy minimalne:

Element 
najmniejszy:

(1,2)
.

(1,2
).

Slajd  

45/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – diagram 

Hassego

W zbiorze X = {(1,2), (2,4), (2,3), (3,2)} 
wprowadzono tzw. porządek produktywny:

( , )

( , )

P

a b

c d

a c

b d

��

٣

Sporządzić diagram Hassego tej relacji.

Wskazać elementy 
wyróżnione.

(1,2)

(2,4)

(2,3

)

(3,2

)

Elementy 
maksymalne:

(3,2), 
(2,4).

Element największy:

Nie ma.

Elementy minimalne:

Element 
najmniejszy:

(1,2)
.

(1,2
).

Slajd  

46/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – diagram 

Hassego

W zbiorze X = {(0,0), (2,4), (3,8), (3,2), (1,5)} 
rozpatrujemy porządek leksykograficzny:

( , )

( , )

(

)

L

a b

c d

a c

a c b d

��<�=٣

Sporządzić diagram Hassego tej relacji.

Wskazać elementy 
wyróżnione.

(0,0)

(2,4)

(3,2

)

(3,8

)

(1,5

)

Elementy 
maksymalne:

(3,8)
.

Element największy:

(3,8).

Elementy minimalne:

Element 
najmniejszy:

(0,0)
.

(0,0
).

Slajd  

47/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Ćwiczenie – diagram 

Hassego

W zbiorze X = {(0,0), (2,4), (3,8), (3,2), (1,5)} 
rozpatrujemy porządek produktywny:

( , )

( , )

P

a b

c d

a c

b d

٣�

Sporządzić diagram Hassego tej relacji.

Wskazać elementy 
wyróżnione.

Elementy 
maksymalne:

(3,8
).

Element największy:

(3,8).

Elementy minimalne:

Element 
najmniejszy:

(0,0)
.

(0,0
).

(0,0)

(2,4)

(3,2

)

(3,8

)

(1,5

)

Slajd  

48/61

 T.Kowalski- Logika – ćw.6: 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  

49/61

 T.Kowalski- Logika – ćw.6: 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  

50/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Uwaga

Diagram Hassego relacji liniowego porządku nie ma 
rozgałęzień. 

(1,2)

(2,4)

(2,3

)

(3,2

)

(0,0)

(2,4)

(3,2

)

(3,8

)

(1,5

)

Porządek leksykograficzny jest porządkiem 
liniowym. 

Slajd  

51/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Dowodzenie praw rachunku zbiorów 

metodami KRZ

Do dowodzenia praw rachunku zbiorów można 
posłużyć się metodą wykorzystującą klasyczny 
rachunek zdań i pojęcie tautologii. 

Slajd  

52/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Dowodzenie praw rachunku zbiorów 

metodami KRZ

Wykrycie, czy dane wyrażenie, mające postać równości 
bądź inkluzji zbiorów, jest ogólnie obowiązującym 
prawem, polega na przekształceniu formuły rachunku 
zbiorów na formułę rachunku zdań, a następnie 
sprawdzeniu, czy otrzymany schemat jest tautologią. 

Jeśli otrzymana formuła jest tautologią, to oznacza, 
że wyjściowy wzór jest prawem rachunku zbiorów; 
jeśli formuła nie jest tautologią, to znak, że badane 
wyrażenie nie jest takim prawem.

Slajd  

53/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Dowodzenie praw rachunku zbiorów 

metodami KRZ

1) A  B    x (x  A  x  B)

2) A = B  x (x  A  x  B)

3) x  (A  B)  (x  A  x  B)

4) x  (A  B)  (x  A  x  B)

6) x  (A – B)  (x  A    ~ (x  B))

5) x  A 

/

  ~ (x  A)

Przekształcanie formuły rachunku zbiorów na 
rachunek zdań polega na systematycznym 
stosowaniu wzorów:

Slajd  

54/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Przykład

Sprawdzić, czy prawem rachunku zbiorów jest 
wyrażenie: 

(A – B)  (A  B).

Należy sprawdzić, 
czy:

x  (A – B) x  (A  

B)

(x  A  ~ (x  

B))

 (x  A  x  

B)

(p  ~ 

q)

Formułę można zmienić całkowicie na schemat KRZ, 
podstawiając za wyrażenie x  A - zmienną p, 

natomiast za x  B - zmienną q. 

Otrzymamy 
wtedy:

 (p  q)

Slajd  

55/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Przykład

Zbadamy przy pomocy metody skróconej, czy 
otrzymana formuła jest tautologią.

Sprawdzimy, czy formuła może stać się schematem 
zdania fałszywego, a zatem, czy pod głównym 
spójnikiem może pojawić się 0.

( p  ~ q )  ( p  q )

0

1

0

1

1

0

1

Ponieważ nie ma możliwości, aby formuła była 
schematem zdania fałszywego, to jest ona 
tautologią.

0

Sprzeczno

ść

Badane wyrażenie 

jest

 prawem 

rachunku zbiorów.

Slajd  

56/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Przykład

x  [(A  B) – 

C]

[(x  A  x  B)  ~ (x  

C)]

[x  (A  B)  ~ (x  

C)]

Sprawdzić, czy prawem rachunku zbiorów jest 

wyrażenie:     [(A  B) – C]  [(A – B )  (B – C)] 

Po podstawieniu zmiennej p za x  A, q za x  B oraz r za 

x  C mamy:

[(p  q)  ~ r]  [(p  ~ q)  (q  ~ r)]

 x  [(A – B )  (B – 

C)] 

 [x  (A – B )  x  (B – 

C)] 

 [(x  A  ~ (x  B ))  (x  B  ~ (x  

C))] 

Slajd  

57/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Przykład

Zbadamy przy pomocy metody skróconej, czy 
otrzymana formuła jest tautologią.

[(p  q)  ~ r]  [(p  ~ q)  (q  ~ 

r)]

0

1

0

1

1

1

1

0

Sprawdzimy, czy formuła może stać się schematem 
zdania fałszywego, stawiając pod głównym spójnikiem 
0.

Ponieważ istnieje przypadek, w którym formuła jest 
schematem zdania fałszywego, to nie jest ona 
tautologią. 

1

1

1

0

0

0

1

1

Tym samym badane wyrażenie 

nie jest

 prawem 

rachunku zbiorów.

Slajd  

58/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Przykład

Jakiej formule rachunku zdań odpowiada poniższa 
formuła rachunku zbiorów:

(A  B)    ( A  B ), 

[A  ( B   C )]    [ ( A  B)   ( B  

C )],

[( A  B )  C 

/

  ]   [ ( A – C )  ( B – 

C )],

[( A – B ) C ]  =  [ ( A  C )  B 

/

 ],

[ A – ( A  B )]  =  ( A – B ).

Slajd  

59/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Z życia studentów

W akademiku w pokoju studenckim trwa 
impreza. Biesiadnicy raz po raz wznoszą toast:

- Za Edka, żeby zdał!

W pewnej chwili otwierają się drzwi i wchodzi 
Edek.

- I co Edek, zdałeś?

- Zdałem, tylko jednej nie przyjęli, bo miała 
obitą szyjkę.

Slajd  

60/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.

Z życia studentek (medycyny)

Studentka zdawała egzamin na Akademii Medycznej z 
układu kostnego.

 

Po namyśle dziewczyna mówi: 
- To był mężczyzna. 

Profesor podał jej miednicę i poprosił o 
zidentyfikowanie płci dawnego właściciela. 

- A dlaczego Pani tak uważa? 

- Bo tutaj był kiedyś członek.

- Oj był, i to wiele razy.

Slajd  

61/61

 T.Kowalski- Logika – ćw.6: Relacja równoważności. Relacja porządku.