Zakład Logiki i Epistemologii
Instytut Filozofii i Socjologii UKW
w Bydgoszczy
ul. Ogińskiego 16
Jak miło jest coś wiedzieć
(Molier, Mieszczanin szlachcicem)
Wykład 13
Rachunek zbiorów i relacji (1)
Podstawowe pojęcia
Algebra Boole'a
Algebra zbiorów
Relacje
Cechy algebry Boole'a
1) Dla każdego zbioru istnieje jego dopełnienie (w teorii mnogość ZF tego już nie ma, ale w teorii mnogości Bernaysa jest ta własność).
2) Przyjmuje się istnienie zbioru uniwersalnego (w teorii mnogości ZF prowadzi to do sprzeczności, przyjmuje się w teorii mnogości Bernaysa klasa i zbiór).
3) Nie ma mowy o rodzinach zbiorów.
4) George Boole nie posługiwał się pojęciem należenia elementu do zbioru.
Algebra Boole'a zawierała twierdzenia matematyki i dlatego nie mogła służyć jako podstawa matematyki. Przekształcił ją odpowiednio G. Frege.
Symbole zawierania " ⊂ " i należenia do " ∈ " pojawiły się dopiero u Peano.
Znał je intuicyjnie I, Kant. G. Cantor posiadał już to pojęcie.
Zbiory
W języku potocznym słowo "zbiór" jest wieloznaczne. Wyróżnia się następujące rodzaje zbiorów: dystrybutywne, kolektywne i rozmyte.
Zbiór
w sensie kolektywnym (zbiory kolektywne)
w sennie dystrybutywnym (zbiory dystrybutywne)
1
w sensie rozmytym (zbiory rozmyte)
Zbiór kolektywny jest całością złożoną z pewnych przedmiotów i traktowanych jako części tej całości. Zbiory takie nazywano zbiorowiskami, agragatmi.
Teorię tak rozumianych zbiorów i teorię stosunku części do całości zbudował
Stanisław Leśniewski, nazywając ją mereologią.
Ex.
Elementem zbioru kolektywnego stołów może być stół jak i część stołu.
Inne przykłady:
kupa kamieni jako zbiorowisko kamieni (dany kamień A jest częścią kupy kamieni)
las jako zbiorowisko drzew (dane drzewo A jest częścią lasu,) miasto jako zbiorowisko budynków,
podział administracyjny kraju na województwa.
dzień, kwadrans
noga krzesła jest częścią krzesła.
Do badań statystycznych wybiera się właśnie zbiory kolektywne.
Zbiór w sensie mereologicznym to zespół wielu elementów posiadających wspólną, połączonych abstrakcyjnie w jedność.
Są to zbiory dające się pojąć przestrzennie.
Charakteryzuje się go za pomocą relacji: x jest częścią zbioru A.
Relacja część – całość jest jedną z podstawowych struktur bytowych. Na gruncie fenomenologii tę relację badał formalnie Barry Smith.
Inne struktury bytowe
substancja - przypadłość
formalnie próbował ująć Peter Simons
akt - możność
materia - forma
istota - istnienie (Tomasz z Akwinu)
(zob. A. Stępień, Wstęp do filozofii)
Mereologia była tworzona jako teoria konkurencyjna wobec teorii mnogości G.
Cantora. Mereologia może mieć zastosowanie w biologii. Teorią części i całości posłużył się A. Wodger aksjomatyzując w latach 60-tych XX wieku genetykę.
W rezultacie przycyzniło się to do gwałtownego obecnie rozwoju badań genomicznych.
2
Leśniewski chciał, aby mereologia leżała u podstaw matematyki. Mereologię w matematyce stosował Alfred Tarski (geometria brył), a współcześnie w topologii stosował Andrzej Pietruszczak (UMK) i Cezary Gorzka (UMK).
Istota i istnienie nie podpadają pod badania logiczne w zakresie mereologii ani w pod logikę klasyczną. Istotą i istnienie nie są częściami bytu (np. tego oto stołu), ale są elementami subontyczny. Elementy te są realnie w bycie, ale nie są oddzielalne, są sprzężone ze sobą. Są poznawalne wyłącznie intelektualnie, tzn.
dochodzi się do nich w analizie struktur bytu.
Badania formalne nad problemem istoty prowadził Alvin Plantinga. Próby formalnego wyrażenia istnienia zebrał Edward Nieznański.
Zbiory dystrybutywne to zbiory, które stosowane w teorii mnogości. Są to zbiory wyznaczone przez pewną własność, np. bycie białym wyznaczy nam zbiór przedmiotów białych. Utożsamia się tu zbiór z własnością. Badania w tym zakresie prowadził brytyjski logik polskiego pochodzenia Peter Thomas Geach.
Zbiory dystrybutywne (G. Cantor) są scharakteryzowane przez relację: x jest elementem zbioru A. Np. liczba 2 jest elementem zbioru liczb naturalnych. Są one badane w teorii mnogości. Zbiór przedmiotów wyznacza cechę, cecha wyznacza zbiór przedmiotów.
Zbiór dystrybutywny można zdefiniować na dwa sposoby:
- przez określenie jego elementów (dwa zbiory, które mają te same elementy są identyczne),
- przez podanie warunku jaki powinny spełniać jego elementy; warunek jest przedstawiony w postaci funkcji zdaniowej.
x ∈ A ⇔ ϕ(x)
Elementy zbioru można określić przez bezpośrednie ich wyliczenie, np.
{a,b,c,d,} jest zbiorem o elementach a, b, c, d.
Zbiory rozmyte ( fuzzy sets) wiążą z pojęciami (nazwami) nieostrymi. Zbiory rozmyte są podobne do zbiorów dystrybutywnych. Różnica jest następująca: własność wyznaczająca zbiór może być nieostra.
Przykłady:
człowiek młody i zbiór ludzi młodych,
moje preferencje smakowe i zbiór moich ulubionych potraw.
Każda potrawa należy do takiej całości w stopniu, który odpowiada mojej subiektywnej ocenie. Jeśli skala ocen rozciąga się od zero do 1 poprzez wszystkie liczby rzeczywiste z przedziału [0,1], to potrawy nielubiane przez 3
mnie mają ocenę 0, a najbardziej lubiane – ocenę 1. Zatem zbiór rozmyty tworzą wszystkie potrawy brane przez mnie pod uwagę 1 .
Pojęcie zbioru rozmytego odpowiada temu co nazywa się pojęciem typologicznym. W filozofii analitycznej pojęcie znaczenia rodzinnego –
wprowadzone przez L. Wittgensteina – jest tym samym co pojęcie typologiczne.
Peirce, Schröer – teoria relacji pojawiła się jako teoria niezależna od logiki i matematyki.
Pojęcie pary uporządkowanej zostało zdefiniowane na gruncie teorii mnogości.
Wiener i A. Kuratowski niezależnie podali definicję pary uporządkowanej.
Dlatego całą teoria relacji może być zredukowana do teorii mnogości.
Zob. A Mostowski, Logika matematyczna.
Uwaga
Ujęcie Mostowskiego jest najbardziej zbliżone do ujęcia Borkowskiego.
Algebra Boole'a ma wiele interpretacji, np. w sieciach elektrycznych, w rachunku zdań, w algebrze zbiorów, w rachunku prawdopodobieństwa. Dlatego ma ona dużą wartość teoretyczną 2.
Aksjomaty algebry Boole'a spełnia klasyczny rachunek logiczny. Logiki wielowartościowe są związane z wielowartościowymi algebrami Boole'a. Ale logika intuicjonistyczna nie odpowiada algebrze Boole'a. W tym przypadku mówi się o algebrze pseudoboolowskiej albo o algebrze Heytinga. Również logiki kwantowe nie spełniają aksjomatów algebry Boole'a.
Mówiąc o algebrze Boole'a rozpatruje się:
- zbiór przedmiotów
- działania: +, ◦, dopełnienie '
- relacja równości
- dwa wyróżnione elementy: 0, 1 (zatem zbiór przedmiotów nie jest pusty)
- nic się nie zakłada o naturze działań
Aksjomaty (wg Mostowskiego)
Terminy pierwotne: K, +, ◦, ', 0, 1
K - zbiór przedmiotów
x, y ∈ K,
1
A. Łachwa, Rozmyty świat zbiorów, liczb, relacji, faktów, reguł i decyzji, Akademicka Oficyna Wydawnicza EXIT, Warszwa 2001.
2
Czym jest interpretacja zob. Borkowski, Słupecki, Elementy logiki matematycznej i teorii mnogości, s.
157.
4
jeśli 0 oraz 1 są elementami zbioru K, to zbiór K nie jest zbiorem pustym.
~(0=1)
działania nie wyprowadzają poza zbiór K
x+y ∈ K, x ◦ y ∈ K, x' ∈ K
Relacja równości w algebrze Boole'a nie jest taka sama jak identyczność w w.r.p.
Relacja identyczności jest zwrotna, symetryczna i przechodnia.
Aksjomaty
1.
x+x=x
x ◦ x=x
2.
x+y=y+x
x ◦ y = y ◦ x
3.
x +(y+z)=(x+y)+z
x ◦ (y ◦ z) = (x ◦ y) ◦ z
4.
x+(y ◦ z) = (x+y) ◦ (x+z)
x ◦ (y+z) = (x ◦ y) + (x ◦ z)
5.
x+1 = 1
x ◦ 0 = 0
6.
x+0 = x
x ◦ 1 = x
7.
x+x' = 1
x ◦ x' = 0
Dla zwiększenia przejrzystości pominięto kwantyfikatory Przykładem algebry Boole'a jest tzw. dwuelementowa algebra Boole'a
<{0,1}, +, ◦, '}
gdzie działania są zdefiniowane następująco
+
0 1
0
0 1
1
1 1
◦
0 1
0
0 0
1
0 1
'
0 1
x' 1 0
5
Innym przykładem algebry Boole'a jest algebra zbiorów. Wtedy przedmiotami są zbiory. Symbol K odnosi się do rodziny podzbiorów ustalonego zbioru, a działania to działania na zbiorach.
Podstawowe definicje i twierdzenia rachunku zbiorów Wyrażenie " x ∈ A " czytamy " x jest elementem zbioru A", "x należy do zbioru A", "x należy do klasy A".
Nie zawsze zamiennie używa się pojęcia klasy i zbioru.
Wyrażenie " x ∉ A " jest skrótem dla "~( x ∈ A)" i czytamy: x nie jest elementem zbioru A.
Def. 1 Iloczyn zbiorów
x ∈ A ∩ B ≡ (x ∈ A ∧ x ∈ B)
Iloczynem zbiorów A i B jestr zbiór złożony z tych przedmiotów, które należą jednocześnie do zbioru A i do zbioru B.
Def. 2 Suma zbiorów
x ∈ A ∪ B ≡ (x ∈ A ∨ x ∈ B)
Suma zbiorów A i B jest zbiorem wszystkich tych przedmiotów, które należą do zbioru lub do zbioru B, a więc są elementami przynajmniej jednego ze zbiorów.
Def. 3 Różnica zbiorów
x ∈ A - B ≡ (x ∈ A ∧ x ∉ B)
Różnica zbioru A i B jest to zbiór tych wszystkich przedmiotów, które należą do zbioru A i nie należą do zbioru B.
Def. 3 Dopełnienie zbiorów
x ∈ –A ≡ x ∉ A
Dopełnienie zbioru A jest to zbiór tych wszystkich przedmiotów, które nie nalę=eżą do zbioru A.
Def. 4 Zbiór pusty
x ∈ ∅ ≡ x ≠ x
Zbiór ∅ nazywa się zbiorem pustym
6
Dla żadnego przedmiotu nie jest prawdą, że nie jest identyczny z samym sobą.
Zatem zbiór pusty to taki zbiór, do którego nie należy żaden przedmiot.
Def. 5 Zbiór uniwersalny
x ∈ V ≡ (x = x)
Zbiór V nazywa się zbiorem uniwersalnym.
Dla każdego przedmiotu jest prawdą, iż jest identyczny z samym sobą.. Zatem zbiór uniwersalny to zbiór do którego należy każdy przedmiot.
W aksjomatycznej teorii mnogości nie można przyjmować pojęcia zbioru uniwersalnego.
Def. 6 Zawieranie się zbiorów
A ⊂ B ≡ Λx (x ∈ A → x ∈ B)
Zbiór A jest zawarty w zbiorze B wttw, gdy każdy element zbioru A jest elementem zbioru B.
Zawieranie się właściwe
A |⊆ B ≡ (A ⊂ B ∧ A ≠B)
Zbiór A jest podzbiorem właściwym zbioru B wttw, gdy każdy element zbioru A jest elementem zbioru B, ale nie każdy element zbioru B jest elementem zbioru A.
Uwaga
Definicje tym się różnią od aksjomatów, że spełniają warunek przekładalności.
Aby udowodnić, że zbiór A zawiera się w zbiorze B wystarczy udowodnoć implikację: x ∈ A → x ∈ B. Polega to na zastosowaniu reguły DΛ i skorzystaniu z definicji zawierania się.
Dowód takiej implikacji można przeprowadzić zakładają poprzednik i wyprowadzając następnik.
Aksjomat ekstensjonalności dla zbiorów
Λx (x ∈ A ≡ x ∈ B) → A = B
stwierdza, że zbiory złożone z tych samych elementów są identyczne.
7
Twierdzenie 1 (odwrotne do aksjomatu) A = B → Λx (x ∈ A ≡ x ∈ B)
Dowód
1.
A = B
z.
2.
x ∈ A ≡ x ∈ A
p ≡ p
3.
x ∈ A ≡ x ∈ B
ExI: 1,2
Λx (x ∈ A ≡ x ∈ B)
DΛ: 3
Twierdzenie 2
A = B ≡ Λx (x ∈ A ≡ x ∈ B)
Dowód
1.
Λx (x ∈ A ≡ x ∈ B) → A = B aksjomat
2.
A = B → Λx (x ∈ A ≡ x ∈ B) twierdzenie 1
A = B ≡ Λx (x ∈ A ≡ x ∈ B)
DE: 1,2
Twierdzenie 3
A = B ≡ A ⊂ B ∧ B ⊂ A
Dowód (uproszczony)
1.
A = B ≡ Λx (x ∈ A ≡ x ∈ B)
twierdzenie 2
2.
Λx [(x ∈ A → x ∈ B) ∧ (x ∈ B → x ∈ A)]
3.
Λx (x ∈ A → x ∈ B) ∧ Λx (x ∈ B → x ∈ A)
A ⊂ B ∧ B ⊂ A
def. zawierania się, 3
Twierdzenie 4
A ⊂ B ≡ A ∩ B = A
Dowód (uproszczony)
1.
p → q ≡ (p ∧ q ≡ p)
prawo
2.
A ⊂ B
z.
3.
A ⊂ B ≡ Λx (x ∈ A → x ∈ B) def. zawierania się
4.
Λx (x ∈ A → x ∈ B)
RO: 3,1
5.
Λx (x ∈ A → x ∈ B) ≡ Λx [(x ∈ A ∧ x ∈ B) ≡ x ∈ A] 4,1, p|x∈A, q|x∈B
6.
Λx [(x ∈ A ∩ B) ≡ x ∈ A]
5, def. iloczynu zbiorów
A ∩ B = A
6, twierdzenie 2
Jest to ciąg równoważności
Twierdzenie 5
A ⊂ B ≡ A ∪ B = B
Dowód (analogicznie j.w.
1.
p → q ≡ (p ∨ q ≡ q)
prawo
itd.
8
A – B ≡ A ∩ -B
Dowód.
1.
x ∈ A ∩ B ≡ (x ∈ A ∧ x ∈ B) def. iloczynu
2.
x ∈ A - B ≡ (x ∈ A ∧ x ∉ B) def. różnicy
3.
x ∈ –A ≡ x ∉ A
def. dopełnienia
4.
x ∈A – B
z.
5.
x ∈ A ∧ x ∉ B
4, 2
6
x ∈ A ∧ x ∈ –A
5, 3 (zastępowanie definicyjne)
x ∈ A ∩ -B
6, 1
Twierdzenie 7 (Prawa de Morgana)
a) -(A ∩ B) ≡ -A ∪ -B
b) -(A ∪ B) ≡ -A ∩ -B
Dowód a)
1.
~(p ∧ q) ≡ (~p ∨ ~q)
prawo
2.
x ∈ -(A ∩ B)
z.
3.
~(x ∈ A ∩ B)
2, def. dopełnienia
4.
~(x ∈ A ∧ x ∈ B)
3, def. iloczynu
5.
x ∉ A ∨ x ∉ B
4, 1 (podstawienie prawa logiki)
6.
x ∈ -A ∨ x ∈ -B
5, def. dopełnienia
x ∈ -A ∪ -B
6, def. sumy
Dowód b)
1.
~(p ∨ q) ≡ (~p ∧ ~q)
prawo
analogicznie
Prawa algebry zbiorów są zbudowane ze zmiennych reprezentujących nazwy zbiorów, stałych: ∩, ∪, -, V, ∅, ⊂, = oraz funktorów rachunku zdań.
Nie występuje w nich funktor ∈.
Prawo zwrotności zawierania się zbiorów
A ⊂ A
Prawo przechodniości zawierania się zbiorów
(A ⊂ B ∧ B ⊂ C) → A ⊂ C
Prawo przemienności iloczynu i sumy zbiorów
A ∩ B ≡ B ∩ A
A ∪ B ≡ B ∪ A
Prawo łączności iloczynu i sumy zbiorów
A ∩ (B ∩ C) = (A ∩ B) ∩ C
9
Prawo rozdzielności iloczynu względem sumy zbiorów (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
Prawo rozdzielności sumy względem iloczynu zbiorów (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C)
System algebry zbiorów jest jedną z interpretacji algebry Boole'a.
10