Eine vollständige Basis ist eine Menge von boolschen Operatoren, mit der alle nur denkbaren boolschen Funktionen abgebildet werden können. Beispielsweise bilden die Und-, die Oder- und die Nicht-Funktion zusammen eine vollständige Basis. (Ist ja klar, weil jede DNF/KNF auf diesen Operatoren beruht). Ein weiteres Beispiel ist die Xor und die Und-Funktion.