Elementy logiki i teorii mnogości

Przyjmujemy, że każde zdanie logiczne jest albo prawdziwe albo fałszywe. Mając podane jakieś zdanie
możemy utworzyć jego zaprzeczenie (będzie miało przeciwne wartości logiczne) i symbolicznie zapisać np.
tak

p

~

(czytamy: nieprawda, że p). Mając co najmniej dwa zdania możemy utworzyć zdania złożone: 1)

koniunkcja

q

p

∧

(czytamy: p i q), przyjmujemy, że takie zdanie jest prawdziwe tylko wtedy, gdy oba zdania

są prawdziwe 2)

alternatywa

q

p

∨

(czytamy: p lub q), przyjmujemy, że takie zdanie jest fałszywe tylko

wtedy, gdy oba zadnia są fałszywe 3)

implikacja

q

p ⇒

(czytamy: jeżeli p to q), p nazywamy poprzednikiem

zaś q następnikiem implikacji; zdanie to jest fałszywe tylko wtedy, gdy poprzednik jest prawdziwy a następnik
fałszywy (z prawdy nigdy nie może wynikać fałsz) 4)

równoważność:

q

p

⇔

(czytamy: p wtedy i tylko

wtedy, gdy q), takie zdanie jest prawdziwe, gdy oba mają tę samą wartość logiczną
Zaprzeczeniem koniunkcji dwóch zdań jest alternatywa zaprzeczeń, zaprzeczeniem alternatywy koniunkcja
zaprzeczeń (są to tzw.

prawa de Morgana).

Nierówność np.

2

1

≤

jest równoważna koniunkcji

2

1

2

1

=

∧

<

. A zatem jest ona prawdziwa, ponieważ

prawdziwe jest jedno z dwóch zdań tej koniunkcji.
Podwójna nierówność np.

3

2

1

<

<

jest równoważna koniunkcji

3

2

2

1

<

∧

<

.

Pojęcia pierwotne – takie, których się nie definiuje np. nie istnieje definicja zbioru. Ich własności są określone
przez odpowiedni układ aksjomatów. Pozostałe pojęcia są definiowane za pomocą pojęć pierwotnych i innych
już zdefiniowanych
Aksjomaty – zdania orzekające, których prawdziwości się nie weryfikuje (uznajemy, że są prawdziwe) np. w
geometrii euklidesowej aksjomatem jest stwierdzenie, że przez punkt poza prostą przechodzi dokładnie jedna
prosta do niej równoległa (jest to równoważne temu, że suma miar kątów w trójkącie wynosi 180 stopni).
Pozostałe zdania orzekające nazywamy

twierdzeniami i dowodzimy je korzystając z odpowiednich reguł

dowodzenia, aksjomatów i twierdzeń już wykazanych. Układy aksjomatów mogą być w zasadzie dowolne byle
tylko spełniały pewne reguły np. nie możemy z nich wywieść dwóch zaprzeczających sobie twierdzeń.
Twierdzenia mają postać

q

p ⇒

- p to

założenie, zaś q - teza, q jest warunkiem koniecznym dla p (jeżeli

zdanie

p

q ⇒

jest fałszywe, to q nie jest

warunkiem dostatecznym dla p, jeżeli prawdziwe to jest

dostatecznym), jeżeli q nie jest spełnione, to p również
Tw.: Jeżeli liczba naturalna jest podzielna przez 24, to jest podzielna przez 4 i 6 (podzielność przez 4 i 6 –
warunek konieczny, ale nie dostateczny podzielności przez 24)
Tw.: Jeżeli liczba naturalna jest podzielna przez 12, to jest podzielna przez 4 i 3 (podzielność przez 4 i 3 –
warunek konieczny i dostateczny podzielności przez 12)
Jeżeli obie implikacje

q

p ⇒

i

p

q ⇒

są prawdziwe, to często tworzymy z nich jedno twierdzenie postaci

q

p

⇔

Twierdzenie

q

p ⇒

możemy dowodzić

wprost (zdanie p przekształcamy tak długo, aż uzyskamy q) lub nie

wprost (bierzemy wówczas zaprzeczenie implikacji czyli zdanie

q

p

~

∧

i staramy się uzyskać sprzeczność).

Możemy również wykazać prawdziwość zdania

p

q

~

~

⇒

, będzie to oznaczało, że

q

p ⇒

też jest prawdziwe.

Bardzo rozpowszechnionymi wyrażeniami są

formy zdaniowe, czyli wyrażenia posiadające zmienne, mające

tę własność, że jeżeli w miejsce zmiennych podstawimy konkretne wartości, to uzyskamy zdanie logiczne.
Formami zdaniowymi są np. równania, nierówności, układy równań. Bardziej złożone formy zdaniowe
tworzymy używając tych samych symboli logicznych jak w przypadku zdań logicznych. Układy równań często
zapisuje się używając klamry – zastępuje ona koniunkcję.
Z formy zdaniowej możemy również utworzyć zdanie logiczne używając

kwantyfikatorów. Są dwa rodzaje:

ogólny oznaczany symbolem

∧

lub

∀

(czytamy: dla każdego) oraz

szczegółowy oznaczany symbolem

∨

lub

∃

(czytamy: istnieje). Np. wyrażenie

2

2

=

+

x

x

jest formą zdaniową zmiennej x, zaś wyrażenia

2

2

=

+

∀

∈

x

x

R

x

oraz

2

2

=

+

∃

∈

x

x

R

x

są zdaniami logicznymi. Pierwsze z nich, które czytamy: dla każdego x

należącego do zbioru liczb rzeczywistych

2

2

=

+

x

x

, jest fałszywe (bo np. dla

0

=

x

uzyskujemy fałsz),

natomiast drugie, które czytamy: istnieje x należący do zbioru liczb rzeczywistych taki, że

2

2

=

+

x

x

, jest

prawdziwe (prawdę uzyskujemy np. dla

1

=

x

).

Zaprzeczenia zdań z kwantyfikatorami tworzymy następująco: kwantyfikatory zmieniamy na przeciwne oraz
bierzemy zaprzeczenie formy zdaniowej np.

2

2

~

2

2

≠

+

⇔

=

+

∃

∀

∈

∈

x

x

x

x

R

x

R

x

. Zaprzeczeniem = jest

≠

,

∈

jest

∉

, < jest

≥

,

≤

jest > itd.

Teoria mnogości zajmuje się zbiorami. Zbiór i należenie elementu do zbioru (oznaczane przez

∈

) są

pojęciami pierwotnymi. Zbiory i elementy można sobie oznaczać dowolnie, ale często umowa jest taka, że
elementy oznaczamy małymi literami zaś zbiory dużymi. Wyrażenie

A

a

∈

czytamy: element a należy do

zbioru A, zaś

A

a

∉

: element a nie należy do zbioru A.

Ilość elementów zbioru (

moc zbioru) oznaczamy rysując dwie kreski nad zbiorem czyli np. A - moc zbioru A

Jeden zbiór może

zawierać się w drugim (oznaczamy to symbolem

⊂

). Wyrażenie

B

A

⊂

czytamy: zbiór A

jest zawarty w zbiorze B. Takie zawieranie oznacza, że wszystkie elementy ze zbioru A są jednocześnie w B,
jest przy tym możliwe, że zbiór B posiada jeszcze jakieś inne elementy, które w A nie występują. Równość
zbiorów (co zapisujemy

B

A

=

) oznacza, że

B

A

⊂

i jednocześnie

A

B

⊂

. Istnieje zbiór, który jest zawarty w

każdym: jest to

zbiór pusty (nie ma żadnych elementów) oznaczany symbolem

∅

. Każdy zbiór jest zawarty

sam w sobie (

A

A

⊂

). Zbiór wszystkich podzbiorów zbioru elementów nazywamy

zbiorem potęgowym i

oznaczamy przez

( )

A

P

lub

A

2 (drugie oznaczenie bierze się stąd, że

A

A

2

2

=

).

Kolejność elementów w zbiorze nie ma znaczenia. Jeżeli zapisujemy go wymieniając elementy (czynimy to
używając klamer), to np.

{ }

b

a,

oznacza to samo, co

{ }

a

b,

. Umawiamy się też, że powtarzanie elementów nie

zmienia zawartości zbioru np.

{

}

b

a

a ,

,

oznacza to samo, co

{ }

b

a,

.

Często szczególnie większe zbiory zapisujemy za pomocą odpowiedniego warunku:

( )

{

}

x

p

x

A

:

=

(A jest

zbiorem x-ów takich, że

( )

x

p

(podajemy warunek czyli formę zdaniową, którą elementy spełniają). Np.

{

}

x

x

x

A

<

=

2

:

(zbiór x-ów takich, że

x

x

<

2

). Bardziej dokładnie powinno być napisane

{

}

x

x

R

x

A

<

∈

=

2

:

lub

{

}

x

x

R

x

x

A

<

∧

∈

=

2

:

.

Jeżeli

B

A

⊂

, to możemy utworzyć

dopełnienie zbioru A w zbiorze B. Oznaczamy go przez A’ – składa się

ono z wszystkich elementów, które należą do B ale do A już nie.
Działania na zbiorach: 1) dodawanie (oznaczamy przez

∪

):

{

}

B

x

A

x

x

B

A

∈

∨

∈

=

∪

:

; suma zbiorów

zawiera więc wszystkie elementy jednego i drugiego zbioru; własności:

A

A

A

=

∪

,

A

B

B

A

∪

=

∪

,

A

A

=

∅

∪

,

(

) (

)

C

B

A

C

B

A

C

B

A

∪

∪

=

∪

∪

=

∪

∪

2)

mnożenie (oznaczamy przez

∩

):

{

}

B

x

A

x

x

B

A

∈

∧

∈

=

∩

:

, iloczyn zbiorów (inaczej: część wspólna) składa się z wszystkich elementów, które

należą jednocześnie do obu zbiorów; własności:

A

A

A

=

∩

,

A

B

B

A

∩

=

∩

,

∅

=

∩

'

A

A

,

∅

=

∅

∩

A

,

(

) (

)

C

B

A

C

B

A

C

B

A

∩

∩

=

∩

∩

=

∩

∩

3)

odejmowanie (oznaczamy przez \ ):

{

}

B

x

A

x

x

B

A

∉

∧

∈

=

:

\

różnica zbiorów składa się z tych elementów, które należą do pierwszego zbioru i nie należą do drugiego;
własności:

∅

=

A

A \

,

A

A

=

∅

\

,

∅

=

∅

A

\

, jeżeli

B

A

≠

, to

A

B

B

A

\

\

≠

4)

odejmowanie symetryczne

(oznaczamy przez ):

(

) (

)

A

B

B

A

B

A

\

\

∪

=

; różnica symetryczna zbiorów składa się z wszystkich

elementów obu zbiorów z wyłączeniem tych, które są wspólne 5)

mnożenie kartezjańskie (oznaczamy przez

×

):

( )

{

}

B

y

A

x

y

x

B

A

∈

∧

∈

=

×

:

,

; iloczyn kartezjański zbiorów składa się z par elementów takich, że

pierwszy element pary należy do pierwszego zbioru, a drugi do drugiego; własności:

∅

=

×

∅

=

∅

×

A

A

, jeżeli

B

A

≠

, to

A

B

B

A

×

≠

×

(wynika to z tego, że jeżeli

b

a

≠

, to

( ) ( )

a

b

b

a

,

,

≠

)

Przedziały liczbowe: 1)

( ) {

}

b

x

a

R

x

b

a

<

<

∈

=

:

,

2)

(

{

}

b

x

a

R

x

b

a

≤

<

∈

=

:

,

3)

) {

}

b

x

a

R

x

b

a

<

≤

∈

=

:

,

4)

{

}

b

x

a

R

x

b

a

≤

≤

∈

=

:

,

5)

(

) {

}

b

x

R

x

b

<

∈

=

∞

−

:

,

6)

(

{

}

b

x

R

x

b

≤

∈

=

∞

−

:

,

7)

) {

}

a

x

R

x

a

≥

∈

=

∞

:

,

8)

( ) {

}

a

x

R

x

a

>

∈

=

∞

:

,

9)

(

)

R

=

∞

∞

−

,

. Przedziały 1, 5 i 8 nazywamy

otwartymi, zaś 4, 6 i 7 domkniętymi.

Przedziały możemy zaznaczać na

osi liczbowej. Jeżeli koniec przedziału do niego należy (nawias ostry), to

odpowiadający mu punkt zamalowujemy, jeżeli koniec nie należy (nawias okrągły), to odpowiadający mu
punkt bierzemy w otwarte kółko.