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:
Die binäre Matrix A hat offenbar eine sehr einfache Struktur, die sich rekursiv aufbauen lässt. In Matlab:
Die Matrix entspricht dem Sirpinski-Dreieck, das ein einfaches Beispiel eines exakten Fraktals ist:
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
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 (+) :
Auch der Binärbaum lässt sich einfach darstellen: