wird gegeben durch eine Abbildung \begin{eqnarray}\sigma :{{\mathfrak{B}}}_{n}({\{0, 1\}}^{n})\times X\to U,\end{eqnarray} mit folgenden Eigenschaften:

1. \({{\mathfrak{B}}}_{n}({\{0, 1\}}^{n})=\{f|f:{\{0, 1\}}^{n}\to \{0, 1\}\}\).
2. U ist eine total geordnete Menge.
3. X ist die Menge der Variablen {x₁,…,x_n}.
4. Gilt π(x_i) = x_j für eine Permutation π : X → X und x_i, x_j ∈ X, so gilt

Eine Signatur einer Eingangsvariablen x_i einer Booleschen Funktion f ist eine Beschreibung von x_i, die unabhängig von der Anordnung der Variablen ist. Eine einfache Signatur einer Variablen x_i einer Booleschen Funktion f ist zum Beispiel der satisfy count des positiven Kofaktors \({f}_{{x}_{i}}\).

Signaturen werden im Rahmen der Schaltkreisverifikation eingesetzt, zum Beispiel wenn entschieden werden soll, ob zwei Boolesche Funktionen durch Permutation ihrer Eingangsvariablen ineinander überführt werden können.