Entscheidungsverfahren (klassische Aussagenlogik)

aus Wikipedia, der freien Enzyklopädie

Wechseln zu: Navigation, Suche

Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik zur Löschung vorgeschlagen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht signifikant verbessert werden können.

Bitte hilf mit und beteilige dich an der Diskussion!

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Siehe Disk.!--Thomas S. ^DISK. QS-Mach mit! 21:35, 28. Dez 2005 (CET)

Bei einem Entscheidungsverfahren handelt es sich um die Überprüfung von Gültigkeit mittels Anwendung eines oder mehrerer Testverfahren.

Inhaltsverzeichnis

1 Semantische Entscheidungsverfahren
- 1.1 Vollständige Matrizenmethode
- 1.2 Verkürzte Matrizenmethode
2 Syntaktische Entscheidungsverfahren
3 Siehe auch

[Bearbeiten] Semantische Entscheidungsverfahren

[Bearbeiten] Vollständige Matrizenmethode

Test auf semantische Gültigkeit eines komplexen Ausdruckes in dem man alle möglichen Einsetzungsinstanzen von w (wahr, oft auch 1) und f (falsch, oft auch 0) unter Benutzung der Wertetabellen für die Junktoren durchmustert.

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 Hauptverknüpfungszeichen stehen nur w’s.

Beispiel 2:

$($	$p$	$\rightarrow$	$q$	$)$	$\vee$	$($	$q$	$\and$	$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 nicht-erfüllende Belegung.

[Bearbeiten] Verkürzte Matrizenmethode

Test auf semantische Gültigkeit eines Ausdrucks, in dem man annimmt, er wäre falsch (hätte den Wert f) und versucht, einen (semantischen) Widerspruch aufzuzeigen.

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$	$\and$	$p$	$)$
					f
		f						f
	w		f
							f		w

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

[Bearbeiten] Syntaktische Entscheidungsverfahren

[Bearbeiten] Siehe auch

Entscheidungsverfahren (klassische Aussagenlogik)

Inhaltsverzeichnis

[Bearbeiten] Semantische Entscheidungsverfahren

[Bearbeiten] Vollständige Matrizenmethode

[Bearbeiten] Verkürzte Matrizenmethode

[Bearbeiten] Syntaktische Entscheidungsverfahren

[Bearbeiten] Siehe auch

Meine Werkzeuge

Namensräume

Varianten

Ansichten

Aktionen

Suche

Navigation

Mitmachen

Drucken/exportieren

Werkzeuge