algebra

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
CompuertasL´gicas
o
Minimizaci´n de Funciones
o

1

Introducci´n
o

2

Expresiones de Conmutaci´n
o

3

Compuertas L´gicas
o

4

Minimizaci´n de Funciones
o

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 Claude Shannon 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 operadoresl´gicos. Las variables pueden valer 0
o
o
´ 1. Y las operaciones b´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
o
Expresiones 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
oCompuertas 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

X ·0=0

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

Contenido
Introducci´n
o
Expresiones de Conmutaci´n
o
Compuertas 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

´
Algebrade 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 lossiguientes 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 de Boole

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

´
Algebra de Boole
Teoremas
Teorema del...