7.2 Vektorraum der

Schaltfunktionen

T_n sei die Menge aller Schaltfunktionen mit n Variablen und B = GF(2) der endliche Körper mit zwei Elementen und den inneren Verknüpfungen exklusives Oder bzw. Und , die hier mit den Infixsymbolen + und * notiert werden sollen. Wir definieren nun die Addition von Schaltfunktionen f,g,hT_n sowie das Produkt einer Schaltfunktion fT_n mit einem Skalar λB :

     h = f  g  ,   wo   h(x) = f(x) + g(x)   xBn            

     p = λ  f  ,   wo  p(x) = λ * f(x)   xBn   

und bezeichnen als Infixsymbole die neu definierten Operationen auf der Menge T_n , + und * die inneren Verknüpfungen von B . Mit diesen Definitionen ist die Menge T_n der Schaltfunktionen von n Variablen ein Vektorraum. Dem Leser sei der Beweis der Axiome V₁ bis V₄ als Übung empfohlen.

Eine Schaltfunktion fT_n , für die gilt

f(x) = 1 (0) für genau ein xBⁿ und
f(y) = 0 (1) y≠x , yBⁿ

nennen wir eine Einspunktfunktion (Nullpunktfunktion) oder in anderem Zusammenhang Minterm (Maxterm).

Die folgende Tabelle stellt sämtliche Einspunktfunktionen aus dem T₃ dar:

Eine Einspunktfunktion lässt sich nicht als Linearkombination der anderen Einspunktfunktionen darstellen, da diese durchweg für den Variablenvektor, bei dem die darzustellende Einspunktfunktion gleich 1 ist, verschwinden. Die 2ⁿ Einspunktfunktionen sind damit linear unabhängig und spannen den T_n auf. Sie stellen also eine Basis dar. Jede Schaltfunktion fT_n lässt sich in der Form

     2n                                    
 f = Σ fi bi(n)   
     i=1                                    

als Linearkombination der Einspunktfunktionen darstellen. Die f_iB (i=1,...,2ⁿ) bilden den Komponentenvektor von f bezüglich der Basis der Einspunktfunktionen. Er ist identisch mit der rechten Spalte der Funktionstabelle.