Función booleana

Función que devuelve uno de solo dos valores

Diagrama de decisión binaria y tabla de verdad de una función booleana ternaria

En matemáticas , una función booleana es una función cuyos argumentos y resultados asumen valores de un conjunto de dos elementos (normalmente {verdadero, falso}, {0,1} o {-1,1}). ^{[1] [2]} Los nombres alternativos son función de conmutación , utilizada especialmente en la literatura informática más antigua , ^{[3] [4]} y función de verdad (o función lógica) , utilizada en lógica . Las funciones booleanas son el tema del álgebra de Boole y la teoría de conmutación . ^[5]

Una función booleana tiene la forma , donde se conoce como el dominio booleano y es un entero no negativo llamado aridad de la función. En el caso donde , la función es un elemento constante de . Una función booleana con múltiples salidas, con es una función booleana vectorial o con valores vectoriales (una S-box en criptografía simétrica ). ^[6] ${\displaystyle f:\{0,1\}^{k}\to \{0,1\}}$ ${\displaystyle \{0,1\}}$ ${\displaystyle k}$ ${\displaystyle k=0}$ ${\displaystyle \{0,1\}}$ ${\displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}}$ ${\displaystyle m>1}$

Hay diferentes funciones booleanas con argumentos; iguales al número de tablas de verdad diferentes con entradas. ${\displaystyle 2^{2^{k}}}$ ${\displaystyle k}$ ${\displaystyle 2^{k}}$

Toda función booleana -aria puede expresarse como una fórmula proposicional en variables , y dos fórmulas proposicionales son lógicamente equivalentes si y solo si expresan la misma función booleana. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle x_{1},...,x_{k}}$

Ejemplos

Las dieciséis funciones booleanas binarias

Las funciones booleanas simétricas rudimentarias ( conectivas lógicas o puertas lógicas ) son:

• NO , negación o complemento : recibe una entrada y devuelve verdadero cuando esa entrada es falsa ("no")
• AND o conjunción : verdadero cuando todas las entradas son verdaderas ("ambas")
• OR o disyunción : verdadero cuando cualquier entrada es verdadera ("cualquiera")
• XOR o disyunción exclusiva : verdadero cuando una de sus entradas es verdadera y la otra es falsa ("no igual")
• Trazo NAND o Sheffer : verdadero cuando no es el caso de que todas las entradas sean verdaderas ("no ambas")
• NOR o nor lógico : verdadero cuando ninguna de las entradas es verdadera ("ninguna")
• XNOR o igualdad lógica : verdadero cuando ambas entradas son iguales ("iguales")

Un ejemplo de una función más complicada es la función mayoritaria (de un número impar de entradas).

Representación

Una función booleana representada como un circuito booleano

Una función booleana se puede especificar de varias maneras:

• Tabla de verdad : enumera explícitamente su valor para todos los valores posibles de los argumentos.
  • Diagrama de Marquand: valores de la tabla de verdad dispuestos en una cuadrícula bidimensional (utilizados en un mapa de Karnaugh )
  • Diagrama de decisión binaria , que enumera los valores de la tabla de verdad en la parte inferior de un árbol binario
  • Diagrama de Venn , que representa los valores de la tabla de verdad como una coloración de las regiones del plano.

Algebraicamente, como fórmula proposicional utilizando funciones booleanas rudimentarias:

• Forma normal de negación , una mezcla arbitraria de AND y OR de los argumentos y sus complementos
• Forma normal disyuntiva , como un OR de AND de los argumentos y sus complementos
• Forma normal conjuntiva , como un AND de OR de los argumentos y sus complementos
• Forma normal canónica , una fórmula estandarizada que identifica de forma única la función:
  • Forma normal algebraica o polinomio de Zhegalkin , como un XOR de AND de los argumentos (no se permiten complementos)
  • Forma normal disyuntiva completa (canónica) , un OR de AND que contiene cada argumento o complemento ( minterms )
  • Forma normal conjuntiva completa (canónica) , un AND de OR que contiene cada argumento o complemento ( maxterms )
  • Forma canónica de Blake , el OR de todos los implicantes primos de la función

Las fórmulas booleanas también se pueden mostrar como un gráfico:

• Grafo acíclico dirigido proposicional
  • Diagrama de circuito digital de puertas lógicas , un circuito booleano
  • Gráfico inversor-AND , que utiliza solo AND y NOT

Para optimizar los circuitos electrónicos, las fórmulas booleanas se pueden minimizar utilizando el algoritmo de Quine-McCluskey o el mapa de Karnaugh .

Análisis

Propiedades

Una función booleana puede tener una variedad de propiedades: ^[7]

• Constante : siempre es verdadera o siempre falsa independientemente de sus argumentos.
• Monótona : para cada combinación de valores de argumentos, cambiar un argumento de falso a verdadero solo puede hacer que la salida cambie de falso a verdadero y no de verdadero a falso. Se dice que una función es monótona en una determinada variable si es monótona con respecto a los cambios en esa variable.
• Lineal : para cada variable, invertir el valor de la variable siempre supone una diferencia en el valor de verdad o nunca supone 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 única 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.
• Doblado : sus derivadas están todas balanceadas (el espectro de autocorrelación es cero)
• Correlación inmune a m- ésimo orden: si la salida no está correlacionada con todas las combinaciones (lineales) de como máximo m argumentos
• Evasiva : 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 se puede utilizar para crear (por composición) cualquier función booleana arbitraria (ver completitud funcional ).
• El grado algebraico de una función es el orden del monomio de orden más alto en su forma normal algebraica.

La complejidad del circuito intenta clasificar las funciones booleanas con respecto al tamaño o la profundidad de los circuitos que pueden calcularlas.

Funciones derivadas

Una función booleana puede descomponerse mediante 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 que resultan de fijar uno de los argumentos (a cero o a uno). Las funciones (k-arias) generales que se obtienen al imponer una restricción lineal a un conjunto de entradas (un subespacio lineal) se conocen como subfunciones . ^[8]

La derivada booleana de la función para 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 el XOR de los dos cofactores correspondientes. Una derivada y un cofactor se utilizan en una expansión de Reed-Muller . El concepto se puede generalizar 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 ), en función de los vectores exponentes monomiales. Es una transformada autoinversa . Se puede calcular de manera eficiente utilizando un algoritmo de 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, sus valores de tabla de verdad (minterm) son iguales a sus coeficientes algebraicos (monomiales). ^[10] Hay 2^2^( k −1) funciones coincidentes de k argumentos. ^[11]

Análisis criptográfico

La transformada de Walsh de una función booleana es una función de valor entero k-ario que da 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 por la transformada de Fourier . Su cuadrado es el espectro de potencia o espectro de Walsh . El coeficiente de Walsh de un vector de un solo bit 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 número más alto 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 a 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 de valor entero k-ario que proporciona 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, se dice que la función satisface el criterio de propagación a ese orden; si todos son cero, entonces la función es una función doblada . ^[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 de transformadas de Walsh. ^[8]

Tabla de aproximación lineal

Estos conceptos se pueden extender de forma natural a funciones booleanas vectoriales considerando sus bits de salida ( coordenadas ) individualmente, o más a fondo, observando el conjunto de todas las funciones lineales de bits de salida, conocidas como sus componentes . ^[6] El conjunto de transformadas de Walsh de los componentes se conoce como Tabla de Aproximación Lineal (LAT) ^{[13] [14]} o matriz de correlación ; ^{[15] [16]} describe la correlación entre diferentes combinaciones lineales de bits de entrada y salida. El conjunto de coeficientes de autocorrelación de los componentes es la tabla de autocorrelación , ^[14] relacionada por una transformada de Walsh de los componentes ^{[17] con la} Tabla de Distribución de Diferencias (DDT) ^{[13] [14]} más ampliamente utilizada que enumera las correlaciones entre las diferencias en los bits de entrada y salida (ver también: S-box ).

Forma polinómica real

Sobre la unidad hipercubo

Cualquier función booleana puede extenderse de forma única (interpolada) al dominio real mediante un polinomio multilineal en , construido sumando los valores de la tabla de verdad multiplicados por polinomios indicadores : Por ejemplo, la extensión de la función binaria XOR es que es igual a Otros ejemplos son negación ( ), AND ( ) y OR ( ). 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 ). ${\displaystyle f(x):\{0,1\}^{n}\rightarrow \{0,1\}}$ ${\displaystyle \mathbb {R} ^{n}}$ $${\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})}$$ ${\displaystyle x\oplus y}$ $${\displaystyle 0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy}$$ $${\displaystyle x+y-2xy}$$ ${\displaystyle 1-x}$ ${\displaystyle xy}$ ${\displaystyle x+y-xy}$

Las expresiones directas para los coeficientes del polinomio se pueden derivar tomando una derivada apropiada: esto se generaliza como la inversión de Möbius del conjunto parcialmente ordenado de vectores de bits: donde denota el peso del vector de bits . Tomada módulo 2, esta es la transformada booleana de Möbius , que da los coeficientes de la forma normal algebraica : 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 . $${\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}}}$$ $${\displaystyle f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)}$$ ${\displaystyle |a|}$ ${\displaystyle a}$ $${\displaystyle {\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)}$$

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

Sobre el hipercubo simétrico

A menudo, el dominio booleano se toma como , con falso ("0") mapeándose a 1 y verdadero ("1") a -1 (ver Análisis de funciones booleanas ). El polinomio correspondiente a se da entonces por: 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 entonces a la transformada de Walsh (en este contexto también conocida como transformada de Fourier ) de la función (ver 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 (ver el lema de apilamiento para un ejemplo). ${\displaystyle \{-1,1\}}$ ${\displaystyle g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}}$ $${\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}}}$$ ${\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}$

Aplicaciones

Las funciones booleanas juegan un papel básico en cuestiones de teoría de la complejidad así como en el diseño de procesadores para computadoras digitales , donde se implementan en circuitos electrónicos utilizando puertas lógicas .

Las propiedades de las funciones booleanas son fundamentales en criptografía , particularmente en el diseño de algoritmos de clave simétrica (véase el cuadro de sustitución ).

En la teoría de juegos cooperativos , las funciones booleanas monótonas se denominan juegos simples (juegos de votación); esta noción se aplica para resolver problemas en la teoría de la elección social .

Véase también

• Portal de filosofía

• Función pseudo-booleana
• Función con valor booleano
• Temas de álgebra de Boole
• Álgebra de conjuntos
• Modelo de árbol de decisión
• Función indicadora
• Conjunto firmado

Referencias

1. "Función booleana - Enciclopedia de Matemáticas". encyclopediaofmath.org . Consultado el 3 de mayo de 2021 .
2. Weisstein, Eric W. "Función booleana". mathworld.wolfram.com . Consultado el 3 de mayo de 2021 .
3. "función de conmutación". TheFreeDictionary.com . Consultado el 3 de mayo de 2021 .
4. Davies, DW (diciembre de 1957). "Funciones de conmutación de tres variables". IRE Transactions on Electronic Computers . EC-6 (4): 265–275. doi :10.1109/TEC.1957.5222038. ISSN  0367-9950.
5. McCluskey, Edward J. (1 de enero de 2003), "Teoría de la conmutación", Enciclopedia de informática , GBR: John Wiley and Sons Ltd., págs. 1727-1731, ISBN 978-0-470-86412-8, consultado el 3 de mayo de 2021
6. Carlet, Claude. "Funciones booleanas vectoriales para criptografía" (PDF) . Universidad de París . Archivado (PDF) desde el original el 17 de enero de 2016.
7. "Funciones booleanas — Manual de referencia de Sage 9.2: Criptografía". doc.sagemath.org . Consultado el 1 de mayo de 2021 .
8. Tarannikov, Yuriy; Korolev, Peter; Botev, Anton (2001). "Coeficientes de autocorrelación e inmunidad de correlación de funciones booleanas". En Boyd, Colin (ed.). Avances en criptología — ASIACRYPT 2001. Apuntes de clase en informática. Vol. 2248. Berlín, Heidelberg: Springer. págs. 460–479. doi : 10.1007/3-540-45682-1_27 . ISBN. 978-3-540-45682-7.
9. Carlet, Claude (2010), "Funciones booleanas para criptografía y códigos de corrección de errores" (PDF) , Modelos y métodos booleanos en matemáticas, informática e ingeniería , Enciclopedia de matemáticas y sus aplicaciones, Cambridge: Cambridge University Press, págs. 257–397, ISBN 978-0-521-84752-0, consultado el 17 de mayo de 2021
10. Pieprzyk, Josef; Wang, Huaxiong; Zhang, Xian-Mo (1 de mayo de 2011). "Transformadas de Möbius, funciones booleanas coincidentes y propiedad de no coincidencia de funciones booleanas". Revista internacional de matemáticas informáticas . 88 (7): 1398–1416. doi :10.1080/00207160.2010.509428. ISSN  0020-7160. S2CID  9580510.
11. Nitaj, Abderrahmane; Susilo, Willy; Tonien, Joseph (1 de octubre de 2017). "Producto de Dirichlet para funciones booleanas". Revista de Matemática Aplicada y Computación . 55 (1): 293–312. doi :10.1007/s12190-016-1037-4. ISSN  1865-2085. S2CID  16760125.
12. Canteaut, Anne; Carlet, Claude; Charpin, Pascale; Fontaine, Caroline (14 de mayo de 2000). "Características de propagación e inmunidad a la correlación de funciones booleanas altamente no lineales". Actas de la 19.ª Conferencia internacional sobre teoría y aplicación de técnicas criptográficas . EUROCRYPT'00. Brujas, Bélgica: Springer-Verlag: 507–522. ISBN 978-3-540-67517-4.
13. Heys, Howard M. "Un tutorial sobre criptoanálisis lineal y diferencial" (PDF) . Archivado (PDF) desde el original el 17 de mayo de 2017.
14. "S-Boxes y sus representaciones algebraicas — Manual de referencia de Sage 9.2: Criptografía". doc.sagemath.org . Consultado el 4 de mayo de 2021 .
15. Daemen, Juana; Govaerts, René; Vandewalle, Joos (1994). "Matrices de correlación". En Preneel, Bart (ed.). Cifrado rápido de software: segundo taller internacional. Lovaina, Bélgica, 14 a 16 de diciembre de 1994, Actas . Apuntes de conferencias sobre informática. vol. 1008. Saltador. págs. 275–285. doi : 10.1007/3-540-60590-8_21 .
16. Daemen, Joan (10 de junio de 1998). "Capítulo 5: Propagación y correlación - Anexo a la propuesta AES de Rijndael" (PDF) . NIST . Archivado (PDF) desde el original el 23 de julio de 2018.
17. Nyberg, Kaisa (1 de diciembre de 2019). "Tablas de autocorrelación extendida y de boomerang y vínculos entre propiedades de no linealidad de funciones booleanas vectoriales" (PDF) . Archivado (PDF) desde el original el 2 de noviembre de 2020.

Lectura adicional

• Crama, Yves; Hammer, Peter L. (2011), Funciones booleanas: teoría, algoritmos y aplicaciones , Cambridge University Press, doi :10.1017/CBO9780511852008, ISBN 9780511852008
• "Función booleana", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Janković, Dragan; Stanković, Radomir S.; Moraga, Claudio (noviembre de 2003). "Optimización de expresiones aritméticas utilizando la propiedad de polaridad dual". Revista Serbia de Ingeniería Eléctrica . 1 (71–80, número 1): 71–80. doi : 10.2298/SJEE0301071J .
• Arnold, Bradford Henry (1 de enero de 2011). Lógica y álgebra de Boole. Courier Corporation. ISBN 978-0-486-48385-6.
• Mano, MM; Ciletti, MD (2013), Diseño digital , Pearson