Funciones Boleanas

ELO211: Sistemas Digitales
Tomás Arredondo Vidal
Este material está basado en:
Ì textos y material de apoyo:

Contemporary Logic Design 1st / 2nd edition. Gaetano

Borriello and Randy Katz. Prentice Hall, 1994, 2005
Ì material del curso ELO211 del Prof. Leopoldo Silva
Ì material en el sitio http://es.wikipedia.org

2: Funciones booleanas

1

2-Funciones y representacionesbooleanas
2.1 Lógica y álgebra de Boole
2.2 Funciones booleanas
2.3 Representaciones de funciones booleanas
2.4 Funciones de varias variables

2: Funciones booleanas

2

Lógica Booleana
Ì Definiciones básicas
r Una variable booleana (e.g. x, y) es un símbolo que
puede ser substituido por un elemento del
conjunto B={0,1}
r Una constante booleana es un valor perteneciente
al conjunto {0,1}r Una expresión (e.g. x+y, x·y, x’) esta compuesta de
variables, constantes y operadores (e.g. +, ·, ’)
r Una función booleana de n variables f(x1, x2, ..., xn)
es un expresión o formula que mapea f a un valor
del conjunto booleano B (0 o 1)
r Un literal es una variable o su complemento
2: Funciones booleanas

3

Álgebra de Boole
Ì Definición: el álgebra de Boole es un

sistemaalgebraico cerrado que contiene:
un conjunto de dos elementos {0, 1},
r dos operadores binarios {+, ·},
r un operador unitario { ‘ }.
r

2: Funciones booleanas

4

Lógica y álgebra de Boole
Ì El álgebra de Boole es la fundación matemática de

los sistemas digitales.
Ì Las operaciones del álgebra de Boole deben regirse
por propiedades y reglas lógicas llamados leyes o
postulados.
ÌEstos postulados se pueden usar para demostrar
leyes mas generales sobre expresiones booleanas.
Ì Estos postulados también se usan para simplificar
y optimizar expresiones booleanas y sistemas
digitales.
r Ejemplo: X AND (Y OR Y’) = X
(¿porque?)

2: Funciones booleanas

5

Álgebra de Boole
Ì Una expresión algebraica de Boole consiste de
r
r
r

un conjunto de B
operacionesbinarias { + , • }
una operaciones unitaria { ’ }

Ì B tiene dos elementos : a, b y los siguientes postulados se cumplen:

Clausura:

a + b esta en B, a • b esta en B

Conmutatividad:

a + b = b + a,

Asociatividad:

a + (b + c) = (a + b) + c
a • (b • c) = (a • b) • c

Identidad:

a + 0 = a,

Distributividad:

a + (b • c) = (a + b) • (a + c)
a • (b + c) = (a • b) + (a • c)Complementariedad:

a + a’ = 1,

a•b=b•a

a•1=a

a • a’ = 0
2: Funciones booleanas

6

Álgebra de Boole: Resumen
Ì Álgebra de Boole

B = {0, 1}
r variables
r + es el OR lógico, • es el AND lógico
r ’ es el NOT lógico
Ì Todos los postulados (axiomas) algebraicos se
cumplen
Ì La prioridad de los operadores es ‘, seguido por
AND y despues OR.
Ì El ‘ tiene la mayor prioridad.
ÌLos ( ) pueden cambiar el orden de evaluación.
r

2: Funciones booleanas

7

Álgebra de Boole: Teoremas
Ì Con la formulación de los postulados del

álgebra de Boole se pueden demostrar varias
proposiciones o teoremas de álgebra booleana
Ì Para las demostraciones de teoremas se
pueden usar:
tablas de verdad,
r postulados,
r y teoremas ya demostrados
r

2: Funciones booleanas8

Álgebra de Boole: Teoremas
Ì Definición: El álgebra de boole es un sistema algebraico cerrado

que contiene un conjunto B de dos elementos {0,1} y tres
operadores {·, +, ‘}.
Ì igualdad: Dos expresiones son iguales si una puede ser substituida

por otra.
Ì identidad:

1. X + 0 = X

1D. X • 1 = X

Ì nulo (elementos únicos):

2. X + 1 = 1

2D. X • 0 = 0

Ì idempotencia:3. X + X = X

3D. X • X = X

Ì involución:

4. (X’)’ = X
Ì complementariedad:

5. X + X’ = 1

5D. X • X’ = 0
2: Funciones booleanas

9

Álgebra de Boole: Teoremas
Ì
Ì
Ì
Ì
Ì

conmutatividad:
6. X + Y = Y + X
asociatividad:
7. (X + Y) + Z = X + (Y + Z)
distributividad:
8. X • (Y + Z) = (X • Y) + (X • Z)
unificación (fusión):
9. X • Y + X • Y’ = X
absorción:
10. X +...