Matrizenmethode

Die Matrizenmethode ist ein Entscheidungsverfahren für die Gültigkeit einer Aussage der Aussagenlogik. Mit ihr kann entschieden werden, ob eine Aussage immer wahr ist – also für jede beliebige Variablenbelegung.

Weitere aussagenlogische Entscheidungsverfahren sind die ähnlich simplen Wahrheitstabellen, Binäre Entscheidungsdiagramme und Davis-Putnam-Verfahren. Auf der theoretischen Seite ist das zum Entscheidungsproblem äquivalente Erfüllbarkeitsproblem der Aussagenlogik von großer Bedeutung.

Vollständige 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:

$($	$p$	$\rightarrow$	$q$	$)$	$\vee$	$($	$q$	$\rightarrow$	$p$	$)$
	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:

$($	$p$	$\rightarrow$	$q$	$)$	$\vee$	$($	$q$	$\land$	$p$	$)$
	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.

Verkürzte Matrizenmethode

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 $X\wedge Y$ , muss für den Beweis der Existenz eines Widerspruchs ggf. sowohl die Möglichkeit $X=w,\ Y=f$ , als auch $X=f,\ Y=w$ durchgeprüft werden, da beide Fälle die Annahme $X\wedge Y=f$ erfüllen würden.

Beispiel 1:

$($	$p$	$\rightarrow$	$q$	$)$	$\vee$	$($	$q$	$\rightarrow$	$p$	$)$
					f
		f						f
	w		f				w		f

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

Beispiel 2:

$($	$p$	$\rightarrow$	$q$	$)$	$\vee$	$($	$q$	$\land$	$p$	$)$
					f
		f						f
	w		f
							f		w

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

Syntaktische Entscheidungsverfahren

Siehe auch

Quelle

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