Función booleana
En matemáticas , una función booleana es una función cuyos argumentos y resultado asumen valores de un conjunto de dos elementos (generalmente {verdadero, falso}, {0,1} o {-1,1}). [1] [2] Los nombres alternativos son función de conmutación , que se utiliza especialmente en la literatura de ciencias de la computación 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 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]
Hay diferentes funciones booleanas con argumentos; igual al número de diferentes tablas de verdad con entradas.
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.
Para optimizar los circuitos electrónicos, las fórmulas booleanas se pueden minimizar utilizando el algoritmo de Quine-McCluskey o el mapa de Karnaugh .
La complejidad del circuito intenta clasificar las funciones booleanas con respecto al tamaño o profundidad de los circuitos que pueden calcularlas.
