Steuerungstasten

→ nächste Folie (auch Enter oder Spacebar).
← vorherige Folie
 d  schaltet das Zeichnen auf Folien ein/aus
 p  wechselt zwischen Druck- und Präsentationsansicht
CTRL  +  vergrößert die Folien
CTRL  -  verkleinert die Folien
CTRL  0  setzt die Größenänderung zurück

Das Weiterschalten der Folien kann ebenfalls durch das Klicken auf den rechten bzw. linken Folienrand erfolgen.

Notation

Typ Schriftart Beispiele
Variablen (Skalare) kursiv $a, b, x, y$
Funktionen aufrecht $\mathrm{f}, \mathrm{g}(x), \mathrm{max}(x)$
Vektoren fett, Elemente zeilenweise $\mathbf{a}, \mathbf{b}= \begin{pmatrix}x\\y\end{pmatrix} = (x, y)^\top,$ $\mathbf{B}=(x, y, z)^\top$
Matrizen Schreibmaschine $\mathtt{A}, \mathtt{B}= \begin{bmatrix}a & b\\c & d\end{bmatrix}$
Mengen kalligrafisch $\mathcal{A}, B=\{a, b\}, b \in \mathcal{B}$
Zahlenbereiche, Koordinatenräume doppelt gestrichen $\mathbb{N}, \mathbb{Z}, \mathbb{R}^2, \mathbb{R}^3$

Inhalt

  • Schaltkreise und Wahrheitstafeln
  • Boolesche Algebra
  • Schaltalgebra
  • Boolesche Funktionen
  • Boolesche Ausdrücke

Schaltkreise und Wahrheitstafeln

switches0
  • Betrachten wir einen einfachen Stromkreis bestehend aus einer Spannungsquelle (z.B. einer Batterie), einem
    Schalter $s$, und einer Lampe $l$
  • Ist der Schalter offen ($s$=0), brennt die Lampe nicht ($l$=0). Ist der Schalter geschlossen ($s$=1), brennt die Lampe ($l$=1).
  • Das Verhalten des Stromkreises kann in einer Wahrheitstafel dargestellt werden
    $s$$l$
    00
    11

Schaltkreise und Wahrheitstafeln

  • Durch eine Reihenschaltung kann eine logische UND-Verknüpfung realisiert werden (Licht brennt, wenn $s_1$=1 UND $s_2$=1)
$s_1$$s_2$$l$
000
010
100
111
switches1
  • Durch eine Parallelschaltung kann eine logische ODER-Verknüpfung realisiert werden (Licht brennt, wenn $s_1$=1 ODER $s_2$=1)
$s_1$$s_2$$l$
000
011
101
111
switches1

Schaltkreise und Wahrheitstafeln

  • Durch umgekehrten Anschluss der Leitung kann eine logisches NICHT realisiert werden (Licht brennt, wenn $s$=0)
$s$$l$
01
10
switches1
  • Damit haben wir schon die Grundelemente UND, ODER, NICHT (Englisch: AND, OR, NOT) kennengelernt, mit denen sich im Prinzip jeder mögliche Schaltkreis aufbauen lässt

Schaltkreise und Wahrheitstafeln

  • Wie könnte ein Schaltkreis aussehen, der folgende Wahrheitstabelle realisiert?
    $s_1$$s_2$$l$
    000
    011
    101
    110
  • Lösung: ($s_1$=0 AND $s_2$=1) OR ($s_1$=1 AND $s_2$=0)
    switches_xor
  • Wir haben haben damit übrigens gerade das "EXKLUSIVE ODER" (Englisch: XOR) implementiert

Schaltkreise und Wahrheitstafeln

  • Wie viele mögliche Funktionen zweier Eingangsvariablen gibt es eigentlich?
    two_inputs
  • Antwort:
    Es gibt 16 mögliche Funktionen zweier Eingangsvariablen:
$s_1$$s_2$16 mögliche Funktionen $l_0$ bis $l_{15}$
00 0000000011111111
01 0000111100001111
10 0011001100110011
11 0101010101010101
  • Im Allgemeinen gibt es bei $n$ Eingangsvariablen $2^{(2^{n})}$ mögliche Funktionen

Boolesche Algebra

Definition mittels Huntington'scher Axiome:

  • Sei $\mathcal{V}$ eine nicht leere Menge von Elementen mit den binären Operatoren $\circ: \mathcal{V} \times \mathcal{V} \rightarrow \mathcal{V}$ und $\bullet: \mathcal{V} \times \mathcal{V} \rightarrow \mathcal{V}$.
  • Das Tripel $(\circ,\bullet,\mathcal{V})$ heißt Boolesche Algebra, wenn für beliebige $a, b, c \in \mathcal{V}$ folgende Axiome gelten:
Operator $\bullet$ Operator $\circ$
kommutativ $a \bullet b = b \bullet a$ $a \circ b = b \circ a$
distributiv $a \bullet (b \circ c) = (a \bullet b) \circ (a \bullet c)$ $a \circ (b \bullet c) = (a \circ b) \bullet (a \circ c)$
Identität $a \bullet 1 = a$ $a \circ 0 = a$
Inversion $a \bullet a^{-1} = 0 $ $a \circ a^{-1} = 1$
  • Dabei müssen die Elemente 0 und 1 jeweils ein bestimmtes ausgezeichnetes Element aus $\mathcal{V}$ sein

Boolesche Algebra

  • Ist der Körper der rellen Zahlen mit der Multiplikation und Addition $(\cdot,+,\mathbb{R})$ eine boolesche Algebra?
  • Antwort: Nein, einige Axiome gelten nicht
Operator $\cdot$ Operator $+$
kommutativ $a \cdot b = b \cdot a$ $a + b = b + a$
distributiv $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$ $a + (b \cdot c) = (a + b) \cdot (a + c)$
Identität $a \cdot 1 = a$ $a + 0 = a$
Inversion $a \cdot a^{-1} = 0$ $a + a^{-1} = 1$

Schaltalgebra

  • Die Schaltalgebra ist eine boolesche Algebra über dem Tripel $(\land,\lor,\mathcal{B})$ mit
    • der Grundmenge $\mathcal{B} = \{0, 1\}$
    • der AND-Verknüpfung (Konjunktionsoperator): "$\land$"
    • der OR-Verknüpfung (Disjunktionsoperator): "$\lor$"
    • und dem inversen Element: der NOT-Operation (Negation): "$\lnot$"
  • Es gilt somit laut Definition:
Operator $\land$ Operator $\lor$
kommutativ $a \land b = b \land a$ $a \lor b = b \lor a$
distributiv $a \land (b \lor c) = (a \land b) \lor (a \land c)$ $a \lor (b \land c) = (a \lor b) \land (a \lor c)$
Identität $a \land 1 = a$ $a \lor 0 = a$
Inversion $a \land \lnot a = 0 $ $a \lor \lnot a = 1$

Schaltalgebra

  • Die Schaltalgebra besteht somit aus folgenden elementaren Grundoperationen
    • Konjunktion (AND): $y = a \land b$
      $a$$b$$y = a \land b$
      000
      010
      100
      111
    • Disjunktion (OR): $y = a \lor b$
      $a$$b$$y = a \lor b$
      000
      011
      101
      111
    • Negation (NOT): $y = \lnot a$
      $a$$y = \lnot a$
      01
      10

Boolesche Funktionen (Schaltfunktion)

  • Eine Funktion $y= \mathrm{f}(x_1, x_2, \dots, x_n)$ mit $x_1, x_2, \dots, x_n \in \{0,1\}$ heisst boolesche Funktion der Stelligkeit $n$
  • Boolesche Funktionen werden auch Schaltfunktionen genannt
  • Die Eingabevariablen $x_1, x_2, \dots, x_n$ werden als freie Variablen bezeichnet
  • Die Ausgabevariable $y$ wird abhängige Variable genannt
  • Beispiele:
    • Der Negationsoperator $y = \lnot x_1$ ist eine boolesche Funktion der Stelligkeit $1$
    • Konjunktionsoperator $y = x_1 \land x_2$ und Disjunktionsoperator $y = x_1 \lor x_2$ sind boolesche Funktionen der Stelligkeit $2$
Quelle:D. W. Hoffmann: Grundlagen der Technischen Informatik, 2. Auflage; Hanser 2009

Boolesche Funktionen (Schaltfunktion)

  • Eine boolesche Funktion kann eindeutig durch eine vollständige Wahrheitstafel beschrieben werden
  • Beispiele:
    $x_1$$x_2$$y$
    000
    011
    101
    110
    $x_1$$x_2$$x_3$$y$
    000 0
    0011
    0101
    0110
    100 1
    1010
    1100
    1111

Boolesche Ausdrücke

bool_expression
Syntaxdiagramm
  • Die Darstellung durch Wahrheitstafeln wird schnell sehr groß und unübersichtlich
  • Daher werden boolesche Funktionen häufig in Formeldarstellung angegeben
  • Diese Formeldarstellungen werden Boolesche Ausdrücke genannt und sind durch das gezeigte Syntaxdiagramm definiert
Quelle: D. W. Hoffmann: Grundlagen der Technischen Informatik, 2. Auflage; Hanser 2009, Abbildung 4.5

Boolesche Ausdrücke

  • Die Darstellung einer booleschen Funktion mittels boolescher Ausdrücke ist nicht eindeutig
  • Beispiel: Die Funktion
    $x_1$$x_2$$y$
    000
    011
    101
    110
    kann durch viele verschiedene boolesche Ausdrücke beschrieben werden:
    $\begin{align}y &= (\lnot x_1 \land x_2) \lor (x_1 \land \lnot x_2)\\ y &= (x_1 \lor x_2) \land \lnot( x_1 \land x_2) \\ y &= \dots \end{align}$
  • Durch die Theoreme auf der nächsten Folie können verschiedene boolesche Ausdrücke in einander überführt werden

Liste der Axiome und Theoreme

  • Aus den Axiomen der booleschen Algebra lassen sich weitere Theoreme ableiten
# Name AND-Operator $\land$ OR-Operator $\lor$
1 Identität $a \land 1 = a$ $a \lor 0 = a$
2 Elimination $a \land 0 = 0$ $a \lor 1 = 1$
3 Idempotenz $a \land a = a$ $a \lor a = a$
4 Involution $\lnot(\lnot a) = a$
5 Komplement $a \land \lnot a = 0 $ $a \lor \lnot a = 1$
6 Kommutativität $a \land b = b \land a$ $a \lor b = b \lor a$
7 Assoziativität $(a \land b) \land c = a \land (b \land c)$ $(a \lor b) \lor c = a \lor (b \lor c)$
8 Distributivität $a \land (b \lor c) = (a \land b) \lor (a \land c)$ $a \lor (b \land c) = (a \lor b) \land (a \lor c)$
9 Vereinigung $(a \lor b) \land (a \lor \lnot b) = a$ $(a \land b) \lor (a \land \lnot b) = a$
10 Absorption $a \land (a \lor b)= a$ $a \lor (a \land b)= a$
11 Absorption (2) $(a \land \lnot b) \lor b= a \lor b$ $(a \lor\lnot b) \land b= a \land b$
12 Faktorisierung $(a \lor b) \land (\lnot a \lor c) = (a \land c) \lor (\lnot a \land b)$ $(a \land b) \lor (\lnot a \land c) = (a \lor c) \land (\lnot a \lor b) $
13 Konsens $(a \lor b) \land (b \lor c) \land (\lnot a \lor c) = (a \lor b) \land (\lnot a \lor c)$ $(a \land b) \lor (b \land c) \lor (\lnot a \land c) = (a \land b) \lor (\lnot a \land c)$
14 de Morgans Gesetz $\lnot (a \land b \land \dots) = \lnot a \lor \lnot b \lor \dots$ $\lnot (a \lor b \lor \dots) = \lnot a \land \lnot b \land \dots$

Dualität

  • Von den aufgelisteten Theoremen muss sich nur eine Spalte der Tabelle gemerkt werden. Die andere Spalte ergibt sich direkt durch die Dualität
  • Der duale boolesche Ausdruck $f_d$ kann aus $f$ ermittelt werden, indem $\lor$ mit $\land$ und $0$ mit $1$ vertauscht wird
    $ \mathrm{f}(x_1, x_2, \dots, x_n, 0, 1, \land, \lor) \leftrightarrows \mathrm{f}_d = f(x_1, x_2, \dots, x_n, 1, 0, \lor, \land)$

De Morgansche Gesetze

de_morgan
Augustus De Morgan
  • Die Gesetze von August De Morgan (∗1806; †1871) lauten
    • $\lnot(a \land b) = \lnot a \lor \lnot b$
    • $\lnot(a \lor b) = \lnot a \land \lnot b$
  • Die Gültigkeit der Gesetze kann leicht anhand von Wahrheitstafeln gezeigt werden
    $a$$b$$a \land b $$\lnot(a \land b)$$\lnot a$$\lnot b$$\lnot a \lor \lnot b$
    0001111
    0101101
    1001011
    1110000
    $a$$b$$a \lor b $$\lnot(a \lor b)$$\lnot a$$\lnot b$$\lnot a \land \lnot b$
    0001111
    0110100
    1010010
    1110000

Negationstheorem

  • Theorem #14 aus unserer Liste ist eine Verallgemeinerung der De Morganschen Gesetze:
    • $\lnot (a \land b \land \dots) = \lnot a \lor \lnot b \lor \dots$
    • $\lnot (a \lor b \lor \dots) = \lnot a \land \lnot b \land \dots$
  • Noch allgemeiner formuliert es das Negationstheorem:
    $\lnot \left( \mathrm{f}(x_1, x_2, \dots, x_n, 0, 1, \land, \lor) \right)= \mathrm{f}(\lnot x_1, \lnot x_2, \dots, \lnot x_n, 1, 0, \lor, \land)$
    • Beispiel:
      $\lnot \left( (a \land 1) \lor b \right) = (\lnot a \lor 0) \land \lnot b$

Weitere Operatoren

  • Neben den elementaren logischen Operationen (AND, OR, NOT) gibt es noch weitere wichtige Operatoren
    • Implikation und Inverse Implikation
    • Äquivalenz und Antivalenz
    • Sheffer-Funktion (NAND) und Peirce-Funktion (NOR)
  • Diese Operationen könnten jedoch alle auch mit den elementaren Operationen realisiert werden
  • Sie verkürzen lediglich die Darstellung

Implikation und Inverse Implikation

  • Implikation: $y = a \rightarrow b = \lnot a \lor b$
    • Gültigkeit der Aussage: "$a$ ist eine hinreichende Bedingung für $b$".
    • Beispiel: "Dass die Sonne scheint, resultiert zwangsläufig (hinreichende Bedingung) in Sonnenbrand"
    • Diese Aussage ist nur falsch, wenn die Sonne scheint und trotzdem kein Sonnenbrand auftritt
    $a$$b$$y = a \rightarrow b$
    001
    011
    100
    111
  • Inverse Implikation: $y = a \leftarrow b = \lnot b \lor a$
    $a$$b$$y = a \leftarrow b$
    001
    010
    101
    111

Äquivalenz und Antivalenz

  • Äquivalenz: $y = a \leftrightarrow b = (\lnot a \land \lnot b) \lor (a \land b)$
    • Wahr, wenn beide Operanden den gleichen Wahrheitswert besitzen
    $a$$b$$y = a \leftrightarrow b$
    001
    010
    100
    111
  • Antivalenz: $y = a \nleftrightarrow b = (\lnot a \land b) \lor (a \land \lnot b)$
    • Wahr, wenn beide Operanden verschiedene Wahrheitswerte besitzen
    • Exklusives Oder (XOR)
    $a$$b$$y = a \nleftrightarrow b$
    000
    011
    101
    110

Sheffer-Funktion und Peirce-Funktion

  • Sheffer-Funktion: $y = a \mathbin{\bar{\land}} b = \lnot(a \land b)$
    • Konjunktion mit anschießender Negation (NAND)
    $a$$b$$y = a \mathbin{\bar{\land}} b$
    001
    011
    101
    110
  • Peirce-Funktion: $y = a \mathbin{\bar{\lor}} b = \lnot (a \lor b)$
    • Disjunktion mit anschließender Negation (NOR)
    $a$$b$$y = a \mathbin{\bar{\lor}} b$
    001
    010
    100
    110

Operatorsymbole der Schaltalgebra nach DIN 66000

OperatorBenennungBeispielSprechweise
$\lnot$
$\overline{\ \ }$ 		Negation, NOT$y = \lnot a = \overline{a}$nicht $a$
$\land$ Konjunktion, AND $y = a \land b$$a$ und $b$
$\lor$ Disjunktion, OR $y = a \lor b$$a$ oder $b$
$\rightarrow$ Implikation $y = a \rightarrow b$$a$ impliziert $b$
$\leftrightarrow$ Äquivalenz $y = a \leftrightarrow b$$a$ äquivalent $b$
$\nleftrightarrow$ Antivalenz, XOR $y = a \nleftrightarrow b$$a$ xor $b$
$\mathbin{\bar{\land}}$ Sheffer-Funktion, NAND $y = a \mathbin{\bar{\land}} b$$a$ nand $b$
$\mathbin{\bar{\lor}}$ Peirce-Funktion, NOR $y = a \mathbin{\bar{\lor}} b$$a$ nor $b$

Operatorsymbole der Schaltalgebra nach DIN 66000

  • Gemäß DIN 66000 besitzen die Symbole folgende Vorrangregeln:
    • Stärkste Bindung: $\lnot$
    • Mittlere Bindung: $\land$, $\lor$, $\mathbin{\bar{\land}}$, $\mathbin{\bar{\lor}}$
    • Niedrige Bindung: $\rightarrow$, $\leftrightarrow$, $\nleftrightarrow$
  • Symbole mit gleicher Bindungsstärke werden linksassoziativ ausgewertet
  • Beispiele:
    • $y = a \land \lnot b = a \land (\lnot b)$
    • $y =a \land b \land c = (a \land b) \land c$
    • $y =a \lor b \lor c = (a \lor b) \lor c$
    • $y =a \lor b \land c = (a \lor b) \land c$
    • $y =a \leftrightarrow \lnot b \lor \lnot c \land d = a \leftrightarrow ( ( (\lnot b) \lor (\lnot c)) \land d ) $

Operatorsymbole der Schaltalgebra, US-Schreibweise

OperatorBenennungBeispielSprechweise
$\overline{\ \ }$ negation, NOT$y = \overline{a}$not $a$
$\cdot$ conjunction, AND $y = a \cdot b = ab$$a$ and $b$
$+$ disjunction, OR $y = a + b$$a$ or $b$
$\implies$ implication $y = a \implies b$$a$ implies $b$
$\equiv$
$\overline{\ \oplus \ }$ 		equivalence, (E)XNOR $y = a \equiv b = \overline{a \oplus b}$$a$ exnor $b$
$\oplus$ exclusive disjunction, (E)XOR $y = a \oplus b$$a$ exor $b$
$\overline{\ \cdot \ }$ NAND $y = \overline{a \cdot b} = \overline{ab}$$a$ nand $b$
$\overline{\ + \ }$ NOR $y = \overline{a + b}$$a$ nor $b$

Abgekürzte Schreibweise boolescher Ausdrücke

  • In dieser Vorlesung wird eigentlich durchgängig die DIN-Schreibweise verwendet
  • Ein entscheidender Unterschied zwischen DIN und US-Schreibweise ist die Bindung der UND-Verknüpfung
  • Während bei der DIN-Norm UND- sowie ODER-Verknüpfung gleichrangig sind, gilt in der US-Schreibweise analog zur Algebra "Punkt- vor Strichrechnung"
    • US-Schreibweise: $a + b \cdot c = a + (b \cdot c) = a + bc$
    • DIN-Schreibweise: $a \lor b \land c = (a \lor b) \land c$
  • Abweichend von der DIN-Norm wird in dieser Vorlesung (und den Übungen) analog zur US-Version teilweise die verkürzte Schreibweise $ab = (a \land b)$ angewendet, um die Ausdrücke lesbarer zu machen
  • Ausschließlich diese verkürzte Schreibweise der UND-Verknüpfung soll eine höhere Bindung haben, als die anderen Operatoren. Die stärkste Bindung hat weiterhin die Negation.
    • DIN-Schreibweise: $(a \land b \land \lnot(c \land d) ) \lor (\lnot e \land f) = (a \land b \land \overline{c \land d} ) \lor (\overline{e} \land f)$
    • Abgekürzte Schreibweise: $ab\overline{cd} \lor \overline{e}f$

Zusammenfassung: Alle zweistelligen Schaltfunktionen

$a$0011
$b$0101
$y=0$0000Nullfunktion
$y=a \land b$0001Konjunktion
$y=a \land \lnot b$0010
$y=a$0011
$y=\lnot a \land b$0100
$y=b$0101
$y=a \nleftrightarrow b$0110Antivalenz
$y=a \lor b$0111Disjunktion
$y=a \mathbin{\bar{\lor}} b$1000 Peirce-Funktion, NOR
$y=a \leftrightarrow b$1001 Äquivalenz
$y=\lnot b$1010
$y=a \leftarrow b$1011 Inverse Implikation
$y=\lnot a$1100
$y= a \rightarrow b$1101Implikation
$y=a \mathbin{\bar{\land}} b$1110 Sheffer-Funktion, NAND
$y=1$1111 Einsfunktion

Gibt es Fragen?

questions

Anregungen oder Verbesserungsvorschläge können auch gerne per E-mail an mich gesendet werden: Kontakt


Weitere Vorlesungsfolien

Impressum, Datenschutz,