Funciones Boleanas
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 +...
Regístrate para leer el documento completo.