Lo mas importante

ELO211: Sistemas Digitales Tomás Arredondo Vidal 1er Semestre – 2007
Este material está basado en:
Ì textos y material de apoyo:

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

Contemporary Logic Design 1st / 2nd edition. Gaetano

2: Funciones booleanas

1

2-Funciones yrepresentaciones booleanas
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 alconjunto {0,1} r Una expresión o formula booleana (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 a f un valor del conjunto booleano B (0 o 1)
2: Funciones booleanas 3

Álgebra de Boole
Ì Un literal es una variable o su complemento Ì Definición: el álgebra de Boole esun

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

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 un conjunto de B r operaciones binarias { +, • } r una operaciones unitaria { ’ } Ì El conjunto B contiene dos elementos : a, b tales que Clausura: Commutatividad: Asociatividad: Identidad: Distributividad: Complementariedad: a + b esta en B, a • b esta en B a + b = b + a, a•b=b•a a + (b + c) = (a + b) + c a • (b • c) = (a • b) • c a + 0 = a, a•1=a a + (b • c) = (a + b) • (a + c) a • (b + c) = (a • b) + (a • c) a + a’ = 1, a • a’ = 0
2:Funciones booleanas 6

los siguientes postulados se cumplen:

Álgebra de Boole: Resumen
Ì Algebra de Boole

= {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 deevaluación.

rB

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, postulados y teoremas ya demostrados

2: Funciones booleanas

8

Á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
Ì nulo (elementos únicos):

1D. X • 1 = X 2D. X • 0 = 0 3D. X • X = X

2. X + 1 = 1
Ì idempotencia:

3. 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 6D. X • Y = Y • X asociatividad: 7. (X + Y) + Z = X + (Y + Z) 7D. (X • Y) • Z = X • (Y • Z) distributividad: 8. X • (Y + Z) = (X • Y) + (X • Z) 8D. X + (Y • Z) = (X + Y) • (X + Z) unificación (fusión): 9. X • Y + X • Y’ = X 9D. (X + Y) • (X +...