Álgebra de Boole
MCC Mónica Ruiz Martínez
Algebra de Boole
• También llamada álgebra Booleana, tanto los conjuntos como las proposiciones tienen propiedades similares. Estas propiedades se usan para definir una estructura matemática llamada álgebra de Boole, en honor a George Boole(1813-1864).
Álgebra de Boole
• Sea B un conjunto en el cual se han definido dos operaciones binarias, + y *, y una operación unaria, denotada por ‘; sean 0 y 1 dos elementos diferentes de B. Entonces a la sextupla.
• <B, +, *, ‘, 0, 1>
cont
• Se le llama álgebra de Boole si se cumplen los siguientes axiomas para elementos a, b, c cualesquiera en el conjunto B:
Leyes conmutativas
(1ª) a + b = b+a (1b) a*b= b*a
Leyes distributivas
(2ª) a+(b*c)=(a+b)*(a+c) (2b) a*(b+c)= (a*b)+(a*c)
Leyes de identidad
(3ª) a+0=a (3b) a*1=a
Leyes de complemento
(4ª) a+a’=1 (4b) a * a’= 0
• Sea B el conjunto de dos elementos, {0,1}, con operaciones + y *.
+ 1 01 1 10 1 0
* 1 01 1 00 0 0
Los complementos se definen por 1’= 0 y 0’= 1
Ejemplos
• Defina la suma, producto y complementos de estas sucesiones bit por bit como en la tabla anterior. Dados los elementos
a=1101010 b=1011011Tenemos a+b= 1111011 a*b=1001010 a’=0010101
• Sea C una colección de conjuntos cerrados bajo uniones, intersecciones y complementos. C es entonces un álgebra de Boole, con el conjunto vacío Ø como el elemento cero y el conjunto universal U como el elemento unidad.
• Sea ∏ el conjunto de las proposiciones. ∏ es entonces un álgebra de Boole bajo las operaciones ᴧ y ᴠ con la negación como �complemento.
Principio de Dualidad
• El dual de cualquier enunciado en un álgebra de Boole B es el enunciado obtenido al intercambiar las operaciones + y *, e intercambiar los correspondientes elementos identidad 0 y 1, en el enunciado original. Ejemplo:
• (1+a)*(b+0)=b es (0*a)+(b*1)=b
Principio de Dualidad
• El dual de cualquier teorema en álgebra de Boole es también un teorema.
Teoremas Básicos
Leyes de idempotencia
(5ª) a+a=a (5b) a*a=a
Leyes de acotamiento
(6ª) a+1= 1 (6b) a*0=0
Leyes de absorción
(7ª) a+(a*b)= a (7b) a*(a+b)=a
Leyes asociativas
(8ª) (a+b)+c= a+(b+c) (8b) (a*b)*c=a*(b*c)
Ley de involución (a’)’=a
(9a)0’=1 (9b) 1’=0
Leyes DeMorgan
(10a) (a+b)’= a’*b’ (10b) (a*b)’=a´+b’
Expresiones de Boole: Forma Suma de Productos
• Una expresión Booleana E (x₁,…xn), es una variable o una expresión construida con estas variables que usan los operadores Booleanas +, *, ‘.
• Ejemplo E=(x+y’z)’ y F=((xy’z’+y)’ + x’z’ Una literal es una variable o una variable complementada, como x, x’.Un producto fundamental es un literal o un producto de dos o mas literales en los cuales no hay dos literales con la misma variable. Por ejemplo, xz’, xy’z, x’yz.Sin embargo xyx’z, xyzy no lo son xyx’z, xyzy .
• Observe que xyx’z=xx’yz=0yz=0Ya que x *x’= 0 , por la ley del complementoY yz * 0= 0, por la ley de acotamiento.
Ejemplo 2 xyzy= xyyz=xyzYa que y*y=y por la ley de idempotencia.Todo producto de Boole se puede reducir a 0 o a un producto fundamental.
Mini términos
• Una expresión de Boole E se dice que está en forma de suma de productos o en forma miniterm o miniterminos si E es un producto fundamental, o es la suma de dos productos fundamentales.
• Ejemplo E= ((ab)’c)’((a’+c)(b’+c’)’
Miniterminos utilizando Tablas
A B C S0 0 0 10 0 1 00 1 0 00 1 1 11 0 0 01 0 1 01 1 0 11 1 1 1
Teniendo las salidas se utilizan únicamente las salidas verdaderas (1) y viendo el número de términos que son (en este caso 3, A, B, C) y cuando en la combinación es falsa (0) se cambia a verdadera (1), un ejemplo para cuando las variables son falsas(0) seria ABC = A'B'C' en este caso se cambiaron todas las combinaciones que había ya que todas eran falsas se convierten a verdaderas para ello se tienen que negar y cuando todas las entradas o una es verdadera no se niega la variable y se queda como esta.Después de haber obtenido cada uno de los miniterminos se unen en forma de suma.
S = A'B'C' + A'BC + ABC' + ABC
Maxiterminos• Un término suma, también llamado maxitérmino, consiste de la
suma Booleana de literales (variables o sus complementos).• Cuando dos o más términos suma son multiplicados, la expresión resultante es un producto de sumas.• Producto de sumas (POS, del inglés product of-sums)
Puede contener un término con una sola variable A’(A+B’+C)
• Una expresión POS (estándar o no) es igual a 0 solo cuando uno o más de los términos suma en la expresión es igual a 0.
Ejemplos
1. A+BC ley distributiva2. (A+B)(A+C)
Maxiterminos utilizando Tablas de verdadA B C S
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
En los maxiterminos utilizamos las salida falsas (0) y en caso que una de las variables sea verdadera (1) se tiene que cambiar falsa (0) y para eso se niega la variable un ejemplo seria cuando A = 0, B= 0, C = 1, A+B+C, en este caso hay una variable verdadera la cual se tiene ke cambiar a falsa (0) y quedaria A = 0, B = 0, C'= 0, A+B+C', esta seria la forma en que se obtiene cada uno de los maxiterminos.Después de obtener cada uno de los maxiterminos entre estos se multiplica .
S = (A+B+C') (A+B'+C) (A'+B+C) (A'+B+C')
Compuertas Lógicas
• Los circuitos lógicos se construyen a partir de ciertos circuitos elementales llamados compuertas lógicas.
• Estos circuitos pueden visualizarse como máquinas que contienen uno o más dispositivos de entrada y exactamente un dispositivo de salida.
Compuerta OR
• Denotamos la salida de una compuerta OR en la forma
Y=A+B
En donde la «adición» está definida
+ 1 01 1 10 1 0
Supongamos A=11001
B= 10010La compuerta OR producirá la sucesión
A+B=11011
• Para dos entradas A y B , las sucesiones especiales que dan estas combinaciones contienen cuatro bits, como sigue
A=0011 B=0101• El valor de la salida para estas sucesiones
especiales (para n entradas contendrán 2ⁿ bits)se le llama tabla de verdad para el circuito
Compuerta AND
• Una compuerta AND tiene dos entradas como mínimo y su operación lógica es un producto entre ambas, no es un producto aritmético, aunque en este caso coincidan.
Compuerta NOT
• Se trata de un inversor, es decir, invierte el dato de entrada, por ejemplo; si pones su entrada a 1 (nivel alto) obtendrás en su salida un 0 (o nivel bajo), y viceversa. Esta compuerta dispone de una sola entrada. Su operación lógica es s igual a a invertida
Compuerta XOR
A B
0 0 0
0 1 1
1 0 1
1 1 0
XOR u OR Exclusivo. La XOR se diferencia de la OR en que si sus dos entradas son '1' entonces el resultado será '0'. El símbolo para expresar XOR viene dado por signo + inscrito en un círculo. La tabla de la verdad de función XOR es:
También existen compuertas para las operaciones lógicas NAND (que es una AND con un inversor (NOT) a la salida), la NOR (una OR con un inversor a la salida) y la XNOR (o NOR exclusivo representado por un punto inscrito en un círculo, que no es más que una XOR con un inversor a la salida) entre algunas otras pero diría que las ya mencionadas son las más importantes.
Compuertas LógicasNombre Símbolo
AND
OR
NOT
NAND
NOR
XOR
XNOR
Circuitos Lógicos
Teorema 8: Los circuitos lógicos vienen en varios patrones.Tratamos un patrón que corresponde a una expresión Boole de suma productos. Específicamente un circuito AND-OR tiene varias entradas, con algunas entradas y sus complementos alimentando a cada compuerta AND. Las salidas de todas las compuertas AND alimentan una sola compuerta OR.
Ejemplo• ACB+AC’B+A’C
AND
AND
AND
ACB
Referencias Bibliográficas
Matemáticas para la ComputaciónSeymour LipschutzEd Mc Graw Hill