Definitionen_Glossary

• 3-Färbbarkeit: Ein Graph $G$ ist 3-färbbar, wenn es eine Funktion $c:V(G)\to \{C_1,C_2,C_3\}$ gibt, so dass $c(u)\ne c(v)$ für alle Kanten $\{u,v\}\in E(G)$.
• 3-COL Problem: Das Entscheidungsproblem, ob ein gegebener Graph $G$ 3-färbbar ist. Dieses Problem ist NP-vollständig.

Dies sind grundlegende Entscheidungsprobleme, die sich auf logische Formeln beziehen:

• Auswertungsproblem: Gegeben eine Formel $\varphi$ und eine Belegung $\beta$, ist $\varphi$ unter $\beta$ wahr?
• Erfüllbarkeitsproblem (SAT): Gegeben eine Formel $\varphi$, gibt es eine Belegung, die $\varphi$ wahr macht?
• Äquivalenzproblem: Gegeben zwei Formeln $\varphi$ und $\psi$, sind sie unter allen Belegungen äquivalent?
• Allgemeingültigkeitsproblem: Gegeben eine Formel $\varphi$, ist sie unter allen Belegungen wahr?

${\mathrm{\Sigma }}_{AL}:=\text{AVar}\cup \{\mathrm{\top },\mathrm{\perp },\mathrm{\neg },\vee ,\wedge ,\to ,\leftrightarrow ,(,)\}$

Ein Argument hat zwei Ebenen:

1. Inhaltlich: die tatsächliche inhaltliche Korrektheit.
2. Abstrakt: die strukturelle, formale Korrektheit, unabhängig von der tatsächlichen inhaltlichen Korrektheit.

Fixierung einer abzählbaren unendlichen Menge $AVar$ von Aussagenvariablen, die $V_i$ für alle $i\ge 0$ enthält.

Eine Formel $\phi \in AL$ ist in disjunktiver Normalform (DNF), wenn sie eine Disjunktion von Konjunktionen von Literalen ist.
Gestalt: $$\bigvee_{i=1}^{n} \left( \bigwedge_{j=1}^{n_i} L_{i,j} \right)$$
$L_{i,j}:$ Literal

Lemma (Distributivität). Für alle $\varphi ,\psi ,\vartheta \in AL$ gilt

• Formeln: Wörter in einer formalen Sprache, die syntaktisch genau definiert sind. Damit kann man Aussagen präzise formulieren.
• Semantikfunktion: Die Semantik legt fest, ob eine Formel für ein bestimmtes Element der Umgebung gilt.
• Die Umgebung (engl. domain): Der Kontext oder die "Welt", in der die Formeln interpretiert werden.

Zu einer gegebenen Formel kann man verschiedene Belegungen betrachten, die auch zu unterschiedlichen Wahrheitswerten für diese Formel führen können. Jede Formel kann eine der drei Eigenschaften haben:

• Erfüllbarkeit: Es existiert eine passende Belegung, die die Formel erfüllt (wahr macht).
• Unerfüllbarkeit: Es existiert keine passende Belegung, die die Formel erfüllt.
• Allgemeingültigkeit (Tautologie): Jede passende Belegung erfüllt die Formel.

Eine Formel $\phi$ ist erfüllbar, wenn es mindestens eine Belegung $\beta$ gibt mit $\beta \models \phi$.
Sie ist unerfüllbar, wenn keine solche Belegung existiert.

Äquivalente Sicht

• $\phi$ ist erfüllbar $⟺$ $\mathrm{\neg }\phi$ ist nicht allgemeingültig (keine Tautologie).
• Zusammenhang zu Modell: Erfüllbarkeit bedeutet „es existiert ein Modell“.

Beispiele

• $X\vee \mathrm{\neg }X$ ist erfüllbar (sogar allgemeingültig).
• $X\wedge \mathrm{\neg }X$ ist unerfüllbar.

Dieses Lemma ist noch mächtiger. Es erlaubt, Teile einer Formel durch äquivalente Teile zu ersetzen.

Sei $\varphi \in AL$ eine Formel und $\psi$ eine Unterformel von $\varphi$.
Sei ${\varphi }^{\prime }$ die Formel, die man aus $\varphi$ erhält, indem man ein Vorkommen der Unterformel $\psi$ durch eine äquivalente Formel ${\psi }^{\prime }\equiv \psi$ ersetzt.

Dann gilt:

Beispielanwendung:
Wir können die Implikation umschreiben:

• Es können beliebige Aussagenlogiken definiert werden.
• Exklusives Oder intuitiv: $(\phi \oplus \psi )$ bedeutet "entweder $\phi$ oder $\psi$".

1. Eine Formel $\psi$ folgt aus einer Formel $\varphi$, geschrieben $\varphi \models \psi$, wenn für jede zu $\varphi$ und $\psi$ passende Belegung $\beta$ gilt:
   Wenn $\beta \models \varphi$, dann auch $\beta \models \psi$.

2. Sei $\mathrm{\Phi }\subseteq AL$ eine Formelmenge und $\psi \in AL$ eine Formel.
   $\psi$ folgt aus $\mathrm{\Phi }$, wenn jede zu $\mathrm{\Phi }\cup \{\psi \}$ passende Belegung $\beta$, die $\mathrm{\Phi }$ erfüllt, auch $\psi$ erfüllt. Wir schreiben $\mathrm{\Phi }\models \psi$.

Beispiele.

1. $\{(X\wedge Y)\}\models (X\vee Y)$?
2. $\{X,Y\}\models (X\vee Y)$?
3. $\{X\}⊭(X\wedge Y)$?

Erinnerung. Die folgende Notation ist oft nützlich:

Beispiel. $\underset{i=1}{\overset{999}{\bigwedge }}{X}_i\to Y$
„Wenn alle 999 $X_i$ wahr sind, so muss auch $Y$ wahr sein.“

Rechtfertigung. Wegen der Assoziativitätsregeln

ändert die Klammerung den Wahrheitswert nicht.

• Basis
  • $\mathrm{\top },\mathrm{\perp }$ sind aussagenlogische Formeln.
  • Jede Variable $X\in \text{AVar}$ ist eine aussagenlogische Formel.
  • $\mathrm{\top },\mathrm{\perp }$ und die Variablen werden atomare Formeln oder Atome genannt.
• Induktionsschritt (Regeln)- Wenn $\phi \in \text{AL}$ eine Formel ist, dann ist auch $\mathrm{\neg }\phi \in \text{AL}$.
  • Wenn $\phi ,\psi \in \text{AL}$ Formeln sind, dann sind auch $(\phi \vee \psi ),(\phi \wedge \psi ),(\phi \to \psi ),(\phi \leftrightarrow \psi )$ Formeln.
  • $\mathrm{\neg },\vee ,\wedge ,\to ,\leftrightarrow$ werden aussagenlogische Verknüpfungen genannt.

Wir definieren eine Basismenge $S_0\subseteq U$ und Regeln
$R_i:U^{k_i}\to \mathcal{P}(U)$ für $0\le i\le n$,
wobei $n,k_0,\dots ,k_n\in \mathbb{N}$.

$U$: Universum (Alle denkbaren Objekte)
$S_0\subseteq U$: Basismenge
Regeln: $R_i:U^k\to P(U)$ für $0\le i\le n$ mit $n\in \mathbb{N}$
Eine Regel könnte sein: $R(a,b)=\{f(a,b)\}$

Dadurch wird eine eindeutige Menge $M$ definiert als kleinste
(bezüglich $\subseteq$) Teilmenge von $U$, die alle Elemente aus $S_0$ enthält und falls
$m_0,\dots ,m_{k_i}\in M$ gilt, auch jedes Element aus
$R_i(m_0,\dots ,m_{k_i})$ enthält für $0\le i\le n$.

Eine Klausel ist eine endliche Menge von Literalen. Sie repräsentiert die Disjunktion (ODER-Verknüpfung) dieser Literale. Die leere Klausel $\square$ (oder {}) ist die leere Menge und repräsentiert einen Widerspruch (ist immer falsch).

Eine Klauselmenge ist eine Menge von Klauseln. Sie repräsentiert die Konjunktion (UND-Verknüpfung) dieser Klauseln und ist damit eine alternative Schreibweise für eine Formel in KNF.

• Sei $\phi \in \text{AL}$ eine Formel und seien $\beta ,{\beta }^{\prime }$ Belegungenx, sodass $\beta (X)={\beta }^{\prime }(X)$ für alle $X\in \text{var}(\phi )$.
• Dann gilt $[[\phi ]{]}^{\beta }=[[\phi ]{]}^{{\beta }^{\prime }}$.

Eine Formel $\phi \in AL$ ist in konjunktiver Normalform (KNF), wenn sie eine Konjunktion von Disjunktionen von Literalen ist.
Gestalt: $$\bigwedge_{i=1}^{n} \left( \bigvee_{j=1}^{n_i} L_{i,j} \right)$$
$L_{i,j}:$ Literal

Die Korrektheit besagt, dass der Kalkül keine falschen Schlüsse zieht. Wenn aus einer Klauselmenge $C$ die leere Klausel abgeleitet werden kann ($C{⊢}_R◻$), dann ist die Klauselmenge $C$ auch tatsächlich unerfüllbar.

Ein Literal $L$ ist eine Aussagenvariable $X\in AVar$ oder deren Negation $\neg X$ . $$\bar{L} := \begin{cases} \neg X & \text{if } L = X \ X & \text{if } L = \neg X. \end{cases}$$

Eine (zu einer Formel passende) Belegung $\beta$ heißt Modell einer aussagenlogischen Formel $\phi$, wenn $[[\phi \parallel \phi ]{]}_{\beta }=1$ gilt.
Notation: $\beta \models \phi$.

Beispiel

• Sei $\phi :=(X\vee \mathrm{\neg }Y)\wedge Z$.
  Die Belegung $\beta (X)=0,\beta (Y)=0,\beta (Z)=1$ ist ein Modell von $\phi$, da
  $X\vee \mathrm{\neg }Y=0\vee 1=1$ und $1\wedge Z=1\wedge 1=1$.

Lemma (de Morgansche Regel). Für alle $\varphi ,\psi \in AL$ gilt:

Eine Formel $\phi \in AL$ ist in Negationsnormalform (NNF), wenn die Symbole $\to$ und $\leftrightarrow$ nicht vorkommen und die Negation $\neg$ nur direkt vor atomaren Formeln (Aussagenvariablen) auftritt.

• Unnötige Klammern können vermieden werden. Hier sind die Regeln:
  • Äußerste Klammern können weggelassen werden.
  • $\mathrm{\neg }$ bindet stärker als die anderen Verknüpfungen.
  • $\wedge ,\vee$ binden stärker als $\to ,\leftrightarrow$.
• Wenn $\mathrm{\Phi }=\{{\phi }_1,\dots ,{\phi }_n\}\subseteq AL$ eine endliche Menge von Formeln ist, schreiben wir:
  • $\bigvee \mathrm{\Phi }$ als Abkürzung für $({\phi }_1\vee \cdots \vee {\phi }_n)$, die Disjunktion über alle Formeln aus $\mathrm{\Phi }$.
  • $\bigwedge \mathrm{\Phi }$ als Abkürzung für $({\phi }_1\wedge \cdots \wedge {\phi }_n)$, die Konjunktion über alle Formeln aus $\mathrm{\Phi }$.
  • Alternative Schreibweise: $\underset{i=1}{\overset{n}{\bigwedge }}{\phi }_i,\underset{1\le i\le n}{\bigvee }{\phi }_i,\text{usw.}$

Eine Resolutionsableitung einer Klausel $C$ aus einer Klauselmenge $\mathrm{\Phi }$ ist eine endliche Folge von Klauseln $(C_1,\dots ,C_n)$, sodass $C_n=C$ und jede Klausel $C_i$ in der Folge entweder ein Element von $\mathrm{\Phi }$ ist oder eine Resolvente von zwei früheren Klauseln in der Folge ist ($C_i=\text{Res}(C_j,C_k)$ mit $j,k<i$).

Eine Resolutionswiderlegung einer Klauselmenge $\mathrm{\Phi }$ ist eine Resolutionsableitung der leeren Klausel $\square$ aus $\mathrm{\Phi }$. Sie ist ein formaler Beweis dafür, dass die Klauselmenge $\mathrm{\Phi }$ unerfüllbar ist.

Gegeben zwei Klauseln $C_1$ und $C_2$ und ein Literal $L$, für das gilt $L\in C_1$ und $\overline{L}\in C_2$, ist die Resolvente die neue Klausel, die durch die Vereinigung der beiden Klauseln ohne das komplementäre Literalpaar entsteht:

Eine Substitution ist eine partielle Abbildung $S:AVar\to AL$ mit endlichem Definitionsbereich.
$S$ ordnet also endlich vielen Variablen eine aussagenlogische Formel zu.

Beispiel: $S:\{V_1,V_2\}\to AL$ definiert durch

• $S(V_1):=V_2$
• $S(V_2):=(V_0\vee V_1)$

Dieses Lemma besagt, dass Äquivalenz unter Substitution erhalten bleibt. Es ist die Grundlage für viele logische Umformungen.

Sei $S$ eine Substitution und seien $\varphi ,{\varphi }^{\prime }\in AL$ Formeln.
Dann gilt: $$ \phi \equiv \phi' \implies \phi S \equiv \phi'S $$

Syntaxbäume sind Bäume mit Wurzel, dessen Blätter mit den Atomen der Formel beschriftet sind und dessen innere Knoten mit den Verknüpfungen der Formel beschriftet sind. Für jede aussagenlogische Formel ist der zugehörige Syntaxbaum eindeutig.

Beispiel: Für $((X\wedge Y)\leftrightarrow ((\mathrm{\neg }Z)\vee (\mathrm{\neg }Y)))$ ergibt sich der folgende Syntaxbaum: !handout1, p.12

Eine Formel $\phi$ ist allgemeingültig, wenn jede passende Belegung $\beta$ die Formel erfüllt, d.h. $\beta \models \phi$ für alle $\beta$.

Charakterisierung

• $\phi$ allgemeingültig $⟺$ $\mathrm{\neg }\phi$ unerfüllbar.
• Tritt auf als semantische Entsprechung zu „immer wahr“.

Beispiele

• $X\vee \mathrm{\neg }X$ ist allgemeingültig (Gesetz des ausgeschlossenen Dritten).
• $(X\wedge Y)\to X$ ist allgemeingültig.

Der Semantik liegt das Grundprinzip tertium non datur zugrunde: Eine Aussage ist entweder wahr oder falsch.

Die Menge $\text{sub}(\phi )$ der Unterformeln einer Formel $\phi$ ist die Menge aller Teilformeln von $\phi$, die selbst wieder korrekte Formeln der Aussagenlogik sind.

Beispiel:
Für $\phi :=((X\vee Y)\wedge \mathrm{\neg }(X\wedge (Y\to Z)))$ gilt:

Für jeden Knoten $u\in V(G)$ und jede Farbe $i\in \{1,2,3\}$ wird eine Variable $X_{u,i}$ eingeführt.

• Intention: $X_{u,i}$ ist wahr, wenn Knoten u mit Farbe $C_i$ gefärbt wird.

Für jede Position (Zeile $i$, Spalte $j$) und jede mögliche Zahl $c\in \{1,...,9\}$ wird eine Variable $X_{i,j}^c$ eingeführt.

• $X_{i,j}^c$ ist wahr, wenn an der Stelle ($i,j$) die Zahl $c$ steht.

Die Vollständigkeit besagt, dass der Kalkül stark genug ist, um alle unerfüllbaren Klauselmengen zu erkennen. Jede unerfüllbare Klauselmenge $C$ besitzt eine Resolutionswiderlegung ($C$ ist unerfüllbar $\Rightarrow C{⊢}_R◻$).

• Die Menge $\text{var}(\phi )$ der Variablen einer Formel $\phi$ ist die Menge $\text{var}(\phi ):=\text{AVar}\cap \text{sub}(\phi )$.
• Eine Wahrheitsbelegung, oder kurz Belegung, ist eine partielle Funktion $\beta :\text{AVar}\to \{0,1\}$.
• Eine Belegung $\beta$ ist eine Belegung für eine Formel $\phi$, oder ist passend für $\phi$, wenn $\text{var}(\phi )\subseteq \text{def}(\beta )$.

Per Induktion über die Struktur der Formeln in $AL$ definieren wir eine Funktion $[[\cdot ]{]}^{\beta }$, die jeder Formel $\phi \in AL$ und jeder zu $\phi$ passenden Belegung $\beta$ einen Wahrheitswert $[[\phi ]{]}^{\beta }\in \{0,1\}$ zuordnet.

Belegung: $\beta :AVar\to \{0,1\}$
passend für $\phi$: $\mathrm{var}(\phi )\subseteq \mathrm{def}(\beta )$

Induktionsbasis

• $[[\mathrm{\perp }]{]}^{\beta }:=0$
• $[[\mathrm{\top }]{]}^{\beta }:=1$
• Für alle $X\in AVar$: $[[X]{]}^{\beta }:=\beta (X)$

Induktionsschritt (wie man größere Formeln aus kleineren berechnet):

• $[[\mathrm{\neg }\phi ]{]}^{\beta }:=1-[[\phi ]{]}^{\beta }$
• $[[(\phi \wedge \psi )]{]}^{\beta }:=min\{[[\phi ]{]}^{\beta },[[\psi ]{]}^{\beta }\}$
• $[[(\phi \vee \psi )]{]}^{\beta }:=max\{[[\phi ]{]}^{\beta },[[\psi ]{]}^{\beta }\}$
• $$[[(\phi \to \psi )]{]}^{\beta }:=\{\begin{array}{ll}1& \text{wenn }[[\phi ]{]}^{\beta }=0\text{ oder }[[\psi ]{]}^{\beta }=1\\ 0& \text{sonst}\end{array}$$
• $[[(\phi \leftrightarrow \psi )]{]}^{\beta }=1⟺[[\phi ]{]}^{\beta }=[[\psi ]{]}^{\beta }$

Zwei Formeln $\phi ,\psi$ sind äquivalent (Notation: $\phi \equiv \psi$), wenn für alle Belegungen $\beta$ gilt:
$\beta \models \phi ⟺\beta \models \psi$.

• Reflexiv, symmetrisch, transitiv.
• Erlaubt ersetzendes Umformen in Beweisen und bei Normalformen.