Simplificación de funciones booleanas

Simplificación mediante funciones algebraicas

En este enfoque, una expresión booleana se minimiza en una expresión equivalente aplicando identidades booleanas.

Problema 1

Minimice la siguiente expresión booleana utilizando identidades booleanas:

$$ F (A, B, C) = A'B + BC '+ BC + AB'C' $$

Solución

Dado, $ F (A, B, C) = A'B + BC '+ BC + AB'C' $

O $ F (A, B, C) = A'B + (BC '+ BC') + BC + AB'C '$

[Por ley idempotente, BC '= BC' + BC ']

O $ F (A, B, C) = A'B + (BC '+ BC) + (BC' + AB'C ') $

O $ F (A, B, C) = A'B + B (C '+ C) + C' (B + AB ') $

[Por leyes distributivas]

O $ F (A, B, C) = A'B + B.1 + C '(B + A) $

[(C '+ C) = 1 y ley de absorción (B + AB') = (B + A)]

O $ F (A, B, C) = A'B + B + C '(B + A) $

[B.1 = B]

O $ F (A, B, C) = B (A '+ 1) + C' (B + A) $

O $ F (A, B, C) = B.1 + C '(B + A) $

[(A '+ 1) = 1]

O $ F (A, B, C) = B + C '(B + A) $

[Como, B.1 = B]

O $ F (A, B, C) = B + BC '+ AC' $

O $ F (A, B, C) = B (1 + C ') + AC' $

O $ F (A, B, C) = B.1 + AC '$

[Como, (1 + C ') = 1]

O $ F (A, B, C) = B + AC '$

[Como, B.1 = B]

Entonces, $ F (A, B, C) = B + AC '$ es la forma minimizada.

Problema 2

Minimice la siguiente expresión booleana utilizando identidades booleanas:

$$ F (A, B, C) = (A + B) (A + C) $$

Solución

Dado, $ F (A, B, C) = (A + B) (A + C) $

O $ F (A, B, C) = AA + AC + BA + BC $ [Aplicación de la regla distributiva]

O $ F (A, B, C) = A + AC + BA + BC $ [Aplicación de la ley idempotente]

O $ F (A, B, C) = A (1 + C) + BA + BC $ [Aplicación de la ley distributiva]

O $ F (A, B, C) = A + BA + BC $ [Aplicación de la ley de dominancia]

O $ F (A, B, C) = (A + 1). A + BC $ [Aplicación de la ley distributiva]

O $ F (A, B, C) = 1.A + BC $ [Aplicación de la ley de dominancia]

O $ F (A, B, C) = A + BC $ [Aplicación de la ley de dominancia]

Entonces, $ F (A, B, C) = A + BC $ es la forma minimizada.

Mapas de Karnaugh

El mapa de Karnaugh (mapa K), introducido por Maurice Karnaughin en 1953, es una representación en forma de cuadrícula de una tabla de verdad que se utiliza para simplificar expresiones de álgebra booleana. Un mapa de Karnaugh tiene cero y una entrada en diferentes posiciones. Proporciona la agrupación de expresiones booleanas con factores comunes y elimina las variables no deseadas de la expresión. En un mapa K, cruzar un límite de celda vertical u horizontal es siempre un cambio de solo una variable.

Ejemplo 1

A continuación se toma una tabla de verdad arbitraria:

UN	segundo	A operación B
0	0	w
0	1	X
1	0	y
1	1	z

Ahora haremos un mapa k para la tabla de verdad anterior:

Ejemplo 2

Ahora haremos un mapa K para la expresión - AB + A'B '

Simplificación con K-map

K-map usa algunas reglas para la simplificación de expresiones booleanas combinando celdas adyacentes en un solo término. Las reglas se describen a continuación:

Rule 1 - Cualquier celda que contenga un cero no se puede agrupar.

Agrupación incorrecta

Rule 2 - Los grupos deben contener 2n celdas (n a partir de 1).

Agrupación incorrecta

Rule 3 - La agrupación debe ser horizontal o vertical, pero no diagonal.

Agrupación diagonal incorrecta

Agrupación vertical adecuada

Agrupación horizontal adecuada

Rule 4 - Los grupos deben estar cubiertos en la mayor medida posible.

Agrupación insuficiente

Agrupación adecuada

Rule 5 - Si 1 de cualquier celda no se puede agrupar con ninguna otra celda, actuará como un grupo.

Agrupación adecuada

Rule 6 - Los grupos pueden superponerse, pero debe haber el menor número posible de grupos.

Agrupación adecuada

Rule 7 - La celda / celdas más a la izquierda se puede agrupar con la celda / celdas más a la derecha y la celda / celdas más arriba se puede agrupar con la celda / celdas más abajo.

Agrupación adecuada

Problema

Minimice la siguiente expresión booleana usando K-map -

$$ F (A, B, C) = A'BC + A'BC '+ AB'C' + AB'C $$

Solución

Cada término se pone en k-map y obtenemos lo siguiente:

K-mapa para F (A, B, C)

Ahora agruparemos las celdas de 1 de acuerdo con las reglas establecidas anteriormente:

K-mapa para F (A, B, C)

Tenemos dos grupos que se denominan $ A'B $ y $ AB '$. Por tanto, $ F (A, B, C) = A'B + AB '= A \ oplus B $. Es la forma minimizada.