Minimalna logika

Minimalna logika lub minimalny rachunek różniczkowy to system logiki symbolicznej , pierwotnie opracowany przez Ingebrigta Johanssona . Jest to intuicjonistyczna i parakonsystentna , która odrzuca zarówno prawo wyłączonego środka , jak i zasadę eksplozji ( ex falso quodlibet ), a zatem nie uznaje żadnego z następujących dwóch wyprowadzeń za ważne:

${\ Displaystyle \ vdash (B \ lor \ neg B)}$

${\ Displaystyle (A \ ziemia \ neg A) \ vdash}$

gdzie i $są$$dowolnymi$ . Większość konstruktywnych logik odrzuca tylko tę pierwszą, czyli prawo wyłączonego środka. W logice klasycznej prawa ex falso

${\ Displaystyle (A \ ziemia \ neg A) \ do b,}$

${\ Displaystyle \ negowanie (A \ lor \ neg A) \ do b,}$

${\ Displaystyle \ neg A \ do (A \ do B)}$

a także ich warianty z $są$$i$ równoważne sobie nawzajem i Minimalna logika również odrzuca te zasady.

Aksjomatyzacja

Logika minimalna jest aksjomatyzowana nad pozytywnym fragmentem logiki intuicjonistycznej. Obie te logiki można sformułować $w$ języku przy użyciu tych samych aksjomatów i $koniunkcji$$,$ i alternatywy jako podstawowych spójników , Minimal dodaje falsum lub absurd ${\ Displaystyle \ bot}$ jako część języka. Alternatywnie, poniżej omówiono bezpośrednie aksjomaty negacji.

Twierdzenia

Tutaj omówione są tylko twierdzenia, których nie da się jeszcze udowodnić w rachunku dodatnim.

Wprowadzenie negacji

Szybka analiza praw implikacji i negacji daje dobrą wskazówkę, co ta logika, pozbawiona pełnej eksplozji, może, a czego nie może udowodnić.

Naturalnym stwierdzeniem w języku z negacją , takim jak logika minimalna, jest na przykład zasada wprowadzenia negacji , zgodnie z którą zaprzeczenie zdania jest udowodnione przez założenie go i wyprowadzenie sprzeczności. Formalnie można to wyrazić jako, dla dowolnych dwóch twierdzeń,

${\ Displaystyle (B \ do (A \ ziemia \ neg A)} \ do \ neg B}$ .

Dla $braku$$sprzeczności$ ustanawia . _

${\ Displaystyle \ neg (A \ ziemia \ neg A)}$ .

Zakładając dowolny $i$ reguła wprowadzenia warunku materialnego daje $C}$$do {\ displaystyle$$B \$ do , także wtedy, gdy są odpowiednio Z tym i eliminacją implikacji wynika powyższa zasada wprowadzenia

${\ Displaystyle (A \ ziemia \ neg A) \ do \ neg B}$ ,

tj. zakładając jakąkolwiek sprzeczność, każde zdanie można zaprzeczyć. Wprowadzenie negacji $możliwe$ w minimalnej logice, więc tutaj zresztą sprzeczność dowodzi każdej . Eksplozja pozwoliłaby usunąć tę ostatnią podwójną negację, ale zasada ta nie jest przyjęta.

Ponadto korzystając z ww

${\ Displaystyle {\ duży (} (A \ lor B) \ ziemia \ neg A {\ duży)} \ do {\big (}(B\lor \neg B)\land \neg \neg B){\big )}}$ .

Należy to porównać z pełnym sylogizmem rozłącznym .

Aksjomatyzacja przez absurd

$możliwych$ schematów rozszerzenia rachunku dodatniego na logikę minimalną jest traktowanie jako implikacji, w którym to przypadku twierdzenia z rachunku implikacji logiki przenoszą się na stwierdzenia W tym celu wprowadza się jako twierdzenie, którego nie da się udowodnić, chyba że system jest niespójny, a negacja $jest$$wtedy$${\ displaystyle B \do \bota}$ od . Konstruktywnie, ${\ displaystyle \ bot}$ reprezentuje propozycję, dla której nie ma powodu, by w nią wierzyć.

Omówione już zasady mogą więc pochodzić z twierdzeń o pozytywnym fragmencie. Wprowadzenie negacji , opisane w poprzedniej sekcji, jest rozumiane jako zwykły szczególny przypadek

${\ Displaystyle (B \ do (A \ ziemia (A \ do C)}} \ do (B \ do C)}$

kiedy do $Displaystyle C = \ bot}$ . W ten sposób minimalną logikę można scharakteryzować jako logikę konstruktywną tylko bez eliminacji negacji (inaczej eksplozji). Powyższego można dowieść poprzez modus ponens , który jako zdanie brzmi

${\ Displaystyle (A \ ziemia (A \ do C)} \ do C}$

$prawdą$ jest rzeczywiście szczególnym przypadkiem powyższego, gdy jest . Z definicją negacji przez $stwierdzenie$ modus ponens może być ponownie wyspecjalizowane w ten sam sposób, a następnie ustanawia zasadę niesprzeczności, również już opisaną powyżej. Rzeczywiście, można uzyskać wszystkie powszechne implikacje intuicjonistyczne obejmujące koniunkcje dwóch zdań , w tym równoważność curry. Dla przykładu warto podkreślić ważną ekwiwalencję

${\ Displaystyle ((A \ lor B) \ do C) \ strzałka w lewo w prawo ((A \ do C) \ ziemia (B \do C))}$ ,

$. Po pierwsze,$$, że są$$i$ sposoby powiedzenia, że ​​​​oba implikują uzyskuje się z niego znane prawa De Morgana ,

${\ Displaystyle \ neg (A \ lor B) \ strzałka w prawo w lewo (\ neg A \ ziemia \ neg B)}$ .

Po drugie, używając go do rozpuszczenia jednej implikacji z dysjunkcji jako poprzednika na dwie implikacje, wynika z tego, że

${\ Displaystyle ((B \ lor (B \ do C)} \ do C) \ do C}$

a to sprowadza się do podwójnej negacji wyłączonego środka

${\ Displaystyle \ neg \ neg (B \ lor \ neg B)}$

Przez wprowadzenie implikacji,

${\ Displaystyle C \ do (B \ do C)}$

To już implikuje również $sposób$$pokazanie$ , w jaki logice Zostało to również wyjaśnione powyżej, ale tutaj można je skrócić

${\ Displaystyle \ bot \ do \ neg B.}$

Jeśli absurdalność jest prymitywna, pełną eksplozję można również określić jako ${\ displaystyle \ bot \ do B}$ .

Aksjomatyzacja poprzez więcej zasad

b ${\ Displaystyle B \ do ((B \ do C) \ do C$ }

${\ Displaystyle B \ do \ neg \ neg B}$

Związane z zasadą wprowadzenia negacji, od

${\ Displaystyle (A \ do B) \ do ((B \ do C) \ do (A \ do C))}$ .

minimalna logika dowodzi przeciwstawności

${\ Displaystyle (A \ do B) \ do (\ neg B \ do \ neg A).}$

Powyższe zasady zostały również uzyskane przy użyciu twierdzeń z rachunku dodatniego w połączeniu z ${\ displaystyle \ bot}$ .

Przyjęcie powyższej zasady podwójnej negacji wraz z zasadą kontrapozycji daje alternatywną aksjomatyzację logiki minimalnej nad pozytywnym fragmentem logiki intuicjonistycznej.

Zdania nie do udowodnienia

Taktyka uogólniania ${ \ displaystyle A \ na$ → do $}$ nie sprawdza się w udowodnieniu wszystkich klasycznie ważnych stwierdzeń obejmujących podwójne Zauważ, że każdy schemat kształtu składniowego jest zbyt silny $, aby można$ było udowodnić: gdyby można było to udowodnić, to każda $}$ udowodniłby każdą inną propozycję ${\ displaystyle B}$ . Teraz interesującym wariantem jest zastąpienie przez ${\ displaystyle (B \ do C$$do$ ) Pokazuje, co prawdopodobnie nie jest zaskakujące, że naiwne uogólnienie eliminacji $nie$ być ten sposób.

Twierdzenie $($ twierdzeniem o minimalnej $→$ . Dlatego przyjęcie zasady pełnej podwójnej negacji $minimalnej$ logice przywraca rachunek klasycznej , również pomijając wszystkie pośrednie logiki .

Istnieją również twierdzenia logiki zdaniowej, których nie da się udowodnić w logice minimalnej, ale są one uzasadnione intuicjonistycznie. W przypadku eksplozji zanegowanych stwierdzeń pełna eksplozja jest równoważna jej szczególnemu przypadkowi ${\ Displaystyle ((\ neg B) \ land \ neg (\ neg B)) \ do B }$ . To ostatnie można sformułować jako eliminację podwójnej negacji dla odrzuconych zdań, ${\ Displaystyle \ neg B \ do (\ neg \ neg B \ do B)}$ . Ta zasada również od razu dowodzi pełnego sylogizmu dysjunkcyjnego. Jest to więc stosunkowo słaby schemat prowadzący do silniejszej logiki intuicjonistycznej .

Jak widać powyżej, podwójnie zanegowany wykluczony środek dla dowolnego zdania jest już możliwy do udowodnienia w logice minimalnej. Warto jednak podkreślić, że w rachunku predykatów prawa logiki minimalnej nie pozwalają na dowód podwójnej negacji nieskończonej koniunkcji wykluczonych zdań środkowych. Rzeczywiście, schemat przesunięcia podwójnej negacji (DNS)

${\ Displaystyle \ forall (n \ in {\ mathbb {N}}). \ neg \ neg P (n) \ implikuje \ neg \ neg \ forall (n \ in {\ mathbb {N}}) .P(n)}$

nie jest nawet ważne intuicjonistycznie i nie jest też ${\ Displaystyle \ neg \ neg \ forall (n \ in {\ mathbb {N}}). Q (n) \ lor \ neg Q (n)}$ . Poza arytmetyką pozwala to na teorie nieklasyczne.

Związek z logiką intuicjonistyczną

Każda formuła wykorzystująca tylko ${\ displaystyle \ land, \ lor, \ to}$ jest możliwa do udowodnienia w logice minimalnej wtedy i tylko wtedy, gdy jest możliwa do udowodnienia w logice intuicjonistycznej.

Zasada eksplozji obowiązuje w logice intuicjonistycznej i wyraża, że ​​aby wyprowadzić dowolne twierdzenia, można to zrobić poprzez wyprowadzenie dowolnego absurdu. W logice minimalnej zasada ta nie obowiązuje aksjomatycznie dla dowolnych zdań. Ponieważ logika minimalna reprezentuje tylko pozytywny fragment logiki intuicjonistycznej, jest ona podsystemem logiki intuicjonistycznej i jest ściśle słabsza.

Sformułowana zwięźle, eksplozja logiki intuicjonistycznej dokładnie przyznaje określone przypadki zasady eliminacji podwójnej negacji, której nie ma logika minimalna.

Sylogizm rozłączny

Praktycznie, w kontekście intuicjonistycznym, zasada eksplozji umożliwia sylogizm rozłączny:

${\ Displaystyle ((A \ lor B) \ ziemia \ neg A) \ do B.}$

$pod$$: Biorąc$ uwagę dowód i odrzucenie , bezwarunkowo dopuszcza się pozytywny wybór $.$ W ten sposób sylogizm jest zasadą rozpakowywania alternatywy. Można to postrzegać jako formalną konsekwencję eksplozji i to też implikuje. Dzieje się tak, ponieważ jeśli zostało $A \ lor B }$ przez udowodnienie, to ${\ Displaystyle$${\ displaystyle B}$$jest$$już$$podczas$ gdy jeśli zostało udowodnione przez udowodnienie to , ponieważ pozwala na to system intuicjonistyczny eksplozja.

Na przykład, biorąc pod uwagę konstruktywny argument, że rzut monetą zakończył się orłem lub reszką ( $wraz$ , $z konstruktywnym argumentem$ że wynik w rzeczywistości nie był reszką, sylogizm wyraża że to już stanowi argument, że wystąpiły reszki.

Jeśli zakłada się metalologicznie, że system logiki intuicjonistycznej jest spójny, sylogizm można odczytać jako mówiący, że konstruktywna demonstracja ${\ Displaystyle A \ lor B}$$przy$ braku nie -logiczne aksjomaty wykazujące , w rzeczywistości zawiera demonstrację $displaystyle$$B}$ .

w ten sposób uzyskać dowodu na ${\ displaystyle B} .$ Jednak ta sama przesłanka implikuje podwójną negację , tj. ${\ displaystyle B}$${\ displaystyle \ neg \ neg B}$ . Jeśli zakłada się $, że$ system logiczny jest metalologicznie spójny, to ten wzór implikacji można wyrazić, mówiąc, że po prostu nie można go odrzucić.

$brzmi$${$ rozłącznego, aw przeciwnym kierunku przykład sylogizmu z i jest równoważne eliminacji podwójnej negacji dla zdań, dla których zachodzi wykluczenie środka

${\ Displaystyle (B \ lor \ neg B) \ do (\ neg \ neg B \ do B)}$ .

Ponieważ materialny warunek warunkowy zapewnia eliminację podwójnej negacji dla sprawdzonych zdań, jest to ponownie równoważne eliminacji podwójnej negacji dla zdań odrzuconych.

Intuicjonistyczny przykład użycia w teorii

Następujące twierdzenie arytmetyczne Heytinga pozwala na dowody istnienia twierdzeń, których nie można udowodnić za pomocą tego ogólnego wyniku bez zasady eksplozji. Rezultatem jest zasadniczo rodzina prostych twierdzeń o eliminacji podwójnej negacji, $wiążących$ obliczalny predykat.

Niech będzie dowolnym predykatem wolnym od kwantyfikatorów, a zatem rozstrzygalnym dla wszystkich liczb $displaystyle P}$ tak aby wykluczone chwyty środkowe, P. ${$

${\ Displaystyle P (n) \ lor \ neg P (n)}$ .

Następnie przez indukcję w ${\ displaystyle m$ }

${\ Displaystyle \ forall m. \ \ neg {\ duży (} \ forall (n <m). \ neg P (n) {\ duży)} \ do \ istnieje (b <m). P ( B)}$

Słownie: dla liczb $skończonym$ zakresie do , jeśli można wykluczyć, że żaden przypadek nie jest sprawdzany, tj. jeśli można wykluczyć, że dla każdej liczby powiedzmy m {\ displaystyle $}$$}$$\ displaystyle n =$ , odpowiednie twierdzenie zawsze będzie możliwe do obalenia, to oznacza, że ​​​​jest wśród nich trochę = $= b}$${\ displaystyle n}$ jest dla których można udowodnić ${\ Displaystyle P (b)} .$

Podobnie jak w przypadku przykładów omówionych wcześniej, dowód tego wymaga eksplozji po stronie poprzedzającej, aby otrzymać zdania bez zaprzeczeń. Jeśli zdanie jest sformułowane tak, że zaczyna się od , to ten początkowy przypadek już daje formę eksplozji z pustej klauzuli m = { $m = 0}$

${\ Displaystyle \ bot \ do \ istnieje (b <0). P (b)}$ .

W następnym przypadku stwierdza się eliminację podwójnej negacji dla rozstrzygalnego predykatu, ${\ displaystyle m = 1}$

${\ Displaystyle \ neg \ neg P (0) \ do P (0)}$ .

Przypadek brzmi ${\ displaystyle m = 2}$

${\ Displaystyle \ neg {\ duży (} \ neg P (0) \ ziemia \ neg P (1) {\ duży )} \ do {\ duży (} P (0) \ lub P (1) {\ duży )}}$ ,

co, jak już wspomniano, jest równoważne

${\ Displaystyle \ neg \ neg {\ duży (} P (0) \ lor P (1) {\ duży)} \to {\big (}P(0)\lub P(1){\big)}}$ .

Zarówno ${\ displaystyle m = 0},$$jak$ przypadkami eliminacji podwójnej negacji dla rozstrzygalnego predykatu. Oczywiście stwierdzenie ${\ Displaystyle \ istnieje (b <m).$$)$$}$ dla ustalonego można udowodnić innymi sposobami, stosując zasady minimalnej logiki.

Nawiasem mówiąc, nieograniczonego schematu dla ogólnych rozstrzygalnych predykatów nie da się nawet udowodnić intuicjonistycznie, patrz zasada Markowa .

Związek z teorią typów

Użycie negacji

Absurd jest $dedukcji$ nie tylko w naturalnej , ale także w typowych sformułowaniach teoretycznych w ramach korespondencji Curry – Howard . W systemach typu ${\ displaystyle \ bot}$ jest często wprowadzany jako typ pusty.

W wielu kontekstach nie musi $.$ oddzielną stałą w logice, ale jej rolę można zastąpić dowolną odrzuconą propozycją $.$ można $zdefiniować$ gdzie być Twierdzenie o nieistnieniu dowodu na to twierdzenie jest zatem twierdzeniem o spójności.

Przykładowa charakterystyka dla $.$$\ bot}$ jest w teorii obejmującej liczby naturalne Można to również przyjąć w zwykłej logice konstruktywnej. Dzięki temu udowodnienie, $że$${4} = 8$ fałszywe, tj. 8 udowodnić ${\ Displaystyle (3 ^ {4} = 8) \ do (0 = 1)}$ . Możemy wprowadzić notację $aby$ uchwycić I rzeczywiście, używając arytmetyki, ${\ Displaystyle {\ tfrac {3 ^ {4} -8} {73}} = 1}$ posiada, ale ${\ Displaystyle (3 ^ {4}=8)}$ implikuje również ${\ Displaystyle {\ tfrac {3 ^ {4} -8} {73}} = 0}$ . Oznaczałoby to więc, że ${\ displaystyle 1 = 0}$ i stąd otrzymujemy ${\ Displaystyle \ neg (3 ^ {4} = 8)}$ . CO BYŁO DO OKAZANIA.

Proste typy

Funkcjonalne rachunki programowania zależą już przede wszystkim od spójnika implikacji, patrz np. rachunek konstrukcji dla struktury logiki predykatów .

W tej sekcji wspominamy o systemie uzyskanym przez ograniczenie logiki minimalnej tylko do implikacji i opisujemy go formalnie. Można go zdefiniować za pomocą następujących kolejnych reguł:

                $\ Displaystyle {\ dfrac {} {\ Gamma \ kubek \ {A \} \ vdash A}} {\ mbox {aksjomat}}}$${\ Displaystyle {\ dfrac {\ Gamma \ puchar \ {A \} \ vdash B} {\ Gamma \ vdash A \ do B}} {\ mbox {intro}}}$${\ Displaystyle {\ dfrac {\ Gamma \ vdash A \ do B ~~~~~~~~~~ \ Delta \ vdash A} {\ Gamma \ kubek \ Delta \ vdash B}} {\ mbox {elim.} }}$

Każda formuła tej ograniczonej logiki minimalnej odpowiada typowi w rachunku lambda o prostym typie , patrz korespondencja Curry – Howard . W tym kontekście wyrażenie minimalna logika jest czasami używane w znaczeniu tego ograniczenia minimalnej logiki. Ten implikacyjny fragment logiki minimalnej jest tym samym, co pozytywny, implikacyjny fragment logiki intuicjonistycznej, ponieważ logika minimalna jest już po prostu pozytywnym fragmentem logiki intuicjonistycznej.

Semantyka

Istnieją semantyki logiki minimalnej, które odzwierciedlają semantykę ramową logiki intuicjonistycznej , zob. omówienie semantyki w logice parakonsystentnej . Tutaj funkcje wartościujące przypisujące zdaniom prawdziwość i fałsz mogą podlegać mniejszym ograniczeniom.

Zobacz też

• Logika intuicjonistyczna
• Logika parakonsystencji
• Implikacyjny rachunek zdań
• Lista systemów logicznych

•   AS Troelstra i H. Schwichtenberg, 2000, Podstawowa teoria dowodu , Cambridge University Press, ISBN 0521779111