Boolesche Funktion \({I}_{k,j}^{(n)}\) für Zahlen k, j, n ∈ ℕ und k ≤ j ≤ n mit \begin{array}{l}{I}_{k,j}^{(n)}:{\{0,1\}}^n\to \{0,1\}\\ {I}_{k,j}^{(n)}({\alpha }_{1},\ldots, {\alpha }_{n})=1\iff k\le \displaystyle \sum _{i=1}^{n}{\alpha }_{i}\le j.\end{array}

Intervallfunktionen sind total symmetrische Boolesche Funktionen. Sie werden zur Darstellung beliebiger total symmetrischer Boolescher Funktionen benutzt. In diesem Zusammenhang ist eine maximale Intervallfunktion einer total symmetrischen Booleschen Funktion f eine Intervallfunktion \({I}_{k,j}^{(n)}\), für die \begin{eqnarray}{I}_{k,j}^{(n)}(\alpha )\le f(\alpha )\end{eqnarray} für alle α ∈ {0, 1}ⁿ gilt, und die maximal in dem Sinne ist, daß weder die Intervallfunktion \({I}_{k-1,j}^{(n)}\) noch die Intervallfunktion \({I}_{k,j+1}^{(m)}\) komponentenweise kleiner gleich f ist. Es gilt der Satz:

Jede total symmetrische Boolesche Funktion läßt sich eindeutig alsDisjunktion maximaler Intervallfunktionen darstellen.

Die Primimplikanten einer Intervallfunktion \({I}_{k,j}^{(n)}:{\{0,1\}}^{n}\to \{0,1\}\) sind die Booleschen Monome über den Variablen x₁, …, x_n die genau aus k positiven und n − j negativen Booleschen Literalen bestehen.

Jedes Minimalpolynom von \({I}_{k,j}^{(n)}\) besteht aus genau \begin{eqnarray}\max \{\left(\begin{array}{c}n\\ k\end{array}\right),\left(\begin{array}{c}n\\ n-j\end{array}\right)\}\end{eqnarray} Primimplikanten.

[1] Wegener, I.: Effiziente Algorithmen für grundlegende Funktionen. B.G. Teubner Verlag Stuttgart, 1989.