representacion y minimizacion de funciones

Estructura de computadores

Tema 3: Representación y minimización de funciones lógicas

Tema 3: Representación y minimización de
funciones lógicas
3.1. Teoremas y postulados del álgebra de Boole
Definiciones
El álgebra de Boole se utiliza para la resolución de problemas de tipo
lógico-resolutivo, desarrollado en 1947 por George Boole.
Actualmente es muy utilizada en electrónica digital(en computadoras), y
sobre todo en síntesis de circuitos digitales.
El álgebra de Boole son las matemáticas de los sistemas digitales.

Variable lógica:
Sea el conjunto B = { 0, 1 }. Con este conjunto podemos codificar la
información en un computador.
Decimos que una variable x es lógica si su dominio es el conjunto B, es
decir, si x solo puede tomar los valores 0 y 1.

Complemento:
Elcomplemento de una variable es su inverso, y se indica con una barra
encima, ó con un apóstrofe.
Lo más utilizado siempre es la barra, pero en estos apuntes utilizamos
un apóstrofe por comodidad en la escritura.
Por ejemplo, el complemento de A es A'.
Si A = 0, entonces A' = 1
Si A = 1, entonces A' = 0

1

Estructura de computadores

Tema 3: Representación y minimización de funcioneslógicas

Postulados del algebra de Boole
Un conjunto B = { 0, 1 }, dotado de dos operaciones denotadas por + y · ,
es un álgebra de Boole si y sólo si se verifican los siguientes postulados o
leyes. En todos los casos consideramos ∀ a,b,c ∈ B.
1. Las operaciones + y · son conmutativas:
a+b=b+a
(conmutativa de la suma)
a·b =b·a
(conmutativa del producto)
2. Las operaciones + y · sonasociativas:
a + (b + c) = (a + b) + c (asociativa de la suma)
a · (b · c) = (a · b) · c
(asociativa del producto)
3. Cada operación es distributiva respecto a la otra:
+ respecto · : a + (b · c) = (a + b) · (a + c)
· respecto +: a · (b + c) = (a · b) + (a · c )
∀ a,b,c ∈ B
Un álgebra de Boole es simétrica con respecto a las operaciones + y ·, y a
los elementos identidad 0 y 1. Talcaracterística es el principio de dualidad,
es decir, si tenemos un teorema, podemos obtener otro dual, cambiando las
operaciones.

Reglas
Un álgebra de Boole B tiene las siguientes propiedades o reglas:
1.
2.
3.
4.
5.
6.
7.
8.
9.

Identidad (+):
Elementos dominantes (+):
Elementos dominantes (·):
Identidad (·):
Idempotencia (+):
Complemento (+):
Idempotencia (·):
Complemento (·):Involutiva:

10. Ley de absorción (dual):
11. Ley del consenso (dual):

a+0=a
a+1=1
a·0=0
a·1=a
a+a=a
a + a' = 1
a·a=a
a · a' = 0
a'' = a

∀a∈B
∀a∈B
∀a∈B
∀a∈B

a + (a · b) = a y a · (a+b) = a
a + (a' · b) = a + b y a · (a’+b) = a · b

Las 2 últimas reglas se pueden obtener a partir de las leyes y de las otras
reglas más sencillas.
a' = Complementario de a

2

Estructurade computadores

Tema 3: Representación y minimización de funciones lógicas

3.2. Teoremas de De Morgan
De Morgan propuso dos teoremas que constituyen una parte muy
importante del álgebra de Boole.
Teoremas de De Morgan:
1. El complemento de una suma de variables es igual al producto de los
complementos de las variables:

(a + b)' = a' · b'

∀ a,b ∈ B

2. El complemento de unproducto de variables es igual a la suma de los
complementos de las variables:

(a · b)' = a' + b'

∀ a,b ∈ B

Estos teoremas son válidos para cualquier número de variables.

Ejemplos:
•

a · b · c = a' + b' + c'

•

(a + b + c)' = a' · b' · c'

•

(a' + b' + c') ' = a · b · c

•

((a + b + c) · d) ' = (a + b + c)' + d' = (a + b + c)' + d' = (a' · b ' · c') + d'

•

((a·b·c)+ (d ·e·f)) ' = (a ·b·c)' · (d·e ·f)' = (a'+b'+c') · (d'+e'+f')

•

((a+b) ·c'·d' + e + f') ' = ((a+b) ·c'·d')' · e' · f = ((a+b)'+c+d) · e ' · f =
= ((a' · b') + c + d) · e' · f

Funciones lógicas
Función lógica:
Dadas n variables lógicas x , x2, ... x , decimos que F es una función
1
n
lógica de las citadas variables si:
F(x1, x2, ... xn) ∈ B
es decir, si F sólo toma los valores...