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 p '" q (czytamy: p i q), przyjmujemy, \
e takie zdanie jest prawdziwe tylko wtedy, gdy oba zdania
sÄ… prawdziwe 2) alternatywa p (" q (czytamy: p lub q), przyjmujemy, \
e takie zdanie jest fałszywe tylko
wtedy, gdy oba zadnia sÄ… faÅ‚szywe 3) implikacja p Ò! q (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ść: p Ô! q (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. 1 d" 2 jest równowa\
na koniunkcji 1 < 2 '"1 = 2 . A zatem jest ona prawdziwa, poniewa\

prawdziwe jest jedno z dwóch zdań tej koniunkcji.
Podwójna nierówność np. 1 < 2 < 3 jest równowa\
na koniunkcji 1 < 2 '" 2 < 3 .
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ć p Ò! q - p to zaÅ‚o\
enie, zaÅ› q - teza, q jest warunkiem koniecznym dla p (je\
eli
zdanie q Ò! p 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 p Ò! q i q Ò! p sÄ… prawdziwe, to czÄ™sto tworzymy z nich jedno twierdzenie postaci
p Ô! q
Twierdzenie p Ò! q mo\
emy dowodzić wprost (zdanie p przekształcamy tak długo, a\
uzyskamy q) lub nie
wprost (bierzemy wówczas zaprzeczenie implikacji czyli zdanie p'" ~ q i staramy się uzyskać sprzeczność).
Mo\
emy równie\
wykazać prawdziwość zdania ~ q Ò!~ p , bÄ™dzie to oznaczaÅ‚o, \
e p Ò! q 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 x2 + x = 2 jest formÄ… zdaniowÄ… zmiennej x, zaÅ› wyra\
enia
2
x2 + x = 2 są zdaniami logicznymi. Pierwsze z nich, które czytamy: dla ka\
dego x
"x + x = 2 oraz "
x"R x"R
nale\
ącego do zbioru liczb rzeczywistych x2 + x = 2 , jest fałszywe (bo np. dla x = 0 uzyskujemy fałsz),
natomiast drugie, które czytamy: istnieje x nale\
Ä…cy do zbioru liczb rzeczywistych taki, \
e x2 + x = 2 , jest
prawdziwe (prawdÄ™ uzyskujemy np. dla x = 1).
Zaprzeczenia zdań z kwantyfikatorami tworzymy następująco: kwantyfikatory zmieniamy na przeciwne oraz
2
bierzemy zaprzeczenie formy zdaniowej np. ~ + x = 2 Ô! x2 + x `" 2. Zaprzeczeniem = jest `" , " jest
"x "
x"R x"R
", < jest e" , d" 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 A ‚" B 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 A = B ) oznacza, \
e A ‚" B i jednoczeÅ›nie B ‚" A. 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
A
oznaczamy przez P(A) lub 2 (drugie oznaczenie bierze siÄ™ stÄ…d, \
e 2A = 2A ).
Kolejność elementów w zbiorze nie ma znaczenia. Je\
eli zapisujemy go wymieniajÄ…c elementy (czynimy to
u\
ywajÄ…c klamer), to np. {a,b} oznacza to samo, co {b, a}. Umawiamy siÄ™ te\
, \
e powtarzanie elementów nie
zmienia zawartości zbioru np. {a, a,b} oznacza to samo, co {a,b}.
Często szczególnie większe zbiory zapisujemy za pomocą odpowiedniego warunku: A = {x : p(x)} (A jest
zbiorem x-ów takich, \
e p(x) (podajemy warunek czyli formę zdaniową, którą elementy spełniają). Np.
A = {x : x2 < x} (zbiór x-ów takich, \
e x2 < x ). Bardziej dokładnie powinno być napisane A = {x " R : x2 < x}
lub A = {x : x " R '" x2 < x}.
Je\
eli A ‚" B , 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 *" ): A *" B = {x : x " A (" x " B}; suma zbiorów
zawiera więc wszystkie elementy jednego i drugiego zbioru; własności: A *" A = A , A *" B = B *" A ,
A *" " = A , A *" (B *" C) = (A *" B)*" C = A *" B *" C 2) mno\
enie (oznaczamy przez )" ):
A )" B = {x : x " A '" x " B}, 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 )" " = " ,
A )"(B )" C) = (A )" B))" C = A )" B )" C 3) odejmowanie (oznaczamy przez \ ): A \ B = {x : x " A '" x " B}
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 A `" B , to A \ B `" B \ A 4) odejmowanie symetryczne
(oznaczamy przez ): A B = (A \ B)*" (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
×): A× B = {(x, y): x " A '" y " B}; 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
A `" B , to A× B `" B × A (wynika to z tego, \
e je\
eli a `" b , to (a,b) `" (b, a))
Przedziały liczbowe: 1) (a,b) = {x " R : a < x < b} 2) (a,b = {x " R : a < x d" b} 3) a,b) = {x " R : a d" x < b}
4) a,b = {x " R : a d" x d" b} 5) (- ",b) = {x " R : x < b} 6) (- ",b = {x " R : x d" b} 7) a,") = {x " R : x e" 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.