Rachunek zdań - Propositional calculus

Rachunek zdań jest gałęzią logiki . Jest również nazywany zdaniowa logika , logika rachunek , rachunek zdań , zdań logiki , albo czasami klasyczny rachunek zdań . Zajmuje się zdaniami (które mogą być prawdziwe lub fałszywe) oraz relacjami między zdaniami, w tym konstruowaniem opartych na nich argumentów. Zdania złożone są tworzone przez łączenie zdań spójnikami logicznymi . Zdania, które nie zawierają spójników logicznych, nazywane są zdaniami atomowymi.

W przeciwieństwie do logiki pierwszego rzędu, logika zdaniowa nie zajmuje się obiektami nielogicznymi, predykatami na ich temat ani kwantyfikatorami . Jednak cała machina logiki zdań zawarta jest w logice pierwszego rzędu i logice wyższego rzędu. W tym sensie logika zdań jest podstawą logiki pierwszego rzędu i logiki wyższego rzędu.

Wyjaśnienie

Spójniki logiczne znajdują się w językach naturalnych. Na przykład w języku angielskim niektóre przykłady to „and” ( spójnik ), „or” ( alternatywa ), „not” ( negacja ) i „if” (ale tylko wtedy, gdy są używane do oznaczenia warunków warunkowych ).

Oto przykład bardzo prostego wnioskowania z zakresu logiki zdań:

Przesłanka 1: Jeśli pada deszcz, to jest pochmurno.
Przesłanka 2: Pada deszcz.
Wniosek: jest pochmurno.

Zarówno przesłanki, jak i zakończenie są propozycjami. Przesłanki przyjmuje się za pewnik i przy zastosowaniu modus ponens ( zasady wnioskowania ) następuje wniosek.

Ponieważ logika zdań nie zajmuje się strukturą zdań poza punkt, w którym nie można ich już rozłożyć za pomocą spójników logicznych, wnioskowanie to można powtórzyć, zastępując zdania atomowe literami zdań, które są interpretowane jako zmienne reprezentujące zdania:

Przesłanka 1:
Przesłanka 2:
Wniosek:

To samo można zwięźle ująć w następujący sposób:

Kiedy P jest interpretowane jako „pada deszcz”, a Q jako „pochmurno”, powyższe wyrażenia symboliczne mogą dokładnie odpowiadać oryginalnemu wyrażeniu w języku naturalnym. Nie tylko to, ale będą też korespondować z każdym innym wnioskowaniem tej formy , które będzie ważne na tej samej podstawie, na której to wnioskowanie.

Rachunek zdań mogą być badane za pośrednictwem oficjalnego systemu , w którym formuły o języku formalnym mogą być interpretowane do reprezentowania propozycje . Systemu z aksjomatów i reguł wnioskowania pozwala na pewne wzory pochodzić. Te wyprowadzone formuły nazywane są twierdzeniami i mogą być interpretowane jako twierdzenia prawdziwe. Skonstruowany ciąg takich formuł jest znany jako wyprowadzenie lub dowód, a ostatnią formułą ciągu jest twierdzenie. Wyprowadzenie może być interpretowane jako dowód zdania reprezentowanego przez twierdzenie.

Gdy system formalny jest używany do reprezentowania logiki formalnej, tylko litery instrukcji (zwykle wielkie litery alfabetu łacińskiego, takie jak , i ) są reprezentowane bezpośrednio. Propozycje języka naturalnego, które powstają podczas ich interpretacji, są poza zakresem systemu, a relacja między systemem formalnym a jego interpretacją jest również poza samym systemem formalnym.

W klasycznej logice prawdziwościowo-funkcjonalnej zdań , formuły są interpretowane jako posiadające dokładnie jedną z dwóch możliwych wartości prawdziwości , wartość prawdziwości prawdy lub wartość prawdziwości fałszu . Przestrzegana jest zasada biwalencji i prawo wyłączonego środka . Funkcjonalna logika zdań zdefiniowana jako taka i systemy z nią izomorficzne są uważane za logikę zerowego rzędu . Możliwe są jednak również alternatywne logiki zdań. Aby uzyskać więcej informacji, zobacz Inne rachunki logiczne poniżej.

Historia

Chociaż logika zdań (która jest wymienna z rachunkiem zdań) była sugerowana przez wcześniejszych filozofów, została rozwinięta w logikę formalną ( logika stoicka ) przez Chrysippusa w III wieku pne i rozwinięta przez jego następcę, stoików . Logika koncentrowała się na propozycjach . Ten postęp różnił się od tradycyjnej logiki sylogistyki , która koncentrowała się na terminach . Jednak większość oryginalnych pism zaginęła, a logika zdań rozwinięta przez stoików nie była już rozumiana później w starożytności. W konsekwencji system został zasadniczo odświeżony przez Petera Abelarda w XII wieku.

Logika zdań została ostatecznie udoskonalona przy użyciu logiki symbolicznej . 17. / 18th-century matematyk Gottfried Leibniz był uznawany za twórcę logiki symbolicznej dla jego pracy z ratiocinator nazębnego . Chociaż jego praca była pierwszą tego rodzaju, nie była znana szerszej społeczności logicznej. W konsekwencji wiele postępów osiągniętych przez Leibniza zostało odtworzonych przez logików takich jak George Boole i Augustus De Morgan — całkowicie niezależnych od Leibniza.

Tak jak logikę zdań można uznać za postęp w stosunku do wcześniejszej logiki sylogistyki, logikę predykatów Gottloba Fregego można również uznać za postęp w stosunku do wcześniejszej logiki zdań. Jeden z autorów opisuje logikę predykatów jako połączenie „charakterystycznych cech logiki sylogistyki i logiki zdań”. W konsekwencji logika predykatów zapoczątkowała nową erę w historii logiki; jednak po Fregego nadal dokonywano postępów w logice zdań, w tym dedukcję naturalną , drzewa prawdy i tabele prawdy . Odliczenie naturalne zostało wynalezione przez Gerharda Gentzena i Jana Łukasiewicza . Drzewa prawdy zostały wynalezione przez Everta Willema Betha . Wynalezienie tablic prawdy ma jednak niepewną atrybucję.

W pracach Fregego i Bertranda Russella znajdują się idee wpływające na wynalezienie tablic prawdy. Faktyczna struktura tabelaryczna (sformatowana jako tabela) jest ogólnie przypisywana Ludwigowi Wittgensteinowi lub Emilowi ​​Postowi (lub obu, niezależnie). Oprócz Fregego i Russella, inni, którym przypisuje się pomysły poprzedzające tabele prawdy, to Philo, Boole, Charles Sanders Peirce i Ernst Schröder . Inni, którym przypisuje się strukturę tabelaryczną, to Jan Łukasiewicz , Alfred North Whitehead , William Stanley Jevons , John Venn i Clarence Irving Lewis . W końcu niektórzy doszli do wniosku, jak John Shosky, że „Nie jest jasne, czy jakakolwiek osoba powinna otrzymać tytuł »wynalazcy« tablic prawdy”.

Terminologia

Ogólnie rzecz biorąc, rachunek różniczkowy to system formalny, który składa się ze zbioru wyrażeń składniowych ( dobrze sformułowanych ), wyodrębnionego podzbioru tych wyrażeń (aksjomatów) oraz zbioru reguł formalnych, które definiują konkretną relację binarną , mającą na celu interpretować jako równoważność logiczną na przestrzeni wyrażeń.

Gdy system formalny ma być systemem logicznym , wyrażenia mają być interpretowane jako zdania, a reguły, znane jako reguły wnioskowania , zazwyczaj mają zachowywać prawdziwość. W tym ustawieniu reguły, które mogą zawierać aksjomaty , mogą być następnie używane do wyprowadzania („wnioskowania”) formuł reprezentujących zdania prawdziwe — z podanych formuł reprezentujących zdania prawdziwe.

Zbiór aksjomatów może być pusty, niepusty zbiór skończony lub zbiór przeliczalnie nieskończony (patrz schemat aksjomatu ). Formalnej gramatyki rekurencyjnie definiuje wyrażeń i formuł o języku . Dodatkowo można podać semantykę określającą prawdę i wartościowania (lub interpretacje ).

Język z rachunku zdań składa się z

  1. zbiór prymitywnych symboli, różnie nazywanych formułami atomowymi , symbolami zastępczymi , literami zdań lub zmiennymi , oraz
  2. zbiór symboli operatorów, różnie interpretowanych jako operatory logiczne lub spójniki logiczne .

Prawidłowo sformułowana formuła to dowolna formuła atomowa lub dowolna formuła, którą można zbudować z formuł atomowych za pomocą symboli operatorowych zgodnie z zasadami gramatyki.

Matematycy czasami rozróżniają stałe zdaniowe, zmienne zdaniowe i schematy. Stałe zdaniowe reprezentują pewne szczególne zdanie, podczas gdy zmienne zdaniowe obejmują zbiór wszystkich zdań atomowych. Schematy jednak obejmują wszystkie propozycje. Często stałe zdaniowe są reprezentowane przez A , B i C , zmienne zdaniowe przez P , Q i R , a litery schematyczne są często literami greckimi, najczęściej φ , ψ i χ .

Podstawowe koncepcje

Poniżej przedstawiono standardowy rachunek zdań. Istnieje wiele różnych sformułowań, które są mniej więcej równoważne, ale różnią się szczegółami:

  1. ich język (tj. określony zbiór symboli pierwotnych i symboli operatorów),
  2. zbiór aksjomatów lub wyróżnionych formuł i
  3. zbiór reguł wnioskowania.

Każde zdanie może być reprezentowane za pomocą litery zwanej „stałą zdania”, analogicznie do reprezentowania liczby przez literę w matematyce (np. a = 5 ). Wszystkie zdania wymagają dokładnie jednej z dwóch wartości prawdziwości: prawdziwej lub fałszywej. Na przykład niech P będzie twierdzeniem, że na zewnątrz pada deszcz. Będzie to prawda ( P ), jeśli na zewnątrz pada deszcz, a fałsz w przeciwnym razie ( ¬ P ).

  • Następnie definiujemy operatory funkcjonalno- prawdowe, zaczynając od negacji. Kontakty P oznacza negację P , które mogą być traktowane jako odmowa P . W powyższym przykładzie, ¬ P wyraża to nie pada na zewnątrz, lub bardziej standardowych czytaniu: „To nie jest tak, że pada deszcz na zewnątrz.” Gdy P jest prawdziwe, ¬ P jest fałszywe; a gdy P jest fałszywe, ¬ P jest prawdziwe. W rezultacie, ¬ ¬ P zawsze ma tę samą wartość logiczną jako P .
  • Koniunkcja to spójnik prawdziwościowo-funkcyjny, który tworzy zdanie z dwóch prostszych zdań, na przykład P i Q . Koniunkcja P i Q jest zapisywana jako PQ i wyraża, że ​​każde z nich jest prawdziwe. Czytamy PQ jako „ P i Q ”. Dla dowolnych dwóch zdań istnieją cztery możliwe przypisania wartości logicznych:
    1. P jest prawdziwe, a Q jest prawdziwe
    2. P to prawda, a Q to fałsz
    3. P jest fałszywe, a Q jest prawdziwe
    4. P jest fałszywe, a Q jest fałszywe
Koniunkcja P i Q jest prawdziwa w przypadku 1, a w przeciwnym razie jest fałszywa. Gdzie P to twierdzenie, że na zewnątrz pada deszcz, a Q to twierdzenie, że nad Kansas jest front zimny, PQ jest prawdziwe, gdy na zewnątrz pada deszcz, a nad Kansas jest front zimny. Jeśli na zewnątrz nie pada, to P ∧ Q jest fałszywe; a jeśli nie ma frontu zimnego nad Kansas, to PQ również jest fałszywe.
  • Rozdzielenie przypomina koniunkcję, ponieważ tworzy zdanie z dwóch prostszych zdań. Piszemy to PQ , a czytamy „ P lub Q ”. Wyraża, że ​​albo P albo Q jest prawdziwe. Tak więc w przypadkach wymienionych powyżej alternatywa P z Q jest prawdziwa we wszystkich przypadkach — z wyjątkiem przypadku 4. Korzystając z powyższego przykładu, alternatywa wyraża, że ​​albo na zewnątrz pada deszcz, albo nad Kansas jest zimny front. (Zauważ, że to użycie alternatywy ma przypominać użycie angielskiego słowa „lub”. Jednak jest ono najbardziej podobne do angielskiego inkluzywnego „lub”, które może być użyte do wyrażenia prawdziwości co najmniej jednego z dwóch zdań. To nie jest takie, jak angielskie wykluczające „lub", które wyraża prawdziwość dokładnie jednego z dwóch zdań. Innymi słowy, wykluczające „lub" jest fałszywe, gdy zarówno P, jak i Q są prawdziwe (przypadek 1). Przykład wykluczającego lub jest: Możesz mieć bajgla lub ciastko, ale nie jedno i drugie. Często w języku naturalnym, biorąc pod uwagę odpowiedni kontekst, dodatek „ale nie oba" jest pomijany, ale jest dorozumiany. Jednak w matematyce „lub" zawsze obejmuje lub; jeśli ma być wyłączny lub ma być określony, prawdopodobnie przez „xor”.)
  • Warunek materialny również łączy dwa prostsze zdania i piszemy PQ , które czytamy "jeśli P to Q ". Zdanie na lewo od strzałki nazywa się poprzednikiem, a zdanie na prawo nazywa się następnikiem. (Nie ma takiego oznaczenia dla koniunkcji lub alternatywy, ponieważ są to operacje przemienne). Wyraża, że Q jest prawdziwe, gdy P jest prawdziwe. Zatem PQ jest prawdziwe w każdym powyższym przypadku z wyjątkiem przypadku 2, ponieważ jest to jedyny przypadek, gdy P jest prawdziwe, a Q nie. Na przykładzie, jeśli P, to Q wyraża, że ​​jeśli na zewnątrz pada deszcz, to nad Kansas jest zimny front. Warunki materialne są często mylone z przyczynami fizycznymi. Warunek materialny łączy jednak tylko dwa zdania na podstawie ich wartości prawdziwościowych — co nie jest stosunkiem przyczyny i skutku. W literaturze jest kontrowersyjne, czy implikacja materialna stanowi przyczynę logiczną.
  • Dwuwarunkowe łączy dwa prostsze zdania i piszemy PQ , które jest czytane „ P wtedy i tylko wtedy, gdy Q ”. Wyraża ona, że P i Q mają tę samą wartość prawdziwości, aw przypadkach 1 i 4. ' P jest prawdziwe wtedy i tylko wtedy, gdy Q ' jest prawdziwe, aw przeciwnym razie jest fałszywe.

Bardzo pomocne jest przyjrzenie się tabelom prawdy dla tych różnych operatorów, a także metodzie tabel analitycznych .

Zamknięcie w ramach operacji

Logika zdań jest zamknięta w spójnikach prawdziwościowo-funkcjonalnych. To znaczy, że każde zdanie φ , ¬ φ również jest zdaniem . Podobnie, za propozycji cp i ψ , cpψ jest propozycja, podobnie do alternatywy warunkowym i biconditional. Oznacza to, na przykład, że φψ jest zdaniem, a więc może być połączone z innym zdaniem. Aby to przedstawić, musimy użyć nawiasów, aby wskazać, które twierdzenie jest połączone z którym. Na przykład, PQR nie jest dobrze sformułowaną formułą, ponieważ nie wiemy, czy łączymy PQ z R czy też łączymy P z QR . Zatem musimy napisać albo ( PQ ) ∧ R , aby reprezentować to pierwsze , albo P ∧ ( QR ) reprezentujące to drugie . Oceniając warunki prawdziwości, widzimy, że oba wyrażenia mają te same warunki prawdziwości (będą prawdziwe w tych samych przypadkach), a ponadto, że każde zdanie utworzone przez dowolne koniunkcje będzie miało te same warunki prawdziwości, niezależnie od położenia nawiasów. Oznacza to, że koniunkcja jest asocjacyjna, jednak nie należy zakładać, że nawiasy nigdy nie służą celowi. Na przykład zdanie P ∧ ( QR ) nie ma tych samych warunków prawdziwości co ( PQ ) ∨ R , więc są to różne zdania rozróżniane tylko nawiasami. Można to zweryfikować za pomocą metody tabeli prawdy, o której mowa powyżej.

Uwaga: Dla dowolnej liczby stałych zdaniowych możemy utworzyć skończoną liczbę przypadków, które wymieniają ich możliwe wartości prawdziwościowe. Prostym sposobem na wygenerowanie tego są tablice prawdy, w których pisze się P , Q , ..., Z , dla dowolnej listy k stałych zdań — to znaczy dowolnej listy stałych zdań z k wpisami. Poniżej tej listy wpisujemy 2 k wierszy, a poniżej P w pierwszej połowie wierszy wpisujemy prawdę (lub T), a w drugiej połowie fałsz (lub F). Poniżej Q w jednej czwartej wiersza wpisujemy T, następnie w jednej czwartej F, następnie w jednej czwartej T i w ostatniej ćwiartce F. W następnej kolumnie dla każdego ósmego wiersza naprzemiennie pojawia się prawda i fałsz, a następnie szesnastych i tak dalej, aż ostatnia stała zdaniowa zmienia się między T i F dla każdego wiersza. Da to pełną listę przypadków lub przypisań wartości prawdziwościowych możliwych dla tych stałych zdaniowych.

Argument

Rachunek zdań definiuje następnie argument jako listę zdań. Ważnym argumentem jest lista zdań, z których ostatnie wynika z pozostałych lub jest z nich implikowane. Wszystkie inne argumenty są nieprawidłowe. Najprostszym poprawnym argumentem jest modus ponens , którego jednym z przykładów jest następująca lista propozycji:

To jest lista trzech propozycji, każda linia jest propozycją, a ostatnia wynika z pozostałych. Pierwsze dwa wiersze nazywają się przesłankami, a ostatni wiersz wnioskiem. Mówimy, że każde zdanie C wynika z dowolnego zbioru zdań , jeśli C musi być prawdziwe, gdy każdy element zbioru jest prawdziwy. W powyższym argumencie, dla każdego P i Q , ilekroć PQ i P są prawdziwe, z konieczności Q jest prawdziwe. Zauważ, że gdy P jest prawdziwe, nie możemy rozpatrywać przypadków 3 i 4 (z tabeli prawdy). Gdy PQ jest prawdziwe, nie możemy rozpatrywać przypadku 2. Pozostaje tylko przypadek 1, w którym Q również jest prawdziwe. Zatem Q jest implikowane przez przesłanki.

To uogólnia schematycznie. Tak więc, gdzie φ i ψ mogą być w ogóle dowolnymi zdaniami,

Inne formy argumentów są wygodne, ale nie konieczne. Mając pełny zestaw aksjomatów (patrz poniżej dla jednego takiego zestawu), modus ponens wystarcza do udowodnienia wszystkich innych form argumentacji w logice zdań, a zatem mogą być uważane za pochodną. Zauważ, że nie dotyczy to rozszerzenia logiki zdań na inne logiki, takie jak logika pierwszego rzędu . Logika pierwszego rzędu wymaga co najmniej jednej dodatkowej reguły wnioskowania w celu uzyskania kompletności .

Znaczenie argumentu w logice formalnej polega na tym, że można uzyskać nowe prawdy z prawd ustalonych. W pierwszym przykładzie powyżej, biorąc pod uwagę te dwie przesłanki, prawda o Q nie jest jeszcze znana ani stwierdzona. Po przedstawieniu argumentu wywnioskowano Q. W ten sposób definiujemy system dedukcyjny jako zbiór wszystkich zdań, które można wydedukować z innego zbioru zdań. Na przykład, mając dany zbiór zdań , możemy zdefiniować system dedukcyjny Γ , który jest zbiorem wszystkich zdań wynikających z A . Reiteration zawsze zakłada się, tak . Również z pierwszego elementu A , ostatniego elementu, a także z modus ponens, R jest konsekwencją, i tak . Ponieważ jednak nie uwzględniliśmy wystarczająco pełnych aksjomatów, nic więcej nie można wydedukować. Tak więc, mimo że większość systemów dedukcyjnych badanych w logice zdań jest w stanie wydedukować , ten jest zbyt słaby, aby udowodnić takie twierdzenie.

Ogólny opis rachunku zdań

Rachunek zdań jest formalny system , w którym:

  • Zestaw alfa jest przeliczalnie nieskończony zestaw elementów zwanych symbole Propozycja lub zmienne propositional . Mówiąc syntaktycznie, są to najbardziej podstawowe elementy języka formalnego , inaczej nazywane formułami atomowymi lub elementami końcowymi . W poniższych przykładach elementami są zazwyczaj litery p , q , r i tak dalej.
  • Omega zestaw Ω skończony zestaw elementów zwanych symbole operatora lub Złączki logicznych . Zbiór Ω jest podzielony na rozłączne podzbiory w następujący sposób:

    W tej partycji znajduje się zbiór symboli operatorskich o arności j .

    W bardziej znanych rachunku zdań Ω dzieli się zwykle w następujący sposób:

    Często przyjmowana konwencja traktuje stałe wartości logiczne jako operatory arności zero, stąd:

    Niektórzy pisarze używają tyldy (~) lub N zamiast ¬ ; niektóre zastosowanie V, zamiast , jak i handlowe i (i), przy czym przedrostek K lub zamiast . Notacja różni się jeszcze bardziej dla zestawu wartości logicznych, a symbole takie jak {fałsz, prawda}, {F, T} lub {0, 1} są widoczne w różnych kontekstach zamiast .
  • Zestaw zeta to skończony zestaw reguł transformacji, które są nazywane regułami wnioskowania, gdy uzyskują aplikacje logiczne.
  • Jota zbiór jest przeliczalny zbiór początkowych punktów , które nazywane są aksjomatami gdy otrzymują interpretacje logicznych.

Język stanowi , znany również jako zestaw wzorów , formuł , jest indukcyjnie określona według następujących zasad:

  1. Podstawa: Każdy element zestawu alfa jest wzorem .
  2. Jeśli są formułami i jest w , to jest formułą.
  3. Zamknięte: nic innego nie jest formułą .

Wielokrotne stosowanie tych zasad pozwala na konstruowanie złożonych formuł. Na przykład:

  • Zgodnie z zasadą 1 p jest formułą.
  • Zgodnie z zasadą 2, jest formułą.
  • Zgodnie z zasadą 1, q jest formułą.
  • Zgodnie z zasadą 2, jest formułą.

Przykład 1. Prosty system aksjomatów

Niech , gdzie , , , definiuje się następująco:

  • Zbiór alfa to przeliczalnie nieskończony zbiór symboli, na przykład:
  • Z trzech spójników dla koniunkcji, alternatywy i implikacji ( , i ), jeden może być traktowany jako prymitywny, a dwa pozostałe mogą być zdefiniowane w terminach tego i negacji ( ¬ ). Wszystkie spójniki logiczne można zdefiniować jako jedyny wystarczający operator . Dwuwarunkowy ( ) można oczywiście zdefiniować w kategoriach koniunkcji i implikacji, przy czym zdefiniowano jako .
    Przyjęcie negacji i implikacji jako dwóch podstawowych operacji rachunku zdań jest równoznaczne z posiadaniem następującego podziału zbioru omega :
  • System aksjomatów zaproponowany przez Jana Łukasiewicza i używany jako część rachunku zdań w systemie Hilberta , formułuje rachunek zdań w tym języku w następujący sposób. Aksjomaty to wszystkie przypadki podstawienia :
  • Regułą wnioskowania jest modus ponens (tj. z p i , wnioskować q ). Następnie jest zdefiniowany jako , i jest zdefiniowany jako . Ten system jest używany w bazie danych dowodu formalnego Metamath set.mm.

Przykład 2. Naturalny system odliczeń

Niech , gdzie , , , definiuje się następująco:

  • Zbiór alfa to przeliczalnie nieskończony zbiór symboli, na przykład:
  • Przegrody omega ustawiają w następujący sposób:

W poniższym przykładzie rachunku zdań reguły transformacji mają być interpretowane jako reguły wnioskowania tzw. systemu dedukcji naturalnej . Przedstawiony tu konkretny system nie ma punktów początkowych, co oznacza, że ​​jego interpretacja dla zastosowań logicznych wywodzi swoje twierdzenia z pustego zbioru aksjomatów.

  • Zbiór punktów początkowych jest pusty, czyli .
  • Zbiór reguł transformacji, , jest opisany w następujący sposób:

Nasz rachunek zdań ma jedenaście reguł wnioskowania. Reguły te pozwalają nam wyprowadzić inne prawdziwe formuły, biorąc pod uwagę zestaw formuł, które z założenia są prawdziwe. Pierwsza dziesiątka po prostu stwierdza, że ​​możemy wywnioskować pewne dobrze sformułowane formuły z innych dobrze sformułowanych formuł. Jednak ostatnia reguła wykorzystuje rozumowanie hipotetyczne w tym sensie, że w założeniu reguły tymczasowo przyjmujemy (niesprawdzoną) hipotezę jako część zestawu wywnioskowanych formuł, aby sprawdzić, czy możemy wywnioskować pewną inną formułę. Ponieważ pierwsze dziesięć reguł tego nie robi, są one zwykle określane jako reguły niehipotetyczne , a ostatnia jako reguła hipotetyczna .

W opisie reguł transformacji możemy wprowadzić symbol metajęzyka . Jest to w zasadzie wygodny skrót do powiedzenia „wnioskuj to”. Format to , w którym Γ jest (prawdopodobnie pustym) zbiorem formuł zwanych przesłankami, a ψ jest formułą zwaną wnioskiem. Reguła transformacji oznacza, że ​​jeśli każde zdanie w Γ jest twierdzeniem (lub ma taką samą wartość logiczną jak aksjomaty), to ψ również jest twierdzeniem. Zauważ, że biorąc pod uwagę następującą regułę Wprowadzenie do koniunkcji , będziemy wiedzieć, że gdy Γ ma więcej niż jedną formułę, zawsze możemy bezpiecznie zredukować ją do jednej formuły za pomocą spójnika. Krótko mówiąc, od tego czasu możemy reprezentować Γ jako jedną formułę zamiast zestawu. Innym pominięciem dla wygody jest sytuacja, gdy Γ jest pustym zestawem, w którym to przypadku Γ może się nie pojawić.

Wprowadzenie do negacji
Od i wywnioskować .
To znaczy .
Eliminacja negacji
Od wywnioskować .
To znaczy .
Eliminacja podwójnej negacji
Z , wywnioskuj p .
To znaczy .
Wprowadzenie do koniunkcji
Na podstawie p i q wywnioskuj .
To znaczy .
Eliminacja koniunkcji
Z , wywnioskuj p .
Z , wywnioskuj q .
To znaczy, i .
Wprowadzenie do alternatywy
Z p wywnioskować .
Z q wywnioskuj .
To znaczy, i .
Eliminacja alternatywy
Z i i , wywnioskuj r .
To znaczy .
Wprowadzenie dwuwarunkowe
Od i wywnioskować .
To znaczy .
Eliminacja dwuwarunkowa
Od wywnioskować .
Od wywnioskować .
To znaczy, i .
Modus ponens (eliminacja warunkowa)
Z p i wywnioskuj q .
To znaczy .
Dowód warunkowy (wprowadzenie warunkowe)
Z [przyjęcie p pozwala na dowód q ], wywnioskuj .
To znaczy .

Podstawowe i pochodne formy argumentacji

Nazwa Kolejny Opis
Modus Ponens Jeśli p to q ; p ; dlatego q
Modus Tollens Jeśli p to q ; nie q ; dlatego nie p
Hipotetyczny sylogizm Jeśli p to q ; jeśli q to r ; zatem, jeśli p, to r
Sylogizm dysjunktywny Albo p lub q , albo oba; nie p ; dlatego q
Konstruktywny dylemat Jeśli p to q ; a jeśli r to s ; ale p lub r ; zatem q lub s
Destrukcyjny dylemat Jeśli p to q ; a jeśli r to s ; ale nie q czy nie s ; dlatego nie p lub nie r
Dylemat dwukierunkowy Jeśli p to q ; a jeśli r to s ; ale p lub nie s ; zatem q lub nie r
Uproszczenie p i q są prawdziwe; dlatego p jest prawdziwe
Spójnik p i q są prawdziwe oddzielnie; dlatego są razem prawdziwe
Dodatek p jest prawdziwe; dlatego alternatywa ( p lub q ) jest prawdziwa
Kompozycja Jeśli p to q ; a jeśli p to r ; dlatego jeśli p jest prawdziwe, to q i r są prawdziwe
Twierdzenie De Morgana (1) Negacja ( p i q ) jest równoważna. do (nie p lub nie q )
Twierdzenie De Morgana (2) Negacja ( p lub q ) jest równoważna. do (nie p i nie q )
Dojazd (1) ( p lub q ) jest równoważne. do ( q lub p )
Dojazd (2) ( p i q ) jest równoważne. do ( q i p )
Dojazdy (3) ( p jest równoważne do q ) jest równoważne. do ( q jest równoważne z p )
Stowarzyszenie (1) p lub ( q lub r ) jest równoważne. do ( p lub q ) lub r
Stowarzyszenie (2) p i ( q i r ) są równoważne. do ( p i q ) i r
Dystrybucja (1) p i ( q lub r ) są równoważne. do ( p i q ) lub ( p i r )
Dystrybucja (2) p lub ( q i r ) jest równoważne. do ( p lub q ) i ( p lub r )
Podwójna negacja oraz p jest równoważne negacji nie p
Transpozycja Jeśli p to q jest równoważne. do jeśli nie q to nie p
Implikacje materialne Jeśli p to q jest równoważne. nie p lub q
Równoważność materiałowa (1) ( p iff q ) jest równoważne. to (jeśli p jest prawdziwe, to q jest prawdziwe) i (jeśli q jest prawdziwe, to p jest prawdziwe)
Równoważność materiałowa (2) ( p iff q ) jest równoważne. do ( p i q są prawdziwe) lub (zarówno p i q są fałszywe)
Równoważność materiałowa (3) ( p iff q ) jest równoważne, zarówno ( p lub nie q jest prawdziwe), jak i (nie p lub q jest prawdziwe)
Wywóz z (jeśli p i q są prawdziwe, to r jest prawdziwe) możemy udowodnić (jeśli q jest prawdziwe, to r jest prawdziwe, jeśli p jest prawdziwe)
Przywóz Jeśli p to (jeśli q to r ) jest równoważne jeśli p i q to r
Tautologia (1) p jest prawdziwe jest równoważne. to p jest prawdziwe lub p jest prawdziwe
Tautologia (2) p jest prawdziwe jest równoważne. to p jest prawdziwe i p jest prawdziwe
Tertium non datur (prawo wyłączonego środka) p czy nie p jest prawdziwe
Prawo niesprzeczności p a nie p jest fałszywe, jest stwierdzeniem prawdziwym

Dowody w rachunku zdań

Jednym z głównych zastosowań rachunku zdań, interpretowanego dla zastosowań logicznych, jest określenie relacji logicznej równoważności między formułami zdań. Relacje te są określane za pomocą dostępnych reguł przekształceń, których ciągi nazywamy derywacjami lub dowodami .

W dalszej części dyskusji dowód przedstawiany jest jako ciąg ponumerowanych wierszy, przy czym każdy wiersz składa się z pojedynczej formuły, po której następuje powód lub uzasadnienie wprowadzenia tej formuły. Każda przesłanka argumentu, czyli założenie wprowadzone jako hipoteza argumentu, jest wymieniona na początku ciągu i oznaczona jako „przesłanka” zamiast innego uzasadnienia. Wniosek znajduje się w ostatnim wierszu. Dowód jest kompletny, jeśli każdy wiersz wynika z poprzednich przez poprawne zastosowanie reguły przekształcenia. (Aby zapoznać się z kontrastującym podejściem, zobacz drzewa dowodowe ).

Przykład dowodu w systemie dedukcji naturalnej

  • Wykazać, że AA .
  • Jeden z możliwych dowodów na to (który, choć ważny, zawiera więcej kroków niż jest to konieczne) może być zorganizowany w następujący sposób:
Przykład dowodu
Numer Formuła Powód
1 przesłanka
2 Od ( 1 ) przez alternatywę wprowadzenie
3 Od ( 1 ) i ( 2 ) przez spójnik wstęp
4 Od ( 3 ) przez eliminację koniunkcyjną
5 Podsumowanie od ( 1 ) do ( 4 )
6 Od ( 5 ) przez dowód warunkowy

Zinterpretuj jako „Zakładając A , wywnioskuj A ”. Czytaj jako „Zakładając nic, wywnioskuj, że A implikuje A ” lub „Jest tautologią, że A implikuje A ” lub „Zawsze jest prawdą, że A implikuje A ”.

Przykład dowodu w klasycznym systemie rachunku zdań

Dowodzimy teraz tego samego twierdzenia w systemie aksjomatycznym opisanym powyżej przez Jana Łukasiewicza , który jest przykładem klasycznego systemu rachunku zdań lub systemu dedukcyjnego w stylu Hilberta dla rachunku zdań.

Aksjomaty to:

(A1)
(A2)
(A3)

A dowód jest następujący:

  1.       (przykład (A1))
  2.       (przykład (A2))
  3.       (od (1) i (2) przez modus ponens )
  4.       (przykład (A1))
  5.       (od (4) i (3) przez modus ponens)

Rzetelność i kompletność zasad

Kluczowe właściwości tego zestawu reguł polegają na tym, że są solidne i kompletne . Nieformalnie oznacza to, że zasady są poprawne i nie są wymagane żadne inne zasady. Twierdzenia te można uczynić bardziej formalnymi w następujący sposób. Zauważmy, że dowody na słuszność i kompletność logiki zdań nie są same w sobie dowodami w logice zdań; są to twierdzenia w ZFC używane jako metateoria do udowodnienia właściwości logiki zdań.

Definiujemy przypisanie prawdy jako funkcję, która odwzorowuje zmienne zdaniowe na true lub false . Nieformalnie takie przypisanie prawdy może być rozumiane jako opis możliwego stanu rzeczy (lub możliwego świata ), w którym pewne stwierdzenia są prawdziwe, a inne nie. Semantykę formuł można następnie sformalizować poprzez zdefiniowanie, dla którego „stanu rzeczy” są one uważane za prawdziwe, co czyni poniższa definicja.

Definiujemy, kiedy takie przypisanie prawdy A spełnia pewną dobrze sformułowaną formułę z następującymi regułami:

  • A spełnia zmienną zdaniową P wtedy i tylko wtedy, gdy A ( P ) = prawda
  • A spełnia ¬ φ wtedy i tylko wtedy, gdy A nie spełnia φ
  • A spełnia ( φψ ) wtedy i tylko wtedy, gdy A spełnia zarówno φ jak i ψ
  • A spełnia ( φψ ) wtedy i tylko wtedy, gdy A spełnia co najmniej jeden z φ lub ψ
  • A spełnia ( φψ ) wtedy i tylko wtedy, gdy nie jest tak, że A spełnia φ ale nie ψ
  • A spełnia ( φψ ) wtedy i tylko wtedy, gdy A spełnia oba φ i ψ lub nie spełnia żadnego z nich

Dzięki tej definicji możemy teraz sformalizować, co to znaczy, że formuła φ jest implikowana przez pewien zbiór S formuł. Nieformalnie jest to prawdą, jeśli we wszystkich światach, które są możliwe przy zbiorze formuł S, zachodzi również formuła φ . Prowadzi to do następującej definicji formalnej: Mówimy, że zbiór S dobrze sformułowanych formuł semantycznie pociąga za sobą (lub implikuje ) pewną dobrze sformułowaną formułę φ, jeśli wszystkie przypisania prawdziwości, które spełniają wszystkie formuły w S, również spełniają φ .

Na koniec definiujemy wnioskowanie syntaktyczne w taki sposób, że φ jest syntaktycznie pociągane przez S wtedy i tylko wtedy, gdy możemy je wyprowadzić za pomocą reguł wnioskowania, które zostały przedstawione powyżej w skończonej liczbie kroków. To pozwala nam dokładnie sformułować, co to znaczy, że zbiór reguł wnioskowania musi być poprawny i kompletny:

Solidność: Jeśli zbiór dobrze sformułowanych formuł S pociąga za sobą składnię dobrze sformułowaną formułę φ, to S pociąga za sobą semantycznie φ .

Kompletność: Jeśli zbiór dobrze sformułowanych formuł S semantycznie pociąga za sobą dobrze sformułowaną formułę φ, to S pociąga za sobą składnię φ .

Tak jest w przypadku powyższego zestawu reguł.

Szkic dowodu solidności

(Dla większości systemów logicznych jest to stosunkowo "prosty" kierunek dowodu)

Konwencje zapisu: Niech G będzie zmienną obejmującą zbiory zdań. Niech A, B i C obejmują zdania. Ponieważ „ G syntaktycznie pociąga za sobą A ” piszemy „ G dowodzi A ”. Ponieważ „ G semantycznie pociąga za sobą A ” piszemy „ G pociąga za sobą A ”.

Chcemy pokazać: ( A )( G ) (jeśli G dowodzi A , to G implikuje A ).

Zauważmy, że „ G dowodzi A ” ma definicję indukcyjną, co daje nam bezpośrednie zasoby do wykazania twierdzeń postaci „Jeżeli G dowodzi A , to ...”. Tak więc nasz dowód przebiega przez indukcję.

  1. Podstawa. Pokaż: Jeśli A jest członkiem G , to G implikuje A .
  2. Podstawa. Pokaż: Jeśli A jest aksjomatem, to G implikuje A .
  3. Krok indukcyjny (indukcja na n , długości dowodu):
    1. Załóżmy dla dowolnych G i A, że jeśli G dowodzi A w n lub mniej krokach, to G implikuje A .
    2. Dla każdego możliwego zastosowania reguły wnioskowania w kroku n + 1 , prowadzącej do nowego twierdzenia B , wykaż , że G implikuje B .

Zauważ, że krok bazowy II można pominąć w przypadku systemów dedukcji naturalnej , ponieważ nie mają one aksjomatów. W przypadku użycia, Krok II polega na wykazaniu, że każdy z aksjomatów jest (semantyczną) logiczną prawdą .

Kroki Basis pokazują, że najprostsze dające się udowodnić zdania z G są również implikowane przez G , dla dowolnego G . (Dowód jest prosty, ponieważ fakt semantyczny, że zbiór implikuje którykolwiek z jego członków, jest również trywialny). za pomocą reguły wnioskowania — i pokazuje, że jeśli nowe zdanie można udowodnić, jest to również implikowane logicznie. (Na przykład, możemy mieć regułę mówiącą nam, że z „ A ” możemy wyprowadzić „ A lub B ”. W III.a Zakładamy, że jeśli A jest dowodliwe, jest to implikowane. Wiemy również, że jeśli A jest dowodliwe, to „ A lub B ” jest dowodliwe. Musimy pokazać, że wtedy implikuje się również „ A lub B ”. Robimy to poprzez odwołanie się do definicji semantycznej i założenia, które właśnie poczyniliśmy. Zakładamy, że A jest dowodliwe z G . również implikowane przez G. Tak więc każde wartościowanie semantyczne czyniące z G prawdziwe czyni A. Ale każde wartościowanie czyniące A prawdziwymi czyni „ A lub B ” prawdziwymi, przez zdefiniowaną semantykę dla „lub”. Zatem każde wartościowanie, które sprawia, że ​​całe G jest prawdziwe sprawia, że ​​„ A lub B ” są prawdziwe. Zatem „ A lub B ” jest implikowane.) Ogólnie rzecz biorąc, krok indukcyjny będzie składał się z długiej, ale prostej analizy poszczególnych przypadków wszystkich reguł wnioskowania, pokazując, że każda „zachowuje” semantykę implikacja.

Zgodnie z definicją dowodliwości nie ma zdań dowodliwych inaczej niż przez przynależność do G , aksjomat lub zastosowanie reguły; więc jeśli wszystkie z nich są implikowane semantycznie, rachunek dedukcji jest prawidłowy.

Szkic dowodu kompletności

(Jest to zwykle znacznie trudniejszy kierunek dowodu.)

Przyjmujemy te same konwencje notacji, co powyżej.

Chcemy pokazać: jeśli G implikuje A , to G dowodzi A . Wychodzimy przez kontrapozycji : Pokażemy natomiast, że jeśli G jest nie udowodnić A potem G ma nie implikuje A . Jeśli pokażemy, że istnieje model, w którym A nie zachodzi, mimo że G jest prawdziwe, to oczywiście G nie implikuje A . Chodzi o to, aby zbudować taki model z naszego samego założenia, że G nie dowodzi A .

  1. G nie dowodzi A . (Założenie)
  2. Jeśli G nie dowodzi A , to możemy skonstruować (nieskończony) Zbiór Maksymalny , G , który jest nadzbiorem G i który również nie dowodzi A .
    1. Uporządkuj (z typem porządku ω) wszystkie zdania w języku (np. najpierw najkrótsze i równie długie w rozszerzonym porządku alfabetycznym) i ponumeruj je ( E 1 , E 2 , ...)
    2. Zdefiniuj szereg G n zbiorów ( G 0 , G 1 , ...) indukcyjnie:
      1. Jeśli okaże się A , to
      2. Jeśli nie nie udowodnić A , a następnie
    3. Zdefiniuj G jako sumę wszystkich G n . (Oznacza to, że G jest zbiorem wszystkich zdań znajdujących się w dowolnym G n .)
    4. Łatwo to wykazać
      1. G zawiera (jest nadzbiorem) G (przez (bi));
      2. G nie dowodzi A (ponieważ dowód zawierałby tylko skończenie wiele zdań i gdy w jakimś G n zostanie wprowadzone ostatnie z nich, to G n dowodziłoby A wbrew definicji G n ); oraz
      3. G jest zbiorem maksymalnym w odniesieniu do A : Jeśli do G dodano jeszcze jakieś zdania, udowodniłoby to A . (Ponieważ gdyby można było dodać więcej zdań, należałoby je dodać, gdy napotkano je podczas konstrukcji G n , znowu z definicji)
  3. Jeśli G jest zbiorem maksymalnym względem A , to jest prawdziwościowe . Oznacza to, że zawiera C wtedy i tylko wtedy, gdy nie zawiera ¬C ; Jeśli zawiera C i zawiera „Jeżeli C, to B ”, to zawiera również B ; i tak dalej. Aby to pokazać, trzeba wykazać, że system aksjomatyczny jest wystarczająco silny dla:
    • Dla dowolnych formuł C i D , jeśli dowodzi zarówno C , jak i ¬C , to dowodzi D . Z tego wynika, że ​​Zbiór Maksymalny względem A nie może udowodnić zarówno C jak i ¬C , ponieważ w przeciwnym razie udowodniłby A .
    • Dla dowolnych formuł C i D , jeśli dowodzi zarówno CD , jak i ¬CD , to dowodzi D . Jest to używane wraz z twierdzeniem o dedukcji , aby pokazać, że dla dowolnej formuły albo ona, albo jej negacja jest w G : Niech B będzie formułą nie należącą do G ; wtedy G z dodatkiem B dowodzi A . Zatem z twierdzenia o dedukcji wynika, że G dowodzi BA . Ale załóżmy, że ¬B również nie było w G , to według tej samej logiki G również dowodzi, że ¬BA ; ale wtedy G dowodzi A , które, jak już wykazaliśmy, jest fałszywe.
    • Dla dowolnych formuł C i D , jeśli dowodzi C i D , to dowodzi CD .
    • Dla dowolnych formuł C i D , jeśli dowodzi C i ¬D , to dowodzi ¬( CD ).
    • Dla dowolnych formuł C i D , jeśli dowodzi ¬C , to dowodzi CD .
    Jeśli dodatkowe operacje logiczne (takie jak koniunkcja i/lub alternatywa) są również częścią słownika, to system aksjomatyczny ma dodatkowe wymaganie (np. jeśli dowodzi C i D , to również dowodzi ich koniunkcji).
  4. Jeśli G jest zbliżone do prawdy, to istnieje G -kanoniczne wartościowanie języka: takie, które sprawia, że ​​każde zdanie w G ∗ jest prawdziwe, a wszystko poza G fałszywe, przy jednoczesnym przestrzeganiu praw składu semantycznego w języku. Zauważ, że wymaganie prawdziwości jest potrzebne, aby zagwarantować, że prawa składu semantycznego w języku zostaną spełnione przez to przypisanie prawdziwości.
  5. A G ∗ - wartościowanie kanoniczne sprawi, że nasz pierwotny zbiór G będzie całkowicie prawdziwy, a A fałszywy.
  6. Jeśli istnieje wartościowanie, w którym G jest prawdziwe, a A jest fałszywe, to G nie implikuje (semantycznie) A .

Zatem każdy system, który ma modus ponens jako regułę wnioskowania i dowodzi następujących twierdzeń (w tym ich podstawień) jest zupełny:

  • p → (¬p → q)
  • (p → q) → ((¬p → q) → q)
  • p → (q → (p → q))
  • p → (¬q → ¬(p → q))
  • ¬p → (p → q)
  • p → p
  • p → (q → p)
  • (p → (q → r)) → ((p → q) → (p → r))

Pierwsze pięć służy do spełnienia pięciu warunków z etapu III powyżej, a ostatnie trzy do udowodnienia twierdzenia o dedukcji.

Przykład

Jako przykład można wykazać, że jak każda inna tautologia, trzy aksjomaty opisanego wcześniej klasycznego systemu rachunku zdań mogą być udowodnione w dowolnym systemie, który spełnia powyższe, a mianowicie ma modus ponens jako regułę wnioskowania i dowodzi powyższego. osiem twierdzeń (w tym ich podstawienia). Z ośmiu twierdzeń ostatnie dwa to dwa z trzech aksjomatów; trzeci aksjomat, , również można udowodnić, jak teraz pokazujemy.

Jako dowód możemy użyć hipotetycznego twierdzenia o sylogizmie (w postaci właściwej dla tego systemu aksjomatycznego), ponieważ opiera się ono tylko na dwóch aksjomatach, które są już w powyższym zbiorze ośmiu twierdzeń. Dowód jest więc następujący:

  1.       (przykład 7. twierdzenia)
  2.       (przykład 7. twierdzenia)
  3.       (od (1) i (2) przez modus ponens)
  4.       (przykład hipotetycznego twierdzenia o sylogizmie)
  5.       (przykład 5. twierdzenia)
  6.       (od (5) i (4) przez modus ponens)
  7.       (przykład drugiego twierdzenia)
  8.       (przykład 7. twierdzenia)
  9.       (od (7) i (8) według modus ponens)
  10.       (przykład 8. twierdzenia)
  11.       (od (9) i (10) według modus ponens)
  12.       (od (3) i (11) według modus ponens)
  13.       (przykład 8. twierdzenia)
  14.       (od (12) i (13) według modus ponens)
  15.       (od (6) i (14) według modus ponens)

Weryfikacja kompletności dla klasycznego systemu rachunku zdań

Sprawdzamy teraz, czy opisany wcześniej klasyczny system rachunku zdań może rzeczywiście dowieść wymaganych ośmiu twierdzeń wspomnianych powyżej. Używamy tutaj kilku sprawdzonych lematów :

(DN1) - Podwójna negacja (jeden kierunek)
(DN2) - Podwójna negacja (inny kierunek)
(HS1) - jedna forma sylogizmu hipotetycznego
(HS2) - inna forma sylogizmu hipotetycznego
(TR1) - Transpozycja
(TR2) - kolejna forma transpozycji.
(L1)
(L3)

Używamy również metody hipotetycznego metateorematu sylogizmu jako skrótu dla kilku kroków dowodowych.

  • p → (¬p → q) - dowód:
    1.       (przykład (A1))
    2.       (przykład (TR1))
    3.       (z (1) i (2) przy użyciu hipotetycznego metateorematu sylogizmu)
    4.       (przykład (DN1))
    5.       (przykład (HS1))
    6.       (od (4) i (5) za pomocą modus ponens)
    7.       (z (3) i (6) przy użyciu hipotetycznego metateorematu sylogizmu)
  • (p → q) → ((¬p → q) → q) - dowód:
    1.       (przykład (HS1))
    2.       (przykład (L3))
    3.       (przykład (HS1))
    4.       (od (2) i (3) przez modus ponens)
    5.       (z (1) i (4) przy użyciu hipotetycznego metateorematu sylogizmu)
    6.       (przykład (TR2))
    7.       (przykład (HS2))
    8.       (od (6) i (7) za pomocą modus ponens)
    9.       (z (5) i (8) za pomocą hipotetycznego metateorematu sylogizmu)
  • p → (q → (p → q)) - dowód:
    1.       (przykład (A1))
    2.       (przykład (A1))
    3.       (z (1) i (2) za pomocą modus ponens)
  • p → (¬q → ¬(p → q)) - dowód:
    1.       (przykład (L1))
    2.       (przykład (TR1))
    3.       (z (1) i (2) przy użyciu hipotetycznego metateorematu sylogizmu)
  • ¬p → (p → q) - dowód:
    1.       (przykład (A1))
    2.       (przykład (A3))
    3.       (z (1) i (2) przy użyciu hipotetycznego metateorematu sylogizmu)
  • p → p - dowód podany w powyższym przykładzie dowodu
  • p → (q → p) - aksjomat (A1)
  • (p → (q → r)) → ((p → q) → (p → r)) - aksjomat (A2)

Kolejny zarys dowodu kompletności

Jeżeli formuła jest tautologią , to istnieje dla niej tabela prawdy , która pokazuje, że każda wycena daje wartość true dla formuły. Rozważ taką wycenę. Poprzez indukcję matematyczną dotyczącą długości podwzorów wykaż, że prawdziwość lub fałszywość podwzorów wynika z prawdziwości lub fałszu (odpowiednio do wartościowania) każdej zmiennej zdaniowej w podformule. Następnie połącz wiersze tabeli prawdy razem po dwa na raz, używając „( P to prawda implikuje S ) implikuje (( P to fałsz implikuje S ) implikuje S )”. Powtarzaj to, aż wszystkie zależności od zmiennych zdaniowych zostaną wyeliminowane. W rezultacie udowodniliśmy daną tautologię. Ponieważ każdą tautologię można udowodnić, logika jest kompletna.

Interpretacja rachunku zdań funkcjonalno-prawdowo

Interpretacja prawda funkcyjną zdań rachunku jest przyporządkowanie każdemu zdań symbolu z jednej lub z drugiej strony (ale nie obydwa) o wartości logicznych prawdą ( T ) i fałszem ( F ) i przypisanie do łącznej symboli o o ich zwykłe znaczenia funkcjonalno-prawdowe. Interpretacja rachunku prawdziwościowo-funkcjonalnego zdań może być również wyrażona w postaci tablic prawdziwościowych .

Dla różnych symboli zdaniowych istnieją różne możliwe interpretacje. Dla dowolnego konkretnego symbolu , na przykład, możliwe są interpretacje:

  1. jest przypisany T , lub
  2. jest przypisany F .

Dla pary , nie są możliwe interpretacje:

  1. oba mają przypisane T ,
  2. oba mają przypisane F ,
  3. jest przypisane T i jest przypisane F , lub
  4. jest przypisane F i jest przypisane T .

Ponieważ ma , to jest przeliczalnie wiele symboli zdaniowych, istnieje , a zatem niezliczona ilość różnych możliwych interpretacji .

Interpretacja zdania prawdziwościowo-funkcjonalnej logiki zdań

Jeśli φ i ψwzory z i jest interpretacją wówczas stosuje się następujące definicje:

  • Zdanie logiki zdań jest prawdziwe w interpretacji, jeśli przypisuje temu zdaniu wartość prawdziwości T. Jeśli zdanie jest prawdziwe w ramach interpretacji, to interpretacja ta nazywana jest modelem tego zdania.
  • φ jest fałszywe w interpretacji, jeśli φ nie jest prawdziwe w .
  • Zdanie logiki zdań jest logicznie słuszne, jeśli jest prawdziwe pod każdą interpretacją.
    φ oznacza, że φ jest logicznie poprawne.
  • Zdanie ψ logiki zdaniowej jest semantyczną konsekwencją zdania φ, jeśli nie ma interpretacji, w której φ jest prawdziwe, a ψ fałszywe.
  • Zdanie logiki zdań jest zgodne, jeśli jest prawdziwe pod przynajmniej jedną interpretacją. Jest niespójny, jeśli nie jest spójny.

Niektóre konsekwencje tych definicji:

  • Dla dowolnej interpretacji dana formuła jest albo prawdziwa, albo fałszywa.
  • Żadna formuła nie jest jednocześnie prawdziwa i fałszywa przy tej samej interpretacji.
  • φ jest fałszywe dla danej interpretacji, jeśli jest prawdziwe dla tej interpretacji; a φ jest prawdziwe w ramach interpretacji iff jest fałszywe w ramach tej interpretacji.
  • Jeśli φ i oba są prawdziwe przy danej interpretacji, to ψ jest prawdziwe przy tej interpretacji.
  • Jeśli i , to .
  • jest prawdziwe pod iff φ nie jest prawdziwe pod .
  • jest prawdziwe pod iff albo φ nie jest prawdziwe pod albo ψ jest prawdziwe pod .
  • Zdanie ψ logiki zdaniowej jest semantyczną konsekwencją zdania φ iff jest logicznie ważne , czyli iff .

Rachunek alternatywny

Możliwe jest zdefiniowanie innej wersji rachunku zdań, w którym większość składni operatorów logicznych definiuje się za pomocą aksjomatów i która wykorzystuje tylko jedną regułę wnioskowania.

Aksjomaty

Niech φ , χ , i ψ oznaczają dobrze uformowane formuły. (Sama dobrze sformułowana formuła nie zawierałaby żadnych liter greckich, a jedynie duże litery rzymskie, operatory spójników i nawiasy). Następnie aksjomaty są następujące:

Aksjomaty
Nazwa Schemat aksjomatu Opis
WTEDY-1 Dodaj hipotezę χ , wprowadzenie do implikacji
WTEDY-2 Rozłóż hipotezę na implikację
I 1 Wyeliminuj spójnik
I-2  
I-3 Wprowadź spójnik
OR-1 Wprowadź alternatywę
OR-2  
OR-3 Wyeliminuj alternatywę
NIE-1 Wprowadź negację
NIE-2 Wyeliminuj negację
NIE-3 Wykluczona środkowa, klasyczna logika
IFF-1 Wyeliminuj równoważność
IFF-2  
IFF-3 Wprowadź równoważność
  • Aksjomat THEN-2 może być uważany za „dystrybucyjną właściwość implikacji w odniesieniu do implikacji”.
  • Aksjomaty AND-1 i AND-2 odpowiadają "eliminacji koniunkcji". Relacja między AND-1 i AND-2 odzwierciedla przemienność operatora koniunkcji.
  • Aksjomat AND-3 odpowiada „wprowadzeniu koniunkcji”.
  • Aksjomaty OR-1 i OR-2 odpowiadają „wprowadzeniu alternatywy”. Relacja między OR-1 i OR-2 odzwierciedla przemienność operatora alternatywy.
  • Aksjomat NOT-1 odpowiada „reductio ad absurdum”.
  • Aksjomat NOT-2 mówi, że „z sprzeczności można wydedukować wszystko”.
  • Aksjomat NOT-3 nazywany jest „ tertium non-datur ” ( łac . „trzecia nie jest dana”) i odzwierciedla semantyczną wartość formuł zdaniowych: formuła może mieć prawdziwość lub fałsz. Nie ma trzeciej wartości prawdziwościowej, przynajmniej nie w logice klasycznej. Logicy intuicjonistyczni nie akceptują aksjomatu NOT-3 .

Reguła wnioskowania

Regułą wnioskowania jest modus ponens :

.

Reguła metainferencji

Niech demonstracja będzie reprezentowana przez sekwencję, z hipotezami po lewej stronie kołowrotu i zakończeniem po prawej stronie kołowrotu. Wtedy twierdzenie o dedukcji może być sformułowane w następujący sposób:

Jeśli sekwencja
został zademonstrowany, wówczas możliwe jest również zademonstrowanie sekwencji
.

To twierdzenie dedukcyjne (DT) samo w sobie nie jest sformułowane za pomocą rachunku zdań: nie jest to twierdzenie rachunku zdań, ale twierdzenie o rachunku zdań. W tym sensie jest to meta-twierdzenie , porównywalne z twierdzeniami o słuszności lub zupełności rachunku zdań.

Z drugiej strony, DT jest tak przydatne do uproszczenia procesu dowodu syntaktycznego, że może być rozważane i wykorzystywane jako kolejna reguła wnioskowania towarzysząca modus ponens. W tym sensie DT odpowiada naturalnej warunkowej regule wnioskowania o dowodzie, która jest częścią pierwszej wersji rachunku zdań wprowadzonej w tym artykule.

Obowiązuje również odwrotność DT:

Jeśli sekwencja
został zademonstrowany, wówczas możliwe jest również zademonstrowanie sekwencji

w rzeczywistości ważność odwrotności DT jest niemal trywialna w porównaniu z DT:

Gdyby
następnie
1:
2:
a z (1) i (2) można wywnioskować
3:
za pomocą modus ponens, QED

Odwrotność DT ma potężne implikacje: może być wykorzystana do przekształcenia aksjomatu w regułę wnioskowania. Na przykład aksjomat AND-1,

można przekształcić za pomocą odwrotności twierdzenia o dedukcji w regułę wnioskowania

czyli eliminacja koniunkcyjna , jedna z dziesięciu reguł wnioskowania stosowanych w pierwszej wersji (w tym artykule) rachunku zdań.

Przykład dowodu

Poniżej znajduje się przykład (syntaktycznej) demonstracji, obejmującej tylko aksjomaty THEN-1 i THEN-2 :

Udowodnij: (Zwrotność implikacji).

Dowód:

  1. Aksjomat THEN-2 z
  2. Aksjomat THEN-1 z
  3. Od (1) i (2) przez modus ponens.
  4. Aksjomat THEN-1 z
  5. Od (3) i (4) według modus ponens.

Równoważność logiki równań

Poprzedni rachunek alternatywny jest przykładem systemu dedukcji w stylu Hilberta . W przypadku systemów zdań aksjomaty są terminami zbudowanymi z spójników logicznych, a jedyną regułą wnioskowania jest modus ponens. Logika równań, standardowo używana nieformalnie w algebrze licealnej, jest innym rodzajem rachunku różniczkowego niż systemy Hilberta. Jego twierdzenia są równaniami, a reguły wnioskowania wyrażają właściwości równości, a mianowicie, że jest ona zbieżnością warunków dopuszczających podstawienie.

Klasyczny rachunek zdań opisany powyżej jest równoważny algebrze Boole'a , podczas gdy intuicjonistyczny rachunek zdań jest równoważny algebrze Heytinga . Równoważność jest pokazana przez translację w każdym kierunku twierdzeń odpowiednich systemów. Twierdzenia klasycznego lub intuicjonistycznego rachunku zdań są tłumaczone odpowiednio jako równania algebry Boole'a lub Heytinga. Odwrotnie, twierdzenia algebry Boole'a lub Heytinga są tłumaczone jako twierdzenia odpowiednio klasycznego lub intuicjonistycznego rachunku różniczkowego, dla których jest standardowym skrótem. W przypadku algebry Boole'a można ją również przetłumaczyć jako , ale to tłumaczenie jest niepoprawne intuicjonistycznie.

Zarówno w algebrze Boole'a, jak i Heytinga, nierówność może być użyta zamiast równości. Równość można wyrazić jako parę nierówności i . Odwrotnie, nierówność można wyrazić jako równość lub jako . Znaczenie nierówności dla systemów w stylu Hilberta polega na tym, że odpowiada ona dedukcji lub symbolowi implikacji tego ostatniego . Powodowanie

jest tłumaczone w nierównościowej wersji szkieletu algebraicznego jako

Odwrotnie, nierówność algebraiczna jest tłumaczona jako wynikanie

.

Różnica pomiędzy pośrednio i nierówności lub wynikania lub jest to, że były to wewnętrzny z logiką, a drugi znajduje się na zewnątrz. Implikacja wewnętrzna między dwoma terminami to inny termin tego samego rodzaju. Entailment jako zewnętrzna implikacja między dwoma terminami wyraża metaprawdę poza językiem logiki i jest uważany za część metajęzyka . Nawet jeśli badana logika jest intuicjonistyczna, wynikanie jest zwykle rozumiane klasycznie jako dwuwartościowe: albo lewa strona pociąga za sobą, albo jest mniejsza lub równa prawej stronie, albo nie jest.

Podobne, ale bardziej złożone translacje do iz logiki algebraicznej są możliwe dla naturalnych systemów dedukcji opisanych powyżej oraz dla rachunku sekwencyjnego . Implikacje tego ostatniego można interpretować jako dwuwartościowe, ale bardziej wnikliwą interpretacją jest zbiór, którego elementy można rozumieć jako abstrakcyjne dowody zorganizowane jako morfizmy kategorii . W tej interpretacji wykrojona reguła rachunku sekwencyjnego odpowiada kompozycji w kategorii. Algebry Booleana i Heytinga wchodzą w ten obraz jako specjalne kategorie mające co najwyżej jeden morfizm na homset, tj. jeden dowód na wyciągnięcie, co odpowiada idei, że liczy się tylko istnienie dowodów: każdy dowód zadziała i nie ma sensu ich rozróżniać .

Rachunki graficzne

Możliwe jest uogólnienie definicji języka formalnego ze zbioru skończonych ciągów na skończonej podstawie, aby objąć wiele innych zbiorów struktur matematycznych, o ile są one zbudowane skończonymi środkami ze skończonych materiałów. Co więcej, wiele z tych rodzin struktur formalnych szczególnie dobrze nadaje się do wykorzystania w logice.

Na przykład istnieje wiele rodzin grafów, które są na tyle bliskimi odpowiednikami języków formalnych, że pojęcie rachunku różniczkowego można do nich dość łatwo i naturalnie rozszerzyć. Wiele gatunków grafów powstaje jako grafy parsowania w analizie składniowej odpowiednich rodzin struktur tekstowych. Wymogi praktycznych obliczeń w językach formalnych często wymagają konwersji ciągów tekstowych na odwzorowania struktury wskaźnikowej grafów parsowania, po prostu w celu sprawdzenia, czy ciągi są poprawnie sformułowanymi formułami, czy nie. Gdy już to zrobimy, można uzyskać wiele korzyści z opracowania graficznego odpowiednika rachunku różniczkowego na strunach. Mapowanie z ciągów do analizowania grafów nazywa się analizowaniem, a odwrotne mapowanie z analizowania grafów na ciągi jest uzyskiwane za pomocą operacji nazywanej przechodzeniem przez graf.

Inne rachunki logiczne

Rachunek zdań to najprostszy obecnie używany rodzaj rachunku logicznego. Można go rozbudować na kilka sposobów. ( Arystotelesowski rachunek „sylogistyczny” , który jest w dużej mierze wyparty we współczesnej logice, jest pod pewnymi względami prostszy – ale pod innymi względami bardziej złożony – niż rachunek zdań.) Najbardziej bezpośrednim sposobem opracowania bardziej złożonego rachunku logicznego jest wprowadzenie reguł, które są wrażliwe na bardziej szczegółowe szczegóły użytych zdań.

Logika pierwszego rzędu (inaczej logika predykatów pierwszego rzędu) powstaje, gdy „zdania atomowe” logiki zdań są dzielone na terminy , zmienne , predykaty i kwantyfikatory , wszystkie zachowując zasady logiki zdań z wprowadzonymi nowymi. (Na przykład z „Wszystkie psy są ssakami” możemy wywnioskować „Jeśli Łazik jest psem, to Łazik jest ssakiem”.) Dzięki narzędziom logiki pierwszego rzędu możliwe jest sformułowanie wielu teorii, zarówno z wyraźnymi aksjomatami lub przez reguły wnioskowania, które same w sobie mogą być traktowane jako rachunki logiczne. Najbardziej znana jest arytmetyka ; inne obejmują teorię mnogości i mereologię . Logika drugiego rzędu i inne logiki wyższego rzędu są formalnymi rozszerzeniami logiki pierwszego rzędu. W związku z tym sensowne jest odwoływanie się do logiki zdań jako logiki zerowego rzędu” , porównując ją z tymi logikami.

Logika modalna oferuje również różnorodne wnioskowania, których nie można uchwycić w rachunku zdań. Na przykład z „Koniecznie p ” możemy wywnioskować, że p . Z p możemy wywnioskować "Możliwe, że p ". Tłumaczenie między logiką modalną a logiką algebraiczną dotyczy logiki klasycznej i intuicjonistycznej, ale z wprowadzeniem jednoargumentowego operatora na algebrach Boole'a lub Heytinga, innego niż operacje Boole'a, interpretującego modalność możliwości, a w przypadku algebry Heytinga drugiego operatora interpretującego konieczność (dla algebry Boole'a jest to zbędne, ponieważ konieczność jest podwójną możliwością De Morgana). Pierwszy operator zachowuje 0 i alternatywę, podczas gdy drugi zachowuje 1 i połączenie.

Logiki wielowartościowe to te, które pozwalają zdaniom mieć wartości inne niż prawda i fałsz . (Na przykład żadne i oba są standardowymi „wartościami dodatkowymi”; „logika kontinuum” pozwala każdemu zdaniu mieć dowolną z nieskończonej liczby „stopni prawdy” między prawdą a fałszem ). rachunek różniczkowy. Kiedy wartości tworzą algebrę Boole'a (która może mieć więcej niż dwie lub nawet nieskończenie wiele wartości), logika wielowartościowa redukuje się do logiki klasycznej; Logiki wielowartościowe są zatem przedmiotem niezależnego zainteresowania tylko wtedy, gdy wartości tworzą algebrę, która nie jest boolowska.

Rozwiązujący

Znajdowanie rozwiązań formuł logiki zdań jest problemem NP-zupełnym . Istnieją jednak metody praktyczne (np. algorytm DPLL , 1962; algorytm Chaffa , 2001), które są bardzo szybkie w wielu użytecznych przypadkach. Ostatnie prace rozszerzyły algorytmy solwera SAT do pracy ze zdaniami zawierającymi wyrażenia arytmetyczne ; to są solvery SMT .

Zobacz też

Wyższe poziomy logiczne

powiązane tematy

Bibliografia

Dalsza lektura

  • Brown, Frank Markham (2003), Boolean Reasoning: The Logic of Boolean Equations , wydanie 1, Kluwer Academic Publishers, Norwell, MA. Wydanie drugie, Dover Publications, Mineola, NY.
  • Chang, CC i Keisler, HJ (1973), Teoria modeli , Holandia Północna, Amsterdam, Holandia.
  • Kohavi, Zvi (1978), Teoria przełączania i automatów skończonych , wydanie 1, McGraw-Hill, 1970. Wydanie drugie, McGraw-Hill, 1978.
  • Korfhage, Robert R. (1974), Discrete Computational Structures , Academic Press, New York, NY.
  • Lambek, J. i Scott, PJ (1986), Wprowadzenie do logiki kategorycznej wyższego rzędu , Cambridge University Press, Cambridge, Wielka Brytania.
  • Mendelson, Elliot (1964), Wprowadzenie do logiki matematycznej , D. Van Nostrand Company.

Powiązane prace

Zewnętrzne linki