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.