Aufgabe:
Eingabe: Eine aussagenlogische Formel ϕ.
Frage: Gibt es eine Belegung die ϕ erfüllt, also eine Belegung β mit β |= ϕ?
Sprache: sat = {code(ϕ) | ϕ ist eine erfüllbare Formel der Aussagenlogik},
cnf-sat = {code(ϕ) | ϕ ist eine erfüllbare Formel der Aussagenlogik in CNF}.
Wir betrachten nun die folgenden aussagenlogischen Formeln:
ϕ1 = (x∨y∨z)∧(¬y∨ ¬z)
ϕ2 = x∧(y∨ ¬x)∧(z∨ ¬y)
ϕ3 = (x∨y∨z∨w)∧(x∨y∨z∨ ¬w)
ϕ4 = (x∨y)∧(x∨ ¬y)∧(¬x∨y)∧(¬x∨ ¬y)
1. Bestimmen Sie für jede Formel ϕi die Anzahl der Belegungen β, sodass β |= ϕi
.
2. Für welche der Formeln ϕi gilt code(ϕi) ∈ cnf-sat?
Problem/Ansatz:
Also das Entail Zeichen heißt ja, dass man zeigen kann, dass beide Seiten wahr sind oder?
In wie fern kann man β |= ϕi zeigen, wenn β eine Anzahl von Belegungen sein soll?
Komme mit der Aufgabenstellung nicht klar.
