M3.pdf
(
332 KB
)
Pobierz
3_logika.indd
Algebra zbiorów
Wstęp
2
1. Algebra zbiorów
3
1.1. Działania algebry zbiorów
3
1.2. Inkluzja (zawieranie) i równość zbiorów
4
1.3. Metody dowodzenia własności zbiorów
5
1.4. Uniwersum i zbiór pusty
6
2. Zbiór potęgowy i inne rodziny zbiorów
11
Bibliografia
15
Wstęp
Zbiory i działania na zbiorach pełnią istotną rolę w informatyce. Przykładem zbioru
informacji gromadzonej w systemie informatycznym jest baza danych. Również
w programistyce spotykamy się ze zbiorem jako jednym z podstawowych typów
danych. Dobry programista musi umiejętnie korzystać ze struktur mających charakter
zbioru, a dobry bazodanowiec musi znać podstawowe własności działań na zbiorach,
aby umieć odpowiednio ekstrahować informacje ze swojej bazy.
Moduł trzeci przedstawia podstawowe pojęcia algebry zbiorów i ich — użyteczne
również z punktu widzenia informatyki — własności.
Omówimy pojęcia pierwotne teorii mnogości: zbiór i relację przynależności. Zostaną
zdefiniowanerelacjerówności i inkluzji zbiorów, a także działania teoriomnogościowe.
Przedstawione zostaną również (w większości wraz z dowodami) własności tych
działań oraz zależności między tymi własnościami.
Zdefiniujemy też pojęcie zbioru potęgowego oraz ciała zbiorów i omówimy ich
własności.
2
1. Algebra zbiorów
Pojęcia
zbioru
i
relacji należenia
są w matematyce traktowane jako pojęcia pierwotne,
czyli pozostawiane bez definicji. Gdyby przyjrzeć się bliżej problemowi definicji
zbioru, można zauważyć, że gdyby nawet udało się zdefiniować zbiór jako na przykład
„grupę pewnych elementów”, zrodzi się wtedy automatycznie pytanie o definicję
takiej „grupy”. Gdyby i to zdefiniować, trzeba byłoby użyć jakichś innych pojęć,
o definicję których znowu trzeba byłoby zadbać itp. Problem ten wiódłby oczywiście
do podobnych rozważań i sporów o definiowanie w nieskończoność. Ustalono
zatem, że dwa wyżej wspomniane pojęcia przyjmuje się za
pierwotne
. Pojęcia te są
odpowiednio charakteryzowane przez aksjomaty tzw.
teorii mnogości
(np.
Zermelo-
Fraenkla
).
W dalszych rozważaniach dużymi literami
A
,
B
oznaczać będziemy zbiory, małymi
zaś
x
,
y
— elementy zbiorów. Przez zapis
x
∈
A
rozumiemy zwyczajowo intuicję:
element
x
należy do zbioru
A
.
Przykład 1
Rozważmy następujące przykłady zbiorów:
A
= {
a
,
b
, 1, 0} — jak można łatwo zauważyć, zbiór ten ma cztery elementy. Są
to:
a
,
b
, 1, 0. Możemy zatem zapisać:
a
∈
A
,
b
∈
A
, 1
∈
A
, 0
∈
A
;
B
= {{
a
},
b
, {1, 0}} — zbiór ten ma trzy elementy. Są to: {
a
},
b
, {1, 0}. Mimo
że {
a
} sam w sobie jest zbiorem (jednoelementowym), to jest on elementem
rozważanego zbioru
B.
Podobnie {1, 0} jest zbiorem dwuelementowym, ale
jako całość jest elementem zbioru
B
. Prawdą jest zatem, że {
a
} ∈
B
,
b
∈
B
oraz
{1, 0} ∈
B
. Ale nie jest prawdą, że
a
∈
B
(choć oczywiście
a
∈ {
a
}). Mamy też
0
∉
B
(choć 0
∈ {1, 0});
C
= {{
a
, {
b
}}} — zbiór
C
ma tylko jeden element. Jest nim (dwuelementowy)
zbiór {
a
, {
b
}}. Mamy zatem {
a
, {
b
}} ∈
C
. Ale nie jest prawdą, że
a
∈
C
czy też
nie jest prawdą, że
b
∈
C
;
D
= {
a
, {
a
, {
b
}}} — zbiór
D
ma dwa elementy. Są to:
a
oraz zbiór {
a
, {
b
}}.
Mamy oczywiście
a
∈
D
, ale też
b
∉
D
;
N
= {0, 1, 2, 3, 4, ...}
— zbiór liczb naturalnych jest zbiorem nieskończonym;
Z
= {... , –4, –3, –2, –1, 0, 1, 2, 3, 4, ...}
— zbiór liczb całkowitych (zbiór
nieskończony).
1.1. Działania algebry zbiorów
A B
Jeżeli
A
oraz
B
są zbiorami, to:
przez zapis
A
∪
B
rozumieć będziemy zbiór spełniający warunek
x
∈
A
∪
B
⇔ (
x
∈
A
∨
x
∈
B
) (element należy do zbioru
A
∪
B
wtedy
i tylko wtedy, gdy należy do jednego z nich lub do drugiego). Zbiór
A
∪
B
nazywamy
sumą
zbiorów
A
oraz
B
. Interpretacja graficzna sumy zbiorów
przedstawiona jest na rysunku 1;
A B
Rysunek 1
3
przez zapis
A
∩
B
rozumiemy zbiór spełniający warunek
x
∈
A
∩
B
⇔ (
x
∈
A
∧
x
∈
B
) (element należy do zbioru
A
∩
B
wtedy i tylko wtedy, gdy należy do jednego z nich
i jednocześnie do drugiego). Zbiór
A
∩
B
nazywamy
iloczynem
lub
częścią wspólną
zbiorów
A
oraz
B
. Interpretacja graficzna
iloczynu zbiorów przedstawiona jest na rysunku 2;
A B
przez zapis
A
–
B
rozumiemy zbiór spełniający warunek
x
∈
A
–
B
⇔ (
x
∈
A
∧
x
∉
B
) (element należy do zbioru
A
–
B
wtedy i tylko wtedy, gdy należy do pierwszego z nich i nie należy do
drugiego). Zbiór
A
–
B
nazywamy
różnicą
zbiorów
A
oraz
B
. Interpretacja
graficzna różnicy zbiorów przedstawiona jest na rysunku 3;
A B
Rysunek 2
przez zapis
A
÷
B
rozumiemy zbiór spełniający warunek
x
∈
A
÷
B
⇔ [(
x
∈
A
∧
x
∉
B
) ∨ (
x
∈
B
∧
x
∉
A
)]. Zbiór
A
÷
B
nazywamy
różnicą symetryczną
zbiorów
A
oraz
B
. Interpretacja graficzna
różnicy symetrycznej zbiorów przedstawiona jest na rysunku 4;
A B
przez zapis
A
’ rozumiemy zbiór spełniający warunek
x
∈
A
’ ⇔
x
∉
A
⇔ ¬
x
∈
A
(element należy do zbioru
A
’
wtedy i tylko wtedy, gdy nie należy do zbioru
A
). Zbiór
A
’ nazywamy
dopełnieniem
zbioru
A
. Interpretacja graficzna
dopełnienia zbioru przedstawiona jest na rysunku 5.
A – B
Rysunek 3
A B
1.2. Inkluzja (zawieranie) i równość zbiorów
Między zbiorami rozważa się dwie podstawowe zależności: zawierania
i równości zbiorów. Powiemy, że zbiór
A
zawiera się w zbiorze
B
, co
zapisujemy
A
⊆
B
(rysunek 6), jeżeli każdy element zbioru
A
należy również
do zbioru
B
.
A-B
Rysunek 4
Formalnie możemy ten fakt zapisać następująco:
A
⊆
B
⇔ ∀
x
(
x
∈
A
⇒
x
∈
B).
Powiemy, że zbiór
A
jest równy zbiorowi
B
wtedy i tylko wtedy, gdy zbiór
A
zawiera się w zbiorze
B
oraz zbiór
B
zawiera się w zbiorze
A
(każdy element
zbioru
A
należy do zbioru
B
oraz każdy element zbioru
B
należy do zbioru
A
).
A
Formalnie:
A
=
B
⇔ [(
A
⊆
B
) ∧ (
B
⊆
A
)]
.
Po odpowiednich przekształceniach możemy otrzymać:
A
,
Rysunek 5
A
=
B
⇔ [(
A
⊆
B
) ∧ (
B
⊆
A
)] ⇔ [∀
x
(
x
∈
A
⇒
x
∈
B
) ∧ ∀
x
(
x
∈
B
⇒
x
∈
A
)] ⇔
1
⇔ ∀
x
[(
x
∈
A
⇒
x
∈
B
) ∧ (
x
∈
B
⇒
x
∈
A
)] ⇔
2
∀
x
(
x
∈
A
⇔
x
∈
B
).
Finalnie mamy:
A
=
B
⇔ ∀
x
(
x
∈
A
⇔
x
∈
B
).
Dla zdefiniowanych wyżej działań i zależności między zbiorami możemy
udowodnić wiele własności zbiorów i działań na zbiorach.
1
Zgodnie z prawem rachunku kwantyfikatorów [
∀
x
A
(
x
)
∧ ∀
x
B
(
x
)]
⇔
∀
x
[
A
(
x
)
∧
B
(
x
)].
Rysunek 6
2
Z prawa rachunku zdań
[(
α
⇒
β
)
∧
(
β
⇒
α
)]
⇔
(
α
⇔
β
).
4
Twierdzenie 1
Dla dowolnych zbiorów
A
,
B
,
C
zachodzą następujące własności:
(a)
A
∩
A
=
A
— idempotentność iloczynu,
(b)
A
∪
A
=
A
— idempotentność sumy,
(c)
A
∩
B
=
B
∩
A
— przemienność iloczynu,
(d)
A
∪
B
=
B
∪
A
— przemienność sumy,
(e)
A
∩ (
B
∪
C
) = (
A
∩
B
) ∪ (
A
∩
C
) — rozdzielność iloczynu względem
sumy,
(f)
A
∪ (
B
∩
C
) = (
A
∪
B
) ∩ (
A
∪
C
) — rozdzielność sumy względem
iloczynu,
(g)
A
∩ (
A
∪
B
) =
A
— pochłanianie,
(h)
A
∪ (
A
∩
B
) =
A
— pochłanianie,
(i)
(
A
∪
B
)’ =
A
’ ∩
B
’ — prawo de Morgana algebry zbiorów,
(j)
(
A
∩
B
)’ =
A
’ ∪
B
’ — prawo de Morgana algebry zbiorów,
(k)
A
∩
B
⊆
A
,
(l)
A
⊆
A
∪
B
.
1.3. Metody dowodzenia własności zbiorów
Udowodnimy dla przykładu własność (a) z
twierdzenia 1
(idempotentności iloczynu
zbiorów):
A
∩
A
=
A
.
Aby udowodnić tę własność, zgodnie z definicją równości zbiorów, należy pokazać, że:
∀
x
(
x
∈
A
∩
A
⇔
x
∈
A
),
czyli dla dowolnego elementu
x
należy wykazać prawdziwość równoważności
x
∈
A
∩
A
⇔
x
∈
A
.
Weźmy zatem dowolny element
x
.
Rozpisując lewą stronę równoważności, otrzymujemy:
L :
x
∈
A
∩
A
⇔
x
∈
A
∧
x
∈
A
⇔
3
x
∈
A
: P
Następnie — wykorzystując prawo przechodniości równoważności
[(α ⇔ β) ∧ (β ⇔ γ)] ⇒ (α ⇔ γ) — otrzymujemy finalnie:
x
∈
A
∩
A
⇔
x
∈
A
.
Dowód (e)
Należy pokazać, że ∀
x
[
x
∈
A
∩ (
B
∪
C
) ⇔
x
∈ (
A
∩
B
) ∪ (
A
∩
C
)].
Weźmy dowolny element
x
. Mamy:
L :
x
∈
A
∩ (
B
∪
C
) ⇔
4
x
∈
A
∧
x
∈ (
B
∪
C
) ⇔
5
x
∈
A
∧ (
x
∈
B
∨
x
∈
C
) ⇔
6
⇔ (
x
∈
A
∧
x
∈
B
) ∨ (
x
∈
A
∧
x
∈
C
) ⇔ (
x
∈ (
A
∩
B
)) ∨
(
x
∈ (
A
∩
C
)) ⇔
x
∈ (
A
∩
B
) ∪ (
A
∩
C
) : P
3
Wykorzystujemy tu prawo idempotentności koniunkcji: α
∧
α
⇔
α.
4
Korzystamy z definicjiiloczynuzbiorów:
x
∈
A
∩
B
⇔ (
x
∈
A
∧
x
∈
B
).
5
Definicjasumy
x
∈
A
∪
B
⇔ (
x
∈
A
∨
x
∈
B
).
6
Prawo rozdzielności koniunkcji względem alternatywy
α
∧
(
β
∨
γ
)
⇔
(
α
∧
β
)
∨
(
α
∧
γ
).
5
Plik z chomika:
darkstone
Inne pliki z tego folderu:
M3_zadania.pdf
(67 KB)
M3_przyklady.pdf
(255 KB)
M3.pdf
(332 KB)
M2_zadania.pdf
(68 KB)
M2_przyklady.pdf
(241 KB)
Inne foldery tego chomika:
semestr II
Zgłoś jeśli
naruszono regulamin