235 lines
11 KiB
Markdown
235 lines
11 KiB
Markdown
|
# Syntax & Semantik
|
||
|
|
## Definition
|
||
|
|
Die Syntax beschreibt jeweils die Form, in der Dinge niedergeschrieben oder abgespeichert sind, während die Semantik bedeutet, wie das Geschriebene/das Gespeicherte interpretiert wird.
|
||
|
|
|
||
|
|
Folgend einige Beispiele:
|
||
|
|
|
||
|
|
| Syntax | Semantik |
|
||
|
|
| ---------------------------------- | ---------------------------------------------- |
|
||
|
|
| Paritur | Musik (Schallwellen) |
|
||
|
|
| Java-Code | Verhalten des Computers |
|
||
|
|
| Terme einer mathematischen Theorie | Mathematische Objekte |
|
||
|
|
| Aussagenlogische Formeln | Boolsche Funktionen |
|
||
|
|
| Peano-Axiome | Die Struktur ($\mathbb{N}$, $+$, $\cdot$ etc.) |
|
||
|
|
| Feynnman-Diagramm | Wechselwirkungen |
|
||
|
|
|
||
|
|
Abgesehen von den bereits aus dem Kapitel "Grundbegriffe und elementare Logik" bekannten Ausdrücke sind auch folgende Ausdrücke wichtig:
|
||
|
|
- $\top$: Gleichbedeutend mit `true`
|
||
|
|
- $\bot$: Gleichbedeutend mit `false`
|
||
|
|
|
||
|
|
## Darstellung
|
||
|
|
Um leichter Erkenntnisse über Wahrheitswerte von Aussagen zu ziehen, können diese in verschiedene Darstellungsformen gebracht werden.
|
||
|
|
|
||
|
|
Im Folgenden werden einige davon aufgezeigt.
|
||
|
|
|
||
|
|
### Ableitungsbaum
|
||
|
|
Ein Ableitungsbaum lässt es zu, den Überblick über eine Aussage bei einer bestimmten Belegung zu geben.
|
||
|
|
|
||
|
|
Folgende Formel gilt es darzustellen:
|
||
|
|
$$f = (((a \wedge b) \vee (\neg c)) \wedge (a \vee b))$$
|
||
|
|
|
||
|
|
Folgendes ist der Ableitungsbaum unter der Bedingung, dass $a = 1$, $b = 0$ und $c = 0$ entspricht:
|
||
|
|
|
||
|
|
```mermaid
|
||
|
|
flowchart BT;
|
||
|
|
a((a: 1));
|
||
|
|
b((b: 0));
|
||
|
|
c((c: 0));
|
||
|
|
a --- 1((AND));
|
||
|
|
b --- 1;
|
||
|
|
c --- 2((NOT));
|
||
|
|
1 -- 0 --- 3((OR));
|
||
|
|
2 -- 1 --- 3;
|
||
|
|
a --- 4((OR));
|
||
|
|
b --- 4;
|
||
|
|
3 -- 1 --- 5((AND));
|
||
|
|
4 -- 1 --- 5;
|
||
|
|
5 --- f((f: 1))
|
||
|
|
```
|
||
|
|
|
||
|
|
### Boolsche Funktionen
|
||
|
|
Ein weiterer Weg, eine Aussage darzustellen ist als boolsche Funktionen.
|
||
|
|
|
||
|
|
Hierbei werden jeweils algebraische Operatoren durch eine Funktion ersetzt, die dasselbe aussagt, nämlich folgende:
|
||
|
|
|
||
|
|
| Operator | Funktion |
|
||
|
|
| ------------ | ------------------ |
|
||
|
|
| $\neg A$ | $\text{not}(A)$ |
|
||
|
|
| $A \wedge B$ | $\text{or}(A, B)$ |
|
||
|
|
| $A \vee B$ | $\text{and}(A, B)$ |
|
||
|
|
|
||
|
|
$$\begin{aligned}
|
||
|
|
\newcommand{\and}{\mathop{\mathrm{and}}}
|
||
|
|
\text{or}(x,y) &= \begin{cases}
|
||
|
|
true & \text{falls} & x = true & \text{oder} & y = true \\
|
||
|
|
false & \text{sonst}
|
||
|
|
\end{cases} \\
|
||
|
|
|
||
|
|
\text{and}(x,y) &= \begin{cases}
|
||
|
|
true & \text{falls} & x = true & \text{und} & y = true \\
|
||
|
|
false & \text{sonst}
|
||
|
|
\end{cases} \\
|
||
|
|
|
||
|
|
\text{not}(x) &= \begin{cases}
|
||
|
|
true & \text{falls} & x = false \\
|
||
|
|
false & \text{sonst}
|
||
|
|
\end{cases}
|
||
|
|
\end{aligned}$$
|
||
|
|
|
||
|
|
### Wahrheitstabelle
|
||
|
|
Ein weiterer Weg, welcher es einem erleichtert, Erkenntnisse aus einer Aussage zu treffen, ist das Ausarbeiten einer Wahrheitstabelle, indem man alle einzelnen Terme berechnet.
|
||
|
|
|
||
|
|
Folgend ein Beispiel für diesen algebraischen Ausdruck:
|
||
|
|
$$p_0 \rightarrow (q \vee p_1)$$
|
||
|
|
|
||
|
|
| $p_0$ | q | $p_1$ | $q \vee p_1$ | $p_0 \rightarrow (q \vee p_1)$ |
|
||
|
|
| :---: | :---: | :---: | :----------: | :----------------------------: |
|
||
|
|
| $0$ | $0$ | $0$ | $0$ | $1$ |
|
||
|
|
| $0$ | $0$ | $1$ | $1$ | $1$ |
|
||
|
|
| $0$ | $1$ | $0$ | $1$ | $1$ |
|
||
|
|
| $0$ | $1$ | $1$ | $1$ | $1$ |
|
||
|
|
| $1$ | $0$ | $0$ | $0$ | $0$ |
|
||
|
|
| $1$ | $0$ | $1$ | $1$ | $1$ |
|
||
|
|
| $1$ | $1$ | $0$ | $1$ | $1$ |
|
||
|
|
| $1$ | $1$ | $1$ | $1$ | $1$ |
|
||
|
|
|
||
|
|
#### Boolsche Operatoren als Wahrheitstabellen
|
||
|
|
Folgendes sind boolsche Operatoren dargestellt als Wahrheitstabellen.
|
||
|
|
|
||
|
|
##### `AND` $\wedge$
|
||
|
|
| $F$ | $G$ | $F \wedge G$ |
|
||
|
|
| :---: | :---: | :----------: |
|
||
|
|
| $0$ | $0$ | $0$ |
|
||
|
|
| $0$ | $1$ | $0$ |
|
||
|
|
| $1$ | $0$ | $0$ |
|
||
|
|
| $1$ | $1$ | $1$ |
|
||
|
|
|
||
|
|
##### `OR` $\vee$
|
||
|
|
| $F$ | $G$ | $F \vee G$ |
|
||
|
|
| :---: | :---: | :--------: |
|
||
|
|
| $0$ | $0$ | $0$ |
|
||
|
|
| $0$ | $1$ | $1$ |
|
||
|
|
| $1$ | $0$ | $1$ |
|
||
|
|
| $1$ | $1$ | $1$ |
|
||
|
|
|
||
|
|
##### Implikation $\Rightarrow$
|
||
|
|
| $F$ | $G$ | $F \Rightarrow G$ |
|
||
|
|
| :---: | :---: | :---------------: |
|
||
|
|
| $0$ | $0$ | $1$ |
|
||
|
|
| $0$ | $1$ | $1$ |
|
||
|
|
| $1$ | $0$ | $0$ |
|
||
|
|
| $1$ | $1$ | $1$ |
|
||
|
|
|
||
|
|
#### Negation $\neg$
|
||
|
|
| $F$ | $\neg F$ |
|
||
|
|
| :---: | :------: |
|
||
|
|
| $0$ | $1$ |
|
||
|
|
| $1$ | $0$ |
|
||
|
|
|
||
|
|
## Semantische Eigenschaften
|
||
|
|
Über eine Formel $A$ mit der Belegung $B$ können unter bestimmten Umständen bestimmte Aussagen getroffen werden.
|
||
|
|
|
||
|
|
Folgend sind Aussagen und dazugehörige Umstände aufgelistet.
|
||
|
|
|
||
|
|
| Bezeichnung | Alternative Bezeichnung | Beschreibung |
|
||
|
|
| ----------------- | --------------------------------- | ------------------------------------------------------------------------------ |
|
||
|
|
| _Gültig_ | _richtig_ oder _wahr_ | Die gegebene Formel ist unter der Belegung $B$ wahr. |
|
||
|
|
| _Allgemeingültig_ | _Tautologie_ oder _immer wahr_ | Die gegebene Formel ist, unabhängig der Belegung $B$, immer wahr. |
|
||
|
|
| _Ungültig_ | _falsch_ oder _unwahr_ | Die gegebene Formel ist unter der Belegung $B$ nicht wahr. |
|
||
|
|
| _Unerfüllbar_ | _Widerspruch_ oder _immer falsch_ | Die gegebene Formel ist, unabhängig der Belegung $B$, immer falsch. |
|
||
|
|
| _erfüllbar_ | | Es gibt mindestens eine Belegung $B$ unter der die Formel erfüllbar ist. |
|
||
|
|
| _widerlegbar_ | | Es gibt mindestens eine Belegung $B$ unter der die Formel nicht erfüllbar ist. |
|
||
|
|
|
||
|
|
## Normalformen
|
||
|
|
Normalformen beinhalten generell nur `AND`s ($\wedge$), `OR`s ($\vee$) und `NOT`s ($\neg$).
|
||
|
|
|
||
|
|
### Negationsnormalform `NNF`
|
||
|
|
Die Negationsnormalform (`NNF`) ist die Form einer Formel, in der nur atomare (nicht aufteilbare) Teilformeln negiert sind.
|
||
|
|
|
||
|
|
Folgendes Beispiel anhand dieser Formel:
|
||
|
|
$$\neg(A \rightarrow (B \wedge \neg(C \vee D)))$$
|
||
|
|
|
||
|
|
Diese Form ist nicht komplett normalisiert, da sie den Operator $\rightarrow$ beinhaltet.
|
||
|
|
Dieser Operator wird im Folgenden umgeformt.
|
||
|
|
|
||
|
|
$$\neg(\neg A \vee (B \wedge \neg(C \vee D)))$$
|
||
|
|
|
||
|
|
Diese Formel ist keine `NNF`, da 2 nicht-atomare Formeln negiert sind.
|
||
|
|
Im Folgenden werden diese entfernt.
|
||
|
|
|
||
|
|
$$(\neg\neg A \wedge \neg(B \wedge (\neg C \wedge \neg D)))$$
|
||
|
|
$$(\neg\neg A \wedge (\neg B \vee \neg(\neg C \wedge \neg D)))$$
|
||
|
|
|
||
|
|
Nun ist nur noch eine letzte nicht-atomare Teilformel negiert. Dieser Teil wird nun entfernt:
|
||
|
|
|
||
|
|
$$(\neg\neg A \wedge (\neg B \vee (\neg\neg C \vee \neg\neg D)))$$
|
||
|
|
|
||
|
|
In einem letzten Schritt werden nun doppelte Negationen weg vereinfacht:
|
||
|
|
|
||
|
|
$$(A \wedge (\neg B \vee (C \vee D)))$$
|
||
|
|
|
||
|
|
Bei dieser Formel handelt es sich nun um eine Negationsnormalform (`NNF`), da nur atomare Teilformeln negiert sind und nur $\neg$s, $\vee$s und $\wedge$s in der Formel genutzt werden.
|
||
|
|
|
||
|
|
### Disjunktive Normalform `DNF`
|
||
|
|
Die Disjunktive Normalform ist eine Umformung der Formel, in der alle Belegungen für die die Formel $true$ ergibt, mit einander "verodert" werden.
|
||
|
|
|
||
|
|
Das sieht folgendermassen aus:
|
||
|
|
|
||
|
|
| $A$ | $B$ | $C$ | $D$ | $B \vee D$ | $(B \vee D) \wedge C$ | $\neg A \wedge ((B \vee D) \wedge C)$ |
|
||
|
|
| :---: | :---: | :---: | :---: | :--------: | :-------------------: | :-----------------------------------: |
|
||
|
|
| $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ |
|
||
|
|
| $0$ | $0$ | $0$ | $1$ | $1$ | $0$ | $0$ |
|
||
|
|
| $0$ | $0$ | $1$ | $0$ | $0$ | $0$ | $0$ |
|
||
|
|
| $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ |
|
||
|
|
| $0$ | $1$ | $0$ | $0$ | $1$ | $0$ | $0$ |
|
||
|
|
| $0$ | $1$ | $0$ | $1$ | $1$ | $0$ | $0$ |
|
||
|
|
| $0$ | $1$ | $1$ | $0$ | $1$ | $1$ | $1$ |
|
||
|
|
| $0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
|
||
|
|
| $1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ |
|
||
|
|
| $1$ | $0$ | $0$ | $1$ | $1$ | $0$ | $0$ |
|
||
|
|
| $1$ | $0$ | $1$ | $0$ | $0$ | $0$ | $0$ |
|
||
|
|
| $1$ | $0$ | $1$ | $1$ | $1$ | $1$ | $0$ |
|
||
|
|
| $1$ | $1$ | $0$ | $0$ | $1$ | $0$ | $0$ |
|
||
|
|
| $1$ | $1$ | $0$ | $1$ | $1$ | $0$ | $0$ |
|
||
|
|
| $1$ | $1$ | $1$ | $0$ | $1$ | $1$ | $0$ |
|
||
|
|
| $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $0$ |
|
||
|
|
|
||
|
|
Wie zu sehen ist, ist diese Formel an folgenden Stellen wahr:
|
||
|
|
- $\neg A \wedge \neg B \wedge C \wedge D$
|
||
|
|
- $\neg A \wedge B \wedge C \wedge \neg D$
|
||
|
|
- $\neg A \wedge B \wedge C \wedge D$
|
||
|
|
|
||
|
|
Die `DNF` erreicht man nun die Teilformeln der genannten Stellen mit einem `OR` verknüpft:
|
||
|
|
$$(\neg A \wedge \neg B \wedge C \wedge D) \vee (\neg A \wedge B \wedge C \wedge \neg D) \vee (\neg A \wedge B \wedge C \wedge D)$$
|
||
|
|
|
||
|
|
### Konjunktive Normalform `KNF`
|
||
|
|
Bei der Konjunktiven Normalform wiederum, werden alle negierten Belegungen, in denen die gegebene Formel $false$ ergibt miteinander "geandet".
|
||
|
|
|
||
|
|
Folgendes wieder anhand eines realen Beispiels:
|
||
|
|
|
||
|
|
| $A$ | $B$ | $C$ | $A \vee C$ | $B \vee (A \wedge C)$ |
|
||
|
|
| :---: | :---: | :---: | :--------: | :-------------------: |
|
||
|
|
| $0$ | $0$ | $0$ | $0$ | $0$ |
|
||
|
|
| $0$ | $0$ | $1$ | $0$ | $0$ |
|
||
|
|
| $0$ | $1$ | $0$ | $0$ | $1$ |
|
||
|
|
| $0$ | $1$ | $1$ | $0$ | $1$ |
|
||
|
|
| $1$ | $0$ | $0$ | $0$ | $0$ |
|
||
|
|
| $1$ | $0$ | $1$ | $1$ | $1$ |
|
||
|
|
| $1$ | $1$ | $0$ | $0$ | $1$ |
|
||
|
|
| $1$ | $1$ | $1$ | $1$ | $1$ |
|
||
|
|
|
||
|
|
An folgenden Stellen ergibt diese Formel $false$:
|
||
|
|
- $\neg A \wedge \neg B \wedge \neg C$
|
||
|
|
Negation: $A \vee B \vee C$
|
||
|
|
- $\neg A \wedge \neg B \wedge C$
|
||
|
|
Negation: $A \vee B \vee \neg C$
|
||
|
|
- $A \wedge \neg B \wedge \neg C$
|
||
|
|
Negation: $\neg A \vee B \vee C$
|
||
|
|
|
||
|
|
Um nun eine `KNF` zu erhalten müssen die Negationen der genannten Stellen mit dem $\vee$-Operator verknüpft werden:
|
||
|
|
$$(A \vee B \vee C) \wedge (A \vee B \vee \neg C) \wedge (\neg A \vee B \vee C)$$
|
||
|
|
|
||
|
|
# Quellen
|
||
|
|
- [YouTube - Konjunktive Normalform KNF / conjunctive normal form CNF | Digitaltechnik](https://www.youtube.com/watch?v=l6b7895U-u8)
|
||
|
|
- [YouTube - Disjunktive Normalform DNF / disjunctive normal form | Digitaltechnik](https://www.youtube.com/watch?v=GyQITHPQst4)
|