En matemáticas y lógica matemática , el álgebra booleana es la rama del álgebra en la que los valores de las variables son los valores de verdad verdadero y falso , generalmente denotados 1 y 0, respectivamente. En lugar del álgebra elemental , donde los valores de las variables son números y las operaciones principales son la suma y la multiplicación, las operaciones principales del álgebra booleana son la conjunción ( y ) denotada como ∧, la disyunción ( o ) denotada como ∨ y la negación ( no) denotado como ¬. Es pues un formalismo para describir operaciones lógicas , del mismo modo que el álgebra elemental describe operaciones numéricas.
El álgebra booleana fue introducida por George Boole en su primer libro The Mathematical Analysis of Logic [1] (1847), y expuesta con más detalle en su An Investigation of the Laws of Thought (1854). [2] Según Huntington , el término "álgebra booleana" fue sugerido por primera vez por Sheffer en 1913, [3] aunque Charles Sanders Peirce dio el título "Un álgebra booleana con una constante" al primer capítulo de su libro "Las matemáticas más simples". en 1880. [4] El álgebra booleana ha sido fundamental en el desarrollo de la electrónica digital , y está previsto en todos los modernoslenguajes de programacion También se utiliza en teoría de conjuntos y estadística . [5]
Un precursor del álgebra booleana fue el álgebra de conceptos de Gottfried Wilhelm Leibniz . El álgebra de conceptos de Leibniz es deductivamente equivalente al álgebra booleana de conjuntos. [6]
El álgebra de Boole es anterior a los desarrollos modernos del álgebra abstracta y la lógica matemática ; sin embargo, se considera que está conectado con los orígenes de ambos campos. [7] En un entorno abstracto, el álgebra booleana fue perfeccionada a fines del siglo XIX por Jevons , Schröder , Huntington y otros, hasta que alcanzó la concepción moderna de una estructura matemática (abstracta) . [7] Por ejemplo, la observación empírica de que uno puede manipular expresiones en el álgebra de conjuntos , traduciéndolas a expresiones en el álgebra de Boole, se explica en términos modernos diciendo que el álgebra de conjuntos es un Álgebra booleana (nótese el artículo indefinido ). De hecho, MH Stone demostró en 1936 que toda álgebra booleana es isomorfa a un cuerpo de conjuntos .
En la década de 1930, mientras estudiaba circuitos de conmutación , Claude Shannon observó que también se podían aplicar las reglas del álgebra de Boole en este entorno, [8] e introdujo el álgebra de conmutación como una forma de analizar y diseñar circuitos por medios algebraicos en términos de puertas lógicas. . Shannon ya tenía a su disposición el aparato matemático abstracto, por lo que formuló su álgebra de conmutación como el álgebra booleana de dos elementos . En los entornos de ingeniería de circuitos modernos, hay poca necesidad de considerar otras álgebras booleanas, por lo que "álgebra de conmutación" y "álgebra booleana" a menudo se usan indistintamente. [9] [10] [11]
La implementación eficiente de funciones booleanas es un problema fundamental en el diseño de circuitos lógicos combinacionales . Las herramientas modernas de automatización de diseño electrónico para circuitos VLSI a menudo se basan en una representación eficiente de funciones booleanas conocidas como diagramas de decisión binaria (BDD) (de orden reducido) para la síntesis lógica y la verificación formal . [12]