Seite parallel anzeigen





Das Widerlegungstheorem - der indirekte Beweis

(Aussagenlogik Kapitel 7.1.3)

Diese Seite nimmt Bezug auf

(Seite parallel anzeigen)
Liste überspringen
Zum Seitenanfang

Das Widerlegungstheorem (auch "Kontradiktionstheorem") ist eine komplementäre Formulierung des Deduktionstheorems.

Das Widerlegungstheorem besagt, dass Γ∪γ ist unerfüllbar gdw. Γ|=!γ gilt.
Daraus folgt:
{γ1, γ2,..., γn}|=γ gilt gdw. γ1&γ2&...&γn&!γ unerfüllbar ist, also zu einem Widerspruch führt.

An dieser letzten Formulierung kann man sehen, dass das Kontradiktionstheorem die Grundlage für den indirekten Beweis ist.

Beispiel - Widerlegungstheorem und indirekter Beweis

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 indirekt zeigen dass wir daraus
  • γ=falle_c1
logisch schließen können, dass also Γ|=γ gültig ist.


Um die Gültigkeit des Schlusses indirekt zu zeigen, nehmen wir das Gegenteil an und führen dies zu einem Widerspruch:
Nach dem Deduktionstheorem können wir die Gültigkeit des Schlusses
  • Γ|=γ
auf die Frage nach der Gültigkeit der Formel
  • γ1&γ2&γ3&γ4->γ
reduzieren. Weiters gilt natürlich folgendes:
  • γ1&γ2&γ3&γ4->γ ist gültig gdw. !(γ1&γ2&γ3&γ4->γ) unerfüllbar ist.
Wandeln wir die Formel !(γ1&γ2&γ3&γ4->γ) um:
  • !(γ1&γ2&γ3&γ4->γ)
  • ≡!(!(γ1&γ2&γ3&γ4)|γ)
  • ≡!!(γ1&γ2&γ3&γ4)&!γ
  • ≡γ1&γ2&γ3&γ4&!γ
Es gilt also
  • {γ1, γ2, γ3, γn}|=γ gilt gdw. γ1&γ2&γ3&γn&!γ unerfüllbar ist.
Dies ist genau die Formulierung des Widerlegungstheorems.