4.1 Teoremas y postulados

 El álgebra booleana es un álgebra, que trata con números binarios y variables binarias. Por lo tanto, también se le llama Álgebra binaria o Álgebra lógica. Un matemático, llamado George Boole, había desarrollado este álgebra en 1854. Las variables utilizadas en este álgebra también se denominan variables booleanas.

El rango de voltajes correspondiente a la lógica 'Alta' se representa con '1' y el rango de voltajes correspondiente a la lógica 'Baja' se representa con '0'.

Postulados Booleanos

Considere los números binarios 0 y 1, la variable booleana (x) y su complemento (x '). La variable booleana o su complemento se conoce como literal . Las cuatro operaciones lógicas O posibles entre estos literales y números binarios se muestran a continuación.

x + 0 = x

x + 1 = 1

x + x = x

x + x '= 1

Del mismo modo, a continuación se muestran las cuatro operaciones lógicas Y posibles entre esos literales y números binarios.

x.1 = x

x.0 = 0

xx = x

x.x '= 0

Estos son los simples postulados booleanos. Podemos verificar estos postulados fácilmente, sustituyendo la variable booleana por '0' o '1'.

Nota : el complemento de complemento de cualquier variable booleana es igual a la variable en sí. Es decir, (x ')' = x.

Leyes básicas del álgebra booleana

Las siguientes son las tres leyes básicas del álgebra booleana.

• Ley conmutativa
• Ley asociativa
• Ley distributiva

Ley conmutativa

Si cualquier operación lógica de dos variables booleanas da el mismo resultado independientemente del orden de esas dos variables, entonces esa operación lógica se dice que es conmutativa . Las operaciones lógicas OR y lógicas AND de dos variables booleanas x & y se muestran a continuación

x + y = y + x

xy = yx

El símbolo '+' indica una operación OR lógica. Del mismo modo, el símbolo '.' Indica una operación AND lógica y es opcional para representar. La ley conmutativa obedece a las operaciones lógicas y lógicas Y.

Ley asociativa

Si primero se realiza una operación lógica de cualquiera de las dos variables booleanas y luego se realiza la misma operación con la variable restante da el mismo resultado, entonces se dice que la operación lógica es asociativa . Las operaciones lógicas OR y lógicas AND de tres variables booleanas x, y & z se muestran a continuación.

x + (y + z) = (x + y) + z

x. (yz) = (xy) .z

La ley asociativa obedece a las operaciones lógicas y lógicas y operaciones AND.

Ley distributiva

Si cualquier operación lógica se puede distribuir a todos los términos presentes en la función booleana, entonces se dice que esa operación lógica es Distributiva . La distribución de las operaciones lógicas OR y lógicas AND de tres variables booleanas x, y & z se muestra a continuación.

x. (y + z) = xy + xz

x + (yz) = (x + y). (x + z)

La ley distributiva obedece a operaciones lógicas y lógicas y operaciones AND.

Estas son las leyes básicas del álgebra booleana. Podemos verificar estas leyes fácilmente, sustituyendo las variables booleanas con '0' o '1'.

Teoremas del algebra booleana

Los siguientes dos teoremas se utilizan en el álgebra de Boole.

• Teorema de dualidad
• Teorema de DeMorgan

Teorema de dualidad

Este teorema establece que el doble de la función booleana se obtiene al intercambiar el operador lógico AND con el operador lógico OR y los ceros con los unos. Para cada función booleana, habrá una función dual correspondiente.

Hagamos las ecuaciones booleanas (relaciones) que discutimos en la sección de postulados booleanos y las leyes básicas en dos grupos. La siguiente tabla muestra estos dos grupos.

Teorema de DeMorgan

Este teorema es útil para encontrar el complemento de la función booleana . Indica que el complemento de OR lógico de al menos dos variables booleanas es igual al AND lógico de cada variable complementada.

El teorema de DeMorgan con 2 variables booleanas xey puede representarse como

(x + y) '= x'.y'

El doble de la función booleana anterior es

(xy) '= x' + y '

Por lo tanto, el complemento de AND lógico de dos variables booleanas es igual al OR lógico de cada variable complementada. De manera similar, podemos aplicar el teorema de DeMorgan para más de 2 variables booleanas también.

Simplificación de funciones booleanas.

Hasta ahora, discutimos los postulados, las leyes básicas y los teoremas del álgebra de Boole. Ahora, simplifiquemos algunas funciones booleanas.

Ejemplo 1

Vamos a simplificar la función de Boole, f = + p'qr pq'r + PQR' + PQR

Podemos simplificar esta función en dos métodos.

Método 1

Dada la función booleana, f = p'qr + pq'r + pqr '+ pqr.

Paso 1 : en primer y segundo término r es común y en tercer y cuarto término pq es común. Entonces, tome los términos comunes usando la ley distributiva .

⇒ f = (p'q + pq ') r + pq (r' + r)

Paso 2 : los términos presentes en el primer paréntesis se pueden simplificar a la operación Ex-OR. Los términos presentes en el segundo paréntesis se pueden simplificar a '1' usando el postulado booleano

⇒ f = (p ⊕q) r + pq (1)

Paso 3 - El primer término no se puede simplificar más. Pero, el segundo término se puede simplificar a pq usando el postulado booleano .

⇒ f = (p ⊕q) r + pq

Por lo tanto, la función booleana simplificada es f = (p⊕q) r + pq

Método 2

Dada la función booleana, f = p'qr + pq'r + pqr '+ pqr.

Paso 1 - Usa el postulado booleano , x + x = x. Eso significa que la operación OR lógica con cualquier variable booleana 'n' veces será igual a la misma variable. Entonces, podemos escribir el último término pqr dos veces más.

⇒ f = p'qr + pq'r + pqr '+ pqr + pqr + pqr

Paso 2 - Uso ley distributiva para 1 ^st y 4 ^th términos, 2 ^nd y 5 ^th términos, 3 ^rd y 6 ^thtérminos.

⇒ f = qr (p '+ p) + pr (q' + q) + pq (r '+ r)

Paso 3 - Use el postulado booleano , x + x '= 1 para simplificar los términos presentes en cada paréntesis.

⇒ f = qr (1) + pr (1) + pq (1)

Paso 4 - Use el postulado booleano , x.1 = x para simplificar los tres términos anteriores.

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

Por lo tanto, la función booleana simplificada es f = pq + qr + pr .

Entonces, tenemos dos funciones booleanas diferentes después de simplificar la función booleana dada en cada método. Funcionalmente, esas dos funciones booleanas son iguales. Entonces, según el requisito, podemos elegir una de esas dos funciones booleanas.

Ejemplo 2

Encontremos el complemento de la función booleana, f = p'q + pq '.

El complemento de la función booleana es f '= (p'q + pq') '.

Paso 1 - Usa el teorema de DeMorgan, (x + y) '= x'.y'.

⇒ f '= (p'q)'. (Pq ')'

Paso 2 - Usa el teorema de DeMorgan, (xy) '= x' + y '

⇒ f '= {(p') '+ q'}. {P '+ (q') '}

Paso 3 - Usa el postulado booleano, (x ')' = x.

⇒ f '= {p + q'}. {P '+ q}

⇒ f '= pp' + pq + p'q '+ qq'

Paso 4 - Usa el postulado booleano, xx '= 0.

⇒ f = 0 + pq + p'q '+ 0

⇒ f = pq + p'q '

Por lo tanto, el complemento de la función booleana, p'q + pq 'es pq + p'q' .