Database Reference
In-Depth Information
alle Formeln
erfullbare, aber
nicht allgemeingultige
Formeln
allgemeingultige
Formeln
unerfullbare
Formeln
=
falsifizierbare, aber
nicht unerfullbare
Formeln
erfullbare Formeln
falsifizierbare Formeln
Abbildung 3.3
Klassifizierung von Formeln
In Abbildung 3.3 ist die Klassifizierung der Formeln aus Definition 3.12 sche-
matisch dargestellt. Es gelten die folgenden Beziehungen:
•
Eine Formel ist genau dann allgemeingultig, wenn sie nicht falsifizierbar ist.
•
Eine Formel ist genau dann unerfullbar, wenn sie nicht erfullbar ist.
Fur die Aussagenlogik und fur geschlossene Formeln
2
der Pradikatenlogik 1. Stufe
gelten bezuglich der Negation daruber hinaus die folgenden Beziehungen:
•
Eine Formel ist genau dann allgemeingultig, wenn ihre Negation unerfullbar
ist.
•
Eine Formel ist genau dann erfullbar, wenn ihre Negation falsifizierbar ist.
Man beachte also, dass aus einer allgemeingultigen Formel durch Negation eine
unerfullbare Formel wird; aus einer erfullbaren, aber nicht allgemeingultigen Formel
wird durch Negation hingegen wieder eine erfullbare, aber nicht allgemeingultige
Formel.
Selbsttestaufgabe 3.13 (Erfullbarkeit)
Geben Sie bei jedem der nachfolgenden
Ausdrucke an (mit Begrundung bzw. Beweis), ob er unerfullbar, erfullbar oder all-
gemeingultig ist:
1.)
P
⇒
P
3.)
¬
P
⇒
P
5.)
P
⇒
(Q
⇒
P )
2.)
P
⇒¬
P
4.)
P
⇔¬
P
2
Eine Formel heißt
geschlossen
, wenn alle darin auftretenden Variablen durch Quantoren ein-
gefuhrt wurden.
