Álgebra Booleana: Conceptos, reglas y ejemplos

¿Qué es el álgebra booleana?

El álgebra booleana es el estudio de operaciones algebraicas sobre valores binarios. La palabra “binario” significa dos, por lo que sólo hay dos valores posibles en el álgebra booleana: VERDADERO y FALSO. El valor VERDADERO suele estar representado por el número uno, mientras que el valor FALSO suele estar representado por el número cero. De manera similar al álgebra regular, las variables se pueden utilizar como marcadores de posición para posibles valores VERDADEROS o FALDOS.

El desarrollo del álgebra booleana introdujo las operaciones lógicas, que son un elemento necesario de muchos temas de álgebra contemporánea, incluida la teoría de conjuntos, el álgebra abstracta y el álgebra lineal. El álgebra booleana se utilizó para desarrollar los circuitos dentro de una computadora y es importante para los cálculos utilizados en los lenguajes de programación. Casi todas las computadoras que se utilizan hoy en día realizan tareas basadas en los unos y los ceros del álgebra booleana.

Historia del álgebra booleana

El álgebra booleana recibe su nombre de George Boole, quien publicó una obra en 1847 titulada El análisis matemático de la lógica. Casi al mismo tiempo, Augustus De Morgan publicó su libro titulado Lógica formal. El trabajo de De Morgan introdujo la idea de validez lógica: si una afirmación es lógicamente válida, la conclusión será verdadera si los supuestos (o premisas) son verdaderos. Este fue el comienzo de la valoración binaria y del etiquetado de ideas como verdaderas o falsas. El Análisis Matemático de la Lógica amplió las ideas que se discutieron en el trabajo de De Morgan, agregando un elemento de razonamiento algebraico a la lógica binaria.

En 1848, George Boole publicó otro artículo titulado Álgebra de la lógica que luego fue estudiado y perfeccionado por John Venn y CS Peirce. Este trabajo definió claramente el álgebra de Boole y aplicó los conceptos a clases abstractas, lo que formó el comienzo de lo que ahora se conoce como teoría de conjuntos. George Boole también publicó un libro en 1854 titulado Una investigación de las leyes del pensamiento que no fue popular de inmediato, lo que provocó que Boole perdiera dinero durante el proceso de publicación. Una investigación de las leyes del pensamiento se inspiró parcialmente en la obra Trigonometría y doble álgebra de De Morgan, que incluía ejemplos de álgebra simbólica en uso. El trabajo de Boole procedió a desarrollar un conjunto claro de símbolos para representar operaciones algebraicas.

La segunda edición del libro Symbolic Logic de John Venn, escrita en 1894, amplió el trabajo de Boole y brindó a los matemáticos las herramientas y explicaciones necesarias para trabajar con la lógica booleana. Esto permitió a los matemáticos ampliar las ideas introducidas por George Boole y crear nuevos campos de las matemáticas. Boole, junto con amigos y colegas que perfeccionaron su trabajo, sentó las bases de la lógica necesaria para los circuitos, la programación de computadoras y muchos otros temas de álgebra moderna.

Conceptos de álgebra booleana

De manera similar al álgebra regular, el álgebra booleana puede usar variables para representar un valor potencialmente VERDADERO o FALSO. Estas variables pueden considerarse como marcadores de posición utilizados para crear declaraciones matemáticas más complejas. Si hay una variable, hay dos posibilidades para esa variable: VERDADERO o FALSO. Si hay dos variables, las cosas se complican más ya que ambas variables podrían ser VERDADERAS, ambas podrían ser FALSAS o una podría ser VERDADERA y la otra podría ser FALSA.

Las tres operaciones básicas utilizadas para manipular variables son Y, O y NO. Tanto Y como O conectan dos variables, mientras que NO se aplica a una sola variable. Una declaración Y solo es VERDADERA si ambas variables son VERDADERAS, una declaración O solo es VERDADERA si al menos una de las variables es VERDADERA y una declaración NO es VERDADERA si la variable adjunta es FALSA. Generalmente, una declaración Y se denomina conjunción, una declaración OR se denomina disyunción y una declaración NO se denomina negación. En la teoría de conjuntos, una declaración Y equivale a encontrar una intersección, una declaración O equivale a encontrar una unión y una declaración NO equivale a encontrar un complemento.

Cuando se utilizan múltiples variables y las operaciones se vuelven cada vez más complejas, puede resultar útil desarrollar tablas de verdad. Las tablas de verdad describen todos los valores de variables posibles y determinan cuál será el valor de operación resultante para cada combinación.

La longitud de las tablas de verdad crece exponencialmente: el número de filas de posibilidades en una tabla de verdad se puede encontrar con la expresión {eq}2^n {/eq} donde n es el número de variables que se consideran. Por ejemplo, una tabla de verdad con 4 variables tendrá {eq}2^4 = 16 {/eq} posibles combinaciones de variables.

Las operaciones se pueden anidar, por lo que puede resultar útil realizar pasos intermedios para realizar un seguimiento de los distintos valores de verdad dentro de la expresión más amplia.

Si una expresión es verdadera para todos los valores posibles de cada variable, se llama tautología. Un ejemplo de tautología es (NO p) O p; esta afirmación es siempre cierta sin importar el valor de verdad que se le asigne a p. Si una expresión es falsa para todos los valores posibles de cada variable, se llama contradicción. Un ejemplo de contradicción es (NO p) Y p; esta afirmación es siempre falsa sin importar el valor de verdad que se asigne a p. Dos expresiones son lógicamente equivalentes si tienen exactamente el mismo resultado en la tabla de verdad. En esta lección, un signo igual indica equivalencia lógica.

Reglas del álgebra booleana

Con operaciones anidadas y manipulación algebraica, resulta ventajoso representar simbólicamente Y, O y NO. Algunos símbolos comunes utilizados para representar Y son {eq}*, \cap, \wedge {/eq}; los símbolos comunes para representar OR son {eq}+, \cup, \vee {/eq}; y los símbolos comunes para representar “NO p” son {eq}\overline p, \neg p, p’ {/eq}. En esta lección se escribirán Y, O y NO.

Las siguientes propiedades y leyes describen las reglas básicas del álgebra booleana.

Propiedad conmutativa

La propiedad conmutativa establece que el orden no importa tanto para las operaciones Y como para O. Esta propiedad tiene dos formas:

Propiedad conmutativa para AND

• p Y q = q Y p

Propiedad conmutativa para OR

• p O q = q O p

Propiedad asociativa

La propiedad asociativa se refiere a la colocación de paréntesis dentro de una expresión utilizando dos operaciones Y o dos operaciones O. Esta propiedad tiene dos formas:

Propiedad asociativa para AND

• p Y (q Y r) = (p Y q) Y r

Propiedad asociativa para OR

• p O (q O r) = (p O q) O r

Propiedad distributiva

La propiedad distributiva establece cómo una operación (Y u O) se distribuye sobre una operación diferente (Y u O). Esta propiedad tiene dos formas:

Propiedad distributiva de Y sobre O

• p Y (q O r) = (p Y q) O (p Y r)

Propiedad distributiva de OR sobre AND

• p O (q Y r) = (p O q) Y (p O r)

Leyes de identidad

Hay dos leyes de identidad y ambas involucran una sola variable. Se afirma que tomar la operación OR de una variable y FALSO da como resultado el valor de verdad de la variable. La otra ley establece que tomar la operación Y de una variable y VERDADERO da como resultado el valor de verdad de la variable. Las dos leyes de identidad son las siguientes:

• p O FALSO = p
• p Y VERDADERO = p

Leyes complementarias

Las leyes del complemento describen lo que sucede cuando se realiza una operación sobre una variable y la negación de esa variable. Las dos leyes del complemento son las siguientes:

• p Y (NO p) = FALSO
• p O (NO p) = VERDADERO

Ley de doble negación

La ley de la doble negación establece que la negación de una negación se anula. Por ejemplo:

• NO (NO p) = p

Teoremas del álgebra booleana

Además de las reglas generales del álgebra booleana, existen teoremas más complejos que fueron descubiertos y demostrados por los matemáticos.

Teorema de De Morgan

El teorema de DeMorgan produce dos leyes relevantes, también llamadas leyes de DeMorgan. Las leyes de DeMorgan describen lo que sucede cuando una negación se distribuye entre una operación Y o una operación O. Las dos leyes son las siguientes:

• NO (p O q) = (NO p) Y (NO q)
• NO (p Y q) = (NO p) O (NO q)

Ejemplo del teorema de DeMorgan

Piense en la afirmación básica: “Kiki bebe café o té”. Si hacemos que p sea igual a “Kiki bebe café” y q sea igual a “bebe té”, el enunciado se puede reescribir como p O q. La negación de esta afirmación sería NO (p O q). Según el teorema de DeMorgan, la negación del enunciado original se puede reescribir como (NO p) Y (NO q). Traduciendo esto a un lenguaje sencillo, la negación de la afirmación original es la misma que: “Kiki no bebe café y no bebe té”.

Teorema complementario

El teorema complementario es una extensión del teorema de DeMorgan al describir cómo negar una expresión larga. El teorema complementario proporciona tres reglas para negar una serie de operaciones.

1. Cambie cada VERDADERO a FALSO y cada FALSO a VERDADERO
2. Negar cada variable
3. Cambie cada operador O a un operador Y, cambie cada operador Y a un operador O

Ejemplo del teorema complementario

Para tomar el complemento de (p Y q) O (NO q O r), niegue cada variable y cambie los operadores.

NO ((p Y q) O (NO q O r)) = (NO p O NO q) Y (NO (NO q) Y NO r)

Teorema de la dualidad

El teorema de la dualidad afirma que si una equivalencia lógica es un enunciado verdadero, una equivalencia lógica dual que sigue ciertas pautas también es un enunciado verdadero. Las pautas para el teorema de la dualidad son las siguientes:

1. Cambie cada VERDADERO a FALSO y cada FALSO a VERDADERO
2. Mantener las variables exactamente iguales
3. Cambie cada operador OR a un operador AND, cambie cada operador Y a un operador O

Ejemplo del teorema de la dualidad

Un gran ejemplo del teorema de la dualidad son las dos leyes de DeMorgan diferentes. Considere la primera ley: NO (p O q) = (NO p) Y (NO q). La segunda ley sigue el teorema de la dualidad, cambiando cada Y por un O y viceversa, lo que da como resultado NO (p Y q) = (NO p) O (NO q). Observe que las variables no se niegan.

Las leyes del complemento y de la identidad demuestran el teorema de la dualidad, incluida la pauta para cambiar cada VERDADERO por FALSO y viceversa. Las propiedades conmutativa, asociativa y distributiva también siguen el teorema de la dualidad.

Teorema de redundancia

El teorema de redundancia busca eliminar redundancias dentro de una expresión. Si dos expresiones son lógicamente equivalentes y una es más corta, utilice la expresión más corta.

Ejemplos del teorema de redundancia

Los siguientes son ejemplos de expresiones redundantes y cómo se pueden escribir de manera más sencilla:

• (p Y q) O (p Y NO q) = p
• (p O q) Y (p O NO q) = p
• (p O NO q) Y q = p Y q
• (p Y NO q) O q = p O q

Teorema de transposición

El teorema de transposición establece que:

• (p Y q) O (NO p Y r) = (p O r) Y (NO p O q)

Resumen de la lección

El álgebra booleana es el estudio de operaciones lógicas sobre valores binarios. Estos valores binarios pueden ser VERDADEROS o FALDOS; si el valor es desconocido, se representa mediante una variable. Normalmente, las variables booleanas son letras minúsculas. Las tres operaciones lógicas básicas son Y, O y NO. La operación Y encuentra la conjunción de dos variables y solo es VERDADERA cuando ambas variables son VERDADERAS. La operación O encuentra la disyunción de dos variables y solo es VERDADERA si al menos una variable es VERDADERA. La operación NO encuentra la negación de una variable y solo es VERDADERA si la variable es FALSA. Las tablas de verdad se pueden utilizar para ver el resultado de diferentes operaciones dadas todas las valoraciones de verdad posibles de cada variable. Las operaciones se pueden anidar para crear expresiones complejas; en este caso, puede resultar útil crear pasos intermedios dentro de una tabla de verdad. Las tautologías y las contradicciones son expresiones que siempre son VERDADERAS y siempre FALSAS, respectivamente, sin importar cuáles sean las variables de entrada. El álgebra booleana describe equivalencias lógicas a través de propiedades, leyes y teoremas, que incluyen, entre otros:

• Propiedad conmutativa
• Propiedad asociativa
• Propiedad distributiva
• Leyes de identidad
• Leyes complementarias
• Ley de doble negación
• Teorema/leyes de DeMorgan
• Teorema complementario
• Teorema de transposición
• Teorema de redundancia
• Teorema de dualidad

La lógica de las operaciones algebraicas utilizadas en el álgebra de Boole ha llevado al desarrollo de muchas disciplinas de álgebra contemporáneas, y las operaciones binarias en el álgebra de Boole tienen usos importantes en computadoras, lenguajes de programación y circuitos. El desarrollo del álgebra de Boole se atribuye predominantemente a George Boole porque sus libros y artículos publicados introdujeron nuevos conceptos que formaron la disciplina. Augustus De Morgan y John Venn también contribuyeron al álgebra de Boole refinando el trabajo de Boole y haciendo que las operaciones algebraicas de Boole fueran más accesibles para otros matemáticos. Muchos otros matemáticos, incluido CS Peirce, han elaborado el trabajo de Boole y han ayudado a crear una forma importante de álgebra: el álgebra de Boole.