Algorithmische Probleme der Logik

Dies sind grundlegende Entscheidungsprobleme, die sich auf logische Formeln beziehen:

• Auswertungsproblem: Gegeben eine Formel $\varphi$ und eine Belegung $\beta$, ist $\varphi$ unter $\beta$ wahr?
• Erfüllbarkeitsproblem (SAT): Gegeben eine Formel $\varphi$, gibt es eine Belegung, die $\varphi$ wahr macht?
• Äquivalenzproblem: Gegeben zwei Formeln $\varphi$ und $\psi$, sind sie unter allen Belegungen äquivalent?
• Allgemeingültigkeitsproblem: Gegeben eine Formel $\varphi$, ist sie unter allen Belegungen wahr?