02. Podstawy matematyki

Treści kształcenia. Celem zajęć jest zaprezentowanie studentom podstawowych pojęć matematycznych takich jak definicja, twierdzenie, implikacja, założenie, teza, implikacja odwrotna, warunek konieczny, warunek dostateczny. Rodzaje dowodów (na przykładach dowodu twierdzenia Pitagorasa i niewymierności pierwiastka z trzech) – dowody „nie wprost”.

Efekty kształcenia. Student potrafi poprawnie formułować wypowiedzi matematyczne, wyróżniać założenia i tezy twierdzeń oraz przenosić tę wiedzę na algorytmy i sprawdzanie ich poprawności. Potrafi dobrać odpowiedni do twierdzenia typ dowodu i go zastosować.

Wstęp¶

Matematyka, podobnie jak każda nauka, operuje własnym językiem, w którym formułowane są elementy teorii matematycznej - aksjomaty, twierdzenia, wnioski, hipotezy, wzory, dowody, etc. Język ten jest swoisty dla danego działu matematyki, ale zawiera również pewne elementy stałe.

Tymi stałymi elementami są rachunek zdań i predykatów oraz elementy teorii zbiorów (tzw. teorii mnogości). Działem, który zajmuje się badaniem zdań, jest logika matematyczna.

Można byłoby zadać naturalne pytanie, czy takie “formalne” podejście i tworzenie sztucznego języka jest rzeczywiście konieczne?

Okazuje się, że tak. Historia matematyki pokazała, że w pewnym momencie, gdy teorie matematyczne bardzo się rozrosły i brakowało solidnych podstaw matematyki, odkrywano rozmaite nieścisłości i antynomie, czyli najogólniej mówiąc zdania ilustrujące sprzeczności w teorii. W odpowiedzi na to, należało nowoczesną (XX-wieczną) matematykę zbudować na “trwałych fundamentach”, którymi są właśnie teoria mnogości i logika matematyczna.

Jakie ma to znaczenie dla informatyka? Zasadnicze. Informatyk “komunikując się” z komputerem musi również używać podobnego, precyzyjnego języka, w swojej naturze bardzo podobnego do języka matematyki i opartego na logice.

Elementy logiki matematycznej¶

Zdaniem (w sensie logiki) nazywamy takie zdanie oznajmujące, o którym możemy powiedzieć, że jest prawdziwe lub fałszywe (np. Słoń jest ssakiem). Prawdziwość bądź fałszywość zdania nazywamy jego wartością logiczną i oznaczamy odpowiednio przez 1 - prawda i 0 - fałsz. Zwykle zdania oznaczamy małymi literami alfabetu (bywa, że z indeksami):

Zatem zdaniami w sensie logicznym będą wyrażenia:

• Warszawa nie jest stolicą Polski.

• Człowiek jest ssakiem.

• Luty ma 31 dni.

Z kolei wyrażenia:

• Ile masz lat?

• Być albo nie być; oto jest pytanie.

nie są zdaniami w sensie logicznym.

Podobnie jak w języku polskim, ze zdań ,,pojedynczych" możemy konstruować zdania złożone. Wykorzystujemy do tego celu spójniki logiczne. Wyróżniamy pięć najważniejszych spójników zdaniowych:

• jednoargumentowy spójnik negacji $\neg$

• dwuargumentowe spójniki: koniunkcji $\wedge$, alternatywy $\vee$, implikacji $\Rightarrow$ i równoważności $\iff$.

Zdefiniowane powyżej operacje logiczne odpowiadają w języku polskim następującym spójnikom zdaniowym:

• $\neg p$ - nieprawda, że $p$,

• $p \wedge q$ - $p$ i $q$,

• $p \vee q$ - $p$ lub $q$,

• $p \Rightarrow q$ - jeśli $p$, to $q$,

• $p \iff q$ - $p$ wtedy i tylko wtedy, gdy $q$.

Zasadniczym pytaniem jest teraz, w jaki sposób od prawdziwości zdań $p$ i $q$ zależy prawdziwość zdań utworzonych przy pomocy powyższych spójników. Informacje o tym daje nam tabela.

Za pomocą powyższych spójników możemy jeszcze bardziej “komplikować” zdania:

Doprecyzujmy, że gdy rozważamy tego typu wyrażenia bez odniesienia do konkretnych zdań (tu - $p$, $q$, $r$, $s$), to mówić będziemy o formułach zdaniowych, a $p$, $q$, $r$ i $s$ nazywać będziemy zmiennymi zdaniowymi.

Jednym z podstawowych zagadnień jest pytanie o wartość logiczną całej formuły w zależności od wartości zmiennych zdaniowych. Dla przykładu rozważmy formułę:

Spróbujmy zbadać wartość logiczną takiej formuły dla wszystkich możliwych wartości przyjmowanych przez zmienne $p$ i $q$. Zbudujemy w tym celu tzw. tabelę prawdy.

Widzimy, że dla każdej możliwej pary wartości logicznych przyjmowanych przez zmienne $p$ i $q$ wartość logiczna formuły

wynosi 1, a zatem zawsze jest ona prawdziwa!

Spróbujmy wykonać kolejny przykład:

Tym razem mamy trzy zmienne zdaniowe, każda z nich przyjmuje jedną z dwóch wartości logicznych, co nam daje $2^3=8$ możliwych realizacji. Każdą taką funkcję, która wartościom logicznym zmiennych zdaniowych przyporządkowuje wartość logiczną formuły, nazywać będziemy wartościowaniem. Zatem jeśli formuła zawiera $n$ zmiennych, to mamy $2^n$ wartościowań. Należy o tym pamiętać budując tabelę prawdy. Sporządźmy dla formuły $(p \vee q \vee \neg r) \Rightarrow r$ taką tabelę.

Tym razem widzimy, że są również takie wartościowania, dla których powyższa formuła przyjmuje wartość fałszywą. Formuła poprzednia jest przykładem tzw. tautologii rachunku zdań, czyli formuły, która przyjmuje wartość prawdziwą przy każdym możliwym wartościowaniu.

Umiejętność stosowania spójników logicznych lub ujmując to “bardziej informatycznie” - operatorów logicznych - jest niezwykle ważna z punktu widzenia programisty. Większość języków programowania posiada typ zmiennej logicznej i operatory odpowiadające spójnikom logicznym. Pozwalają one kreować i kontrolować programiście właściwy przepływ programu. Są sytuacje, w których potrzebujemy sprawdzić, czy zachodzi wiele warunków jednocześnie albo alternatywa kilku warunków itp. Wtedy właśnie należy wykorzystać operatory logiczne, których działanie jest takie jak zdefiniowanych spójników.

Przykład¶

Spośród liczb od 1 do 100 wypisać wszystkie

• podzielne przez 4,

• podzielne przez 6,

• podzielne przez 4 i 6,

• podzielne przez 4 lub 6,

• podzielne przez 4 lub 6 i jednocześnie niepodzielne przez 36.

Analiza tabelki spójników logicznych pozwala zauważyć, że spośród spójników dwuargumentowych wszystkie oprócz implikacji są przemienne. Stąd też mówimy o poprzedniku i następniku implikacji. Implikacja ma jeszcze jedną ważną własność - odpowiada matematycznemu rozumieniu pojęcia wynikanie. Choć może się to wydawać na początku zaskakujące, implikacja jest prawdziwa (jak to wynika z tabeli prawdy) zawsze gdy poprzednik jest fałszywy. Prawdziwe jest więc zdanie

Jeśli Kraków jest stolicą Polski, to Słońce krąży wokół Ziemi.

jak również

Jeśli Kraków jest stolicą Polski, to Ziemia krąży wokół Słońca.

Fałszywe jest natomiast następujące zdanie:

Jeśli Ziemia krąży wokół Słońca, to Kraków jest stolicą Polski.

Ostatnie dwa z powyższych przykładów ilustrują nieprzemienność implikacji.

Kwantyfikatory¶

Okazuje się, że sam rachunek zdań nie jest wystarczający, do tego, aby stanowił on model języka matematycznego. Potrzebne jest rozbudowanie tego języka jeszcze o pewne elementy. Należą do nich m.in. kwantyfikatory.
Kwantyfikatorem ogólnym (dużym, uniwersalnym) wiążącym zmienną $x$ nazywamy wyrażenie: dla każdego $x$. Oznaczamy go symbolem

Kwantyfikatorem szczegółowym (małym, egzystencjalnym) wiążącym zmienną $x$ nazywamy wyrażenie: istnieje $x$. Oznaczamy go symbolem

Wyrażenie

oznacza, że równanie

ma rozwiązania całkowite. Osobną kwestią jest ilość tych rozwiązań.

Z kolei wyrażenie

oznacza, że każda liczba rzeczywista różna od 1 jest rozwiązaniem równania

Podstawowe elementy teorii matematycznej¶

Pojęcia pierwotne, definicje, aksjomaty i twierdzenia¶

Wiemy już mniej więcej, jakiego typu zdania będą pojawiały się w matematyce. Kolejnym krokiem jest przeznaczenie tych zdań - budowanie teorii. Matematycy budując jakąś teorię potrzebują, mówiąc bardziej obrazowo, różnych elementów konstrukcji. Do najbardziej podstawowych pojęć matematyki należą pojęcia pierwotne - czyli pojęcia, których się nie definiuje. Pojęciem pierwotnym jest np. pojęcie zbioru czy punktu. Pojęcia pierwotne mogą być różne w różnych matematycznych teoriach. Kolejnym elementem “konstrukcji” są definicje pojęć czyli zdania, za pomocą których ustalamy nazwę i znaczenie danego pojęcia. W definicji możemy odwoływać się tylko do zdefiniowanych uprzednio pojęć oraz pojęć pierwotnych.

Przyjrzyjmy się poniższej definicji.

Okręgiem nazywamy zbiór wszystkich punktów równoodległych od danego punktu.

Choć definicja wydaje się intuicyjnie poprawna, to jednak brakuje jej kilku istotnych elementów. Definiowanym pojęciem jest okrąg. Nie znamy kontekstu, więc dobrze byłoby napisać “na płaszczyźnie”. Zwróćmy również uwagę na pojęcia pierwotne i pojęcia, które pojawiają się w powyższej definicji okręgu - zbiór, punkt, odległość. O ile zbiór i punkt są z pewnością pojęciami pierwotnymi, tak uściślenia (formalnie definicji) wymagałoby pojęcie odległości, które jak się okazuje może w zasadniczy sposób wpłynąć na kształt definiowanego okręgu.

Odpowiednia kolejność definiowania pojęć używanych w danej definicji nie gwarantuje nam poprawności definicji i istnienia obiektu definiowanego. Muszą istnieć pewne dodatkowe ograniczenia (zasady) tworzenia poprawnych obiektów i zdań w matematyce. Dlatego wyróżnia się w matematyce aksjomaty czyli pewne z założenia prawdziwe zdania tzn. takie, których się nie uzasadnia, a z których wynikać mają wszystkie inne prawdziwe zdania - twierdzenia danej teorii.

Może zatem okazać się, że zaproponowana definicja jest po prostu sprzeczna, bo jej istnienie przeczyłoby któremuś z aksjomatów czy twierdzeń.

Różnica między aksjomatem, a twierdzeniem jest taka, że twierdzenie musi w logiczny sposób wynikać z aksjomatów lub innych twierdzeń. Innymi słowy wymaga matematycznego dowodu prawdziwości (w oparciu o istniejące aksjomaty i twierdzenia).

Twierdzenia matematyczne mają zasadniczo postać implikacji czasem bardzo rozbudowanej, lub kilku implikacji.

Twierdzenie Pitagorasa¶

Jeżeli trójkąt jest prostokątny, to suma kwadratów przyprostokątnych jest równa kwadratowi przeciwprostokątnej. Innymi słowy

Jeśli przyjmiemy, że zmienna zdaniowa $p$ oznacza zdanie trójkąt jest prostokątny, zaś zmienna $q$ - zdanie - suma kwadratów przyprostokątnych jest równa kwadratowi przeciwprostokątnej, to twierdzenie Pitagorasa ma postać implikacji

Poprzednik implikacji nazywamy założeniem twierdzenia, zaś następnik - tezą twierdzenia. Oczywiście dla większości twierdzeń teza nie jest bezpośrednim i oczywistym wnioskiem z założenia. Stąd też dowody twierdzeń (o których mówić będziemy za chwilę) bywają niejednokrotnie bardzo złożone, a “wymyślenie” ich zajmuje nawet dziesięciolecia lub stulecia!

Twierdzenie odwrotne, przeciwne i przeciwstawne¶

Przypuśćmy, że pewne twierdzenie $T$ dane jest w postaci implikacji, tzn.

Twierdzeniem odwrotnym do $T$ nazywamy twierdzenie postaci $q \Rightarrow p$. Zauważmy, że w twierdzeniu odwrotnym implikacja zmienia swój “kierunek”. Jest to tzw. implikacja odwrotna.

Twierdzeniem przeciwnym do $T$ nazywamy twierdzenie postaci $\neg p \Rightarrow \neg q$.

Twierdzeniem przeciwstawnym do $T$ nazywamy twierdzenie postaci $\neg q \Rightarrow \neg p$.

W ramach ćwiczenia zastanówmy się, czy któreś z równoważności

są prawdziwe. Zbudujmy tabelę prawdy dla ostatniej z nich.

Z uzyskanej tabeli wynika, że twierdzenie $T$ oraz twierdzenie przeciwstawne do $T$ są (logicznie) równoważne. Twierdzenia odwrotne i przeciwne do $T$ też są wzajemnie równoważne, jednak żadne z nich nie musi być równoważne twierdzeniu $T$.

Spróbujmy w ramach kolejnego ćwiczenia sformułować twierdzenie odwrotne, przeciwne i przeciwstawne do twierdzenia Pitagorasa i ocenić wartość logiczną każdego z tych twierdzeń.

Twierdzenie odwrotne: Jeżeli suma kwadratów długości dwóch boków trójkąta jest równa kwadratowi długości trzeciego boku, to trójkąt ten jest prostokątny.

Twierdzenie przeciwne: Jeżeli trójkąt nie jest prostokątny, to suma kwadratów przyprostokątnych jest różna od kwadratu przeciwprostokątnej.

Twierdzenie przeciwstawne: Jeżeli suma kwadratów długości dwóch boków trójkąta jest różna od kwadratu długości trzeciego boku, to trójkąt ten nie jest prostokątny.

Doskonale wiemy ze szkoły, że oprócz twierdzenia Pitagorasa prawdziwe jest twierdzenie do niego odwrotne. Stąd uwzględniając fakt, że oba twierdzenia są prawdziwe, prawdziwe będą twierdzenia do nich przeciwstawne. Zatem wszystkie cztery twierdzenia są prawdziwe. Moglibyśmy to podsumować następująco:

Twierdzenie¶

Trójkąt jest prostokątny wtedy i tylko wtedy, gdy

Warunek konieczny i dostateczny¶

Jeżeli ze zdania $p$ wynika zdanie $q$, czyli implikacja $p \implies q$ jest prawdziwa, to mówimy, że zdanie $p$ jest warunkiem dostatecznym dla $q$, zaś zdanie $q$ jest warunkiem koniecznym dla $p$.

Istotnie, z faktu, że implikacja jest prawdziwa, wynika, że prawdziwość poprzednika gwarantuje prawdziwość następnika. Z drugiej strony, na to, aby $p$ było prawdziwe (gdy $p \implies q$ jest prawdziwe), koniecznym jest, aby prawdziwe było również $q$.

Spróbujmy rozstrzygnąć następujące problemy:

• Liczba $n$ jest podzielna przez 24. Czy jest to warunek konieczny/dostateczny podzielności przez 4 i przez 6?

• Odwrotnie - czy podzielność danej liczby przez 4 i 6 jest konieczna/wystarczająca do podzielności przez 24?

Widzimy zatem, że podzielność przez 24 jest warunkiem dostatecznym (ale nie koniecznym) podzielności przez 4 i przez 6. Podzielność przez 6 i 4 jest warunkiem koniecznym (ale nie dostatecznym) podzielności przez 24. Łatwo wywnioskować, że podzielność przez 12 jest warunkiem koniecznym i dostatecznym podzielności przez 4 i przez 6.

Dowody twierdzeń¶

Jak już zostało wyżej wspomniane, w matematyce każde twierdzenie czyli zdanie prawdziwe, które nie jest aksjomatem, wymaga uzasadnienia, które nazywamy dowodem twierdzenia.
Istnieje wiele sposobów dowodzenia twierdzeń. Najbardziej naturalny wydaje się być dowodzenie metodą “wprost”, które nieco upraszczając, polega na tym, aby zbudować taki ciąg formuł danej teorii, w którym ostatnie z nich jest tezą dowodzonego twierdzenia. Każdy kolejny element tego ciągu musi logicznie wynikać z poprzednich jego elementów.
Inną techniką dowodową jest metoda “nie wprost”. Zasadniczą częścią tej metody jest przypuszczenie (na początku), że teza tego twierdzenia jest fałszywa i wykazanie, że przypuszczenie to prowadzi do sprzeczności.

Zilustrujmy obie metody na prostych przykładach.

Dowód twierdzenia Pitagorasa¶

Rozważmy trójkąt prostokątny o przyprostokątnych długości $a$ i $b$ oraz przeciwprostokątnej długości $c$. Przedłużmy bok długości $a$ o długość $b$, zaś bok długości $b$ o długość $a$. Oba boki są prostopadłe, możemy więc skonstruować kwadrat o boku długości $a+b$. Następnie prowadząc wewnątrz kwadratu z wierzchołków kątów ostrych odcinki prostopadłe do przeciwprostokątnej trójkąta oraz łącząc punkty, w których odcinki te przecinają odpowiednie boki kwadratu, otrzymujemy mniejszy kwadrat (o boku $c$) wpisany w kwadrat utworzony uprzednio.

Aby udowodnić twierdzenie, wystarczy porównać wzory na pole obliczone dwiema metodami:

• $P = (a+b)^2$

• $P = 4 \cdot \frac{1}{2} \cdot a \cdot b + c^2$

Otrzymujemy stąd równość

skąd

co kończy dowód.

Kolejny dowód - niewymierności pierwiastka z liczby 3 - przeprowadzimy metodą nie wprost.

Dowód niewymierności liczby $\sqrt{3}$¶

Dla dowodu nie wprost przypuśćmy, że liczba $\sqrt{3}$ jest wymierna. Możemy zatem zapisać ją w postaci ułamka nieskracalnego $\frac{m}{n}$, gdzie $m,n \in \mathbb{Z}$, $n \neq 0$. Mamy zatem $\sqrt{3} = \frac{m}{n}$. Po podniesieniu tej równości do kwadratu i przemnożeniu obustronnie przez $n^2$ dostajemy

Zauważmy, że liczba po lewej stronie równości jest podzielna przez 3, zatem $m^2$ jest również podzielna przez 3. Co więcej również $m$ jest podzielne przez 3. Istnieje więc taka liczba całkowita $l$, że $m = 3l$. Po podstawieniu do pierwszej z równości otrzymujemy

a stąd

Argumentując jak poprzednio dostajemy, że również liczba $n$ jest podzielna przez 3. Obie zatem liczby $m$ i $n$ są podzielne przez 3, co przeczy temu, że ułamek był nieskracalny. A zatem przypuszczenie, że liczba $\sqrt{3}$ jest wymierna, było fałszywe. Liczba $\sqrt 3$ jest zatem niewymierna.

Istnieje jeszcze wiele innych technik dowodowych, które będziemy systematycznie poznawać - dowód indukcyjny, dowód kombinatoryczny, itp. Zobaczymy także inne rodzaje dowodów - np. dowody konstrukcyjne czy dowody niekonstruktywne. Z pewnością pozwoli nam to rozwinąć aparat matematyczny, a przez to także informatyczny.