Fragment notatki:
II. Logika i teoria zbiorów
1. Elementy logiki matematycznej
Przedmiotem logiki jest badanie związków między zdaniami. Przez zdanie rozumiemy w logice
wyłącznie zdanie orzekające, które jest prawdziwe lub fałszywe. O zdaniu prawdziwym mówimy, że
ma ono wartość logiczną 1, natomiast o zdaniu fałszywym mówimy, że ma ono wartość logiczną 0.
Sama istota prawdy i fałszu nie należy do obszaru badań matematycznych.
Przykład 1. Zdanie
π jest liczbą niewymierną
jest prawdziwe, czyli ma wartość logiczną 1, natomiast zdanie
π jest liczbą naturalną
jest fałszywe, czyli ma wartość logiczną 0. Zdanie z języka potocznego
100 jest piękną liczbą
nie jest prawdziwe ani fałszywe, więc nie jest zdaniem w znaczeniu przyjętym w logice.
Zdania będziemy oznaczać małymi literami p, q, r,... W tekstach matematycznych występują
najczęściej zdania złożone, połączone funktorami zdaniotwórczymi:
∼
∨
∧
⇒
⇔
Symbol
∼p
p∨q
p∧q
p⇒q
p⇔q
negacją,
alternatywą,
koniunkcją,
implikacją (wynikaniem),
równoważnością.
Nazwa
negacja zdania p
alternatywa zdań p i q
koniunkcja zdań p i q
implikacja o poprzedniku p i następniku q
równoważność zdań p i q
Czytamy
nieprawda, że p
p lub q
piq
jeśli p, to q
p wtedy i tylko wtedy, gdy q
W zależności od wartości logicznych zdań p i q określone powyżej zdania mają wartości logiczne
określone w poniższych tabelach:
p
0
1
∼p
1
0
p
0
0
1
1
q
0
1
0
1
p∨q
0
1
1
1
p∧q
0
0
0
1
p⇒q
1
1
0
1
p⇔q
1
0
0
1
Z powyższych tabel wynika, że alternatywa dwóch zdań jest prawdziwa, gdy co najmniej jedno
ze zdań p, bądź q jest prawdziwe; koniunkcja jest prawdziwa jedynie wtedy, gdy oba zdania p i q
są prawdziwe. Implikacja, w której poprzednik jest prawdziwy a następnik fałszywy, jest fałszywa.
Logika i teoria zbiorów
Potocznie mówiąc, z prawdy nie może wynikać fałsz. Zauważmy jednak, że z fałszywego zdania może
wyniknąć zarówno prawda jak i fałsz.
Poznane zdania i funktory stanowią elementy tzw. rachunku zdań. W rachunku tym zdania mogą
być uważane za zmienne zdaniowe, gdyż przyjmują wartości logiczne 0 lub 1.
Prawem rachunku zdań (inaczej tautologią) nazywamy takie wyrażenie tego rachunku, które
staje się zdaniem prawdziwym przy dowolnym podstawieniu wartości logicznych za zmienne zdaniowe. Można powiedzieć, że tautologie to schematy zdań zawsze prawdziwych. Treść zdań, które
podstawiamy do tautoligii na miejsce zmiennych zdaniowych, nie ma żadnego wpływu na wartość
logiczną zdania jakie z niej otrzymujemy, gdyż warość ta jest zawsze równa 1.
Nazwa tautologii
Prawo podwójnego zaprzeczenia
Prawo wyłączonego środka
Prawo przechodniości implikacji
Prawo kontrapozycji
Prawo zaprzeczenia implikacji
Prawo de Morgana dla alternatywy
Prawo de Morgana dla koniunkcji
Zapis
∼ (∼ p)
p ∨ (∼ p)
(p ⇒ q) ∧ (q ⇒ r) ⇒ (p ⇒ r)
(p ⇒ q) ⇔ (∼ q) ⇒ (∼ p)
∼ (p ⇒ q) ⇔ p ∧ (∼ q)
∼ (p ∨ q) ⇔ (∼ p) ∧ (∼ q)
∼ (p ∧ q) ⇔ (∼ p) ∨ (∼ q)
Poza zdaniami, w matematyce posługujemy się często formami (funkcjami) zdaniowymi. Forma
zdaniowa p(x) jest to wyrażenie, które zawiera pewną zmienną (lub zmienne) i staje się zdaniem
logicznym (prawdziwym lub fałszywym), gdy w miejsce zmiennej podstawimy nazwę dowolnego
przedmiotu należącego do dziedziny tej formy.
Przykład 2. Nierówność
2x − 5 1
jest formą zdaniową. Jeśli za zmienną x podstawimy 0, to forma ta staje się zdaniem fałszywym
−5 1. Jeśli za zmienną x podstawimy 4, to forma ta staje się zdaniem prawdziwym 3 1.
Ważną rolę przy budowie zdań lub form zdaniowych spełniają tzw. kwantyfikatory.
Zwrot
dla każdego x takiego, że...
nazywamy kwantyfikatorem ogólnym lub dużym i oznaczamy symbolem
∀,
(1)
x
zaś zwrot
istnieje takie x, że...
nazywamy kwantyfikatorem szczegółowym lub małym i oznaczamy symbolem
∃.
(2)
x
Kwantyfikatory (1) i (2) odnoszą się do pewnego zakresu (zbioru wartości) zmiennej x w formie
zdaniowej p(x).
Przykład 3. Rozważmy formę zdaniową p(x), określoną następująco:
p(x) : x x2 .
Jeżeli teraz funkcję tę poprzedzimy dużym kwantyfikatorem, to otrzymamy zdanie
∀ x x2 .
x
15
Logika i teoria zbiorów
Możemy sie domyślić, że zakresem zmiennej x jest tu zbiór liczb rzeczywistych R. Powyższe wyrażenie
możemy więc napisać w postaci
∀ x x2 .
x∈R
Jest to oczywiście zdanie fałszywe, gdyż na przykład dla x = 2 nierówność x x2 nie zachodzi. Jeżeli
jednak użyjemy tu kwantyfikatora o ograniczonym zakresie, to może się zmienić wartość logiczna
naszego wyrażenia. Na przykład zdanie
∀
x x2
x∈(0,1)
jest prawdziwe.
Widzimy zatem, że jeżeli p(x) jest formą zdaniową, to wyrażenie ∀ p(x) czy też ∃ p(x) jest już
x
x
zdaniem logicznym, bowiem zmienna x została związana kwantyfikatorem.
Zdania i formy zdaniowe, funktory i kwantyfikatory stanowią elementy tzw. rachunku kwantyfikatorów. Podamy tu kilka przykładów tautologii rachunku kwantyfikatorów:
∀ p(x) ⇒ p(x0 ),
p(x0 ) ⇒ ∃ p(x),
x
x
przy czym x0 oznacza dowolny element z zakresu formy zdaniowej p(x).
A oto inne przykłady tautologii:
∀ p(x) ⇒ ∃ p(x),
x
x
∀ p(x) ∧ q(x) ⇔ ∀ p(x) ∧ ∀ q(x) ,
x
x
x
∃ p(x) ∨ q(x) ⇔ ∃ p(x) ∨ ∃ q(x) .
x
x
x
Następujące tautologie nazywamy prawami de Morgana dla kwantyfikatorów (lub prawami przeczenia kwantyfikatorów):
∼ ∀ p(x) ⇔ ∃ ∼ p(x),
x
x
∼ ∃ p(x) ⇔ ∀ ∼ p(x).
x
x
Przykład 4. Zdanie
∀ x2 x
x∈R
jest fałszywe, gdyż na przykład dla x =
1
2
1 2
2
zdanie
1
2
jest fałszywe. Natomiast zdanie
x2 x
∀
x∈(1,+∞)
jest prawdziwe.
Zdanie
∃ x2 x
x∈R
jest prawdziwe, gdyż na przykład 22 2. Natomiast zdanie
∃
x2 x
x∈(0,1)
jest fałszywe.
16
Logika i teoria zbiorów
2. Elementy teorii mnogości
Zbiór jest pojęciem pierwotnym, to znaczy takim, którego nie definiujemy. Pojęcie to opisują tak
zwane aksjomaty teorii mnogości. Zbiory oznaczamy dużymi literami alfabetu A, B,. . . Przedmioty,
które należą do danego zbioru nazywamy elementami. Dla oznaczenia, że x jest elementem zbioru
A piszemy1
x ∈ A.
Zbiór, do którego nie należy żaden element nazywamy zbiorem pustym i oznaczamy ∅. Zatem forma
zdaniowa x ∈ ∅ jest zawsze fałszywa. Jeśli element x nie należy do zbioru A, to piszemy x ∈ A i
/
czytamy: x nie należy do A.
Definicja 1. Niech X będzie ustalonym zbiorem. Zbiór wszystkich x ∈ X, przy których forma
zdaniowa p(x) jest zdaniem prawdziwym oznaczamy symbolem
{x ∈ X : p(x)}.
Działania na zbiorach pozostają w ścisłym związku z działaniami na zdaniach logicznych.
Definicja 2. Sumą zbiorów A i B nazywamy zbiór A ∪ B złożony z tych i tylko tych elementów,
które należą do co najmniej jednego spośród zbiorów A i B, to jest
x ∈ A ∪ B ⇔ x ∈ A ∨ x ∈ B.
Definicja 3. Iloczynem (częścią wspólną) zbiorów A i B nazywamy zbiór A ∩ B złożony z tych i
tylko tych elementów, które należą jednocześnie do obydwu zbiorów A i B, to jest
x ∈ A ∩ B ⇔ x ∈ A ∧ x ∈ B.
Definicja 4. Różnicą zbiorów A i B nazywamy zbiór A \ B złożony z tych i tylko tych elementów,
które należą do zbioru A i nie należą do zbioru B, to jest
x ∈ A \ B ⇔ x ∈ A ∧ x ∈ B.
/
Przykład 5. Niech A = {−2, 0, 1} i B = {1, 2, 3}. Wówczas A ∪ B = {−2, 0, 1, 2, 3}, A ∩ B = {1},
A \ B = {−2, 0}, B \ A = {2, 3}.
Definicja 5. Zbiory A i B, dla których A ∩ B = ∅ nazywamy zbiorami rozłącznymi. Nie posiadają
one wspólnych elementów.
Definicja 6. Zbiory A i B są równe (to znaczy identyczne), gdy mają te same emelenty, to jest
x ∈ A ⇔ x ∈ B.
Stąd każdy zbiór jest wyznaczony jednoznacznie przez swoje elementy.
Definicja 7. Mówimy, że zbiór A jest podzbiorem zbioru B (lub że A zawiera się w B), gdy każdy
element zbioru A jest także elementem zbioru B. Piszemy wtedy A ⊂ B. W jezyku logiki
A ⊂ B ⇔ (x ∈ A ⇒ x ∈ B).
Z podanej definicji wynika, że zbiór pusty jest podzbiorem każdego zbioru, gdyż implikacja o
poprzedniku fałszywym jest prawdziwa.
Definicja 8. Niech X będzie ustalonym zbiorem. Zbiór ten nazywamy przestrzenią, gdy rozważamy
jego podzbiory. Dopełnieniem podzbioru A przestrzeni X nazywamy podzbiór A przestrzeni X
określony wzorem
A = X \ A.
1
Znak ∈ pochodzi od włoskiego matematyka Giuseppe Peano (1858-1932) i jest pierwszą literą greckiego słowa
στ ι (jest).
17
Logika i teoria zbiorów
Podstawowe prawa rachunku zbiorów:
(1) A ∪ B = B ∪ A, A ∩ B = B ∩ A,
(2) (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C),
(3) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),
(4) A ∪ A = A, A ∩ A = A,
(5) A ∪ ∅ = A, A ∩ ∅ = ∅,
(6) (A ∪ B) = A ∩ B , (A ∩ B) = A ∪ B ,
(7) (A ) = A,
(8) A ⊂ A ∪ B, A ∩ B ⊂ A, A \ B ⊂ A.
Definicja 9. Parą uporządkowaną (a, b) nazywamy zbiór postaci2
(a, b) = {{a}, {a, b}}.
Można pokazać, że (a, b) = (c, d) wtedy i tylko wtedy, gdy a = b i c = d.
Definicja 10. Iloczynem kartezjąńskim zbiorów A i B nazywamy zbiór A × B wszystkich par
uporządkowanych (x, y), gdzie x ∈ A, y ∈ B, to jest
(x, y) ∈ A × B ⇔ x ∈ A ∧ y ∈ B.
Iloczyn kartezjański X × X oznaczamy krótko X 2 .
Przykład 6. Niech A = {0, 1} i B = {−1, 0, 2}. Wtedy
A × B = {(0, −1), (0, 0), (0, 2), (1, −1), (1, 0), (1, 2)}.
2
Definicja ta pochodzi od polskiego matematyka Kazimierza Kuratowkiego (1896-1980)
18
... zobacz całą notatkę
Komentarze użytkowników (0)