Dieser Blogpost ist vor allem für Hörer von Prof. Dr. Asfour im WS 2012 / 2013 interessant. Ich höre momentan die Vorlesung bei ihm. Deshalb sind die Inhalte teilweise identisch oder zumindest sehr ähnlich.
Dieser Blogpost soll nur möglichst gute Definitionen liefern. Ich werde ihn vermutlich bis zum Ende des Semesters immer wieder erweitern.
Boolesche Algebra
Konjunktion: \(\land\) Disjunktion: \(\lor\)
Sei $x$ eine Variable.
L heißt Literal $:\Leftrightarrow L \in \{x, \bar x\}$.
Seien $L_1, \dots, L_n$ Literale.
$K(x_1, \dots, x_n)$ heißt ein Produktterm $:\Leftrightarrow K(x_1, \dots, x_n) = \bigwedge_{i=1}^n L_i$ oder $K = 1$ oder $K=0$.
Jeder Produktterm \(K(x_1, \dots, x_n)\) kann so dargestellt werden, dass eine Variable \(x\) in höchstens einem Literal vorkommt.
Sei $K(x_1, \dots, x_n)$ ein Produktterm und $y(x_1, \dots x_n)$ eine boolesche Funktion.
$K$ heißt Implikant von $y :\Leftrightarrow (K \Rightarrow y)$
Sei $K(x_1, \dots, x_n)$ ein Implikant der boolesche Funktion $y(x_1, \dots x_n)$.
$K$ heißt Minterm von $y :\Leftrightarrow$ Für jede Variable $x_i$ in $y$ kommt genau ein mal in $K$ als Literal vor.
Sei $y(x_1, \dots x_n)$ eine boolesche Funktion und $x$ ein boolescher Ausdruck, der $y$ entspricht.
$x$ heißt disjunktive Normalform (DNF) von $y :\Leftrightarrow$
$x=\bigvee_{i=0}^k K_i, \; k \leq 2^n - 1:\quad K_i \neq K_j \Leftrightarrow i \neq j$
Sei $D(x_1, \dots, x_m)$ eine Disjunktion von Literalen $\bigvee_{i=1}^m L_i$ oder die Konstante „0“ oder die Konstante „1“. Sei weiter $y(x_1, \dots x_n)$ eine boolesche Funktion.
$D$ heißt Implikat von $y :\Leftrightarrow \bar D \Rightarrow \bar y$
Summenterm ist ein Synonym zu Implikat.
Sei $y(x_1, \dots x_n)$ eine boolesche Funktion und $D$ ein Implikat von $y$.
$D$ heißt Maxterm von $y :\Leftrightarrow$ Ein Literal jeder Variable $x_i$ der Funktion $y$ kommt in $D$ genau einmal vor.
Beispiele:
| Minterm | Maxterm | |
|---|---|---|
| 0 | $\bar a \bar b \bar c$ | $a \lor b \lor c$ |
| 1 | $a \bar b \bar c$ | $\bar a \lor b \lor c$ |
| 2 | $\bar a b \bar c$ | $a \lor \bar b \lor c$ |
| 3 | $a b \bar c$ | $\bar a \lor \bar b \lor c$ |
| 4 | $\bar a \bar b c$ | $a \lor b \lor \bar c$ |
| 5 | $a \bar b c$ | $\bar a \lor b \lor \bar c$ |
| 6 | $\bar a b c$ | $a \lor \bar b \lor \bar c$ |
| 0 | $a b c$ | $\bar a \lor \bar b \lor \bar c$ |
Ein boolescher Ausdruck der Form
$\bigwedge_i \bigvee_j (\neg)x_{ij}$
wird konjunktive Normalform (KNF) genannt.