Show Menu

Aussagenlogik Cheat Sheet by

abc

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.

Download the Aussagenlogik Cheat Sheet

1 Page
//media.cheatography.com/storage/thumb/tiziano123_aussagenlogik.750.jpg

PDF (recommended)

Alternative Downloads

Share This Cheat Sheet!

 

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