5. algebra de boole

37
ALGEBRA DE BOOLE ALGEBRA DE BOOLE Sistemas Digitales Sistemas Digitales

Upload: miguel-pinto-bernabe

Post on 10-Nov-2014

60 views

Category:

Documents


3 download

TRANSCRIPT

ALGEBRA DE BOOLEALGEBRA DE BOOLE

Sistemas DigitalesSistemas Digitales

IntroducciónIntroducción

Arquitectura de Computadores

Aproximadamente en el año 1850 George Boole, desarrolló un sistema algebraico para formular proposiciones con símbolos.

George Boole1815-1864

IntroducciónIntroducción

Arquitectura de Computadores

Su álgebra consiste en un método para resolver problemas de lógica que recurre solamente a los valores binarios 1 y 0 y a tres operadores:

• AND (y) • OR (o) • NOT (no)

George Boole1815-1864

Variables BooleanasVariables Booleanas

Las variables Booleanas sólo toman los valores binarios: 1 ó 0.

Una variable Booleana representa un bit que quiere decir:– Binary digIT

Arquitectura de Computadores

Operaciones Booleanas: OROperaciones Booleanas: OR

Arquitectura de Computadores

xx yy x+yx+y

00 00 00

00 11 11

11 00 11

11 11 11

Operación OR:

Operaciones Booleanas: OROperaciones Booleanas: OR

Arquitectura de Computadores

xx yy x+yx+y

00 00 00

00 11 11

11 00 11

11 11 11

Operación OR:

Si una de las entradas es 1, entonces la salida es 1

Operaciones Booleanas: OROperaciones Booleanas: OR

Arquitectura de Computadores

Compuerta OR:

x

yx + y

Operaciones Booleanas: ANDOperaciones Booleanas: AND

Arquitectura de Computadores

xx yy x yx y

00 00 00

00 11 00

11 00 00

11 11 11

Operación AND:

Operaciones Booleanas: ANDOperaciones Booleanas: AND

Arquitectura de Computadores

xx yy x yx y

00 00 00

00 11 00

11 00 00

11 11 11

Operación AND:

Si una de las entradas es 0, entonces la salida es 0

Operaciones Booleanas: ANDOperaciones Booleanas: AND

Arquitectura de Computadores

Compuerta AND:

x

yx y

Operaciones Booleanas: NOTOperaciones Booleanas: NOT

Arquitectura de Computadores

Operación NOT:

xx xx

00 11

11 00

Operaciones Booleanas: NOTOperaciones Booleanas: NOT

Arquitectura de Computadores

Operación NOT:

xx xx

00 11

11 00

La salida es la negación de la entrada

Operaciones Booleanas: NOTOperaciones Booleanas: NOT

Arquitectura de Computadores

Compuerta NOT:

x x

Operaciones Booleanas: AplicaciónOperaciones Booleanas: Aplicación

Arquitectura de Computadores

Ejercicio:

Encontrar w = x y + y z para todas las combinaciones.

Operaciones Booleanas: AplicaciónOperaciones Booleanas: Aplicación

Arquitectura de Computadores

Ejercicio:

Encontrar w = x y + y z para todas las combinaciones.

xx yy zz xyxy yzyz ww

00 00 00 00 00 00

00 00 11 00 00 00

00 11 00 00 00 00

00 11 11 00 11 11

11 00 00 11 00 11

11 00 11 11 00 11

11 11 00 00 00 00

11 11 11 00 11 11

Algebra Booleana: IdentidadAlgebra Booleana: Identidad

Arquitectura de Computadores

Postulados de Identidad:

• 0 + x = ?

• 1 × x = ?

Algebra Booleana: IdentidadAlgebra Booleana: Identidad

Arquitectura de Computadores

Postulados de Identidad:

• 0 + x = x

• 1 × x = x

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Propiedad conmutativa:

• x + y = ?

• x y = ?

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Propiedad conmutativa:

• x + y = y + x

• x y = y x

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Axiomas de complemento:

• x x = ?

• x + x = ?

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Axiomas de complemento:

• x x = 0

• x + x = 1

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Teorema de idempotencia:

• x x = ?

• x + x = ?

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Teorema de idempotencia:

• x x = x

• x + x = x

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Teorema de elementos dominantes:

• x × 0 = ?

• x + 1 = ?

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Teorema de elementos dominantes:

• x × 0 = 0

• x + 1 = 1

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Propiedad distributiva:

• x ( y + z ) = ?

• x + ( y z ) = ?

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Propiedad distributiva:

• x ( y + z ) = x y + x z

• x + ( y z ) = ( x + y ) ( x + z )

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Ley involutiva:

• ( x ) = ?

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Ley involutiva:

• ( x ) = x

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Teorema de absorción:

• x + x y = ?

• x ( x + y ) = ?

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Teorema de absorción:

• x + x y = x

• x ( x + y ) = x

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Teorema del consenso:

• x + x y = ?

• x ( x + y ) = ?

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Teorema del consenso:

• x + x y = x + y

• x ( x + y ) = x y

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Teorema asociativo:

• x + ( y + z ) = ?

• x ( y z ) = ?

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Teorema asociativo:

• x + ( y + z ) = ( x + y ) + z

• x ( y z ) = ( x y) z

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Leyes de Morgan:

• ( x + y ) = x y

• ( x y ) = ?

Algebra Booleana: PropiedadesAlgebra Booleana: Propiedades

Arquitectura de Computadores

Leyes de Morgan:

• ( x + y ) = x y

• ( x y ) = x + y