Erfüllbarkeit, Unerfüllbarkeit und Allgemeingültigkeit

Zu einer gegebenen Formel kann man verschiedene Belegungen betrachten, die auch zu unterschiedlichen Wahrheitswerten für diese Formel führen können. Jede Formel kann eine der drei Eigenschaften haben:

• Erfüllbarkeit: Es existiert eine passende Belegung, die die Formel erfüllt (wahr macht).
• Unerfüllbarkeit: Es existiert keine passende Belegung, die die Formel erfüllt.
• Allgemeingültigkeit (Tautologie): Jede passende Belegung erfüllt die Formel.