M4.pdf
(
556 KB
)
Pobierz
4_logika.indd
Iloczyn kartezjański i relacje binarne
Wstęp
2
1. Para uporządkowana i iloczyn kartezjański zbiorów
3
2. Relacje binarne
7
3. Rodzaje relacji binarnych
14
Bibliografia
18
Wstęp
Moduł czwarty przedstawi podstawowe pojęcia teorii mnogości potrzebne między
innymi do opisu i modelowania systemów informatycznych.
Temat pierwszy dotyczy pojęcia pary uporządkowanej oraz definicji iloczynu kar-
tezjańskiego zbiorów. Zostaną omówione i — w większości — udowodnione pod-
stawowe własności iloczynu kartezjańskiego.
Temat drugi zaprezentuje pojęcie relacji binarnej, reprezentacji graficznej relacji
i działań na relacjach wraz z ich podstawowymi własnościami.
W temacie trzecim zawarte są definicjewłasnościrelacjibinarnych, przykłady oraz
zależności między nimi.
2
1. Para uporządkowana
i iloczyn kartezjański zbiorów
Para uporządkowana
i
iloczyn kartezjański
zbiorów
są podstawowymi pojęciami nauki
o zbiorach, na których opiera się pojęcie relacji.
Para uporządkowana (
a
,
b
) to dowolny, złożony z dwóch elementów obiekt, speł-
niający poniższe założenia:
jeśli
a
≠
b
, to (
a
,
b
) ≠ (
b
,
a
).
jeśli (
a
,
b
) = (
c
,
d
), to
a
=
c
oraz
b
=
d.
Jeżeli
(
a
,
b
) jest parą uporządkowaną, to element
a
nazywamy
poprzednikiem pary
,
zaś element
b
następnikiem pary
.
Jedną z popularniejszych definicjipary uporządkowanej podał w 1920 roku polski
matematyk Kazimierz Kuratowski: (
a
,
b
) =
df.
{{
a
}, {
a
,
b
}}. Łatwo można udowod-
nić, że tak zdefiniowana—
za pomocą pojęcia zbioru — para uporządkowana speł-
nia podane wyżej wymagania.
Pojęcie pary uporządkowanej służy do zdefiniowania pojęcia iloczynu kartezjań-
skiego zbiorów. Niech
A
oraz
B
będą dowolnymi zbiorami. Iloczynem kartezjań-
skim zbiorów
A
i
B
nazywamy zbiór wszystkich takich par uporządkowanych
(
a
,
b
), że
a
∈
A
oraz
b
∈
B
. Iloczyn kartezjański zbiorów
A
oraz
B
oznaczamy sym-
bolem
A
×
B
.
Rozważmy zbiory
A
= {1, 2, 3} oraz
B
= {
a
,
b
}. Iloczynem kartezjańskim tych
zbiorów jest, zgodnie z definicją, zbiór wszystkich par uporządkowanych (
a
,
b
) ta-
kich, że
a
∈
A
oraz
b
∈
B
. Mamy zatem
A
×
B
= {(1,
a
), (2,
a
), (3,
a
), (1,
b
),
(2,
b
), (3,
b
)}.
Jeżeli zbiór
A
ma
n
elementów, a zbiór
B
ma
k
elementów, to iloczyn kartezjański
A
×
B
ma
n
⋅
k
elementów.
Przykład 1
Znanym przykładem iloczynu kartezjańskiego jest płaszczyzna, rozumiana jako
zbiór punktów o współrzędnych rzeczywistych.
Twierdzenie 1
Zachodzą następujące własności dla iloczynu kartezjańskiego:
(a)
(
A
×
B
≠
B
×
A
) ⇔ (
A
≠
B
∧
A
≠ ∅ ∧
B
≠ ∅),
(b)
(
A
×
B
=
B
×
A
) ⇔ (
A
=
B
∨
A
= ∅ ∨
B
= ∅),
(c)
A
× (
B
∪
C
) = (
A
×
B
) ∪ (
A
×
C
) (iloczyn kartezjański jest rozdzielny względem
sumy zbiorów),
(d)
A
× (
B
∩
C
) = (
A
×
B
) ∩ (
A
×
C
) (iloczyn kartezjański jest rozdzielny względem
iloczynu zbiorów),
(e)
A
× (
B
–
C
) = (
A
×
B
) – (
A
×
C
) (iloczyn kartezjański jest rozdzielny względem
różnicy zbiorów),
3
(f)
A
×
B
≠ ∅ ⇔ (
A
≠ ∅ ∧
B
≠ ∅)
(g)
A
×
B
= ∅ ⇔ (
A
= ∅ ∨
B
= ∅),
(h
)
A
× ∅ = ∅,
(i)
∅ ×
A
= ∅,
(j)
∅ × ∅ = ∅.
Dowód (c)
Aby udowodnić powyższą równość, musimy — zgodnie z definicją równości zbio-
rów — wykazać prawdziwość następującego warunku:
∀
x
(
x
∈
A
× (
B
∪
C
) ⇔
x
∈ (
A
×
B
) ∪ (
A
×
C))
Niech
x
będzie dowolne. Rozpatrzmy dwa przypadki: albo
x
nie jest parą uporządko-
waną, albo
x
jest parą uporządkowaną. W pierwszym przypadku równoważność jest
oczywista (obie strony fałszywe, obiekt niebędący parą uporządkowaną nie może
należeć do iloczynu kartezjańskiego).
Jeśli zaś
x
= (
a
,
b
), to:
L :
x
∈
A
× (
B
∪
C
) ⇔
1
(
a
,
b
) ∈
A
× (
B
∪
C
) ⇔
2
a
∈
A
∧
b
∈ (
B
∪
C
) ⇔
3
⇔
a
∈
A
∧ (
b
∈
B
∨
b
∈
C
) ⇔
4
(
a
∈
A
∧
b
∈
B
) ∨ (
a
∈
A
∧
b
∈
C
) ⇔
⇔ (
a
,
b
) ∈ (
A
×
B
) ∨ (
a
,
b
) ∈ (
A
×
C
) ⇔
⇔
x
∈ (
A
×
B
) ∨
x
∈ (
A
×
C
) ⇔
x
∈ (
A
×
B
) ∪ (
A
×
C
) : P
Dowód (e)
Mamy wykazać, że ∀
x
(
x
∈
A
× (
B
–
C
) ⇔
x
∈ (
A
×
B
) – (
A
×
C
)).
Niech
x
będzie dowolne. Rozpatrzmy dwa przypadki: albo
x
nie jest parą uporząd-
kowaną, albo
x
jest parą uporządkowaną.
W pierwszym przypadku równoważność jest oczywista.
W drugim przypadku, jeśli
x
= (
a
,
b
), to:
L :
x
∈
A
× (
B
–
C
) ⇔
5
(
a
,
b
) ∈
A
× (
B
–
C
) ⇔
6
a
∈
A
∧
b
∈ (
B
–
C
) ⇔
7
⇔
a
∈
A
∧ (
b
∈
B
∧
b
∉
C
) (*)
P :
x
∈ (
A
×
B
) – (
A
×
C
) ⇔
x
∈ (
A
×
B
) ∧
x
∉ (
A
×
C
) ⇔
⇔ (
a
,
b
) ∈ (
A
×
B
) ∧ (
a
,
b
) ∉ (
A
×
C
) ⇔ (
a
,
b
) ∈ (
A
×
B
) ∧ ¬[ (
a
,
b
) ∈ (
A
×
C
) ] ⇔
⇔ (
a
∈
A
∧
b
∈
B
) ∧ ¬(
a
∈
A
∧
b
∈
C
) ⇔ (
a
∈
A
∧
b
∈
B
) ∧ (¬(
a
∈
A
) ∨ ¬(
b
∈
C
)) ⇔
⇔ (
a
∈
A
∧
b
∈
B
∧ ¬(
a
∈
A
)) ∨ (
a
∈
A
∧
b
∈
B
∧ ¬(
b
∈
C
)) ⇔
8
⇔
a
∈
A
∧ (
b
∈
B
∧
b
∉
C
) (*)
1
Ponieważ założyliśmy, że
x
= (
a
,
b
).
2
Z definicji iloczynu kartezjańskiego.
3
Definicja sumy zbiorów.
4
Prawo rozdzielności koniunkcji względem alternatywy.
5
Ponieważ założyliśmy, że
x
= (
a
,
b
).
6
Z definicji iloczynu kartezjańskiego.
7
Definicja różnicy zbiorów.
8
Lewy składnik alternatywy jest fałszywy, zatem alternatywa ta jest równoważna pozosta-
łemu składnikowi.
4
W rezultacie rozpisanie obu stron równoważności dało ten sam wynik (*), zatem
L ⇔ P, czyli:
x
∈
A
× (
B
–
C
) ⇔
x
∈ (
A
×
B
) – (
A
×
C
)
.
Dowód (h)
Mamy wykazać, że
∀
x
(
x
∈
A
× ∅ ⇔
x
∈ ∅).
Niech
x
będzie dowolne. Rozpatrzmy dwa przypadki: albo
x
nie jest parą uporząd-
kowaną, albo
x
jest parą uporządkowaną. W pierwszym przypadku równoważność
jest oczywista.
W drugim przypadku, gdy
x
= (
a
,
b)
, mamy:
L : x
∈
A
× ∅ ⇔ (
a
,
b
) ∈
A
× ∅ ⇔
a
∈
A
∧
b
∈ ∅ ⇔
9
x
∈ ∅ : P
Twierdzenie 2
W ogólnym przypadku nie zachodzą następujące własności iloczynu kartezjańskiego:
(a)
A
∪ (
B
×
C
) = (
A
∪
B
) × (
A
∪
C
),
(b)
A
∩ (
B
×
C
) = (
A
∩
B
) × (
A
∩
C
),
(c)
A
– (
B
×
C
) = (
A
–
B
) × (
A
–
C
).
Dowód (a)
Pokażemy, że dla zbiorów
A
=
B
=
C
=
R
nie zachodzi równość z podpunktu (a).
Mamy:
L =
R
∪ (
R
×
R
)
.
Zbiór ten to suma zbioru liczb rzeczywistych oraz zbioru par uporządkowanych,
których elementami są liczby rzeczywiste.
Mamy na przykład 1
∈
R
, co natychmiast daje 1 ∈
R
∪ (
R
×
R
).
Rozważmy stronę prawą równości. Mamy:
P = (
R
∪
R
) × (
R
∪
R
) =
R
×
R.
Oczywiście, do tego zbioru należą tylko odpowiednie pary uporządkowane, a za-
tem 1 ∉
R
×
R
.
Pokazaliśmy istnienie elementu, który należy do lewej strony równości, a nie nale-
ży do prawej, zatem zbiory powyższe nie są równe.
Dowód (b)
Pokażemy, że dla zbiorów
A = B = C = R
nie zachodzi równość z podpunktu (b).
Mamy:
P
= (
R
∩
R
) × (
R
∩
R
) =
R
×
R
.
Oczywiście
R
×
R
≠ ∅.
9
Ta równoważność jest prawdziwa, gdyż ma obie strony fałszywe (nic nie może należeć do
zbioru pustego).
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