Hierbei sind im Folgenden ausschließlich extensionale logische Aussage-Operationen gemeint, also solche, deren Wahrheitsgehalt ausschließlich vom Wahrheitswert der Eingänge abhängt, aber nicht von deren Inhalt. Weiterhin bedeutet 0 = FALSCH, 1 = WAHR.

Negation (${\displaystyle \neg }$)
x	NOT(x)
0	1
1	0

Disjunktion (${\displaystyle \lor }$) x y OR(x,y) 0 0 0 1 0 1 0 1 1 1 1 1

Konjunktion (${\displaystyle \land }$) x y AND(x,y) 0 0 0 1 0 0 0 1 0 1 1 1

Implikation (${\displaystyle \Rightarrow }$) x y IMPL(x,y) 0 0 1 1 0 0 0 1 1 1 1 1

Äquivalenz (${\displaystyle \Leftrightarrow }$) x y NXOR(x,y) 0 0 1 1 0 0 0 1 0 1 1 1

Antivalenz (${\displaystyle \oplus }$) x y XOR(x,y) 0 0 0 1 0 1 0 1 1 1 1 0

Ein Tripel ${\displaystyle (B,+,*)}$ bestehend aus einer Trägermenge ${\displaystyle B=\{0,1\}}$ sowie den Verknüpfungen ${\displaystyle +}$ (ODER), ${\displaystyle *}$ (UND) bezeichnet man als Bool'sche Algebra, falls folgende Axiome erfüllt sind :

• Abgeschlossenheit : ${\displaystyle \forall a,b\in B:a+b\in B,a*b\in B}$
• Kommutativität : ${\displaystyle \forall a,b\in B:a+b=b+a,a*b=b*a}$
• Assoziativität : ${\displaystyle \forall a,b,c\in B:a+(b+c)=(a+b)+c,a*(b*c)=(a*b)*c}$
• Distributivität : ${\displaystyle \forall a,b,c\in B:a+b*c=(a+b)*(a+c),a*(b+c)=a*b+a*c}$
• Neutrale Elemente : ${\displaystyle \forall a\in B:a=0+a,a=1*a}$
• Inverse Elemente : ${\displaystyle \forall a\in B:a+{\overline {a}}=1,a*{\overline {a}}=0}$

Aus den obigen Axiomen lässt sich ein weiteres, für die technische Implementierung Bool'scher Funktionen äußerst wichtiges Gesetz ableiten :

• ${\displaystyle \forall a\in B:a=a+a=a*a}$

Der Beweis über eine Wertetabelle ist jedoch erheblich einfacher und, da es sich um diskrete Mengen handelt auch vollkommen legal.

Des weiteren gilt das Reduktionsgesetz :

• ${\displaystyle \forall a\in B:a+1=1,a*0=0}$

Auch hier ist der Beweis über eine Wertetabelle möglich, er kann - und sollte - aber auch axiomatisch durch logisches Schlussfolgern erfolgen.

Da jede Variable/jedes Literal genau ein Inverses Element besitzt, ist das Inverse des Inversen wieder das Ausgangselement, formal :

• ${\displaystyle \forall x,x_{1},x_{2}\in B:x_{1}={\overline {x}},x_{2}={\overline {x}}\Longrightarrow x_{1}=x_{2}\Longrightarrow {\overline {\overline {x}}}=x}$

Eine Bool'sche Funktion ${\displaystyle f}$ bezeichnet die Abbildung ${\displaystyle f:B^{n}\longrightarrow B}$.

Hat eine Bool'sche Funktion ${\displaystyle n}$ Variablen, so besitzt sie insgesamt ${\displaystyle 2^{n}}$ Funktionswerte.

Hierbei ist die folgende Schreibweise bei Funktionsanwendung der Funktion ${\displaystyle y\longmapsto f(x_{n},...,x_{0})}$ üblich :

• ${\displaystyle f(...,x_{i}=1,...)=f(...+2^{i}+...)}$
• ${\displaystyle f(...,x_{i}=0,...)=f(...+0+...)}$

Unter einem Literal versteht man eine eingebettete Funktionsanwendung auf genau eine Variable. In der Bool'schen Algebra besteht die Menge der Literale ${\displaystyle {\underline {x}}}$ einer Variablen ${\displaystyle x}$ aus der Identität sowie Inversion dieser Variablen, etwas formaler ausgedrückt :

• ${\displaystyle {\underline {x}}=\{x,{\overline {x}}\}}$

Nach Einführung des Literal-Begriffs ist es nun möglich die Funktionaldefinition, also die Definition einer Funktion, welche auf Mengen operiert, vorzunehmen.

Ein Bool'sches Funktional ${\displaystyle f}$ bezeichnet die Abbildung ${\displaystyle f:{\underline {x}}^{n}\longrightarrow B^{n}\longrightarrow B}$.

Folglich gibt es genau ${\displaystyle 2^{n}}$ verschiedene Funktionen und ${\displaystyle 2^{2^{n}}}$ verschiedene Funktionswerte der Variablenanzahl ${\displaystyle n}$.

Analog der Funktionsbezeichnung verwendet man üblicherweise für Bool'sche Funktionalanwendung der Art ${\displaystyle f\longmapsto f({\underline {x_{n}}},...,{\underline {x_{0}}})}$ :

• ${\displaystyle f(...,x_{i},...)=f_{...+2^{i}+...}}$
• ${\displaystyle f(...,{\overline {x_{i}}},...)=f_{...+0+...}}$

Ein Operatorensystem ist genau dann vollständig, falls Negation, Konjunktion, sowie Disjunktion darstellbar sind. Andere Bool'sche Operationen werden hierbei durch Anwendung auf eine Konstante, welche vorher ausgewertet werden muss, eliminiert:

Essentiell für die Konvertierung konjunktiver/disjunktiver Normalformen ist der Shannon'sche Inversionsatz. Dessen einfache Fassung lautet:

• ${\displaystyle {\overline {a\land b}}={\overline {a}}\lor {\overline {b}}}$
• ${\displaystyle {\overline {a\lor b}}={\overline {a}}\land {\overline {b}}}$

Er lässt sich jedoch auch für beliebige Anzahl von Literalen erweitern:

• ${\displaystyle {\overline {\land _{i}x_{i}}}=\lor _{i}{\overline {x_{i}}}}$
• ${\displaystyle {\overline {\lor _{i}x_{i}}}=\land _{i}{\overline {x_{i}}}}$

Ein technisch einfach zu realisierendes und von daher sehr wichtiges Operatorensystem ist das NAND-System. Folgender Abschnitt beschreibt die Herleitung der essentiellen Operationen:

• Negation

Die Negation ist durch Anwendung des Idempotenzgesetzes recht schnell gezeigt :

${\displaystyle {\overline {x}}={\overline {x\land x}}}$

• Disjunktion

Dies ist durch Eindeutigkeit des Inversen Elements, Anwendung des Shannon'schen Inversionssatzes, sowie der Idempotenz einfach hergeleitet:

${\displaystyle x\lor y={\overline {\overline {x\lor y}}}={\overline {{\overline {x}}\land {\overline {y}}}}={\overline {{\overline {x\land x}}\land {\overline {y\land y}}}}}$

• Konjunktion

Analog verhält es sich bei der Konjunktion:

${\displaystyle x\land y={\overline {\overline {x\land y}}}={\overline {{\overline {x\land y}}\land {\overline {x\land y}}}}}$

Ebenfalls einfach zu realisieren sind NOR-Systeme. Nachgewiesen werden die notwendigen Eigenschaften mit Idempotenz, Shannon'schen Inversionssatz, sowie der Eindeutigkeit des Inversen Elements:

• Negation :

${\displaystyle {\overline {x}}={\overline {x\lor x}}}$

• Disjunktion :

${\displaystyle x\lor y={\overline {\overline {x\lor y}}}={\overline {{\overline {x\lor y}}\lor {\overline {x\lor y}}}}}$

• Konjunktion :

${\displaystyle x\land y={\overline {\overline {x\land y}}}={\overline {{\overline {x}}\lor {\overline {y}}}}={\overline {{\overline {x\lor x}}\lor {\overline {y\lor y}}}}}$