• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Wie wende ich die Shannon-Zerlegung an?

Contents

  • Wie wende ich die Shannon-Zerlegung an?
    • Vorgehen
    • Beispiel 1
    • Beispiel 2

Die Shannon-Zerlegung ist hilfreich, um die disjunktive bzw. konjunktive Form einer Funktion zu erhalten. Im Folgenden gibt es ein paar Beispiele, wie man das macht:

Vorgehen

  1. Man hat eine boolsche Funktion $f(x_1, x_2, \dots, x_n)$ gegeben.
  2. Entwickeln nach einer Variablen $x_i$:
    1. $g(x_1, \dots, x_n) := f(x_1, \dots, x_i=1, \dots, x_n)$
    2. $h(x_1, \dots, x_n) := f(x_1, \dots, x_i=0, \dots, x_n)$
    3. $f(x_1, x_2, \dots, x_n) = x_i [ g(x_1, \dots, x_n)] \lor \bar x_i [h(x_1, \dots, x_n)]$
  3. Vereinfachen der Funktion

Beispiel 1

\begin{align} f(c, b, a) :&= (c \land b) \barwedge a) \Leftrightarrow (b \lor a)\\ \text{Entwickeln nach c:} &= c[((1 \land b) \barwedge a) \Leftrightarrow (b \lor a)] \lor \bar c [((0 \land b) \barwedge a) \Leftrightarrow (b \lor a)]\\ &= c[(b \barwedge a) \Leftrightarrow (b \lor a)] \lor \bar c [(0 \barwedge a) \Leftrightarrow (b \lor a)]\\ &= c[(b \barwedge a) \Leftrightarrow (b \lor a)] \lor \bar c [1 \Leftrightarrow (b \lor a)]\\ &= c((b \barwedge a) \Leftrightarrow (b \lor a)) \lor \bar c (b \lor a)\\ \text{Entwickeln nach b:}&= b \lor \bar b\\ &= b \lor \bar b \\ &= b(c \bar a \lor \bar c) \lor \bar b (ca \lor \bar c a)\\ \text{Entwickeln nach a:} &= a[b(c \bar 1 \lor \bar c) \lor \bar b (c \lor \bar c)] \lor \bar a [b(c \bar 0 \lor \bar c) \lor \bar b (\bar c a)]\\ &=a(b \bar c \lor \bar b) \lor \bar ab\\ &= ab \bar c \lor a \bar b \lor \bar a b\\ &= ab \bar c \lor a \bar b c \lor a \bar b \bar c \lor \bar a b c \lor \bar a b \bar c \end{align}

Die letzte Darstellung der Funktion \(f\) wird Disjunktive Normalform (DNF) genannt. Die vorletzte ist einfach nur eine disjunktion von Konjunktionen.

Beispiel 2

\begin{align} f(c,b,a) &:= ab \lor \bar c\\ \text{Entwickeln nach b:} &= b[a \lor \bar c] \lor \bar b[\bar c]\\ &= b(a \lor \bar c) \lor \bar b \bar c\\ \text{Entwickeln nach a:} &= a[b \lor \bar b \bar c] \lor \bar a [b(\bar c) \lor \bar b \bar c]\\ &= a(b \lor \bar b \bar c) \lor \bar a \bar c\\ &= ab \lor a \bar b \bar c \lor \bar a \bar c\\ &= (abc \lor ab \bar c) \lor a \bar b \bar c \lor (\bar a b \bar c \lor \bar a \bar b \bar c) \end{align}

Man muss auch nicht immer Entwicklen, um das Ergebnis zu erhalten. Die Klammern im Ergebnis verdeutlichen, wie man den letzten Schritt durchführt. Also wie man von einer Disjunktiven Form auf die Disjunktive Normalform kommt.


Published

Jan 17, 2013
by Martin Thoma

Category

German posts

Tags

  • Boolean algebra 2
  • boolean expression 2
  • Digitaltechnik 8

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor