Aussagenlogischen Formel

Einfache Sprache

Bestandteile:

1. Symbole für booleschen Wert, also wahr und falsch -> $\top$ bzw. $\bot$
2. Symbole für Variablen, immer in Großschrift z.B: $X_0,X_1,Y,\ldots$
3. Junktoren

Obwohl als Zeichenketten (Zeichenkette) dargestellt stellt eine Formel formal eine Baum dar:

• Knoten sind Junktoren
• Blätter sind Variablen und Konstante

Def Aussagenlogische Variablen, Aussagenlogische Formeln)

Gegeben aussagenlogische Variable $X_i$ für $i \in \mathbb{N}_0$, die Menge aller aussagenlogischen Variablen $\mathbf{V}_{AL}$, die Boolescher Wert $\top$ und $\bot$, und die Menge der Junktoren $\mathcal C = \{\land, \lor, \rightarrow, \neg\}$.

Die Menge aller aussagenlogischen Formeln $\mathbf F_{AL}$ können wir nun mit Strukturelle Induktion definieren:

_Basiselemente.

• Die einknotigen Bäume, deren Wurzel mit $\top$ oder $\bot$ beschriftet sind, sind aussagenlogische Formeln.
• Die einknotigen Bäume, deren Wurzel mit einer aussagenlogischen Variable $X_i \in \mathbf V_{AL}$ beschriftet sind, sind aussagenlogische Formeln.

Diese Formeln nennen wir auch atomare Formeln.

Induktive Regel.

Ist $C\in \mathcal C$ ein $n$-stelliger Junktor für $n \in \mathbb N_{>0}$ und sind $\varphi_0, \ldots, \varphi_{n-1}\in \mathbf F_{AL}$ aussagenlogische Formeln, dann ist auch der Baum dessen Wurzel mit $C$ beschriftet ist und den $n$ Teilbäumen $\varphi_0, \ldots, \varphi_{n-1}$ eine aussagenlogische Formel.

Semantik von booleschen Ausdrücken

Aussagenlogische Formel ohne Variablen können entsprechend der Junktoren ausgewertet werden. Dabei steht $\top$ für wahr und $\bot$ für falsch. Junktoren werden zunächst mit Wertetabellen definiert -> Später kommen hier mathematische Operationen. Also Funktionen (z.B.: $f_\neg$ für die Negation)

• Beispiel $(\neg\bot\land\bot)\lor\neg\bot$ wird zu $f_\lor(f_\land(f_\neg(0),0),f_\neg(0))=f_\lor(f_\land(1,0),1)=f\lor(0,1)=1$

Def Variablenbelegung und Wahrheitswerte

Eine boolesche Variablenbelegung ist eine Funktion, die einer Menge von aussagenlogischen Variablen Wahrheitswerte $\{0, 1\}$ zuordnet, also $\mathbf V_{AL} \rightharpoonup \{0,1\}$. Eine Variablenbelegung $\beta$ passt zu einem booleschen Ausdruck $\varphi$, wenn $\beta$ für jede Variable, die in $\varphi$ auftritt, definiert ist. Die Menge der Wahrheitswerte, $\{0, 1\}$, wird mit $\mathbf B$ bezeichnet

#Def Auswertung einer aussagenlogischen Formel unter einer Belegung

Der Wert einer aussagenlogischen Formel $\varphi \in \mathbf F_{AL}$ unter einer passenden Belegung $\beta$ wird mit $\textlbrackdbl \varphi \textrbrackdbl_\beta$ bezeichnet und ist induktiv definieren durch

Basiselemente. $\textlbrackdbl\top \textrbrackdbl_\beta = 1$, $\textlbrackdbl\bot \textrbrackdbl_\beta = 0$ und $\textlbrackdbl X_i \textrbrackdbl_\beta = \beta(X_i)$ für alle $i \in \mathbb N_0$.

Induktive Regel. Ist $C$ ein $n$-stelliger Junktor und $\varphi_0, \ldots, \varphi_{n-1} \in \mathbf F_{AL}$, dann gilt $\textlbrackdbl C(\varphi_0, \ldots, \varphi_{n-1} \textrbrackdbl_\beta = f_C(\textlbrackdbl \varphi_0 \textrbrackdbl_\beta, \ldots, \textlbrackdbl \varphi_{n-1} \textrbrackdbl_\beta)$.

Dabei wird mit $f_C$ die boolesche Funktion des Junktors $C$ bezeichnet, die durch eine Tabellen gegeben ist (oder ein mathematischen Operation)

Notation und Terminologie

Für $\varphi\in\mathbf F_{AL}$ und passende Belegung $\beta$ sagen wir:

• $\beta$ ist eine 1-Belegung (bzw. Modell) für $\varphi$, falls $\textlbrackdbl\varphi\textrbrackdbl_\beta=1$.
• $\beta$ ist eine 0-Belegung (bzw. kein Modell) für $\varphi$, falls $\textlbrackdbl\varphi\textrbrackdbl_\beta=0$.