LOGIKA
wykład 7
XI. Teoria relacji
LOGIKA
wykład 7
XI. Teoria relacji
XI. Teoria relacji
Zbiory są wyznaczone przez zestaw należących do nich elementów, a
nie przez jakiekolwiek ich uporządkowanie. Zatem kolejność wypisania
elementów określonego zbioru jest nieistotna. W szczególności zbiory
dwuelementowe
{
a
, b
}
oraz
{b
, a
}
są identyczne.
Zbiory dwuelementowe nazywane są parami nieuporządkowanymi.
Jeżeli chcemy posłużyć się pojęciem pary rozumianej nie tylko jako
pewien dobór dwóch elementów, ale również jako określony porządek
tych elementów, to pojęcie pary nieuporządkowanej nie jest
odpowiednie do tego celu.
W teorii mnogości istnieje jednak możliwość zdefiniowania pojęcia pary
uporządkowanej, czyli takiego zestawu dwóch elementów, w którym
jeden element jest wyróżniony jako pierwszy.
XI.1 Iloczyn kartezjański zbiorów
Na oznaczenie tak rozumianej pary uporządkowanej używa się symbolu:
(
a
,
b
). Para
(
b
,
a
)
stanowi inny sposób uporządkowania niż para
(
a
,
b
),
wobec czego są to różne pary, czyli
(
a
,
b
) (
b
,
a
)
(o ile
a b
).
Parę uporządkowaną można zdefiniować przy pomocy pojęcia zbioru
w następujący sposób:
(
a
,
b
) = {
{
a
,
b
}
, a
}
.
Prawa strona tej równości spełnia wymóg stawiany wobec pojęcia pary
uporządkowanej, określa bowiem żądaną parę elementów
a
i
b
oraz
wskazuje na
a
jako element pierwszy.
Definicja ta czyni zadość wymogom:
•
(
a
,
b
) (
b
,
a
)
, ponieważ: {
{
a
,
b
}
,
a
} {
{
b
,
a
}
,
b
} (dla
a b
),
•
(
a
,
b
) = (
c
,
d
)
wtedy i tylko wtedy, gdy
a = c
i
b = d
.
Posługując się pojęciem pary uporządkowanej, można zdefiniować
kolejną operację na zbiorach, zwaną iloczynem kartezjańskim zbiorów
A
i
B
(symbolicznie ).
Iloczynem kartezjańskim nazywamy zbiór par uporządkowa-
nych, których pierwszy element należy do zbioru
A, a drugi do zbioru
B.
B
A
B
A
Symbolicznie:
inaczej:
Na przykład:
Zauważmy, że iloczyn kartezjański n
-
elementowego zbioru
A
i
m
-
elementowego zbioru
B
jest zbiorem
n
.
m
-
elementowym.
}
)
,
3
(
),
,
2
(
),
,
1
(
),
,
3
(
),
,
2
(
),
,
1
(
{
}
,
{
}
3
,
2
,
1
{
b
b
b
a
a
a
b
a
}
)
3
,
(
),
3
,
(
),
2
,
(
),
2
,
(
),
1
,
(
),
1
,
(
{
}
3
,
2
,
1
{
}
,
{
b
a
b
a
b
a
b
a
}
:
)
,
(
{
B
y
A
x
y
x
B
A
B
y
A
x
B
A
y
x
)
,
(
B
A
Iloczyn kartezjański nazywamy kwadratem kartezjańskim
zbioru
A
i oznaczamy symbolem
A
2
.
Zgodnie z tą definicją
A
2
jest zbiorem wszystkich par uporządkowa-
nych, których obydwa elementy należą do zbioru
A.
Przykładowo:
Kwadrat kartezjański zbioru
n
-
elementowego jest zbiorem
n
2
-
elemen-
towym. Jego elementami są wszystkie możliwe pary uporządkowane,
dające się utworzyć z elementów zbioru A.
A
A
2
}
,
,
{
c
b
a
}
)
,
(
),
,
(
),
,
(
),
,
(
),
,
(
),
,
(
),
,
(
),
,
(
),
,
(
{
c
c
b
c
a
c
c
b
b
b
a
b
c
a
b
a
a
a
Za pomocą pojęcia iloczynu kartezjańskiego można w języku teorii
mnogości określić pojęcie relacji dwuczłonowej. W języku potocznym
czy też w różnych naukach termin relacja jest używany do określenia
rozmaitych związków czy też zależności między obiektami.
Przykładami relacji są związki:
... jest ojcem ...
– relacja ojcostwa,
... jest większy od ...
– relacja większości,
... jest przełożonym ...
– relacja bycia przełożonym,
... jest prostopadła do ...
– relacja prostopadłości,
... jest podobny do ...
– relacja podobieństwa,
... jest podzielne przez ...
– relacja podzielności,
... jest rówieśnikiem ...
– relacja rówieśnictwa,
... jest sąsiadem ...
– relacja sąsiedztwa
itp.
XI.2 Teoria relacji
Obecnie zilustrujemy możliwość przedstawienia tak rozumianych relacji
w języku teorii mnogości na przykładzie relacji ojcostwa, określonej w
wybranym zbiorze osób.
Niech
A
będzie zbiorem osób stanowiących pewną dwupokoleniową
rodzinę:
A
=
{ Jan, Zofia, Stefan, Maria, Anna, Bogdan, Łukasz, Dariusz, Ewa },
o strukturze więzi rodzinnych odzwierciedlonych za pomocą następują-
cego drzewa genealogicznego:
Jan Zofia (
żona Jana
)
Stefan Maria (
żona Stefana
)
Anna Bogdan (
mąż Anny
)
(
bezdzietni
)
Łukasz Dariusz Ewa
Pary osób pozostających w relacji ojcostwa w tej rodzinie mogą być
symbolizowane przy pomocy par uporządkowanych postaci
(x, y
), gdzie
x
reprezentuje imię osoby będącej ojcem, zaś
y – imię osoby, której
ojcem jest
x.
Relacja ojcostwa w zbiorze
A
jest określona wyczerpująco poprzez
podanie wszystkich par
(x, y
)
takich, że
x, y A oraz, że
x
jest ojcem
y.
Inaczej mówiąc, relacja ta jest identyczna z następującym zbiorem par
uporządkowanych:
{(Jan, Stefan), (Jan, Anna), (Bogdan, Łukasz),
(Bogdan, Dariusz), (Bogdan, Ewa)}.
Zatem relacja ojcostwa, określona w zbiorze
A, to następujący zbiór:
będący (jak łatwo spostrzec) podzbiorem kwadratu kartezjańskiego
A
2
.
,
}
ojcem
jest
,
:
)
,
(
{
y
x
A
y
x
y
x
Odnotujmy, że w rozważonym przykładzie zarówno pierwsze, jak i
drugie elementy par uporządkowanych brane były z jednego zbioru.
W wielu jednak sytuacjach bywa tak, że pierwsze elementy par
pochodzą z jednego zbioru, a drugie – z zupełnie innego zbioru.
Rozważmy przykładowo zbiory
A
=
{
2, 3, 4, 5
} i
B
=
{
10, 11, 12, 13,
14, 15
} oraz relację podzielności liczb ze zbioru
B
przez liczby ze
zbioru
A.
Wówczas relację tworzy następujący zbiór par uporządkowanych:
{
(
2, 10
), (
2, 12
), (
2, 14
), (
3, 12
), (
3, 15
), (
4, 12
), (
5, 10
), (
5, 15
)
}
,
który, jak widać, jest podzbiorem iloczynu kartezjańskiego
.
B
A
Analizowane przykłady relacji prowadzą do ścisłej definicji pojęcia
relacji.
Dla dowolnych dwu zbiorów
A
i
B
relacją (relacją dwuargumentową,
lub relacją dwuczłonową) w iloczynie kartezjańskim nazywamy
dowolny podzbiór tego iloczynu.
Zatem
R
jest relacją w wtedy i tylko wtedy, gdy
Fakt, że: , zapisujemy jako: i czytamy:
„element
x
jest w relacji
R
z elementem
y”.
B
A
R
)
,
(
y
x
y
xR
B
A
.
B
A
R
Jeżeli relacja
R
jest podzbiorem kwadratu kartezjańskiego
A
2
, tzn.
a
A
2
(przypadek
A = B
), to dla prostoty mówimy, że relacja
R
jest
określona w (na) zbiorze
A.
Dla dowolnej relacji lewe człony par uporządkowanych,
należących do tej relacji, nazywamy poprzednikami tej relacji, a prawe
– następnikami.
Z kolei zbiór wszystkich poprzedników nazywany jest dziedziną relacji
( ), zaś zbiór wszystkich następników – przeciwdziedziną relacji
(
).
R
B
A
R
)
(R
D
)
(R
D
Symbolicznie dziedzinę i przeciwdziedzinę można określić następująco:
Warto także odnotować natychmiastowe spostrzeżenie, że:
W przypadku relacji będącej podzbiorem kwadratu kartezjańskiego
( ) definiuje się dodatkowo pole relacji ( ) jako sumę
dziedziny i przeciwdziedziny, czyli:
}
:
{
)
(
y
x
A
x
D
B
y
R
R
}
:
{
)
(
y
x
B
y
D
A
x
R
R
B
D
A
D
)
(
,
)
(
R
R
2
A
R
)
(R
P
.
)
(
)
(
)
(
R
R
R
D
D
P
Na przykład dziedziną relacji bycia ojcem określonej w zbiorze wszystkich ludzi jest
zbiór wszystkich ojców, jej przeciwdziedziną jest zbiór wszystkich ludzi, gdyż każdy
człowiek posiada ojca (żyjącego lub nieżyjącego, znanego lub nieznanego), zaś polem
tej relacji jest także zbiór wszystkich ludzi.
Dziedziną relacji bycia żoną jest zbiór wszystkich mężatek, przeciwdziedziną – zbiór
wszystkich żonatych mężczyzn, a polem – zbiór wszystkich osób będących w stanie
małżeńskim.
Dziedziną relacji mniejszości określonej w zbiorze
A = {
0,
1,
2,
3,
4,
5
}
jest zbiór
{
0,
1
1,
2,
3,
4
}, przeciwdziedziną zbiór
{
1,
2,
3,
4,
5
}, zaś polem zbiór
A.
Dziedziną, przeciwdziedziną i polem relacji prostopadłości prostych określonej w
zbiorze
A
wszystkich prostych leżących na danej płaszczyźnie jest ten sam zbiór
A.
Relacją odwrotną do danej relacji
(konwersem relacji
R
)
nazywamy taką relację , która zachodzi między
x
i
y
wtedy i
tylko wtedy, gdy relacja
R
zachodzi między
y
i
x
(
w odwrotnej kolejności
).
Symbolicznie:
Na przykład konwersem relacji bycia bogatszym jest relacja bycia biedniejszym,
konwersem relacji bycia podwładnym jest relacja bycia zwierzchnikiem, konwersem
relacji rówieśnictwa jest ta sama relacja rówieśnictwa itp.
B
A
R
A
B
R
)
)
,
(
)
,
(
(
R
R
R
R
x
y
y
x
x
y
y
x
)
(
)
(
)
(
)
(
R
R
R
R
R
R
D
D
D
D
Złożeniem (superpozycją) relacji nazywa się
taką relację , która zachodzi między elementami
x
i
y
wtedy i tylko wtedy, gdy istnieje takie
z, że między
x
i
z
zachodzi
relacja
R
, a między
z
i
y
relacja
S
.
Symbolicznie:
Przykładowo superpozycją relacji bycia mężem i relacji bycia córką jest relacja bycia
zięciem, gdyż mężczyzna
x
jest zięciem osoby
y
wtedy i tylko wtedy, gdy pewna
kobieta jest żoną
x-a i córką
y-ka.
Natomiast relacja bycia dziadkiem jest superpozycją relacji bycia ojcem i relacji bycia
rodzicem, gdyż
x
jest dziadkiem
y
wtedy i tylko wtedy, gdy istnieje ktoś, kogo
x
jest
ojcem a
y
dzieckiem.
C
B
B
A
S
R
i
C
A
R
S
T
S
R
R
S
)
,
(
)
,
(
)
,
(
y
z
z
x
y
x
B
z
Dotychczas rozważane własności relacji i operacje na nich wykonywane
są dość ogólne, siłą rzeczy pojęcie relacji nie zawsze w pełni przystaje
do opisywanej rzeczywistości. Aby wobec tego tworzyć bardziej
specyficzne i „szczegółowe” relacje, dołącza się kolejne, dodatkowe
warunki do definicji.
Jednym z możliwych podejść zasadza się na spostrzeżeniu i
wykorzystanie specyfiki relacji określonych nie w dowolnym iloczynie
kartezjańskim, a w kwadracie kartezjańskim jednego zbioru.
W tym podejściu pojawiają się m.in. relacje o pewnych formalnych własnościach
(zwrotność, symetryczność, antysymetryczność, przechodniość, spójność i inne).
Najważniejszymi typami relacji posiadającymi po kilka powyższych własności są
równoważności i porządki.
Niech dany będzie dowolny zbiór
A
oraz relacja
R
w tym zbiorze, czyli
.
Relacja
R
jest zwrotna w zbiorze
A
wtedy i tylko wtedy, gdy dowolny
element zbioru
A
pozostaje w tej relacji sam ze sobą.
Symbolicznie:
Zwrotnymi są np. takie relacje jak: równość liczb, rówieśnictwo, równoległość
prostych, podobieństwo figur, niewiększość liczb (
≤
), inkluzja zbiorów, należenie do
tej samej partii politycznej itp.
XI.3 Równoważności i porządki
2
A
R
x
x
A
x
R
Relacja
R
jest symetryczna w zbiorze
A
wtedy i tylko wtedy, gdy
zachodząc między elementami
x
i
y
zachodzi też między
y
i
x.
Symbolicznie:
Przykłady: równość liczb, rówieśnictwo, podobieństwo figur, prostopadłość prostych,
równoległość prostych, relacja krzyżowania się zbiorów, relacja rozłączności zbiorów,
sąsiedztwo, brak pokrewieństwa między ludźmi, wykonywanie tego samego zawodu
itp.
Relacja
R
jest antysymetryczna w zbiorze
A
wtedy i tylko wtedy, gdy
jeżeli zachodzi między elementami
x
i
y
oraz
y
i
x
ze zbioru
A, to
x
jest identyczne z y.
y
x
y
x
A
y
A
x
R
R
Symbolicznie:
Przykłady: relacja niewiększości dla liczb (
≤
), relacja niemniejszości dla liczb (
≥
),
relacja inkluzji zbiorów.
Relacja
R
jest asymetryczna w zbiorze
A
wtedy i tylko wtedy, gdy nie
zachodzi między żadnymi elementami
y
i
x, o ile zachodzi między
x
i
y.
Symbolicznie:
Przykłady: starszeństwo, ojcostwo, bycie dziadkiem, bycie żoną, bycie wyższym,
bycie podzbiorem właściwym, bycie dwukrotnością w zbiorze liczb różnych od zera
itp.
y
x
x
y
y
x
A
y
A
x
R
R
x
y
y
x
A
y
A
x
R
R
)
)
,
(
)
,
(
(
R
R
y
x
y
x
A
y
A
x
Relacja
R
jest przechodnia w zbiorze
A
wtedy i tylko wtedy, gdy
zachodząc między elementami
x
i
y
oraz
y
i
z
ze zbioru
A
zachodzi
także między
x
i
z.
Symbolicznie:
Przykłady: równoległość prostych, podobieństwo figur, rówieśnictwo, podzielność
liczb, inkluzja, starszeństwo, bycie niższym, relacja wynikania logicznego miedzy
zdaniami.
Relacja R jest spójna w zbiorze A wtedy i tylko wtedy, gdy zachodzi
między dowolnymi dwoma różnymi elementami tego zbioru.
Symbolicznie:
z
x
z
y
y
x
A
z
A
y
A
x
R
R
R
x
y
y
x
y
x
A
y
A
x
R
R
Przykłady: większość liczb, mniejszość liczb, bycie wcześniejszym dla momentów
czasowych, leżenie na lewo od ... między punktami na prostej, leżenie na prawo od ...
między punktami prostej.
Za pomocą tak określonych własności relacji dwuargumentowych
można zdefiniować pewne rodzaje relacji odgrywających szczególnie
ważną rolę w poznaniu teoretycznym.
Należą do nich relacje równoważnościowe (równoważności) oraz
relacje porządkujące (porządki).
R Ó W N O W A Ż N O Ś C I
Mówimy, że relacja
R
jest równoważnościowa w zbiorze
A
wtedy
i tylko wtedy, gdy jest zwrotna, symetryczna i przechodnia w tym
zbiorze.
Przykładami relacji równoważnościowych są: równoległość prostych, podobieństwo
figur, rówieśnictwo, relacja bycia jednakowo wysokim, relacja równoliczności zbiorów
(
posiadanie takiej samej liczby elementów
) i ogólnie każda relacja bycia takim samym pod
pewnym względem.
Jeżeli
R
jest równoważnością określoną w zbiorze
A, to dla dowolnego
elementu
a
A
można utworzyć zbiór wszystkich elementów zbioru
A,
które pozostają w relacji
R
z elementem
a.
Taki zbiór nazywany jest klasą abstrakcji relacji
R
w zbiorze
A
wyznaczoną przez element
a
i oznaczany przez
[a]
R,A
, lub
[a].
Symbolicznie:
Dla ustalonej klasy abstrakcji
[a]
R,A
dowolny element
x
zbioru
A
taki,
że nazywany jest reprezentantem klasy
[a]
R,A
.
W szczególności także i
a
jest reprezentantem klasy
[a]
R,A
.
Wprost z definicji równoważności oraz z definicji klasy abstrakcji
wynikają następujące własności:
}
:
{
]
[
,
x
a
A
x
a
A
R
R
A
a
x
,
]
[
R
1.
2.
3.
Jeżeli to
czyli każde dwie różne klasy abstrakcji relacji równoważnościowej są rozłączne
4.
czyli wszystkie klasy abstrakcji są zbiorami niepustymi
5.
Suma wszystkich klas abstrakcji relacji równoważnościowej
R
w
zbiorze
A
jest równa
A.
y
x
y
x
A
A
R
R
R
,
,
]
[
]
[
A
A
a
a
a
,
]
[
R
,
]
[
]
[
,
,
A
A
y
x
R
R
.
]
[
]
[
,
,
A
A
y
x
R
R
A
A
a
a
,
]
[
R
W związku z tym, iż równoważność, określona w danym zbiorze
A,
wyznacza zbiór niepustych, rozłącznych między sobą oraz dających w
sumie cały zbiór
A
podzbiorów
A
(klas abstrakcji), to mówimy, że
dokonuje ona podziału logicznego zbioru
A.
Przykłady
a.
Relacja podobieństwa trójkątów dokonuje podziału wszystkich trójkątów w taki
sposób, że do jednego podzbioru (klasy abstrakcji) należą wszystkie te i tylko te
trójkąty, które mają identyczny kształt. Każdemu trójkątowi określonemu układem
miar kątów odpowiada jedna klasa abstrakcji. Możemy powiedzieć, że abstraktem od
relacji podobieństwa trójkątów jest ich kształt.
b.
Analogicznie abstraktem relacji równoległości prostych jest kierunek (do jednej klasy
abstrakcji tej relacji należą proste o tym samym kierunku).
c.
Relacja rówieśnictwa dokonuje podziału zbioru ludzi na grupy ludzi w tym samym
wieku. Jej abstraktem jest kategoria wieku.
P O R Z Ą D K I
Mówimy, że relacja
R
jest (częściowym) porządkiem w zbiorze
A
wtedy i tylko wtedy, gdy jest w tym zbiorze zwrotna, antysymetryczna i
przechodnia. Mówi się wówczas także, że relacja
R
porządkuje zbiór
A
.
Z kolei parę (
A,
R
) nazywa się zbiorem (częściowo) uporządkowanym.
Przykłady
A.
Ustalony zbiór ludzi o różnym wzroście jest uporządkowany relacją niewyższości.
B.
Relacje niewiększości (
≤
) oraz niemniejszości (
≥
) porządkują ustalony zbiór liczbowy.
C.
Relacja podzielności liczb porządkuje dowolnie ustalony zbiór liczbowy.
Rozważmy pewien szczególny przypadek tego typu. Mianowicie niech dany będzie
zbiór dzielników naturalnych liczby 30, czyli
{
1
, 2
, 3
, 5
, 6
, 10
, 15
, 30
}
wraz z
relacją podzielności | . Łatwo sprawdzić, że rzeczywiście jest to zbiór uporządkowany.
Dla tego zbioru można w bardzo prosty sposób narysować diagram porządku | :
30
6
10
15
2
3
5
1
Ostatni przykład dobrze ilustruje tak istotę pojęcia porządku, jak i fakt, że porządki
nazywane są częściowymi porządkami. Zauważmy bowiem, że ani , ani
a
(czyli, że częściowe porządki nie są spójne).
Warto jeszcze odnotować, że w przypadku skończonego zbioru
uporządkowanego nie tylko można narysować jego diagram, ale i
odwrotnie – diagram skończony w jednoznaczny sposób określa pewien
zbiór uporządkowany.
10
|
6
6
|
10
P O R Z Ą D K I L I N I O W E
Mówimy, że relacja
R
jest porządkiem liniowym w zbiorze
A
wtedy i
tylko wtedy, gdy jest w tym zbiorze asymetryczna, przechodnia i spójna.
Porządek liniowy pozwala na pełne „uszeregowanie” wszystkich
elementów porządkowanego zbioru.
Przykładami relacji porządku liniowego są: relacja mniejszości liczb (
<
), relacja
większości liczb (
>
), relacja bycia wcześniejszym dla momentów czasowych itp.
Ale dla odmiany relacja podzielności liczb nie jest porządkiem liniowym w zbiorze
liczb naturalnych.
Dziękuję za uwagę!