Álgebra Booleana

Por Ariel Parra

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.

CPC Γα=Ω5

Operaciones básicas

NOT ( ! )

a ¬a
0 1
1 0

AND ( && )

a b a · b
0 0 0
0 1 0
1 0 0
1 1 1

OR ( || )

a b a + b
0 0 0
0 1 1
1 0 1
1 1 1
CPC Γα=Ω5

Propiedades y Axiomas

  1. Ley asociativa:

  2. Existencia del elemento neutro:

  3. Ley conmutativa:

  4. Ley distributiva:

  5. Existencia del elemento complementario:

CPC Γα=Ω5

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:

CPC Γα=Ω5

NOT

  • Ley de involución:

Leyes de De Morgan

CPC Γα=Ω5

Conectivas derivadas

CPC Γα=Ω5

NOR

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

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

Tabla NOR

a b y
0 0 1
0 1 0
1 0 0
1 1 0
CPC Γα=Ω5

NAND

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

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

Tabla NAND

a b ¬( a + b )
0 0 1
0 1 1
1 0 1
1 1 0
CPC Γα=Ω5

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

a b a ⊕ b
0 0 0
0 1 1
1 0 1
1 1 0
CPC Γα=Ω5

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

a b ¬(a ⊕ b)
0 0 1
0 1 0
1 0 0
1 1 1

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

CPC Γα=Ω5

Prolemas de simplificación de expresiones

#c

CPC Γα=Ω5

Problema 1

Expresión a simplificar:

CPC Γα=Ω5

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:

CPC Γα=Ω5

  1. Aplicar la Ley de Absorción:

    Entonces la expresión simplificada es:

Problema 2

Expresión a simplificar:

CPC Γα=Ω5

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:

CPC Γα=Ω5

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.
CPC Γα=Ω5

Expresión Booleana Inicial

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

o en sintaxis de c++

                                    (P || M) && (P || A)

Donde:

  • = Puerta abierta (0 = cerrada, 1 = abierta)
  • = Movimiento detectado (0 = no, 1 = sí)
  • = Alarma encendida (0 = apagada, 1 = encendida)
CPC Γα=Ω5

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:

CPC Γα=Ω5

Ejemplo Simplificado en C++

bool shouldActivateAlarm(bool doorOpen, bool motionDetected, bool alarmOn) {
    return doorOpen && (motionDetected || alarmOn);
}
int main() {
    bool doorOpen = true;        // Puerta abierta
    bool motionDetected = false; // No hay movimiento
    bool alarmOn = true;         // Alarma encendida

    if (shouldActivateAlarm(doorOpen, motionDetected, alarmOn)) {
        cout << "La alarma  se activa.";
    } else {
        cout << "La alarma NO se activa.";
    }
    return 0;
}
CPC Γα=Ω5

Problemas

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

CPC Γα=Ω5

Referencias

CPC Γα=Ω5

Mencionar que or es suma y and es multiplicación

la barra es la negación