6
.
Algebra
zbioró
w
6
Pra
w
a
algebry
zbioró
w
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A
6
Meto
dy
do
w
o
dzenia
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B
6
Do
w
o
dy
oparte
o
pra
w
a
logiki
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
C
6
Meto
da
zero
jedynk
o
w
a
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
D
6
Diagram
y
V
enna
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
E
6
wi zenia
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
F
6
Zadania
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
G
Pra
w
a
algebry
zbioró
w
☛
u v w
Suma,
przekró
j
i
ró»ni a
symetry zna
s¡
ª¡ zne,
tzn.
dla
do
w
oln
y
h
zbioró
w
,
,
pra
wdziw
e
s¡
(u ∪ v) ∪ w = u ∪ (v ∪ w) (u ∩ v) ∩ w = u ∩ (v ∩ w) (u ÷ v) ÷ w = u ÷ (v ÷ w) ró
wno± i
,
i
.
☛
u v
Suma,
przekró
j
i
ró»ni a
symetry zna
s¡
przemienne,
tzn.
dla
do
w
oln
y
h
zbioró
w
,
pra
wdziw
e
s¡
u ∪ v = v ∪ u u ∩ v = v ∩ u
u ÷ v = v ÷ u
ró
wno± i
,
i
.
☛
u v w
Suma
i
przekró
j
s¡
rozdzielne
wzgldem
siebie,
tzn.
dla
do
w
oln
y
h
zbioró
w
,
,
pra
wdziw
e
s¡
(u ∪ v) ∩ w = (u ∩ w) ∪ (v ∩ w) (u ∩ v) ∪ w = (u ∪ w) ∩ (v ∪ w) ró
wno± i
i
.
☛
u
u ∪ u =
Suma
i
przekró
j
s¡
op
era jami
idemp
oten
tn
ymi,
tzn.
dla
k
a»dego
zbioru
za
ho
dzi
ró
wno±¢
u ∩ u = u; ró»ni a symetry zna nie jest opera j¡ idempotentn¡.
☛ Ró»ni a zbiorów nie ma »adnej z powy»szy h wªasno± i; speªnia ona jednak tzw. prawa de Morgana: u \ (v ∪ w) = (u \ v) ∩ (u \ w)
u \ (v ∩ w) = (u \ v) ∪ (u \ w)
i
.
☛
u v
u ⊆ v u ∩ v = u u ∪ v = v
Dla
do
w
oln
y
h
zbioró
w
,
nastpuj¡ e
w
arunki
s¡
ró
wno
w
a»ne:
,
,
i
u \ v = ∅; prawdziwe s¡ ponadto nastpuj¡ e implika je:
x ⊆ u
y ⊆ v
x ∪ y ⊆ u ∪ v
x ∩ y ⊆ u ∩ v
je±li
i
,
to
i
;
u ⊆ v
v ⊆ w
u ⊆ w
je±li
i
,
to
;
u ⊆ w
v ⊆ w
u ⊆ v
w \ v ⊆ w \ u
je±li
i
,
to
wtedy
i
t
ylk
o
wtedy
,
gdy
.
6
6
.
Algebra
zbioró
w
A
Meto
dy
do
w
o
dzenia
☛ Istniej¡ trzy podstawowe metody dowodzenia praw algebry zbiorów: wykorzystanie praw logiki, metoda zero
jedynk
o
w
a
i
diagram
y
V
enna.
☛ Dowody oparte o prawa logiki to najbardziej wymagaj¡ a, ale i najbardziej uniwersalna metoda dowodzenia
pra
w
algebry
zbioró
w
zakres
jej
zastoso
w
a«
jest
zna znie
szerszy
ni»
p
ozostaªy
h
meto
d.
☛ Metoda zerojedynkowa znajduje zastosowanie przy badaniu zale»no± i pomidzy wyra»eniami zbudo-
w
an
ymi
ze
zmienn
y
h,
na
wiasó
w
i
znak
ó
w
op
era ji
teoriomnogo± io
wy
h.
☛ Diagramy Venna to gra zna wersja metody zerojedynkowej; zakres jej zastosowa« jest taki sam, jak meto
dy
zero
jedynk
o
w
ej.
6
6
.
Algebra
zbioró
w
B
Do
w
o
dy
oparte
o
pra
w
a
logiki
☛ Dowody oparte o prawa logiki przeprowadza si w opar iu o aksjomat ekstensjonalno± i, prawa ra-
h
unku
zda«
i
kw
an
t
yk
atoró
w:
u = v
u ⊆ v
v ⊆ u
u ⊆ v
ab
y
wyk
aza¢,
»e
do
w
o
dzi
si,
»e
i
;
ab
y
wyk
aza¢,
»e
,
do
w
o
dzi
si,
»e
dla
x
x ∈ u ⇒ x ∈ v
k
a»dego
pra
wdziw
a
jest
implik
a ja
;
x ∈ u ⇒ x ∈ v
x
u
ab
y
wyk
aza¢,
»e
,
zakªadam
y
,
»e
nale»y
do
i
do
w
o
dzim
y
,
k
orzysta
j¡
z
pra
w
logiki,
x
v
»e
nale»y
do
.
☛
(u ∪ v) ∩ w = (u ∩ w) ∪ (v ∩ w)
Dziaªanie
tej
meto
dy
zademonstrujem
y
na
przykªadzie
ró
wno± i
.
Ab
y
(u ∪ v) ∩ w ⊆ (u ∩ w) ∪ (v ∩ w) (u ∩ w) ∪ (v ∩ w) ⊆ (u ∪ v) ∩ w j¡
udo
w
o
dni¢,
wyk
a»em
y
,
»e
i
.
x ∈ (u ∪ v) ∩ w
(x ∈ u ∨ x ∈ v) ∧ x ∈ w
Je»eli
,
to
.
K
orzysta
j¡
z
rozdzielno± i
k
oniunk
ji
wzgldem
(x ∈ u ∧ x ∈ w) ∨ (x ∈ v ∧ x ∈ w)
x ∈ (u ∩ w) ∪ (v ∩ w)
alternat
ywy
otrzym
ujem
y
,
sk
¡d
.
x ∈ (u ∩ w) ∪ (v ∩ w)
(x ∈ u ∧ x ∈ w) ∨ (x ∈ v ∧ x ∈ w)
Je»eli
,
to
.
K
orzysta
j¡
z
rozdzielno± i
(x ∈ u ∨ x ∈ v) ∧ x ∈ w
x ∈ (u ∪ v) ∩ w
k
oniunk
ji
wzgldem
alternat
ywy
otrzym
ujem
y
,
sk
¡d
.
6
6
.
Algebra
zbioró
w
C
Meto
da
zero
jedynk
o
w
a
☛ Metoda zerojedynkowa korzysta z aksjomatu ekstensjonalno± i, sprowadzaj¡ pytanie o równo±¢ zbio-
u v
x ∈ u x ∈ v
ró
w
,
do
p
ytania
o
ró
wno
w
a»no±¢
zda«
,
.
☛
u ÷ (v ÷ w) (u ÷ v) ÷ w
Dziaªanie
tej
meto
dy
zademonstrujem
y
na
przykªadzie
wyra»e«
,
.
W
yk
a»em
y
,
x ∈ u ÷ (v ÷ w) x ∈ (u ÷ v) ÷ w
»e
s¡
one
sobie
ró
wne
do
w
o
dz¡ ,
»e
zdania
,
s¡
ró
wno
w
a»ne.
☛ Tworzymy tabelk, w której pierwsze trzy kolumny wypeªniamy wszystkimi mo»liwymi warto± iami
x ∈ u x ∈ v
x ∈ w
zda«
,
i
.
☛
x ∈ v ÷ w x ∈ u ÷ (v ÷ w) x ∈ u ÷ v
P
ozostaªe
k
olumn
y
wyp
eªniam
y
w
arto± iami
logi zn
ymi
zda«
,
,
i
x ∈ (u ÷ v) ÷ w, obli zonymi na podstawie warto± i znajduj¡ y h si w pierwszy h trze h kolumna h.
☛
x ∈ u ÷ (v ÷ w) x ∈ (u ÷ v) ÷ w
Ab
y
st
wierdzi¢,
zy
zdania
,
s¡
ró
wno
w
a»ne,
wystar zy
teraz
spra
wdzi¢,
zy
o
dp
o
wiada
j¡ e
im
k
olumn
y
za
wiera
j¡
te
same
w
arto± i.
x ∈ u x ∈ v x ∈ w
x ∈ v ÷ w x ∈ u ÷ (v ÷ w)
x ∈ u ÷ v x ∈ (u ÷ v) ÷ w
0
0
0
0
0
0
0
.
.
.
1
1
1
0
1
0
1
6
6
.
Algebra
zbioró
w
D
Diagram
y
V
enna
☛
u \ (v ∪ w) (u \ v) ∩
Dziaªanie
meto
dy
diagramó
w
V
enna
zademonstrujem
y
na
przykªadzie
wyra»e«
,
(u \ w). Porównuj¡ i h diagramy, wyka»emy, »e s¡ one sobie równe.
☛
u v
w
Diagram
V
enna
dla
wyra»enia
zbudo
w
anego
ze
zbioró
w
,
i
p
o
wsta
je
p
oprzez
takie
naryso
w
anie
t
y
h
zbioró
w
na
pªasz zy¹nie,
»e:
u ∩ v ∩ w u ∩ v ∩ (R2 \ w) u ∩ (R2 \ v) ∩ w (R2 \ u) ∩ v ∩ w u ∩ (R2 \ v) ∩ (R2 \ w)
k
a»dy
ze
zbioró
w
,
,
,
,
,
(R2 \ u) ∩ v ∩ (R2 \ w) (R2 \ u) ∩ (R2 \ v) ∩ w (R2 \ u) ∩ (R2 \ v) ∩ (R2 \ w)
,
i
jest
sp
ó
jn
y
i
niepust
y;
zbiór
b
d¡ y
rozw
a»an
ym
wyra»eniem
jest
p
ok
oloro
w
an
y
jedn
ym
k
olorem,
a
aªa
reszta
pªasz zyzn
y
drugim.
u
v
u
v
u \ (v ∪ w)
w
(u \ v) ∩ (u \ w)
w
:
:
6
6
.
Algebra
zbioró
w
E