Download EC-1723 2 Álgebra de Boole

George Boole
Á LGEBRA DE B OOLE
Matemático británico (1815-1864).
En su libro Laws of Thought dió forma matemática a la
lógica de Aristóteles (1847).
Circuitos Digitales EC1723
Su lógica simbólica le llevó a crear una familia de
álgebras conocidas en conjunto como Álgebra de
Boole o Álgebra Booleana.
Universidad Simón Bolívar
Departamento de Electrónica y Circuitos
Prof. Juan. Claudio Regidor
Universidad Simón Bolívar
Prof. Juan Claudio Regidor
2
1
Álgebra Booleana
Álgebra de Conmutación
El Álgebra bi-evaluada que define una operación de
“suma” y otra de “producto” es la base de los
circuitos lógicos digitales.
Álgebra definida para un conjunto de dos símbolos
({falso, verdadero}, {F, T}, {0, 1}, ...), con una operación
de “suma” y una operación de “producto”.
En 1939, Claude Shannon aplicó el álgebra
booleana al diseño de circuitos de conmutación.
Reglas de la suma (A+B):
0+0=0
Los símbolos ‘0’ y ‘1’ se usan para representar los dos
valores del álgebra, pero no tienen un significado
numérico. Puede usarse otro par cualquiera, como ‘F’
y ‘T’, o dos valores diferentes de tensión o corriente.
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
0+1=1
1+0=1
1+1=1
1·0=0
1·1=1
Reglas del producto (A·B):
0·0=0
3
Prof. Juan Claudio Regidor
0·1=0
Universidad Simón Bolívar
4
Álgebra de Conmutación
Compuertas Lógicas
La operación de suma booleana se conoce en lógica
como o inclusivo, abreviado o (se acostumbra usar el
equivalente en inglés or). Su símbolo es !.
La implementación electrónica de una función del
álgebra de conmutación es llamada compuerta.
Algunos símbolos circuitales:
La operación de producto booleano se conoce en
lógica como y (se acostumbra usar el equivalente en
inglés and). Su símbolo es ".
Existe también la operación de complemento o
negación (not). Su símbolo es ¬.
Compuerta AND de dos entradas
A
B
Compuerta OR de dos entradas
A
B
Compuerta NOT o inversor
A
A·B
A+B
A'
A · (B’ + C) ! A " (¬ B ! C)
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
5
Compuertas Lógicas
A
B
Compuerta NOR de dos entradas
(or inclusivo negado)
A
B
Compuerta XOR de dos entradas
(or exclusivo)
A
B
Es una representación de una función lógica que
enumera el valor de la función para cada una de las
combinaciones de valores de sus operandos.
(A·B)'
(A+B)'
A!B
x
y x·y
x
y x+y
x
y (x · y)’
x
y x!y
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
1
0
1
1
0
1
1
1
0
0
1
0
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
0
1
1
0
and
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
6
Tabla de verdad
Algunos símbolos circuitales (cont.):
Compuerta NAND de dos entradas
(and negado)
Universidad Simón Bolívar
Prof. Juan Claudio Regidor
7
Prof. Juan Claudio Regidor
or inclusivo
and negado
Universidad Simón Bolívar
or exclusivo
8
Conjuntos
Conjuntos
La teoría de conjuntos es un ejemplo de álgebra
booleana, si se hacen las identificaciones:
La operación A · (B + C) puede representarse con un
diagrama de Venn:
B
0: conjunto vacío, !
A
1: conjunto universal, U
Suma: unión de conjuntos, #
A$(B#C)
C
Producto: intersección de conjuntos, $
(B + C) es la unión de los conjuntos B y C, en amarillo
Complemento con respecto al conjunto universal U
La intersección de B # C con A se ve en anaranjado.
Universidad Simón Bolívar
Prof. Juan Claudio Regidor
9
Postulados del Álgebra de
Conmutación
"
"
"
"
x = 1 si x ! 0
x = 0 ! x’ = 1" "
"
"
"
x = 1 ! x’ = 0
"
"
"
"
1+1=1
4. 1 . 1 = 1" "
"
"
"
"
0+0=0
5. 0 . 1 = 1 · 0 = 0" "
"
"
1+0=0+1=1
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
10
Al igual que en el álgebra tradicional, se establece por
convención una precedencia de operadores: el
producto se realiza antes que la suma; el complemento tiene la mayor precedencia. Se puede alterar el
orden de las operaciones por medio de paréntesis.
2. Complemento
3. 0 . 0 = 0" "
Universidad Simón Bolívar
Precedencia de Operadores
1. Existencia de sólo dos valores
x = 0 si x ! 1" "
Prof. Juan Claudio Regidor
Ejemplos:
x · y + x · z = (x · y) + (x · z)
u · (v + t) ! u · v + t
x‘ · u · v‘ · (y + z’) = (x’) · u · (v‘) · (y + (z’))
11
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
12
Principio de Dualidad
Teoremas
Toda identidad booleana se mantiene si se hacen
simultáneamente los intercambios
0 ! 1
Ejemplos: x + 0 = x
1. Elemento identidad
"
+ ! ·
! !
! !
!
!
Universidad Simón Bolívar
Teoremas
13
"
"
"
"
x·x=x
x$x = x
Prof. Juan Claudio Regidor
"
x·1=x
"
"
"
x·0=0
x$! = !
Universidad Simón Bolívar
14
(iii)
"
"
"
"
"
"
x · x’ = 0
"
0 + 0’ = 0 + 1 = 1" "
"
0 · 0’ = 0 . 1 = 0
"
1 + 1’ = 1 + 0 = 1" "
"
1 · 1’ = 1 . 0 = 0
" U"
(1’)’ = (0)’ = 1
Universidad Simón Bolívar
x + x’ = 1""
Por inducción perfecta:
Por inducción perfecta: (0’)’ = (1)’ = 0
"
"
Prof. Juan Claudio Regidor
"
(x’)’ = x
"
"
Teoremas
4. Involución o doble complemento
"
"
5. Complementos
En conjuntos: x#x = x;
"
x + 1 = 1" "
(ii)
3. Idempotencia
"
"
En conjuntos: x#U = U;
x + ( y ! z) = ( x + y) ! ( x + z)
x + x = x""
"
2. Elemento nulo
x ! ( y + z) = x ! y + x ! z
"
x + 0 = x""
Se puede demostrar por inducción perfecta o por
conjuntos: x#! = x; x$U = x
!!
x ! 1= x
Prof. Juan Claudio Regidor
(i)
15
"
Prof. Juan Claudio Regidor
"
x
"
"
x’
"
x#x’ = U;
Universidad Simón Bolívar
x$x’ = !
16
Teoremas
Teoremas
(iv)
(v)
8. Distributividad
x · (y + z) = x · y + x · z"
6. Conmutatividad
"
x + y = y + x"
"
"
"
"
Prof. Juan Claudio Regidor
x · (y · z) = (x · y) · z
Universidad Simón Bolívar
y
17
Teoremas
(x # y) $ (x # z)
x
y$z
x
x + (y + z) = (x + y) + z" "
x + (y · z) = (x + y) · (x + z)
x # (y $ z)
x·y=y.x
7. Asociatividad
!
"
x
y
z
Universidad Simón Bolívar
Prof. Juan Claudio Regidor
Teoremas
(vi)
8. Distributividad (cont.)
z
18
(vii)
9. Absorción
x + (y · z) = (x + y) · (x + z)
x + x · y = x"
"
"
x · (x + y) = x
(x + y) · (x + z) = x · x + x · z + x · y + y · z
Demostración:
"
= x + x · z + x · y + y · z (idempotencia)
x + x · y = x · 1 + x · y" "
"
x · (x + y) = (x + 0) · (x + y)
"
=x·1+x·z+x·y+y·z
"
= x · (1 + y)"
= x + (0 · y)
"
= x · (1 + z + y) + y · z##(distributividad)
"
= x · 1 = x"
=x+0=x
"
= x + y · z""
Prof. Juan Claudio Regidor
"
Universidad Simón Bolívar
"
"
(identidad)
" "
"
(elemento nulo)
19
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
20
Teoremas
Teoremas
(viii)
10. Combinación
x · y + x · y’ = x" "
11. Consenso
"
"
"
x · y + x’ · z + y · z = x · y + x’ · z
(x + y) · (x + y’) = x
(x + y) · (x’ + z) · (y + z) = (x + y) · (x’ + z)
Demostración:
x · y + x · y’ = x · (y + y’)" "
"
(ix)
= x · (1) = x"
= x+(0) = x
Universidad Simón Bolívar
Prof. Juan Claudio Regidor
Demostración:
x · y + x’ · z + y · z = x · y + x’ · z + y · z · (x + x’)
(x + y)·(x + y’) = x+(y · y’)
Teoremas
21
"
= x · y + x’ · z + x · y · z + x’ · y · z
"
= x · y + x’ · z
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
22
Leyes de De Morgan
(x)
12.
x + x’ · y = x + y""
"
"
"
x · (x’ + y) = x · y
Augustus de Morgan, matemático inglés (1806-71).
Demostración:
Encontró la expresión matemática para las leyes que
llevan su nombre, aunque eran conocidas desde la
Edad Media.
x + x’ · y = (x + x’) · (x + y)" x · (x’ + y) = x · x’ + x · y
"
= (1) · (x + y)"
=0+x·y
"
= x + y"
=x·y
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
23
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
24
Leyes de De Morgan
(x · y)’ = x’ + y‘" "
"
"
"
Leyes de De Morgan
(x + y)’ = x’ · y’
Las leyes de De Morgan pueden extenderse a n
variables:
Demostración: Si (x · y) es el complemento de (x’ + y‘)
entonces debe cumplirse:
(x · y) · (x’ + y‘) = 0
y
(x1 · x2 · … · xn)’ = x’1 + x’2 + … + x’n
(x · y) + (x’ + y‘) = 1
(x1 + x2 + … + xn)’ = x’1 · x’2 · … · x’n
Ejemplo:
(x · y) · (x’ + y‘) = x’ · x · y + x · y · y’ = 0 · y + x · 0 = 0
[A’ + B + (C · D’ · E)]’ = A · B’ · (C · D’ · E)‘
"
= A · B’ · (C’ + D + E’)
(x · y) + (x’ + y‘) = x’ + x · y + y‘ = x’ + y + y’ = 1
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
25
Universidad Simón Bolívar
Prof. Juan Claudio Regidor
Teorema de De Morgan
generalizado
26
Leyes de De Morgan
[F(x1, x2, …, xn , +, ·)]’ = F(x’1, x’2, …, x’n , ·, +)
(A · B)’ = A’ + B‘
Ejemplo:
A
B
(A·B)'
=
A
B
(A·B)'
=
A
B
(A+B)'
F(x, y, z) = x · y + z · (x’ + y)
! [F(x, y, z)]’ = (x’ + y’) · (z’ + x · y’)
(A + B)’ = A’ · B’
Hallar el complemento de A’·B + A·D’·(B + C + E’)
A
B
{(A’·B) + [A·D’·(B + C + E’)]}’ =
" " " (A + B’) · (A’ + D + B’·C’·E)
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
27
Prof. Juan Claudio Regidor
(A+B)'
Universidad Simón Bolívar
28
Teoremas de Expansión de
Shannon
Análisis de circuitos
combinatorios
F ( x1 , x2 , x3 , ..., xn ) = x1 ' · F ( 0, x2 , x3 , ..., xn )
Podemos hallar el valor de la salida para cada una de
las combinaciones de variables de entrada:
+ x1 · F (1, x2 , x3 , ..., xn )
x y z
1 1 1
F ( x1 , x2 , x3 , ..., xn ) = !" x1 + F ( 0, x2 , x3 , ..., xn ) #$
x y z x·y x’·z F
1
· !" x1 ' + F (1, x2 , x3 , ..., xn ) #$
1
Ejemplo:
1
1
[(A + B + C+ D)·(A·B’·C)’·(B + C’ + D)]’ =
"
A’ · [(B + C+ D)·(B + C’ + D)]’ +
"
A · [(B’·C)’·(B + C’ + D)]’
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
1
29
Minimización de funciones
0
0
0
0
1
1
0 1 0
0
0
0
0 1 1
0
1
1
1 0 0
0
0
0
1 0 1
0
0
0
1 1 0
1
0
1
1 1 1
1
0
1
Universidad Simón Bolívar
37
Una función lógica, en general, no tiene una
expresión algebraica única. Varias expresiones (o
circuitos) pueden producir la misma tabla de verdad
y son equivalentes.
Literal: una variable o su complemento. Ej.: y, x’, rs
Término de producto: un literal simple o el
producto de varios literales. Ej.: y’, A·B, w’·x’·z
Término de suma: un literal simple o la suma de
varios literales. Ej.: y’, A + B, w’ + x’ + z
x · y + z · (x’ + y) = x’ · z + x · y = (x + z) · (x’ + y)
Nuestro objetivo es lograr una expresión con el
menor número posible de literales y términos, a fin
de reducir el costo del circuito necesario. Para ello
podemos usar los teoremas conocidos.
Expresión de suma de productos: es la suma de
varios términos de producto. Ej.: b + a’·c + b·c’·d
Expresión de producto de sumas: es el producto de
varios términos de suma. Ej.: (a + b)·(a’ + c) ·d’
Universidad Simón Bolívar
Prof. Juan Claudio Regidor
0
0
0 0 1
Minimización de funciones
Definiciones:
Prof. Juan Claudio Regidor
1
0 0 0
38
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
39
Minimización de funciones
Minimización de funciones
Simplificar F1(A, B, C) = A + B’·C’ + B’·C
Simplificar F3(x, y) = (x+y)·(x+y’)·(x’+y)·(x’+y’)
A + B’·C’ + B’·C = A + B’·(C’ + C)" (distributividad)
"
= A + B’"
(complementos)
(x+y)·(x+y’)·(x’+y)·(x’+y’)
= (x·x + x·y’+ x·y + y·y’)·(x’· x’+ x’·y’+ x’·y + y·y’)
"
(distributividad)
= (x + x·y’+ x·y + y·y’)·(x’+ x’·y’ + x’·y + y·y’)
"
(idempotencia)
= (x + x·y’+x·y)·(x’ + x’·y’ + x’·y)"
(complemento)
= x · x‘"
(absorción)
= 0"
(complemento)
Simplificar F2(A, B, C) = (A + B’ + C)·(A + B’ + C´)
(A + B’ + C)·(A + B’ + C´) = (A + B’) + C·C’
"
"
(distributividad)
"
= A + B’" (complementos)
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
40
Minimización de funciones
(A+B)·(A+B·C’)+A’·B’+A’·C’+A’·B·C’
= A+A·B·C’+A·B+B·C’+A’·B’+A’·C’+A’·B·C’"(distributividad)
= A+B·C’+A’·B’+A’·C’"
(absorción)
= A + B’ + B·C’ + A’·C’"
(teorema 12)
= A + B’ + C’ + A’·C’"
(teorema 12)
= A + B’ + C’"
(teorema 12)
Universidad Simón Bolívar
Universidad Simón Bolívar
41
Minimización de funciones
Simplificar F4(A, B, C) = (A+B)·(A+B·C’)+A’·B’+A’·C’+A’·B·C’
Prof. Juan Claudio Regidor
Prof. Juan Claudio Regidor
42
Simplificar
F5(A,B,C,D) = [(A+C’+D’)·(A’+C’+D’)·(B’+C+D’)]’
[(A+C’+D’)·(A’+C’+D’)·(B’+C+D’)]’
= (A+C’+D’)’+(A’+C’+D’)’+(B’+C+D’)‘"(de Morgan)
= A’·C·D + A·C·D + B·C’·D"
(de Morgan)
= C·D + B·C’·D"
(combinación)
= D·(C+ B·C’)"
(distributividad)
= D.(C + B)"
(teorema 12)
= B·D + C·D"
(distributividad)
Prof. Juan Claudio Regidor
Universidad Simón Bolívar
43
Suma de Productos
Suma de Productos
Mediante el teorema de De Morgan puede
representarse con un solo tipo de compuertas:
Una suma de productos puede implementarse con
compuertas AND cuyas salidas se unen en una
compuerta OR. Se le llama lógica de dos niveles.
A'
D
OR
ƒ(A,B,C,D) = A'.D + B.C'
A'
D
A'
D
AND
B
C'
A'
D
ƒ
AND
B
C'
44
Producto de Sumas
El producto de sumas puede implementarse con
compuertas OR cuyas salidas se unen en una compuerta AND. Es otra forma de lógica de dos niveles.
ƒ(A,B,C,D) = (A+B) · (C+D’)
A
B
A
B
ƒ
ƒ
C
D'
Prof. Juan Claudio Regidor
OR
B
C'
AND
NOT
A'
D
NAND
ƒ
NOT
C
D'
A'
=
A
Universidad Simón Bolívar
A'
46
Prof. Juan Claudio Regidor
NAND
ƒ
NAND
B
C'
NAND
A
Universidad Simón Bolívar
A
NOT
ƒ
AND
NAND
Prof. Juan Claudio Regidor
NOT
AND
OR
B
C'
AND
A'
=
A
Universidad Simón Bolívar
ƒ
NAND
A'
45