Dr Andrzej Kmiecik
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 14

Rachunek zbiorów i relacji (2)

Istnieją różne struktury algebraiczne: grupoid, grupa, pierścień, ciało, algebra,
moduł, przestrzeń liniowa, krata. Są to zbiory z pewnymi działaniami,
scharakteryzowanymi aksjomatycznie.

W tym wykładzie należy pamiętać, że mówimy o algebrze zbiorów.

Interpretacja rachunku zdań w algebrze boole'a
Teoria 1

terminy pierwotne: +,

•

, , ', 0, 1, =

Teoria 2

rachunek zbiorów

interpretacja 1:

∪

,

∩

, –,

∅

, V, =

interpretacja 2:

∩

,

∪

, –, V,

∅

, =

Teoria 3

rachunek zdań

interpretacja 1:

∨

,

∧

, ~, 0: p

∧

~p, 1: p

∨

~p,

≡

interpretacja 2:

∧

,

∨

, ~, 0: p

∨

~p, 1: p

∧

~p,

≡

Aksjomaty Teorii 1 przechodzą w tezy lub aksjomaty Teorii 2

Ex.

x+x'=1

A

∪

–A=V

p

∨

~p

≡

1

x+y=y+x

A

∪

B=B

∪

A

p

∨

q

≡

q

∨

p

x+0=x

A

∪∅

=A

p

∨

(p

∧

~p)

≡

p

x

•

1=x

A

∩

V=A

p

∧

(p

∨

~p)

≡

p

Definicje pojęć, które nie należą do algebry zbiorów.
Def.: y

∈

{x}

≡

(y = x)

Zbiór {x} jest zbiorem jednostkowym

Def.: z

∈

{x, y}

≡

[(z = x)

∨

(z = y)]

Zbiór {x, y} jest zbiorem utworzonym z dwóch elementów x i y.

Def.: y

∈

{x

1

, ... , x

n

}

≡

[(y = x

1

)

∨

...

∨

(y = x

n

)]

Zbiór {x

1

, ... , x

n

} jest zbiorem utworzonym wyłącznie z elementów x

1

, ... , x

n

.

Zbiór, którego elementami są zbiory nazywa się rodziną zbiorów.

Twierdzenie

x = y

→

Λ

A

(x

∈

A

≡

y

∈

A)

Dowód

1.

x = y

z.

2.

x

∈

A

≡

x

∈

A

podstawienie prawa p

≡

p

3.

x

∈

A

≡

y

∈

A

ExI: 1,2

Λ

A

(x

∈

A

≡

y

∈

A)

Twierdzenie

Λ

A

(x

∈

A

≡

y

∈

A)

→

x=y

Dowód

1.

Λ

A

(x

∈

A

≡

y

∈

A)

z.

2.

x

∈

{y}

≡

y

∈

{y}

O

Λ

: 1

3.

x=y

≡

y=y

2, definicja zbioru jednostkowego,

reguła ekstensjonaności dla rachunku zdań.

x=y

3, y=y

Stąd następujące twierdzenie
Twierdzenie

1

x = y

≡

Λ

A

(x

∈

A

≡

y

∈

A)

Dwa indywidua są identyczne wtw, gdy dla dowolnego zbioru bądź
jednocześnie są jego elementami, bądź jednocześnie nie są jego elementami.
Twierdzenie to może służyć za definicję identyczności indywiduów.

Zwróćmy uwagę, że w rachunku kwantyfikatorów dowodzi się twierdzenia

2

x = y

≡

Λ

x

(A(x)

≡

A(y))

Zgodnie z tym przedmiotu x, y są identyczne wtedy i tylko wtedy, gdy każda
cecha przysługująca dowolnemu z nich przysługuje też drugiemu.
Teza ta może być definicją identyczności. Ta myśl występuje też u Arystotelesa,
że przedmiotom identycznym przysługują te same własności. Podobnie uważał
Tomasz z Akwinu, przedmioty są identyczne, gdy to co przysługuje jednemu to
przysługuje drugiemu.

Wg Leibniza przedmioty idemntyczne nie różnią się żadną cechą

(principium identitatis indiscernibilium)

1

Słupecki, borkowski, Elementy logiki matematycznej i teorii mnog9oścu, s. 141, T. 1.5.

2

Słupecki, borkowski, Elementy logiki matematycznej i teorii mnog9oścu, s. 130, T. VI.

Te dwa twierdzenia są analogiczne. Różnią się tylko tym, że w jednym mówimy
o zbiorach, a w drugim o własnościach. Istnieje też między nimi ściślejszy
związek, gdyż każde z nich można udowodnić przypomocy drugiego

3

.

Twierdzenie

A

⊂

1

Każdy zbiór indywiduów jest podzbiorem zbioru pełnego.
Dowód

1.

x

∈

1

→

(x

∈

A

→

x

∈

1)

teza p

→

(q

→

p)

2.

x

∈

1

aksjomat algebry zbiorów

3.

x

∈

A

→

x

∈

1

1, 2

Λ

x

(x

∈

A

→

x

∈

1)

3, definicja zawierania się zbiorów.

Twierdzenie
Zbiór pusty jest modułem dodawania zbiorów

A

∪

∅

= A

Twierdzenie

A

∩

1 = A

Zbiór pełny jest modułem mnożenia zbiorów

(Dowody zob. Słupecki, Borkowski, Elementy, s. 143.)

Lemat 1 (dowód zob. Borkowski, Logika formalna, s. 169)

{x} = {y}

≡

x=y

Lemat 2 (dowód zob. Borkowski, Logika formalna, s. 170)

{x,y} = {z,u}

≡

[(x=z

∧

y=u)

∨

(y=z

∧

x=u)]

Lemat 3

[{x,y} = {z,u}

∧

(x=z)]

→

y=u

Dowód (zob. Borkowski, Logika formalna, s. 169)

1.

{x,y} = {z,u}

z.

2.

x=z

z.

3.

y

≠

u

zdn.

4.

y=z

∨

y=u

y

∈

{x,y}

y

∈

{x: W(x)

≡

W(y)} – prawo eliminacji operatora

abstrakcji

3

Słupecki, borkowski, Elementy logiki matematycznej i teorii mnog9oścu, s. 162, § 5.

A=B

≡

Λ

x

(x

∈

A

≡

x

∈

B) tw., definicja zbioru

2-elementowego

5.

y=z

OA: 3,4

6.

x=y

2,5

7.

u=x

∨

u=y

u

∈

{z,u}

y

∈

{x: W(x)

≡

W(y)} – prawo eliminacji operatora

abstrakcji

A=B

≡

Λ

x

(x

∈

A

≡

x

∈

B) tw., definicja zbioru

2-elementowego

8.

u=x

OA: 3,7

9.

y

≠

x

3,8

sprzeczność:

6,9

Twierdzenie

[{x,y} = {z,u}

≡

[(x=z

∧

y=u)

∨

(x=u

∧

y=z)]

Dowód (zob. Borkowski, Logika formalna, s. 170)
(a)
1.

{x,y} = {z,u}

2.

x=z

∨

x=u

x

∈

{x,y}

y

∈

{x: W(x)

≡

W(y)} – prawo eliminacji operatora

abstrakcji

A=B

≡

Λ

x

(x

∈

A

≡

x

∈

B) tw., definicja zbioru

2-elementowego

1.1 x=z

z.d.

1.2

y=u

lemat 3, 1, 1.1

1.3

x=z

∧

y=u

1.1, 1.2

2.1

x=u

z.d.

2.2

y=z

lemat 3, 1, 2.1

2.3

x=u

∧

y=u

2.1, 2.2

(x=z

∧

y=u)

∨

(x=u

∧

y=z)

1.1

→

1.3, 2.1

→

2.3, 2

p

→

r

q

→

s

p

∨

q

-----
r

∨

s

b)
1.

(x=z

∧

y=u)

∨

(x=u

∧

y=z)

z.

2.

{x,y}={x,y}

A=A

1.1

x=z

∧

y=u

z.d.

1.2

{x,y}={z,u}

OK:1.1, 1.1, 2

2.1

x=u

∧

y=z

z.d.

2.2

{x,y}={u,z}={z,u}

2.1, 2, definicja zbioru

jednoelementowego

{x,y}={z,u}

1.1

→

1.2, 2.1

→

2.2, 1

Dylemat konstrukcyjny
x=z

∧

y=u

→

{x,y}={z,u}

p

→

q

x=u

∧

y=z

→

{x,y}={u,z}={z,u}

s

→

q

(x=z

∧

y=u)

∨

(x=u

∧

y=z)

p

∨

s

-------
q

Def
Uporządkowaną parą <x,y> nazywamy zbiór {{x},{x,y}}

W teorii mnogości podstawą tej definicji jest aksjomat wyboru, mówiący, że
jeśli mamy rodzinę zbiorów, to można utworzyć nowy zbiór, wybierając z
każdego podzbioru po jednym elemencie.

Na podstawie tej definicji można udowodnić warunek równości par
uporządkowanych

Twierdzenie
Warunek równości par uporządkowanych
Jest to własność par uporządkowanych

<x,y> = <z,u> wttw, gdy (x=z)

∧

(y=u)

Dowód a)
1.

<x,y> = <z,u>

z.

2.

{{x},{x,y}}={{z},{z,u}}

1. def. pary uporządkowanej

3.

[{x,y} = {z,u}

≡

[(x=z

∧

y=u)

∨

(x=u

∧

y=z)]

Twierdzenie

4.

[{x}={z}

∧

{x,y}={z,u}]

∨

[{x}={z,u}

∧

{x,y}={z}], 2, 3

1.1

{x}={z}

∧

{x,y}={z,u}

z.d.

1.2

{x}={y}

≡

x=y

twierdzenie

1.3

x=z

1.1, 1.2

1.4 [{x,y} = {z,u}

∧

(x=z)]

→

y=u

twierdzenie (lemat 3)

1.5

y=u

1.4, 1.1, 1.3

2.1 {x}={z,u}

∧

{x,y}={z}

z.d.

2.2

A=B

≡

Λ

x

(x

∈

A

≡

x

∈

B)

twierdzenie

2.3

x=z

x

∈

{x,y}, 2.1, 2.2, def. zbioru {,}

2.4

y=z

y

∈

{x,y}, 2.1, 2.2, def. zbioru {,}

2.5

u=x

u

∈

{z,u}, 2.1, 2.2, def. zbioru {,}

2.8

y=u

2.4, 2.3, 2.5

(x=z)

∧

(y=u)

1.1

→

1.3

∧

1.5,

2.1

→

2.3

∧

2.8, 4

[{x}={z}

∧

{x,y}={z,u}]

→

[ x=z

∧

y=u]

[{x}={z,u}

∧

{x,y}={z}]

→

[x=z

∧

y=u]

[{x}={z}

∧

{x,y}={z,u}]

∨

[{x}={z,u}

∧

{x,y}={z}]

----------------------------------------------------------------

(x=z)

∧

(y=u)

p

→

s

q

→

s

p

∨

q

-------
s

Dowód b)
1.

(x=z)

∧

(y=u)

z.

2.

<x,y> = <x,y>

A=A

<x,y> = <z,u>

EI: 1,2

Def
Uporządkowaną trójką <a,b, c> nazywamy zbiór <<a,b>,c>

Ogólnie uporządkowaną n-tką (a

1

,..., a

n

> nazywamy zbiór

<<...<a

1

,a

2

>, a

3

>...>,a

n

>

Twierdzenie
Dwie pary są różne, gdy różnią się pierwszymi lub drugimi elementami

<x,y>

≠

<z,u>

≡

(x

≠

z)

∨

(y

≠

u)

Dowód
Na podstawie reguły negowania członów równoważności i negowania
koniunkcji.

Def.
Iloczyn Kartezjański dwóch zbiorów jest to zbiór par uporządkowanych

A x B = {<a,b>: a

∈

A

∧

b

∈

B}