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.