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

  • Beweise durch vollständige Wahrheitstafeln
  • Beweise durch Umformung boolescher Ausdrücke
  • Vereinfachung durch Umformung boolescher Ausdrücke
  • Literale und Monome

Beweise durch vollständige Wahrheitstafeln

  • Durch die Verwendung vollständiger Wahrheitstafeln können leicht Aussagen bewiesen werden
  • Beispiel:
    Beweise das Vereinigungstheorem (9): $xy \lor x\overline{y} = x$
    $x$ $y$$xy$$x\overline{y}$$xy \lor x\overline{y}$
    000 00
    010 00
    100 11
    111 01

Beweise durch Umformung

  • Die Verwendung von Wahrheitstafel ist für größere Funktionen aufwendig
  • Durch Verwendung der Liste der Axiome und Theorme aus dem letzten Kapitel können ebenfalls Aussagen bewiesen werden
  • Beispiel 1:
    Beweise das Vereinigungstheorem (9): $xy \lor x\overline{y} = x$
    $\begin{align} & xy \lor x\overline{y} \\ \stackrel{\small (8)}{=}& x \land (y \lor \overline{y}) \\ \stackrel{\small (5)}{=}& x \land 1\\ \stackrel{\small (1)}{=}& x \end{align}$

Beweise durch Umformung

  • Beispiel 2:
    Beweise das Theorem der Absorption (10): $x \lor xy = x$
    $\begin{align} & x \lor xy \\ \stackrel{\small (1)}{=}& (x \land 1) \lor xy \\ \stackrel{\small (8)}{=}& x \land (1 \lor y)\\ \stackrel{\small (2)}{=}& x \land 1\\ \stackrel{\small (1)}{=}& x \end{align}$
  • Die Klammer über dem Gleichheitszeichen gibt jeweils das bei der Umformung verwendete Axiom an (siehe "Liste der Axiome und Theorme" aus dem letzten Kapitel)

Beweise durch Umformung

  • Beispiel 3:
    Beweise das Theorem der Involution (4): $\lnot( \lnot x) = x$
    $\begin{align} & \lnot( \lnot x) = \lnot \overline{x} \\ \stackrel{\small (1)}{=}& \lnot \overline{x} \land 1 \\ \stackrel{\small (5)}{=}& \lnot \overline{x} \land (x \lor \overline{x}) \\ \stackrel{\small (8)}{=}& (\lnot \overline{x} \land x) \lor ( \lnot \overline{x} \land \overline{x}) \\ \stackrel{\small (6)}{=}& (\lnot \overline{x} \land x) \lor ( \overline{x} \land \lnot \overline{x}) \\ \stackrel{\small (5)}{=}& (\lnot \overline{x} \land x) \lor 0 \\ \stackrel{\small (5)}{=}& (\lnot \overline{x} \land x) \lor (x \land \overline{x})\\ \stackrel{\small (6)}{=}& (\lnot \overline{x} \land x) \lor (\overline{x} \land x)\\ \stackrel{\small (8)}{=}& (\lnot \overline{x} \lor \overline{x}) \land x\\ \stackrel{\small (5)}{=}& 1 \land x \\ \stackrel{\small (1)}{=}& x \end{align}$
Quelle:D. W. Hoffmann: Grundlagen der Technischen Informatik, 2. Auflage; Hanser 2009, S. 122

Vereinfachung durch Umformung

  • Beispiel 1:
    $\begin{align} & (x \nleftrightarrow y) \lor (x \leftrightarrow y) \\ \stackrel{}{=}& (\lnot x \land y)\lor (x \land \lnot y)\lor (\lnot x \land \lnot y)\lor (x \land y)\\ \stackrel{}{=}& (\overline{x} \land y)\lor (x \land \overline{y}) \lor (\overline{x} \land \overline{y}) \lor (x \land y)\\ \stackrel{\small (6)}{=}& \left((\overline{x} \land y)\lor (\overline{x} \land \overline{y})\right) \lor \left((x \land \overline{y}) \lor (x \land y)\right) \\ \stackrel{\small (8)}{=}& \left(\overline{x} \land (y \lor \overline{y})\right) \lor \left(x \land (\overline{y} \lor y)\right) \\ \stackrel{\small (5)}{=}& (\overline{x} \land 1) \lor (x \land 1) \\ \stackrel{\small (1)}{=}& \overline{x} \lor x \\ \stackrel{\small (5)}{=}& 1 \\ \end{align}$
  • Der boolesche Ausdruck $(x \nleftrightarrow y) \lor (x \leftrightarrow y)$ ist demnach immer gleich 1.
  • Eine solcher Ausdruck heißt allgemeingültig
Quelle:D. W. Hoffmann: Grundlagen der Technischen Informatik, 2. Auflage; Hanser 2009, S. 124

Vereinfachung durch Umformung

  • Beispiel 2:
    $\begin{align} & (x \nleftrightarrow y) \land \left((x \land \overline{y}) \lor y\right)\\ \stackrel{}{=}& (\overline{x} \land y)\lor (x \land \overline{y}) \land \left((x \land \overline{y}) \lor y\right)\\ \stackrel{\small (6)}{=}& (x \land \overline{y}) \lor (\overline{x} \land y) \land \left((x \land \overline{y}) \lor y\right)\\ \stackrel{\small (7)}{=}& \left((x \land \overline{y}) \lor (\overline{x} \land y)\right) \land \left((x \land \overline{y}) \lor y\right)\\ \stackrel{\small (8)}{=}& (x \land \overline{y}) \lor \left( (\overline{x} \land y) \land y\right) \\ \stackrel{\small (7)}{=}& (x \land \overline{y}) \lor \left( \overline{x} \land (y \land y)\right) \\ \stackrel{\small (3)}{=}& (x \land \overline{y}) \lor ( \overline{x} \land y ) \\ \stackrel{\small (6)}{=}& ( \overline{x} \land y ) \lor (x \land \overline{y}) \\ \stackrel{}{=}& (x \nleftrightarrow y) \end{align}$
Quelle:D. W. Hoffmann: Grundlagen der Technischen Informatik, 2. Auflage; Hanser 2009, S. 124

Tipps zum Rechnen mit booleschen Ausdrücken

  • Abkürzende Schreibweise erst verwenden, wenn Sie Sicherheit mit booleschen Ausdrücken erlangt haben
  • Beim Vereinfachen des Ausdrucks von den innersten geklammerten Ausdrücken nach außen vorgehen. Eventuell Klammerpaare farblich markieren.
  • Immer zunächst in folgender Reihenfolge prüfen, ob sich der Ausdruck vereinfachen lasst:
    • Absorption  (10)
    • Absorption II  (11)
    • Vereinigung  (9)
  • Besonders Distributivität (8) erst nach Prüfen aller anderen Möglichkeiten verwenden, wenn sich dadurch der Ausdruck verlängert

Literale und Monome

  • Ein Literal  ist eine Variable oder eine negierte Variable,
    z.B. $a$, $b$, $\lnot c$, $\overline{x}$, etc.
  • Ein Monom  ist eine UND-Verknüpfung von Literalen,
    z.B. $(a \land b \land \lnot c) = ab\overline{c}$, $\overline{f}\overline{e}\overline{d}$, $\overline{x}\overline{y}$, $xy\overline{z}$ etc.
  • Die Schaltfunktion eines Monoms kann nur dann $1$ sein, wenn jedes vorkommende Literal $1$ ist, d.h. jede vorkommende Variable mit $1$ und jede negierte Variable mit $0$ belegt ist
  • Das Monom $\overline{x}y\overline{z}$ ist also nur dann $1$, falls $x=z=0$ und $y=1$ sind

Literale und Monome

  • Ein boolescher Ausdruck, der aus einer ODER-Verknüpfung von Monomen besteht, evaluiert genau dann zu $1$, wenn mindestens eines der Monome zu $1$ evaluiert
  • So evaluiert der Ausdruck $y = (\overline{x}y\overline{z} \lor x\overline{y}z)$ zu 1, wenn $x=z=0$ und $y=1$
    oder $x=z=1$ und $y=0$
  • Durch die ODER-Verknüpfung von Monomen kann somit eine beliebige Schaltfunktion abgebildet werden

Literale und Monome

half_adder
Halbaddierer
  • Beispiel: 1-bit binärer Halbaddierer
    • Eingänge: Summanden $a$ und $b$
    • Ausgänge: Summe $s$, Carry-out $c_{\text{out}}$ (Übertrag)
    $a$$b$$s$$c_{\text{out}}$
    0000
    0110
    1010
    1101
  • Aus der Wahrheitstafel können in jeder Spalte, in der das Ergebnis $1 $sein soll, die Monome abgelesen werden
  • Damit ergibt sich:
    • $s = \overline{a}b \lor a\overline{b} = a \nleftrightarrow b$
    • $c_{\text{out}} = ab$

Literale und Monome

full_adder
Volladdierer
  • Beispiel: 1-bit binärer Volladdierer
    • Eingänge: Summanden $a$ und $b$, Carry-in $c_{\text{in}}$
    • Ausgänge: Summe $s$, Carry-out $c_{\text{out}}$
    $a$$b$$c_{\text{in}}$$s$$c_{\text{out}}$
    00000
    00110
    01010
    01101
    10010
    10101
    11001
    11111
  • Damit ergibt sich:
    • $s = \overline{a}\overline{b}c_{\text{in}} \lor \overline{a}b\overline{c}_{\text{in}} \lor a\overline{b}\overline{c}_{\text{in}} \lor abc_{\text{in}}$
    • $c_{\text{out}} = \overline{a}bc_{\text{in}} \lor a\overline{b}c_{\text{in}} \lor ab\overline{c}_{\text{in}} \lor abc_{\text{in}}$

Literale und Monome

  • Als Beispiel soll nun der boolesche Ausdruck für das $c_{\text{out}}$ des Volladdierers vereinfacht werden:
    $\begin{align} c_{\text{out}}&= \overline{a}bc_{\text{in}} \lor a\overline{b}c_{\text{in}} \lor ab\overline{c}_{\text{in}} \lor abc_{\text{in}}\\ &\stackrel{\small (3)}{=} \overline{a}bc_{\text{in}} \lor a\overline{b}c_{\text{in}} \lor ab\overline{c}_{\text{in}} \lor abc_{\text{in}} \lor abc_{\text{in}} \lor abc_{\text{in}}\\ &\stackrel{\small (6)}{=} \left(\overline{a}bc_{\text{in}} \lor abc_{\text{in}}\right) \lor \left(a\overline{b}c_{\text{in}} \lor abc_{\text{in}}\right) \lor \left(ab\overline{c}_{\text{in}} \lor abc_{\text{in}}\right) \\ &\stackrel{\small (8)}{=} \left((\overline{a} \lor a)bc_{\text{in}}\right) \lor \left(a(\overline{b} \lor b)c_{\text{in}}\right) \lor \left(ab(\overline{c}_{\text{in}} \lor c_{\text{in}})\right) \\ &\stackrel{\small (5)}{=} \left((1)bc_{\text{in}}\right) \lor \left(a(1)c_{\text{in}}\right) \lor \left(ab(1)\right) \\ &\stackrel{\small (1)}{=} bc_{\text{in}} \lor ac_{\text{in}} \lor ab \end{align}$

Quiz

  • Frage: Ist der boolesche Ausdruck
    $(a∧b)∨(a∧¬b) \lor \lnot a$
    allgemeingültig?
    • Antwort 1: Nein
    • Antwort 2: Ja
    • Antwort 3: keine Ahnung
Am Online-Quiz teilnehmen durch Besuch der Webseite:
www.onlineclicker.org

Gibt es Fragen?

questions

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


Weitere Vorlesungsfolien