V-InterpretationZur Definition der Semantik weisen wir jeder Formel φ ∈ AL(V) zu einer gegebenen V-Interpretation einen Wahrheitswert φI ∈ B zu. Die Funktion |
J:V → B
p → J(p)
J interpretiert p als
“falsch” wenn J(p) = 0 oder
“wahr” wenn J(p)=1, AllgemeingültigkeitDefinition 2.2 Eine Formel φ ∈ AL(V) heißt allgemeingültig gdw. für alle V-Interpretationen J gilt: J |= φ. In Symbolen: |= φ (anstelle von ∅ |= φ). | z.B. gilt für jedes φ: |=φ ∨ ¬φ. Man prüft mittels Wahrheitstafeln nach, dass φ |= ψ gdw. |= φ → ψ. |
| | FolgerungsbeziehungDefinition 2.1 φ |= ψ bzw. Φ |= ψ. Für φ,ψ ∈ AL(V), bzw. Φ ⊆ AL(V) und ψ ∈ AL(V): ψ ist eine logische Folgerung von φ, oder ψ folgt aus φ, in Symbolen φ |= ψ, gdw. für alle V-Interpretationen J gilt: J |= φ ⇒ J |= ψ. Entsprechend ist Φ |= ψ für Formelmengen Φ definiert (ψ folgt aus Φ). | Beispiele: Man weist anhand von Wahrheitstafeln nach, dass z.B. für beliebige φ, ψ gilt: φ ∧ ψ |= φ ∨ ψ, oder dass ψ |= (ψ ∧ φ) ∨ (ψ ∧ ¬φ). |
Quiz ALDie Formelmenge {p,p→q,¬q}
ist erfüllbar. Falsch | Für jede Formelmenge Φ ⊆ AL gilt Φ|=⊤. Wahr | Eine Formel φ ∈ AL enthält nur endlich viele aussagenlogische Variablen. Wahr | Wenn eine Formel φ ∈ AL erfüllbar ist, dann ist ¬φ nicht erfüllbar. Falsch | Wenn jede Formel einer Formelmenge Φ ⊆ AL erfüllbar ist, dann ist auch Φ erfüllbar. Falsch |
(I) φ ist erfüllbar gdw. φ ⊢ nicht allgemeingültig ist
(II) φ ist allgemeingültig gdw. ⊢ φ allgemeingültig ist
(III). φ|=ψ gdw. φ⊢ψ allgemeingültig ist
(IV). Φ ist unerfüllbar gdw. Φ ⊢allgemeingültig ist
(V). Φ ist unerfüllbar gdw. Φ0 ⊢ allgemeingültig ist für ein endliches Φ0 ⊆ Φ Lemma von KönigLemma 4.4 Sei T ein unendlicher, aber endlich verzweigter Baum. Dann gibt es in T einen unendlichen Pfad (von der Wurzel aus). | Bem.: Es ist klar, dass T beliebig lange endliche Pfade haben muss; daraus folgt aber keineswegs, dass es einen unendlich langen Pfad gibt |
| | Logische ÄquivalenzDefinition 2.3 Zwei Formeln φ, ψ ∈ AL(V) heißen (logisch) äquivalent, gdw. für alle V-Interpretationen J gilt: J|=φ gdw. J|=ψ. In Symbolen: φ≡ψ. | Für φ, ψ ∈ ALn gilt demnach: φ ≡ ψ gdw. für alle (b1,...,bn) ∈ Bn ist φ[b1,...,bn] =
ψ[b1,...,bn]. | Logische Äquivalenz lässt sich durch Wahrheitstafeln nachweisen. |
Vollständige Systeme von JunktorenFür n >= 1 lassen sich alle Booleschen Funktionen in Bn durch ALn-Formeln darstellen, die nur die Aussagenvariablen in Vn und die logischen Junktoren ∧ und ¬ benutzen. (Genauso auch mit ∨ und ¬.) | Ein solches System von Junktoren (oder zugehörigen Booleschen Funktionen) heißt vollständig. |
Kompaktheitssatz (AL)Satz 4.1 Sei V = {pi : 1 <= i ∈ N}, AL = AL(V). Für jede Formelmenge Φ ⊆ AL sind äquivalent: | (i) Φ ist erfüllbar. (ii) Jede endliche Teilmenge Φ0 ⊆ Φ ist erfüllbar. | Korollar 4.2 Für jede Formelmenge Φ ⊆ AL und Formel ψ ∈ AL sind äquivalent: | (i) Φ |= ψ. (ii) Es gibt eine endliche Teilmenge Φ0 ⊆ Φ derart, dass Φ0|= ψ. |
| | Erfüllbarkeit SAT(AL)Defintion 2.6 φ ∈ AL(V) heißt erfüllbar gdw. eine Interpretation existiert mit J |= φ. Analog für Formelmengen Φ ⊆ AL(V): Φ ist erfüllbar gdw. es eine Interpretation J gibt, die Φ erfüllt, d.h. mit J |= φ für alle φ ∈ Φ | Beobachtung 2.7 Erfüllbarkeit ist dual zur Allgemeingültigkeit: φ allgemeingültig gdw. ¬φ nicht erfüllbar. | Beobachtung 2.8 Die Folgerungsbeziehung lässt sich auf Erfüllbarkeit reduzieren: Φ |= ψ gdw. Φ ∪ {¬ψ} unerfüllbar ist. |
Funktionale VollständigkeitSatz 3.2 Zu jeder Funktion f ∈ Bn gibt es φ ∈ ALn mit f =fφ. | Man prüft durch Fallunterscheidung | to do |
KNF und DNFSatz 3.7 Zu jeder Formel φ ∈ ALn gibt es äquivalente Formeln φ1 ∈ALn in KNF und φ2 ∈ALn in DNF. |
|
Created By
Metadata
Comments
No comments yet. Add yours below!
Add a Comment
More Cheat Sheets by tiziano123