Seite parallel anzeigen





Logische Konsequenz und Implikation - Das Deduktionstheorem

(Aussagenlogik Kapitel 7.1.2)

Diese Seite nimmt Bezug auf

(Seite parallel anzeigen)
Liste überspringen
Zum Seitenanfang

Das Deduktionstheorem setzt die logische Konsequenz in Beziehung zur Implikation.
 
Das Deduktionstheorem besagt, dass Γ∪δ |=γ gilt gdw. Γ|=δ->γ gilt.
Daraus folgt:
{γ1, γ2,..., γn}|=γ gilt
gdw. |=γ1->(γ2->(...->(γn->γ)...)) gilt
gdw. |=γ1&γ2&...&γn->γ gilt.

Dies ermöglicht es uns, eine Schlussfolgerung auf eine Formel abzubilden und so die Frage nach der Gültigkeit eines Schlusses auf die nach der Gültigkeit einer Formel zu reduzieren:
  • Haben wir einen Schluss mit Prämissen, also eine Aussage der Form Γ|=γ, wobei Γ={γ1, γ2,..., γn}
    • wenden wir zunächst das Deduktionstheorem an, und erhalten einen Schluss der Gestalt
    • |=δ, wobei δ = γ1&γ2&...&γn->γ
  • Da |=δ bedeutet, dass δ eine Tautologie ist, können wir nun die Gültigkeit der Formel δ prüfen.

Das Deduktionstheorem bildet damit einen der wesentlichen Mechanismen, um den semantischen Begriff der logischen Konsequenz in mechanischen Inferenzsystemen durch rein formale Manipulationen handhabbar zu machen.

Beispiel - Anwendung des Deduktionstheorems

Betrachten wir wieder den Ausschnitt aus der Wumpus-Welt:
Nehmen wir an, die Formelmenge Γ besteht aus folgenden Formeln:
  • γ1=luftzug_b1->falle_c1|falle_b2
  • γ2=!luftzug_a2->!falle_b2&!falle_a3
  • γ3=luftzug_b1
  • γ4=!luftzug_a2
Wir wollen zeigen dass wir daraus
  • γ=falle_c1
logisch schließen können, dass also Γ|=γ gültig ist.


Wenden wir das Deduktionstheorem an ({γ1, γ2, γ3, ..., γn}|=γ gilt gdw. |=γ1&γ2&...&γn->γ gilt), so erhalten wir:
  • {luftzug_b1->falle_c1|falle_b2, !luftzug_a2->!falle_b2&!falle_a3, luftzug_b1, !luftzug_a2}|=falle_c1 gilt gdw.
    |=δ gilt, wobei δ = (luftzug_b1->falle_c1|falle_b2)&(!luftzug_a2->!falle_b2&!falle_a3)&luftzug_b1&!luftzug_a2->falle_c1

Nun müssen wir nur noch zeigen, dass δ gültig (also eine Tautologie) ist.