Rachunek kwantyfikatorów - Polski Serwis Naukowy

Rachunek predykatów pierwszego rzędu – (ang. first order predicate calculus) to system logiczny, w którym zmienna, na której oparty jest kwantyfikator, może być elementem pewnej wybranej dziedziny (zbioru), nie może natomiast być zbiorem takich elementów. Tak więc nie mogą występować kwantyfikatory typu "dla każdej funkcji z X na Y ..." (gdyż funkcja jest podzbiorem X × Y), "istnieje własność p, taka że ..." czy "dla każdego podzbioru X zbioru Z ...". Rachunek ten nazywa się też krótko rachunkiem kwantyfikatorów, ale często używa się też nazwy logika pierwszego rzędu (szczególnie wśród matematyków zajmujących się logiką matematyczną).

Równoważność (lub: ekwiwalencja) – twierdzenie, w którym teza jest warunkiem koniecznym jak i dostatecznym przesłanki. To zdanie zapisuje się za pomocą spójnika wtedy i tylko wtedy, gdy.
Kurt Gödel (1906-1978) – austriacki logik i matematyk; autor ważnych twierdzeń z zakresu logiki matematycznej, współautor jednej z aksjomatyk teorii mnogości. Do najbardziej znanych osiągnięć matematycznych Gödla należą twierdzenia o niezupełności i niesprzeczności bogatszych teorii dedukcyjnych (to znaczy takich, które obejmują arytmetykę liczb naturalnych).

Na przykład w rachunku predykatów pierwszego rzędu można zapisać zdanie "dla dowolnej liczby rzeczywistej istnieje liczba większa", jednak nie można zapisać "każdy zbiór liczb rzeczywistych ma kres górny", gdyż wówczas kwantyfikator ogólny musiałby przebiegać wszystkie możliwe podzbiory zbioru liczb rzeczywistych i potrzebny byłby rachunek predykatów co najmniej drugiego rzędu.

Forma preneksowa (ang. prenex form lub prenex normal form) to taka postać formuły logicznej, w której wszystkie kwantyfikatory przesunięte są na początek formuły. Inna jej nazwa to przedrostkowa postać normalna.
Kwantyfikator – termin przyjęty w matematyce i logice matematycznej na oznaczenie zwrotów: dla każdego, istnieje takie i im pokrewnych, a także odpowiadającym im symbolom wiążacym zmienne w formułach. Są podstawowym elementem w rozwoju logiki pierwszego rzędu.

Rachunek predykatów pierwszego rzędu w ogólnym przypadku nie jest rozstrzygalny (w przeciwieństwie do rachunku zdań), lecz półrozstrzygalny (czyli rekurencyjnie przeliczalny), ale jeszcze nadaje się do komputerowej analizy (co już niekoniecznie można powiedzieć o rachunku predykatów wyższych rzędów, które dopuszczają kwantyfikatory dla zbiorów).

Ciąg – w matematyce pojęcie oddające intuicję ponumerowania, czy też uporządkowania elementów zbioru. W zależności od rodzaju elementów zbioru stosuje się różne nazwy: w przypadku liczb mówi się o ciągach liczbowych, bądź bardziej precyzyjnie, np. w przypadku zbioru liczb całkowitych, rzeczywistych czy zespolonych, ciąg nazywa się wtedy odpowiednio ciągiem całkowitoliczbowym, rzeczywistym i zespolonym. Jeśli elementami zbioru są funkcje, to ciąg nazywa się ciągiem funkcyjnym. Ciąg powstały poprzez wybranie elementów innego ciągu nazywa się podciągiem.
Saharon Shelah (hebr. שהרן שלח) (ur. 3 lipca 1945 w Jerozolimie), izraelski matematyk, laureat wielu nagród, w tym Nagrody Wolfa z matematyki w 2001 roku. Profesor matematyki na Uniwersytecie Hebrajskim w Jerozolimie i w Rutgers University (stan New Jersey).

Znaczna część rozważań matematycznych może być sformalizowana na gruncie logiki pierwszego rzędu. Ponadto logika ta ma wiele własności czyniących ją bardziej użyteczną od innych logik, co ma wpływ na pewne preferowanie teorii formalizowalnych na jej gruncie.

W literaturze istnieje szereg równoważnych rozwinięć tego tematu. Prezentacja przedstawiona poniżej jest do pewnego stopnia oparta o książkę Martina Goldsterna i Haima Judaha. Wśród innych źródeł omawiających te zagadnienia należy wymienić podręcznik Witolda Pogorzelskiego czy też książkę Zofii Adamowicz i Pawła Zbierskiego. Bardzo popularnym jest też opracowanie Josepha Shoenfielda.

Struktura matematyczna - zbiór obiektów matematycznych połączonych w pewien system. Często można się spotkać z innymi nazwami struktury matematycznej, na przykład: model, system semantyczny, model semantyczny, dziedzina, struktura pierwszego rzędu.
Teoria mnogości (również: teoria zbiorów) – dział matematyki a zarazem logiki matematycznej zapoczątkowany przez niemieckiego matematyka Georga Cantora pod koniec XIX wieku. Początkowo wzbudzała wiele kontrowersji, jednak wraz z postępem matematyki zaczęła ona pełnić rolę fundamentu, na którym opiera się większość matematycznych rozważań.

Wstęp do formalizacji

Logika pierwszego rzędu jest podstawą, na której formalizujemy większość matematyki. We wstępie do wspomnianej powyżej książki Goldsterna i Judaha traktującej właśnie o tej tematyce, Saharon Shelah napisał: [Na gruncie matematyki] możemy zdefiniować czym jest dowód i wykazać, że w pewnym sensie "być prawdziwym" i "mieć dowód" znaczą to samo (twierdzenie Gödla o pełności). (...) Nie możemy wyciągnąć sami siebie z bagna za włosy: nie możemy udowodnić w naszym systemie, że nie ma w nim sprzeczności (twierdzenie Gödla o niezupełności) (...) Możemy zbudować ogólną teorię teorii matematycznych (teoria modeli).

System rachunku predykatów pierwszego rzędu składa się z:

Działanie – w matematyce i logice jest to operacja na jednym lub większej liczbie elementów nazywanych argumentami lub operandami, wynikiem której jest element nazywany wynikiem działania.
Twierdzenie o zwartości to twierdzenie mówiące, że nieskończony zbiór zdań rachunku predykatów pierwszego rzędu jest spełnialny, jeśli tylko każdy jego podzbiór skończony jest spełnialny. Równoważnie, jeśli taki zbiór jest sprzeczny, to istnieje jego skończony podzbiór, który jest sprzeczny.

zmiennych nazwowych (litery, za które wolno podstawić nazwy dowolnych przedmiotów)

stałych nazwowych (nazwy własne przedmiotów)

liter predykatowych (predykaty)

symboli funkcyjnych (funktory nazwotwórcze od argumentów nazwowych)

stałych logicznych (spójniki prawdziwościowe rachunku zdań i kwantyfikatory)

znaków pomocniczych (nawiasy)

symbolu równości.

Używając symboli wymienionych powyżej i przestrzegając naturalnych reguł możemy budować poprawnie zbudowane napisy. Niektóre z tych napisów mogą być interpretowane jako nazwy na pewne obiekty, a inne będą mówić o własnościach tych obiektów. Pierwsza grupa napisów poprawnie zbudowanych to termy, a druga to zdania. Przykładowy schemat kwantyfikatorowy zdania: Nie ma czegoś, czym ciekawią się wszyscy...

Twierdzenie Gödla to jeden z najbardziej znanych rezultatów logiki matematycznej. W istocie znane są dwa różne twierdzenia Gödla: pierwsze z nich to twierdzenie o niezupełności, drugie zaś to jego bezpośredni (równoważny) wniosek nazywany też twierdzeniem o niedowodliwości niesprzeczności. Oba twierdzenia zostały udowodnione w 1931 roku przez austriackiego matematyka i logika Kurta Gödla. Uważa się również, że twierdzenia te dają negatywną odpowiedź na drugi problem Hilberta, i w ten sposób mają spore znaczenie w filozofii matematyki. Inne bardzo ważne twierdzenia Gödla to: twierdzenie o istnieniu modelu i twierdzenie o nierozstrzygalności (patrz: teoria, struktura matematyczna).
Logika matematyczna – dział matematyki, który wyodrębnił się jako samodzielna dziedzina na przełomie XIX i XX wieku, wraz z dążeniem do dogłębnego zbadania podstaw matematyki. Koncentruje się ona na analizowaniu zasad rozumowania oraz pojęć z nim związanych z wykorzystaniem sformalizowanych oraz uściślonych metod i narzędzi matematyki.

$\neg(\exist x)(S(x)\and(\forall y)(I(y)\implies C(y,x)))$

(czyt.: Nie istnieje taki x, że x jest substratem wiedzy, i dla każdego y, że jeżeli y jest istotą rozumną, to y ciekawi się x.)

Następnie ustalimy reguły wnioskowania a także metody interpretacji naszych napisów.

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)