Elementy teorii relacji.

Własności relacji.

Logika – wykład 5

dr Tomasz Kowalski

Slajd

2/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Iloczyn kartezjański

zbiorów

Iloczynem kartezjańskim

niepustych zbiorów A i B

nazywamy zbiór:

AB ={(x,y

):

xA 

yB }

Slajd

3/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład

A = {0,1}, B = {a, b, c}

A  B =

Wyznaczyć zbiór kartezjański zbiorów:

{
}

(0,a
),

(0,b
),

(0,c
),

(1,a
),

(1,b
),

(1,c
)

Slajd

4/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Kwadrat kartezjański zbioru

Kwadratem kartezjańskim

niepustego zbioru A

nazywamy zbiór:

AA =

{(x,y
):

xA 

yA }

A

2

=

Slajd

5/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Kwadrat kartezjański zbioru -

przykłady

Wyznaczyć kwadrat kartezjański zbioru:

A = { 1 }.

A

2

= {

}

(1,

1)

Slajd

6/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Kwadrat kartezjański zbioru -

przykłady

Wyznaczyć kwadrat kartezjański zbioru:

A = { 1, 2
}.

A

2

= {

}.

(1,
1),

(1,
2),

(2,
1),

(2,

2)

Slajd

7/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Relacja – definicja

formalna

Dowolny podzbiór iloczynu kartezjańskiego X
 Y nazywamy relacją i oznaczamy symbolem R.

Relacja jest zbiorem pewnych par, utworzonych
nie na zasadzie: każdy z każdym, ale najczęściej
według pewnego przepisu utożsamianego z
relacją.

R  X  Y .

Slajd

8/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

Niech

W tym wypadku relacja jest zbiorem par:

X = {0, 1}, Y = {0, 1, 2}

X  Y = {(0,0), (0,1), (0,2), (1,0),

(1,1), (1,2)}.

R = {

(0, 1), (0, 2),

(1, 2)

}

R = {(x, y)  X  Y ; x <

y }.

X  Y = {(0,0),

(0,1)

,

(0,2)

, (1,0),

(1,1),

(1,2)

}.

Slajd

9/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Relacja w zbiorze

Jeżeli R jest podzbiorem zbioru X

x

X (czyli,

gdy poprzedniki i następniki par pochodzą z
tego samego zbioru X), to mówimy, że relacja
określona jest w zbiorze X.

W ramach tego wykładu rozpatrywać będziemy
przede wszystkim relacje takiego właśnie typu.

Slajd

10/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Relacja w zbiorze

To, że elementy x i y są ze sobą w relacji
R (tworząc umowną parę) zapisywać
możemy jako:

R(x,y) – zapis najczęściej stosowany w rachunku
predykatów,

(x,y)R – taki zapis najbardziej odpowiada definicji

formalnej,

xRy – zapis taki stosowany jest najczęściej w
teorii relacji,

będziemy go też stosować w

dalszej części wykładu.

Slajd

11/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Kwantyfikatory

Kwantyfikatory to wyrażenia określające ilość
przedmiotów, o których jest mowa.

W logice mamy do czynienia z dwoma
kwantyfikatorami.

Slajd

12/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Kwantyfikator ogólny

Pierwszy z kwantyfikatorów odpowiada wyrażeniu:

Dla każdego

…

i jest oznaczany symbolem



.

Kwantyfikator ten nazywany jest też „dużym
kwantyfikatorem” lub „kwantyfikatorem ogólnym”.

Slajd

13/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Kwantyfikator szczegółowy

Drugi z kwantyfikatorów odpowiada wyrażeniu:

Istnieje

(

przynajmniej jedno

) …

i jest oznaczany symbolem



.

Kwantyfikator ten nazywany jest też „małym
kwantyfikatorem”, „kwantyfikatorem szczegółowym”
lub „kwantyfikatorem egzystencjalnym”.

Slajd

14/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Oznaczenia

kwantyfikatorów

Oznaczenia kwantyfikatorów wywodzą się z języka
angielskiego:

kwantyfikator ogólny



– odwrócona litera „A” od słowa

A

ll (wszystkie),

kwantyfikator szczegółowy



– odwrócone „E” od słowa

E

xists (istnieje).

Slajd

15/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Uwagi notacyjne

Po kwantyfikatorach znajdują się (bez nawiasów),
symbole elementów, do których dany kwantyfikator
się odnosi.

Na przykład:

x

– oznacza

dla

każdego x

,

y

– oznacza

istnieje y

.

Slajd

16/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Dziedzina relacji

W każdej relacji możemy określić:

dziedzinę lewostronną, nazywaną czasem po prostu
dziedziną,

dziedzinę prawostronną, nazywaną również
przeciwdziedziną,

pole relacji.

Slajd

17/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Dziedzina lewostronna

relacji

Dziedzina lewostronna relacji R oznaczana
symbolem D

L

(R), to zbiór takich przedmiotów, które

pozostają w relacji R do jakiegoś (przynajmniej
jednego) przedmiotu.

Symbolicznie:

D

L

(R) = {x: y (xRy)}.

Gdy relacja określona jest przez pewien warunek, to
dziedzina lewostronna jest zbiorem wszystkich
elementów stanowiących podmiot warunku
opisującego relację.

Slajd

18/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Dziedzina prawostronna

relacji

Dziedzina prawostronna (przeciwdziedzina) relacji
R oznaczana symbolem D

L

(R), to zbiór tych

przedmiotów, do których jakiś przedmiot pozostaje
w relacji R.

Symbolicznie:

D

P

(R) = {y: x (xRy)}.

Gdy relacja określona jest przez pewien warunek, to
dziedzina prawostronna jest zbiorem wszystkich
elementów stanowiących orzecznik warunku
opisującego relację.

Slajd

19/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Pole relacji

Pole relacji to suma dziedziny lewostronnej i
prawostronnej.

Symbolicznie:

P(R) = D

P

(R)  D

L

(R).

Slajd

20/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład – relacja i jej

dziedziny

P(R) =

X = { a, b, c, d }

R = { (a, a), (a, b), (c, b), (d, d) }

D

L

(R) =

D

P

(R) =

{ a, c, d }

{ a, b, d }

{ a, b, c, d }

Slajd

21/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład – relacja i jej

dziedziny

P(R) =

X = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
12 }

xRy – x jest dzielnikiem właściwym y

D

L

(R) =

D

P

(R) =

{ 2, 3, 4, 5, 6 }

{ 4, 6, 8, 9, 10, 12 }

{ 2, 3, 4, 5, 6, 8, 9, 10, 12 }

Slajd

22/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład – relacja i jej

dziedziny

P(R) –

X – zbiór ludzi

xRy – x jest żoną y

D

L

(R) –

D

P

(R) –

zbiór wszystkich
mężatek

zbiór wszystkich żonatych
mężczyzn

zbiór ludzi pozostających w związkach
małżeńskich (będących żoną lub
mających żonę).

Slajd

23/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Graf (diagram) relacji

W przypadku, gdy zbiory X i Y są skończone relację R 

X  Y można ilustrować w postaci grafu (diagramu).

Jeżeli xRy, to od x
do y prowadzimy
strzałkę.

R = { }

(a, d),

(a, e),

(b,d),

(c,e)

Slajd

24/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Graf (diagram) relacji

W szczególności w podobny sposób może być
interpretowana relacja R  X  X gdy X jest zbiorem

skończonym.

R =
{ }

(

a,

a

),

(

a,

b

),

(

b,

a

),

(

a,

c

)

Slajd

25/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład

Naszkicować diagram relacji określonej
w zbiorze:

Jeżeli xR y ( x jest
dzielnikiem y) , to od x do
y prowadzimy strzałkę).

1

5

2

3

4

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

xRy  x jest dzielnikiem y.

poprzez warunek:

Slajd

26/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Tabelka relacji

W przypadku, gdy zbiór X jest zbiorem
skończonym, relację określoną w tym zbiorze
można ilustrować za pomocą tabelki.

Jeżeli xR y (tu x | y)
, to na przecięciu
wiersza x z
kolumną y postawimy
1, w przeciwnym
razie postawimy 0.

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

xRy  x jest dzielnikiem y

x

y

1

2

3

4

5

1
2
3
4
5

Slajd

27/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Tabelka relacji

W przypadku, gdy zbiór X jest zbiorem
skończonym, relację określoną w tym zbiorze
można ilustrować za pomocą tabelki.

Jeżeli xR y (tu x | y)
, to na przecięciu
wiersza x z
kolumną y postawimy
1, w przeciwnym
razie postawimy 0.

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

xRy  x jest dzielnikiem y

x

y

1

2

3

4

5

1
2
3
4
5

1

1

1

1

1

0

1

0

1

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

1

Slajd

28/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Ćwiczenie

W zbiorze X = {1, 2 3, 4} definiujemy relację R
wzorem:.

Jeżeli xRy (czyli, gdy x + y
jest parzyste) , to na
przecięciu wiersza x z
kolumną y postawimy 1,
w przeciwnym razie
postawimy 0.

Sporządzić tabelkę tej relacji.

xRy  x + y jest liczbą

parzystą.

x

y

1

2

3

4

1
2
3
4

Slajd

29/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Ćwiczenie

W zbiorze X = {1, 2 3, 4} definiujemy relację R
wzorem:.

Jeżeli xR y (czyli, gdy x + y
jest parzyste) , to na
przecięciu wiersza x z
kolumną y postawimy 1,
w przeciwnym razie
postawimy 0.

Sporządzić tabelkę tej relacji.

xRy  x + y jest liczbą

parzystą.

x

y

1

2

3

4

1
2
3
4

1

0

1

0

0

1

0

1

1

0

1

0

0

1

0

1

Slajd

30/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Działania na relacjach

Ponieważ relacje są zbiorami (zbiorami par), możemy
wykonywać na nich działania, jakie wykonywaliśmy
na „zwykłych” zbiorach: tj. możemy obliczyć ich
sumę, iloczyn, różnicę i dopełnienie.

Slajd

31/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład

W zbiorze X = { 1, 2, 3, 4, 5, 6 } dane są relacje:

xRy  x = 2y,

xSy  x = y + 1.

Wyznaczyć:

R  S

R  S

R \ S

S \ R

R = { (2, 1), (4, 2), (6, 3)
}S = { (2, 1), (3, 2), (4, 3), (5, 4), (6, 5) }

= { (2,
1)}

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

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

= { (3, 2), (4, 3), (5, 4), (6, 5) }

Slajd

32/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład

Dane są relacje:

xRy  x jest bratem y,

xTy  x jest

rówieśnikiem y,

xSy  x jest rodzeństwem y,

xQy  x jest

siostrą y.

Wyznaczyć:

R  T

Iloczyn relacji bycia bratem i bycia rówieśnikiem
to relacja zawierająca pary należące zarówno do T
jaki i R, a zatem relacja bycia bratem
rówieśnikiem (bratem bliźniakiem) (x jest bratem
bliźniakiem y).

Slajd

33/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład

Dane są relacje:

xRy  x jest bratem y,

xTy  x jest

rówieśnikiem y,

xSy  x jest rodzeństwem y,

xQy  x jest

siostrą y.

Wyznaczyć:

S \ R

Gdy od relacji bycia rodzeństwem odejmiemy
relację bycia bratem, otrzymamy relację bycia
siostrą (x jest siostrą y).

Slajd

34/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład

Dane są relacje:

xRy  x jest bratem y,

xTy  x jest

rówieśnikiem y,

xSy  x jest rodzeństwem y,

xQy  x jest

siostrą y.

Wyznaczyć:

S  R

Dodając do relacji bycia rodzeństwem relację bycia
bratem, nie dodajemy do S w istocie niczego
nowego.

Zatem wynikiem działania jest S, czyli relacja bycia
rodzeństwem (x jest rodzeństwem y).

Slajd

35/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład

Wyznaczyć:

T

/

Dopełnienie relacji T to zbiór par, które do T nie
należą, a zatem jest to relacja bycia w innym wieku
(x jest w innym wieku niż y lub: x nie jest
rówieśnikiem y).

Dane są relacje:

xRy  x jest bratem y,

xTy  x jest

rówieśnikiem y,

xSy  x jest rodzeństwem y,

xQy  x jest

siostrą y.

Slajd

36/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład

Wyznaczyć:

Q

/

 S

Dopełnienie relacji Q, to relacja nie-bycia siostrą.

Dane są relacje:

xRy  x jest bratem y,

xTy  x jest

rówieśnikiem y,

xSy  x jest rodzeństwem y,

xQy  x jest

siostrą y.

Cześć wspólna tej relacji z relacją bycia
rodzeństwem to relacja bycia bratem (x jest bratem
y).

Slajd

37/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Konwers relacji

Konwers relacji R nazywany jest relacją
odwrotną do R i bywa oznaczany symbolicznie R

-

1.

.

Konwers relacji R, jest to relacja zachodząca
pomiędzy elementami y i x wtedy i tylko
wtedy, gdy pomiędzy x i y zachodzi R.

Symbolicznie:

yR

-1

x  xRy.

Slajd

38/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład – relacja i relacja

odwrotna

X = { a, b, c, d }

R = { (a, a), (a, b), (c, b), (d, d) }

R

-1

= { (a, a), (b, a), (b, c),

(d, d) }

P(R) =

D

L

(R) =

D

P

(R) =

{ a, c, d }

{ a, b, d }

{ a, b, c, d }

= D

P

(R

-1

)

= D

L

(R

-1

)

= P(R

-1

)

Wyznaczyć relację odwrotną. Podać zależności między
dziedzinami jednostronnymi obu relacji.

Slajd

39/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Konwers relacji –

przykłady

Konwersem relacji bycia rodzicem, jest relacja bycia

(Ponieważ

y jest dzieckiem x

wtedy i tylko wtedy, gdy

x jest rodzicem y).

dzieckiem
.

Slajd

40/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Konwers relacji –

przykłady

Konwersem relacji bycia młodszym jest relacja
bycia

starszy
m.

Slajd

41/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Konwers relacji –

przykłady

Konwersem pewnej relacji może być też czasem ta
sama relacja .

Konwersem relacji bycia w tym samym wieku jest ta
sama relacja bycia w tym samym wieku.

Slajd

42/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Graf i tabelka relacji

odwrotnej

Graf relacji odwrotnej powstaje przez odwrócenie
zwrotu wszystkich strzałek występujących w tym
grafie.

Tabelka relacji odwrotnej powstaje przez
symetryczne odbicie tabelki relacji względem
głównej przekątnej.

Slajd

43/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Uwaga

Rozpatrywane relacje dotyczą zawsze jakiegoś
konkretnego uniwersum.

Relacja posiadająca daną własność w jednym
uniwersum, może nie posiadać jej w innym.

We wzorach dotyczących relacji wyrażenia: x oraz x

powinny przybierać formę 

xX

oraz 

xX

.

Aby zbytnio wzorów nie komplikować, nie będziemy tak
jednak pisać, domyślnie przyjmując, że każdorazowo
chodzi nam jedynie o elementy z danego uniwersum.

Slajd

44/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Relacja zwrotna

Mówimy, że relacja jest zwrotna, gdy każdy
element uniwersum jest w tej relacji do siebie
samego.

Symbolicznie:

R jest zwrotna  x (xRx).

Slajd

45/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji zwrotnej

Warunek jest spełniony, ponieważ każdy człowiek
jest w takim samym wieku w stosunku do siebie
samego.

X – zbiór ludzi

xRy  x jest w tym samym wieku

co y.

R jest zwrotna  x (xRx).

Slajd

46/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji zwrotnej

X – zbiór liczb naturalnych

xRy  x jest

dzielnikiem y.

Warunek jest spełniony, ponieważ każda liczba
jest swoim własnym dzielnikiem.

R jest zwrotna  x (xRx).

Slajd

47/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Relacja przeciwzwrotna

Relacja jest przeciwzwrotna, gdy żaden element
uniwersum nie jest w relacji do siebie samego.

Symbolicznie:

R jest przeciwzwrotna  x ~ (xRx).

Slajd

48/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

przeciwzwrotnej

Warunek jest spełniony, ponieważ żaden człowiek
nie jest swoim rodzicem.

X – zbiór ludzi

xRy  x jest rodzicem y.

R jest przeciwzwrotna  x ~ (xRx).

Slajd

49/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

przeciwzwrotnej

Warunek jest spełniony, ponieważ żaden człowiek
nie jest starszy od siebie samego.

X – zbiór ludzi

xRy  x jest starszy niż y.

R jest przeciwzwrotna  x ~ (xRx).

Slajd

50/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

przeciwzwrotnej

Warunek jest spełniony, ponieważ żadna liczba
rzeczywista nie jest większa od siebie samej.

– zbiór liczb rzeczywistych

xRy  x > y.

R jest przeciwzwrotna  x ~ (xRx).

Slajd

51/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Relacja symetryczna

Mówimy, że relacja jest symetryczna, gdy jest tak,
że jeśli relacja zachodzi pomiędzy dwoma
elementami w jedną stronę, to zachodzi i w drugą
(jeśli zachodzi pomiędzy x i y, to zachodzi też
pomiędzy y i x).

Symbolicznie:

R jest symetryczna  xy (xRy  yRx).

Slajd

52/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

symetrycznej

Warunek jest spełniony.
Gdy o jednej osobie można powiedzieć, że jest tej
samej płci co druga, to o drugiej osobie w
odniesieniu do pierwszej można powiedzieć to
samo.

U– zbiór ludzi

xRy  x jest tej samej płci, co y.

R jest symetryczna  xy (xRy  yRx).

Slajd

53/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

symetrycznej

Warunek jest spełniony.
Gdy o jednej osobie można powiedzieć, że jest innej
płci niż druga, to o drugiej osobie w odniesieniu do
pierwszej można powiedzieć to samo.

X – zbiór ludzi

xRy  x jest innej samej płci, co y.

R jest symetryczna  xy (xRy  yRx).

Slajd

54/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

symetrycznej

Warunek jest spełniony.
Gdy o jednej figurze można powiedzieć, że jest
podobna do drugiej, to o drugiej figurze w
odniesieniu do pierwszej można powiedzieć to
samo.

X – zbiór figur
geometrycznych

xRy  x jest podobna do y.

R jest symetryczna  xy (xRy  yRx).

Slajd

55/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Relacja asymetryczna

Relacja jest asymetryczna (antysymetryczna,
przeciwsymetryczna), gdy jest tak, że jeśli zachodzi
w jedną stronę, to nie zachodzi w drugą.

Symbolicznie:

R jest asymetryczna  xy (xRy  ~ yRx).

Slajd

56/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

asymetrycznej

Warunek jest spełniony.
Gdy o jednej osobie można powiedzieć, że jest
ojcem drugiej, to o drugiej osobie w odniesieniu do
pierwszej nigdy nie da się już tak powiedzieć.

X – zbiór ludzi

xRy  x jest ojcem y.

R jest asymetryczna  xy (xRy  ~ yRx).

Slajd

57/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

asymetrycznej

Warunek xy (xRy  ~ yRx) jest spełniony.

Gdy o jednej osobie można powiedzieć, że jest
starsza od drugiej, to o drugiej osobie w odniesieniu
do pierwszej nigdy nie da się już tak powiedzieć.

X – zbiór ludzi

xRy  x jest starszy od y.

R jest asymetryczna  xy (xRy  ~ yRx).

Slajd

58/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

asymetrycznej

Warunek jest spełniony.
Gdy pierwsza z liczb jest większa od
drugiej, to druga od pierwszej - nie.

X – zbiór liczb naturalnych

xRy  x > y.

R jest asymetryczna  xy (xRy  ~ yRx).

Slajd

59/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Relacja przechodnia

Relacja jest przechodnia, jeśli zachodząc pomiędzy
jakimś elementem x i y, a także elementem y i
elementem z, zachodzi również pomiędzy x i z.

Symbolicznie:

R jest przechodnia  xyz [(xRy  yRz)  xRz].

Slajd

60/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

przechodniej

Warunek jest spełniony.

Jeśli jedna osoba jest starsza od drugiej, a druga od
trzeciej, to na pewno pierwsza jest również starsza
od trzeciej.

X – zbiór ludzi

xRy  x jest starszy niż y.

R jest przechodnia  xyz [(xRy  yRz)  xRz].

Slajd

61/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji

przechodniej

Warunek jest spełniony.

Jeśli pierwsza liczba jest dzielnikiem drugiej, a druga
jest dzielnikiem trzeciej, to na pewno pierwsza jest
również dzielnikiem trzeciej.

X – zbiór liczb naturalnych

xRy  x jest dzielnikiem y.

R jest przechodnia  xyz [(xRy  yRz)  xRz].

Slajd

62/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Relacja spójna

Relacja jest spójna, jeśli dla dowolnych dwóch
różnych elementów uniwersum zachodzi ona
przynajmniej w jedną stronę, czyli x jest w relacji do
y lub y do x.

Symbolicznie:

R jest spójna  xy [x



 y  (xRy  yRx)].

Slajd

63/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Przykład relacji spójnej

Warunek jest spełniony.

Jeśli weźmiemy dwie różne liczby, to na pewno jedna
będzie mniejsza od drugiej albo druga od pierwszej.

X – zbiór liczb

xRy  x < y.

R jest spójna  xy [x



 y  (xRy  yRx)].

Slajd

64/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Studenckie przechwałki

W akademickiej stołówce rozmawia trzech
studentów:

- Ja Sylwestra spędziłem na Kanarach, mówię
wam, super laseczki, kąpiel w morzu, drinki z
parasolkami, cudo - zagaja pierwszy.

- A ja - przechwala się drugi - byłem w Alpach.
Narty, dziewczyny zarumienione od
mrozu, grzane wino do łóżka, coś wspaniałego.

- A co ty robiłeś? - pytają trzeciego.

- A ja siedziałem razem z wami w pokoju, tylko
nie paliłem tego świństwa!

Slajd

65/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.

Studenckie problemy

Student weterynarii „pływał” na egzaminie.

W końcu dostał Pytanie Ostatniej Szansy:

- "Czy krowie można zrobić aborcję?"

Niestety, nie wiedział, więc wyleciał z dwóją.

Zmartwiony poszedł do baru, usiadł w kącie i
powoli upija się na smutno rozmyślając o
pytaniu.

- Nie mam pojęcia, ale coś mi się widzi, że
nieźle sobie pan życie skomplikował...

Barman co jakiś czas na niego zerka, w końcu
podchodzi i zagaduje:

- Coś niewyraźnie Pan wygląda, jakieś kłopoty?

- Niech mi pan powie, czy krowie można zrobić
aborcję?

Slajd

66/66

T.Kowalski- Logika – wykład 5: Elementy teorii relacji. Własności relacji.