Elementy logiki matematycznej

Zamiast wstępu...

Myliłby się ktoś kto sądzi iż logika matematyczna towarzyszy matematyce od zarania dziejów. Otóż dział ten powstał właściwie dopiero na przełomie XIX i XX wieku. Logika matematyczna zajmuje się w zasadzie tym samym, co logika filozoficzna, jednak jej badania koncentrują się przede wszystkim na analizowaniu pojęć matematycznych. Do analiz stosuje głównie metody i narzędzia wypracowane przez setki lat rozwoju logiki filozoficznej, jednak po ich odpowiednim sformalizowaniu i uściśleniu. Formalizowanie logiki tradycyjnej przez logikę matematyczną polega na tworzeniu systemów algebraicznych, dzięki którym można zamiast słownych określeń stosować proste symbole zdań oraz dokonywać obliczeń symbolicznych. Twórcami logiki matematycznej byli m.in. George Boole, Gottlob Frege i Bertrand Russell, a do jej rozwoju przyczynił się w dużym stopniu między innymi genialny uczony Kurt Gödel. Rezultaty Gödla zalicza się do największych osiągnięć matematyki XX wieku. Gödel zajmował się również problemami ogólnej teorii względności; między innymi wyprowadził nietypowe rozwiązania równań Einsteina - dopuszczające możliwość podróży w czasie. W tamtym okresie uważano to za poważną wadę teorii. Einstein twierdził później, że wiedział o istnieniu takich rozwiązań od samego początku, ale ukrywał to, gdyż słusznie uważał, że inni fizycy nie zaakceptują teorii pozwalającej na podróże w czasie. Dlatego fakt ten musiał czekać wiele lat, zanim został odkryty przez Gödla.

George Boole	Gottlob Frege	Bertrand Russell	Kurt Gödel

Twórcy podstaw logiki matematycznej

Charakterystyczną cechą matematyki jest dowodzenie twierdzeń, na podstawie innych twierdzeń, których prawdziwość została już dowiedziona lub z góry założona. Dowodzenie twierdzeń odbywa się za pomocą tak zwanego rozumowania dedukcyjnego, które stanowi niezwykle ważne narzędzie matematyki. Nauką, której jednym z zadań jest badanie rozumowań stosowanych w matematyce i ustalanie kryteriów ich poprawności, jest własnie logika matematyczna.

... ale może wreszcie będziesz wyrażał się jaśniej... co...?

OK, OK. Logika matematyczna jest formalną metodą matematyczną służącą do badania prawdziwości lub fałszywości zdań. Ale czym są owe tajemnicze zdania?

Zdania i funkcje zdaniowe

Zdaniem nazywamy w logice wypowiedź orzekającą, której można przypisać jedną z dwóch ocen: prawdy lub fałszu. Orzekającą, czyli twierdzącą - zdanie zaczynające się od "CZY" nie będzie zatem zdaniem w sensie logiki matematycznej. Wartość logiczną zdania prawdziwego oznaczamy przez 1, zdania fałszywego przez 0. JEST TO TYLKO UMOWA. Równie dobrze moglibyśmy użyć innych oznaczeń. Ktokolwiek widzi w tym analogię do systemu dwójkowego stosowanego dzisiaj w komputerach, ten nic a nic się nie myli... Zdania na ogół oznaczamy literami: p, q, r,...

I tak na przykład zdanie 13 jest liczbą pierwszą jest (w arytmetyce liczb naturalnych) zdaniem prawdziwym (wartość logiczna 1), zaś zdanie 13 jest liczbą parzystą jest zdaniem fałszywym (wartość logiczna 0). Zdanie: czy kwadrat jest czworokątem? nie jest zdaniem orzekającym, zatem nie ma żadnej wartości logicznej. Zdanie: prosta jednym ruchem gałki ocznej niszczy galaktyki jest wprawdzie zdaniem orzekającym, ale w ramach geometrii bezsensownym (ani prawdziwym ani fałszywym). Logika nie ustala wartości logicznych pojedynczych zdań. Czyni to odpowiednia nauka. Na przykład zdanie Istnieje liczba będąca ilorazem 13 i 5 jest fałszywe w arytmetyce liczb naturalnych (bo ułamek trzynaście piątych nie jest liczbą naturalną), ale prawdziwe w arytmetyce liczb wymiernych czy rzeczywistych. Oczywiście to samo zdanie jest w ogóle bez sensu na przykład w etyce.

Funkcją zdaniową nazywamy wyrażenie, które po wstawieniu w miejsce zawierające zmienną x dowolnego elementu należącego do dziedziny staje się zdaniem logicznym.

I tak na przykład funkcja zdaniowa x jest liczbą naturalną, staje się zdaniem po podstawieniu pod x konkretnej wartości liczbowej. Jeżeli wstawimy np. x = 5, zdanie będzie prawdziwe, dla x = -7, zdanie będzie fałszywe.

A teraz będzie NAJWAŻNIEJSZE, zabieramy się za...

Operacje na zdaniach

Negacja

Negację (zaprzeczenie) zdania p- zdanie „nieprawda, że p” oznaczamy:

Na przykład jeżeli oznacza zdanie: 3 jest liczbą parzystą
to oznacza zdanie: nieprawda, że 3 jest liczbą parzystą. W tym przykładzie zdanie jest fałszywe, a zdanie jest prawdziwe.

Dwa zdania: oraz nazywamy sprzecznymi. Z pojęciem negacji związane jest tzw. prawo wyłączonego środka: z dwóch zdań oraz co najmniej jedno jest prawdziwe. Innymi słowy prawo to mówi nam, że dwa zdania sprzeczne nie mogą być jednocześnie fałszywe. Prawo wyłączonego środka nosi łacińską nazwę tertium non datum (trzeciej możliwości brak).

Koniunkcja

Koniunkcję zdań p i q czyli zdanie „p i q” oznaczamy:

Na przykład zdanie: (kwadrat jest czworokątem) i (7 jest liczbą pierwszą) jest prawdziwe, natomiast zdanie (kwadrat jest czworokątem) i (7 jest liczbą parzystą) jest fałszywe.

Alternatywa

Alternatywę zdań p i q czyli zdanie „p lub q” oznaczamy:

Na przykład zdanie: (kwadrat jest czworokątem) lub (7 jest liczbą parzystą) jest prawdziwe, natomiast zdanie (kwadrat nie jest czworokątem) lub (7 jest liczbą parzystą) jest fałszywe. Podobnie zdanie 6 jest liczbą parzystą lub nieparzystą jest prawdziwe, natomiast 7 jest podzielne przez 2 lub przez 3 jest fałszywe.

Implikacja

Implikację (wynikanie) zdań p i q - zdanie „jeśli p, to q” oznaczamy:

Pierwsze ze zdań (p) nazywamy poprzednikiem implikacji, drugie (q) następnikiem implikacji. Implikacja jest bodaj najciekawszym przypadkiem rachunku zdań. Przeczy ona bowiem niekiedy tzw. zdrowemu rozsądkowi (zdrowy rozsądek - zespół fałszywych przekonań wbijanych przez dorosłych). W mowie potocznej nie używamy słowa "wynika" w tak szerokim znaczeniu. Na przykład nie mówimy o wynikaniu gdy zarówno poprzednik jak i następnik są fałszywe. Tymczasem, o dziwo, w tym przypadku w logice matematycznej takie zdanie jest prawdziwe! Wraz z naszymi postępami w nauce zobaczymy, że KAŻDE twierdzenie matematyczne można zapisać w postaci pewnej implikacji - według schematu: jeżeli ZAŁOŻENIE to TEZA.

Z implikacją związana jest tzw. reguła odrywania. Mówi ona, że jeżeli prawdziwe jest wynikanie oraz zdanie , wówczas prawdziwe jest zdanie .
Przykład: z arytmetyki wiadomo, że implikacja jeżeli suma cyfr liczby dzieli się przez 3, to ta liczba dzieli się przez 3 jest prawdziwa. Zdanie: suma cyfr liczby 723 dzieli się przez 3 jest również prawdziwe. Na podstawie reguły odrywania wnioskujemy, że sama liczba 723 dzieli się przez 3. Kolejnym ważnym prawem jest prawo przechodniości implikacji. Jeżeli prawdziwe są dwie implikacje oraz , to prawdziwa jest implikacja . Taki ciąg implikacji może być bardzo długi. Milion, miliard, trylion implikacji... a niech i będzie nieskończoność, byle przeliczalna, precz z ograniczeniami... No i kto teraz będzie dalej uparcie twierdził, że machnięcie skrzydłami motyla w Paragwaju nie może wywołac paniki na giełdzie w Kuala Lumpur... Związku pozornie nie widać ale czy aby na pewno go nie ma....

Równoważność

Równoważność zdań p i q czyli zdanie „p wtedy i tylko wtedy, gdy q” oznaczamy:

Już na pierwszy rzut oka widać, że równoważność jest prawdziwa, gdy po obu stronach stoją zdania o tej samej wartości logicznej. No bo wart pac pałaca... Fałsz równoważny fałszowi a prawda prawdzie. Inaczej mówiąc, jeżeli równoważność jest prawdziwa, to zdania p i q nazywamy zdaniami równoważnymi. Na przykład: (3x - 6 = 0) <=> (x = 2) (trzy razy x minus 6 jest równe 0, wtedy i tylko wtedy gdy x równa się 3). Równoważność jest pewnym uogólnieniem równości, stąd nieprzypadkowe podobieństwo symboli.

Tabelka wartości logicznych negacji, koniunkcji, alternatywy, implikacji i równoważności:

0	0	1	1	0	0	1	1
0	1	1	0	0	1	1	0
1	0	0	1	0	1	0	0
1	1	0	0	1	1	1	1

Z powyższej tabelki wynikają proste wnioski dotyczące wartości logicznych. By stać się (arcy)mistrzem logiki wystarczy zapamiętać, że:

Negacja ma zawsze wartość przeciwną do zdania negowanego.

Koniunkcja dwóch zdań jest prawdziwa wtedy i tylko wtedy gdy oba zdania są prawdziwe.

Alternatywa dwóch zdań jest fałszywa wtedy i tylko wtedy gdy oba zdania są fałszywe.

Implikacja jest fałszywa wtedy i tylko wtedy gdy z prawdy wynika fałsz.

Równoważność dwóch zdań jest prawdziwa wtedy i tylko wtedy gdy oba zdania mają tą samą wartość logiczną.

Tautologia

Tautologia (fajnie brzmi, prawda...) to zdanie złożone, które jest zawsze prawdziwe, niezależnie od wartości logicznych zdań prostych, z których się składa. Jakby nie kombinować zawsze otrzymamy prawdę. Najbardziej znanymi tautologiami są podane niżej prawa de Morgana:

Pierwsze prawo de Morgana

Drugie prawo de Morgana

a także prawo wyłączonego środka (Tertium non datum)

i prawo transpozycji

Na koniec tego krótkiego wykładu powiemy sobie o kwantyfikatorach. W matematyce posługujemy się często zwrotami dla każdego x i istnieje takie x, że... Są to, odpowiednio:

Kwantyfikator ogólny (dla każdego...), oznaczany symbolem lub . Zapis ten czytamy "DLA KAŻDEGO x należącego do X".

Kwantyfikator szczegółowy (istnieje..), oznaczany symbolem lub . Zapis ten czytamy "ISTNIEJE x należące do X".

Jak brzmi zatem (po polsku) poniższe zdanie zapisane za pomocą kwantyfikatorów:

Otóż brzmi ono: Istnieje liczba naturalna n, taka że dla każdej liczby rzeczywistej x jej n-ta potęga jest większa lub równa 0. Prawda jaka porażająca elegancja i zwięzłość tego zapisu?

Z kolei zapis:

Oznacza: Dla każdej liczby rzeczywistej x istnieje liczba rzeczywista y, taka że x + y = 5.

No to ćwiczonko... Zapiszmy za pomocą kwantyfikatorów zdanie: "dla każdego Kątowicza k_n należącego do zbioru wszystkich Kątowiczów K liczba kolczyków c_n jest większa lub równa 10" lub bardziej po polsku "Każdy kątowicz nosi przynajmniej 10 kolczyków". A oto jak to zrobić:

 

Paradoksy logiczne

Paradoks to rozumowanie, w którym wnioskując z prawdziwych przesłanek, dowodzi się twierdzeń wzajemnie sprzecznych. Choć paradoks z pozoru wygląda na jakiś żart, często wyraża problemy natury filozoficznej. Ponoć najbardziej znanym jest paradoks kłamcy. Przyjmujemy w nim, iż kłamca to taki osobnik, który zawsze kłamie. Kłamca mówi "kłamię", to niewinne zdanie jest z pozoru jednocześnie fałszywe i prawdziwe (dlaczego?). Niniejsze zdanie jest fałszywe. Tak w inny sposób można sformułować ów paradoks. Precz z preczem! I tysiące innych sformułowań, prowadzi do tego samego problemu. Innym paradoskem jest tzw. paradoks fryzjera. Pewien fryzjer goli wszystkich mężczyzn, którzy nie golą się sami, natomiast nie goli tych, którzy golą się sami. Czy goli się sam? Jeśli goli się sam, to nie może golić się sam, a jeśli nie goli się sam, to goli się sam! Antynomia Grellinga, paradoks Berry'ego, paradoks hipergry, paradoks więźnia, to tylko kilka innych przykładów.

Paradoks powstaje, ponieważ wypowiadane zdanie orzeka o tymże samym zdaniu. Sposobem uniknięcia tego rodzaju paradoksów w logice jest rozróżnianie języka oraz metajęzyka (języka "wyższego rzędu"), służącego do opisu analizowanego języka.

Przykładowe zadania

1. Zdefiniować koniunkcję za pomocą alternatywy i negacji.
2. Czy prawdziwe jest zdanie: Jeżeli z faktu, że wszystkie boki trójkąta ABC są równe wynika, że wszystkie kąty trójkąta ABC są równe i trójkąt ma nierówne kąty, to ma również nierówne boki.
3. Oceń wartość logiczną zdania: "Jeżeli Toruń leży nad Wisłą, to pies jest ssakiem".
4. Oceń wartość logiczną zdania: "Liczba 0 jest wymierna i liczba 0 jest najmniejszą liczbą całkowitą".
5. Wykazać, że poniższe wyrażenia są tautologiami:

GÓRA         SZKOŁA