Procedura dowód - Proof procedure

W logiką , w szczególności teorii dowód , A dowód procedura dla danego logicznego jest systematyczne Sposób wytwarzania dowody w niektórych dowód rachunku kwasu (udowodnienia) instrukcji.

Rodzaje dowód kamicy używany

Istnieje kilka rodzajów dowód kamieni. Najbardziej popularne są dedukcja naturalna , kamicy SEQUENT (tj Gentzen systemy typu), systemy Hilberta i semantyczny tableaux lub drzewa. Dana procedura dowód będzie skierowany do konkretnego rachunku dowód, ale często można przeformułować tak, aby wytworzyć dowodów w innych stylach dowodu.

Kompletność

Dowód procedura logiki jest kompletna , jeśli produkuje dowód dla każdego udowodnienia oświadczeniu. Twierdzenia układów logicznych są zazwyczaj rekurencyjnie przeliczalny , co implikuje istnienie kompletnego ale niezwykle nieefektywne procedury dowodowej; Jednak procedura jest tylko dowód zainteresowania, jeżeli jest racjonalnie efektywne.

W obliczu udowodnienia oświadczenie, kompletna procedura dowód może czasem uda się jej wykrywania i sygnalizacji unprovability. W ogólnym przypadku, gdy niedowodliwość jest semidecidable właściwość, to nie jest możliwe, a zamiast tego będą się różnić procedura (nie zakończyć).

Zobacz też

• Automatyczne dowodzenie twierdzeń
• dowód złożoność
• dowód tableaux
• System dedukcyjny
• Dowód (prawda)

Referencje

• W. Quine 1982 (1950). Metody logiki . Harvard Univ. Naciśnij.