Función booleana

Una función booleana puede tener diversas propiedades: ^{[ 7 ]}

• Constante : Siempre es verdadera o siempre falsa, independientemente de sus argumentos.
• Monótono : para cualquier combinación de valores de argumentos, cambiar un argumento de falso a verdadero solo puede provocar que la salida cambie de falso a verdadero, y no de verdadero a falso. Se dice que una función es monótona con respecto a una variable si es monótona con respecto a los cambios en dicha variable.
• Lineal : para cada variable, invertir el valor de la variable siempre produce una diferencia en el valor de verdad o nunca produce una diferencia (una función de paridad ).
• Simétrico : el valor no depende del orden de sus argumentos.
• Lectura única : Se puede expresar con conjunción , disyunción y negación con una sola instancia de cada variable.
• Equilibrada : si su tabla de verdad contiene la misma cantidad de ceros y unos. El peso de Hamming de la función es la cantidad de unos en la tabla de verdad.
• Bent : todas sus derivadas están equilibradas (el espectro de autocorrelación es cero).
• Correlación inmune al orden m : si la salida no está correlacionada con todas las combinaciones (lineales) de como máximo m argumentos.
• Evasivo : si la evaluación de la función siempre requiere el valor de todos los argumentos.
• Una función booleana es una función de Sheffer si puede utilizarse para crear (por composición) cualquier función booleana arbitraria (véase completitud funcional ).
• El grado algebraico de una función es el orden del monomio de mayor orden en su forma normal algebraica.

La complejidad de los circuitos intenta clasificar las funciones booleanas en función del tamaño o la profundidad de los circuitos que pueden calcularlas.

Una función booleana puede descomponerse utilizando el teorema de expansión de Boole en cofactores de Shannon positivos y negativos ( expansión de Shannon ), que son las funciones ( k -1)-arias resultantes de fijar uno de los argumentos (a 0 o 1). Las funciones k -arias generales obtenidas al imponer una restricción lineal sobre un conjunto de entradas (un subespacio lineal) se conocen como subfunciones . ^{[ 8 ]}

La derivada booleana de la función respecto a uno de los argumentos es una función ( k -1)-aria que es verdadera cuando la salida de la función es sensible a la variable de entrada elegida; es la operación XOR de los dos cofactores correspondientes. Una derivada y un cofactor se utilizan en una expansión de Reed-Muller . El concepto puede generalizarse como una derivada k -aria en la dirección dx, obtenida como la diferencia (XOR) de la función en x y x + dx. ^{[ 8 ]}

La transformada de Möbius (o transformada de Boole-Möbius ) de una función booleana es el conjunto de coeficientes de su polinomio ( forma normal algebraica ), como función de los vectores exponenciales monomiales. Es una transformada autoinversa . Se puede calcular eficientemente usando un algoritmo mariposa (" Transformada rápida de Möbius "), análogo a la transformada rápida de Fourier . ^{[ 9 ]} Las funciones booleanas coincidentes son iguales a su transformada de Möbius, es decir, los valores de su tabla de verdad (minterm) son iguales a sus coeficientes algebraicos (monomiales). ^{[ 10 ]} Hay 2^2^( k −1 ) funciones coincidentes de k argumentos. ^{[ 11 ]}

La transformada de Walsh de una función booleana es una función entera k-aria que proporciona los coeficientes de una descomposición en funciones lineales ( funciones de Walsh ), análoga a la descomposición de funciones de valor real en armónicos mediante la transformada de Fourier . Su cuadrado es el espectro de potencia o espectro de Walsh . El coeficiente de Walsh de un vector de bits es una medida de la correlación de ese bit con la salida de la función booleana. El coeficiente de Walsh máximo (en valor absoluto) se conoce como la linealidad de la función. ^{[ 8 ]} El mayor número de bits (orden) para el cual todos los coeficientes de Walsh son 0 (es decir, las subfunciones están equilibradas) se conoce como resiliencia , y se dice que la función es inmune a la correlación para ese orden. ^{[ 8 ]} Los coeficientes de Walsh juegan un papel clave en el criptoanálisis lineal .

La autocorrelación de una función booleana es una función entera k-aria que da la correlación entre un cierto conjunto de cambios en las entradas y la salida de la función. Para un vector de bits dado, está relacionada con el peso de Hamming de la derivada en esa dirección. El coeficiente de autocorrelación máximo (en valor absoluto) se conoce como el indicador absoluto . ^{[ 7 ] [ 8 ]} Si todos los coeficientes de autocorrelación son 0 (es decir, las derivadas están equilibradas) para un cierto número de bits, entonces se dice que la función satisface el criterio de propagación hasta ese orden; si todos son cero, entonces la función es una función bent . ^{[ 12 ]} Los coeficientes de autocorrelación juegan un papel clave en el criptoanálisis diferencial .

Los coeficientes de Walsh de una función booleana y sus coeficientes de autocorrelación están relacionados por el equivalente del teorema de Wiener-Khinchin , que establece que la autocorrelación y el espectro de potencia son un par transformado de Walsh. ^{[ 8 ]}

Cualquier función booleana${\displaystyle f(x):\{0,1\}^{n}\rightarrow \{0,1\}}$puede extenderse (interpolarse) de forma única al dominio real mediante un polinomio multilineal en${\displaystyle \mathbb {R} ^{n}}$, construida sumando los valores de la tabla de verdad multiplicados por polinomios indicadores :$${\displaystyle f^{*}(x)=\sum _{a\in {\{0,1\}}^{n}}f(a)\prod _{i:a_{i}=1}x_{i}\prod _{i:a_{i}=0}(1-x_{i})}$$Por ejemplo, la extensión de la función XOR binaria.${\displaystyle x\oplus y}$es$${\displaystyle 0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy}$$lo cual es igual a$${\displaystyle x+y-2xy}$$Otros ejemplos son la negación (${\displaystyle 1-x}$), Y (${\displaystyle xy}$) y O (${\displaystyle x+y-xy}$Cuando todos los operandos son independientes (no comparten variables), la forma polinómica de una función se puede encontrar aplicando repetidamente los polinomios de los operadores en una fórmula booleana. Cuando los coeficientes se calculan módulo 2, se obtiene la forma normal algebraica ( polinomio de Zhegalkin ).

Se pueden obtener expresiones directas para los coeficientes del polinomio tomando la derivada adecuada:$${\displaystyle {\begin{array}{lcl}f^{*}(00)&=&(f^{*})(00)&=&f(00)\\f^{*}(01)&=&(\partial _{1}f^{*})(00)&=&-f(00)+f(01)\\f^{*}(10)&=&(\partial _{2}f^{*})(00)&=&-f(00)+f(10)\\f^{*}(11)&=&(\partial _{1}\partial _{2}f^{*})(00)&=&f(00)-f(01)-f(10)+f(11)\\\end{array}}}$$Esto se generaliza como la inversión de Möbius del conjunto parcialmente ordenado de vectores de bits:$${\displaystyle f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)}$$dónde${\displaystyle |a|}$denota el peso del vector de bits${\displaystyle a}$. Tomada módulo 2, esta es la transformada de Möbius booleana , que da los coeficientes de la forma normal algebraica :$${\displaystyle {\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)}$$En ambos casos, la suma se toma sobre todos los vectores de bits a cubiertos por m , es decir, los bits "uno" de a forman un subconjunto de los bits uno de m .

Cuando el dominio se restringe al hipercubo n-dimensional${\displaystyle [0,1]^{n}}$, el polinomio${\displaystyle f^{*}(x):[0,1]^{n}\rightarrow [0,1]}$Proporciona la probabilidad de un resultado positivo cuando la función booleana f se aplica a n variables aleatorias independientes ( Bernoulli ), con probabilidades individuales x . Un caso especial de este hecho es el lema de acumulación para funciones de paridad . La forma polinómica de una función booleana también puede utilizarse como su extensión natural a la lógica difusa .

A menudo, el dominio booleano se toma como${\displaystyle \{-1,1\}}$, donde falso ("0") se asigna a 1 y verdadero ("1") a −1 (véase Análisis de funciones booleanas ). El polinomio correspondiente a${\displaystyle g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}}$entonces viene dado por:$${\displaystyle g^{*}(x)=\sum _{a\in {\{-1,1\}}^{n}}g(a)\prod _{i:a_{i}=-1}{\frac {1-x_{i}}{2}}\prod _{i:a_{i}=1}{\frac {1+x_{i}}{2}}}$$El uso del dominio booleano simétrico simplifica ciertos aspectos del análisis , ya que la negación corresponde a multiplicar por −1 y las funciones lineales son monomios (XOR es multiplicación). Esta forma polinómica corresponde, por lo tanto, a la transformada de Walsh (en este contexto también conocida como transformada de Fourier ) de la función (véase más arriba). El polinomio también tiene la misma interpretación estadística que el del dominio booleano estándar, excepto que ahora trata con los valores esperados.${\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}$(Véase el lema de acumulación para un ejemplo).