Teoria demonstracji – Wikipedia

. Teoria demonstracji , znany również jako Teoria dowodu (z angielskiego Teoria dowodu ), jest gałęzią logiki matematycznej. Został założony przez Davida Hilberta na początku Xx ^{To jest} wiek.

Hilbert zaproponował tę nową dyscyplinę matematyczną podczas swojej słynnej prezentacji 2 ^{To jest} Kongres Międzynarodowych Matematyków w 1900 r. W celu wykazania spójności matematyki. Cel ten został unieważniony przez nie mniej znane twierdzenie o niekompletności Gödela w 1931 r., Które nie zapobiegły rozwojowi teorii demonstracji, w szczególności dzięki pracy Jacquesa Herbranda i Gerharda Gentzena. Ten ostatni wykazał jeden z głównych wyników teorii demonstracji, znany jako Hauptsatz (główne twierdzenie) lub twierdzenie o cięciach. Gentzen następnie użył tego twierdzenia, aby nadać pierwszą czysto syntaktyczną demonstrację spójności arytmetyki.

Po okresie spokoju, który nadal umożliwił ustanowienie pewnej liczby innych wyników względnej spójności i szkicowanie klasyfikacji teorii aksjomatycznych, teoria demonstracji doświadczyła spektakularnego odrodzenia w latach 60. XX wieku w latach 60. XX wieku który wykazywał nowy i głęboki związek strukturalny między logiką a informatyką: zasadniczo procedura cięcia określona przez gentzen można postrzegać jako proces obliczeniowy, aby pokazy formalne stały się programami, których typ jest propozycją, którą należy wykazać. Od tego czasu teoria demonstracji rozwinęła się w ścisłej symbiozie z innymi obszarami logiki i informatyki teoretycznej, w szczególności Lambda-Calculcul, i urodziła nowe modele obliczeń, najnowszą jest logika liniowa Jean-Yves Girard W 1986 r. Dziś część teorii demonstracji jest mylona z semantyką języków programowania i wchodzi w interakcje z wieloma innymi dyscyplinami logiki lub informatyki teoretycznej:

• (W) Bus S. R. (red.), Podręcznik teorii dowodu , Amsterdam, Elsevier, 1998.
• (W) A. S. Troelstra (W) , H. Schwichtenberg (1996). Podstawowa teoria dowodu . W serii Cambridge traktaty w teoretycznej informatyce , Cambridge University Press, (ISBN 0-521-77911-1 ) .
• Karim Nour, René David, Raffali Christophe Wprowadzenie do logiki: teoria demonstracji – poprawione kursy i ćwiczenia , wyd. Dunod.
• J.-Y. Girard, Ślepy punkt , Lekcje logiczne , wyd. Hermann, Paryż, kolekcja «Visions des Sciences»:
  • Tome 1: Do perfekcji , 280 s., Maj 2006 . Kursy w teorii demonstracji rozpoczyna się od refleksji na temat obecnego stanu logiki (esencjalizm i egzystencjalizm, twierdzenie niekompletności Gödela, obliczenia sekwencyjnego), kontynuuje korespondencję curry-howard (system F, interpretacja kategorii), a następnie motywuje i opisuje logikę liniową (spójne przestrzenie, system LL, sieci dowodowe).
  • Tome 2: Do niedoskonałości , 288 s., Mars 2007 . Kurs trwa poprzez ujawnienie „hipotezy polaryzacji” („Designs”, „Playful” i systemów LC I LLP ), następnie opisuje systemy eksperymentalny Lll I Łokieć I „spójne przestrzenie kwantowe”, a ostatecznie kończy się „geometrią interakcji”.
• J.-Y. Girard, P. Taylor, Y. Lafont, Dowody i typy , Cambridge University Press, 1989