|
Zur Definition der Semantik weisen wir jeder Formel φ ∈ AL(V) zu einer gegebenen V-Interpretation einen Wahrheitswert φI ∈ B zu. Die Funktion
|
|
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. |= φ → ψ.
|
|
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 ψ |= (ψ ∧ φ) ∨ (ψ ∧ ¬φ).
|
|
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
|
0 ⊢ allgemeingültig ist für ein endliches Φ0 ⊆ Φ
|
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
|
|
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 (b1,...,bn) ∈ Bn ist φ[b1,...,bn] = ψ[b 1,...,bn]. |
|
Logische Äquivalenz lässt sich durch Wahrheitstafeln nachweisen.
|
|
Für n >= 1 lassen sich alle Booleschen Funktionen in B
n 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.
|
|
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|= ψ. |
|
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.
|
|
Satz 3.2 Zu jeder Funktion f ∈ B
n gibt es φ ∈ ALn mit f =fφ. |
|
Man prüft durch Fallunterscheidung
|
|
to do
|
|
Satz 3.7 Zu jeder Formel φ ∈ AL
n gibt es äquivalente Formeln φ1 ∈ALn in KNF und φ2 ∈ALn in DNF. |
No comments yet.
Cheatography n. The art of mapping complex subjects into clear, instantly navigable reference guides.