Fitch-Kalkül
Der Fitch-Kalkül ist eine von dem amerikanischen Logiker Frederic Brenton Fitch erfundene Methode für Beweise in Prädikatenlogik erster Stufe. Der Beweis wird lediglich aufgrund syntaktischer Regeln geführt, ohne Berücksichtigung inhaltlicher Bedeutungen der vorkommenden Sätze, also formal. Der Fitch-Kalkül ist sowohl korrekt als auch vollständig und daher auch als Interaktives Beweissystem geeignet. Im Fitch-Kalkül ist zusätzlich zu den Prämissen des Hauptbeweises die Einführung beliebiger weiterer Annahmen erlaubt, aber nur innerhalb von Unterbeweisen. Damit ein Beweis korrekt ist, müssen alle Schritte außer den Voraussetzungen und den initialen Annahmen der Unterbeweise durch Logikregeln erster Ordnung belegt werden. Nachdem eine atomare Aussage bewiesen wurde, darf diese zur Begründung einer neuen Aussage herangezogen werden, bis der Beweis geführt wurde.

Regeln 
Der Fitch-Kalkül verwendet die Sprache der Prädikatenlogik erster Ordnung, also deren logische Operatoren (zum Beispiel UND, ODER, IMPLIZIERT, NICHT usw.), angewendet auf atomare Aussagen (im Folgenden vertreten durch Kleinbuchstaben p, q, …). Das Symbol  ist der Ableitungsoperator (z. B.  lies: „p beweist q“ oder „q ist ableitbar aus p“).
Im Fitch-Kalkül gibt es folgende Ableitungsregeln:

Negations-Einführung Ist p IMPLIZIERT q sowie p IMPLIZIERT NICHT q gegeben, dann auch NICHT p (s. Reductio ad absurdum). Beispiel: 
Negations-Beseitigung Ist NICHT NICHT p gegeben (oder jede andere gerade Anzahl von Negationen), dann auch p (s. Gesetz der doppelten Negation). Beispiel: 
Konjunktions-Einführung Sind p, q, r… gegeben, dann auch p UND q UND r…. Beispiel: 
Konjunktions-Beseitigung Ist p UND q UND r… gegeben, dann auch p, q, r…. Beispiel: 
Disjunktions-Einführung Ist p gegeben, dann auch p ODER q ODER r…. Beispiel: 
Disjunktions-Beseitigung Ist p ODER q ODER r… gegeben sowie p IMPLIZIERT z, q IMPLIZIERT z, r IMPLIZIERT z…, dann auch z. Beispiel: 
Äquivalenz-Einführung Ist p IMPLIZIERT q sowie q IMPLIZIERT p gegeben, dann auch p ÄQUIVALENT q. Beispiel: 
Äquivalenz-Beseitigung Ist p ÄQUIVALENT q gegeben, dann auch p IMPLIZIERT q sowie q IMPLIZIERT p. Beispiel: 
Subjunktions-Einführung Ist gezeigt worden, dass q durch Fitch-Ableitungsregeln aus p bewiesen werden kann (Notation: p  q), dann gilt auch p IMPLIZIERT q. Durch Subjunktions-Einführung beendet man einen Unterbeweis. Beispiel: 
Subjunktionsbeseitigung Ist p gegeben sowie p IMPLIZIERT q, dann auch q. Beispiel: 

Enthält die Sprache Quantoren, kommen vier weitere Regeln hinzu:
Allquantor-Einführung Ist ein Satz mit freien Variablen gegeben, lässt sich die Tatsache, dass diese jeden beliebigen Wert der Grundmenge annehmen können, als Allquantifizierung schreiben. Beispiel: 

Allquantor-Beseitigung Ist ein allquantifizierter Satz gegeben, lässt sich von diesem allgemeinen Fall auf einen beliebigen Einzelfall schließen; die vom Allquantor gebundene Variable kann also durch jedes Element der Grundmenge ersetzt werden. Beispiel: 

Existenzquantor-Einführung Ist ein konkreter Einzelfall gegeben, lässt sich dies als Existenzaussage formalisieren. Beispiel: „Rom ist die Hauptstadt Italiens“ impliziert drei Existenzaussagen: 1. Es existiert etwas, das die Hauptstadt Italiens ist, 2. es existiert etwas, von dem Rom die Hauptstadt ist, 3. es existiert etwas, das die Hauptstadt von etwas ist.

Existenzquantor-Beseitigung Aus einer allquantifizierten Implikation (zum Beispiel ∀x.r(x) → y, „Für alle x gilt: hat x die Eigenschaft r, so folgt y“) und dem Wissen um die Existenz eines solchen x (im Beispiel: ∃x.r(x), „es existiert ein x mit dem Prädikat r“) lässt sich auf das Sukzedens (hier: y) schließen. Beispiel: Aus den beiden Prämissen 1. ∀x.(x erhält die Mehrheit der abgegebenen Stimmen → x ist gewählt) und 2. ∃x.(x hat die Mehrheit der Stimmen erhalten) lässt sich schließen: x ist gewählt.

Beispiele 
Das folgende Beispiel beweist den Kettenschluss: . Daraus folgt .
Der Pfeil → bedeutet IMPLIZIERT, IE ist kurz für Implication Elimination (Subjunktionsbeseitigung), II für Implication Introduction (Subjunktionseinführung).

Hier ein Beweis für die Distribution der Implikation :

Aus der Prämisse ∃y.∀x.r(x,y) – „Es existiert ein y, sodass r(x,y) für alle x gilt“ soll gezeigt werden, dass dann auch ∀x.∃y.r(x,y) gilt – „Zu jedem x existiert ein y, sodass r(x,y)“ wahr ist:

Abkürzungen: UE: Universal Elimination = Allquantor-Beseitigung, UI: Universal Introduction = Allquantor-Einführung, EI: Existential Introduction = Existenzquantor-Einführung, EE: Existential Eliminitation = Existenzquantor-Beseitigung

Anwendungen 
Der Fitch-Kalkül kann neben philosophischen Zwecken auch in der Informatik eingesetzt werden. Es hat vor allem in der theoretischen Informatik Bedeutung.

Weblinks 
 Eintrag „Fitch Calculus“ In: John Halleck's Logic Systems
 Übungen und Beweisrechner für den Fitch-Kalkül auf den Seiten der Stanford University.
 Java-Anwendung für Fitch-Beweise von Christian Gottschall (Universität Wien).

Literatur 
 Jon Barwise und John Etchemendy: Sprache, Beweis und Logik, Band 1: Aussagen- und Prädikatenlogik. Mentis 2005, ISBN 3-89785-440-6, dort. S. 59ff.117ff et passim (Band 2: Anwendungen und Metatheorie. Mentis 2006, ISBN 3-89785-441-4); dt. Übers. von Language proof and logic, Seven Bridges Press and CSLI, 1999.
 engl. Original als pdf

Logikkalkül
Philosophische Logik