Database Reference
In-Depth Information
3.4.4
Wahrheitstafeln und Ableitungen in der Aussagenlogik
Fur die Aussagenlogik stehen verschiedene Inferenzverfahren zur Verfugung. Die
bekannteste Methode basiert auf den schon besprochenen Wahrheitstafeln.
Beispiel 3.37 (Wahrheitstafeln)
Um die Allgemeingultigkeit der Formel (P
⇒
Q)
Q)zuuberprufen, legen wir fur die einzelnen Komponenten der Formel
entsprechende Spalten in einer Wahrheitstafel an. Es ergibt sich folgende Tabelle:
⇔
(
¬
P
∨
P
Q
P
⇒
Q
¬
P
¬
P
∨
Q
(P
⇒
Q)
⇔
(
¬
P
∨
Q)
0
0
1
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
1
1
In der letzten Spalte steht an jeder Stelle eine 1. Da der Wahrheitswert der Formel
damit fur
jede
Belegung der beteiligten atomaren Aussagen P und Q wahr ist,
handelt es sich bei der Formel (P
⇒
Q)
⇔
(
¬
P
∨
Q) um eine Tautologie.
Das Verfahren der Wahrheitstafeln bildet ein einfaches Entscheidungsverfahren,
eine aussagenlogische Formel auf Allgemeingultigkeit hin zu uberprufen. Allerdings
wachst der Aufwand exponentiell mit der Anzahl der in einer Formel auftretenden
Variablen: Fur eine Formel mit n atomaren Formeln mussen 2
n
Zeilen der Wahr-
heitstafel berechnet werden.
Selbsttestaufgabe 3.38 (Wahrheitstafeln)
Untersuchen Sie mit Hilfe von
Wahrheitstafeln, fur welche Interpretationen die folgenden Paare von Formeln den
gleichen Wahrheitswert haben:
1.
¬
(P
∧
Q)
⇔
R
und
P
∧
Q
∧
R
R)
Neben der Wahrheitstafelmethode stehen die aussagenlogischen Inferenzregeln
der klassisch-logischen Systeme fur Ableitungen in der Aussagenlogik zur Verfugung
(vgl. Abschnitt 3.3.3), wobei auch das Beweisverfahren durch Herleitung eines Wi-
derspruchs moglich ist (Abschnitt 3.3.5). Auf die aussagenlogische Variante des
Resolutionsverfahrens werden wir in Abschnitt 3.6 eingehen.
2. (
¬
P
∨
Q)
⇔
R
und
(
¬
(
¬
P
∨
Q)
∨
R)
∧
((P
⇒
Q)
∨¬
3.5
Logische Grundlagen: Pradikatenlogik 1. Stufe
Wahrend wir die wichtigsten Aspekte der Aussagenlogik im letzten Abschnitt formal
definiert haben, wollen wir nun die Pradikatenlogik 1. Stufe (PL1) ebenfalls kurz
vorstellen. Wesentliche Eigenschaften von PL1 haben wir ja bereits im Rahmen
allgemeiner logischer Systeme angegeben; im Folgenden benutzen wir wieder die in
Abschnitt 3.2 eingefuhrte Sprechweise und erlautern, wie PL1 die Aussagenlogik
erweitert. Dabei definieren wir nicht, wie sonst eher ublich, erst die gesamte Syntax
und dann die Semantik von PL1, sondern geben zu den jeweiligen syntaktischen
Einheiten unmittelbar auch ihre semantische Bedeutung mit an.
