Matrizenmethode

Eine Möglichkeit, die Allgemeingültigkeit einer Aussage zu überprüfen, besteht darin, die Aussage für alle möglichen Variablenbelegungen auszuwerten und zu schauen, ob immer wahr herauskommt. Im Folgenden ist in jeder Zeile eine andere Kombination von Variablenbelegungen notiert. Unter den Variablen selbst steht diese Belegung. Unter Benutzung der Wertetabellen für die Junktoren, werden die einzelnen Terme (hier in Klammern) ausgewertet und das Ergebnis unter die Junktoren geschrieben.

Beispiel 1:

${\displaystyle (}$	${\displaystyle p}$	${\displaystyle \rightarrow }$	${\displaystyle q}$	${\displaystyle )}$	${\displaystyle \vee }$	${\displaystyle (}$	${\displaystyle q}$	${\displaystyle \rightarrow }$	${\displaystyle p}$	${\displaystyle )}$
	w	w	w		w		w	w	w
	w	f	f		w		f	w	w
	f	w	w		w		w	f	f
	f	w	f		w		f	w	f

Der getestete Ausdruck ist gültig, denn in der Spalte unter dem Hauptjunktor stehen nur w’s, d. h. die Auswertung der Formel ergibt immer wahr.

Beispiel 2:

${\displaystyle (}$	${\displaystyle p}$	${\displaystyle \rightarrow }$	${\displaystyle q}$	${\displaystyle )}$	${\displaystyle \vee }$	${\displaystyle (}$	${\displaystyle q}$	${\displaystyle \land }$	${\displaystyle p}$	${\displaystyle )}$
	w	w	w		w		w	w	w
	w	f	f		f		f	f	w
	f	w	w		w		w	f	f
	f	w	f		w		f	f	f

Der in Beispiel 2 getestete Ausdruck ist nicht gültig, denn es gibt eine Belegung, für die sich die Aussage nicht zu wahr auswertet.

Eine kürzere Methode ist die Folgende. Man nimmt an, die Aussage wäre falsch und versucht, einen (semantischen) Widerspruch aufzuzeigen.

Man beachte, dass die Methode nicht für alle Junktoren so einfach abläuft, wie im folgenden Beispiel! Hat man etwa einen Ausdruck vom Typ ${\displaystyle X\wedge Y}$, muss für den Beweis der Existenz eines Widerspruchs ggf. sowohl die Möglichkeit ${\displaystyle X=w,\ Y=f}$, als auch ${\displaystyle X=f,\ Y=w}$ durchgeprüft werden, da beide Fälle die Annahme ${\displaystyle X\wedge Y=f}$ erfüllen würden.

Beispiel 1:

${\displaystyle (}$	${\displaystyle p}$	${\displaystyle \rightarrow }$	${\displaystyle q}$	${\displaystyle )}$	${\displaystyle \vee }$	${\displaystyle (}$	${\displaystyle q}$	${\displaystyle \rightarrow }$	${\displaystyle p}$	${\displaystyle )}$
					f
		f						f
	w		f				w		f

Unter der Annahme, der Ausdruck ${\displaystyle (p\rightarrow q)\vee (q\rightarrow p)}$ sei falsch, kommt man zu dem Widerspruch, das ${\displaystyle p}$ (und auch ${\displaystyle q}$) „gleichzeitig“ sowohl wahr als auch falsch sein müssen.

Beispiel 2:

${\displaystyle (}$	${\displaystyle p}$	${\displaystyle \rightarrow }$	${\displaystyle q}$	${\displaystyle )}$	${\displaystyle \vee }$	${\displaystyle (}$	${\displaystyle q}$	${\displaystyle \land }$	${\displaystyle p}$	${\displaystyle )}$
					f
		f						f
	w		f
							f		w

Unter der Annahme, der Ausdruck ${\displaystyle (p\rightarrow q)\vee (q\land p)}$ sei falsch, kommt man zu keinem Widerspruch. Jede Belegung, die ${\displaystyle p}$ den Wert w und ${\displaystyle q}$ den Wert f zuordnet ist widerlegende Belegung.

• Hilbertkalkül
• Tableaukalkül
• Systeme natürlichen Schließens (SNS)
• Sequenzenkalkül

• Kalkül
• Beweistheorie

• Horst Wessel: Logik. VEB Deutscher Verlag der Wissenschaften, Berlin 1984, S. 60 ff.