97 lines
4.9 KiB
TeX
97 lines
4.9 KiB
TeX
\section{Boolsche Algebra}
|
|
|
|
Es gelten folgende Grundgesetze, wie in der Algebra:
|
|
|
|
\begin{center}
|
|
\begin{tabular}{r l l} \toprule
|
|
Kommutativität & $A \land B = B \land A$ \\
|
|
& $A \lor B = B \lor A$ \\
|
|
Assoziativität & $A \land (B \land C) = (A \land B) \land C$ \\
|
|
& $A \lor (B \lor C) = (A \lor B) \lor C$ \\
|
|
Distributivität & $(\textcolor{blue}{A\,\land}~B) \lor (\textcolor{blue}{A\,\land}\,C) = \textcolor{blue}{A\,\land}\,(B \lor C)$ \\
|
|
& $(\textcolor{blue}{A\,\lor}~B) \land (\textcolor{blue}{A\,\lor}\,C) = \textcolor{blue}{A\,\lor}\,(B \land C)$ \\ \bottomrule
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
Aus diesem Grund gilt folgende für die Logikminimierung sehr nützliche Umwandlung:
|
|
|
|
\begin{center}
|
|
\eqboxf{$\land \rightleftharpoons \cdot$ \qquad $\lor \rightleftharpoons +$}
|
|
\end{center}
|
|
|
|
Zusätzlich zu den Grundregeln gelten folgende Regeln:
|
|
|
|
\begin{center}
|
|
\begin{tabular}{r l l} \toprule
|
|
Nicht & $\overline{\overline{A}} = A$ & \\
|
|
Null-Theorem & $A \lor 0 = A$ & $A \land 0 = 0$ \\
|
|
Eins-Theorem & $A \lor 1 = 1$ & $A \land 1 = A$ \\
|
|
Idempotenz & $A \lor A = A$ & $A \land A = A$ \\
|
|
Verknüpfung mit Komplement & $A \lor \overline{A} = 1$ & $A \land \overline{A} = 0$ \\ \midrule
|
|
Adsorptionsgesetze & \multicolumn{2}{l}{$A \lor (\overline{A} \land B) = A \lor B$} \\
|
|
& \multicolumn{2}{l}{$A \land (\overline{A} \lor B) = A \land B$} \\
|
|
Absorptionsgesetze & \multicolumn{2}{l}{$A \lor (A \land B) = A$} \\
|
|
& \multicolumn{2}{l}{$A \land (A \lor B) = A$} \\
|
|
Nachbarschafts Gesetze & \multicolumn{2}{l}{$(A \land B) \lor (\overline{A} \land B) = B$} \\
|
|
& \multicolumn{2}{l}{$(A \lor B) \land (\overline{A} \lor B) = B$} \\ \bottomrule
|
|
\end{tabular}
|
|
\end{center}
|
|
\vfill
|
|
|
|
|
|
\subsection{De Morgan'sche Gesetze}
|
|
|
|
Beziehungen zwischen NAND/NOR und AND/OR:
|
|
|
|
\begin{center}
|
|
\begin{tabular}{r l} \toprule
|
|
Erstes Gesetz: & $\overline{A \land \dots \land B} = \not{A} \lor \dots \lor \not{B}$ \\
|
|
Zweites Gesetz: & $\overline{A \lor \dots \lor B} = \not{A} \land \dots \land \not{B}$ \\ \bottomrule
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
Daraus folgen zwei sehr nützliche Umwandlungen:
|
|
|
|
\begin{center}
|
|
\eqboxf{$A \land \dots \land B = \overline{\not{A} \lor \dots \lor \not{B}} \qquad A \lor \dots \lor B = \overline{\not{A} \land \dots \land \not{B}}$}
|
|
\end{center}
|
|
|
|
|
|
\subsection{Normalformen}
|
|
|
|
Der \emph{Minterm} ist eine AND-Verknüpfung, welcher $'1'$ ergibt für nur eine Kombination der Schaltungsvariablen. \medskip
|
|
|
|
Der \emph{Maxterm} ist eine OR-Verknüpfung, welcher $'0'$ ergibt für nur eine Kombination der Schaltungsvariablen. Bei der Bildung der Maxterme \emph{müssen die Variablen invertiert werden}!\medskip
|
|
|
|
\begin{center}
|
|
\renewcommand{\arraystretch}{1.25}
|
|
\begin{tabular}{|c c|c|c|c|} \hline
|
|
A & B & Z & Minterme & Maxterme \\ \hline
|
|
0 & 0 & 1 & $\overline{A} \land \overline{B}$ & \\
|
|
0 & 1 & 0 & & $A \lor \overline{B}$ \\
|
|
1 & 0 & 0 & & $\overline{A} \lor B$ \\
|
|
1 & 1 & 1 & $A \land B$ & \\ \hline
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
\subsubsection{Disjunktive Normalform DNF (ODER-Normalform)}
|
|
|
|
Besteht aus einer ODER-Verknüpfung aller Minterme:
|
|
|
|
\begin{center}
|
|
\eqbox{$Z = (\not{A} \land \not{B}) \lor (A \land B)$}
|
|
\end{center}
|
|
|
|
\subsubsection{Konjunktive Normalform KNF (UND-Normalform)}
|
|
|
|
Besteht aus einer UND-Verknüpfung aller Maxterme:
|
|
|
|
\begin{center}
|
|
\eqbox{$\not{Z} = (A \lor \not{B}) \land (\not{A} \lor B)$}
|
|
\end{center}
|
|
|
|
\subsubsection{Kanonische Normalform}
|
|
|
|
Die kanonische Normalform ist die unvereinfachte Normalform einer Wahrheitstabelle. Sie gibt also nicht notwendigerweise die einfachsten Funktionsgleichungen an.
|
|
\vfill
|