Gültigkeit einer Formel
Def.: Die Interpretation, die eine Formel P zu einer wahren Aussage macht, heißt ein Modell der Formel. Es gilt:
- Eine Formel heißt erfüllbar (konsistent), wenn sie mindestens ein Modell hat. Beispiel: a ? b Modell ist (die Interpretation mit) Belegung a =1 und b=1.
- Eine Formel heißt nicht erfüllbar (kontradiktorisch), wenn sie kein Modell hat. Beispiel: a ? ?a
- Eine Formel heißt eine Tautologie, wenn sie für alle Belegungen wahr ist (Alle Belegungen liefern ein Modell der Formel). Beispiel: a ? ?a