ALGEBRA DE BOOLE PROBLEMAS RESUELTOS PDF

Álgebras booleanas y circuitos combinatorios , Propiedades de los circuitos combinatorios , Rincón de solución de problemas , Funciones booleanas y simplificación de circuitos, Aplicaciones , Autoevaluación del capítulo , Ejercicios para computadora CLICK AQUI PARA OTRA OPCION DE DESCARGA - VISUALIZACION CLASES AUDIOVISUALES CLICK AQUI Varias definiciones honran al matemático del siglo XIX George Boole; álgebra booleana, funciones booleanas, expresión booleana y anillo booleano, por nombrar unas cuantas. Boole es una de las personas de una larga cadena histórica que se preocuparon por formalizar y mecanizar el proceso del pensamiento lógico. De hecho, en 1854 Boole escribió un libro titulado The Laws of Thought (Las leyes del pensamiento). La contribución de Boole fue el desarrollo de una teoría de lógica que usa símbolos en lugar de palabras. Un análisis del trabajo de Boole se encuentra en [Hailperin]. Casi un siglo después del trabajo de Boole, C. E. Shannon observó en 1938 (vea [Shannon]) que el álgebra booleana se podía usar para analizar circuitos eléctricos. Fue así como el álgebra booleana se convirtió en una herramienta indispensable para el análisis y diseño de las computadoras electrónicas en las siguientes décadas. En este capítulo se exploran las relaciones del álgebra booleana con los circuitos. ÁLGEBRAS BOOLEANAS Y CIRCUITOS COMBINATORIOS Él es indigno, deshonesto, egoísta, engañoso, despreciable; pero él está allá y yo estoy acá. Dicen que él es normal y yo no. Bueno, si eso es normal, no lo quiero. DE MILAGRO EN LA CALLE 34 Circuitos combinatorios En una computadora digital sólo hay dos posibilidades, que se escriben como 0 y 1, para el objeto indivisible más pequeño. En última instancia, todos los programas y datos se pueden reducir a combinaciones de bits. A través de los años se ha usado una variedad de dispositivos en las computadoras digitales para almacenar bits. Los circuitos electrónicos permiten que estos dispositivos de almacenamiento se comuniquen entre sí. Un bit en una parte del circuito es trasmitido a otra parte del circuito como un voltaje. Entonces se necesitan dos niveles de voltaje; por ejemplo, un voltaje alto puede comunicar un 1 y un voltaje bajo, un 0. En esta sección analizaremos los circuitos combinatorios. La salida de un circuito combinatorio se define de manera única para cada combinación de entradas. Un circuito de este tipo carece de memoria; las entradas anteriores y el estado del sistema no afectan su salida. Los circuitos para los cuales la salida es una función, no sólo de las entradas sino también del estado del sistema, se llaman circuitos secuenciales y se estudiarán en el capítulo 12. Los circuitos combinatorios se pueden construir usando dispositivos de estado sólido, llamados compuertas, que son capaces de cambiar los niveles de voltaje (bits). Se comenzará por analizar las compuertas AND (y), OR (o) y NOT (no). Una compuerta AND recibe entradas x1 y x2, donde x1 y x2 son bits, y produce una salida denotada por x1 ∧ x2, donde Una compuerta AND se dibuja como se indica en la figura 11.1.1. Una compuerta OR recibe entradas x1 y x2, donde x1 y x2 son bits, y produce una salida denotada por x1 ∨ x2, donde Una compuerta OR se dibuja como se indica en la figura 11.1.2. Una compuerta NOT (o inversor) recibe una entrada x, donde x es un bit, y produce una salida denotada por x , donde Una compuerta NOT se dibuja como se indica en la figura 11.1.3. La tabla lógica de un circuito combinatorio lista todas las entradas posibles junto con las salidas producidas. A continuación aparecen las tablas lógicas para los circuitos AND, OR y NOT básicos (figuras 11.1.1 a la 11.1.3). Se observa que realizar la operación AND (OR) es lo mismo que tomar el mínimo (máximo) de dos bits x1 y x2. El circuito de la figura 11.1.4 es un ejemplo de un circuito combinatorio, ya que la salida y se define de manera única para cada combinación de entradas x1, x2 y x3. x1 ∧ x2 x1 x2 x1 ∨ x2 x x Definición 11.1.1 ▼ x1 ∧ x2 = 1 ifx1 = 1 and x2 = 1 0 otherwise. si y de otra manera. x1 ∨ x2 = 1 ifx1 = 1 or x2 = 1 0 otherwise. si o de otra manera. Figura 11.1.1 Compuerta AND. Figura 11.1.2 Compuerta OR. Figura 11.1.3 Compuerta NOT. ▼ Definición 11.1.2 ▼ Definición 11.1.3 ▼ x x Ejemplo 11.1.4 ▼ Ejemplo 11.1.5 ▼ ▼ La tabla lógica para este circuito combinatorio es la siguiente. Observe que se listan todas las combinaciones posibles de los valores de las entradas x1, x2 y x3. Para un conjunto determinado de entradas, el valor de la salida y se calcula rastreando el flujo a través del circuito. Por ejemplo, la cuarta línea de la tabla da el valor de la salida y para los valores de entrada x1 = 1, x2 = 0, x3 = 0. Si x1 = 1 y x2 = 0, la salida de la compuerta AND es 0 (vea la figura 11.1.5). Como x3 = 0, las entradas a la compuerta OR son ambas 0. Por lo tanto, la salida de la compuerta OR es 0. Como la entrada a la compuerta NOT es 0, se produce una salida y = 1. El circuito de la figura 11.1.6 no es un circuito combinatorio porque la salida y no es única para cada combinación de entradas x1 y x2. Por ejemplo, suponga que x1 = 1 y x2 = 0. Si la salida de la compuerta AND es 0, entonces y = 0. Por otro lado, si la salida de la compuerta AND es 1, entonces y = 1. Un circuito de este tipo sirve para almacenar un bit. Los circuitos combinatorios individuales se pueden interconectar. Es posible combinar los circuitos combinatorios C1, C2 y C3 de la figura 11.1.7, como se muestra, para obtener el circuito combinatorio C. x1 y x2 Figura 11.1.4 Un circuito combinatorio. Figura 11.1.5 Circuito de la figura 11.1.4 cuando x1 = 1 y x2 = x3 = 0. Figura 11.1.6 Un circuito que no es combinatorio. Ejemplo 11.1.6 ▼ Ejemplo 11.1.7 ▼ ▼ ▼ Un circuito combinatorio con una salida, como el de la figura 11.1.4, se representa mediante una expresión que usa los símbolos ∧, ∨ y ¬. Se sigue el flujo del circuito simbólicamente. Primero se aplica AND a x1 y x2 (figura 11.1.8), lo que produce la salida x1 ∧ x2. Esta salida después se une por OR con x3 para producir la salida (x1 ∧ x2) ∨ x3. Después se aplica NOT a esta salida. Entonces la salida y puede ser (11.1.1) Las expresiones como (11.1.1) se llaman expresiones booleanas. Las expresiones booleanas en los símbolos x1, . . . , xn se definen de manera recursiva como sigue. 0, 1, x1, . . . , xn (11.1.2) son expresiones booleanas. Si X1 y X2 son expresiones booleanas, entonces (11.1.3) son expresiones booleanas. Si X es una expresión booleana en los símbolos x1, . . . , xn, algunas veces se escribe Cualquiera de los símbolos x o x se llama literal. Utilice la definición 11.1.9 para demostrar que el lado derecho de (11.1.1) es una expresión booleana en x1, x2 y x3. ▼ Figura 11.1.7 El circuito combinatorio C se obtiene interconectando los circuitos combinatorios C1, C2 y C3. Figura 11.1.8 Representación de un circuito combinatorio mediante una expresión booleana. ▼ Ejemplo 11.1.8 ▼ y = (x1 ∧ x2) ∨ x3. a) (X 1), b) X1, c) X1 ∨ X2, d) X1 ∧ X2 X = X(x1, . . . , xn). ▼ Definición 11.1.9 ▼ Ejemplo 11.1.10 ▼ Por (11.1.2), x1 y x2 son expresiones booleanas. Por (11.1.3d), x1 ∧ x2 es una expresión booleana. Por (11.1.3a), (x1 ∧ x2) es una expresión booleana. Por (11.1.2), x3 es una expresión booleana. Como (x1 ∧ x2) y x3 son expresiones booleanas, por (11.1.3c), también lo es (x1 ∧ x2) ∨ x3. Por último, se aplica (11.1.3b) para concluir que es una expresión booleana. Si X = X(x1, . . . , xn) es una expresión booleana y se asignan valores a1, . . . , an en {0, 1} a x1, . . . , xn, se pueden usar las definiciones 11.1.1 a la 11.1.3 para calcular el valor de X. Este valor se denota por X(a1, . . . , an) o X(xi = ai). Para x1 = 1, x2 = 0 y x3 = 0, la expresión booleana X(x1, x2, x3) = de (11.1.1) se convierte en Se calculó de nuevo el cuarto renglón de la tabla en el ejemplo 11.1.5. En una expresión booleana en la que no se usan paréntesis para especificar el orden de las operaciones, se supone que ∧ es evaluado antes de ∨. Para x1 = 0, x2 = 0 y x3 = 1, el valor de la expresión booleana x1 ∧ x2 ∨ x3 es El ejemplo 11.1.8 mostró cómo se representa un circuito combinatorio con una salida como una expresión booleana. El siguiente ejemplo muestra cómo se construye un circuito combinatorio que representa una expresión booleana. Encuentre el circuito combinatorio correspondiente a la expresión booleana y escriba la tabla lógica para el circuito obtenido. Se comienza con la expresión x 2 ∨ x3 en el paréntesis interior. Esta expresión se convierte en un circuito combinatorio como el mostrado en la figura 11.1.9. Se aplica AND a la salida de este circuito y x1 para producir el circuito dibujado en la figura 11.1.10. Por último, se aplica OR a la salida de este circuito y x2 para dar el circuito deseado de la figura 11.1.11. La tabla lógica es la que sigue. ▼ ▼ (x1 ∧ x2) ∨ x3 ▼ X(1, 0, 0) = (1 ∧ 0) ∨ 0 = 0 ∨ 0 ya que 1 ∧ 0 = 0 = 0 ya que 0 ∨ 0 = 0 = 1 ya que 0 = 1. x1 ∧ x2 ∨ x3 = 0 ∧ 0 ∨ 1 = 0 ∨ 1 = 1. (x1 ∧ (x2 ∨ x3)) ∨ x2 (x1 ∧ x2) ∨ x3 Ejemplo 11.1.11 ▼ Ejemplo 11.1.12 ▼ Ejemplo 11.1.13 ▼ Figura 11.1.9 Circuito combinatorio correspondiente a la expresión booleana x 2 ∨ x3. Figura 11.1.10 Circuito combinatorio correspondiente a la expresión booleana x3 ∧ (x 2 ∨ x3) 1. ¿Qué es un circuito combinatorio? 2. ¿Qué es un circuito secuencial? 3. ¿Qué es una compuerta AND? 4. ¿Qué es una compuerta OR? 5. ¿Qué es una compuerta NOT? 6. ¿Qué es un inversor? 7. ¿Qué es una tabla lógica de un circuito combinatorio? 8. ¿Qué es una expresión booleana? 9. ¿Qué es una literal? x1 x2 x3 (x1 ∧ (x2 ∨ x3)) ∨ x2 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 Figura 11.1.11 Circuito combinatorio correspondiente a la expresión booleana (x1 ∧ (x2 ∨ x3)) ∨ x2. ▼ Sección de ejercicios de repaso Ejercicios En los ejercicios 1 al 6, escriba la expresión booleana que representa el circuito combinatorio, escriba la tabla lógica y escriba la salida de cada compuerta simbólicamente como en la figura 11.1.8. 1. 2. 3. 4. 5. 6. El circuito inferior de la figura 11.1.7. Los ejercicios 7 al 9 se refieren al circuito 7. Demuestre que este circuito no es un circuito combinatorio. 8. Demuestre que si x = 0, la salida y está determinada de manera única. 9. Demuestre que si x = 1, la salida y es indeterminada. En los ejercicios 10 al 14, encuentre el valor de las expresiones booleanas para 10. x1 = 1, x2 = 1, x3 = 0, x4 = 1. x1 ∧ x2 11. 12. 13. 14. 15. Usando la definición 11.1.9, demuestre que cada expresión en los ejercicios 10 al 14 es una expresión booleana. En los ejercicios 16 al 20, determine si la expresión indicada es booleana. Si lo es, utilice la definición 11.1.9 para demostrarlo. 16. 17. 18. 19. 20. 21. Encuentre el circuito combinatorio correspondiente a cada expresión booleana en los ejercicios 10 al 14 y escriba la tabla lógica. Un circuito de conmutación es una red eléctrica que consiste en interruptores cada uno de los cuales está abierto o cerrado. Un ejemplo aparece en la figura 11.1.12. Si el interruptor X está abierto (cerrado) se escribe X = 0 (X = 1). Los interruptores etiquetados con la misma letra, como B en la figura 11.1.12, están todos abiertos o todos cerrados. El interruptor X, como A en la figura 11.1.12, está abierto si y sólo si el interruptor X , como A , está cerrado. Si puede fluir corriente entre las terminales extremas izquierda y derecha del circuito, se dice que la salida del circuito es 1; de otra manera, se dice que la salida del circuito es 0. Una tabla de conmutación da la salida del circuito para todos los valores de los interruptores. La tabla de conmutación para la figura 11.1.12 es la siguiente: 22. Dibuje un circuito con dos interruptores A y B que tienen la propiedad de que la salida del circuito es 1 precisamente cuando ambos, A y B, están cerrados. Esta configuración se etiqueta A ∧ B y se llama circuito en serie. 23. Dibuje un circuito con dos interruptores A y B que tienen la propiedad de que la salida del circuito es 1 justo cuando uno de ellos, A o B, está cerrado. Esta configuración se etiqueta A ∨ B y se llama circuito en paralelo. 24. Demuestre que el circuito de la figura 11.1.12 se puede representar simbólicamente como Represente cada circuito en los ejercicios 25 al 29 simbólicamente y dé su tabla de conmutación. 25. 26. 27. 28. 29. Represente las expresiones en los ejercicios 30 al 34 como circuitos de conmutación y escriba las tablas de conmutación. En la sección anterior se definieron dos operadores binarios ∧ y ∨ en Z2 = {0, 1} y un operador unitario – en Z2. (En el resto de este capítulo Z2 denota el conjunto {0, 1}). Se vio que estos operadores podían implementarse en los circuitos como compuertas. En esta sección se analizan algunas propiedades del sistema que consiste en Z2 y los operadores ∧, ∨ y –. Si ∧, ∨ y – son los operadores de las definiciones 11.1.1 a la 11.1.3, entonces se cumplen las siguientes propiedades. a) Leyes asociativas: para todo a, b, c ∈ Z2. b) Leyes conmutativas: para todo a, b ∈ Z2. c) Leyes distributivas: para todo a, b, c ∈ Z2. d) Leyes de identidad: para todo a ∈ Z2. e) Leyes de complementos: para todo a ∈ Z2. Demostración Las demostraciones son verificaciones directas. Se probará la primera ley distributiva y las otras ecuaciones se dejan como ejercicios (vea los ejercicios 16 y 17). Debe demostrarse que para todo a, b, c ∈ z2. (11.2.1) Simplemente se evalúan ambos lados de (11.2.1) para todos los valores posibles de a, b y c en Z2 y se verifica que en cada caso se obtenga el mismo resultado. La tabla proporciona los detalles. Utilice el Teorema 11.2.1 para demostrar que los circuitos combinatorios de la figura 11.2.1 tienen salidas idénticas para entradas idénticas dadas. Las expresiones booleanas que representan los circuitos son, respectivamente, x1 ∨ (x2 ∧ x3), (x1 ∨ x2) ∧ (x1 ∨ x3). 11.2➜Propiedades de los circuitos combinatorios WWW Teorema 11.2.1 (a ∨ b) ∨ c = a ∨ (b ∨ c) (a ∧ b) ∧ c = a ∧ (b ∧ c) a ∨ b = b ∨ a, a ∧ b = b ∧ a a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) a ∨ 0 = a, a ∧ 1 = a a ∨ a = 1, a ∧ a = 0 a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) a b c a∧ (b ∨ c) (a ∧ b) ∨ (a ∧ c) 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 Ejemplo 11.2.2 ▼ Por el Teorema 11.2.1c), para todo a, b, c ∈ Z2 (11.2.2) Pero (11.2.2) dice que los circuitos combinatorios de la figura 11.2.1 tienen salidas idénticas para valores idénticos de entrada. Las expresiones booleanas arbitrarias se definen iguales si tienen los mismos valores para todas las asignaciones posibles de bits a las literales. Sean expresiones booleanas. Se dice que X1 es igual a X2, y se escribe X1 = X2 si para todo ai ∈ Z2. Demuestre que (11.2.3) Según la definición 11.2.3, la ecuación (11.2.3) se cumple si es cierta para todas las opciones de x y y en Z2. Entonces se puede simplemente elaborar una tabla que liste todas las posibilidades para verificar (11.2.3). Si se define una relación R en el conjunto de expresiones booleanas mediante la regla X1 R X2 si X1 = X2, R es una relación de equivalencia. Cada clase de equivalencia consiste en un conjunto de expresiones booleanas donde cada una es igual a cualquier otra. Por las leyes asociativas, Teorema 11.2.1a), se puede escribir sin ambigüedad (11.2.4) o bien, (11.2.5) ▼ a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) X1 = X1(x1, . . . , xn) and X2 = X2(x1, . . . , xn) X1(a1, . . . , an) = X2(a1, . . . , an) (x ∨ y) = x ∧ y. x y 1 1 1 0 0 1 0 0 (x ∨ y) x ∧ y 0 0 0 0 0 0 1 1 a1 ∨ a2 ∨ ··· ∨ an a1 ∧ a2 ∧ ··· ∧ an Figura 11.2.1 Los circuitos combinatorios a) y b) tienen salidas idénticas para entradas idénticas dadas y se dice que son equivalentes. Definición 11.2.3 ▼ y ▼ Ejemplo 11.2.4 ▼ ▼ para ai ∈ Z2. El circuito combinatorio correspondiente a (11.2.4) se dibuja como en la figura 11.2.2 y el circuito combinatorio correspondiente a (11.2.5) se dibuja como en la figura (11.2.3). Las propiedades listadas en el Teorema 11.2.1 se cumplen en muchos sistemas. Un sistema que satisface estas propiedades se llama una álgebra booleana. Las álgebras booleanas abstractas se examinarán en la sección 11.3. Una vez definida la igualdad de las expresiones booleanas, se define la equivalencia de los circuitos combinatorios. Se dice que dos circuitos combinatorios, cada uno con entradas x1, . . . , xn y una sola salida, son equivalentes si, siempre que los circuitos reciban las mismas entradas, producen las mismas salidas. Los circuitos combinatorios de las figuras 11.2.4 y 11.2.5 son equivalentes ya que, como se observa, tienen tablas lógicas idénticas. Si se define una relación R en un conjunto de circuitos combinatorios por la regla C1 R C2 si C1 y C2 son equivalentes (en el sentido de la definición 11.2.5), R es una relación de equivalencia. Cada clase de equivalencia consiste en un conjunto de circuitos combinatorios mutuamente equivalentes. El ejemplo 11.2.6 indica que es posible que los circuitos equivalentes no tengan el mismo número de compuertas. En general, es deseable emplear el menor número posible de compuertas para minimizar el costo de las componentes. Se deduce de inmediato, a partir de las definiciones, que los circuitos combinatorios son equivalentes si y sólo si las expresiones booleanas que los representan generan tablas lógicas idénticas. ▼ Figura 11.2.2 Compuerta OR con n entradas. Figura 11.2.3 Compuerta AND con n entradas. Definición 11.2.5 ▼ Ejemplo 11.2.6 ▼ Figura 11.2.4 Un circuito combinatorio y su tabla lógica. Figura 11.2.5 Circuito combinatorio y su tabla lógica, que es idéntica a la tabla lógica de la figura 11.2.4. Se dice que los circuitos de las figuras 11.2.4 y 11.2.5 son equivalentes porque tienen tablas lógicas idénticas. ▼ Sea C1 y C2 circuitos combinatorios representados respectivamente por las expresiones booleanas X1 = X1(x1, . . . , xn) y X2 = X2(x1, . . . , xn). Entonces C1 y C2 son equivalentes si y sólo si X1 = X2. Demostración El valor X1(a1, . . . , an) [respectivamente, X2(a1, . . . , an)] para ai ∈ Z2 es la salida del circuito C1 (respectivamente, C2) para entradas a1, . . . , an. De acuerdo con la definición 11.2.5, los circuitos C1 y C2 son equivalentes si y sólo si tienen las mismas salidas X1(a1, . . . , an) y X2(a1, . . . , an) para todas las entradas posibles a1, . . . , an. Entonces, los circuitos C1 y C2 son equivalentes si y sólo si X1(a1 ,. . . , an) = X2(a1, . . . , an) para todo a1 ∈ Z2. (11.2.6) Pero por la definición 11.2.3, la ecuación (11.2.6) se cumple si y sólo si X1 = X2. En el ejemplo 11.2.4 se demostró que Por el Teorema 11.2.7, los circuitos combinatorios (figuras 11.2.4 y 11.2.5) correspondientes a estas expresiones son equivalentes. ▼ (x ∨ y) = x ∧ y. Teorema 11.2.7 Ejemplo 11.2.8 ▼ 1. Establezca las leyes asociativas para ∧ y ∨. 2. Establezca las leyes conmutativas para ∧ y ∨. 3. Establezca las leyes distributivas para ∧ y ∨. 4. Establezca las leyes de identidad para ∧ y ∨. 5. Establezca las leyes de complementos para ∧, ∨ y _ . 6. ¿Cuándo son iguales dos expresiones booleanas? 7. ¿Qué son expresiones combinatorias equivalentes? 8. ¿Cuál es la relación entre las expresiones combinatorias y las expresiones booleanas que las representan? Sección de ejercicios de repaso Ejercicios Demuestre que los circuitos combinatorios de los ejercicios 1 al 5 son equivalentes. 1. 2. 3. 4. 5. Verifique las ecuaciones en los ejercicios 6 al 10. 6. 7. 8. 9. 10. Pruebe o desapruebe las ecuaciones en los ejercicios 11 al 15. 11. 12. 13. 14. 15. 16. Pruebe la segunda afirmación del Teorema 11.2.1c). 17. Pruebe los incisos a), b) y e) del Teorema 11.2.1. Se dice que dos circuitos de conmutación son equivalentes si las expresiones booleanas que los representan son iguales. 18. Demuestre que los circuitos de conmutación son equivalentes. 19. Para cada circuito de conmutación en los ejercicios 25 al 29 de la sección 11.1, encuentre un circuito de conmutación equivalente usando circuitos en paralelo y en serie que tengan el menor número posible de interruptores. 20. Para cada expresión booleana en los ejercicios 30 al 34 de la sección 11.1, encuentre un circuito de conmutación usando circuitos paralelos y en serie con el menor número posible de interruptores. Un circuito puente es un circuito de conmutación, como el que se ilustra en seguida, que usa circuitos no paralelos y no en serie. Para cada circuito de conmutación, encuentre un circuito de conmutación equivalente usando circuitos puente que tengan el menor número de interruptores. 21. 22. 23. 24. Para cada expresión booleana en los ejercicios 30 al 34 de la sección 11.1, encuentre un circuito de conmutación usando circuitos puente con el menor número posible de interruptores. x1 ∨ x1 = x1 x1 ∨ (x1 ∧ x2) = x1 x1 ∧ x2 = (x1 ∨ x2) x1 ∧ (x2 ∧ x3) = (x1 ∧ x2) ∨ (x1 ∧ x3) (x1 ∨ x2) ∧ (x3 ∨ x4) = (x3 ∧ x1) ∨ (x3 ∧ x2) ∨ (x4 ∧ x1) ∨ (x4 ∧ x2) x = x x1 ∧ x2 = x1 ∨ x2 x1 ∧ ((x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3)) = x2 ∧ x3 ((x1 ∧ x2) ∨ (x1 ∧ x3)) = (x1 ∨ x2) ∧ (x1 ∨ x3) (x1 ∨ x2) ∧ (x3 ∨ x4) ∧ (x3 ∧ x2) = 0 ★ En esta sección se consideran los sistemas generales que tienen propiedades como las indicadas en el Teorema 11.2.1. Se verá que, en apariencia, varios sistemas obedecen estas mismas leyes. Estos sistemas reciben el nombre de álgebras booleanas. Un álgebra booleana B consiste en un conjunto S que contiene elementos distintos 0 y 1, operadores binarios + y · en S, y un operador unitario en S que satisface las siguientes leyes. a) Leyes asociativas: para todo x, y, z ∈ S. b) Leyes conmutativas: para todo x, y ∈ S. c) Leyes distributivas: para todo x, y, z ∈ S. d) Leyes de identidad: para todo x ∈ S. e) Leyes de complementos: para todo x ∈ S. Si B es un álgebra booleana, se escribe B = (S, +, ·, , 0, 1). Las leyes asociativas se pueden omitir de la definición 11.3.1, puesto que se deducen de las otras leyes (vea el ejercicio 24). Por el Teorema 11.2.1, (Z2, ∧, ∨, –, 0, 1) es un álgebra booleana. (Se está estableciendo que Z2 denota el conjunto {0, 1}). Los operadores +, ·, en la definición 11.3.1 son ∧, ∨, –, respectivamente. Como es costumbre, suele abreviarse a · b como ab. También se supone que · se evalúa antes que +. Esto permite eliminar algunos paréntesis. Por ejemplo, (xy) + z se escribe de manera más sencilla como xy + z. Es adecuado hacer algunos comentarios respecto a la definición 11.3.1. En primer lugar, 0 y 1 son sólo nombres simbólicos y, en general, no tienen relación con los números 0 y 1. Este mismo comentario se aplica a + y ·, que sólo denotan operadores binarios y, en general, no tienen relación con la suma y multiplicación comunes. Sea U un conjunto universal y sea S = P (U) el conjunto potencia de U. Si se definen las siguientes operaciones en S, entonces (S, ∪, ∩, –, ∅, U) es un álgebra booleana. El conjunto vacío ∅ asume el papel de 0 y el conjunto universal U hace el papel de 1. Si X, Y y Z son subconjuntos de S, las propiedades a) a la e) de la definición 11.3.1 se convierten en las siguientes propiedades de conjuntos (vea el Teorema 2.1.12): ▼ ▼ (x + y) + z = x + (y + z) (x · y) · z = x · (y · z) x + y = y + x, x · y = y · x x · (y + z) = (x · y) + (x · z) x + (y · z) = (x + y) · (x + z) x + 0 = x, x · 1 = x x + x = 1, x · x = 0 X + Y = X ∪ Y, X · Y = X ∩ Y, X = X (X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z) b ) X ∪ Y = Y ∪ X, X ∩ Y = Y ∩ X a ) ( X ∪ Y ) ∪ Z = X ∪ (Y ∪ Z) 11.3➜Álgebras booleanas Definición 11.3.1 ▼ Ejemplo 11.3.2 ▼ Ejemplo 11.3.3 ▼ para todo X, Y, Z ∈ (U). para todo X, Y ∈ P (U). P En este punto se derivan algunas otras propiedades de las álgebras booleanas. Primero se demuestra que el elemento x en la definición 11.3.1e) es único. En un álgebra booleana, el elemento x de la definición 11.3.1e) es único. Específicamente, si x + y = 1 y xy = 0, entonces y = x . Demostración definición 11.3.1d) definición 11.3.1e) definición 11.3.1c) definición 11.3.1b) proporcionado definición 11.3.1e) definición 11.3.1b) definición 11.3.1c) proporcionado definición 11.3.1d) En un álgebra booleana, el elemento x recibe el nombre de complemento de x. Ahora es posible derivar varias propiedades adicionales de las álgebras booleanas. Sea B = (S, +, ·, , 0, 1) un álgebra booleana. Las siguientes propiedades se cumplen. a) Leyes de idempotencia: para todo x ∈ S. b) Leyes de acotación: para todo x ∈ S. c) Leyes de absorción: para todo x, y ∈ S. d) Leyes de involución: para todo x ∈ S. e) Leyes de 0 y 1: f) Leyes de De Morgan para álgebras booleanas: para todo x, y ∈ S. Como se explicó en el ejemplo 11.3.3, si U es un conjunto, (U) se puede considerar un álgebra booleana. Por lo tanto, las leyes de De Morgan, que para conjuntos se pueden enunciar para todo X, Y ∈ (U), se cumplen. Estas ecuaciones se verifican de manera directa (vea el Teorema 2.1.12), pero el Teorema 11.3.6 demuestra que son una consecuencia de otras leyes. Sin duda el lector ha observado que las ecuaciones que incluyen elementos de un álgebra booleana vienen en pares. Por ejemplo, las leyes de identidad [definición 11.3.1d)] son Se dice que estos pares son duales. El dual de una afirmación que incluye expresiones booleanas se obtiene sustituyendo 0 por 1, 1 por 0, + por · y · por +. El dual de es Cada condición en la definición de álgebra booleana (definición 11.3.1) incluye su dual. Por lo tanto, se tiene el siguiente resultado. El dual de un teorema de álgebras booleanas también es un teorema. Demostración Suponga que T es un teorema de álgebras booleanas. Entonces existe una prueba P de T que involucra sólo las definiciones de un álgebra booleana (definición 11.3.1). Sea P la secuencia de afirmaciones obtenidas al sustituir cada enunciado en P por su dual. Entonces P es una prueba del dual de T. El dual de (11.3.3) es (11.3.4) Antes se probó (11.3.3) [vea la prueba del Teorema 11.3.6a)]. Si se escribe el dual de cada afirmación en la demostración de (11.3.3), se obtiene la siguiente demostración de (11.3.4): Las demostraciones dadas en el Teorema 11.3.6 de las dos afirmaciones del inciso b) son duales entre sí. ▼ ▼ ▼ ▼ P P Ejemplo 11.3.7 ▼ (X ∪ Y ) = X ∩ Y, (X ∩ Y ) = X ∪ Y x + 0 = x, x1 = x. (x + y) = x y (xy) = x + y . x + x = x xx = x. x = x1 = x(x + x ) = xx + xx = xx + 0 = xx. Ejemplo 11.3.9 ▼ Ejemplo 11.3.11 ▼ Ejemplo 11.3.12 ▼ Definición 11.3.8 ▼ Teorema 11.3.10 ▼ 1. Defina álgebra booleana. 2. ¿Qué son las leyes de idempotencia para álgebras booleanas? 3. ¿Qué son las leyes de acotación para álgebras booleanas? 4. ¿Qué son las leyes de absorción para álgebras booleanas? 5. ¿Qué son las leyes de involución para álgebras booleanas? 6. ¿Qué son las leyes 0/1 para álgebras booleanas? 7. ¿Qué son las leyes de De Morgan para álgebras booleanas? 8. ¿Cómo se obtiene el dual de una expresión booleana? 9. ¿Qué puede decirse del dual de un teorema sobre álgebras booleanas? Sección de ejercicios de repaso Ejercicios 1. Verifique las propiedades a ) a c ) del ejemplo 11.3.3. 2. Sea S = {1, 2, 3, 6}. Defina x + y = mcm(x, y), x · y = mcd(x, y), para x, y ∈ S (mcm denota el mínimo común múltiplo y mcd el máximo común divisor). Demuestre que es un álgebra booleana. 3. S = {1, 2, 4, 8}. Defina + y · como en el ejercicio 2 y defina x = 8/x. Demuestre que no es un álgebra booleana. Sea Sn = {1, 2, . . . , n}. Defina x + y = máx{x, y}, x · y = mín{x, y}. 4. Demuestre que los incisos a) a c) de la definición 11.3.1 se cumplen para Sn. 5. Demuestre que es posible definir 0, 1 y de manera que es un álgebra booleana si y sólo si n = 2. 6. Rescriba las condiciones del Teorema 11.3.6 para conjuntos como los del ejemplo 11.3.3. 7. Interprete el Teorema 11.3.6 para conjuntos como los del ejemplo 11.3.3. Escriba el dual de cada afirmación en los ejercicios 8 al 14. 8. 9. 10. Si y , entonces y = z. 11. xy = 0 si y sólo si xy = x. 12. Si , entonces 13. x = 0 si y sólo si para toda y. 14. 15. Pruebe la afirmación del ejercicio 8 al 14. 16. Pruebe los duales de las afirmaciones de los ejercicios 8 al 14. 17. Escriba el dual del Teorema 11.3.4. ¿Cómo se relaciona el dual con el Teorema 11.3.4 en sí? 18. Pruebe las segundas afirmaciones de los incisos a), c) y f) del Teorema 11.3.6. 19. Pruebe las segundas afirmaciones de los incisos a), c) y f) del Teorema 11.3.6 obteniendo el dual de las demostraciones de las primeras afirmaciones. 20. Pruebe el Teorema 11.3.6, incisos d) y e). 21. Deduzca el inciso a) de la definición 11.3.1 a partir de los incisos b) a e) de la definición 11.3.1. 22. Sea U el conjunto de enteros positivos. Sea S la colección de subconjuntos X de U con uno de X o X finito. Demuestre que es un álgebra booleana. 23. Sea n un entero positivo. Sea S el conjunto de todos los divisores de n, incluyendo 1 y n. Defina + y · como en el ejercicio 2 y defina x = n/x. ¿Qué condición debe satisfacer n para que sea un álgebra booleana? 24. Demuestre que las leyes asociativas se deducen de las otras leyes de la definición 11.3.1. (S, +, · , , 1, n) (S, ∪, ∩, , ∅, U) x + x(y + 1) = x y = xy + x y x + y = 0 x = 0 = y. x + y = xx + y = x + z + z (x + y ) = xy (x + y)(x + 1) = x + xy + y (Sn, +, · , , 0, 1) (S, +, · , , 1, 8) (S, +, · , , 1, 6) x = 6 x Rincón de solución Álgebras booleanas de problemas Problema Sea (S, +, · , , 0, 1) un álgebra booleana y sea A un subconjunto de S. Demuestre que (A, +, · , , 0, 1) es un álgebra booleana si y sólo si 1 ∈ A y xy ∈ A para todo x, y ∈ A. Cómo atacar el problema Como la afirmación dada es del tipo “si y sólo si”, hay que probar dos afirmaciones: Si (A, +, · , , 0, 1) es un álgebra booleana, entonces 1 ∈ A y xy ∈ A para todo x, y ∈ A. (1) Si 1 ∈ A y xy ∈ A para todo x, y ∈ A, entonces (A, +, · , , 0, 1) es un álgebra booleana. (2) Para probar la afirmación (1), resultan útiles las leyes especificadas en la definición de “álgebra booleana” (definición 11.3.1) y las leyes derivadas del Teorema 11.3.6 que deben obedecer los elementos de un álgebra booleana. Para probar que (A, +, · , , 0, 1) es un álgebra booleana, se verificará que se satisfacen las leyes especificadas en la definición 11.3.1. Antes de continuar con la lectura es recomendable repasar la definición 11.3.1 y el Teorema 11.3.6. Cómo encontrar una solución Primero se intentará probar la afirmación (1). Se supone que (A, +, · , , 0, 1) es un álgebra booleana y se quiere probar que ■ 1 ∈ A y ■ xy ∈ A para todo x, y ∈ A. ★ ★ ★ La definición 11.3.1 dice que un álgebra booleana contiene el 1. Como (A, +, · , , 0, 1) es un álgebra booleana, 1 ∈ A. Ahora suponga que x, y ∈ A. La definición 11.3.1 dice que es un operador unitario en A. Esto significa que y ∈ A. La definición 11.3.1 también dice que · es un operador binario en A. Esto quiere decir que xy ∈ A. Esto completa la prueba de la afirmación (1). Ahora se intentará probar el enunciado (2). Esta vez se supone que 1 ∈ A y xy en A para todo x, y ∈ A y se quiere probar que (A, +, · , , 0, 1) es un álgebra booleana. Según la definición 11.3.1, se debe probar que A contiene elementos distintos 0 y 1 (3) + y · son operadores binarios en A. (4) es un operador unitario en A. (5) Las leyes asociativas se cumplen. (6) Las leyes conmutativas se cumplen. (7) Las leyes distributivas se cumplen. (8) Las leyes de identidad se cumplen. (9) Las leyes de complementos se cumplen. (10) A contiene el 1 por suposición. Para demostrar la afirmación (3), debe probarse que 0 ∈ A. Se tienen sólo dos suposiciones acerca de A: 1 ∈ A y si x, y ∈ A, entonces xy ∈ A. Todo lo que podemos hacer en este punto es combinar estas suposiciones; es decir, tomar x = y = 1 y examinar la conclusión: 11 ∈ A. Ahora el Teorema 11.3.6e) [aplicado al álgebra booleana (S, +, · , , 0, 1)] dice que 1 = 0. Sustituyendo 1 ahora se sabe que 10 ∈ A. Pero el Teorema 11.3.6b) dice que para cualquier x, x 0 = 0. Entonces 10 = 0 está en A. ¡Se tuvo éxito! A contiene el 1 y el 0. 0 y 1 son distintos porque son elementos del álgebra booleana (S, +, · , , 0, 1). Por lo tanto, la afirmación (3) queda demostrada. Para demostrar la aseveración (4), debe probarse que + y · son operadores binarios en A; es decir, si x, y ∈ A, entonces x + y y xy están en A. Considere probar que · es un operador binario en A. Se sabe que si x, y ∈ A, entonces xy ∈ A, que es muy cercano a lo que se desea probar. Si se pudiera de alguna manera sustituir y por y en la expresión xy , se podría concluir que xy ∈ A. Lo que se desea hacer es suponer que x, y ∈ A, para deducir posteriormente x, y ∈ A, (11) y luego concluir xy = xy ∈ A. Para deducir la expresión (11), es necesario demostrar que si y ∈ A, entonces y ∈ A. Pero esto es la afirmación (5). ¡Desviación! Se trabajará en esta última. Se supondrá que y ∈ A y se intentará probar que y ∈ A. Si se pudiera eliminar esa molesta x (en la hipótesis x, y ∈ A implica xy ∈ A), se tendría exactamente lo que se quiere. De hecho se puede eliminar x haciendo x = 1 puesto que 1y = y. Formalmente, se argumenta lo siguiente. Sea y en A. Como 1 ∈ A, y = 1y ∈ A. [y = 1y por la definición 11.3.1b) y 11.3.1d)]. La afirmación (5) queda demostrada. Ahora de regreso a la aseveración (4). Sean x, y ∈ A. Por la propiedad (5) que se acaba de probar, y ∈ A. Por la condición dada, xy = xy ∈ A [y = y por el teorema 11.3.6d)]. Esto demuestra que · es un operador binario en A. Las leyes de De Morgan [Teorema 11.3.6f)], de hecho, permiten intercambiar + y ·, para poder usarlos a fin de probar que si x, y ∈ A, entonces x + y ∈ A. Formalmente, se argumenta lo siguiente. Suponga que x, y ∈ A. Por la afirmación (5), se sabe que x y y están ambos en A. Como ya se probó que · es un operador binario en A, x y ∈ A. Por la aseveración (5), (x y ) ∈ A. Por las leyes de De Morgan [Teorema 11.3.6f)] y el Teorema 11.3.6d), x + y = x + y = (x y ) ∈ A. Por lo tanto, + es un operador binario en A. Esto prueba la aseveración (4). La siguiente afirmación que se debe probar es (6), que trata de verificar las leyes asociativas. (x + y) + z = x + (y + z), (xy)z = x(yz) para todo x, y, z ∈ A. Ahora bien, (S, +, · , , 0, 1) es un álgebra booleana y por ello las leyes asociativas se cumplen en S. Como A es un subconjunto de S, las leyes asociativas sin duda se cumplen en A. Entonces la afirmación (6) se cumple. Por la misma razón, las propiedades (7) a (10) también se cumplen en A. Por lo tanto, (A, +, · , , 0, 1) es un álgebra booleana. Solución formal Suponga que (A, +, · , , 0, 1) es un álgebra booleana. Entonces 1 ∈ A. Suponga que x, y ∈ A. Entonces y ∈ A. Por tanto, xy ∈ A. Ahora suponga que 1 ∈ A y xy ∈ A para todo x, y ∈ A. Haciendo x = y = 1, se obtiene 0 = 11 ∈ A. Tomando x = 1, se obtiene y = 1y ∈ A. Entonces es un operador unitario en A. Sustituyendo y por y , se obtiene xy = xy ∈ A. Así, · es un operador binario en A. Ahora bien, x + y = x + y = (x y ) ∈ A. Entonces + es un operador binario en A. Los incisos a) a e) de la definición 11.3.1 se cumplen automáticamente en A, ya que se cumplen en S. Por lo tanto (A, +, · , , 0, 1) es un álgebra booleana. Resumen de las técnicas de solución de problemas ■ Al intentar desarrollar una demostración, escriba con cuidado las suposiciones y qué se quiere probar. ■ Al intentar desarrollar una demostración, examine definiciones y teoremas que tengan relación. ■ Para probar que algo es un álgebra booleana, vaya directamente a la definición (definición 11.3.1). ■ Considere demostrar las afirmaciones en un orden diferente al dado. En este problema fue más fácil probar la afirmación (5) antes que la (4). ■ Intente diferentes sustituciones para las variables en una afirmación cuantificada universalmente. (Después de todo, “cuantificada universalmente” significa que la afirmación se cumple para todos los valores). Al hacer x = y = 1 en la afirmación xy ∈ A para todo x, y ∈ A, se pudo demostrar que 0 ∈ A. Un circuito permite realizar una tarea específica. Si se quiere construir un circuito combinatorio, el problema puede darse en términos de entradas y salidas. Por ejemplo, suponga que se desea construir un circuito combinatorio para calcular el OR-exclusivo de x1 y x2. Se puede establecer el problema haciendo una lista de las entradas y salidas que define el ORexclusivo. Esto equivale a elaborar la tabla lógica deseada. El OR-exclusivo de x1 y x2 escrito x1 ⊕ x2 se define en la tabla 11.4.1. Una tabla lógica, con una salida, es una función. El dominio es el conjunto de entradas y el recorrido o imagen es el conjunto de salidas. Para la función OR-exclusivo dada en la tabla 11.4.1, el dominio es el conjunto y el rango es el conjunto Si se pudiera desarrollar una fórmula para la función OR-exclusivo de la forma donde X es un expresión booleana, se podría resolver el problema de la construcción del circuito combinatorio. Se podría simplemente construir el circuito correspondiente a X. Las funciones que se pueden representar por expresiones booleanas se llaman funciones booleanas. Sea X(x1, . . . , xn) un expresión booleana. Una función f de la forma se llama función booleana. La función f: Z 3 2 → Z2 definida por es una función booleana. Las entradas y salidas se dan en la siguiente tabla. En el siguiente ejemplo se muestra cómo una función f: Z n 2 →Z 2 puede interpretarse como una función booleana. ▼ ▼ {(1, 1), (1, 0), (0, 1), (0, 0)} Z2 = {0, 1}. x1 x2 x1 ⊕ x2 0 1 1 0 1 1 1 0 0 1 0 0 x1 ⊕ x2 = X(x1, x2), f (x1, . . . , xn) = X(x1, . . . , xn) f (x1, x2, x3) = x1 ∧ (x2 ∨ x3) x1 x2 x3 f (x1, x2, x3) 1 0 1 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 11.4➜Funciones booleanas y simplificación de circuitos Definición 11.4.1 ▼ Ejemplo 11.4.2 ▼ Ejemplo 11.4.3 ▼ ▼ TABLA 11.4.1 ■ OR-exclusivo. Demuestre que la función f dada por la siguiente tabla es una función booleana. Considere el primer renglón de la tabla y la combinación (11.4.1) Observe que si x1 = x2 = x3 = 1, como se indica en el primer renglón de la tabla, entonces la expresión (11.4.1) es 1. Los valores de xi dados por cualquier otro renglón de la tabla dan un valor de 0 a la expresión (11.4.1). De manera similar, para el cuarto renglón de la tabla se puede construir la combinación (11.4.2) La expresión (11.4.2) tiene el valor 1 para los valores de xi dados por el cuarto renglón de la tabla, mientras que los valores de xi dados por cualquier otro renglón de la tabla dan el valor 0 para (11.4.2). El procedimiento es claro. Se considera un renglón R de la tabla cuya salida es 1. Después se forma la combinación x1 ∧ x2 ∧ x3 y se coloca una barra sobre cada xi cuyo valor sea 0 en el renglón R. La combinación formada es 1 si y sólo si las xi tienen los valores dados en el renglón R. Entonces, para el renglón 6, se obtiene la combinación (11.4.3) Después, se aplica OR a los términos de (11.4.1) a (11.4.3) para obtener la expresión booleana (11.4.4) Se asegura que f (x1, x2, x3) y (11.4.4) son iguales. Para verificarlo, primero se supone que x1, x2 y x3 tienen los valores dados por un renglón de la tabla para el que f (x1, x2, x3) = 1. Entonces una de las expresiones (11.4.1) a la (11.4.3) es 1, de manera que el valor de (11.4.4) es 1. Por otro lado, si x1, x2, x3 tienen los valores dados por un renglón de la tabla para el que f (x1, x2, x3) = 0, todas las combinaciones (11.4.1) a (11.4.3) son 0, de manera que el valor de (11.4.4) es 0. Entonces f y la expresión booleana (11.4.4) están de acuerdo en Z 3 2; por lo tanto, como se aseguró. Después de una definición más, se mostrará que el método del ejemplo 11.4.4 se puede usar para representar cualquier f : Z n 2 → Z2. Un mintérmino en los símbolos x1, . . . , xn es una expresión booleana de la forma donde cada yi es ya sea xi o X i. ▼ ▼ Ejemplo 11.4.4 ▼ x1 x2 x3 f (x1, x2, x3) 1 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 x1 ∧ x2 ∧ x3. x1 ∧ x2 ∧ x3. x1 ∧ x2 ∧ x3. (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3). f (x1, x2, x3) = (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3), y1 ∧ y2 ∧ ··· ∧ yn, Definición 11.4.5 ▼ Si f: Z n 2 →Z2, entonces f es una función booleana. Si f no es idénticamente cero, sea A1, . . . , Ak los elementos Aj de Z n 2 para los cuales f (Ai) = 1. Para cada Ai = (a1, . . . , an), sea donde entonces (11.4.5) Demostración Si f (x1, . . . , xn) = 0 para todo xi, entonces f es una función booleana, ya que 0 es una expresión booleana. Suponga que f no es idénticamente cero. Sea mi(a1, . . . , an) el valor obtenido de mi al sustituir cada xj por aj. Se deduce de la definición de mi que Sea A ∈ Z n 2. Si A = Ai para alguna i ∈ {1, . . . , k}, entonces f (A) = 1, mi(A) = 1 y Por otro lado, si A ≠ Ai para cualquier i ∈ {1, . . . , k}, entonces f (A) = 0, mi(A) = 0 para i = 1, . . . , k y Por lo tanto, (11.4.5) se cumple. La representación (11.4.5) de una función booleana f: Z n 2 → Z2 se llama forma disyuntiva normal de la función f. Diseñe un circuito combinatorio que calcule el OR-exclusivo de x1 y x2. La tabla lógica para la función OR-exclusivo x1 ⊕ x2 se reproduce en la tabla 11.4.1. La forma disyuntiva normal de esta función es (11.4.6) El circuito combinatorio correspondiente a (11.4.6) se presenta en la figura 11.4.1. ▼ Teorema 11.4.6 mi = y1 ∧ · · ·∧ yn, yj = x j si aj = 1 x j si aj = 0. f (x1, . . . , xn) = m1 ∨ m2 ∨ · · ·∨ mk . mi (A) = 1 siA = Ai 0 siA Ai . m1(A) ∨ · · ·∨mk (A) = 1. m1(A) ∨ · · ·∨mk (A) = 0. Definición 11.4.7 ▼ Ejemplo 11.4.8 ▼ x1 ⊕ x2 = (x1 ∧ x2) ∨ (x1 ∧ x2). Figura 11.4.1 Circuito combinatorio para el ORexclusivo. ▼ Suponga que una función está dada por una expresión booleana como y se desea encontrar la forma disyuntiva normal de f. Se podría escribir la tabla lógica de f y después usar el Teorema 11.4.6. De forma alternativa, se puede manejar directamente la expresión booleana usando las definiciones y resultados de las secciones 11.2 y 11.3. Se comenzará por distribuir los términos x3 como sigue: Aunque esto representa la expresión booleana como una combinación de términos de la forma y ∧ z, no está en la forma disyuntiva normal, ya que cada término no contiene todos los símbolos x1, x2 y x3. Sin embargo, esto tiene remedio de la siguiente forma: Esta expresión está en la forma disyuntiva normal de f. El Teorema 11.4.6 tiene un dual. En este caso la función f se expresa como (11.4.7) Cada Mi es de la forma (11.4.8) donde yj es ya sea xj o x j. Un término de la forma (11.4.8) se llama maxtérmino y la representación de f (11.4.7) se llama forma conjuntiva normal. Los ejercicios 24 al 28 exploran con mayor detalle los maxtérmino y la forma conjuntiva normal . f (x1, x2, x3) = (x1 ∨ x2) ∧ x3 (x1 ∨ x2) ∧ x3 = (x1 ∧ x3) ∨ (x2 ∧ x3). (x1 ∧ x3) ∨ (x2 ∧ x3) = (x1 ∧ x3 ∧ 1) ∨ (x2 ∧ x3 ∧ 1) = (x1 ∧ x3 ∧ (x2 ∨ x2)) ∨ (x2 ∧ x3 ∧ (x1 ∨ x1)) = (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) ∨(x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) = (x1 ∧ x2 ∧ x3) ∨ (x1 ∧ x2 ∧ x3) ∨(x1 ∧ x2 ∧ x3). f (x1, . . . , xn) = M1 ∧ M2 ∧ · · · ∧ Mk . y1 ∨ ··· ∨ yn, 1. Defina el OR-exclusivo. 2. ¿Qué es una función booleana? 3. ¿Qué es un mintérmino? 4. ¿Qué es la forma disyuntiva normal de una función booleana? 5. ¿Cómo se puede obtener la forma disyuntiva normal de una función booleana? 6. ¿Qué es un maxtérmino? 7. ¿Qué es la forma conjuntiva normal de una función booleana? Sección de ejercicios de repaso Ejercicios En los ejercicios 1 al 10. encuentre la forma normal disyuntiva de cada función y dibuje el circuito combinatorio correspondiente a esa forma normal disyuntiva. En la sección anterior se mostró cómo diseñar un circuito combinatorio usando las compuertas AND, OR y NOT que calculan una función arbitraria de Z2 n en Z2, donde Z2 = {0, 1}. En este sección se considera el uso de otros tipos de compuertas para implementar un circuito. También se estudia el problema de un diseño eficiente. Se concluye con la revisión de varios circuito útiles que tienen salidas múltiples. En toda la sección, a ∧ b se escribe ab. Antes de considerar alternativas para las compuertas AND, OR y NOT, debe darse una definición precisa de “compuerta”. Una compuerta es una función de Z2 n en Z2. La compuerta AND es la función ∧ de Z2 2 en Z2 definida como en la definición 11.1.1. La compuerta NOT es la función – de Z2 en Z2 como en la definición 11.1.3. La atención se centra en las compuertas que permiten construir circuitos combinatorios arbitrarios. Se dice que un conjunto de compuertas {g1, . . . , gk} es funcionalmente completo si, dado cualquier entero positivo n y una función f de Z2 n en Z2, es posible construir un circuito combinatorio que calcule f usando sólo las compuertas g1, . . . , gk. El Teorema 11.4.6 demuestra que un conjunto de compuertas {AND, OR, NOT} es funcionalmente completo. Un hecho interesante es que se pueda eliminar ya sea AND o bien OR del conjunto {AND, OR, NOT} y todavía obtener un conjunto de compuertas funcionalmente completo. Los conjuntos de compuertas {AND, NOT} {OR, NOT} son funcionalmente completos. Demostración Se demostrará que el conjunto de compuertas {AND, NOT} es funcionalmente completo y se deja para los ejercicios el problema de demostrar que el otro conjunto es funcionalmente completo (vea el ejercicio 1). Se tiene ley de involución ley de De Morgan. Por lo tanto, una compuerta OR se puede sustituir por una compuerta AND y tres compuertas NOT. (El circuito combinatorio se ilustra en la figura 11.5.1). ▼ ▼ ▼ ▼ 11.5➜Aplicaciones WWW Definición 11.5.1 ▼ Definición 11.5.3 ▼ Ejemplo 11.5.2 ▼ Ejemplo 11.5.4 ▼ Teorema 11.5.5 Dada cualquier función f: Zn 2 →Z2, por el Teorema 11.4.6 se puede construir un circuito combinatorio C usando las compuertas AND, OR y NOT, que calcula f. Pero la figura 11.5.1 muestra que cada compuerta OR se puede sustituir por compuertas AND y NOT. Por lo tanto, el circuito C se puede modificar de manera que consista sólo de compuertas AND y NOT. Entonces, el conjunto de compuertas {AND, NOT} es funcionalmente completo. Aunque ninguno de AND, OR o NOT por sí solos forma un conjunto funcionalmente completo (vea los ejercicios 2 al 4), es posible definir una nueva compuerta que, por sí misma, forme un conjunto funcionalmente completo. Una compuerta NAND recibe entradas x1 y x2, donde x1 y x2 son bits, y produce una salida denotada por x1 ↑x2, donde Una compuerta NAND se dibuja como se muestra en la figura 11.5.2. Muchos circuitos básicos usados hoy en las computadoras digitales se construyen a partir de compuertas NAND. El conjunto {NAND} es un conjunto de compuertas funcionalmente completo. Demostración Primero se observa que Por lo tanto, (11.5.1) (11.5.2) Las ecuaciones (11.5.1) y (11.5.2) muestran que tanto OR como NOT se pueden escribir en términos de NAND. Por el Teorema 11.5.5, el conjunto {OR, NOT} es funcionalmente completo. Se concluye que el conjunto {NAND} también es funcionalmente completo. Diseñe circuitos combinatorios usando compuertas NAND para comparar las funciones f1(x) = x y f2(x, y) = x ∨ y. Los circuitos combinatorios, derivados de las ecuaciones (11.5.1) y (11.5.2), se ilustran en la figura 11.5.3. ▼ x1 ↑ x2 = 0 ifx1 = 1 and x2 = 1 1 otherwise. Figura 11.5.1 Circuito combinatorio que usa sólo las compuertas AND y NOT para calcular x ∨ y. Figura 11.5.2 Compuerta NAND. x y x y Definición 11.5.6 ▼ si x1 y x2 = 1 de otra manera Teorema 11.5.7 Ejemplo 11.5.8 ▼ x1 x2 x1 x2 Considere el problema de diseñar un circuito combinatorio usando compuertas AND, OR y NOT para calcular la función f. La forma disyuntiva normal de f es (11.5.3) El circuito combinatorio correspondiente a (11.5.3) se presenta en la figura 11.5.4. El circuito combinatorio de la figura 11.5.4 tiene nueve compuertas. Como se demostrará, es posible diseñar un circuito con menos compuertas. El problema de encontrar el mejor circuito se llama problema de minimización. Existen muchas definiciones de “el mejor”. Para encontrar un circuito más sencillo equivalente al de la figura 11.5.4, se intenta simplificar la expresión booleana (11.5.3) correspondiente. Las ecuaciones (11.5.4) (11.5.5) donde E representa una expresión booleana arbitraria, son útiles al simplificar expresiones booleanas. La ecuación (11.5.4) se deriva como sigue: Ea ∨ Ea = E E = E ∨ Ea, Ea ∨ Ea = E(a ∨ a) = E1 = E f (x, y, z) = xyz ∨ xyz ∨ x y z. Figura 11.5.3 Circuitos combinatorios usando sólo compuertas NAND que calculan x y x ∨ y. ▼ Figura 11.5.4 Circuito combinatorio que calcula f (x, y, z) = xyz ∨ xyz ∨ x y z. usando las propiedades de álgebras booleanas. La ecuación (11.5.5) es en esencia la ley de absorción [Teorema 11.3.6c)]. Mediante las ecuaciones (11.5.4) y (11.5.5), se puede simplificar la ecuación (11.5.3) como sigue: por (11.5.4) por (11.5.5) por (11.5.4). Es posible una simplificación más, (11.5.6) aplicando la ley distributiva [definición 11.3.1c)]. La figura 11.5.5 muestra el circuito combinatorio correspondiente a (11.5.6), que requiere sólo tres compuertas. El circuito combinatorio en la figura 11.4.1 usa cinco compuertas AND, OR y NOT para calcular el OR-exclusivo, x ⊕ y, de x y y. Diseñe un circuito que calcule x ⊕ y usando menos compuertas AND, OR y NOT. Por desgracia, las expresiones (11.5.4) y (11.5.5) no ayudan a simplificar la forma disyuntiva normal de x ⊕ y. Entonces debemos experimentar con varias reglas booleanas hasta producir una expresión que requiera menos de cinco compuertas. Una solución está dada por la expresión cuya implementación requiere sólo cuatro compuertas. Este circuito combinatorio se muestra en la figura 11.5.6. El conjunto de compuertas disponible determina el problema de minimización. Como el estado de la tecnología determina las compuertas disponibles, el problema de minimización cambia con el tiempo. En los años 50, el problema típico consistía en minimizar circuitos considerando compuertas AND, OR y NOT. Se desarrollaron soluciones como el método de Quine-McCluskey y el método de mapas de Karnaugh. Se recomienda al lector consultar en [Mendelson] los detalles de estos métodos. Los avances en la tecnología de estado sólido han hecho posible fabricar componentes muy pequeños, llamados circuitos integrados, que en sí son circuitos completos. Actualmente, diseñar un circuito consiste en combinar compuertas básicas como AND, OR, NOT y NAND y los circuitos integrados para calcular las funciones deseadas. El álgebra booleana sigue siendo una herramienta esencial, como lo mostraría una hojeada a cualquier libro de diseño lógico como [McCalla]. x y ∨ x y xyz ∨ xyz ∨ x y z = xy ∨ x y z = xy ∨ xyz ∨ x y z = xy ∨ xz. xy ∨ xz = x(y ∨ z), (x ∨ y)xy Figura 11.5.5 Circuito combinatorio con tres compuertas equivalente al de la figura 11.5.4. Figura 11.5.6 Circuito combinatorio de cuatro compuertas que calcula el OR-exclusivo x ⊕ y de x y y. Ejemplo 11.5.9 ▼ ▼ Se concluye esta sección con el análisis de varios circuitos combinatorios útiles que tienen salidas múltiples. Un circuito con n salidas se puede caracterizar por n expresiones booleanas, como se aprecia el ejemplo siguiente. Escriba dos expresiones booleanas para describir el circuito combinatorio de la figura 11.5.7. La salida y1 se describe por la expresión y y2 se describe por la expresión El primer circuito se llama medio sumador (half adder) o semisumador. Un medio sumador acepta como entrada dos bits x y y para producir como salida la suma binaria cs de x y y. El término cs es un número binario de dos bits; s es el bit de la suma y c es el bit de acarreo. Circuito medio sumador Diseñe un circuito combinatorio sumador parcial. La tabla del medio sumador es la siguiente: Esta función tiene dos salidas, c y s. Se observa que c = xy y s = x ⊕ y. Entonces se obtiene el circuito medio sumador de la figura 11.5.8. Se usó el circuito de la figura 11.5.6 para considerar el OR-exclusivo. ▼ Ejemplo 11.5.10 ▼ y1 = ab, y2 = bc ∨ ab. Figura 11.5.7 Circuito combinatorio con dos salidas. Definición 11.5.11 ▼ Ejemplo 11.5.12 ▼ Figura 11.5.8 Circuito medio sumador. ▼ ▼ Un sumador completo suma tres bits y se emplea para sumar dos bits y un tercer bit de acarreo de una suma anterior. Un sumador completo acepta como entrada tres bits x, y y z y produce como salida la suma binaria cs de x, y y z. El término cs es un número binario de dos bits. Circuito sumador completo Diseñe un circuito combinatorio sumador completo. La tabla para el circuito sumador completo es la siguiente: Al verificar las ocho posibilidades, se observa que así, se pueden utilizar dos circuitos OR-exclusivo para calcular s. Para calcular c, primero se encuentra la forma disyuntiva normal (11.5.7) de c. Después se utilizan las ecuaciones (11.5.4) y (11.5.5) para simplificar la (11.5.7) como sigue: Es posible eliminar las compuertas adicionales si se escribe Se obtiene el circuito sumador completo de la figura 11.5.9. ▼ s = x ⊕ y ⊕ z; c = xyz ∨ xyz ∨ x yz ∨ x yz xyz ∨ xyz ∨ x yz ∨ x yz = xy ∨ x yz ∨ x yz = xy ∨ xyz ∨ x yz ∨ x yz = xy ∨ xz ∨ x yz = xy ∨ xz ∨ xyz ∨ x yz = xy ∨ xz ∨ yz. c = xy ∨ z(x ∨ y). x y z c s 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 Definición 11.5.13 ▼ Ejemplo 11.5.14 ▼ Figura 11.5.9 Circuito sumador completo. x z y c s ▼ El último ejemplo muestra cómo se emplean los circuitos medio sumador y sumador completo para construir un circuito que sume números binarios. Circuito para sumar números binarios Empleando los circuitos sumador parcial y sumador completo, diseñe un circuito combinatorio que calcule la suma de dos números de tres bits. Sea M = x3 x2 x1 y N = y3 y2 y1 los números que deben sumarse y sea z4 z3 z2 z1 la suma. El circuito que calcula la suma de M y N se ilustra en la figura 11.5.10. Se trata de una implementación del algoritmo estándar para sumar números ya que, de hecho, el “bit de acarreo” se acarrea a la siguiente suma binaria. Si se estuvieran utilizando registros de tres bits para la suma, de manera que la suma de dos números de tres bits fuera cuando mucho de tres bits, se podría usar el bit z4 en el ejemplo 11.5.15 como una bandera de saturación. Si z4 = 1, ocurrió un desbordamiento; si z4 = 0, no hubo saturación. En el siguiente capítulo (ejemplo 12.1.3), se estudia un circuito secuencial que utiliza un memoria interna primitiva para sumar números binarios. Medio sumador Sumador completo Sumador completo Ejemplo 11.5.15 ▼ Figura 11.5.10 Un circuito combinatorio que calcula la suma de dos números de tres bits. ▼ 1. ¿Qué es una compuerta? 2. ¿Qué es un conjunto de compuertas funcionalmente completo? 3. Dé ejemplos de conjuntos de compuertas funcionalmente completos. 4. ¿Qué es una compuerta NAND? 5. ¿El conjunto {NAND} es funcionalmente completo? 6. ¿Cuál es el problema de minimización? 7. ¿Qué es un circuito integrado? 8. Describa un circuito medio sumador. 9. Describa un circuito sumador completo. Sección de ejercicios de repaso Ejercicios 1. Demuestre que el conjunto de compuertas {OR, NOT} es funcionalmente completo. Demuestre que cada conjunto de compuertas en los ejercicios 2 al 5 no es funcionalmente completo. 2. {AND} 3. {OR} 4. {NOT} 5. {AND, OR} 6. Dibuje un circuito con sólo compuertas NAND que calcule xy. 7. Escriba xy usando sólo ↑. 8. Pruebe o desapruebe: para todo . Escriba expresiones booleanas para describir los circuitos de salidas múltiples en los ejercicios 9 al 11. 9. x, y, z ∈ Z2 x ↑ (y ↑ z) = (x ↑ y) ↑ z, 10. 11. 12. Diseñe circuitos usando sólo compuertas NAND para calcular las funciones de los ejercicios 1 al 10, sección 11.4. 13. ¿Puede reducir el número de compuertas NAND incluidas en cualquiera de los circuitos del ejercicio 12? 14. Diseñe circuitos que usen el menor número de compuertas AND, OR y NOT tanto como sea posible para calcular las funciones de los ejercicios 1 al 10, sección 11.4. 15. Diseñe un circuito medio sumador usando sólo compuertas NAND. 16. Diseñe un circuito medio sumador usando cinco compuertas NAND. Una compuerta NOR recibe entradas x1 y x2, donde x1 y x2 son bits, y produce una salida denotada por x1 ↓ x2, donde 17. Escriba xy, x ∨ y, x y x ↑ y en términos de ↓. 18. Escriba x ↓ y en términos de ↑. 19. Escriba la tabla lógica para la función nor. 20. Demuestre que el conjunto de compuertas {NOR} es funcionalmente completo. 21. Diseñe circuitos usando sólo compuertas NOR para calcular las funciones de los ejercicios 1 al 10, sección 11.4. 22. ¿Puede reducir el número de compuertas NOR empleadas en cualquiera de sus circuitos para el ejercicio 21? 23. Diseñe un circuito medio sumador con sólo compuertas NOR. 24. Diseñe un circuito medio sumador con cinco compuertas NOR. 25. Diseñe un circuito con tres entradas que produce 1 justo cuando dos o tres entradas tienen valor 1. 26. Diseñe un circuito que multiplique los números binarios x2 x1 y y2 y1. La salida será de la forma z4 z3 z2 z1. 27. Un módulo de 2 es un circuito que acepta como entrada dos bits b y FLAGIN y produce bits c y FLAGOUT. Si FLAGIN = 1, entonces c = b y FLAGOUT = 1. Si FLAGIN = 0 y b = 1, entonces FLAGOUT = 1. Si FLAGIN = 0 y b = 0, entonces FLAGOUT = 0. Si FLAGIN = 0, entonces c = b. Diseñe un circuito para implementar el módulo de 2. El complemento de 2 de un número binario se calcula utilizando el siguiente algoritmo. Algoritmo 11.5.16 Cómo encontrar el complemento de 2 Este algoritmo calcula el complemento de 2 CNCN − 1 · · · C2C1 del número binario M = BNBN−1 · · · B2B1. El número M se barre de derecha a izquierda y los bits se copian hasta que se encuentra 1. En adelante, si Bi = 0, se hace Ci = 1 y si Bi = 0, se hace Ci = 0. La bandera F indica si se encontró un 1 (F = verdadero) o no (F = falso). Entrada: BNBN−1 · · · B1 Salida: CNCN−1 · · · C1 complemento_dos(B) { F = falso i = 1 while (¬F ∧ i ≤ n) { Ci = Bi if (Bi == 1) F = verdadero i = i + 1 } while (i ≤ n) { Ci = Bi ⊕ 1 i = i + 1 } return C } Encuentre el complemento de 2 de los números en los ejercicios 28 al 30 usando el algoritmo 11.15.16. 28. 101100 29. 11011 30. 011010110 31. Utilizando módulos de 2, diseñe un circuito que calcule el complemento de 2 y3 y2 y1 del número binario de tres bits x3 x2 x1. 32. Sea * un operador binario en un conjunto S que contiene 0 y 1. Escriba un conjunto de axiomas para *, modelado tomando en cuenta las reglas que satisface NAND, de manera que si se define entonces es un álgebra booleana. 33. Sea * un operador binario en S que contiene 0 y 1. Escriba un conjunto de axiomas para *, modelado tomando en cuenta las reglas que satisface NOR, y las definiciones de –, ∨ y ∧ de manera que sea un álgebra booleana. 34. Demuestre que {→} es funcionalmente completo (vea la definición 1.2.3). 35. Sea B(x, y) una expresión booleana en las variables x y y que sólo usa el operador ↔ (vea la definición 1.2.8). a) Demuestre que si B contiene un número par de x, los valores de B( x , y) y B(x, y) son iguales para toda x y y. b) Demuestre que si B contiene un número impar de x, los valores de B( x , y) y B ( x . y ) son iguales para toda x y y. c) Utilice los incisos a) y b) para demostrar que {↔} no es funcionalmente completo. Paul Pluznikov contribuyó con este ejercicio. (S, ∨, ∧, , 0, 1) (S, ∨, ∧, , 0, 1) x1 ↓ x2 = 0 if x1 = 1 or x2 = 1 1 otherwise. si x1 = 1 o x2 = 1 de otra manera. x = x ∗ x x ∨ y = (x ∗ x) ∗ (y ∗ y) x ∧ y = (x ∗ y) ∗ (x ∗ y), ★ ★ ★ ★ ★ ★ Algunas referencias generales de álgebras booleanas son [Hohn; y Mendelson]. [Mendelson] contiene más de 150 referencias de álgebras booleanas y circuitos combinatorios. Los libros de diseño lógico incluyen [Kohavi; McCalla; y Ward]. [Hailperin] presenta un análisis técnico de las matemáticas de Boole. También proporciona referencias adicionales. El libro de Boole, The Laws of Thought (Las leyes del pensamiento), se ha reeditado (vea [Boole]). A causa de nuestro interés en las aplicaciones del álgebra booleana, la mayor parte del análisis se limitó al álgebra booleana . Sin embargo, las versiones de la mayoría de nuestros resultados siguen siendo válidas para álgebras booleanas finitas arbitrarias. Las expresiones booleanas en símbolos x1, . . . , xn sobre un álgebra booleana arbitraria se definen de manera recursiva como ■ Para cada s ∈ S, s es una expresión booleana. ■ x1, . . . , xn son expresiones booleanas. Si X1 y X2 son expresiones booleanas, también lo son Una función booleana sobre S se define como una función de Sn a S de la forma donde X es un expresión booleana en los símbolos x1, . . . , xn sobre S. Se puede definir una forma disyuntiva normal para f. Otro resultado es que si X y Y son expresiones booleanas sobre S y para todo xi ∈ S, entonces Y se puede derivar de X usando la definición de un álgebra booleana (definición 11.3.1). Otros resultados son que cualquier álgebra booleana finita tiene 2n elementos y que si dos álgebras booleanas tienen 2n elementos, en esencia, son la misma. Se concluye que cualquier álgebra booleana finita es esencialmente el ejemplo 11.3.3, el álgebra booleana de los subconjuntos de un conjunto universal finito U. Las demostraciones de estos resultados se encuentran en [Mendelson]. (S, +, · , , 0, 1) (Z2, ∨, ∧, , 0, 1). (X1), X 1, X1 + X2, X1 · X2. f (x1, . . . , xn) = X(x1, . . . , xn), X(x1, . . . , xn) = Y (x1, . . . , xn) Notas Sección 11.1 1. Circuito combinatorio 2. Circuito secuencial 3. Compuerta AND 4. Compuerta OR 5. Compuerta NOT (inversor) 6. Tabla lógica de un circuito combinatorio 7. Expresión booleana 8. Literal Sección 11.2 9. Propiedades de ∧, ∨ y –: leyes asociativas, conmutativas, distributivas, de identidad, de complemento (vea el Teorema 11.2.1) 10. Expresiones booleanas iguales 11. Expresiones booleanas equivalentes 12. Las expresiones combinatorias son equivalentes si y sólo si las expresiones booleanas que las representan generan tablas lógicas idénticas. Sección 11.3 13. Álgebra booleana 14. x : complemento de x 15. Propiedades de álgebras booleanas: leyes de idempotencia, de acotación, de absorción, de involución, 0 y 1, y leyes De Morgan Repaso del capítulo 16. Dual de afirmación que incluye expresiones booleanas 17. El dual de un teorema de álgebras booleanas también es un teorema. Sección 11.4 18. OR-exclusivo 19. Función booleana 20. Mintérmino: , donde cada yi es xi o x i 21. Forma disyuntiva normal 22. Cómo escribir una función booleana en la forma disyuntiva normal (Teorema 11.4.6) 23. Maxtérmino: , donde cada yi es xi o x i 24. Forma conjuntiva normal Sección 11.5 25. Compuerta 26. Conjunto de compuertas funcionalmente completo 27. Los conjuntos de compuertas {AND, not} y {OR, NOT} son funcionalmente completos. 28. Compuerta NAND 29. El conjunto {NAND} es un conjunto de compuerta funcionalmente completo. 30. Problema de minimización 31. Circuito integrado 32. Circuito medio sumador 33. Circuito sumador completo y1 ∨ y2 ∨ · · · ∨ yn, y1 ∧ y2 ∧ · · · ∧ yn, Autoevaluación del capítulo Sección 11.1 1. Escriba una expresión booleana que represente el circuito combinatorio y escriba la tabla lógica. 2. Encuentre el valor de la expresión booleana si x1 = x2 = 0 y x3 = 1. 3. Encuentre un circuito combinatorio correspondiente a las expresiones booleanas del ejercicio 2. 4. Demuestre que el siguiente circuito no es combinatorio. Sección 11.2 ¿Son equivalentes los circuitos combinatorios en los ejercicios 5 y 6? Explique. 5. (x1 ∧ x2) ∨ (x2 ∧ x3) 6. Pruebe o desapruebe las ecuaciones en los ejercicios 7 y 8. 7. 8. Sección 11.3 9. Si U es un conjunto universal y S = (U), el conjunto potencia de U, entonces es un álgebra booleana. Establezca las leyes de frontera y absorción para esta álgebra booleana. 10. Pruebe que en cualquier álgebra booleana, para toda x y y. 11. Escriba el dual de la afirmación del ejercicio 10 y pruébelo. 12. Sea U el conjunto de enteros positivos. Sea S una colección de subconjuntos finitos de U. ¿Por qué no es un álgebra booleana? Sección 11.4 En los ejercicios 13 al 16, encuentre la forma disyuntiva normal de una expresión booleana que tiene una tabla lógica igual a la tabla que se incluye y dibuje el circuito correspondiente a la forma disyuntiva normal. 13. (S, ∪, ∩, , ∅, U) (x(x + y · 0)) = x P x1 x2 x3 y 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 (x ∧ y) ∨ (x ∧ z) ∨ (x ∧ y ∧ z) = y ∨ (x ∧ z) (x ∧ y ∧ z) ∨ (x ∨ z) = (x ∧ z) ∨ (x ∧ z) (S, ∪, ∩, , ∅, U) 14. 15. 16. Sección 11.5 17. Escriba la tabla lógica para el circuito 18. Encuentre una expresión booleana en la forma disyuntiva normal para el circuito del inciso a) del ejercicio 6. Use métodos algebraicos para simplificar la forma disyuntiva normal. Dibuje el circuito correspondiente a la expresión simplificada. 19. Diseñe un circuito sólo con compuertas NAND para calcular x ⊕ y. 20. Diseñe un circuito sumador completo que use dos sumadores parciales y una compuerta OR. 1. Escriba un programa que tenga como entrada una expresión booleana en x y y e imprima la tabla lógica de la expresión. 2. Escriba un programa que reciba como entrada una expresión booleana en x, y y z e imprima la tabla lógica de la expresión. Ejercicios para computadora Capítulo 11 Autoevaluación 1. 2. 1. 3. 4. Suponga que x es 1. Entonces la entrada superior a la compuerta OR es 0. Si y es 1, entonces la entrada inferior a la compuerta OR es 0. Como ambas entradas a la compuerta OR son 0, la salida y de la compuerta OR es 0, lo cual es imposible. Si y es 0, entonces la entrada inferior a la compuerta OR es 1. Como la entrada a la compuerta OR es 1, la salida y de la compuerta OR es 1, lo cual es imposible. Por lo tanto, si la entrada al circuito es 1, la salida no está determinada de manera única. Entonces el circuito no es un circuito combinatorio. 5. Los circuitos son equivalentes. La tabla lógica para cualquiera de los circuitos es 6. Los circuitos no son equivalentes. Si x = 0, y = 1 y z = 0, la salida del circuito a) es 1, pero la salida del circuito b) es 0. 7. La ecuación es verdadera. La tabla lógica para cualquiera de las expresiones es 8. La ecuación es falsa. Si x = 1, y = 0 y z = 1, entonces pero 9. Leyes de acotación: para toda X ∈ S. Leyes de absorción: para toda X, Y ∈ S. 10. (ley de acotación) (ley de identidad) (ley de idempotencia) 11. Dual: (ley de acotación) (ley de identidad) (ley de idempotencia) 12. no es un operador unitario en S. Por ejemplo, . En los ejercicios 13 al 16, a ∧ b se escribe ab.

Archivo

Mostrar más
Related Posts Plugin for WordPress, Blogger...