Función booleana

Función con dominio {0,1} ^ k para algunos k y con rango {0,1}

Un diagrama de decisión binario y una tabla de verdad de una función booleana ternaria

No confundir con la función binaria .

En matemáticas y lógica , una función booleana es una función cuyos argumentos , así como la función en sí, asumen valores de un conjunto de dos elementos (generalmente {0,1} o {verdadero, falso}). ^{[1] [2]} Un nombre alternativo es función de conmutación , que se utiliza especialmente en la literatura científica de informática más antigua. ^{[3] [4] Las} funciones booleanas son el tema del álgebra booleana y la teoría de conmutación . ^[5]

Una función booleana toma la forma , donde se conoce como dominio booleano y es un número 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 una función booleana vectorial o con valores vectoriales (una caja S en criptografía ). ^[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; igual al número de diferentes tablas de verdad con entradas. ${\displaystyle 2^{2^{k}}}$${\displaystyle k}$${\displaystyle 2^{k}}$

Cada función booleana -ary 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

Ver también: tabla de la verdad

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

• NO , negación o complemento - que recibe una entrada y devuelve verdadero cuando esa entrada es falsa ("no")

• Y o conjunción : verdadero cuando todas las entradas son verdaderas ("ambos")

• 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 es igual")

• Trazo NAND o Sheffer : verdadero cuando no es el caso que todas las entradas sean verdaderas ("no ambas")
• NOR o lógico ni : 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 formas:

• 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 (utilizado en un mapa de Karnaugh )
  • Diagrama de decisión binario , 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 una fórmula proposicional usando 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 OR de AND de los argumentos y sus complementos
• Forma normal conjuntiva , como 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 XOR de AND de los argumentos (no se permiten complementos)
  • Forma normal disyuntiva completa (canónica) , un OR de AND, cada uno de los cuales contiene todos los argumentos o complementos ( minitérminos )
  • 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:

• Gráfico acíclico dirigido por proposiciones
  • Diagrama de circuito digital de puertas lógicas , un circuito booleano
  • Gráfico de inversor Y , usando solo Y y NO

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 varias propiedades: ^[7]

• Constante : siempre es verdadera o siempre falsa independientemente de sus argumentos.
• Monótono : para cada combinación de valores de argumento, cambiar un argumento de falso a verdadero solo puede hacer que la salida cambie de falso a verdadero y no de verdadero a falso.
• Lineal : para cada variable, invertir el valor de la variable siempre hace una diferencia en el valor de verdad o nunca hace 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.
• Equilibrado : si su tabla de verdad contiene la misma cantidad de ceros y unos. El peso de Hamming de la función es el número de unos en la tabla de verdad.
• Doblado : sus derivadas están todas equilibradas (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
• 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 se puede usar para crear (por composición) cualquier función booleana arbitraria (ver completitud funcional )

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

Funciones derivadas

Una función booleana se puede descomponer usando el teorema de expansión de Boole en cofactores de Shannon positivos y negativos ( expansión de Shannon ), que son las funciones arias (k-1) que resultan de fijar uno de los argumentos (a cero o uno). Las funciones generales (k-ary) obtenidas 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 a uno de los argumentos es una función (k-1) -ary 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]

Análisis criptográfico

La transformada de Walsh de una función booleana es una función k-aria con valores enteros que da los coeficientes de una descomposición en funciones lineales ( funciones de Walsh ), análoga a la descomposición de funciones con valores reales 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 linealidad de la función. ^[8]El mayor número de bits (orden) para el que 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 k-aria de valores enteros 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á relacionado 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 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 en ese orden; si todos son cero, entonces la función es una función doblada . ^[9] Los coeficientes de autocorrelación juegan un papel clave encriptoaná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]

Estos conceptos pueden extenderse naturalmente a las funciones vectoriales booleanas 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) ^{[10] [11]} o matriz de correlación ^{[12] [13]} ; 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 ^[11], relacionado por una transformada de Walsh de los componentes ^[14] con la Tabla de Distribución de Diferencias (DDT) ^{[10] [11]} más ampliamente utilizada que enumera las correlaciones entre las diferencias en los bits de entrada y salida (ver también: S-box ).

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 mediante puertas lógicas .

Las propiedades de las funciones booleanas son críticas en criptografía , particularmente en el diseño de algoritmos de claves simétricas (ver 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 .

Ver también

• Álgebra de conjuntos
• álgebra de Boole
• Temas de álgebra booleana
• Cálculo diferencial booleano
• Función con valor booleano
• Modelo de árbol de decisión
• Función indicadora
• Conectivo lógico
• Función pseudo-booleana
• Conjunto firmado
• Función de la verdad
• Mesa de la verdad

Referencias

1. "Función booleana - Enciclopedia de las 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" . Transacciones IRE en computadoras electrónicas . 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 del cambio" , Enciclopedia de la informática , GBR: John Wiley and Sons Ltd., págs. 1727-1731, ISBN 978-0-470-86412-8, consultado el 2021-05-03
6. Carlet, Claude. "Funciones booleanas vectoriales para criptografía" (PDF) . Universidad de Paris .
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). Boyd, Colin (ed.). "Coeficientes de autocorrelación e inmunidad de correlación de funciones booleanas" . Avances en Criptología - ASIACRYPT 2001 . Apuntes de conferencias en informática. Berlín, Heidelberg: Springer. 2248 : 460–479. doi : 10.1007 / 3-540-45682-1_27 . ISBN 978-3-540-45682-7.
9. Canteaut, Anne; Carlet, Claude; Charpin, Pascale; Fontaine, Caroline (14 de mayo de 2000). "Características de propagación y correlación-inmunidad de funciones booleanas altamente no lineales" . Actas de la XIX 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.
10. Hola, Howard M. "Un tutorial sobre criptoanálisis lineal y diferencial" (PDF) .
11. "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 .
12. Daemen, Joan; Govaerts, René; Vandewalle, Joos (1995). Preneel, Bart (ed.). "Matrices de correlación" . Cifrado de software rápido . Apuntes de conferencias en informática. Berlín, Heidelberg: Springer: 275-285. doi : 10.1007 / 3-540-60590-8_21 . ISBN 978-3-540-47809-6.
13. Daemen, Joan (10 de junio de 1998). "Capítulo 5: Propagación y correlación - Anexo a la propuesta AES Rijndael" (PDF) . NIST .
14. Nyberg, Kaisa (1 de diciembre de 2019). "La Autocorrelación Extendida y Tablas Boomerang y Vínculos entre Propiedades de No Linealidad de Funciones Booleanas Vectoriales" (PDF) .

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" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Janković, Dragan; Stanković, Radomir S .; Moraga, Claudio (noviembre de 2003). "Optimización de expresiones aritméticas mediante propiedad de polaridad dual" (PDF) . Revista Serbia de Ingeniería Eléctrica . 1 (71–80, número 1): 71–80. doi : 10.2298 / SJEE0301071J . Archivado desde el original (PDF) el 5 de marzo de 2016 . Consultado el 7 de junio de 2015 .
• Arnold, Bradford Henry (1 de enero de 2011). Lógica y álgebra booleana . Corporación de mensajería. ISBN 978-0-486-48385-6.
• Mano, MM; Ciletti, MD (2013), Diseño digital , Pearson

Este artículo necesidades específicas adicionales o más categorías . Por favor, ayudar a cabo mediante la adición de categorías de forma que se pueden enumerar los artículos similares. ( Mayo de 2021 )