LOGIKA I METODOLOGIA NAUK #6
Elementy teorii relacji
Relacje są zawsze zbiorami, obiektami abstrakcyjnymi.
x kocha y-a
Ważna jest kolejność!
Relacja to zbiór par (możemy mówić o konkretnej parze).
Relacje - zbiory dystrybutywne, w środku są pary uporządkowane a obiekty są abstraktami
Pojęcia umożliwiające zdefiniowanie relacji:
- para (n-tka) uporządkowana x ≠ y <x,y> ≠ <y,x>
- iloczyn kartezjański
Symbol - …x…
X x Y = {<x,y>: x
X
y
Y}
Przykłady:
{a,b,c} x {b,d} = {<a,b>, <a,d>, <b,b>, <b,d> <c,b>, <c,d>}
L={ x: x jest człowiekiem} Mamy: LxL = {<x,y>: x,y
L}
*Pojęcie pary uporządkowanej można rozszerzyć na pojęcie n-tki uporządkowanej.
<x1, x2, …, xn>
a b para
do iloczynu kartezjańskiego
Relacja: x bezpośrednio poprzedza y w alfabecie języka polskiego.
Rozważana relacja poprzedzania jest następującym zbiorem: {<a,b>, <c,d>}
Każda relacja jest podzbiorem określonego iloczynu kartezjańskiego.
Definicja
R jest relacją 2-argumentową w zbiorze x wtedy, gdy ∃y1, ∃y2 (Y1, Y2 x oraz R Y1 x Y2)
{ } x { } = { < , >}
{ , } { < , >}
Ø {< , >}
Dziedzina (lewa dziedzina) relacji R:
Dl (R) = {x: ∃y x Ry}
Przeciwdziedzina (prawa dziedzina) relacji R:
Dp (R) = {y: ∃x x Ry}
Pole relacji
P (R) = Dl (R)
Dp (R)
Przykłady:
{a,c,e}, {b,d}
R = {<a,b>, <c,d>} Mamy:
Dl (R) = {a,c}
Dp (R) = {b,d}
P (R) = {a,c}
{b,d} = {a,b,c,d}
Zbiory: M = mężczyźni, L = ludzie, relacja: x jest synem y-a:
S = {<y>
M x L: x jest synem y-a} Mamy:
Dl (S) = M
Dp (S) =ludzie mający syna
P (S) = M
ludzie mający syna
Relacje można odwracać (konwers relacji)
R -1 (zbiór par, tylko odwrotnych)
R -1 = {<y,x>: x Ry}
Przykłady:
R = {<a,b>, <c,d>}
R -1 = {<b,a>, <d,c>}
S = { <x,y>
M x L: x jest synem y-a}
S -1 = {<x>
L x M: y jest matką lub ojcem mężczyzny}
W = relacja bycia zwierzchnikiem
W -1 = relacja bycia podwładnym
W = {a,b,c}
W x W = {<a,a>, <a,b>, <a,c>, <b,a>, <b,c>, <c,a>, <c,b>, <c,c>}
X jest starszy od y-a
S(W) = {<x,y>: x jest starszy od y-a} = {<b,a>, <c,b>, <c,a>}
Dl (S) = {b,c}
Dp (S) = {a,b}
P (S) {b,c}
{a,b} = {a,b,c}
Id (W) = {<a,a>, <b,b>, <c,c>}
Dl (Id) = {a,b,c} = Dp (Id) = P (Id)
S
Id = {<b,a>, <c,b>, <c,a>, <a,a>, <b,b>, <c,c>}
relacja macierzyństwa w zbiorze ludzi
relacja ojcostwa w zbiorze ludzi
x jest uczniem y-a
x jest nauczycielem y -a
S
Id = Ø
Dl (S) = Ø
Dp (S) = Ø
P (S) = Ø
S - Id = S
-S = {<a,a>, <a,b>, <b,b>, <b,c>, <c,c>}
konwers relacji S
S-1 (W) = {<a,b>, <b,c>, <a,c>}
Konwers i dopełnienie to coś różnego!
Relacje można „składać” - otrzymujemy iloczyny względne - symboliczne R ; S
R ; S = {<x,y>: ∃z (x Rz
zSy)}
Np.:
R = relacja bycia ojcem
R ; R = relacja bycia dziadkiem ze strony ojca
R = relacja bycia terapeutą
S = relacja bycia ofiarą (przemocy)
R ; S = relacja bycia terapeutą ofiary (przemocy)
L
Ar P
<K,J>
<M,J>
<J,M>
<K,M>
<Ar,P>
a
b
c
e
d
a
b
c
d
e
L
K
M
P
J
M
A
a
b
c
a
b
c
a
b
c