Show Menu
Cheatography
  1. Home >
  2. Cheat Sheets >

AL sätze Cheat Sheet (DRAFT) by

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Funkti­onale Vollst­änd­igkeit

Man prüft durch Fallun­ter­sch­eidung
Satz 3.2 Zu jeder Funktion f ∈Bn gibt es φ∈ALn mit f =fφ. Damit wissen wir nun auch: φ → fφ liefert eine bijektive Korres­pondenz zwischen den Äquiva­len­zkl­assen von ALn-Fo­rmeln bezüglich ≡ und den n-stel­ligen Booleschen Funkti­onen.

Vollst­ändige Systeme von Junktoren

Für n >= 1 lassen sich alle Booleschen Funktionen in Bn durch ALn-Fo­rmeln darste­llen, die nur die Aussag­env­ari­ablen in Vn und die logischen Junktoren ∧ und ¬ benutzen. (Genauso auch mit ∨ und ¬.) Grund: Man kann ∨ oder aber ∧ durch Dualität elimin­ieren (und 0 ≡ p1 ∧ ¬p1 sowie 1 ≡ p1 ∨ ¬p1 benutzen). Ein solches System von Junktoren (oder zugehö­rigen Booleschen Funkti­onen) heißt vollst­ändig

Quiz AL

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
Die Formel­menge {p,p→q,¬q}
ist erfül­lbar. Falsch
Wenn jede Formel einer Formel­menge Φ ⊆ AL erfüllbar ist, dann ist auch Φ erfül­lbar. Falsch
Für jede Formel­menge Φ⊆AL giltΦ|=⊤. Wahr
TO DO H2G lösen
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. Φ ⊢ allgem­ein­gültig ist V. Φ ist unerfu­̈llbar gdw. Φ
0
⊢ allgem­ein­gültig ist für ein endliches Φ
0
⊆ Φ
ZU RESOLUTION AL Sei K = {{p}} und C = {p,q}. Dann gilt K |= C, allerdings nicht C ∈ Res∗(K) = K. Stattd­essen gilt K |= genau dann, wenn ∈ Res∗(K) für alle Klause­lmengen K.
ZU RESOLUTION AL Seien C1 = {p,q}, C2 = {¬p,r} Klauseln und C = {q,r} eine Resolvente von C1 und C2. Dann gilt {C} ≡ {C1,C2} nicht. Stattd­essen gilt {C1,C2,C} ≡ {C1,C2} für alle Resolv­enten C zweier beliebiger Klauseln C1 und C2.
ZU RESOLUTION AL K = {{p,q}} ist eine erfül­lbare Klause­lmenge ohne eindeutige minimale erfül­lende Belegung, weil sowohl {p → 1,q → 0} |= K als auch {p → 0,q → 1} |= K gilt. Stattd­essen besitzt jede erfül­lbare Hornkl­aus­elmenge eine eindeutige minimale erfül­lende Belegung
 

Logische Äquivalenz

Definition 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 φ, ψ ∈ AL
n
gilt demnach:φ ≡ ψ gdw. für alle (b
1
,...,b
n
) ∈ Bn ist φ[b
1
,...,b
n
] =
ψ[b
1
,...,b
n
].
Logische Äquivalenz lässt sich durch Wahrhe­its­tafeln nachwe­isen.
Formeln mit derselben Semantik heißen logisch äquivalent

Erfüll­barkeit (AL)

Definition 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 φ ∈ Φ.
Beobac­htung 2.7 Erfüll­barkeit ist dual zur Allgem­ein­gül­tig­keit: φ allgem­ein­gültig gdw. ¬φ nicht erfüllbar.
Beobac­htung 2.8 Die Folger­ung­sbe­ziehung lässt sich auf Erfüll­barkeit reduzi­eren: Φ |= ψ gdw. Φ ∪ {¬ψ} unerfü­llbar ist.
Hü und altkla­usuren hier rein 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.

Allgem­ein­gül­tigkeit

Definition 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

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. fu ̈r alle V-Inte­rpr­eta­tionen I gilt: I |= φ ⇒ I |= ψ. 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 ψ |= (ψ ∧ φ) ∨ (ψ ∧ ¬φ).
 

Kompak­the­itssatz (AL)

Satz 4.1 Sei V = {p
i
: 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 |= ψ.

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).