Die im vorangegangenen Abschnitt eingeführten Basisfunktionen pi spannen ebenso wie die Minterme (=Einspunktfunktionen) den Tn auf. Deshalb gibt es eine lineare Transformation
r = A*f
zwischen den Komponentenvektoren r und f der gegebenen Schaltfunktion. Die binäre Matrix A kann hergeleitet werden aus den Funktionstabellen der Basisfunktionen der Reed-Muller-Form. Wir schreiben diese Funktionstabellen der Reihe nach als Spalten in eine Matrix und erhalten für eine, zwei, drei Variablen:
binexp2bintab3(rmbasis({'a'}),{'a'},2) % Funktionstabellen
binexp2bintab3(rmbasis({'a';'b'}),{'a';'b'},2) % Funktionstabellen
binexp2bintab3(rmbasis({'a';'b';'c'}),{'a';'b';'c'},2) % Funktionstabellen
Die binäre Matrix A hat offenbar eine sehr einfache Struktur, die sich rekursiv aufbauen lässt. In Matlab:
A = 1; result2fig(A) % Anfang: einmal klicken
A = [ A zeros(size(A)) ; A A ]; result2fig(A) % dies wiederholt klicken
Die Matrix entspricht dem Sirpinski-Dreieck, das ein einfaches Beispiel eines exakten Fraktals ist:
for k=1:8 demosirpinski(k); end
Wir benötigen nirgends in diesem Skript Kenntnisse über Fraktale. Dennoch nehmen wir dieses Beispiel als Anlass zur Erläuterung. Die Anzahl Z der Einsen nimmt bei der Verdopplung der Spalten- bzw. Zeilenzahl der Matrix A nicht mit einer Potenz von 2 zu wie dies bei Längen, Flächen und Rauminhalten der Fall ist (Dimension = 1, 2 bzw. 3), sondern nach
Z(2m) = 3 Z(m) = 2d Z(m) mit d = ln(3) / ln(2) = 1.585
Die Dimension d ist also gebrochen, daher die Bezeichnung Fraktal.
Die Matrix A ist zu sich selbst invers. Wir beweisen dies durch Induktion:
(1) Für 0 Variable gilt A(0) = 1 und folglich A(0)*A(0) = 1 . Die Behauptung gilt also für diesen Fall.
(2) Die Behauptung gelte für n Variable, also ist A(n)*A(n) = I , wo I eine Einheitsmatrix entsprechender Größe ist. Dann hat A(n+1) die vier Blockmatrizen
A(n) O A(n) A(n)
Diese Matrix mit sich selbst multipliziert ergibt die Blockmatrizen
A(n)*A(n) O O A(n)*A(n)
Die Blockmatrizen auf der Hauptdiagonalen sind wegen der Induktionsvorausssetzung Einheitsmatrizen. Also ist auch die gesamte Matrix eine Einheitsmatrix. Damit ist die behauptung für alle natürlichen n bewiesen.
Als Konsequenz ergit sich, dass sowohl
r = A*f
wie auch
f = A*r
gilt.
Transformationen zwischen den verschiedenen Darstellungen können in Handarbeit nach oben beschriebenem Verfahren durchgeführt werden. Einfacher ist die Benutzung der folgenden Funktionen
hilfe( 'binexp2bintab3' )
hilfe( 'binexp2rmexp' )
hilfe( 'binexp2dnfexp' )
hilfe( 'binexp2knfexp' )
hilfe( 'binexp2rmexp' )
hilfe( 'bintab2bdd' )
hilfe( 'bintab2dnfexp' )
hilfe( 'bintab2knfexp' )
hilfe( 'bintab2rmexp' )
Als Beispiel nehmen wir die Ermittlung von DNF, KNF und Reed-Muller-Form für eine als schaltalgebraischer Ausdruck gegebene Funktion mit NICHT (~) , UND (&) , ODER (|) und XOR (+) :
binexp2dnfexp( 'c | (~a&b) | c+d' ,{'a';'b';'c';'d'}) % die DNF
binexp2knfexp( 'c | (~a&b) | c+d' ,{'a';'b';'c';'d'}) % die KNF
binexp2rmexp( 'c | (~a&b) | c+d' ,{'a';'b';'c';'d'}) % die Reed-Muller-Form
Auch der Binärbaum lässt sich einfach darstellen:
t = binexp2bintab3(f,v); % Funktionstabelle bintreegraph(reducebintree(bintab2bintree(t)),v)