Show Menu
Cheatography

Aussagenlogik Cheat Sheet by

V-Inte­rpr­etation

Zur Definition der Semantik weisen wir jeder Formel φ ∈ AL(V) zu einer gegebenen V-Inte­rpr­etation einen Wahrhe­itswert φI ∈ B zu. Die Funktion
J:V → B
p → J(p)
J interp­retiert p als
“falsch” wenn J(p) = 0 oder
“wahr” wenn J(p)=1,

Allgem­ein­gül­tigkeit

Defi­nition 2.2 Eine Formel φ ∈ AL(V) heißt allgem­ein­gültig gdw. für alle V-Inte­rpr­eta­tionen J gilt: J |= φ. In Symbolen: |= φ (anstelle von ∅ |= φ).
z.B. gilt für jedes φ: |=φ ∨ ¬φ. Man prüft mittels Wahrhe­its­tafeln nach, dass φ |= ψ gdw. |= φ → ψ.
 

Folger­ung­sbe­ziehung

Defi­nition 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-Inte­rpr­eta­tionen J gilt: J |= φ ⇒ J |= ψ. Entspr­echend ist Φ |= ψ für Formel­mengen Φ definiert (ψ folgt aus Φ).
Beispiele: Man weist anhand von Wahrhe­its­tafeln nach, dass z.B. für beliebige φ, ψ gilt: φ ∧ ψ |= φ ∨ ψ, oder dass ψ |= (ψ ∧ φ) ∨ (ψ ∧ ¬φ).

Quiz AL

Die Formel­menge {p,p→q,¬q}
ist erfül­lbar. Falsch
Für jede Formel­menge Φ ⊆ AL gilt Φ|=⊤. Wahr
Eine Formel φ ∈ AL enthält nur endlich viele aussag­enl­ogische Variablen. Wahr
Wenn eine Formel φ ∈ AL erfüllbar ist, dann ist ¬φ nicht erfül­lbar. Falsch
Wenn jede Formel einer Formel­menge Φ ⊆ AL erfüllbar ist, dann ist auch Φ erfül­lbar. Falsch
(I) φ ist erfüllbar gdw. φ ⊢ nicht allgem­ein­gültig ist
(II) φ ist allgem­ein­gültig gdw. ⊢ φ allgem­ein­gültig ist
(III). φ|=ψ gdw. φ⊢ψ allgem­ein­gültig ist
(IV). Φ ist unerfu­̈llbar gdw. Φ ⊢allge­mei­ngu­̈ltig ist
(V). Φ ist unerfu­̈llbar gdw. Φ0 ⊢ allgem­ein­gültig ist für ein endliches Φ0 ⊆ Φ

Lemma von König

Lemma 4.4 Sei T ein unendl­icher, aber endlich verzwe­igter Baum. Dann gibt es in T einen unendl­ichen Pfad (von der Wurzel aus).
Bem.: Es ist klar, dass T beliebig lange endliche Pfade haben muss; daraus folgt aber keines­wegs, dass es einen unendlich langen Pfad gibt
 

Logische Äquivalenz

Defi­nition 2.3 Zwei Formeln φ, ψ ∈ AL(V) heißen (logisch) äquiva­lent, gdw. für alle V-Inte­rpr­eta­tionen 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 Wahrhe­its­tafeln nachwe­isen.

Vollst­ändige Systeme von Junktoren

Für n >= 1 lassen sich alle Booleschen Funktionen in Bn durch ALn-­Formeln darste­llen, die nur die Aussag­env­ari­ablen in Vn und die logischen Junktoren ∧ und ¬ benutzen. (Genauso auch mit ∨ und ¬.)
Ein solches System von Junktoren (oder zugehö­rigen Booleschen Funkti­onen) heißt voll­stä­ndig.

Kompak­the­itssatz (AL)

Satz 4.1 Sei V = {pi : 1 <= i ∈ N}, AL = AL(V). Für jede Formel­menge Φ ⊆ AL sind äquiva­lent:
(i) Φ ist erfüllbar. (ii) Jede endliche Teilmenge Φ0 ⊆ Φ ist erfüllbar.
Korollar 4.2 Für jede Formel­menge Φ ⊆ AL und Formel ψ ∈ AL sind äquiva­lent:
(i) Φ |= ψ. (ii) Es gibt eine endliche Teilmenge Φ0 ⊆ Φ derart, dass Φ0|= ψ.
 

Erfüll­barkeit SAT(AL)

Defi­ntion 2.6 φ ∈ AL(V) heißt erfüllbar gdw. eine Interp­ret­ation existiert mit J |= φ. Analog für Formel­mengen Φ ⊆ AL(V): Φ ist erfüllbar gdw. es eine Interp­ret­ation J gibt, die Φ erfüllt, d.h. mit J |= φ für alle φ ∈ Φ
Beob­achtung 2.7 Erfüll­barkeit ist dual zur Allgem­ein­gül­tig­keit: φ allgem­ein­gültig gdw. ¬φ nicht erfüllbar.
Beob­achtung 2.8 Die Folger­ung­sbe­ziehung lässt sich auf Erfüll­barkeit reduzi­eren: Φ |= ψ gdw. Φ ∪ {¬ψ} unerfü­llbar ist.

Funkti­onale Vollst­änd­igkeit

Satz 3.2 Zu jeder Funktion f ∈ Bn gibt es φ ∈ ALn mit f =fφ.
Man prüft durch Fallun­ter­sch­eidung
to do

KNF und DNF

Satz 3.7 Zu jeder Formel φ ∈ ALn gibt es äquiva­lente Formeln φ1 ∈ALn in KNF und φ2 ∈ALn in DNF.

Help Us Go Positive!

We offset our carbon usage with Ecologi. Click the link below to help us!

We offset our carbon footprint via Ecologi
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          More Cheat Sheets by tiziano123