Unidad 4 - Algebra de Boole

MATEMTICA DISCRETA Y
AUTMATAS
UNIDAD 4 LGEBRA DE BOOLE
CAPTULO 10 - ROSEN
Ing. Silvana Hernndez

silvana.hernandez327@gmail.co
Matemtica discreta y autmatas
FUNCIONES BOOLEANAS
Definicin 1
El lgebra de Boole proporciona las operaciones y las leyes para

trabajar en el conjunto {0, 1}.
Las tres operaciones de un lgebra de Boole ms utilizados son:
Complemento:
Suma:
Producto Booleano
Las reglas de precedencia de los operadores son:
complementos, producto y suma
SUMA: OR +
COMPLEMENTO:
NOT
PRODUCTO: AND .
EXPRESIONES Y FUNCIONES
BOOLEANAS
Definicin 2
Sea B ={0, 1}, entonces Bn = {(x1, x2, , xn) / xi B, 1 i < n} es el

conjunto de todas las posibles n-tuplas de ceros y unos.
La variable x se llama variable booleana si toma
valores en el conjunto B. Una funcin Bn en B se llama
funcin booleana de grado n.
Las funciones booleanas se pueden representar utilizando
expresiones construidas con variables y operadores
booleanos. Las expresiones booleanas en las variables
x1, x2, , xn se definen recursivamente como:
0, 1, x1, x2, , xn Son expresiones booleanas;
Si E1 y E2 son expresiones booleanas, entonces E1, (E1E2) y
(E1 + E2) son expresiones booleanas
EXPRESIONES Y FUNCIONES
BOOLEANAS
Definicin 3
Definicin 4
Dos funciones booleanas de n variables F y G son iguales si, y

sol si, F(b1, b2, , bn) = G(b1, b2, , bn) para cualesquiera b1, b2, ,
bn de B. se dice que dos expresiones booleanas diferentes
son equivalentes si representan la misma funcin.
El dual de una expresin booleana se obtiene intercambiando entre
s la suma y el producto booleano, as como los ceros y los unos.
El dual de una funcin boolena F representada por una expresin
booleana es la funcin representada por el dual de dicha
expresin.
Una igualdad entre funciones booleanas sigue siendo vlida
cuando se toman duales a ambos lados de la igualdad, a esto se
lo conoce como Principio de Dualidad
PROPIEDADES
Propiedad
Nombre
Propiedad
Nombre
x + ( y + z) = (x + y )
+z
x.(y.z) = (x.y).z
Prop. asociativas
x=x
Prop. del doble

complemento
x + yz = (x + y ) (x +
z)
x (y + z) = xy + xz
Prop. distributivas
Prop. de De Morgan
x+x=x
x.x=x
Prop.de idempotencia
x+0=x
x .1 = x
Prop. del elem.

neutro
x +1 = 1
x.0=0
Prop. de acotacin
(x.y) = x + y
(x + y) = x.y
Prop. de absorcin
x+y=y+x
x.y = y.x
Prop. conmutativas
x + x.y = x
x.(x + y) = x
x+x=1
Prop. del inverso para

el 1
x.x = 0
Prop. del inverso para
DEFINICIN ABSTRACTA DEL ALGEBRA DE

BOOLE
Definicin 5
Un lgebra de boole es un conjunto B con dos operaciones

binarias, y , los elementos 0 y 1una operacin unaria , de
modo que para cualesquiera elementos x, y, z de B se
verifican las siguientes leyes:
x 0 = xLeyes del elem. neutro
x1=x
x x = 1Leyes del complemento
x x=0
(x y) z = x (y z)
Leyes asociativas
(x y) z = x (y z)
x y= y x Leyes conmutativas
xy=yx
x (y z) = (x y) (x z)
Leyes distributivas
x (y z) = (x y) (x z)
PRCTICA
Resolver los problemas del 1, 2 y 3.

Ejercicio 26
REPRESENTACIN DE FUNCIONES
BOOLEANAS
Definicin 6
Definicin 7
Un literal es una variable booleana complementada. Un

minitermino en las variables booleanas x1, x2, , xn es un
producto booleano y1.y2 , yn donde o yi = xi o yi = xi .
Por lo tanto, un minitermino es un producto de n literales
con un literal por cada variable.
A la suma de minitrminos que representa a la funcin se
le llama desarrollo en suma de productos o bien forma
normal disyuntiva de la funcin booleana
COMPLITUD FUNCIONAL
Definicin 8
Toda funcin booleana se puede expresar como una suma

booleana de minitrminos. Cada minitrmino es un producto
booleano de literales.
Por lo tanto, toda funcin booleana se puede represeentar
utilizando los operadores booleanos + .
Se dice que el conjunto {+, .,
} es funcionalmente completo.
Hay conjuntos ms pequeos de operadores funcionalmente
completo, lso mismos son: | o NAND y o NOR
NAND |
NOR
PRCTICA
Resolver los problemas del 1, 2 y 3.

Ejercicio 19
PUERTAS LGICAS
Definicin 9
El lgebra de Boole se usa para modelar los circuitos de dispositivos

electrnicos. Los elementos bsicos de los circuitos se llaman
puertas lgicas. Cada tipo de puerta implementa una operacin
booleana.
Los circuitos a estudiar producen una salida dependiente de la entrada
y no del estado actual del circuito, es decir, no tienen memoria.
Estos circuitos se llaman redes lgicas o circuitos combinacionales.
Veremos la construccin de una red lgica utilizando 3 tipos de

elementos:
Inversor o puerta NOT
Puerta OR
Puerta AND
SUMADORES
Definicin 10
Circuito de salida mltiple: circuito donde la salida consiste en

dos bits; s (bit de suma) y c (bit de arrastre).
Semisumador: circuito que se utiliza para realizar suma de dos
enteros positivos a partir de sus representaciones binarias.
Sumador completo: se usa para calcular el bit suma y el bit de
arrastre cuando suman dos bits y un bit de arrastre
PRCTICA
Resolver los problemas del 1, 3 y 5

Ejercicio 6

Unidad 4 - Algebra de Boole

Cargado por

Copyright:

Formatos disponibles

Unidad 4 - Algebra de Boole

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Unidad 4 - Algebra de Boole

Cargado por

Copyright:

Formatos disponibles

MATEMTICA DISCRETA Y

Ing. Silvana Hernndez

Matemtica discreta y autmatas

El lgebra de Boole proporciona las operaciones y las leyes para

Sea B ={0, 1}, entonces Bn = {(x1, x2, , xn) / xi B, 1 i < n} es el

Dos funciones booleanas de n variables F y G son iguales si, y

Prop. del doble

Prop. del elem.

Prop. del inverso para

Prop. del inverso para

DEFINICIN ABSTRACTA DEL ALGEBRA DE

Un lgebra de boole es un conjunto B con dos operaciones

Resolver los problemas del 1, 2 y 3.

Un literal es una variable booleana complementada. Un

Toda funcin booleana se puede expresar como una suma

Resolver los problemas del 1, 2 y 3.

El lgebra de Boole se usa para modelar los circuitos de dispositivos

Veremos la construccin de una red lgica utilizando 3 tipos de

Inversor o puerta NOT

Circuito de salida mltiple: circuito donde la salida consiste en

Resolver los problemas del 1, 3 y 5

También podría gustarte