Representación de funciones booleanas – Part 1

Una función booleana se describe mediante una expresión algebraica que consiste en variables binarias, las constantes 0 y 1 y los símbolos de operación lógica. +,\:.\:,\:^\prime
Para un conjunto dado de valores de las variables binarias involucradas, la función booleana puede tener un valor de 0 o 1. Para ejemplo, la función booleana F= x^\prime y + zse define en términos de tres variables binarias x,\:y,\:z. La función es igual a 1 si x=0y y=1simultáneamente o z=1.
Cada función booleana se puede expresar mediante una expresión algebraica, como la mencionada anteriormente, o en términos de una tabla de verdad. Una función puede expresarse mediante varias expresiones algebraicas, por ser lógicamente equivalentes, pero sólo existe una única tabla de verdad para cada función.
Una función booleana se puede transformar de una expresión algebraica a un diagrama de circuito compuesto por puertas lógicas conectadas en una estructura particular. Diagrama de circuito para F

Formas canónicas y estándar:
cualquier variable binaria puede tomar una de dos formas, xo x^\prime. Una función booleana se puede expresar en términos de nvariables binarias. Si todas las variables binarias se combinan juntas usando la operación AND, entonces hay un total de 2^ncombinaciones ya que cada variable puede tomar dos formas.
Cada una de las combinaciones se denomina minitérmino o producto estándar . Un minitérmino está representado por m_idonde ies el equivalente decimal del número binario al que se designa el minitérmino.
Nota importante: en un término mínimo, la variable binaria no está primada si la variable es 1 y está primada si la variable es 0, es decir, si el término mínimo es xy^\primeentonces eso significax=1y y=0.
Por ejemplo, para una función booleana en dos variables, los minitérminos son:
m_0=x^\prime y^\prime,\:m_1=x^\prime y,\:m_2=x y^\prime,\:m_3=x y

De manera similar, si las variables se combinan con la operación OR, el término obtenido se denomina maxterm o suma estándar . Un maxterm está representado por M_idonde ies el equivalente decimal del número binario al que se designa el maxterm.

Nota importante: en un término máximo, la variable binaria no está primada si la variable es 0 y está primada si la variable es 1, es decir, si el término máximo es x^\prime+yentonces eso significa x^\prime=1y y=0.
Por ejemplo, para una función booleana en dos variables, los términos máximos son:
M_0=x+y,\:M_1=x+y^\prime,\:M_2=x^\prime + y,\:M_3=x^\prime + y^\prime

Minitérminos y Maxtérminos para función en 3 variables –

Relación entre Mintérminos y Maxtérminos – Cada minitérmino es el complemento de su correspondiente maxtérmino.
Por ejemplo, para una función booleana en dos variables:

m_0=x^\prime y^\prime
(m_0)^\prime=(x^\prime y^\prime)^\prime
(m_0)^\prime=(x^\prime)^\prime + (y^\prime)^\prime
(m_0)^\prime=x+y=M_0
In general m_i = (M_i)^\prime or M_i = (m_i)^\prime

Construcción de funciones booleanas: ahora que sabemos qué son los términos mínimos y máximos, podemos usarlos para construir expresiones booleanas.

«Una función booleana se puede expresar algebraicamente a partir de una tabla de verdad dada formando un término mínimo para cada combinación de las variables que produce un 1 en la función y luego tomando el OR de todos esos términos».

Por ejemplo, considere dos funciones f_1y f_2con las siguientes tablas de verdad:

X y z F 1 F 2
0 0 0 0 0
0 0 1 1 0
0 1 0 0 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

 \begin{tabular}{||c||c||c||c||c||} \hline x&y&z&f_1&f_2\\ \hline \hline  0&0&0&0&0\\ \hline  0&0&1&1&0\\ \hline  0&1&0&0&0\\ \hline  0&1&1&0&1\\ \hline  1&0&0&1&0\\ \hline  1&0&1&0&1\\ \hline  1&1&0&0&1\\ \hline  1&1&1&1&1\\ \hline  \end{tabular}
La función
f_1
es 1 para las siguientes combinaciones de
x,\:y,\:z
– 001,100,111
Los minitérminos correspondientes son-
x^\prime y^\prime z
,
x y^\prime z^\prime
,
xyz
.
Por lo tanto, la expresión algebraica para
f_1
es-
f_1(x,y,z) = x^\prime y^\prime z + x y^\prime z^\prime + xyz
f_1(x,y,z) = m_1 + m_4 +m_7
De manera similar, la expresión algebraica para
f_2
es-
f_2(x,y,z) = m_3 + m_5 + m_6 + m_7
Si usamos la ley de De Morgans en
f_1
y
f_2
todos los 1 se convierten en 0 y todos los 0 se convierten en 1. Por lo tanto, obtenemos-
f_1(x,y,z)^\prime = m_0 + m_2 +m_3 + m_5 + m_6
f_2(x,y,z)^\prime = m_0 + m_1 + m_2 + m_4
Sobre el uso de la Ley de De Morgan de nuevo-
f_1(x,y,z) = (m_0 + m_2 +m_3 + m_5 + m_6)^\prime
f_1(x,y,z) = m_0^\prime . m_2^\prime . m_3^\prime . m_5^\prime . m_6^\prime
f_1(x,y,z) = M_0 . M_2 . M_3 . M_5 . M_6
y
f_2(x,y,z) = (m_0 + m_1 + m_2 + m_4)^\prime
f_2(x,y,z) = m_0^\prime . m_1^\prime . m_2^\prime . m_4^\prime
f_2(x,y,z) = M_0 . M_1 . M_2 . M_4
Podemos concluir de lo anterior que las funciones booleanas se pueden expresar como
suma de minitérminos
o un
producto de maxterms
.

“Se dice que las funciones booleanas expresadas como suma de minitérminos o producto de maxtérminos están en forma canónica .

  • Ejemplo 1: exprese la siguiente expresión booleana en formularios SOP y POS:
    F=x+y^\prime z
  • Solución: la expresión se puede transformar en formato SOP agregando variables faltantes en cada término multiplicando por k+k^\prime = 1dónde kestá la variable faltante.
    Se deduce del hecho de que: 1.x = x.1 = x
     F=x(y+y^\prime)+y^\prime z\\ F=xy+xy^\prime+y^\prime z\\ F=xy(z+z^\prime)+xy^\prime(z+z^\prime)+(x+x^\prime)y^\prime z\\ F=xyz + xyz^\prime + xy^\prime z + xy^\prime z^\prime + xy^\prime z + x^\prime y^\prime z
    Al reorganizar los términos mínimos en orden ascendente
     F=x^\prime y^\prime z + xy^\prime z^\prime + xy^\prime z + xyz^\prime + xyz\\ F=m_1 + m_4 + m_5 + m_6 + m_7
    Si queremos el formulario POS, podemos negar dos veces el formulario SOP como se indicó anteriormente para obtener
     F=M_0.M_2.M_3
    : Los formularios SOP y POS tienen una notación breve de representación :
     F(x,y,z) = \sum(1,4,5,6,7)\\ F(x,y,z) = \prod(0,2,3)\\

Formas estándar:
las formas canónicas son formas básicas que se obtienen de la tabla de verdad de la función. Estas formas generalmente no se utilizan para representar la función, ya que son engorrosas de escribir y es preferible representar la función en el menor número de literales posible.
Hay dos tipos de formularios estándar:

  1. Suma de productos (SOP): una expresión booleana que involucra términos AND con uno o más literales cada uno, combinados con OR.
  2. Producto de sumas (POS) Una expresión booleana que implica términos OR con uno o más literales cada uno, combinados con AND, p. ej.
    SOP- x^\prime + xy +yz^\prime
    POS- (x^\prime).(x + y).(y + z^\prime)
    

    Nota: las expresiones anteriores no son equivalentes, son solo ejemplos.

Preguntas de GATE CS Corner

Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.

1. GATE CS 2010, Pregunta 6
2. GATE CS 2008, Pregunta 7
3. GATE CS 2014 Conjunto-1, Pregunta 17

Referencias-

Diseño digital 5ª edición, por Morris Mano y Michael Ciletti

Este artículo es una contribución de Chirag Manwani . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *