Boolescher Term, Boolesche Formel, die kleinste Teilmenge \({{\mathfrak{A}}}_{n}\) der endlichen Folgen über dem Alphabet \(\{0,1,{x}_{1},\ldots, {x}_{n}\}\cup \{\wedge, \vee, ⌝,(,)\}\), die den Eigenschaften (a), (b) und (c) genügt.

1. Jedes Zeichen aus {0, 1, x₁, …, x_n} ist Element von \({{\mathfrak{A}}}_{n}\).
2. Sind \({{\mathscr{W}}}_{1},\ldots, {{\mathscr{W}}}_{k}\) Elemente von \({{\mathfrak{A}}}_{n}\), so auch die endliche Folge \(({{\mathscr{W}}}_{1}\wedge \ldots \wedge {{\mathscr{W}}}_{k})\), die Konjunktion der Booleschen Ausdrücke \({{\mathscr{W}}}_{1},\ldots, {{\mathscr{W}}}_{k}\) oder Produkt der Booleschen Ausdrücke \({{\mathscr{W}}}_{1},\ldots, {{\mathscr{W}}}_{k}\) genannt wird, und die endliche Folge \(({{\mathscr{W}}}_{1}\vee \ldots \vee {{\mathscr{W}}}_{k})\), die Disjunktion der Booleschen Ausdrücke \({{\mathscr{W}}}_{1},\ldots, {{\mathscr{W}}}_{k}\) oder Summe der Booleschen Ausdrücke \({{\mathscr{W}}}_{1},\ldots, {{\mathscr{W}}}_{k}\) genannt wird.
3. Ist \({\mathscr{W}}\) Element von \({{\mathfrak{A}}}_{n}\), so auch die endliche Folge \(\bar{{\mathscr{W}}}\), die in der Regel durch \(\bar{{\mathscr{W}}}\) dargestellt und als Komplement von w bezeichnet wird.

Zumeist ist vereinbart, daß das Symbol \(⌝\) stärker als das Symbol ∧ bindet und dieses wiederum stärker als ∨ bindet. Dies erlaubt es, nicht alle Klammern hinschreiben zu müssen.

Boolesche Ausdrücke über den Variablen \({x}_{1},\ldots, {x}_{n}\) dienen insbesondere zur Darstellung Boolescher Funktionen. Die Interpretation erfolgt durch die Abbildung \(\phi :{{\mathfrak{A}}}_{n}\to {{\mathfrak{B}}}_{n}({\{0,1\}}^{n})\), die die über den Variablen \({x}_{1},\ldots, {x}_{n}\) definierten Booleschen Ausdrücke in die Boolesche Algebra der Booleschen Funktionen \(f:{\{0,1\}}^{n}\to \{0,1\}\) abbildet. Sie ist definiert durch

1. \begin{eqnarray}\forall \alpha \in {\{0,1\}}^{n}:\phi (0)(\alpha )=0,\end{eqnarray}

\begin{eqnarray}\forall {{\mathscr{W}}}_{1},\ldots, {{\mathscr{W}}}_{k}\in {{\mathfrak{A}}}_{n}:\phi (({{\mathscr{W}}}_{1}\vee \ldots \vee {{\mathscr{W}}}_{k}))=\phi ({{\mathscr{W}}}_{1})\vee \ldots \vee \phi ({{\mathscr{W}}}_{k}),\end{eqnarray}

\begin{eqnarray}\forall {\mathscr{W}}\in {{\mathfrak{A}}}_{n}:\phi (\bar{{\mathscr{W}}})=\phi (\bar{{\mathscr{W}}})\end{eqnarray}

.

Verwendet wird in diesem Zusammenhang die Sprechweise ist ein Boolescher Ausdruck der Booleschen Funktion \(\phi ({\mathscr{W}})\)“ und „\(\phi ({\mathscr{W}})\) ist die durch den Booleschen Ausdruck w dargestellte Boolesche Funktion”. Stellen zwei Boolesche Ausdrücke die gleiche Boolesche Funktion dar, so spricht man von äquivalenten Booleschen Ausdrücken. Ein Verfahren, das entscheidet, ob zwei gegebene Boolesche Ausdrücke äquivalent sind, wird Äquivalenztest genannt.

Die Kosten eines Booleschen Ausdrucks spiegeln die Fläche wider, die eine Eins-zu-Eins Realisierung dieses Booleschen Ausdrucks durch einen kombinatorischen logischen Schaltkreis benötigt. In der Regel wird der Flächenbedarf durch die Anzahl der verwendeten Grundbausteine (Bausteinbibliothek) bestimmt, sodaß die Kosten costs(w) eines Booleschen Ausdrucks \({\mathscr{W}}\in {{\mathfrak{A}}}_{n}\) als die Anzahl der in w enthaltenen Zeichen ∨, ∧ und ⌝ definiert sind. Sie geben die Anzahl der Grundbausteine mit einem oder zwei Eingängen an, die benötigt werden, um den Booleschen Ausdruck Eins-zuEins als mehrstufigen kombinatorischen logischen Schaltkreis zu realisieren. Abweichend von dieser allgemeinen Definition sind die Kosten eines Booleschen Polynoms p definiert als die Anzahl der in p enthaltenen Booleschen Monome, wenn programmierbare logische Felder (logischer Schaltkreis) die Zieltechnologie sind.

Im Rahmen verschiedener Anwendungen Boolescher Ausdrücke wird manchmal auch eine verallgemeinerte Definition für Boolesche Ausdrücke benutzt. Gegeben ist hierbei eine Bausteinbibliothek Ω. Die Menge \({{\mathfrak{A}}}_{n}(\Omega )\) der sog. Booleschen Ω-Ausdrücke ist gegeben durch

\begin{eqnarray}\mathop{\displaystyle \cup }\limits_{i\ge 0}{{\mathfrak{A}}}_{n}^{(i)}(\Omega )\end{eqnarray}

mit

\begin{eqnarray}{{\mathfrak{A}}}_{n}^{(0)}(\Omega )=\{0,1,{x}_{1},\ldots, {x}_{n}\}\end{eqnarray}

und

\begin{eqnarray}{{\mathfrak{A}}}_{n}^{(i)}(\Omega ) & = & {{\mathfrak{A}}}_{n}^{(i-1)}(\Omega ){\displaystyle \cup }^{\text{}}\\ & & \{\omega ({{\mathscr{W}}}_{1},\ldots, {{\mathscr{W}}}_{k})|\omega \in \Omega {\displaystyle \cap }^{\text{}}{{\mathfrak{B}}}_{k}({\{0,1\}}^{k})\\ & & \text{und}\text{\hspace{0.17em}}{{\mathscr{W}}}_{1},\ldots, {{\mathscr{W}}}_{K}\in {{\mathfrak{A}}}_{n}^{(i-1)}(\Omega )\}\end{eqnarray}

für i ≥ 1.