Definisjon: Oppfyllbarhet
Test deg selv
Hvilke av disse formlene er oppfyllbare?
Denne er oppfyllbar. Vi kan gjøre den sann ved å gjøre $P$ sann.
Denne er oppfyllbar. Vi kan gjøre den sann ved å gjøre $P$ sann eller ved å gjøre $Q$ sann (eller begge).
Denne er oppfyllbar. Den er sann uansett hva sannhetsverdien til $P$ er.
$(P \land \neg P)$ er ikke oppfyllbar, for det finnes ingen valuasjoner som gjør formelen sann. Hvis vi for motsigelse antar at formelen er oppfyllbar, så må det finnes en valuasjon som gjør $P$ sann og $\neg P$ sann. For å gjøre $\neg P$ sann må $P$ være usann. Da har vi en motsigelse, for $P$ kan ikke både være sann og usann. Altså er ikke formelen oppfyllbar.
Denne er oppfyllbar. Den er sann uansett hva sannhetsverdien til $P$ er.
$\neg (P → P)$ er ikke oppfyllbar, for det finnes ingen valuasjoner som gjør formelen sann. Hvis vi for motsigelse antar at formelen er oppfyllbar, så må det finnes en valuasjon som gjør $\neg (P → P)$ sann og dermed $(P → P)$ usann. For å gjøre $(P → P)$ usann må valuasjonen gjøre $P$ sann og $P$ usann. Da har vi en motsigelse, for $P$ kan ikke både være sann og usann. Altså er ikke formelen oppfyllbar.
Denne er oppfyllbar. Vi kan gjøre den sann ved å gjøre $P$ usann.