Propiedades Circuitos Combinatorios

Tema 4.3.2

Definición. Una algebra booleana es B= (S, +, · , - , 0, 1 ) con 0 y 1 Î S tal que

(a) Leyes asociativas

		(x +y) + z = x + (y+Z), (x· y) · z = x · (y·z)

(b) Leyes conmutativas

		x+y = y+x,   x·y = y · x

© Leyes distributivas

		x·(y+z) = x·y + x ·z, x+(y·z) = (x + y) · (x + z)

(d) Elementos neutros

		x+0 = x,      x · 1 = x

(e) Ley de complementos

		x+x’ = 1, x ·x = 0

Ejemplos:

	(Z2, Ù, Ú, -, 0, 1) es un algebra Booleana, donde el conjunto Z2={0,1}
	(P(U), È, Ç, c, Æ, U) es un agebra Booleana, P(U) contiene a todos los subconjuntos de un universo U.

(P, Ù, Ú, Ø, false, true) es un algebra Booleana. El cojunto de las proposiciones que vimos en el capítulo 2.

Teorema:

(a) Leyes de Idempotencia

		x + x = x, x · x = x

(b) Leyes de Acotamiento

		x+1= 1, x · 0 = 0

© Leyes de Absorción

		x + xy = x , x(x + y) = x

(d) Ley de Involución

		(x) = x,

(e) Leyes recíprocas de los complementos

		0 = 1, 1 = 0

(f) Leyes De Morgan

		(x + y) = x y , (xy) = x + y

Definición. El dual de una expresión booleana se obtiene intercambiando + con · y también 0 con 1.

Ejemplo: (x + y) = x y

	La expresión dual es

			(x · y) = x + y

Teorema: Si dos expresiones booleanas son iguales, la igualdad también se cumple con sus respectivas expresiones duales.

NOTA: Cuando se demuestra que dos expresiones son iguales. La misma demostración tomando en cada paso expresiones duales comprueba el teorema dual, a esto se le llama demostración dual.