Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Um circuito digital combinatório possui:
- uma ou mais entradas digitais;
- uma ou mais saídas digitais;
- uma especificação funcional que descreve cada saída em função dos valores
das entradas;
- uma especificação temporal que inclui, pelo menos, o tempo máximo que o
circuito vai demorar para produzir valores de saída a partir de um conjunto
arbitrário de valores de entrada (válidos e estáveis) -> tempo de propagação.
x1
x2
x3
x4
x5
(gerar na saída valor ‘1’ se pelo
menos 3 das 5 entradas estarão
a ‘1’; caso contrário gerar ‘0’)
Circuito digital
(saída válida será gerada
passados, no máximo, 2 s após
a recepção de entradas válidas)
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
y1
Álgebra de Boole binária - é um instrumento matemático que permite descrever
relações funcionais entre as entradas e saídas de um circuito digital.
Álgebra de Boole é uma estrutura matemática baseada num conjunto {B,+, },
satisfazendo o seguinte conjunto de postulados:
1.
2.
3.
4.
Fecho (as operações são fechadas em B)
Comutatividade
Elementos neutros
Distributividade mútua
5. Complementação
6. Cardinalidade
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
P1 - fecho: ambas as operações são fechadas em B:
b1  b2  B
b1 , b2  B 
 b1  b2  B
P2 - comutatividade
b1 , b2  B
b1  b2  b2  b1

 b1  b2  b2  b1
P3 – elementos neutros
b0 b  B: b  b0  b
b1 b  B: b  b1  b
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
P4 – distributividade mútua

b1  b2  b3   b1  b2   b1  b3 

b1  b2  b3   b1  b2   b1  b3 
b1 ,b2 ,b3B
b1 ,b2 ,b3B
P5 - complementação
b  Bb  B
b  b  b1

 b  b  b0
P6 – cardinalidade
  b1  b2 #B  2
b1B b2 B
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Se #B = 2, temos álgebra de Boole a dois valores (B={0,1}).
Operadores:
soma lógica
OR
0+0=0
0+1=1
1+0=1
1+1=1
produto
AND
00=0
01=0
10=0
11=1
complementação
NOT
0 = 1
1 = 0
Expressões - conjunto de variáveis e/ou constantes 0 e 1 associadas por
operadores
x yz
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Idempotência bB b  b = b e b + b = b
P3
P5
P4
P5
P3
b  b = b  b + b0 = b  b + b b = b  (b + b) = b  b1 = b
Unicidade do elemento neutro
Sejam b0a e b0b tal que b + b0a = b + b0b = b
b0a + b0b = b0a
P3
b0b + b0a = b0b
P3
b0a + b0b = b0b
P2
=> b0a = b0b
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Unicidade do complemento
Elemento absorvente bB b  b0 = b0
b + b1 = b1
P3
P5
P4
P3
P5
b  b0 = b  b0 + b0 = b  b0 + b b = b  (b0 +b) = b b = b0
Absorção x,yB x + x  y = x
x  (x + y) = x
P3
P4
P3
x + x  y = x  b1 + x  y = x  (b1 + y) = x  b1 = x
Simplificação x,yB x +x  y = x + y
x  (x +y) = x  y
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Adjacência x,yB x  y + x y = x
(x + y)  (x +y) = x
P4
P5
P3
x  y + x y = x  (y +y) = x  b1 = x
Involução xB x = x
indução perfeita:
x
0
1
x
1
0
x
0
1
Consenso x,y,zB x  y +x  z + y  z = x  y +x  z
(x + y)  (x + z)  (y + z) = (x + y)  (x + z)
Associatividade x,y,zB (x  y)  z = x  (y  z)
(x + y) + z = x + (y + z)
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
x,yB x + y =x y
x  y =x +y
e
P5, elemento absorvente,
idempotência
P4
(x + y)  (x y) = x x y +x  y y = b0
Generalização para n variáveis:
n
n
x  x
i 1
i
i
i 1
n
n
x  x
i
i 1
i 1
i
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Todo o teorema ou identidade algébrica dedutível a partir dos postulados da
álgebra de Boole conserva a validade se as operações (+) e (.) e os elementos
neutros forem trocados.
F D ( x1, x2 ,...,xn ,,,0,1)  F ( x1, x2 ,...,xn ,,,1,0)
F ( x1, x2 ,...,xn )  F D ( x1, x2 ,...,xn )
Exemplos:
[ (x +y)  (z + 1) ]D = (x  y) + (z  0)
( x1  x2 )  x3  x1  x2  x3
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
- conjunto de operadores a partir dos quais se pode representar qualquer
função booleana.
{ AND, OR, NOT }
{ AND, NOT }
{ OR, NOT }
{ NAND }
{ NOR }
...
x y
x
0
0
1
1
y
0
1
0
1
x NAND y
1
1
1
0
x y
x
0
0
1
1
y
0
1
0
1
x NOR y
1
0
0
0
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Para escrever uma expressão booleana apenas com operadores NAND devese primeiro colocá-la na forma da soma de produtos e a seguir aplicar o
teorema de involução e as leis de DeMorgan
Para escrever uma expressão booleana apenas com operadores NOR devese primeiro colocá-la na forma do produto de somas e a seguir aplicar o
teorema de involução e as leis de DeMorgan
Exemplos:
x  ( y  z)  x  ( y  z)  x  y  z
x  ( y  z )  ( x  y)  ( x  z )  ( x  y)  ( x  z )  x  y  x  z
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Uma função booleana é uma correspondência que associa um elemento do
conjunto B={0,1} a cada uma das 2n combinações possíveis que as variáveis
podem assumir.
x1
x2
...
xn
y1
y2
...
ym
Sistema digital
n
Existem 2m×2 funções booleanas diferentes que podem ser
implementadas num sistema digital com n entradas e m saídas.
Exemplos:
1
Para n=1, m=1: 21×2 = 4
x
0
1
constante ‘0’
0
0
4
Para n=4, m=3: 23×2 = 248= 281 474 976 710 656
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
x
0
1
x
1
0
constante ‘1’
1
1
Para obter a função dual de f, deve-se aplicar o princípio de dualidade a f.
f D ( x1, x2 ,...,xn ,,,0,1)  f ( x1, x2 ,...,xn ,,,1,0)
Uma função f é auto-dual se f = fD =>
f ( x1, x2 ,...,xn )  f ( x1, x2 ,...,xn )
Exemplo:
f ( x, y, z )  x  y  x  z  y  z
f D ( x, y, z)  ( x  y)  ( x  z )  ( y  z ) 
 (x  y  z)  ( y  z) 
 x  y  x  z  y  z  f ( x, y, z )
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
f(x,y,z)
0
0
1
0
1
0
1
1
- tabular (tabela de verdade)
- algébrica
- esquemática (circuitos lógicos)
f ( x, y, z)  x  y  z  x  y  z 
 x y z  x y z  x y z
Representação tabular é única:
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
f(x,y,z)
0
1
0
0
1
1
1
1
Representação algébrica inclui
frequentemente termos redundantes:
Representação esquemática:
x
y
z
=> necessidade de simplificação
f ( x, y, z )  x  y  z
f(x,y,z)
x
y
z
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
f(x,y,z)
buffer
NOT
AND
NAND
OR
NOR
XOR
XNOR
x y
x
0
0
1
1
y
0
1
0
1
x XOR y
0
1
1
0
x y
x
0
0
1
1
y
0
1
0
1
x XNOR y
1
0
0
1
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova
Exprima a função y na forma mais simples recorrendo a operadores NAND.
y  x1  ( x2  x3  x4 )  x2
y  x1  x2  x1  x3  x4  x2  x2  x1  x3  x4
y  x2  x1  x3  x4  x2  x1  x3  x4
Exprima a função y na forma mais simples recorrendo a operadores NOR.
y  x1  ( x2  x3  x4 )  x2
y  ( x1  x2 )  ( x2  x3  x4  x2 )  ( x1  x2 )  ( x2  x3  x4 )
y  ( x1  x2 )  ( x2  x3 )  ( x2  x4 )
y  ( x1  x2 )  ( x2  x3 )  ( x2  x4 )  ( x1  x2 )  ( x2  x3 )  ( x2  x4 )
Sistemas Digitais (Bolonha), 2007, Iouliia Skliarova