V-Interpretation
Zur 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ültigkeit
Definition 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. |= φ → ψ. |
|
|
Folgerungsbeziehung
Definition 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 AL
Die 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önig
Lemma 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 Äquivalenz
Definition 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 φ, ψ ∈ AL n
gilt demnach: φ ≡ ψ gdw. für alle (b 1
,...,b n
) ∈ B n ist φ[b 1
,...,b n
] = ψ[b 1
,...,b n
]. |
Logische Äquivalenz lässt sich durch Wahrheitstafeln nachweisen. |
Vollständige Systeme von Junktoren
Für n >= 1 lassen sich alle Booleschen Funktionen in B n
durch AL n
-Formeln darstellen, die nur die Aussagenvariablen in V n
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 = {p i
: 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ändigkeit
Satz 3.2 Zu jeder Funktion f ∈ B n
gibt es φ ∈ AL n
mit f =f φ
. |
Man prüft durch Fallunterscheidung |
to do |
KNF und DNF
Satz 3.7 Zu jeder Formel φ ∈ AL n
gibt es äquivalente Formeln φ 1
∈AL n
in KNF und φ 2
∈AL n
in DNF. |
|
Created By
Metadata
Comments
No comments yet. Add yours below!
Add a Comment
More Cheat Sheets by tiziano123