Logika dla informatyków
wykład 2
ZBIORY
Zbiór i należenie ( ∈) są pojęciami pierwotnymi. Zbiory zazwyczaj oznaczamy
dużymi literami. Zapis x ∈ A czytamy x należy do A lub x jest elementem
A. Piszemy x /
∈ A zamiast ¬ x ∈ A.
OZNACZENIA. N = zbiór liczb naturalnych, czyli {0,1,2,3,...}. Z = zbiór
liczb całkowitych, czyli {0,1,-1,2,-2,...}. Q = zbiór liczb wymiernych. R =
zbiór liczb rzeczywistych.
Zbiory skończone możemy określać przez wypisanie w nawiasach klamrowych
wszystkich ich elementów lub - gdy elementów jest sporo - kilku pierwszych
i ostatniego poprzedzonego wielokropkiem, np. { 1 , 2 , 3 } lub { 1 , 2 , 3 , ..., 100 }.
Niektóre zbiory nieskończone możemy określać podobnie, wypisując kilka ich
elementów tak, żeby łatwo można było zauważyć regułę wg której te elementy
powstają i w ten sposób wiedzieć jakie pozostałe elementy do tego zbioru
należą (np. definicja zbioru Z wyżej). O nieskończoności takiego zbioru mówi
wielokropek, po którym już nic nie występuje. Jednak nie wszystkie zbiory
można tak określić.
Definicja 1. (Formuła zdaniowa). Niech D będzie ustalonym zbiorem. Wy-
rażenie ze zmienną x, które staje się zdaniem (prawdziwym lub nie), gdy w
miejsce x podstawimy dowolny element a ∈ D nazywamy formułą zdaniową
zmiennej x określoną na D.
PRZYKŁAD. Niech D = R oraz ϕ( x) = ( x > 0). Wtedy np. zdanie ϕ(1) jest prawdziwe, a zdanie ϕ( − 1) fałszywe.
WYRÓŻNIANIE. Inną metodą określania zbiorów jest operacja wyróżniania.
Jeśli ϕ( x) jest formułą zdaniową określoną na zbiorze D, to {x ∈ D : ϕ( x) }
jest zbiorem tych i tylko tych x ∈ D, które spełniają ϕ( x). Tak więc ze wszyst-
kich elementów zbioru D wyróżniamy te x, dla których ϕ( x) jest prawdziwe.
PRZYKŁAD. Zbiór liczb rzeczywistych dodatnich możemy zapisać jako {x ∈
R : x > 0 }, zbiór liczb całkowitych podzielnych przez 3 jako {k ∈ Z : 3 |k}.
1
Przyzwyczailiśmy się do słowa zbiór tak bardzo, że sądzimy często, że każda
kolekcja obiektów tworzy zbiór. Tak jednak nie jest. Nie istnieje na przy-
kład zbiór wszystkich zbiorów ( twierdzenie Russela). Spróbujmy to uzasad-
nić. Przypuśćmy nie wprost, że V jest takim zbiorem. Za pomocą operacji
wyróżniania określamy wtedy zbiór {X ∈ V : X /
∈ X}. Zauważmy, że A ∈ A
wtedy i tylko wtedy, gdy A ∈ V i A /
∈ A. Ale zdanie A ∈ V jest prawdziwe.
Zatem A ∈ A wtedy i tylko wtedy, gdy A /
∈ A. Otrzymaliśmy sprzeczność.
AKSJOMAT EKSTENSJONALNOŚCI. Ważną rolę odgrywa aksjomat eks-
tensjonalności. Mówi on, że zbiory A i B są równe wtedy i tylko wtedy, gdy
mają te same elementy. Innymi słowy A = B wtedy i tylko wtedy, gdy rów-
noważność x ∈ A ←→ x ∈ B jest prawdziwa dla każdego x.
PRZYKŁAD. Niech A = { 1 , 2 , 3 }, B = { 1 , 2 , 2 , 3 , 3 , 3 }. Elementy zbioru A to 1,2,3. Zbiór B ma te same elementy. Zatem A = B.
PRZYKŁAD. Zbiór pusty to zbiór, do którego nie należy żaden element. Ile
jest zbiorów pustych? Pytanie nie jest trudne. Niech ∅
będą zbiorami
1 , ∅ 2
pustymi. Ustalmy x. Zauważmy, że x ∈ ∅ wtedy i tylko wtedy, gdy
,
1
x ∈ ∅ 2
ponieważ zdania po obu stronach równoważności są fałszywe. Zatem ∅ =
.
1
∅ 2
Jest więc tylko jeden zbiór pusty, oznaczamy go przez ∅.
Definicja 2. (Zawieranie). Jeśli każdy element zbioru A należy do zbioru B,
to mówimy, że zbiór A zawiera się w zbiorze B (lub A jest podzbiorem B) i
piszemy A ⊆ B.
PRZYKŁAD. { 1 , 2 } ⊆ { 1 , 2 , 3 }. Z ⊆ Q.
PRZYKŁAD. Zauważmy, że A ⊆ A dla dowolnego zbioru A. Podobnie ∅ ⊆ A
dla dowolnego zbioru A, bo dla dowolnego x implikacja x ∈ ∅ −→ x ∈ A
jest prawdziwa, więc każdy element zbioru pustego należy do A. Zatem zbiór
pusty jest podzbiorem każdego zbioru. W szczególności ∅ ⊆ ∅, ale oczywiście
∅ /
∈ ∅.
ZBIÓR POTĘGOWY. Przez P ( A) oznaczamy zbiór wszystkich podzbiorów
zbioru A ( zbiór potęgowy zbioru A).
PRZYKŁAD. Jedynym podzbiorem zbioru pustego jest on sam (dlaczego?),
zatem P ( ∅) = {∅}. Rozważmy zbiór { 1 , 2 , 3 }. Wszystkie jego podzbiory to: 2
∅, { 1 }, { 2 }, { 3 }, { 1 , 2 }, { 1 , 3 }, { 2 , 3 }, { 1 , 2 , 3 }, zatem P ( { 1 , 2 , 3 }) = {∅, { 1 }, { 2 }, { 3 }, { 1 , 2 }, { 1 , 3 }, { 2 , 3 }, { 1 , 2 , 3 }}.
OPERACJE NA ZBIORACH. Zdefiniujemy najpierw operację sumy ( ∪),
przekroju ( ∩), różnicy ( \) i różnicy symetrycznej ( △) dwóch zbiorów: x ∈ A ∪ B ←→ x ∈ A ∨ x ∈ B,
x ∈ A ∩ B ←→ x ∈ A ∧ x ∈ B,
x ∈ A \ B ←→ x ∈ A ∧ x /
∈ B,
x ∈ A△B ←→ x ∈ A \ B ∨ x ∈ B \ A.
Ponadto definiujemy operację dopełnienia ( c) zbioru A ⊆ X do aktualnie
rozważanej przestrzeni X (tzn. X jest pewnym ustalonym zbiorem):
x ∈ Ac ←→ x ∈ X \ A.
PRZYKŁAD. Niech A = { 1 , 2 , 3 , 4 }, B = { 3 , 4 , 5 , 6 , 7 , 8 } oraz przestrzeń X = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 }. Wtedy A ∪ B = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }, A ∩ B =
{ 3 , 4 }, A \ B = { 1 , 2 }, A△B = { 1 , 2 , 5 , 6 , 7 , 8 }, Ac = { 5 , 6 , 7 , 8 , 9 , 10 }.
PODSTAWOWE PRAWA RACHUNKU ZBIORÓW. Z niektórych praw bę-
dziemy często korzystać. Przedstawiamy te podstawowe:
A ∪ B = B ∪ A (przemienność),
A ∩ B = B ∩ A (przemienność),
A ∪ ( B ∪ C) = ( A ∪ B) ∪ C (łączność),
A ∩ ( B ∩ C) = ( A ∩ B) ∩ C (łączność),
A ∩ ( B ∪ C) = ( A ∩ B) ∪ ( A ∩ C) (rozdzielność),
A ∪ ( B ∩ C) = ( A ∪ B) ∩ ( A ∪ C) (rozdzielność),
( A ∪ B) c = Ac ∩ Bc (prawo de Morgana),
( A ∩ B) c = Ac ∪ Bc (prawo de Morgana),
A \ B = A ∩ Bc,
( A ⊆ B) ∧ ( B ⊆ C) −→ ( A ⊆ C),
( A = B) ←→ ( A ⊆ B) ∧ ( B ⊆ A).
Wykażemy na przykład prawo rozdzielności przekroju względem sumy. Sko-
rzystamy z prawa rozdzielności dla rachunku zdań. Ustalmy x. Wtedy x ∈
A ∩ ( B ∪ C) ←→ x ∈ A ∧ x ∈ B ∪ C ←→ x ∈ A ∧ ( x ∈ B ∨ x ∈ C) ←→
3
( x ∈ A ∧ x ∈ B) ∨ ( x ∈ A ∧ x ∈ C) ←→ x ∈ A ∩ B ∨ x ∈ A ∩ C ←→ x ∈
( A ∩ B) ∪ ( A ∩ C). Zatem zbiory A ∩ ( B ∪ C) i ( A ∩ B) ∪ ( A ∩ C) mają te same elementy, więc są równe.
W zbiorach kolejność elementów nie jest istotna. Przecież zbiory { 1 , 2 } i
{ 2 , 1 } są równe. A co jeśli będziemy chcieli nadać elementom 1 i 2 kolej-
ność? Potrzebujemy pojęcia pary uporządkowanej. Poniższą definicję podał
Kuratowski.
Definicja 3. (Para uporządkowana). Zbiór ( a, b) = {{a}, {a, b}} nazywamy
parą uporządkowaną elementów a i b (a jest pierwszym, b drugim elementem
pary).
Definicja ta spełnia warunek, dzięki któremu w parze uporządkowanej istotna
jest kolejność elementów:
( ⋆)
( a, b) = ( a′, b′) ←→ a = a′ ∧ b = b′.
Uzasadnijmy własność ( ⋆) pary uporządkowanej. Implikacja ” ←−” jest ja-
sna. Naszkicujemy dowód implikacji odwrotnej. Rozważymy dwa przypadki.
Jeśli a = b, to ( a, b) = {{a}}, więc ( a′, b′) = {{a′}}, zatem a = a′ = b′ = b.
Jeśli a 6= b i {{a}, {a, b}} = {{a′}, {a′, b′}}, to a = a′, więc b = b′.
ILOCZYN KARTEZJAŃSKI. Zbiór wszystkich par uporządkowanyh ( a, b)
takich, że a ∈ A i b ∈ B to iloczyn kartezjański zbioru A ze zbiorem B, który oznaczamy A × B. Na przykład R × R to zbiór uporządkowanych par liczb
rzeczywistych, czyli po prostu układ współrzędnych.
Przy pomocy pojęcia pary uporządkowanej możemy rekurencyjnie określić
pojęcie uporządkowanej n-ki: ( a
) = ((
)
). Teraz
1 , a 2 , ..., a
a
, a
n+1
1 , a 2 , ..., an
n+1
możemy zdefiniować iloczyn kartezjański n zbiorów A
jako:
1 , A 2 , ..., An
A
=
) :
1 × A 2 × ... × A
{( a
a
∈ A }.
n
1 , a 2 , ..., an
1 ∈ A 1 ∧ a 2 ∈ A 2 ∧ ... ∧ an
n
Podobną własność do ( ⋆) mają n-ki:
( a
) = (
)
=
=
=
1 , a 2 , ..., a
a′ , a′ , ..., a′ ←→ a
a′ ∧ a
a′ ∧ ... ∧ a
a′ .
n
1
2
n
1
1
2
2
n
n
Na przykład R × R × R to trójwymiarowy układ współrzędnych.
4