1
Logika
Zdanie logiczne – takie, któremu moŜna przyporządkować jedną z dwóch wartości logicznych:
prawdę (oznaczaną przez 1) albo fałsz (0)
Zdania, które nie są logicznymi:
„Gdańsk jest uprzejmy” – bo miasto nie moŜe być uprzejme, „Sopot jest duŜy” – trudno się do tego
ustosunkować, zaleŜy względem jakiej miejscowości. „Po co ja to piszę” – tego zdradzić nie mogę, ale z
pewnością o Ŝadnym pytaniu nie da się powiedzieć, czy jest prawdziwe czy fałszywe. „I co teraz?” –
jeszcze nie wiem, ale to teŜ jest pytanie. „Dość juŜ tego wszystkiego!” – krzyczeć sobie moŜna, ale takich
wrzasków nikt nie oceni logicznie. „Gdybym tylko mógł to zrobić” – nie ja jeden tak sobie myślę, ale w
takiej formie to robiąc nie mówię ani prawdy ani fałszu.
Zdania, które są logiczne:
„Mam wszystko w tyle” – nie wiem czy to zdanie jest dostatecznie jasne, ale mogę o nim powiedzieć czy
jest prawdziwe. „Wyjadę do Krakowa na chwilę” – tu moŜna mieć pewne wątpliwości, ale gdy powiem
„Wyjadę jutro do Krakowa na chwilę” – wszystko będzie jasne. „Jestem kompletnie łysy” – bardzo
fałszywe, ale absolutnie logiczne. „W moim samochodzie leŜą duŜe irysy” – totalny fałsz chociaŜby z
tego powodu, Ŝe nie posiadam samochodu.
Ale to wszystko nic. Jak się później okaŜe zdaniami logicznymi są równieŜ takie, które normalnie
okrzyknęlibyśmy kosmiczną bzdurą: „jeŜeli 2>3, to w 1999 roku w Berlinie był Festiwal Miłości” –
mało, Ŝe logiczne, to jeszcze prawdziwe. „Skrzydła rosną nam u rąk lub kąty to nie trójkąty” – teŜ
prawda. „Jestem tu i jestem tam” – niestety fałsz. „Rosną mi dwie głowy wtedy i tylko wtedy, gdy
pomidor to owad matowy” – prawda!
Niełatwo jest wymyślać zdania logiczne, które miałyby związek z tak zwanym Ŝyciem. Równie
trudno oceniać logicznie te zdania, którymi się na co dzień posługujemy. Na szczęście (?) nasza precyzja
takiej oceny daleko odbiega od ścisłego ideału, ale dzięki temu na ogół mamy jakiś konkretny stosunek
do informacji, które do nas docierają nawet jeŜeli nie ma w nich za grosz sensu.
Pojedyncze zdania logiczne moŜemy sobie nazwać atomowymi. W ich przypadku trzeba
bezpośrednio przyporządkować jakąś wartość logiczną. Na szczęście nie jesteśmy skazani na
posługiwanie się tylko nimi. MoŜemy równieŜ tworzyć zdania złoŜone (jak np. „Jestem tu lub jestem
tam”). W logice dokładnie definiuje się za pomocą czego je tworzymy (za pomocą funktorów
zdaniotwórczych) i w jaki sposób oceniamy je logicznie. Do najwaŜniejszych i najczęściej uŜywanych
funktorów (moŜna teŜ je nazywać spójnikami) naleŜą: negacja, koniunkcja, alternatywa, alternatywa
wykluczająca, implikacja i równowaŜność. Zdania złoŜone składają się z pojedynczych (atomowych)
zdań, zatem ich wartości logiczne będą zaleŜne od wartości logicznych zdań atomowych (oznaczać je
będziemy małymi literami p, q, r, s, t itd.). Stad teŜ definiując funktory zdaniotwórcze tak naprawdę
określać będziemy wartości logiczne tworzonych za ich pomocą zdań.
1. Negacja (oznaczenie np.: ~)
Tabela ta mówi dokładnie tyle, Ŝe jeŜeli p jest prawdziwe, to ~p (nie prawda, Ŝe p) jest
fałszywe, jeŜeli p fałszywe, to ~p prawdziwe
„Nieprawda, Ŝe Ziemia stoi na duŜym Ŝółwiu” – zdanie prawdziwe, bo jest negacją
fałszywego zdania „Ziemia stoi na duŜym Ŝółwiu” (fałszywego bynajmniej nie z powodu podawania
błędnych gabarytów Ŝółwia lub złego określenia rodzaju podtrzymującego nas zwierzaka).
2. Koniunkcja (oznaczenie:
∧
)
Zgodnie z tabelą zdanie
q
p
∧
(p i q) jest prawdziwe tylko wtedy, gdy oba zdania p
oraz q są prawdziwe
„Jestem tu i 2<3” – pozornie bezsensowne zdanie to jest jednak jak najbardziej
prawdziwe, bowiem zarówno zdanie „Jestem tu” jak i „2<3” są prawdziwe, więc
ich koniunkcja równieŜ taką jest.
p
~p
1
0
0
1
p
q
q
p
∧
1
1
1
1
0
0
0
1
0
0
0
0
2
3. Alternatywa: (oznaczenie:
∨
)
Alternatywa dwóch zdań jest fałszywa tylko w jednym przypadku: gdy oba zdania
są fałszywe.
q
p
∨
czytamy jako „p lub q”
„Skrzydła nam rosną u rąk lub kąty to nie trójkąty” – skrzydła co prawda u rąk nam
nie rosną, ale kąty to z pewnością nie trójkąty – prawdziwość tego jednego zdania
powoduje, Ŝe cała alternatywa równieŜ jest prawdziwa. Z tych samych powodów
prawdziwe jest równieŜ zdanie „2 jest mniejsze lub równe 2” (
2
2
2
2
=
∨
<
), które zapisujemy krótko:
„
2
2
≤
”.
4. Implikacja (oznaczenie: ⇒ )
W zdaniu
q
p ⇒
(p to q) p nazywamy
poprzednikiem implikacji, zaś q
następnikiem. Implikacja jest fałszywa tylko wtedy, gdy poprzednik jest
prawdziwy a następnik fałszywy
„JeŜeli to, co na tej stronie napisałem jest prawdą, to w Pizie nie ma Ŝadnej
krzywej wieŜy” – w Pizie jak wiadomo jedna z wieŜ naprawdę z lekka się skrzywiła (następnik jest
fałszywy), mam nadzieję, Ŝe nie ma szans, by to, co tutaj jest napisane było choćby w części bzdurą
(poprzednik jest prawdziwy) więc cała implikacja jest fałszywa.
5.
RównowaŜność (oznaczenie:
⇔
)
RównowaŜność dwóch zdań jest prawdziwa tylko wtedy, gdy oba mają te samą
wartość logiczną
q
p
⇔
- p wtedy i tylko wtedy, gdy q
„Mam trzy nogi wtedy i tylko wtedy, gdy na Ŝadnym baranim łbie nigdy nie rosły
rogi” – ilość moich nóg z pewnością nie przekracza dwóch, moja uboga intuicja zoologiczna podpowiada
mi, Ŝe przynajmniej jeden z baranów posiadał kiedyś jakieś rogi. Skoro więc oba zdania są fałszywe
równowaŜność jest prawdziwa. W praktyce rzadko zdarza nam się mówić „wtedy i tylko wtedy, gdy”:
zamiast „Jestem tu wtedy i tylko wtedy, gdy on tu jest” mówimy krótko „Jestem tu, gdy on jest” starając
się akcentować fragment „gdy on jest”. Akcentując fragment „jestem tu” raczej mamy na myśli
implikację „JeŜeli on tu jest, to ja tu jestem”.
6.
Alternatywa wykluczająca (oznaczenie
∨
)
q
p
∨
- p albo q
Albo tym się róŜni od lub, Ŝe przy alternatywie oba zdania mogą być prawdziwe
by całość była prawdą, przy prawdziwej alternatywie wykluczającej prawdziwe
moŜe być (i musi) tylko jedno zdanie
„Nie mam skrzydeł u rąk albo kąty to nie trójkąty” – zdanie to jest fałszywe, bo ani mi skrzydła rosną u
rąk ani teŜ jakikolwiek kąt trójkątem nie jest. Ale juŜ zdanie „Nie mam skrzydeł u rąk lub kąty to nie
trójkąty” dokładnie z tych samych powodów jest prawdziwe.
Korzystając z funktorów zdaniotwórczych oraz nawiasów moŜemy tworzyć zdania jeszcze
bardziej złoŜone. Ich wartości logiczne ustalamy korzystając z wartości logicznych zdań atomowych oraz
podanych wyŜej zdań złoŜonych, stosując dość prostą metodę (nazwijmy ją zero-jedynkową), która
wygląda następująco:
oceńmy wartość logiczną zdania np.
(
)
[
]
{
}
p
q
p
q
p
⇔
∨
∧
⇒
~
~
p
q
q
p
∨
1
1
1
1
0
1
0
1
1
0
0
0
p
q
q
p ⇒
1
1
1
1
0
0
0
1
1
0
0
1
p
q
q
p
⇔
1
1
1
1
0
0
0
1
0
0
0
1
p
q
q
p
∨
1
1
0
1
0
1
0
1
1
0
0
0
3
Z ostatniej kolumny wynika, Ŝe zdanie to jest prawdziwe tylko wtedy, gdy prawdziwe jest p i
fałszywe q. Wartości logiczne w poszczególnych kolumnach powstały następująco:
z tabeli negacji z tabeli koniunkcji z tabeli implikacji z tabeli negacji
z tabeli alternatywy
z tabeli równowaŜności
Okazuje się, Ŝe tą metodą moŜna ocenić wartości logiczne nawet długich zdań, z których nic lub
prawie nic nie rozumiemy. Np. takie zdanie: „JeŜeli izometria ma trzy niewspółliniowe punkty stałe, to
kaŜdy punkt płaszczyzny jest punktem stałym tej izometrii, a jeŜeli kaŜdy punkt płaszczyzny jest punktem
stałym przekształcenia, to przekształcenie jest toŜsamościowe, a więc jeśli izometria ma trzy
niewspółliniowe punkty stałe, to jest przekształceniem toŜsamościowym płaszczyzny”. MoŜna spróbować
od razu ustalić wartość logiczną tego zdania, ale moŜna to zrobić równieŜ tak: niech p oznacza zdanie
„Izometria ma trzy niewspółliniowe punkty stałe”, q – „KaŜdy punkt płaszczyzny jest punktem stałym
izometrii”, r – „Przekształcenie jest toŜsamościowe”, wówczas całe nasze zdanie wygląda następująco:
(
) (
)
[
]
(
)
r
p
r
q
q
p
⇒
⇒
⇒
∧
⇒
(zauwaŜmy, Ŝe „a jeŜeli” oznacza to samo, co „i jeŜeli” zaś „a więc” to
samo, co „to”; przy okazji widać tu chyba sens stosowania symboliki w matematyce – dzięki niej pewne
długie zdania moŜna zapisać w znacznie krótszy sposób). Oceńmy wartość logiczną tego zdania:
p q r
q
p ⇒
r
q ⇒
(
) (
)
r
q
q
p
⇒
∧
⇒
r
p ⇒
(
) (
)
[
]
(
)
r
p
r
q
q
p
⇒
⇒
⇒
∧
⇒
1 1 1
1
1
1
1
1
1 1 0
1
0
0
0
1
1 0 1
0
1
0
1
1
1 0 0
0
1
0
0
1
0 1 1
1
1
1
1
1
0 1 0
1
0
0
1
1
0 0 1
1
1
1
1
1
0 0 0
1
1
1
1
1
Z ostatniej kolumny wynika, Ŝe zdanie to jest prawdziwe bez względu na to jakie wartości
logiczne maja zdania p, q i r. Nawet jeŜeli nie rozumie się tych zdań i nie umie ocenić ich wartości
logicznych moŜna ocenić wartość logiczną całości. Zdania, które w ten sposób da się ocenić (są
prawdziwe bez względu na wartości logiczne występujących w nim zdań atomowych) nazywamy
tautologiami. Niektóre z nich noszą swoje nazwy i są w matematyce często stosowane. Wypiszmy
waŜniejsze z nich:
p
q
~p
p
q
~
∧
(
)
p
q
p
~
∧
⇒
~q
(
)
[
]
q
p
q
p
~
~
∨
∧
⇒
(
)
[
]
{
}
p
q
p
q
p
⇔
∨
∧
⇒
~
~
1
1
0
0
0
0
0
0
1
0
0
0
0
1
1
1
0
1
1
1
1
0
1
0
0
0
1
0
1
1
1
0
p
~p
1
0
1
0
0
1
0
1
q
~p
p
q
~
∧
1
0
0
0
0
0
1
1
1
0
1
0
p
p
q
~
∧
(
)
p
q
p
~
∧
⇒
1
0
0
1
0
0
0
1
1
0
0
1
q
~q
1
0
0
1
1
0
0
1
(
)
p
q
p
~
∧
⇒
~q
(
)
[
]
q
p
q
p
~
~
∨
∧
⇒
0
0
0
0
1
1
1
0
1
1
1
1
(
)
[
]
q
p
q
p
~
~
∨
∧
⇒
p
(
)
[
]
{
}
p
q
p
q
p
⇔
∨
∧
⇒
~
~
0
0
0
0
1
1
1
0
0
1
1
0
4
1.
(
) (
)
[
]
(
)
r
p
r
q
q
p
⇒
⇒
⇒
∧
⇒
- prawo przechodniości implikacji
2.
(
)
(
) (
)
[
]
p
q
q
p
q
p
⇒
∧
⇒
⇔
⇔
3.
(
) (
)
q
p
q
p
~
~
∧
⇔
⇒
- prawo
zaprzeczenia implikacji
4.
(
) (
)
p
q
q
p
~
~
⇒
⇔
⇒
- prawo
kontrapozycji
5.
(
) (
)
q
p
q
p
~
~
~
∨
⇔
∧
- prawo zaprzeczenia koniunkcji
6.
(
) (
)
q
p
q
p
~
~
~
∧
⇔
∨
- prawo zaprzeczenia alternatywy
(prawa 5 i 6 nazywamy
prawami de Morgana)
7.
(
)
[
]
(
) (
)
[
]
r
q
q
p
r
q
p
∨
∧
∨
⇔
∧
∨
- rozdzielność alternatywy względem koniunkcji
8.
(
)
[
]
(
) (
)
[
]
r
q
q
p
r
q
p
∧
∨
∧
⇔
∨
∧
- rozdzielność koniunkcji względem alternatywy
9.
(
) (
)
p
q
q
p
∨
⇔
∨
- przemienność alternatywy
10.
(
) (
)
p
q
q
p
∧
⇔
∧
- przemienność koniunkcji
11.
(
)
[
]
(
)
[
]
r
q
p
r
q
p
∧
∧
⇔
∧
∧
- łączność koniunkcji (dzięki temu prawu, jeŜeli występuje sama
koniunkcja, nie musimy uŜywać nawiasów i moŜemy pisać
r
q
p
∧
∧
)
12.
(
)
[
]
(
)
[
]
r
q
p
r
q
p
∨
∨
⇔
∨
∨
- łączność alternatywy (korzyść jak w 11)
13.
( )
p
p
⇔
~
~
- prawo podwójnego zaprzeczenia
14.
p
p
~
∨
- prawo wyłączonego środka
15.
(
)
[
]
q
q
p
p
⇒
⇒
∧
- reguła odrywania
JeŜeli jakieś zdanie przy pewnym układzie wartości logicznych zdań atomowych okaŜe się
fałszywe wówczas nie jest ono tautologią (tak jak zdanie
(
)
[
]
{
}
p
q
p
q
p
⇔
∨
∧
⇒
~
~
, które np. dla p i q
fałszywych okazało się fałszywe).
Forma zdaniowa jednej zmiennej – wyraŜenie zawierające zmienną, dla której istnieje
przynajmniej jedna wartość taka, Ŝe jej podstawienie w miejsce zmiennej czyni z tej formy zdanie
logiczne. Np.
x
x
1
1
3
<
−
- forma zdaniowa jednej zmiennej x – istnieje przynajmniej jedna wartość (w
tym przypadku liczba rzeczywista), która po podstawieniu w miejsce x czyni z tego wyraŜenia zdanie
logiczne (np. dla x=1:
1
1
1
1
3
<
−
⋅
jest zdaniem logicznym – nie jest istotne to, Ŝe fałszywym).
Forma zdaniowa wielu zmiennych – wyraŜenie zawierające zmienne, dla których istnieją
wartości takie, Ŝe po ich podstawieniu w miejsce tych zmiennych otrzymujemy zdanie logiczne. Np.
forma zdaniową dwóch zmiennych jest wyraŜenie x+y=1 (wystarczy za x i y wstawić np. 1: 1+1=1 –
otrzymujemy zdanie logiczne).
Dziedzinę formy zdaniowej tworzą wszystkie te wartości, dla których staje się ona zdaniem
logicznym. Dziedzinę formy
x
x
1
1
3
<
−
tworzą wszystkie liczby rzeczywiste róŜne od zera. Dziedziną
formy x+y=1 są wszystkie moŜliwe pary liczb rzeczywistych. Elementami dziedziny nie muszą być
liczby czy teŜ układy liczb. Dziedziną formy „x jest lekkoatletycznym mistrzem świata w biegu na 100
m” tworzą wszyscy ludzie.
Formy zdaniowe występują powszechnie w matematyce. KaŜde równanie, nierówność, układ
równań, układ nierówności jest formą zdaniową jednej lub wielu zmiennych. W zasadzie dla kaŜdej z
nich trzeba czynić odpowiednie załoŜenia dla zmiennych, czyli ustalać dziedzinę.
Podstawienie wartości w miejsce zmiennych nie jest jedynym sposobem uczynienia z formy
zdaniowej zdania logicznego. Innym często spotykanym jest uŜycie
kwantyfikatorów:
ogólnego -
∧
(inne oznaczenie
∀
)
szczegółowego -
∨
(inne oznaczenie
∃
)
JeŜeli p(x) jest formą zdaniową zmiennej x wówczas następujące zdania czytamy:
( )
x
p
A
x
∧
∈
- dla kaŜdego
A
x
∈
p(x) (A – pewien zbiór)
np.
1
1
3
<
−
∧
∈
x
R
x
- dla kaŜdego
R
x
∈
3x-1<1
5
( )
x
p
A
x
∨
∈
- istnieje x naleŜące do zbioru A takie, Ŝe p(x)
np.
1
≠
∨
∈
x
R
x
- istnieje x naleŜące do zbioru R (liczb rzeczywistych) takie, Ŝe
1
≠
x
MoŜemy stosować większą ilość kwantyfikatorów (ale bez sensu stosować ich więcej niŜ forma
zdaniowa ma zmiennych):
1
=
+
∨
∧
∈
∈
y
x
R
y
R
x
- dla kaŜdego
R
x
∈
istnieje
R
y
∈
taki, Ŝe x+y=1
1
=
+
∧
∨
∈
∈
y
x
R
y
R
x
- istnieje
R
x
∈
taki, Ŝe dla kaŜdego
R
y
∈
x+y=1
1
=
+
∧
∧
∈
∈
y
x
R
y
R
x
- dla kaŜdego
R
x
∈
i kaŜdego
R
y
∈
x+y=1 (krócej zdanie to zapisujemy tak:
1
,
=
+
∧
∈
y
x
R
y
x
- dla kaŜdych x i y naleŜących do R x+y=1)
1
=
+
∨
∨
∈
∈
y
x
R
y
R
x
- istnieje
R
x
∈
i istnieje
R
y
∈
takie, Ŝe x+y=1 (krócej zdanie to zapisujemy tak:
1
,
=
+
∨
∈
y
x
R
y
x
- istnieją x i y naleŜące do R takie, Ŝe x+y=1)
JeŜeli zastosujemy tyle kwantyfikatorów ile dana forma zdaniowa ma zmiennych wówczas
otrzymamy zdanie logiczne (naleŜy pamiętać o tym, Ŝe zawsze najpierw stawiamy kwantyfikatory a
dopiero po nich formę zdaniową – nigdy odwrotnie!).
0
3
<
−
∨
∈
x
x
R
x
- prawda – wystarczy, Ŝe za x wstawimy -1:
0
1
3
<
−
−
−
jest prawdą
0
3
<
−
∧
∈
x
x
R
x
- fałsz – np. dla x=1 forma
0
3
<
−
x
x
staje się zdaniem fałszywym (
0
1
3
<
−
) – nie
moŜna więc powiedzieć, Ŝe dla wszystkich x rzeczywistych jest ona prawdziwa.
0
≥
∧
∈
x
R
x
- prawda – moŜna to udowodnić korzystając z definicji wartości bezwzględnej
0
<
∨
∈
x
R
x
- fałsz – wykazujemy korzystając z tej samej definicji
Uzasadnianie wartości logicznych pierwszych dwóch zdań jest raczej proste: wystarczy podać
jedną wartość dla zmiennej (w tym przypadku x). Znacznie trudniejsze są sytuacje takie jak w
pozostałych dwóch zdaniach, gdzie trzeba przeprowadzać juŜ dowód opierając się na definicjach bądź teŜ
innych zdaniach, o których wiadomo, Ŝe są prawdziwe.
1
=
+
∨
∧
∈
∈
y
x
R
y
R
x
- prawda – jeŜeli mamy jakąś ustaloną wartość x, to wystarczy za y wstawić 1-x i forma
x+y=1 stanie się zdaniem prawdziwym
1
=
+
∧
∨
∈
∈
y
x
R
y
R
x
- fałsz – jeŜeli wybierzemy sobie jakąś liczbę rzeczywistą x, to biorąc za y np. liczbę –x
otrzymamy z pewnością zdanie fałszywe (
( )
1
0
≠
=
−
+
x
x
) czyli dla tego x nie jest prawdą, Ŝe
1
=
+
∧
∈
y
x
R
y
1
,
=
+
∨
∈
y
x
R
y
x
- prawda – np. x=1, y=0
1
,
=
+
∧
∈
y
x
R
y
x
- fałsz – np. dla x=y=1
1
≠
+
y
x
Dostawienie kwantyfikatora zmienia nam ilość zmiennych w formie zdaniowej: x+y=1 – forma
dwóch zmiennych x i y,
1
=
+
∨
∈
y
x
R
x
- forma jednej zmiennej y.
Zaprzeczenia zdań z kwantyfikatorami dokonujemy zgodnie ze schematem:
( )
( )
x
p
x
p
A
x
A
x
~
~
∧
∨
∈
∈
⇔
( )
( )
x
p
x
p
A
x
A
x
~
~
∨
∧
∈
∈
⇔
W zaprzeczeniu kwantyfikator zmienia się na drugi, zaprzeczenie wędruje przed formę zdaniową.
(
)
0
3
0
3
~
0
3
~
≥
−
⇔
<
−
⇔
<
−
∧
∧
∨
∈
∈
∈
x
x
x
x
x
x
R
x
R
x
R
x
6
(
)
1
3
1
3
~
1
3
~
≠
−
⇔
=
−
⇔
=
−
∨
∨
∧
∈
∈
∈
x
x
x
x
x
x
R
x
R
x
R
x
Dla większej ilości kwantyfikatorów ta sama zasada: kaŜdy zamieniamy na drugi, zaprzeczenie
wędruje przed formę zdaniową:
⇔
≠
+
∨
∧
∈
∈
1
~
y
x
R
y
R
x
(
)
⇔
≠
+
∧
∨
∈
∈
1
~
y
x
R
y
R
x
1
=
+
∧
∨
∈
∈
y
x
R
y
R
x
(moŜna zawsze pisać wynik ostateczny)
R
y
x
R
y
R
x
∈
+
∧
∨
∈
∈
~
R
y
x
R
y
R
x
∉
+
⇔
∨
∧
∈
∈
⇔
≤
+
∨
∈
1
~
,
y
x
R
y
x
1
,
>
+
∧
∈
y
x
R
y
x
⇔
>
+
∧
∈
1
~
,
y
x
R
y
x
1
,
≤
+
∨
∈
y
x
R
y
x
Przeczenia najczęściej występujących symboli: < -
≥
,
≤
- >,
∈
-
∉
, = -
≠
Zaprzeczenia zdań złoŜonych:
(
)
(
)
(
)
(
)
R
x
x
R
x
x
R
x
x
R
x
x
R
x
R
x
R
x
R
x
∉
∧
≥
⇔
∈
∧
<
⇔
∈
∨
<
⇔
∈
∨
<
∧
∧
∧
∨
∈
∈
∈
∈
1
~
1
~
1
~
1
~
(korzystamy z
prawa zaprzeczenia alternatywy)
(
)
(
)
(
)
(
)
1
1
1
~
1
~
1
1
~
1
1
~
<
∨
≠
⇔
≥
∨
=
⇔
≥
∧
=
⇔
≥
∧
=
∨
∨
∨
∧
∈
∈
∈
∈
x
x
x
x
x
x
x
x
R
x
R
x
R
x
R
x
(korzystamy z
prawa zaprzeczenia koniunkcji)
(
)
(
)
(
)
(
)
R
x
x
R
x
x
R
x
x
R
x
x
R
x
R
x
R
x
R
x
∈
∧
≤
⇔
∉
∧
≤
⇔
∉
⇒
≤
⇔
∉
⇒
≤
∧
∧
∧
∨
∈
∈
∈
∈
1
~
1
1
~
1
~
(korzystamy
z prawa zaprzeczenia implikacji)
Zapisywanie zdań za pomocą symboli logicznych:
1) Równanie 3x-2=0 ma pierwiastek rzeczywisty:
0
2
3
=
−
∨
∈
x
R
x
(
pierwiastek równania to inaczej jego
rozwiązanie)
2) Istnieje liczba rzeczywista m, od której nie jest większy kwadrat dowolnej liczby rzeczywistej x:
m
x
R
x
R
m
≤
∧
∨
∈
∈
2
(nie jest większy – jest niewiększy czyli jest mniejszy lub równy)
3) Dla kaŜdego rzeczywistego m równanie mx-m+1=0 ma rozwiązanie rzeczywiste:
0
1
=
+
−
∨
∧
∈
∈
m
mx
R
x
R
m
(rozwiązanie równania – wartość, która to równanie spełnia – po podstawieniu jej w miejsce zmiennej
otrzymujemy zdanie prawdziwe)
4) Nie dla kaŜdej liczby rzeczywistej x jej sześcian jest niewiększy od tej liczby:
x
x
R
x
≤
∧
∈
3
~
(niewiększy
czyli mniejszy lub równy)
5) Dla kaŜdej liczby rzeczywistej x jej wartość bezwzględna jest nieujemna:
0
≥
∧
∈
x
R
x
(nieujemna czyli
mniejsza lub równa zero)
Podstawowe pojęcia wspólne dla wszystkich teorii matematycznych:
1) język – symbole oznaczające zmienne lub konkretne obiekty (x, y, liczby, punkty, zbiory itd.) –
kaŜdy z obiektów jest albo pojęciem pierwotnym (np. punkt, zbiór, naleŜenie elementu do zbioru) albo
jest ściśle zdefiniowany;
zmienna jest symbolem, w miejsce którego moŜemy w kaŜdej chwili wstawić
konkretny obiekt
2)
pojęcia pierwotne – takie, których nie definiujemy (ale te z ich własności, z których
korzystamy określane są w aksjomatach)
3)
definicje – określają pojęcia nie będące pierwotnymi odwołując się do nich bądź teŜ do pojęć
juŜ zdefiniowanych
4)
aksjomaty – zdania orzekające o pewnych faktach – nie sprawdzamy ich prawdziwości,
przyjmujemy, Ŝe takimi właśnie są. Układ takich zdań – aksjomatów nie moŜe być dowolny – przede
wszystkim nie moŜe prowadzić do sprzeczności czyli do wywiedzenia z nich jakiegoś zdania i jego
zaprzeczenia. Aksjomaty są fundamentem kaŜdej teorii – wszystkie inne fakty w jej obrębie dają się z
nich wywieść. Aksjomaty słuŜą równieŜ do określenia własności istniejących w danej teorii pojęć
7
pierwotnych (nikt nie definiuje np. pojęcia zbiór; zakłada się, Ŝe wszyscy rozumieją je tak samo. Okazało
się jednak, Ŝe nie moŜna go uŜywać w sposób dowolny, bo powstają wówczas sprzeczności np. paradoks
golibrody: zakładamy, Ŝe goli on tylko tych, którzy nie golą się sami. Czy naleŜy on do zbioru tych,
którzy golą się sami czy teŜ do zbioru tych, którzy tego nie robią? Aby uniknąć tego typu pytań, na które
odpowiedź nie istnieje, w matematyce korzysta się tylko z tych własności pojęć pierwotnych, które
zostały zapisane w aksjomatach lub z nich wyprowadzone)
5)
twierdzenia – zdania logiczne orzekające o prawdziwości pewnych faktów – kaŜde daje się
wywieść mniej lub bardziej bezpośrednio z aksjomatów. Zawsze ma postać implikacji albo
równowaŜności (z kaŜdego w postaci równowaŜności moŜna zrobić dwa twierdzenia, oba mające postać
implikacji – patrz tautologia nr 2). JeŜeli twierdzenie jest postaci
q
p ⇒
, to p nazywamy
warunkiem
wystarczającym dla q, zaś q warunkiem koniecznym dla p. JeŜeli jest postaci
q
p
⇔
, to p jest
warunkiem koniecznym i wystarczającym dla q (podobnie jak q dla p).
JeŜeli mamy twierdzenie
q
p ⇒
(moŜemy je nazwać
prostym), to
p
q ⇒
nazywamy
twierdzeniem (tw.)
odwrotnym,
p
q
~
~
⇒
-
przeciwstawnym,
q
p
~
~
⇒
-
przeciwnym. Z prawa
kontrapozycji (patrz tautologia nr 3) wynika, Ŝe twierdzenia proste i przeciwstawne są sobie równowaŜne
(podobnie jak w przypadku odwrotnego i przeciwnego). Wartość logiczna twierdzenia prostego nie ma
wpływy na wartość logiczną odwrotnego (potocznie uŜywa się określeń: twierdzenie prawdziwe,
twierdzenie fałszywe a więc i wartość logiczna twierdzenia)
Tw. proste: „JeŜeli dwa boki przeciwległe czworokąta są równe i równoległe, to czworokąt ten
jest równoległobokiem”.
Tw. odwrotne: „JeŜeli czworokąt jest równoległobokiem, to jego dwa boki przeciwległe są równe
i równoległe”.
Tw. przeciwstawne: „JeŜeli czworokąt nie jest równoległobokiem, to jego dwa przeciwległe boki
nie są równe lub nie są równoległe”. (wykorzystano prawo zaprzeczenia koniunkcji)
Tw. przeciwne: „JeŜeli dwa przeciwległe boki czworokąta nie są równe lub nie są równoległe, to
nie jest on równoległobokiem”. (wykorzystano prawo zaprzeczenia koniunkcji)
Zdanie, o którego prawdziwości nic nie wiemy, nazywane jest
hipotezą (kaŜdego roku setki
tysięcy hipotez pada pod mózgami matematyków przekształcając się w twierdzenia. Niektóre z nich
trzymają się jednak dzielnie – większość dlatego, Ŝe nikt ich jeszcze nie sformułował, nieliczne dlatego,
bo są piekielnie trudne – do niedawna (do 1995 roku) taką hipotezą przez kilkaset lat nie udowodnioną
było, teraz juŜ twierdzenie, Fermata o rozwiązaniach całkowitych, x, y, z równania
n
n
n
z
y
x
=
+
, gdzie n
jest dowolną liczbą naturalną).
Dowody twierdzeń – polegają na tworzeniu mniej lub bardziej długiego ciągu implikacji:
q
p
p
p
p
n
⇒
⇒
⇒
⇒
⇒
...
2
1
(lub równowaŜności, jeśli takiej postaci jest twierdzenie) poczynając od p
–
załoŜenia twierdzenia a kończąc na q – jego tezie (nazwy te występują przy twierdzeniu postaci
q
p ⇒
). JeŜeli wszystkie występujące w tym ciągu implikacje (równowaŜności) będą prawdziwe, to
prawdziwe będzie równieŜ nasze twierdzenie czyli implikacja
q
p ⇒
(równowaŜność
q
p
⇔
). Ilość
implikacji pośrednich zaleŜy od stopnia skomplikowania twierdzenia i moŜliwości intelektualnych
odbiorcy dowodu. KaŜda z nich jest wykazywana wprost albo nie wprost (przez zaprzeczenie).
Ewentualnie tworzymy dla nich implikacje przeciwstawne wykazując ich prawdziwość jedną z dwu
wymienionych metod. W przypadku równowaŜności od razu dokonujemy wnioskowań równowaŜnych
albo równowaŜności rozbijamy na dwie implikacje osobno (czasem róŜnymi metodami) wykazując
prawdziwość kaŜdej z nich (korzystamy z tautologii nr 2)
Twierdzenie:
JeŜeli w trójkącie suma miar dwóch kątów jest równa
o
90 , to jest on prostokątny
Lemat:
Suma miar kątów w kaŜdym trójkącie wynosi
o
180
Dowód twierdzenia:
Niech a, b, c – miary kątów danego trójkąta. Przy tych oznaczeniach twierdzenie moŜemy
sformułować następująco:
o
o
90
90
=
⇒
=
+
c
b
a
.
Z lematu
o
180
=
+
+
c
b
a
a z załoŜenia twierdzenia
o
90
=
+
b
a
, więc
o
o
180
90
=
+
c
czyli
o
90
=
c
.
cnd
8
(co naleŜało dowieść)
Często w dowodach twierdzeń korzystamy z twierdzeń juŜ dowiedzionych (zwanych lematami)
choć nie zawsze wyraźnie to zaznaczamy (robimy to raczej wtedy, gdy jest on dość skomplikowany, gdy
jego dowód przedstawiamy w innym miejscu).
Dowód tego samego twierdzenia (nie wprost):
(korzystamy z tautologii nr 3 dotyczącej zaprzeczenia implikacji)
ZałoŜenie: suma miar dwóch kątów w trójkącie jest równa
o
90 i trójkąt ten nie jest prostokątny.
JeŜeli a, b, c – miary kątów w trójkącie, to
o
180
=
+
+
c
b
a
. Z załoŜenia np.
o
90
=
+
b
a
. Stąd
(
)
o
o
o
o
90
90
180
180
=
−
=
+
−
=
b
a
c
. Zatem trójkąt ten posiada kąt prosty, więc jest prostokątny, co jest
sprzeczne z załoŜeniem, Ŝe prostokątny nie jest. ZałoŜenie jest więc fałszywe, prawdziwe jest zatem jego
zaprzeczenie czyli nasze twierdzenie.
cnd
RozwaŜmy twierdzenie będące kontrapozycją poprzedniego:
JeŜeli trójkąt nie jest prostokątny, to suma miar Ŝadnych dwóch kątów nie jest równa
o
90 .
Dowód wprost:
Z załoŜenia trójkąt nie jest prostokątny, więc jeśli a, b, c to miary jego trzech kątów, to
o
90
≠
a
,
o
90
≠
b
i
o
90
≠
c
. W kaŜdym trójkącie
o
180
=
+
+
c
b
a
, zatem:
(
)
o
o
o
o
o
o
90
90
90
180
180
90
≠
+
=
−
≠
−
=
+
⇒
≠
c
b
a
c
b
a
(
)
o
o
o
o
o
o
90
90
90
180
180
90
≠
+
=
−
≠
−
=
+
⇒
≠
c
a
b
c
a
b
(
)
o
o
o
o
o
o
90
90
90
180
180
90
≠
+
=
−
≠
−
=
+
⇒
≠
b
a
c
b
a
c
czyli suma miar Ŝadnych dwóch kątów nie jest równa
o
90 .
cnd
Dowód nie wprost tego twierdzenia wygląda identycznie tak samo jak dowód nie wprost
poprzedniego:
(
) (
)
(
)
p
q
q
p
q
p
~
~
~
~
~
⇒
⇔
∧
⇔
⇒
.
Wszystkie te sposoby prowadzą do dowodów o podobnej trudności, więc który z nich wybierzemy
nie jest zbyt istotne. Ale nie zawsze tak jest. Weźmy twierdzenie następujące: Liczb pierwszych jest
nieskończenie wiele. Bardzo trudno było by (o ile to w ogóle moŜliwe) wykazać go wprost. Twierdzenie
to moŜna wysnuć jako wniosek z innych, niestety bardziej zaawansowanych, twierdzeń. MoŜna jednak
wykazać go całkiem prosto stosując metodę nie wprost.
Dowód (nie wprost)
ZałoŜenie: liczb pierwszych jest skończona ilość (róŜna od zera – np. 2, 3 są liczbami
pierwszymi). Niech liczbami tymi są
n
p
p
p
,...,
,
2
1
(
+
∈
N
n
). Utwórzmy liczbę
1
...
2
1
+
⋅
⋅
⋅
=
n
p
p
p
x
. Z
pewnością nie jest ona równa Ŝadnej z nich i x>1.
JeŜeli x jest liczbą pierwszą otrzymujemy, Ŝe prócz
n
p
p
p
,...,
,
2
1
istnieje jeszcze jedna liczba
pierwsza, co jest sprzeczne z załoŜeniem, Ŝe innych liczb pierwszych nie ma.
Lemat : KaŜda liczba złoŜona dzieli się przez liczbę pierwszą
JeŜeli x jest liczbą złoŜoną, to (z lematu) dzieli się przez liczbę pierwszą. Nie jest ona równa
Ŝ
adnej z liczb
n
p
p
p
,...,
,
2
1
(Ŝadna z nich nie jest dzielnikiem liczby x) jest więc inną jeszcze jedną liczbą
pierwszą, co znowu daje nam sprzeczność.
ZałoŜenie okazało się błędne. Prawdziwe jest więc jego zaprzeczenie czyli nasze twierdzenie.
cnd
Twierdzenie:
2
jest liczbą niewymierną.
(dokładniejsze sformułowanie winno być takie: jeŜeli
2
jest liczbą rzeczywistą (a więc jeśli istnieje), to
jest liczba niewymierną)
Dowód wprost tego twierdzenia równieŜ był by potwornie trudny, tutaj równieŜ zastosowanie metody nie
wprost znacznie ułatwia sprawę.
Dowód (nie wprost)
9
ZałóŜmy, Ŝe
2
jest liczbą rzeczywistą (istnieje) i nie jest liczbą niewymierną. Wynika stąd, Ŝe jest
liczbą wymierną, a więc postaci
q
p
, gdzie p i q są pewnymi liczbami całkowitymi (
0
≠
q
).
2
jest liczbą
dodatnią, moŜemy zatem dodatkowo załoŜyć, Ŝe p i q są liczbami naturalnymi. Poza tym niech są one
względnie pierwsze – zapewni to nieskracalność ułamka
q
p
. Równość
q
p
=
2
przekształćmy
następująco:
p
q
=
2
i podnieśmy teraz obie jej strony do kwadratu (wolno to zrobić skoro p i q są tego
samego znaku) otrzymując:
2
2
2
p
q
=
. 2 jest dzielnikiem lewej strony tej równości, jest więc równieŜ
dzielnikiem jej strony prawej czyli liczby
2
p . Zatem liczby p teŜ. Stąd p jest postaci 2n, gdzie n jest
pewną liczbą naturalną dodatnią. Równość
2
2
2
p
q
=
przekształca się na
( )
2
2
2
2
n
q
=
co jest równowaŜne
równości
2
2
4
2
n
q
=
. Dzieląc obie jej strony przez 2 otrzymujemy
2
2
2n
q
=
. 2 jest dzielnikiem prawej
strony więc lewej równieŜ czyli liczby
2
q , a stad liczby q. Otrzymaliśmy w ten sposób, Ŝe 2 jest
dzielnikiem zarówno p jak i q. To zaś sprawia, Ŝe ułamek
q
p
jest skracalny, co jest sprzeczne z
załoŜeniem, Ŝe skracalny nie jest. Nasze załoŜenie, Ŝe
2
jest liczba wymierną doprowadziło do
sprzeczności, zatem
2
jest liczbą niewymierną.
cnd
Zapiszmy ten dowód stosując symbolikę logiczną:
Zał.:
NW
R
∉
∧
∈
2
2
Wtedy:
(
)
0
2
2
,
≠
∧
=
⇒
∈
∨
∈
q
W
q
p
C
q
p
Zał.: p,
+
∈
N
q
∧
( )
1
,
=
q
p
q
q
p
⋅
=
2
( )
2
2
p
q
=
n
p
p
p
p
q
N
n
2
2
2
2
2
2
2
=
⇒
⇒
⇒
=
∨
+
∈
( )
2
2
2
2
n
q
=
⇔
2
:
4
2
2
2
n
q
=
2
2
2n
q
=
q
q
2
2
2
⇒
⇒
(
)
( )
1
,
2
2
≠
⇒
∧
q
p
q
p
sprzeczność z załoŜeniem
( )
1
,
=
q
p
czyli
NW
NW
∈
⇒
∉
2
2
~
cnd
(opieramy się tu na załoŜeniu, Ŝe
R
∈
2
(czyli, Ŝe w ogóle istnieje. Jest ono spełnione – juŜ wieleset lat
temu platończycy zauwaŜyli, Ŝe długość przekątnej kwadratu o boku długości 1 ma taką właśnie wartość)
Porównanie dwóch róŜnych zapisów ostatniego twierdzenia przekonuje, mam nadzieję, Ŝe
symbolika znacznie skraca wszelkie wywody matematyczne (i nie tylko takie) czyniąc je bardziej
przejrzystymi.