Mapas De Karnaugh

Contenido Introducci´n o Expresiones de Conmutaci´n o Compuertas L´gicas o Minimizaci´n de Funciones o

´ Algebra de Boole
Prof. Rodrigo Araya E. raraya@inf.utfsm.cl
Universidad T´cnica Federico Santa Mar´ e ıa Departamento de Inform´tica a

Valpara´ 1er Semestre 2006 ıso,

RAE

´ Algebra de Boole

Contenido Introducci´n o Expresiones de Conmutaci´n o Compuertas L´gicas oMinimizaci´n de Funciones o

1

Introducci´n o Expresiones de Conmutaci´n o Compuertas L´gicas o Minimizaci´n de Funciones o

2

3

4

RAE

´ Algebra de Boole

Contenido Introducci´n o Expresiones de Conmutaci´n o Compuertas L´gicas o Minimizaci´n de Funciones o

Introducci´n o

En 1815 George Boole propuso una herramienta matem´tica a ´ llamada Algebra de Boole. Luego en 1938 ClaudeShannon propuso que con esta ´lgebra a es posible modelar los llamados Sistemas Digitales.

RAE

´ Algebra de Boole

Contenido Introducci´n o Expresiones de Conmutaci´n o Compuertas L´gicas o Minimizaci´n de Funciones o

´ Algebra de Boole

´ El Algebra de Boole es un sistema matem´tico que utiliza a variables y operadores l´gicos. Las variables pueden valer 0 o o ´ 1. Y las operacionesb´sicas son OR(+) y AND(·). a Luego se definen las expresiones de conmutaci´n como un o n´mero finito de variables y constantes, relacionadas mediante u los operadores (AND y OR). En la ausencia de par´ntesis, se utilizan las mismas reglas de e precedencia, que tienen los operadores suma (OR) y multiplicaci´n (AND) en el ´lgebra normal. o a

RAE

´ Algebra de Boole

Contenido Introducci´n oExpresiones de Conmutaci´n o Compuertas L´gicas o Minimizaci´n de Funciones o

´ Algebra de Boole

Leyes En el ´lgebra de Boole se cumplen las siguientes Leyes: a 1) Conmutatividad: X +Y =Y +X X ·Y =Y ·X

RAE

´ Algebra de Boole

Contenido Introducci´n o Expresiones de Conmutaci´n o Compuertas L´gicas o Minimizaci´n de Funciones o

´ Algebra de Boole
Leyes 2) Asociatividad: X + (Y + Z ) =(X + Y ) + Z X · (Y · Z ) = (X · Y ) · Z 3) Distributividad: X + (Y · Z ) = (X + Y ) · (X + Z ) X · (Y + Z ) = (X · Y ) + (X · Z )

RAE

´ Algebra de Boole

Contenido Introducci´n o Expresiones de Conmutaci´n o Compuertas L´gicas o Minimizaci´n de Funciones o

´ Algebra de Boole
Identidades 4) Elementos Neutros (Identidad): X +0=X X ·1=X 5) Complemento: X +X =1 X ·X =0

RAE

´Algebra de Boole

Contenido Introducci´n o Expresiones de Conmutaci´n o Compuertas L´gicas o Minimizaci´n de Funciones o

´ Algebra de Boole
Leyes 6) Dominaci´n: o X +1=1 Demostraci´n: o X + 1 = (X + 1) · 1 = (X + 1) · (X + X ) (X + 1) · (X + X ) = X + (1 · X ) = 1 7) Idempotencia: X +X =X X ·X =X
RAE ´ Algebra de Boole

X ·0=0

Contenido Introducci´n o Expresiones de Conmutaci´n oCompuertas L´gicas o Minimizaci´n de Funciones o

´ Algebra de Boole
Leyes 8) Doble complemento: X =X . 9) Absorci´n: o X +X ·Y =X X · (Y + X ) = X Demostraci´n: o X + X · Y = (X · 1) + (X · Y ) = X · (1 + Y ) = X
RAE ´ Algebra de Boole

Contenido Introducci´n o Expresiones de Conmutaci´n o Compuertas L´gicas o Minimizaci´n de Funciones o

´ Algebra de Boole

Leyes 10) DeMorgan: A·B =A+B A+B=A·B

RAE

´ Algebra de Boole

Contenido Introducci´n o Expresiones de Conmutaci´n o Compuertas L´gicas o Minimizaci´n de Funciones o

´ Algebra de Boole
Teoremas Luego se establecen los siguientes Teoremas: Teorema de la Simplificaci´n o A+A·B =A+B A · (A + B) = A · B Demostraci´n: o → A·A=0 A·A+B =B (A + B) · (A + B) = B A · (A + B) · (A + B) = A · B A · (A + B) = A · B
RAE ´ Algebra deBoole

Contenido Introducci´n o Expresiones de Conmutaci´n o Compuertas L´gicas o Minimizaci´n de Funciones o

´ Algebra de Boole
Teoremas Teorema del complemento unico ´ Suponemos 2 complementos para A (A1 y A2 ) A + A1 = 1 A + A2 = 1 A · A1 = 0 A · A2 = 0 Luego, A1 = A1 · 1 = A1 · (A + A2 ) = A1 · A + A1 · A2 A1 = 0 + A2 · A1 A1 = A · A2 + A1 · A2 = (A + A1 ) · A2 A1 = 1 · A2 = A2
RAE...