Álgebra Booleana

El álgebra de Boole es una herramienta diseñada para poder representar proposiciones lógicas en forma algebraica. Desarrollada originalmente en 1847 por George Boole.

Actualmente, este tipo de álgebra es utilizada ampliamente en el diseño y simplificación de sistemas digitales binarios, es decir, sistemas que basan todo su comportamiento en los valores {1,0}.

Para nosotros nos sera útil para simplificar expresiónes lógicas y en operaciones de bits.

Propiedades y Axiomas

1. Ley asociativa:

2. Existencia del elemento neutro:

3. Ley conmutativa:

4. Ley distributiva:

5. Existencia del elemento complementario:

AND

• Ley de idempotencia para el producto:

• Ley de absorción para el producto:

• Ley de identidad para el producto:

OR

• Ley de idempotencia para la suma:

• Ley de absorción para la suma:

• Ley de identidad para la suma:

NOT

• Ley de involución:

Leyes de De Morgan

Conectivas derivadas

NOR

Es la negada de la función “OR”:

En c++: ! ( a && b )

Tabla NOR

NAND

Es la negada de la función “AND”:

En c++: !( a && b )

Tabla NAND

XOR

Es la función OR excluyente: uno u otro, pero no los dos. Se puede utilizar para detectar señales que son distintas.

En c++: ( a || b ) && !( a && b )

Tabla XOR

XNOR

Es la negada de la función “XOR”. Se puede utilizar para detectar señales que son iguales:

En c++: !( ( a || b ) && !( a && b ) )

Tabla XNOR

https://www.boolean-algebra.com/

Prolemas de simplificación de expresiones

Problema 1

Expresión a simplificar:

Solución:

1. Aplicar la Ley Distributiva:

2. Simplificar:

   • Para ( A \cdot (A + B) ):

     (por la Ley de Absorción)

   • Para ( \overline{B} \cdot (A + B) ):

     Entonces:

   Entonces:

3. Aplicar la Ley de Absorción:

   Entonces la expresión simplificada es:

Problema 2

Expresión a simplificar:

Solución:

1. Simplificar por agrupación:

   • Agrupa

   con la Ley de Distributiva:

   • Reescribe la expresión:

2. Aplicar la Ley de Absorción:

   • Nota que ( (A \cdot B) + (B \cdot \overline{C}) = B ) (porque ( A \cdot B ) está contenido en ( B )).
   • Entonces:

   La expresión no se simplifica más. Entonces:

Ejemplo Práctico: Sistema de Alarma en una Casa Inteligente

Imaginemos que queremos que el sistema de alarma se active bajo ciertas condiciones:

1. Condiciones:
   • La puerta de entrada está abierta (P).
   • El sensor de movimiento detecta movimiento (M).
   • El sistema de alarma está encendido (A).

Queremos que la alarma suene si:

• La puerta está abierta y hay movimiento, o
• La puerta está abierta y el sistema de alarma está encendido.

Expresión Booleana Inicial

La lógica para activar la alarma se puede expresar como:

o en sintaxis de c++

Donde:

• = Puerta abierta (0 = cerrada, 1 = abierta)
• = Movimiento detectado (0 = no, 1 = sí)
• = Alarma encendida (0 = apagada, 1 = encendida)

Simplificación de la Expresión

1. Expresión Inicial:

2. Aplicar Leyes de Booleanos:

   • Factorización:

3. Resultado Simplificado:

   • La expresión simplificada es:

Ejemplo Simplificado en C++

Problemas

para subir el problema I, deben ingresar manualmente al gym, darle en submit y elegir el problema https://codeforces.com/gym/102890/submit

• Problema I. Is this the best deal?, del ICPC Mexico ronda 3 del 2020

Referencias

• boolean-algebra. (s.f.). Boolean Algebra Simplifier. Recuperado de https://www.boolean-algebra.com/
• Brunete, A. (s.f.). 3.1 Álgebra de Boole. Recuperado de https://bookdown.org/alberto_brunete/intro_automatica/algebraboole.html
• khandelwal, S. (2024) Boolean Algebra. Recuperado de https://www.geeksforgeeks.org/boolean-algebra/
• UNAM. (s.f.) Algebra de Boole. Recuperado de http://ecampus.fca.unam.mx/ebook/imprimibles/informatica/arquitectura_computadoras/Unidad_4.pdf
• UNAM. (s.f). Álgebra Booleana. Recuperado de https://virtual.cuautitlan.unam.mx/intar/sistdig/algebra-booleana/