Transcript
Seminar: Logik und Komplexität von: Thomas Zeume
1 Logiken 1.1 Aussagenlogik
Problem:
p−W SAT (Φ)
(Gewichtetes, parametrisiertes Erfüllbarkeitsproblem zur Klasse Φ).
Gegeben ϕ ∈ Φ und k ∈ N. Parameter sei k. Ist φ k-erfüllbar? D.h. gibt es eine erfüllende Belegung in der k Variablen wahr sind?
De nition.
P ROP := {ϕ | ϕ ist aussagenlogische Formel }
De nition (Eine Hierarchie von Formeln der Aussagenlogik). Γ0,d := {λ1 ∧ . . . ∧ λc | c ∈ [d], λ1 , . . . , λc Literale }, ∆0,d := {λ1 ∨ . . . ∨ λc | c ∈ [d], λ1 , . . . , λc Literale } V Γt+1,d := { i∈[d] δi | d ∈ N und δi ∈ ∆t,d für alle i ∈ [d]} W ∆t+1,d := { i∈[d] δi | d ∈ N und δi ∈ Γt,d für alle i ∈ [d]}
Lemma.
p−W SAT (Γ1,1 ) ≤f pt
≤f pt p−W SAT (Γ2,1 ) ≤f pt p−W SAT (Γ3,1 )
p−W SAT (Γ1,2 ) . . .
≤f pt p−W SAT (P ROP ) ≤f pt p−W SAT (CIRC)
1.2 Prädikatenlogik
De nition (Struktur). Sei τ Menge von Relationssymbolen R, jedes mit festgelegter Stelligkeit s(R). Eine
τ -Struktur A besteht aus einem Universum A und einer Interpretation, die jedem Relationssymbol R in τ eine Relation RA ⊆ As(R) zuordnet. Hier: Nur endliche Universen und Mengen von Relationssymbolen.
De nition (Semantik). Bestimme induktiv erfüllende Tupel ϕ(A) über dem Universum. Beispielsweise • Falls ϕ(x, y) = Rxy , dann ϕ(A) := {(ax , ay ) ∈ A2 | (ax , ay ) ∈ RA } • Falls ϕ(x, y) = φ(x, y) ∧ ψ(x, y), dann ϕ(A) := {(ax , ay ) ∈ A2 | (ax , ay ) ∈ φ(A) und (ax , ay ) ∈ ψ(A)} • Falls ϕ(x) = ∃yφ(x, y), dann ϕ(A) := {(ax )| es gibt ein ay ∈ A mit (ax , ay ) ∈ φ(A)}
Notation: A |= ϕ(a1 , a2 ) anstelle (a1 , a2 ) ∈ ϕ(A)
Beispiel. (a) Graph-Struktur. Die Symbolmenge τgraph bestehe aus dem binären Relationssymbol E . De niere τgraph -Struktur G = (G, E G ), wobei G die Menge der Knoten und E G ⊆ G2 die Menge der Kanten ist.
(b) Logische Charakterisierung von V ERT EX − COV ER: vc0k (x1 , . . . , xk ) := ∀y∀z Eyz →
_
(xi = y ∨ xi = z)
i∈[k]
vck := ∃x1 . . . ∃xk
^
xi 6= xj ∧ vc0k (x1 , . . . , xk )
1≤i
