M5.pdf
(
516 KB
)
Pobierz
5_logika.indd
Relacje równoważności
i relacje częściowo porządkujące
Wstęp
2
1. Relacje równoważności
3
2. Podział zbioru
8
3. Relacje częściowo porządkujące
10
4. Elementy wyróżnione w zbiorach częściowo uporządkowanych
14
5. Elementy teorii krat i algebr Boole’a
19
Bibliografia
23
Wstęp
Relacja równoważności i związane z nią pojęcie podziału zbioru są pojęciami
wykorzystywanymi (świadomie lub nie) w wielu naukach. Mało kto wie, że dzieci we
wczesnych klasach szkoły podstawowej uczą się o liczbach, wykorzystując te pojęcia.
Umożliwiany przez relację równoważności podział danego zbioru pozwala rozważać
nie wszystkie jego elementy, ale pewne podzbiory (których liczba jest zazwyczaj
znacznie mniejsza od liczby wszystkich elementów). W informatyce pojęcia relacji
równoważności i podziału zbioru są między innymi podstawowymi narzędziami
pracy przy formalnym opisie i weryfikacji własności systemów oprogramowania.
Relacje częściowego porządku określone na danym zbiorze — również z punktu
widzenia informatyki — odgrywają bardzo istotną rolę. Podstawowe struktury
danych, takie jak drzewa, kolejki czy stosy, utożsamiać możemy z odpowiednimi
strukturami częściowo uporządkowanymi. Częstym zadaniem programistycznym
jest znalezienie w danej strukturze danych elementu minimalnego (w jakimś sensie),
największego itp. Dobrym przykładem jest odnalezienie w bazie danych firmy
pracownika otrzymującego najniższe (lub najwyższe) wynagrodzenie. Formalny opis
działania pewnych systemów oprogramowania może być również przeprowadzany
w oparciu o wyżej wspomniane struktury.
Algebra Boole’a jest bardzo ważną strukturą matematyczną, stosowaną do opisu
wielu istotnych pojęć w różnych dziedzinach matematyki i logiki (również
matematycznej). Algebrę tę można definiować dwojako. Jednym ze sposobów jest
definicja poprzez teorię krat — w tym przypadku algebra Boole’a definiowana jest
jako dystrybutywna (rozdzielna) krata z zerem i jedynką, w której każdy element
posiada uzupełnienie. Kluczowym pojęciem jest tutaj relacja częściowego porządku.
Innym podejściem jest aksjomatyczna definicja algebraiczna, według której algebra
Boole’a jest pewnym specyficznym typem algebry definiowanym równościowo
(przez określoną liczbę aksjomatów równościowych). Kluczowymi pojęciami są tu
odpowiednio zdefiniowane działania.
2
1. Relacje
równoważności
Rozważmy relację określoną na elementach niepustego zbioru
A
(δ
⊆
A
×
A
). Powiemy,
że relacja δ (δ
⊆
A
×
A
) jest
relacją (typu) równoważności
, jeżeli jest:
(a) zwrotna: ∀
x
∈
A
(
x
δ
x
),
(b) symetryczna: ∀
x,y
∈
A
(
x
δ
y
⇒
y
δ
x
),
(c) przechodnia: ∀
x,y,z
∈
A
[(
x
δ
y
∧
y
δ z) ⇒
x
δ
z
].
Przykład 1
Oznaczmy przez
A
zbiór wszystkich rzeczy materialnych, których kolor jest możliwy
do określenia (sposób rozumienia tego zbioru pozostawiamy jako dowolny).
Rozważmy następującą relację δ określoną na tym zbiorze:
Dla dwóch dowolnych elementów
x
,
y
należących do zbioru
A
, powiemy, że
x
jest
w relacji z elementem
y
(czyli inaczej
x
δ
y
) wtedy i tylko wtedy, gdy element
x
jest
tego samego koloru, co element
y
.
Łatwo można zauważyć, że relacja δ jest zwrotna, symetryczna i przechodnia, zatem
jest relacją równoważności.
Dowód
(a)
zwrotność:
∀
x
∈
A
(
x
δ
x
)
Zauważmy, że jeżeli weźmiemy dowolny element
x
∈
A
(dowolną rzecz
materialną), to jest on tego samego koloru, co on sam (czyli
x
δ
x
).
(b)
symetria:
∀
x,y
∈
A
(
x
δ
y
⇒
y
δ
x
)
Zauważmy, że jeżeli weźmiemy dwa dowolne elementy
x
,
y
∈
A
(dowolne dwie
rzeczy materialne), to jeżeli prawdą jest, że
x
jest tego samego koloru, co
y
, to
również można powiedzieć, że
y
jest tego samego koloru, co
x
.
(c)
przechodniość:
∀
x,y,z
∈
A
[(
x
δ
y
∧
y
δ
z
) ⇒
x
δ
z
]
Zauważmy, że jeżeli weźmiemy trzy dowolne elementy
x
,
y, z
∈
A
, to
jeżeli
x
jest tego samego koloru, co
y
oraz
y
jest tego samego koloru, co
z
, to również prawdą jest to, że
x
jest tego samego koloru, co
z
.
Przykład 2
Rozważmy zbiór pięcioelementowy
A
= {
a
,
b
,
c
,
d
,
e
} i określoną na nim
relację δ (δ ⊆
A
×
A
) daną poniższym grafem (rysunek 1).
Zauważmy, że relacja ta jest relacją równoważności, jest bowiem zwrotna,
symetryczna i przechodnia.
Rysunek 1
3
Twierdzenie 1
Jeżeli na zbiorze
A
określona jest relacja równoważności δ (δ ⊆
A
×
A
), to dzieli ona
zbiór
A
(„rozcina” zbiór
A
) na podzbiory, spełniające następujące własności:
(a)
żaden z nich nie jest pusty,
(b)
są one parami rozłączne (żadne dwa różne podzbiory nie mają punktów
wspólnych),
(c)
suma wszystkich takich podzbiorów daje cały zbiór
A
.
Podzbiory te nazywamy
klasami abstrakcji
.
Każda z tych klas jest wyznaczana (generowana) przez pewien element
zbioru
A
. Do klasy wyznaczonej przez dowolny element
a
∈
A
(element ten
nazywamy
generatorem
klasy) należą wszystkie i tylko takie elementy ze zbioru
A
,
które pozostają w relacji δ z generatorem
a
.
Formalnie:
[
a
]
δ
=
df.
{
x
∈
A
:
x
δ
a
}.
Wprost z powyższej definicji otrzymujemy:
x
∈ [
a
]
δ
⇔
x
δ
a
.
Uwaga:
Dowolny element zbioru generuje pewną (wyznaczoną przez ten element)
klasę abstrakcji.
Zbiór wszystkich klas abstrakcji wyznaczonych w zbiorze
A
przez relację
równoważności δ nazywamy
zbiorem ilorazowym
zbioru
A
względem relacji δ
i oznaczamy symbolem .
A
δ
Przykład 3
Ponieważ opisana w
przykładzie 1
relacja δ jest relacją równoważności, to — zgodnie
z powyższymi uwagami — powinna ona dzielić zbiór
A
na klasy abstrakcji (podzbiory
mające wypisane wyżej własności). Aby przekonać się, czym są te klasy, wyznaczymy
kilka z nich. Przypomnijmy, że w celu wyznaczenia dowolnej klasy potrzebny jest
jej generator, czyli dowolny element danego zbioru. Weźmy jako generator klasy
liść brzozy (zakładamy, że jest to letni liść brzozy, ma zatem kolor zielony). Zgodnie
z definicją klas abstrakcji liść ten generuje klasę (zbiór) wszystkich takich elementów
zbioru
A
(rzeczy materialnych), które są w relacji δ z tym liściem. Do klasy tej należą
zatem te i tylko te rzeczy materialne, które są tego samego koloru, co liść (patrz
definicja relacji δ). Mamy zatem:
[zielony liść brzozy]
δ
= {zbiór rzeczy materialnych o kolorze zielonym}.
Podobnie łatwo zauważyć, że np. płatek maku polnego generuje klasę rzeczy
materialnych o kolorze czerwonym, standardowa opona samochodowa generuje
klasę rzeczy o kolorze czarnym, śnieg — białym itp.
Zauważmy, że zbiór rzeczy materialnych został podzielony na podzbiory ze względu
na kolor tych rzeczy. Zauważmy również, że żaden z tych podzbiorów nie jest pusty,
są one parami rozłączne (żadne dwa różne podzbiory nie mają punktów wspólnych)
oraz zsumowane dają cały zbiór
A
.
4
Przykład 4
Rozważmy relację, której graf dany jest na rysunku 1. Zwróćmy uwagę, że
z elementem
a
są w relacji elementy
a
,
b
oraz
c
— i żadne inne. Mamy zatem
a
δ
a
,
b
δ
a
oraz
c
δ
a
, czyli [
a
]
δ
= {
a
,
b
,
c
}. Podobnie [
d
]
δ
= {
d
,
e
}. Zauważmy również,
że spełnione są także równości [
a
]
δ
= [
b
]
δ
= [
c
]
δ
oraz [
d
]
δ
= [
e
]
δ
. Dana relacja zatem
dzieli zbiór {
a
,
b
,
c
,
d
,
e
} na podzbiory {
a
,
b
,
c
} oraz {
d
,
e
}. Możemy więc napisać,
że w tym przypadku zbiór ilorazowy ma dwa elementy i wynosi:
{
a
,
b
,
c
,
d
,
e
}
δ
= {{
a
,
b
,
c}
, {
d
,
e}
}.
Przykład 5
Oznaczmy przez
A
zbiór wszystkich samochodów. Rozważmy następującą relację δ
określoną na tym zbiorze:
Dla dwóch dowolnych elementów
x
,
y
należących do zbioru
A
powiemy, że
x
jest
w relacji z
y
(
x
δ
y
), wtedy i tylko wtedy, gdy
x
jest tej samej marki, co
y
.
Również tutaj można zauważyć, że relacja δ jest zwrotna, symetryczna i przechodnia,
zatem jest relacją równoważności. Relacja ta dzieli zbiór
A
na klasy abstrakcji
(podzbiory). Weźmy jako generator klasy przysłowiową syrenkę pana Kowalskiego.
Zgodnie z definicją klas abstrakcji, syrenka ta generuje klasę (zbiór) wszystkich
takich elementów zbioru
A
(samochodów), które są w relacji δ z tą syrenką. Do klasy
tej należą zatem te i tylko te samochody, które są tej samej marki, co syrenka pana
Kowalskiego (patrz definicja relacji δ).
Mamy zatem:
[syrenka p. Kowalskiego]
δ
= {zbiór samochodów marki Syrenka},
ale również:
[mercedes S. Zasady]
δ
= {zbiór samochodów marki Mercedes},
[lancia premiera]
δ
= {zbiór samochodów marki Lancia} itp.
Zauważmy, że zbiór samochodów został podzielony na podzbiory ze względu
na markę samochodu. Zauważmy również, że zachodzą znane już własności klas
abstrakcji: żaden z tych podzbiorów nie jest pusty, są one parami rozłączne (żadne
dwa różne nie mają punktów wspólnych), zsumowane zaś dają cały zbiór
A
.
Własności podane w
twierdzeniu 1
można symbolicznie zapisać następująco:
Twierdzenie 2
Jeżeli δ ⊆
A
×
A
jest równoważnością, to dla dowolnych
a, b
∈
A
spełnione są
następujące warunki:
(a)
[
a
]
δ
∈ 2
A
,
1
(
b
)
[
a
]
δ
≠ ∅,
2
(c)
a
δ
b
⇔ [
a
]
δ
∩ [
b
]
δ
≠ ∅,
3
(d)
[
a
]
δ
∩ [
b
]
δ
≠ ∅ ⇔ [
a
]
δ
= [
b
]
δ
,
4
(e)
a
δ
b
⇔ [
a
]
δ
= [
b
]
δ
,
(f)
[
a
]
δ
≠ [
b
]
δ
⇔ [
a
]
δ
∩ [
b
]
δ
= ∅,
(g)
∪
a
∈
A
[
a
]
δ
=
A
.
1
Klasy abstrakcji są podzbiorami zbioru
A
.
2
Żadna klasa nie jest zbiorem pustym.
3
Iloczyn klas jest niepusty wtedy i tylko wtedy, gdy generatory wyznaczające klasy są w relacji δ.
4
Iloczyn klas jest niepusty wtedy i tylko wtedy, gdy te klasy są równe.
5
Plik z chomika:
darkstone
Inne pliki z tego folderu:
M6_zadania.pdf
(129 KB)
M6_przyklady.pdf
(207 KB)
M6.pdf
(558 KB)
M5_zadania.pdf
(298 KB)
M5_przyklady.pdf
(322 KB)
Inne foldery tego chomika:
semestr IV
Zgłoś jeśli
naruszono regulamin