Teoremas

POSTULADOS DEL ÁLGEBRA BOOLEANA Los postulados son suposiciones fundamentales que también se denominan axiomas. El álgebra booleana se basa en 10 axiomas, a partir de los cuales es posible deducir todos los teoremas. A continuación se enumeran los postulados por parejas, debido a la dualidad que existe en cada par. Por ejemplo al cambiar en el postulado 1ª todos los 0 por 1 y “.” Por “+”, se obtiene el postulado 1b al efectuar cambios parecidos. Tal dualidad también se cumple para los demás postulados, así como para los teoremas que serán presentados posteriormente. A partir de este momento, los postulados se presentarán e ilustraran mediante el empleo de conmutadores. Obsérvese que un conmutador abierto o un circuito abierto se representa por 0, y que un conmutador cerrado o un circuito cerrado se representa por 1. Postulado 1a: 0 • 0 = 0 Dos conmutadores abiertos conectados en serie dan por resultados un circuito abierto. Postulado 1b: 1 + 1 = 1 Dos conmutadores cerrados conectados en paralelo dan por resultado un circuito cerrado

Postulado 2a: 0 • 1 = 0 Un conmutador abierto conectado en serie con un conmutador cerrado da por resultado un circuito abierto Postulado 2b: 1 + 0 = 1 Un conmutador cerrado conectado en paralelo con un conmutador abierto da por resultado un circuito cerrado. Postulado 3a: 1 • 0 = 0 Un conmutador cerrado conectado en serie con un conmutador abierto da por resultado un circuito abierto. Postulado 3b: 0 + 1 = 1 Un conmutador abierto conectado en paralelo con un conmutador cerrado da por resultado un circuito cerrado. Postulado 4a: 1• 1 = 1 Un conmutador cerrado conectado en serie con un conmutador cerrado da por resultado un circuito cerrado. Postulado 4b: 0 + 0 = 0 Un conmutador abierto conectado en paralelo con un conmutador abierto da por resultado un circuito abierto.

Postulado 5a: Ō = 1 Un conmutador que no está abierto se encuentra cerrado. Postulado 5b: Ī = 0 Un conmutador que no está cerrado se encuentra abierto. TEOREMAS DEL ÁLGEBRA BOOLEANA Los teoremas son reglas fundamentales, o leyes. En esta sección se describen 10 teoremas del álgebra booleana, los cuales se demuestran por medios de varios métodos, incluyendo diagramas de compuertas lógicas, tablas de verdad y referencias a postulados y teoremas previamente establecidos. TEOREMA 1 Teorema 1a: X • Y = Y • X Este teorema establece que las entradas a una compuerta AND son perfectamente intercambiables, y que la salida no es afectada por el orden en que se hayan escrito las entradas. Para la demostración del teorema consúltense las figuras 1.

Teorema 1b: X + Y = Y + X

Éste es el dual del teorema 1ª. Su demostración se muestra en las figuras 1. X

Y X•Y =

Y

Y•X X •••••

Figura 1. Diagramas lógicos Teorema 2

Las leyes asociativas

Teorema 2a: X • (Y • Z) = (X • Y) • Z Este teorema establece que no importa el orden en que se apliquen las variables a una expresión AND. Teorema 2b: X + (Y + Z) = (X + Y) + Z

Este teorema establece que no importa el orden en que se apliquen las variables a una expresión OR. Teorema 3

Las leyes ídem potentes

Teorema 3a: X • X = X Este teorema establece que si a un valor binario se le aplica la operación AND consigo mismo, la salida resultante tiene el valor binario de la entrada. Teorema 3b: X + X = X Este teorema afirma que si a un valor binario se le aplica la operación OR consigo mismo, entonces la salida resultante tiene el valor binario de la entrada.

Teorema 4

Las leyes de las identidades

Teorema 4a: X • 1 = X Teorema 4b: X + 0 = X

Teorema 5

Las leyes de los elementos nulos (ceros)

Teorema 5a: X • 0 = 0

Teorema 5b: X + 1 = 1 Teorema 6 Las leyes de los complementos Teorema 6a: X • X = 0 Teorema 6b: X + X = 1 Teorema 7

Las leyes de absorción Teorema 7a: X + X • Y = X Teorema 7b: X • (X + Y) = X

Teorema 8

Las leyes distributivas Teorema 8a: X • (Y + Z) = X • Y + X • Z

El resultado del miembro derecho puede obtenerse por medio de la multiplicación booleana, multiplicando por X la expresión que esta dentro del paréntesis esto se muestra en la tabla de verdad de la tabla 1.

Tabla 1.- Demostración del teorema 8a: X • (Y + Z) = X • Y + X • Z X 0 0 0 0

Y 0 0 1 1

Z 0 1 0 1

Y+Z 0 1 1 1

X • (Y+Z) 0 0 0 0

X •Y 0 0 0 0

X •Z 0 0 0 0

X•Y + X•Z 0 0 0 0

1 1 1 1

0 0 1 1

0 1 0 1

0 1 1 1

0 1 1 1

0 0 1 1

0 1 0 1

0 1 1 1

Elementos idénticos en esta columna Teorema 8b: (X + Y) • (X + Z) = X + Y • Z Este teorema puede demostrarse por medio del álgebra booleana como se observa en el ejemplo que se presenta a continuación. (X + Y) • (X + Z) = X • X + X • Y + X • Z + Y • Z X(1 + Z) + Y • Z = X + Y • Z

= X+X•Y+X•Z+Y•Z

= X(1 + Y) + X • Z + Y • Z

Teorema 9

La ley de la doble negación Teorema 9: X = X, donde X = X

Teorema 10

Los teoremas de De Morgan

Los teoremas (leyes) de De Morgan son muy utilizados en álgebra booleana para obtener el complemento de una expresión o una función, así como también para simplificar expresiones y funciones booleanas. Tabla 2.- Demostraciones del primer teorema de De Morgan: X • Y = X + Y X

Y

X•Y

X•Y

X

Y

X+Y

0 0 1 1

0 1 0 1

0 0 0 1

1 1 1 0

1 1 0 0

1 0 1 0

1 1 1 0

Teorema 10a: X • Y = X + Y. Éste es el primero de los teoremas de De Morgan. Establece que el complemento de una operación AND es igual a la operación OR de los complementos de las variables. Se demuestra en la tabla siguiente.

Para implementar el primer teorema de De Morgan se deben cambiar todos los productos boléanos “•” por sumas booleanas “+” y tomar el complemento de cada variable (o constante). Si una variable es complementada para empezar con ella, debe tomarse nuevamente su complemento, para obtener la variable sin complementar, de acuerdo con el teorema 9 de la doble negación. Tabla 3.- Demostración del segundo teorema De Morgan: X + Y = X • Y X

Y

X+Y

0 0 1 1

0 1 0 1

0 1 1 1

X+Y

X

Y

X•Y

1 1 1 0 1 0 0 0 1 0 0 0 Elementos idénticos en esta columna

1 0 0 0

Teorema 10b: X + Y = X • Y Éste es el segundo teorema de De Morgan, el cual establece que el complemento de una operación OR es igual a la operación AND aplicada a los complementos de las variables, lo cual se muestra en la tabla 3.

Para implementar el segundo teorema de De Morgan se deben cambiar todas las sumas booleanas “+” por productos booléanos “•” y tomar los complementos de cada una de las variables (o constantes). Si se toma el complemento de una variable para empezar con ella, debe tomarse de nuevo su complemento con la finalidad de obtener la variable sin complementar, de acuerdo con el teorema 9 de la doble negación.