Aussagenlogik

Aussagenlogik / Propositional-Logik

Proposition = Aussage

Wahrheitswerte wahr / falsch

Aussagenvariablen können wahr / falsch sein

Junktoren elementare Operatoren (Siehe unten)

Quantoren keine

Operationen

Sind Funktionen und beschreiben Operatoren-Symbole auf semantischer Ebene.

$\neg$ Negation

$\wedge$ Konjunktion

$\vee$ Disjunktion

$\not\equiv, \not\Leftrightarrow$ Antivalenz, XOR

$\equiv, \Leftrightarrow$ Äquivalenz, $\neg$ XOR, iff

Beispiel:

Immer wenn du hüpfst, dann hüpfe ich auch. Sonst nicht .

$\supset, \Rightarrow$ Implikation

Beispiel:

Immer wenn du hüpfst, dann hüpfe ich auch. Sonst vielleicht aber auch.

Beispiel:

Wenn / Falls ich ins Kino gehe, dann esse ich dort immer Popkorn.

(Gleiche Aussage wie) Ich gehe nur dann ins Kino, wenn ich dort Popkorn esse.

Das liegt daran, dass ich nicht im Kino sein kann ohne Popkorn zu essen.

$\uparrow$ Negierte Konjunktion, nand

$\downarrow$ Negierte Disjunktion, nor

Funktionale Vollständigkeit

Eine Menge von Funktionen mit denen alle Funktionen (einer Funktions-Klasse) ausgedrückt werden können.

Beispiele:

{not, and}, {nand}, {nor}, {not, or}, {not, implies}, {implies, false}

Induktive Definition

Allgemeiner Vorgang zur induktiven Definition unendlicher Mengen:

$\mathcal{U}$ Universum, Menge aller relevanten Elemente

$\mathcal{M}_{0} \subseteq \mathcal{U}$ Menge von Grundelementen

$f_{1}: \mathcal{U}^{n_{1}} \mapsto \mathcal{U}, ~~f_{2}: \mathcal{U}^{n_{2}} \mapsto \mathcal{U}$ Konstruktionsfunktionen

Stufenweise Konstruktion der Menge $\mathcal{M}$
$\begin{aligned}\mathcal{M}_{i+1}=\mathcal{M}_{i} \cup &\left\{f_{1}\left(x_{1}, \ldots, x_{n_{1}}\right) \mid x_{1}, \ldots, x_{n_{1}} \in \mathcal{M}_{i}\right\} \\& \cup\left\{f_{2}\left(x_{1}, \ldots, x_{n_{2}}\right) \mid x_{1}, \ldots, x_{n_{2}} \in \mathcal{M}_{i}\right\} \\& \cup \cdots\end{aligned}$
$\mathcal{M}=\lim _{i \rightarrow \infty} \mathcal{M}_{i}=\bigcup_{i \geq 0} \mathcal{M}_{i}$

Induktive Definition der Menge $\mathcal{M}$
$\mathcal{M}$ ist die kleinste Menge für die gilt:
- $\mathcal{M}_{0} \subseteq \mathcal{M}$
- Wenn $x_{1}, \ldots, x_{n_{1}} \in \mathcal{M}$ , dann $f_{1}\left(x_{1}, \ldots, x_{n_{1}}\right) \in \mathcal{M}$
- Wenn $x_{1}, \ldots, x_{n_{1}} \in \mathcal{M}$ , dann $f_{2}\left(x_{1}, \ldots, x_{n_{1}}\right) \in \mathcal{M}$
- $\dots$

Beispiele:

Menge der geraden Zahlen unter $\N$
1. Stufenweise Konstruktion (Konstruktiv)
  - $0$ ist eine gerade Zahl: $G_0 = \{0\}$
  - $G_1 = G_0 \cup \{ n + 2 \space| \space n \in G_0 \} = \{0,2\}$
  - $G_{i+1} = G_i \cup \{ n + 2 \space| \space n \in G_i \} = \{0,2,4,...,2(i+1)\}$
  - $\mathbb{G} =lim_{i \rarr \infin} G_i = \bigcup_{i\geq0}G_i$
1. Induktive Konstruktion (Nicht konstruktiv - greift auf bestehende Menge $\mathbb{G}$ zurück)
  $\mathbb{G}$ ist die kleinste Menge für die gilt:
  - $0 \in \mathbb{G}$
  - Wenn $n \in \mathbb{G}$ dann auch $n+2 \in \mathbb{G}$

Geschachtelte Klammern
Gesucht: Menge der syntaktisch richtigen Folgen von runden, eckigen, geschwungenen Klammern. wie zb [{()}] .
Induktive Definition
$\mathcal{K}$ ist die kleinste Menge der Klammerfolgen für die gilt:
1. $\{ \texttt{(), [], \{\}}\} \sube \mathcal{K}$
1. Wenn $x \in \mathcal{K}$ , dann auch $(x) \in \mathcal{K}$
1. Wenn $x \in \mathcal{K}$ , dann auch $[x] \in \mathcal{K}$
1. Wenn $x \in \mathcal{K}$ , dann auch $\{x\} \in \mathcal{K}$
Um zu beweisen dass [{()}] $\in \mathcal{K}$
$\begin{array}{l} () \in \mathcal{K}\end{array}\\\begin{array}{ll}\text { Da }() \in \mathcal{K}, \text { gilt auch }\{()\} \in \mathcal{K} . \quad \text { wegen }(k 4) \\\text { Da }\{()\} \in \mathcal{K}, \text { gilt auch }[\{()\}] \in \mathcal{K} . \quad \mathrm{wegen} (k3)\\\text { Da }[\{()\}] \in \mathcal{K}, \text { gilt auch }[[\{()\}]] \in \mathcal{K} . \quad \text { wegen }(k 3)\\\text { Da }[[\{()\}]] \in \mathcal{K}, \text { gilt auch }([[\{()\}]]) \in \mathcal{K} . \quad \text { wegen }(k 2)\end{array}$

Induktive Definition der Syntax in der Aussagenlogik

$\mathcal{U}$ Menge aller Zeichenketten (aus Variablen, Operatoren, Klammern)

$\mathcal{V} := \{A, B, C, ... A_0, A_1, ..., \top, \bot\}$ Aussagenlogische Variablen als Grundelemente

Konstruktionsfunktionen:

$\begin{array}{l}f_{\neg}(F)= \neg F \\f_{\wedge}(F, G)= \left(F \wedge G_{n}\right) \\f_{\uparrow}(F, G)=\left( F_{n} \uparrow G_{n}\right) \\\vdots \\f_{\subset}(F, G)=\left( F \subset G_{n}\right)\end{array}$

Induktive Definition der Menge $\mathcal{A}$

Die Menge $\mathcal{A}$ der aussagenlogischen Formeln $\textsf{F}_i$ ist die kleinste für die gilt:

$\mathcal{V} \sube \mathcal{A}$ (eine Variable ist eine gültige Formel)

$\{\top, \bot\} \sube \mathcal{A}$

Wenn $\textsf{F} \in \mathcal{A}$ dann auch $\neg \textsf{F} \in \mathcal{A}$

Wenn $\textsf{F,G} \in \mathcal{A}$ dann auch $(\textsf{F} *\textsf{G}) \in \mathcal{A}$
wobei $*:=\{\wedge, \vee, \uparrow, \downarrow, \equiv, \not\equiv, \sub, \supset\}$

Semantik

Die Semantik ist eine Funktion die Zeichenkette $\mapsto$ Bedeutung.

$I: \mathcal{V} \mapsto \mathbb{B}$ Wahrheitsbelegung / Interpretation (für einzelne Variablen )

Mit Wahrheitswerten $\mathbb{B} = \{1,0\}$

$\mathcal{I}=\{I \mid I: \mathcal{V} \mapsto \mathbb{B}\}$ Menge aller Interpretationen

Semantik von Formeln (Auswertung)

Wahrheits-Wert einer Formel mit der Belegung / Interpretation $I$ festgelegt durch die Funktion:

$\textsf{val: } \mathcal{I} \times \mathcal{A} \mapsto \mathbb{B}$

$\textsf{val}(I, A) = \textsf{val}_I(A)$

Für jede Operation auf der syntaktischen Ebene gibt es auch eine auf der semantischen Ebene (Metaebene):

$\begin{aligned} &\operatorname{val}_{I}(A)=I(A) \text { für } A \in \mathcal{V}\\ &\operatorname{val}_{I}(\top)=1 \text { und val }_{I}(\perp)=0 \text { ; }\\ &\operatorname{val}_{I}(\neg F)=\operatorname{not} \operatorname{val}_{I}(F)\\ &\operatorname{val}_{I}((F * G))=\operatorname{val}_{I}(F) \circledast \operatorname{val}_{I}(G)\\ \end{aligned}$

wobei $\circledast$ die logische Funktion zum Operator $*$ ist.

Beispiele

Beispiele für $\circledast$ : Ausdrücken von Semantik in der Aussagenlogik. (Alles darunter bezieht sich nur auf Aussagenlogik).

Semantische Äquivalenz

Semantik $=$ ist durch $\equiv$ ausdrückbar.

$F = G$ sind semantisch äquivalent wenn $\textsf{val}_I(F) = \textsf{val}_I(G)$ gültig ist.

Logische Konsequenz

Die Semantik $\models$ ist durch $\supset$ ausdrückbar

$F_{1}, \ldots, F_{n} \models, G$ genau dann wenn $F_{1} \supset\left(F_{2} \supset \cdots\left(F_{n} \supset G\right) \cdots\right)$

Und weil $A \supset(B \supset C)=(A \wedge B) \supset C$ folgt daraus die äquivalenz mit $(F_1 \wedge ... \wedge F_n) \supset G$ .

Anwendungen:

"Falls in der Wahrheitsbelegung $I$ alle Prämissen wahr sind, dann ist auch die Konklusion wahr in $I$ ." (Kriterium für die Gültigkeit von Inferenzregeln)

"Die Formel $G$ ist eine logische Konsequenz der Formeln $F_1,...,F_n$ "

$\models F$ ist eine Abkürzug dafür, dass $F$ gültig ist. Man muss es quasi als $\text{true} \models F$ lesen.

Eigenschaften von Formeln

gültig wenn für alle Wahrheitsb. immer $\textsf{val}_I(F) = 1$

Immer wahr

erfüllbar wenn für mindestens eine Wahrheitsb. $\textsf{val}_I(F) = 1$

Mind. bei 1 Fall wahr

widerlegbar wenn für mindestens eine Wahrheitsb. $\textsf{val}_I(F) = 0$

Mind. bei 1 Fall falsch

unerfüllbar wenn für alle Wahrheitsb. immer $\textsf{val}_I(F) = 0$

Immer falsch

Bool'sche Algebra

In der boolschen Algebra gelten die Eigenschaften: Assoziativität, Kommutativität, Idempotenz,...

Beispiele für boolsche Algebra:

$\langle\mathbb{B}, \text { and, or}, \text { not, } 0,1\rangle$

$\left\langle 2^{M}, \cap, \cup,^{-}, \emptyset, M\right\rangle$ ( $2^M$ steht für alle möglichen Mengen)

DNF / KNF

Manche meinen mit DNF / KNF die maximale Form bei der alle Variablen von der Funktion vorkommen müssen - in dieser LVA ist nicht diese gemeint.

Anwendung

Von der Funktion $f$ zur dazugehörigen Formel.

Defintion

$\vec{b}=\left(b_{1}, \ldots, b_{n}\right) \in \mathbb{B}^{n}$ sind Tupel mit bool'schen Werten.

Wir haben eine Funktion $f:\mathbb{B}^n \mapsto \mathbb{B}$ mit Argumenten $A_i$ die durch Interpretation $I_{\vec{b}} (A_i) = b_i$ belegt werden.

Also $f(A_i) = b \in \mathbb B$

Konjunkte / Disjunkte einer Menge von Variablen:

$\bigwedge\{F, G, H, \ldots\}=F \wedge G \wedge H \wedge \cdots$

$\\\bigvee \{F, G, H, \ldots\}=F \vee G \vee H \vee \cdots$

Wobei $\bigwedge\{\}=\top$ und $\bigvee\{\}=\perp$

DNF: Disjunktionen von Konjunktionen von Literalen (= Variablen oder ihre negierte Form)

Charakteristisches Konjunkt für $\vec{b}=\left(b_{1}, \ldots, b_{n}\right) \in \mathbb{B}^{n}$ :

$K_{\vec{b}}=\bigwedge\left\{\textcolor{pink}{A_{i}} \mid b_{i}=\textcolor{pink}1,~ i=1 . . n\right\} \wedge \bigwedge\left\{\textcolor{pink}{\neg A_{i}} \mid b_{i}=\textcolor{pink}0,~i=1 . . n\right\}$

Wobei $A_i$ die Variablen sind die als Argumente der Funktion dienen.

Beispiel:

$I_{\vec{b}}: A_{1} \mapsto 1, A_{2} \mapsto 0, A_{3} \mapsto 1, A_{4} \mapsto 1 \quad \Longrightarrow \quad \operatorname{val}_{I_{\bar{b}}}\left(K_{\vec{b}}\right)=1$

$\vec{b}=(1,0,1,1) \quad \Longrightarrow \quad K_{\vec{b}}=A_{1} \wedge \neg A_{2} \wedge A_{3} \wedge A_{4}$

Für Wahrheitsbelegung $I_b$ hat $K_{\vec{b}}$ den Wert $1$ und sonst $0$ .

Die Konjunkte werden disjunktiv verbunden.

$\operatorname{DNF}_{f}=\bigvee\left\{K_{\vec{b}} \mid f(\vec{b})=1, \vec{b} \in \mathbb{B}^{n}\right\}$

Dadurch repräsentiert die DNF die Funktion f.

$\forall \vec{b} \in \mathbb{B}^{n}: \text{val}_{\vec{b}}\left(\mathrm{DNF}_{f}\right)=f(\vec{b})$

DNF: Konjunktionen von Disjunktionen von Literalen

Charakteristisches Disjunkt für $\vec{b}=\left(b_{1}, \ldots, b_{n}\right) \in \mathbb{B}^{n}$ :

$D_{\vec{b}}=\bigvee \left\{\textcolor{pink}{A_{i}} \mid b_{i}=\textcolor{pink}0,~ i=1 . . n\right\} \vee \bigvee \left\{\textcolor{pink}{\neg A_{i}} \mid b_{i}=\textcolor{pink}1,~ i=1 . . n\right\}$

Wobei $A_i$ die Variablen sind die als Argumente der Funktion dienen.

Beispiel:

$I_{\vec{b}}: A_{1} \mapsto 1, A_{2} \mapsto 0, A_{3} \mapsto 1, A_{4} \mapsto 1 \quad \Longrightarrow \quad \operatorname{val}_{I_{\bar{b}}}\left(D_{\vec{b}}\right)=0$

$\vec{b}=(1,0,1,1) \quad \Longrightarrow \quad D_{\vec{b}}=\neg A_{1} \vee A_{2} \vee \neg A_{3} \vee \neg A_{4}$

Für Wahrheitsbelegung $I_b$ hat $D_{\vec{b}}$ den Wert $0$ und sonst $1$ .

Die Konjunkte werden disjunktiv verbunden.

$\operatorname{KNF}_{f}=\bigwedge\left\{D_{\vec{b}} \mid f(\vec{b})=0, \vec{b} \in \mathbb{B}^{n}\right\}$

Dadurch repräsentiert die DNF die Funktion f.

$\forall \vec{b} \in \mathbb{B}^{n}: \text{val}_{\vec{b}}\left(\mathrm{KNF}_{f}\right)=f(\vec{b})$

Laufzeiten

von einer beliebigen Formel zu DNF / KNF kommen:

Beide exponentielle obere Schranke für Laufzeit

Semantische Methode (Siehe oben) -übersichtlicher, einfacher, aberimmerexponentielle Laufzeit $2^{Anz. Variablen}$ weil für jedes element von $\vec{b}$ ein Konj. / Disjunkt gebildet werden muss.

Algebraische Methode (Algebraisch umformen / kürzen bis man erwünschte Form erreicht) - durchschnittlich effizienter, aber obere Schranke wie semantische Methode

Normalformen

Formeln unter gewissen Einschränkungen. - An der Semantik ändert sich nichts.

Normalformen sind meistens nicht eindeutig.

Beispiele

Disjunktive Normalform DNF

Konjunktive Normalform KNF

Negations Normalform NNF
(DNF, KNF sind auch gültige NNF)
kleinstmögliche Menge für die gilt:
1. $(F \vee G)$ und $(F \wedge G)$ sind in der Menge wenn $\{F, G\} \in$ NNF.
2. Literale (= negierte / nicht negierte Variablen) sowie $\top$ , $\bot$ sind NNF

Andere Einschränkungen auch möglich für Normalformen, zb nur Nand-Operator $\uparrow$ erlaubt. (Operator muss funktional vollständig sein)

SAT-Problem

P Problemklasse, die sich polynomiell lösen lässt.

NP Problemklasse, die sich polynomiell verifizieren lässt.

NP-vollständig Problemklasse, auf die sich alle NP-Probleme reduzieren lassen.

Erfüllbarkeitsproblem / Satisfiability / SAT (NP-vollständig)

Wir haben eine Formel $F$ und wollen wissen ob sie erfüllbar ist.

Wir wollen wissen ob $\exists\space I \in \mathcal{I}: \textsf{val}_I(F) = 1$

Aussagenlogische Frage übersetzt zu (Un)Erfüllbarkeitsproblem:

Ggu¨ltig⟺¬Gunerfu¨llbarGwiderlegbar⟺¬Gerfu¨llbarG=Hgu¨ltig⟺G≢Hunerfu¨llbarF1,…,Fn⊨G⟺F1∧⋯∧Fn∧¬Gunerfu¨llbar\begin{aligned}G \text { gültig } & \Longleftrightarrow \neg G \text { unerfüllbar } \\G \text { widerlegbar } & \Longleftrightarrow \neg G\text { erfüllbar } \\G=H \space \text{gültig} & \Longleftrightarrow G \not \equiv H \text { unerfüllbar } \\F_{1}, \ldots, F_{n} \models G & \Longleftrightarrow F_{1} \wedge \cdots \wedge F_{n} \wedge \neg G \text { unerfüllbar }\end{aligned}Ggu¨ltigGwiderlegbarG=Hgu¨ltigF1,…,Fn⊨G⟺¬Gunerfu¨llbar⟺¬Gerfu¨llbar⟺G≡Hunerfu¨llbar⟺F1∧⋯∧Fn∧¬Gunerfu¨llbar

SAT lösen:

Wahrheitstafel (ineffizient)

DNF (ineffizient, Probleme meistens fast in KNF Form)

SAT-Solver

SAT-Solver

Mögliche Resultate:

a) "SAT" $\exists\space I \in \mathcal{I}: \textsf{val}_I(F) = 1$ (Formel ist erfüllbar)

b) "UNSAT" $\not\exists\space I \in \mathcal{I}: \textsf{val}_I(F) = 1$ (Formel ist unerfüllbar)

SAT Solver Beispiel

Dualität

Dualität ≠ Negation

Duale Funktionen

Zwei n-stellige Funktionen $f$ und $g$ heißen dual zueinander, wenn gilt:

$\operatorname{not} f\left(x_{1}, \ldots, x_{n}\right)=g\left(\operatorname{not} x_{1}, \ldots, \operatorname{not} x_{n}\right)$

Beispiel: and und or bei gespiegelten Wahrheitsbelegungen

DeMorgan Gesetz: not(x and y) = (not x) or (not y)

$\begin{array}{cc|cc}x & y & x \text { and } y & x \text { or } y \\\hline 1 & 1 & 1 & 1 \\1 & 0 & 0 & 1 \\0 & 1 & 0 & 1 \\0 & 0 & 0 & 0\end{array}$

$\begin{array}{cc|cc}x & y & x \text { or } y & x \text { and } y \\\hline 0 & 0 & 0 & 0 \\0 & 1 & 1 & 0 \\1 & 0 & 1 & 0 \\1 & 1 & 1 & 1\end{array}$

Duale Operatoren

Operatoren (semantisch) sind dual wenn ihre Funktionen dual sind.

Duale Formeln

Formel $F\left[A_{1}, \ldots, A_{n}\right]$ und $G\left[A_{1}, \ldots, A_{n}\right]$ sind dual zu einander wenn gilt:

$\neg F\left[A_{1}, \ldots, A_{n}\right]=G\left[\neg A_{1}, \ldots, \neg A_{n}\right]$

Quasi wenn überall in der Formel die Operatoren mit ihrem Dual ausgetauscht werden - aber eine Formel kann zu mehreren anderen dual sein.

Beispiel:

$\neg(((A \wedge B) \not \equiv \neg(B \uparrow C)) \not \supset((A \wedge \top) \vee B))$ ist dual zu

$\neg(((A \vee B) \equiv \neg(B \downarrow C)) \subset((A \vee \perp) \wedge B))$

Aussagenlogische Modellierung

deklarativ-statisch, nicht prozedural-dynamisch

$+$ deklarativ (man sagt welchen Zustand man sich unter welchen Bedingungen wünscht)

$+$ modular

$-$ Erraten von Parametern oft notwendig (siehe Simpsons bsp)

$-$ Große Zahl an Variablen und Formeln

$-$ Frame Problem: Bei jeder Aktion muss auch definiert werden, was sich nicht ändert.

$-$ unintuitiv - menschen denken bei Modellieren nicht an statischen Bedingungen

Beispiele