Podcast o Logika formalna i predykatowa

Přepis

Anna: Czyli kwantyfikatory to w zasadzie tylko taki super wymyślny sposób na powiedzenie „wszyscy” albo „ktoś”? To jest genialne!

Lukáš: Dokładnie tak! Logika formalna brzmi strasznie, ale w rzeczywistości to tylko narzędzie, żeby być super precyzyjnym. A na egzaminach precyzja jest kluczowa.

Anna: No dobrze, musimy to rozebrać na czynniki pierwsze. Słuchacie Studyfi Podcast. Dziś z naszym ekspertem, Łukaszem, zanurkujemy w świat logiki formalnej.

Lukáš: Cześć Anno, cześć wszystkim. Nie bójcie się, nie będzie tak strasznie, jak to brzmi. Właściwie to całkiem fajna zabawa, kiedy wiecie, jak się do tego zabrać.

Anna: Dobra, to przejdźmy od razu do przykładu. Mamy zdanie: „Między dowolnymi dwoma różnymi liczbami parzystymi leży liczba nieparzysta.” Jak ja to, jakim cudem, przetłumaczę na te wasze symbole?

Lukáš: Świetne pytanie! Rozbijemy to na kawałki. „Dowolnymi dwoma” mówi nam, że będziemy mówić o wszystkich możliwych parach. Czyli potrzebujemy dwóch kwantyfikatorów ogólnych. Oznacza się je ∀. Więc zaczniemy od ∀x ∀y.

Anna: Okej, czyli „dla wszystkich x” i „dla wszystkich y”. Rozumiem. Co dalej?

Lukáš: Teraz musimy powiedzieć, że te x i y są parzyste. Więc dodamy warunek: (even(x) ∧ even(y)). Ten symbol daszka ∧ oznacza „i jednocześnie”.

Anna: Czyli: dla wszystkich x i dla wszystkich y zachodzi, że x jest parzyste i jednocześnie y jest parzyste. Na razie to ma sens. Ale to zdanie mówi o *różnych* liczbach.

Lukáš: Dokładnie! Musimy to sprecyzować. Dodamy kolejny warunek: x < y. Całość wygląda teraz tak: ∀x ∀y((even(x) ∧ even(y) ∧ x < y) ... a teraz przyjdzie ta druga część zdania.

Anna: Ta część, gdzie mówi się, że „między nimi leży liczba nieparzysta”.

Lukáš: Tak. „Leży” albo „istnieje” sugeruje nam, że użyjemy kwantyfikatora egzystencjalnego, ∃. Więc nasza formuła będzie kontynuowana strzałką, która oznacza implikację, a potem ∃z.

Anna: Czyli jeśli zachodzi ta pierwsza część o dwóch różnych liczbach parzystych, TO ISTNIEJE jakieś 'z'?

Lukáš: Perfekcyjnie powiedziane. A teraz już tylko doprecyzujemy, czym jest to 'z'. Musi być nieparzyste, więc (odd(z)).

Anna: I musi leżeć *między* x a y.

Lukáš: Zgadza się. Czyli x < z i jednocześnie z < y. Kiedy to wszystko połączymy, otrzymamy finalną formułę.

Anna: Czyli: ∀x ∀y((even(x) ∧ even(y) ∧ x < y) → ∃z(odd(z) ∧ x < z ∧ z < y)). O rany. Kiedy człowiek widzi to tak rozłożone na czynniki pierwsze, to nagle nie jest to taka magia.

Lukáš: Wcale nie. To jak układanka. Każde słowo ma swój symbol i swoje miejsce.

Anna: Wspomniałeś o takiej małej wskazówce, która mogłaby się przydać. Coś o tym, jak kwantyfikatory lubią się ze spójnikami.

Lukáš: Tak, to dobra podpowiedź. Kwantyfikator ogólny ∀, czyli „dla wszystkich”, najczęściej łączy się z implikacją, czyli tą strzałką →. Mówimy tym: „DLA WSZYSTKICH elementów zachodzi, że JEŚLI spełniają warunek A, TO spełniają też warunek B.”

Anna: Jasne, jak w naszym przykładzie. JEŚLI x i y to dwie różne liczby parzyste, TO między nimi leży nieparzysta.

Lukáš: Dokładnie. A na odwrót, kwantyfikator egzystencjalny ∃, czyli „istnieje”, zazwyczaj łączy się z koniunkcją ∧, czyli „i jednocześnie”.

Anna: Bo mówimy: „ISTNIEJE element, który ma właściwość A I JEDNOCZEŚNIE właściwość B.”

Lukáš: W punkt. Jak w naszym przykładzie to z: ISTNIEJE z, które jest nieparzyste I JEDNOCZEŚNIE jest większe niż x I JEDNOCZEŚNIE mniejsze niż y. To jest naprawdę przydatne ułatwienie.

Anna: Ale co, jeśli w zadaniu nie mam wszystkich potrzebnych symboli? Na przykład tutaj mamy even i odd, ale co gdybyśmy mieli zdefiniowane tylko parzyste?

Lukáš: Świetna obserwacja. To zdarza się często. Musimy sobie umieć radzić z tym, co mamy. Gdybyśmy mieli tylko predykat even(x), to liczbę nieparzystą zapisalibyśmy po prostu jako jego negację: ¬even(x).

Anna: Aha! Czyli „nie jest parzyste”. To sprytne. To jak w programowaniu, kiedy coś definiujesz przez negację.

Lukáš: Dokładnie tak. Albo wyobraź sobie, że masz w zadaniu tylko zbiór katalogów, dir(x). Ale zadanie chce od ciebie, żebyś pracowała z plikami. Jak zapisałabyś, że 'x' to plik?

Anna: No... po prostu powiedziałabym, że to nie jest katalog? Czyli ¬dir(x)?

Lukáš: Bingo! Logika właśnie na tym polega. Pracować z tym, co jest zdefiniowane, a resztę sprytnie wywnioskować. Nie zawsze wszystko jest podane na tacy.

Anna: Dobra, praktykę byśmy mieli. Ale na egzaminach są też pytania teoretyczne. A niektóre brzmią… no, dość strasznie. Na przykład: Sformułuj pierwsze twierdzenie Gödla o niezupełności.

Lukáš: Ach, Gödel. Wielki straszak. Ale my się go bać nie będziemy. Spróbujmy prosto. Pierwsze twierdzenie w zasadzie mówi, że każdy wystarczająco silny i niesprzeczny system matematyczny – jak na przykład arytmetyka, którą znamy ze szkoły – zawsze będzie zawierał twierdzenia, które są prawdziwe, ale w ramach tego systemu nie można ich udowodnić.

Anna: Czekaj, czekaj. Czyli istnieją matematyczne prawdy, których po prostu nie możemy udowodnić za pomocą matematyki, której używamy?

Lukáš: Dokładnie! To jest absolutnie oszałamiająca myśl. Zawsze będą istnieć granice tego, co możemy udowodnić. System nigdy nie może być jednocześnie wystarczająco silny, niesprzeczny i zupełny.

Anna: To jest… trochę niepokojące. A co z drugim twierdzeniem?

Lukáš: Ono do tego nawiązuje. Drugie twierdzenie Gödla mówi, że żaden taki system nie może udowodnić swojej własnej niesprzeczności. Innymi słowy, matematyka nie może udowodnić, że w niej samej nie ma żadnych sprzeczności.

Anna: Czyli musimy po prostu wierzyć, że 2+2=4 i że cały system gdzieś nam się nie zawali?

Lukáš: W zasadzie tak. Musimy założyć, że jest niesprzeczny, bo od wewnątrz nie da się tego udowodnić. To filozoficzny wymiar matematyki, który fascynuje ludzi już prawie sto lat.

Anna: Dobra, Gödel to filozofia. Ale co z tymi bardziej suchymi definicjami? Na przykład: „Zdefiniuj pojęcie interpretacji języka logiki predykatów pierwszego rzędu.”

Lukáš: Brzmi to skomplikowanie, ale wyobraź sobie to jako słownik. Interpretacja to para (D, α). 'D' to dziedzina – to świat, o którym mówimy. Na przykład zbiór wszystkich ludzi albo wszystkich liczb.

Anna: A to 'α'?

Lukáš: 'α' to to odwzorowanie, ten tłumacz. Mówi nam, co poszczególne symbole w naszym świecie 'D' oznaczają. Każdej zmiennej przypisuje konkretny element z dziedziny, każdemu symbolowi predykatowemu przypisuje jakąś relację, a każdemu symbolowi funkcyjnemu jakąś funkcję.

Anna: Czyli interpretacja to w zasadzie klucz do tego, jak czytać naszą formułę w rzeczywistym świecie? Bez niej to tylko puste symbole.

Lukáš: Dokładnie. A z tym wiąże się też kolejne pojęcie: term. Co to jest term?

Anna: To brzmi jak coś z Terminatora.

Lukáš: Blisko. Term to w zasadzie cokolwiek, co może oznaczać jakiś obiekt w naszej dziedzinie. Najprostszy term to zmienna. A potem, jeśli mamy jakiś symbol funkcyjny 't' i jakieś termy 't1' aż 'tn', to 't(t1, ..., tn)' też jest termem.

Anna: Czyli na przykład 'x' to term. A kiedy mamy funkcję 'ojciec(x)', to 'ojciec(x)' też jest termem? Bo oznacza konkretną osobę – ojca osoby x.

Lukáš: Dokładnie tak! Termy to nazwy dla obiektów. Formuły to z kolei całe twierdzenia o tych obiektach.

Anna: Przejdźmy do kolejnego. Dowód formuły w logice zdań, tak zwany dowód Hilbertowski.

Lukáš: To proste. To ciąg formuł, który kończy się tą formułą, którą chcemy udowodnić. A teraz to ważne: każda formuła w tym ciągu musi być albo aksjomatem – czyli jakąś podstawową, daną prawdą – albo musi być wyprowadzona z poprzednich formuł za pomocą jakiejś reguły wnioskowania, typowo Modus Ponens.

Anna: Czyli to jak budowanie ściany. Każda cegła (formuła) musi albo stać na solidnym fundamencie (aksjomat), albo musi być podparta innymi, już ułożonymi cegłami (wyprowadzenie).

Lukáš: Idealna analogia! A z tym wiążą się dwa kluczowe pojęcia: poprawność i zupełność systemu.

Anna: To brzmi ważnie.

Lukáš: To są najważniejsze właściwości. System jest *poprawny*, jeśli wszystko, co w nim udowodnimy, jest rzeczywiście prawdą. Innymi słowy, nasz system nie produkuje żadnych kłamstw. Dowodliwe implikuje prawdziwe.

Anna: A zupełność?

Lukáš: *Zupełność* to druga strona medalu. System jest zupełny, jeśli każda prawda, która w nim zachodzi, jest w nim jednocześnie dowodliwa. Czyli, że żadna prawda nam nie umknie, że na wszystko możemy wpaść.

Anna: Aha! Czyli poprawność oznacza „nie udowadniamy bzdur”, a zupełność oznacza „udowadniamy wszystkie prawdy”.

Lukáš: Dokładnie. Idealny system logiczny jest poprawny i zupełny. Ale jak nam pokazał Gödel, w przypadku bardziej skomplikowanych systemów, takich jak arytmetyka, tej zupełności nigdy nie osiągniemy.

Anna: Wow. Logika formalna jest w końcu o wiele głębsza, niż się wydaje. Nie chodzi tylko o symbole, chodzi o granice naszego poznania.

Lukáš: Dokładnie tak. A zrozumienie tych podstaw da wam ogromną przewagę, nie tylko na egzaminie, ale i w krytycznym myśleniu ogólnie. A o tym opowiemy więcej zaraz po krótkiej przerwie.

Anna: Także kiedy już mamy formułę w jakiejś podstawowej formie, to jeszcze nie koniec, prawda? Natknęłam się na przykład na prawo rozdzielności, które wyglądało... no, dość dziko.

Lukáš: Tak, to potrafi dać w kość, ale zasada jest właściwie prosta. To podobne do tego, jak w podstawówce wymnażasz nawiasy w matematyce.

Anna: Wymnażasz? To brzmi znajomo.

Lukáš: Dokładnie tak. Wyobraź sobie, że masz wyrażenie A lub (B i C). Prawo rozdzielności pozwala ci to „lub” rozdzielić do nawiasu. Czyli dostajesz (A lub B) i (A lub C).

Anna: Aha! Czyli to działa też dla tego bardziej skomplikowanego przykładu, który widziałam? To było coś w stylu nie-X lub (Y i (nie-Z lub nie-W)).

Lukáš: Dokładnie! Bierzesz to nie-X i w zasadzie „dodajesz” je do każdego członu w tym dużym nawiasie. Wynik to (nie-X lub Y) i jednocześnie (nie-X lub nie-Z lub nie-W). Tym krokiem dochodzimy do tak zwanej koniunkcyjnej postaci normalnej, czyli KPN.

Anna: Super, to jest o wiele jaśniejsze. Ale co, jeśli po takim przekształceniu powstanie mi w nawiasie jakiś chaos?

Lukáš: Dobre pytanie. Po każdym kroku kluczowe jest uproszczenie wyrażenia. To jest prawie najważniejsza część.

Anna: Czyli takie logiczne porządki?

Lukáš: Dokładnie tak. Kiedy masz na przykład w nawiasie (Y i Y i Z), to jest niepotrzebnie długie. Możesz to skrócić tylko do (Y i Z).

Anna: To ma sens. A co z jakimś bardziej skomplikowanym przypadkiem?

Lukáš: No to co na przykład (Y i nie-Z i nie-Y)? Tutaj dzieje się coś ciekawego. Masz tam Y i jednocześnie jego negację nie-Y.

Anna: Te dwie rzeczy przecież nie mogą zachodzić jednocześnie.

Lukáš: Bingo! To jest sprzeczność. Cały ten nawias jest więc fałszywy, logiczne zero. A kiedy masz coś połączone z zerem, często to upraszcza całe wyrażenie. Więc z chaosu nagle jest... nic.

Anna: Znika to jak kamfora. Świetnie. Teraz jednak odbiję do czegoś, co brzmi jak tajny kod... MGU. Co to, na litość boską, jest?

Lukáš: MGU, czyli Most General Unifier. Po polsku najogólniejszy unifikator. Celem jest wzięcie kilku różnych wyrażeń i za pomocą podstawiania zmiennych zrobienie z nich jednego, absolutnie identycznego wyrażenia.

Anna: Czyli ujednolicanie wyrażeń. Jak to działa w praktyce?

Lukáš: Pokażemy to na przykładzie. Mamy trzy predykaty: P(x, g(v), v), potem P(w, z, a) i na koniec P(h(u), u, y). Zaczniemy od pierwszych dwóch.

Anna: Dobra, jestem gotowa.

Lukáš: Idziemy od lewej do prawej. Porównujemy pierwsze pozycje: x i w. Proste, podstawiamy x za w. Teraz mamy P(w, g(v), v) i P(w, z, a).

Anna: Super, pierwszy kawałek zgodny. Co dalej?

Lukáš: Drugie pozycje: g(v) i z. Więc podstawiamy zmienną z całym tym wyrażeniem g(v). I ostatnia pozycja: v i stała a. Podstawiamy więc v za a. I uwaga, musimy to podstawić wszędzie, więc także wewnątrz g(v), z którego zrobi się g(a).

Anna: Czyli po pierwszej fazie mamy z obu wyrażeń jedno takie samo: P(w, g(a), a)?

Lukáš: Dokładnie tak! A teraz to nowe wyrażenie porównamy z tym trzecim, P(h(u), u, y). I jedziemy znowu od lewej.

Anna: Czyli w podstawiam za h(u). Potem mam g(a) i u, więc u podstawiam za g(a). I na koniec a i y, więc y podstawiam za stałą a.

Lukáš: Perfekcyjnie! Zrobiłaś to na szóstkę. A wszystkie te podstawienia, które zrobiliśmy, razem tworzą ten poszukiwany najogólniejszy unifikator. To właściwie taki przepis, jak te wyrażenia ujednolicić.

Anna: Rozumiem. To takie stopniowe układanie puzzli. A do czego dokładnie to jest dobre w praktyce? To chyba zostawimy na następny raz, co?

Anna: Czyli unifikacja pomaga nam znaleźć wspólny język między różnymi wyrażeniami. Ale do czego to właściwie prowadzi? Co jest tym następnym krokiem?

Lukáš: Świetne pytanie! Ten następny krok to super potężna metoda, która nazywa się rezolucja. To właściwie taki logiczny detektyw.

Anna: Logiczny detektyw? To brzmi ciekawie. Co dokładnie bada?

Lukáš: Szuka sprzeczności! Sedno polega na znalezieniu dwóch takich samych wyrażeń, gdzie jedno jest w negacji. Na przykład P(f(x)) i jednocześnie ¬P(f(x)). Ponieważ zachodzenie obu naraz to bzdura, znoszą się nawzajem.

Anna: Jasne, jak plus pięć i minus pięć. A co jeśli te wyrażenia nie są zupełnie takie same?

Lukáš: Właśnie tam wkracza nasza unifikacja! Użyjemy podstawienia, żeby je ujednolicić, a potem możemy je wyeliminować. Ale uwaga, musi chodzić o ten sam predykat! Nie możesz wyeliminować P(coś) i ¬S(coś). To byłoby jak dodawanie jabłek i zanegowanych gruszek.

Anna: Dobra, jabłka z gruszkami nie. Pokaż mi przykład.

Lukáš: No to na przykład mamy dwa wiersze: w jednym jest ¬P(f(x,y)) ∨ Q(y), a w drugim ¬Q(z). Widzisz tam coś, co dałoby się ruszyć?

Anna: No, Q(y) i ¬Q(z) wyglądają podejrzanie. Gdybyśmy za 'z' podstawili 'y'...

Lukáš: Dokładnie! Podstawienie z za y, i nagle mamy Q(y) i ¬Q(y). One się znoszą i zostaje nam tylko ¬P(f(x,y)). Proste, prawda?

Anna: To ma sens. Ale co, jeśli przeszkadzają nam tam te kwantyfikatory, to 'dla wszystkich' i 'istnieje'?

Lukáš: Świetna obserwacja. Zanim zabierzemy się do bardziej skomplikowanych rezolucji, musimy posprzątać w formułach. A do tego mamy prenexową postać normalną, w skrócie PPN.

Anna: Kolejny skrót! Co oznacza?

Lukáš: Celem jest umieszczenie wszystkich kwantyfikatorów zupełnie na początku formuły. Po prostu wszystkie je wystawiamy przed nawiasy.

Anna: I tak po prostu? Bezkarnie je przesuwać?

Lukáš: Prawie. Zazwyczaj tak, ale musisz uważać na jedną rzecz. Jeśli przesuwasz kwantyfikator, na przykład ∃z, przez część formuły, gdzie już jakieś 'z' jest, musisz go przemianować. Na przykład na 'v'. Inaczej byłoby w tym zamieszanie.

Anna: Czyli po prostu zapewnię, żeby każda nazwa zmiennej była unikalna w danym kontekście. Logiczne.

Lukáš: Dokładnie. A jak już mamy wszystkie kwantyfikatory ładnie w rzędzie na początku, przychodzi ostatni krok czyszczenia: Skolemizacja.

Anna: To brzmi prawie jak jakieś zaklęcie.

Lukáš: Trochę. Skolemizacją pozbywamy się wszystkich kwantyfikatorów egzystencjalnych, czyli tych '∃'. Po prostu je usuwamy.

Anna: Czekaj, tak po prostu je usuwamy? To przecież zmieni znaczenie, prawda?

Lukáš: Zmieni, ale kontrolowanie! Zamiast zmiennej, która tam była, na przykład 'z', podstawiamy tak zwaną funkcję Skolema. Oznaczamy ją na przykład fz. A do nawiasu tej funkcji wstawiamy wszystkie zmienne z kwantyfikatorów '∀', które stały przed naszym '∃z'.

Anna: Aha! Czyli jeśli na początku było ∀x ∀y ∃z, to zamiast 'z' będziemy teraz pisać fz(x,y)?

Lukáš: Bingo! Całkowicie dokładnie. A jeśli przypadkiem żadne '∀' przed '∃' by nie było, stanie się z tego stała. To elegancki sposób na pozbycie się egzystencji i przygotowanie gruntu pod samą rezolucję. I właśnie do niej teraz wrócimy przy bardziej skomplikowanych przykładach.

Anna: ...dokładnie tak. A to świetnie prowadzi nas do kolejnego tematu, którym są notatki do nauki. Mam wrażenie, że mnóstwo studentów tylko pasywnie zapisuje to, co słyszy.

Lukáš: To jest ogromny błąd! Pasywne notatki są prawie na nic. To jak słuchanie muzyki, ale niesłyszenie melodii.

Anna: Dobra, to jak do tego podejść „aktywnie”? Co to dokładnie oznacza w praktyce?

Lukáš: Oznacza to myślenie o tym, co piszesz. Zamiast dosłownego przepisywania z prezentacji, staraj się przeformułować główne myśli własnymi słowami. To ogromna różnica.

Anna: Czyli moje notatki, które w liceum wyglądały raczej jak sztuka abstrakcyjna pełna strzałek i własnych skrótów, były właściwie poprawne?

Lukáš: Dokładnie tak! Jeśli to pomogło ci to zapamiętać, to było genialne. Celem nie jest posiadanie pięknego zeszytu na Instagram, ale funkcjonalnych notatek dla twojego mózgu.

Anna: A co z takimi tekstami jak „nienawidzę tego przedmiotu” napisanymi przez całą stronę? To chyba za bardzo nie pomoże, co?

Lukáš: To naprawdę nie. To tylko wentylacja frustracji, a nie efektywna nauka. Kluczowe jest oddzielenie emocji od faktów i staranie się strukturyzować nawet informacje, które cię akurat nie bawią.

Anna: Rozumiem. Podsumowując: myśleć, przeformułowywać i nie rysować w zeszycie wściekłych buziek. Przejdźmy teraz do konkretnych metod...

Anna: No to na koniec ostatnia szybka runda. Taka zgadywanka. Jesteś gotowy?

Lukáš: Jestem! Mam nadzieję, że nie polegnę.

Anna: Dobra. Kto to jest ten typowy nerd w okrągłych okularach, który na żadnym zdjęciu nie ma brody?

Lukáš: To będzie na pewno Kurt Gödel. Jasna sprawa.

Anna: Dokładnie tak! A co ten, co wygląda trochę jak Mike z Breaking Bad? Łysy, też okrągłe okulary...

Lukáš: Ten opis pasuje idealnie do Davida Hilberta. To świetne skojarzenie!

Anna: Prawda? Dobrze, kto jest często widywany z fajką, zazwyczaj jako starszy pan z siwymi włosami?

Lukáš: To jest Bertrand Russell. Klasyk. Jego zdjęcia z fajką są ikoniczne.

Anna: Perfekcyjnie. I ostatni... ze wszystkich ma najdłuższą brodę. I to chyba jedyne zdjęcie, gdzie ma włosy.

Lukáš: Gottlob Frege! Ta jego pełna broda jest niezapomniana.

Anna: Super, zdałeś to na szóstkę! I tym samym jesteśmy na końcu dzisiejszego odcinka.

Lukáš: Dokładnie tak. Omówiliśmy naprawdę sporo, od podstaw logiki zdań aż po słynnych logików i ich... brody.

Anna: Dokładnie tak. Mamy nadzieję, że dobrze się bawiliście i nauczyliście czegoś nowego. Dzięki za słuchanie!

Lukáš: Trzymajcie się ciepło i do usłyszenia w kolejnym odcinku Studyfi Podcastu.