Aussagenlogischen Formel

Einfache Sprache

Bestandteile:

1. Symbole für Boolescher 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 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.

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