Skondensowany oderwanie

Skondensowane oderwanie (reguła D) to metoda znajdowania najbardziej ogólnego możliwego wniosku na podstawie dwóch formalnych stwierdzeń logicznych. Został opracowany przez irlandzkiego logika Carewa Mereditha w latach pięćdziesiątych XX wieku i inspirowany pracami Łukasiewicza .

Nieformalny opis

Zasada oderwania (często określana jako $i$ ponens $q }$ mówi: „Biorąc pod uwagę, że implikuje biorąc $pod$ uwagę , wnioskować ${ \$ ”.

Skondensowany oderwanie idzie o krok dalej i mówi: „ Biorąc ${$ $i$ , że implikuje biorąc $pod$ uwagę , użyj unifikatora $\ displaystyle p}$ ${ \ displaystyle r}$ , aby uczynić $displaystyle$ r $r}$ takimi samymi, a następnie zastosować standardową zasadę oderwania.

Podstawienie A , które po zastosowaniu do daje $i$ podstawienie B , które po zastosowaniu do daje $}$ nazywane są unifikatorami $t$ { \ $r}$ $p}$ ${\ displaystyle$ i ${\ displaystyle r}$ .

Różne unifikatory mogą generować wyrażenia o różnej liczbie wolnych zmiennych . Niektóre możliwe wyrażenia ujednolicające są instancjami zastępczymi innych. Jeśli jedno wyrażenie jest instancją podstawienia innego (a nie tylko zmianą nazwy zmiennej), wówczas to drugie jest nazywane „bardziej ogólnym”.

Jeśli najbardziej ogólny unifikator jest używany w skondensowanym oderwaniu, to wynikiem logicznym jest najbardziej ogólny wniosek, jaki można wyciągnąć w danym wnioskowaniu z danym drugim wyrażeniem. Ponieważ każde słabsze wnioskowanie, jakie można uzyskać, jest instancją podstawienia najbardziej ogólnego, w praktyce nigdy nie używa się niczego innego niż najbardziej ogólny unifikator.

Niektóre logiki, takie jak klasyczny rachunek zdań , mają zestaw definiujących aksjomatów z właściwością „D-zupełności”. Jeśli zbiór aksjomatów jest D-zupełny, to każde ważne twierdzenie systemu, w tym wszystkie jego przypadki podstawienia (aż do zmiany nazwy zmiennej), może zostać wygenerowane przez samo skondensowane oderwanie. $(p\rightarrow p)\rightarrow (p\rightarrow p)$ przykład, jeśli $instancję$ twierdzeniem systemu D-zupełnego, skondensowane oderwanie może udowodnić nie tylko to twierdzenie, ale także jego używając dłuższego dowodu. Zauważ, że „D-zupełność” jest właściwością aksjomatycznej podstawy systemu, a nie wewnętrzną właściwością samego systemu logicznego.

JA Kalman udowodnił, że każdy wniosek, który może być generowany przez sekwencję podstawień jednolitych (wszystkie wystąpienia zmiennej są zastępowane tą samą treścią) i kroków modus ponens , może być generowany przez samo skondensowane oderwanie lub jest przypadkiem podstawieniowym czegoś, co może być generowany przez sam skondensowany oderwanie. To sprawia, że skondensowane oderwanie jest przydatne w każdym systemie logicznym, który ma modus ponens i substytucję, niezależnie od tego, czy jest D-zupełny, czy nie.

notacja D

Ponieważ dana przesłanka główna i dana przesłanka drugorzędna jednoznacznie określają wniosek (aż do zmiany nazwy zmiennej), Meredith zauważyła, że należy tylko zauważyć, które dwa stwierdzenia były zaangażowane, i że skondensowany rozdział może być używany bez wymaganej innej notacji. Doprowadziło to do „notacji D” dla dowodów . Ta notacja używa operatora „D” do oznaczenia skondensowanego oderwania i przyjmuje 2 argumenty w standardowym notacji przedrostka . Na przykład, jeśli masz cztery aksjomaty, typowy dowód w notacji D może wyglądać tak: DD12D34, który pokazuje skondensowany krok oddzielenia, wykorzystując wynik dwóch poprzednich skondensowanych kroków oddzielenia, z których pierwszy wykorzystywał aksjomaty 1 i 2, a drugi z który używał aksjomatów 3 i 4.

Ten zapis, oprócz tego, że jest używany w niektórych automatycznych dowodach twierdzeń, czasami pojawia się w katalogach dowodów.

Użycie unifikacji w skondensowanym oderwaniu poprzedza technikę rozwiązywania zautomatyzowanego dowodzenia twierdzeń , która została wprowadzona w 1965 roku.

Zalety

W przypadku zautomatyzowanego dowodzenia twierdzeń skondensowane oderwanie ma szereg zalet w porównaniu z surowym modus ponens i podstawieniem jednolitym.

W Modus Ponens i dowodzie podstawienia masz nieskończoną liczbę możliwości wyboru tego, co możesz zastąpić zmiennymi. Oznacza to, że masz nieskończoną liczbę możliwych kolejnych kroków. Przy skondensowanym oderwaniu istnieje tylko skończona liczba możliwych kolejnych kroków w dowodzie. ^{[ wymagane wyjaśnienie ]}

Notacja D dla kompletnych skondensowanych dowodów oderwania umożliwia łatwe opisywanie dowodów w celu katalogowania i wyszukiwania. Typowy kompletny 30-stopniowy dowód ma mniej niż 60 znaków w notacji D (z wyłączeniem zestawienia aksjomatów).

Hindley, J. Roger (1993), „logiki BCK i BCI, skondensowane oderwanie i właściwość 2” , Notre Dame Journal of Formal Logic , 34 (2): 231–250, doi : 10.1305/ndjfl/1093634655 , MR 1231287
William McCune i Larry Wos (1992). „Eksperymenty w automatycznej dedukcji ze skondensowanym oderwaniem” (PDF) . W D. Kapur (red.). proc. 11. Międzynarodowa Konferencja na temat Automatycznego Odliczenia (CADE) . LNCS. Tom. 607. Zygmunt. s. 209–223.