Circuitos digitales - Álgebra booleana
Boolean Algebraes un álgebra, que se ocupa de números binarios y variables binarias. Por lo tanto, también se llama álgebra binaria o álgebra lógica. Un matemático, llamado George Boole había desarrollado esta álgebra en 1854. Las variables utilizadas en esta á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 y leyes básicas del álgebra de Boole
En esta sección, analicemos los postulados booleanos y las leyes básicas que se utilizan en el álgebra booleana. Son útiles para minimizar las funciones booleanas.
Postulados booleanos
Considere los números binarios 0 y 1, la variable booleana (x) y su complemento (x '). O la variable booleana o su complemento se conoce comoliteral. Los cuatro posibleslogical OR Las operaciones 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, los cuatro posibles logical AND las operaciones entre esos literales y números binarios se muestran a continuación.
x.1 = x
x.0 = 0
xx = x
x.x '= 0
Estos son los postulados booleanos simples. Podemos verificar estos postulados fácilmente, sustituyendo la variable booleana con '0' o '1'.
Note- El complemento de complemento de cualquier variable booleana es igual a la propia variable. es decir, (x ')' = x.
Leyes básicas del álgebra de Boole
A continuación se presentan 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 se dice que la operación lógica es Commutative. Las operaciones lógicas OR y lógicas AND de dos variables booleanas x e y se muestran a continuación
x + y = y + x
xy = yx
El símbolo '+' indica una operación lógica OR. Del mismo modo, el símbolo '.' indica operación lógica Y y es opcional representar. La ley conmutativa obedece a operaciones lógicas OR y lógicas AND.
Ley asociativa
Si una operación lógica de dos variables booleanas se realiza primero 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 Associative. 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 operaciones lógicas OR y lógicas 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 Distributive. La distribución de 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 OR y lógicas AND.
Estas son las leyes básicas del álgebra de Boole. Podemos verificar estas leyes fácilmente, sustituyendo las variables booleanas con '0' o '1'.
Teoremas del álgebra booleana
Los dos teoremas siguientes se utilizan en álgebra de Boole.
- Teorema de dualidad
- Teorema de DeMorgan
Teorema de dualidad
Este teorema establece que el dualde la función booleana se obtiene intercambiando el operador lógico AND con el operador lógico OR y los ceros con unos. Para cada función booleana, habrá una función Dual correspondiente.
Hagamos las ecuaciones (relaciones) booleanas que discutimos en la sección de postulados booleanos y leyes básicas en dos grupos. La siguiente tabla muestra estos dos grupos.
| Grupo 1 | Grupo 2 |
|---|---|
| x + 0 = x | x.1 = x |
| x + 1 = 1 | x.0 = 0 |
| x + x = x | xx = x |
| x + x '= 1 | x.x '= 0 |
| x + y = y + x | xy = yx |
| x + (y + z) = (x + y) + z | x. (yz) = (xy) .z |
| x. (y + z) = xy + xz | x + (yz) = (x + y). (x + z) |
En cada fila, hay dos ecuaciones booleanas y son duales entre sí. Podemos verificar todas estas ecuaciones booleanas de Group1 y Group2 usando el teorema de dualidad.
Teorema de DeMorgan
Este teorema es útil para encontrar el complement of Boolean function. Establece que el complemento del O lógico de al menos dos variables booleanas es igual al Y lógico de cada variable complementada.
El teorema de DeMorgan con 2 variables booleanas xey se puede representar como
(x + y) '= x'.y'
El dual de la función booleana anterior es
(xy) '= x' + y '
Por lo tanto, el complemento del Y lógico de dos variables booleanas es igual al O lógico de cada variable complementada. De manera similar, también podemos aplicar el teorema de DeMorgan para más de 2 variables booleanas.
Simplificación de funciones booleanas
Hasta ahora, discutimos los postulados, leyes básicas y teoremas del álgebra de Boole. Ahora, simplifiquemos algunas funciones booleanas.
Ejemplo 1
Nos deja simplify la función booleana, f = p'qr + pq'r + pqr '+ pqr
Podemos simplificar esta función en dos métodos.
Method 1
Dada la función booleana, f = p'qr + pq'r + pqr '+ pqr.
Step 1- En primer y segundo términos r es común y en tercer y cuarto términos pq es común. Entonces, tome los términos comunes usandoDistributive law.
⇒ f = (p'q + pq ') r + pq (r' + r)
Step 2- Los términos presentes en el primer paréntesis se pueden simplificar a operación Ex-OR. Los términos presentes en el segundo paréntesis se pueden simplificar a '1' usandoBoolean postulate
⇒ f = (p ⊕q) r + pq (1)
Step 3- El primer término no se puede simplificar más. Pero, el segundo término se puede simplificar a pq usandoBoolean postulate.
⇒ f = (p ⊕q) r + pq
Por lo tanto, la función booleana simplificada es f = (p⊕q)r + pq
Method 2
Dada la función booleana, f = p'qr + pq'r + pqr '+ pqr.
Step 1 - Utilice el Boolean postulate, x + x = x. Eso significa que la operación O 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
Step 2 - utilizar Distributive lawpara 1 st y 4 th términos, 2 nd y 5 th términos, 3 rd y 6 th términos.
⇒ f = qr (p '+ p) + pr (q' + q) + pq (r '+ r)
Step 3 - utilizar Boolean postulate, x + x '= 1 para simplificar los términos presentes en cada paréntesis.
⇒ f = qr (1) + pr (1) + pq (1)
Step 4 - utilizar Boolean postulate, 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, obtuvimos dos funciones booleanas diferentes después de simplificar la función booleana dada en cada método. Funcionalmente, esas dos funciones booleanas son las mismas. Entonces, según el requisito, podemos elegir una de esas dos funciones booleanas.
Ejemplo 2
Encontremos el complement de la función booleana, f = p'q + pq '.
El complemento de la función booleana es f '= (p'q + pq') '.
Step 1 - Utilice el teorema de DeMorgan, (x + y) '= x'.y'.
⇒ f '= (p'q)'. (Pq ')'
Step 2 - Utilice el teorema de DeMorgan, (xy) '= x' + y '
⇒ f '= {(p') '+ q'}. {P '+ (q') '}
Step3 - Utilice el postulado booleano, (x ')' = x.
⇒ f '= {p + q'}. {P '+ q}
⇒ f '= pp' + pq + p'q '+ qq'
Step 4 - Utilice el postulado booleano, xx '= 0.
⇒ f = 0 + pq + p'q '+ 0
⇒ f = pq + p'q '
Por lo tanto, los complement de la función booleana, p'q + pq 'es pq + p’q’.