imported>PerfektesChaos: tk k

2026-01-22T09:38:47Z

tk k

Neue Seite

Die '''Matrizenmethode''' ist ein [[Entscheidbar|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 [[Wahrheitstabelle]]n, [[Binäres Entscheidungsdiagramm|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 [[Junktor]]en, werden die einzelnen Terme (hier in Klammern) ausgewertet und das Ergebnis unter die Junktoren geschrieben.

{| style="margin:0; text-align:center;"
|+ '''Beispiel 1'''
|-
| <math>(</math>
| <math>p</math>
| <math>\rightarrow</math>
| <math>q</math>
| <math>)</math>
| <math> \vee</math>
| <math>(</math>
| <math>q</math>
| <math>\rightarrow</math>
| <math>p</math>
| <math>)</math>
|-
|
| 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''.

{| style="margin:0; text-align:center;"
|+ '''Beispiel 2'''
|-
| <math>(</math>
| <math>p</math>
| <math>\rightarrow</math>
| <math>q</math>
| <math>)</math>
| <math> \vee</math>
| <math>(</math>
| <math>q</math>
| <math>\land</math>
| <math>p</math>
| <math>)</math>
|-
|
| 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 <math>X\wedge Y</math>, muss für den Beweis der Existenz eines Widerspruchs ggf. sowohl die Möglichkeit <math>X=w,\ Y=f</math>, als auch <math>X=f,\ Y=w</math> durchgeprüft werden, da beide Fälle die Annahme <math>X\wedge Y=f</math> erfüllen würden.

{| style="margin:0; text-align:center;"
|+ '''Beispiel 1'''
|-
| <math>(</math>
| <math>p</math>
| <math>\rightarrow</math>
| <math>q</math>
| <math>)</math>
| <math> \vee</math>
| <math>(</math>
| <math>q</math>
| <math>\rightarrow</math>
| <math>p</math>
| <math>)</math>
|-
|
|
|
|
|
| '''f'''
|
|
|
|
|
|-
|
|
| f
|
|
|
|
|
| f
|
|
|-
|
| '''w'''
|
| '''f'''
|
|
|
| '''w'''
|
| '''f'''
|
|}

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

{| style="margin:0; text-align:center;"
|+ '''Beispiel 2'''
|-
| <math>(</math>
| <math>p</math>
| <math>\rightarrow</math>
| <math>q</math>
| <math>)</math>
| <math> \vee</math>
| <math>(</math>
| <math>q</math>
| <math>\land</math>
| <math>p</math>
| <math>)</math>
|-
|
|
|
|
|
| '''f'''
|
|
|
|
|
|-
|
|
| f
|
|
|
|
|
| f
|
|
|-
|
| w
|
| f
|
|
|
|
|
|
|
|-
|
|
|
|
|
|
|
| f
|
| w
|
|}

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

== Syntaktische Entscheidungsverfahren ==
* [[Hilbertkalkül]]
* [[Tableaukalkül]]
* [[Systeme natürlichen Schließens|Systeme natürlichen Schließens (SNS)]]
* [[Sequenzenkalkül]]

== Siehe auch ==
* [[Kalkül]]
* [[Beweistheorie]]

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

[[Kategorie:Mathematische Logik]]

Matrizenmethode - Versionsgeschichte

imported>PerfektesChaos: tk k