02_Algebra_booleana_portas_logicas

Prévia do material em texto

Álgebra booleana e portas lógicas
Aviso
O conteúdo apresentado nestes slides 
é APENAS um resumo dos tópicos 
discutidos em sala de aula e NÃO deve 
ser utilizado como fonte única de 
consulta. A leitura da bibliografia 
recomendada é essencial.
2
Introdução
† Circuitos eletrônicos
„ Analógicos
† Operam com diversos níveis de tensão (voltagem) 
dentro de um intervalo
† Um sinal analógico pode assumir qualquer valor 
entre o mínimo e o máximo
„ Digitais
† Operam com apenas dois níveis de tensão
(voltagem) dentro de um intervalo
† Um sinal digital pode assumir apenas o valor 
mínimo ou o valor máximo
3
Introdução
† Circuitos eletrônicos
„ Sinal analógico x sinal digital
4
Uma lâmpada controlada por 
este sinal, pode assumir 
diversos níveis de luminosidade 
entre apagada e o brilho 
máximo
Uma lâmpada controlada por 
este sinal, pode assumir 
apenas dois níveis de 
luminosidade: apagada ou 
brilho máximo
Analógico Digital
Intervalo
Introdução
† Os dois níveis de tensão utilizados pelos circuitos eletrônicos 
digitais são chamados de baixo (low) e alto (high)
„ O nível baixo corresponde a 0 Volt
„ O nível alto corresponde tipicamente a: 
† 1,5 Volts ou
† 3,3 Volts ou
† 5 Volts
† Dependendo da tensão de alimentação exigida pelo circuito
5
0V
1,5V; 3,3V; 5V
Álgebra booleana
† Proposta pelo matemático inglês George Boole, em 1854
† Usada para projetar e analisar circuitos digitais
† Diferente da álgebra convencional, onde as variáveis podem 
assumir valores no intervalo (-∞, +∞ ), as variáveis boolenas 
podem assumir apenas dois valores: 0 e 1 (níveis lógicos)
† Considerando um circuito digital
„ 0 correspode ao nível baixo (0V)
„ 1 corresponde ao nível alto (5V; 3,3V ou 1,5V)
† Na álgebra booleana, os valores 0 e 1 também são 
conhecidos como verdadeiro (true) e falso (false)
6
Álgebra booleana
† Veremos os inicialmente os circuitos lógicos mais 
elementares: portas lógicas
† A partir da interconexão entre portas lógicas, sistemas 
digitais complexos são criados (e.g. processador)
† As portas lógicas implementam fisicamante as operações 
básicas da álgebra boolena (operações lógicas)
„ AND (e lógico)
„ OR (ou lógico)
„ NOT (complemento ou negação)
† Tabelas verdade
„ Apresentam o funcionamento do circuito lógico em forma de tabela
7
Álgebra booleana
† Operações básicas
„ OR (ou lógico)
† Também denominada adição lógica
† Símbolos: + , ν
„ A + B, A v B v C
„ Linguagens de programação (e.g. C, Java): |, || 
† Definição
„ A operação OR resulta 1 se ao menos uma das variáveis 
de entrada vale 1. Resulta 0 se todas variáveis de entrada 
valem 0.
8
A B S
0 0 0
0 1 1
1 0 1
1 1 1
Tabela verdadePorta lógica
S = A + B
2n linhas
n = número de 
variáveis de 
entrada
Álgebra booleana
† Operações básicas
„ OR (ou lógico)
† Forma de onda (wave form)
„ Descreve o comportamento dinâmico do circuito
Se alguma das entradas é 
igual a 1, a saída é 1
9
Álgebra booleana
† Operações básicas
„ OR (ou lógico)
† Porta lógica pode ter várias entradas
† Definição
„ A operação OR resulta 1 se ao menos uma das variáveis 
de entrada vale 1. Resulta 0 se todas variáveis de entrada 
valem 0.
10
A B C S
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
Tabela verdade
Porta lógica
S = A + B + C
A
B
C
S Se alguma das 
entradas é igual 
a 1, a saída é 1
SA
B
C
S = (A + B) + C
S
Álgebra booleana
† Operações básicas
„ OR (ou lógico)
† Forma de onda (wave form)
„ Descreve o comportamento dinâmico do circuito
A
B
C
S
Glitch/spike devido à 
mudança simultânea 
das entradas
Se alguma das 
entradas é igual 
a 1, a saída é 1
11
Álgebra booleana
† Operações básicas
„ AND (e lógico)
† Também denominada multiplicação lógica
† Símbolos: . , ^
„ A . B, A ^ B ^ C
„ Linguagens de programação (e.g. C, Java): &, && 
† Definição
„ A operação AND resulta 1 se todas variáveis de entrada 
valem 1. Resulta 0 se ao menos uma das variáveis de 
entrada vale 0.
A B S
0 0 0
0 1 0
1 0 0
1 1 1
Tabela verdadePorta lógica
S = A . B
12
Álgebra booleana
† Operações básicas
„ AND (e lógico)
† Forma de onda (wave form)
„ Descreve o comportamento dinâmico do circuito
SSe alguma das entradas é 
igual a 0, a saída é 0
13
Álgebra booleana
† Operações básicas
„ AND (e lógico)
† Porta lógica pode ter várias entradas
† Definição
„ A operação AND resulta 1 se todas variáveis de entrada 
valem 1. Resulta 0 se ao menos uma das variáveis de 
entrada vale 0.
14
A B C S
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
Tabela verdade
Porta lógica
S = A . B . C
A
B
C
S Se alguma 
entrada é igual 
a 0, a saída é 0
SA
B
C
S = (A . B) . C
Álgebra booleana
† Operações básicas
„ NOT (complemento ou negação)
† Inverte o valor lógico da variável de entrada
† Símbolos: ¯, ¬, ‘, ~, ! 
„ Ā, ¬A, A’, ~A, !A (operação unária)
„ Linguagens de programação (e.g. C, Java): ~, !
† Definição
„ A operação NOT resulta 1 se a variável de entrada vale 0. 
Resulta 0 se a variável de entrada vale 1.
15
A Ā
0 1
1 0
Tabela verdadePorta lógica (inversor)
S = Ā
Álgebra booleana
† Operações básicas
„ NOT (complemento ou negação)
† Forma de onda (wave form)
„ Descreve o comportamento dinâmico do circuito
S
16
Álgebra booleana
† Resumo das operações básicas
„ OR
† 0 + 0 = 0
† 0 + 1 = 1
† 1 + 0 = 1
† 1 + 1 = 1
† 0 + 0 + 0 + 0 + 1 + 0 = 1 (Se alguma entrada é 1, a saída é 1)
„ AND
† 0 . 0 = 0
† 0 . 1 = 0
† 1 . 0 = 0
† 1 . 1 = 1
† 1 . 1 . 1 . 0 . 1 . 1 . 1 = 0 (Se alguma entrada é 0, a saída é 0)
„ NOT
† !0 = 1
† !1 = 0
17
Álgebra booleana
† Circuitos lógicos
„ Representação gráfica de equações booleanas utilizando 
portas lógicas
„ Os circuitos são criados a partir da interconexão das 
portas lógicas
„ Qualquer circuito lógico pode ser implementado 
utilizando as portas lógicas OR, AND e NOT, e descrito a 
partir de equações booleanas
18
Álgebra booleana
† Exemplos
19
Álgebra booleana
† Exemplos Conexão
Não há conexão
Símbolo da 
operação AND 
(.) suprimido
20
Álgebra booleana
† Circuito integrado (CI)
„ Conjunto de portas lógicas fabricadas em um chip
„ A partir do circuito lógico pode-se implementar fisicamente equações 
booleanas usando C.Is (circuito digital)
21
Álgebra booleana
† Circuito integrado (CI)
„ Placa do Apple I (Leiloada por US$ 374.500)
22
Álgebra booleana
† Avaliação de equações booleanas
„ Dada a equação que descreve uma função Booleana F, 
deseja-se saber qual o comportamento de F
„ Podemos montar a tabela-verdade para F
† Identificar as variáveis de entrada
† Para cada variável de entrada, destinar uma coluna
† Criar colunas à direita, conforme a ordem de precedência 
das operações contidas na equação
„ Parênteses (do mais interno para o mais externo) ou NOT de 
variável (e.g. !B)
„ AND (e.g. A + B . C)
„ OR
23
Álgebra booleana
† Avaliação de equações booleanas
„ F = X . (Y + !Z)
† Variáveis de entrada: X, Y e Z
† A tabela-verdade para uma equação com n variáveis de entrada 
contém 2n linhas. 8 linhas nesse caso (23).
X Y Z
0 0 0 0
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1
Nestas linhas deve-se enumerar todas as
combinações das variáveis de entrada
(tipicamente, em ordem crescente usando 
representação binária)
8 linhas (23)
24
Álgebra booleana
† Avaliação de equações booleanas
„ F = X . (Y + !Z)
† Avaliação de !Z
X Y Z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
25
Álgebra booleana
† Avaliação de equações booleanas
„ F = X . (Y + !Z)
† Avaliação de !Z
X Y Z !Z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
26
Álgebra booleana
† Avaliação de equações booleanas
„ F = X . (Y + !Z)
† Avaliação de !Z
X Y Z !Z
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
27
Álgebra booleana
† Avaliação de equações booleanas
„ F = X . (Y + !Z)
† Avaliação de (Y + !Z)
X Y Z !Z Y + !Z
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 028
Álgebra booleana
† Avaliação de equações booleanas
„ F = X . (Y + !Z)
† Avaliação de (Y + !Z)
X Y Z !Z Y + !Z
0 0 0 1 1
0 0 1 0 0
0 1 0 1 1
0 1 1 0 1
1 0 0 1 1
1 0 1 0 0
1 1 0 1 1
1 1 1 0 1
29
Álgebra booleana
† Avaliação de equações booleanas
„ F = X . (Y + !Z)
† Avaliação de X . (Y + !Z)
X Y Z !Z Y + !Z
0 0 0 1 1
0 0 1 0 0
0 1 0 1 1
0 1 1 0 1
1 0 0 1 1
1 0 1 0 0
1 1 0 1 1
1 1 1 0 1
30
Álgebra booleana
† Avaliação de equações booleanas
„ F = X . (Y + !Z)
† Avaliação de X . (Y + !Z)
X Y Z !Z Y + !Z F
0 0 0 1 1
0 0 1 0 0
0 1 0 1 1
0 1 1 0 1
1 0 0 1 1
1 0 1 0 0
1 1 0 1 1
1 1 1 0 1
31
Álgebra booleana
† Avaliação de equações booleanas
„ F = X . (Y + !Z)
† Avaliação de X . (Y + !Z)
X Y Z !Z Y + !Z F
0 0 0 1 1 0
0 0 1 0 0 0
0 1 0 1 1 0
0 1 1 0 1 0
1 0 0 1 1 1
1 0 1 0 0 0
1 1 0 1 1 1
1 1 1 0 1 1
32
Álgebra booleana
† Avaliação de equações booleanas
„ Pode-se determinar algebricamente o valor da função 
para uma determinada entrada
„ Exemplo: X=1, Y=0, Z=0
† F = X . (Y + !Z)
† F = 1 . (0 + !0) → substitui variáveis de entrada pelos valores lógicos
† F = 1 . (0 + 1)
† F = 1 . (1)
† F = 1
33
Álgebra booleana
† Avaliação de equações booleanas
„ X = !A + B
† Variáveis de entrada: A e B
† Tabela verdade com 4 linhas (22)
A B
0 0
0 1
1 0
1 1
34
Álgebra booleana
† Avaliação de equações booleanas
„ X = !A + B
† Variáveis de entrada: A e B
† Tabela verdade com 4 linhas (22)
† Avaliação de !A
A B !A
0 0
0 1
1 0
1 1
35
Álgebra booleana
† Avaliação de equações booleanas
„ X = !A + B
† Variáveis de entrada: A e B
† Tabela verdade com 4 linhas (22)
† Avaliação de !A
A B !A
0 0 1
0 1 1
1 0 0
1 1 0
36
Álgebra booleana
† Avaliação de equações booleanas
„ X = !A + B
† Variáveis de entrada: A e B
† Tabela verdade com 4 linhas (22)
† Avaliação de !A + B
A B !A X
0 0 1
0 1 1
1 0 0
1 1 0
37
Álgebra booleana
† Avaliação de equações booleanas
„ X = !A + B
† Variáveis de entrada: A e B
† Tabela verdade com 4 linhas (22)
† Avaliação de !A + B
A B !A X
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1
38
Álgebra booleana
† Avaliação de equações booleanas
„ X = !(A + B)
† Variáveis de entrada: A e B
† Tabela verdade com 4 linhas (22)
A B
0 0
0 1
1 0
1 1
39
Álgebra booleana
† Avaliação de equações booleanas
„ X = !(A + B)
† Variáveis de entrada: A e B
† Tabela verdade com 4 linhas (22)
† Avaliação de (A + B)
A B A + B
0 0
0 1
1 0
1 1
40
Álgebra booleana
† Avaliação de equações booleanas
„ X = !(A + B)
† Variáveis de entrada: A e B
† Tabela verdade com 4 linhas (22)
† Avaliação de (A + B)
A B A + B
0 0 0
0 1 1
1 0 1
1 1 1
41
Álgebra booleana
† Avaliação de equações booleanas
„ X = !(A + B)
† Variáveis de entrada: A e B
† Tabela verdade com 4 linhas (22)
† Avaliação de !(A + B)
A B A + B X
0 0 0
0 1 1
1 0 1
1 1 1
42
Álgebra booleana
† Avaliação de equações booleanas
„ X = !(A + B)
† Variáveis de entrada: A e B
† Tabela verdade com 4 linhas (22)
† Avaliação de !(A + B)
A B A + B X
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
43
Álgebra booleana
† Avaliação de equações booleanas
„ X = (!A.B.C) . !(A + D)
† Variáveis de entrada: A, B, C e D
† Tabela verdade com 16 linhas (24)
A B C D
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
44
Álgebra booleana
† Avaliação de equações booleanas
„ X = (!A.B.C) . !(A + D)
A B C D !A
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 1
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0
Avaliação de !A
45
Álgebra booleana
† Avaliação de equações booleanas
„ X = (!A.B.C) . !(A + D)
A B C D !A A + D
0 0 0 0 1 0
0 0 0 1 1 1
0 0 1 0 1 0
0 0 1 1 1 1
0 1 0 0 1 0
0 1 0 1 1 1
0 1 1 0 1 0
0 1 1 1 1 1
1 0 0 0 0 1
1 0 0 1 0 1
1 0 1 0 0 1
1 0 1 1 0 1
1 1 0 0 0 1
1 1 0 1 0 1
1 1 1 0 0 1
1 1 1 1 0 1
Avaliação de (A + D)
46
Álgebra booleana
† Avaliação de equações booleanas
„ X = (!A.B.C) . !(A + D)
A B C D !A A + D !(A + D)
0 0 0 0 1 0 1
0 0 0 1 1 1 0
0 0 1 0 1 0 1
0 0 1 1 1 1 0
0 1 0 0 1 0 1
0 1 0 1 1 1 0
0 1 1 0 1 0 1
0 1 1 1 1 1 0
1 0 0 0 0 1 0
1 0 0 1 0 1 0
1 0 1 0 0 1 0
1 0 1 1 0 1 0
1 1 0 0 0 1 0
1 1 0 1 0 1 0
1 1 1 0 0 1 0
1 1 1 1 0 1 0
Avaliação de !(A + D)
47
Álgebra booleana
† Avaliação de equações booleanas
„ X = (!A.B.C) . !(A + D)
A B C D !A A + D !(A + D) !A.B.C
0 0 0 0 1 0 1 0
0 0 0 1 1 1 0 0
0 0 1 0 1 0 1 0
0 0 1 1 1 1 0 0
0 1 0 0 1 0 1 0
0 1 0 1 1 1 0 0
0 1 1 0 1 0 1 1
0 1 1 1 1 1 0 1
1 0 0 0 0 1 0 0
1 0 0 1 0 1 0 0
1 0 1 0 0 1 0 0
1 0 1 1 0 1 0 0
1 1 0 0 0 1 0 0
1 1 0 1 0 1 0 0
1 1 1 0 0 1 0 0
1 1 1 1 0 1 0 0
Avaliação de (!A.B.C)
48
Álgebra booleana
† Avaliação de equações booleanas
„ X = (!A.B.C) . !(A + D)
A B C D !A A + D !(A + D) !A.B.C X
0 0 0 0 1 0 1 0 0
0 0 0 1 1 1 0 0 0
0 0 1 0 1 0 1 0 0
0 0 1 1 1 1 0 0 0
0 1 0 0 1 0 1 0 0
0 1 0 1 1 1 0 0 0
0 1 1 0 1 0 1 1 1
0 1 1 1 1 1 0 1 0
1 0 0 0 0 1 0 0 0
1 0 0 1 0 1 0 0 0
1 0 1 0 0 1 0 0 0
1 0 1 1 0 1 0 0 0
1 1 0 0 0 1 0 0 0
1 1 0 1 0 1 0 0 0
1 1 1 0 0 1 0 0 0
1 1 1 1 0 1 0 0 0
Avaliação de X
49
Álgebra booleana
† Circuitos lógicos
„ O desenho de um circuito lógico (esquemático) deve 
obedecer à ordem de precedência das operações 
mostradas na equação que se deseja implementar
„ Exemplo: F = X . (Y + !Z)
!Z
Y + !Z
X . (Y + !Z)
50
Álgebra booleana
† Circuitos lógicos
„ F = A.C + B.!C + !A.B.C
51
Álgebra booleana
† Circuitos lógicos
„ F = A.C + B.!C + !A.B.C
52
Álgebra booleana
† Circuitos lógicos
„ F = A.C + B.!C + !A.B.C
A.C
B.!C
!A.B.C
53
Álgebra booleana
† Circuitos lógicos
„ F = A.C + B.!C + !A.B.C
A.C
B.!C
!A.B.C
A.C + B.!C + !A.B.C
54
Álgebra booleana
† Circuitos lógicos
„ S = !A.C + (B.C + A.!B)
55
Álgebra booleana
† Circuitos lógicos
„ S = !A.C + (B.C + A.!B)
!A.C
B.C
A.!B
56
Álgebra booleana
† Circuitos lógicos
„ S = !A.C + (B.C + A.!B)
!A.C
B.C
A.!B
B.C + A.!B
57
Álgebra booleana
† Circuitos lógicos
„ S = !A.C + (B.C + A.!B)
!A.C
B.C
A.!B
B.C + A.!B
!A.C + (B.C + A.!B)
58
Álgebra booleana
† Circuitos lógicos
„ S = !(C.!B).(A.B + !C + A)
C.!B !(C.!B)
A.B
!C + A A.B + !C + A
!(C.!B).(A.B + !C + A)
Versão 1 (or de 
2 entradas)
59
Álgebra booleana
† Circuitos lógicos
„ S = !(C.!B).(A.B + !C + A)
C.!B !(C.!B)
A.B
A.B + !C + A
!(C.!B).(A.B + !C + A)
Versão 2 (or de 
3 entradas)
60
Álgebra booleana
† Circuitos lógicos
„ O valor da função para um dado conjunto de valores 
das variáveis de entrada pode ser determinado através 
do circuito lógico, sem usar a equação booleana
= 1 = 0 = 1
0
1
0
1
1
0
0
0
0
0
0
61
Álgebra booleana
† Circuitos lógicos
„ O valor da função para um dado conjunto de valores 
das variáveis de entrada pode ser determinado através 
do circuito lógico, sem usar a equação booleana
1 = = 1 = 0
0
0
1
1
1
1
1
1
1
0
1
62
Álgebra booleana
† Circuitos lógicos
„ A equação booleana pode ser obtida diretamente a 
partir do circuito lógico
63
Álgebra booleana
† Circuitos lógicos
„ A equação booleana pode ser obtida diretamente a 
partir do circuito lógico
64
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = !(!A + !B).B.C
† Variáveis de entrada: A, B e C
† Tabela verdade com 8 linhas (23)
A B C
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
65
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = !(!A + !B).B.C
† Variáveis de entrada: A, B e C
† Tabela verdade com 8 linhas (23)
A B C !A !B
0 0 0 1 1
0 0 1 1 1
0 1 0 1 0
0 1 1 1 0
1 0 0 0 1
1 0 1 0 1
1 1 0 0 0
1 1 1 0 0
Avaliação de !A e de !B
66
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = !(!A + !B).B.C
† Variáveis de entrada: A, B e C
† Tabela verdade com 8 linhas (23)
A B C !A !B !A + !B
0 0 0 1 1 1
0 0 1 1 1 1
0 1 0 1 01
0 1 1 1 0 1
1 0 0 0 1 1
1 0 1 0 1 1
1 1 0 0 0 0
1 1 1 0 0 0
Avaliação de (!A + !B)
67
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = !(!A + !B).B.C
† Variáveis de entrada: A, B e C
† Tabela verdade com 8 linhas (23)
A B C !A !B !A + !B !(!A + !B)
0 0 0 1 1 1 0
0 0 1 1 1 1 0
0 1 0 1 0 1 0
0 1 1 1 0 1 0
1 0 0 0 1 1 0
1 0 1 0 1 1 0
1 1 0 0 0 0 1
1 1 1 0 0 0 1
Avaliação de !(!A + !B)
68
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = !(!A + !B).B.C
† Variáveis de entrada: A, B e C
† Tabela verdade com 8 linhas (23)
A B C !A !B !A + !B !(!A + !B) X
0 0 0 1 1 1 0 0
0 0 1 1 1 1 0 0
0 1 0 1 0 1 0 0
0 1 1 1 0 1 0 0
1 0 0 0 1 1 0 0
1 0 1 0 1 1 0 0
1 1 0 0 0 0 1 0
1 1 1 0 0 0 1 1
Avaliação de X
69
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = !(!A + !B).B.C
† Variáveis de entrada: A, B e C
† Tabela verdade com 8 linhas (23)
!B
!A !A + !B !(!A + !B)
B
C
!(!A + !B).B.C
70
Álgebra booleana
† Logisim
71
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = (!A.!B.!C) + (A.!B.!C) + (!A.!B.D)
† Variáveis de entrada: A, B, C e D
† Tabela verdade com 16 linhas (24)
A B C D
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
72
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = (!A.!B.!C) + (A.!B.!C) + (!A.!B.D)
A B C D !A !B !C
0 0 0 0 1 1 1
0 0 0 1 1 1 1
0 0 1 0 1 1 0
0 0 1 1 1 1 0
0 1 0 0 1 0 1
0 1 0 1 1 0 1
0 1 1 0 1 0 0
0 1 1 1 1 0 0
1 0 0 0 0 1 1
1 0 0 1 0 1 1
1 0 1 0 0 1 0
1 0 1 1 0 1 0
1 1 0 0 0 0 1
1 1 0 1 0 0 1
1 1 1 0 0 0 0
1 1 1 1 0 0 0
Avaliação de !A, !B e !C
73
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = (!A.!B.!C) + (A.!B.!C) + (!A.!B.D)
A B C D !A !B !C !A.!B.!C
0 0 0 0 1 1 1 1
0 0 0 1 1 1 1 1
0 0 1 0 1 1 0 0
0 0 1 1 1 1 0 0
0 1 0 0 1 0 1 0
0 1 0 1 1 0 1 0
0 1 1 0 1 0 0 0
0 1 1 1 1 0 0 0
1 0 0 0 0 1 1 0
1 0 0 1 0 1 1 0
1 0 1 0 0 1 0 0
1 0 1 1 0 1 0 0
1 1 0 0 0 0 1 0
1 1 0 1 0 0 1 0
1 1 1 0 0 0 0 0
1 1 1 1 0 0 0 0
Avaliação de !A.!B.!C
74
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = (!A.!B.!C) + (A.!B.!C) + (!A.!B.D)
A B C D !A !B !C !A.!B.!C A.!B.!C
0 0 0 0 1 1 1 1 0
0 0 0 1 1 1 1 1 0
0 0 1 0 1 1 0 0 0
0 0 1 1 1 1 0 0 0
0 1 0 0 1 0 1 0 0
0 1 0 1 1 0 1 0 0
0 1 1 0 1 0 0 0 0
0 1 1 1 1 0 0 0 0
1 0 0 0 0 1 1 0 1
1 0 0 1 0 1 1 0 1
1 0 1 0 0 1 0 0 0
1 0 1 1 0 1 0 0 0
1 1 0 0 0 0 1 0 0
1 1 0 1 0 0 1 0 0
1 1 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0
Avaliação de A.!B.!C
75
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = (!A.!B.!C) + (A.!B.!C) + (!A.!B.D)
A B C D !A !B !C !A.!B.!C A.!B.!C !A.!B.D
0 0 0 0 1 1 1 1 0 0
0 0 0 1 1 1 1 1 0 1
0 0 1 0 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 1
0 1 0 0 1 0 1 0 0 0
0 1 0 1 1 0 1 0 0 0
0 1 1 0 1 0 0 0 0 0
0 1 1 1 1 0 0 0 0 0
1 0 0 0 0 1 1 0 1 0
1 0 0 1 0 1 1 0 1 0
1 0 1 0 0 1 0 0 0 0
1 0 1 1 0 1 0 0 0 0
1 1 0 0 0 0 1 0 0 0
1 1 0 1 0 0 1 0 0 0
1 1 1 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0
Avaliação de 
!A.!B.D
76
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = (!A.!B.!C) + (A.!B.!C) + (!A.!B.D)
A B C D !A !B !C !A.!B.!C A.!B.!C !A.!B.D X
0 0 0 0 1 1 1 1 0 0 1
0 0 0 1 1 1 1 1 0 1 1
0 0 1 0 1 1 0 0 0 0 0
0 0 1 1 1 1 0 0 0 1 1
0 1 0 0 1 0 1 0 0 0 0
0 1 0 1 1 0 1 0 0 0 0
0 1 1 0 1 0 0 0 0 0 0
0 1 1 1 1 0 0 0 0 0 0
1 0 0 0 0 1 1 0 1 0 1
1 0 0 1 0 1 1 0 1 0 1
1 0 1 0 0 1 0 0 0 0 0
1 0 1 1 0 1 0 0 0 0 0
1 1 0 0 0 0 1 0 0 0 0
1 1 0 1 0 0 1 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0
Avaliação de X
77
Álgebra booleana
† Construir a tabela verdade e desenhar o circuito
„ X = (!A.!B.!C) + (A.!B.!C) + (!A.!B.D)
!A
!B
!C
!A.!B.!C
A.!B.!C
!A
!B
!A.!B.D
A
(!A.!B.!C) + (A.!B.!C) + (!A.!B.D)
78
Álgebra booleana
† Logisim
79
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
80
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
!A
!B
!A + !B
!(!A + !B)
X
Saída e sinais 
intermediários avaliados a 
cada transição das entradas
81
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
!A
!B
!A + !B
!(!A + !B)
X
82
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
!A
!B
!A + !B
!(!A + !B)
X
83
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
!A
!B
!A + !B
!(!A + !B)
X
84
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
!A
!B
!A + !B
!(!A + !B)
X
85
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
!A
!B
!A + !B
!(!A + !B)
X
86
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
!A
!B
!A + !B
!(!A + !B)
X
87
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
!A
!B
!A + !B
!(!A + !B)
X
88
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
!A
!B
!A + !B
!(!A + !B)
X
89
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
!A
!B
!A + !B
!(!A + !B)
X
90
Álgebra booleana
† Forma de onda: X = !(!A + !B).B.C
A
B
C
!A
!B
!A + !B
!(!A + !B)
X
91
Álgebra booleana
† Teoremas e propriedades
„ Auxiliam na simplificação de equações e circuitos 
lógicos 
„ Reduzir o número de termos
„ Reduzir o número de variáveis
„ Reduzir o número de portas lógicas
92
Álgebra booleana
† Teoremas e propriedades
„ Propriedades da adição lógica (OR)
† X + 0 = X
† X + 1 = 1
† X + X = X
† X + !X = 1
Exemplo: F = A.(B + B)↔ F = A.B
93
Álgebra booleana
† Teoremas e propriedades
„ Propriedades da multiplicação lógica (AND)
† X . 0 = 0
† X . 1 = X
† X . X = X
† X . !X = 0
Exemplo: F = A + (B.!B) ↔ F = A + 0 ↔ F = A 
94
Álgebra booleana
† Teoremas e propriedades
„ X (nas propriedades) pode representar uma variável ou 
uma expressão em uma equação booleana
„ Exemplo 1: X representando a variável B
† F = A + (B.!B) ↔ F = A + 0 ↔ F = A
„ Exemplo 2: X representando expressão C.D
† F = A.B + (C.D . !(C.D)) ↔ F = A.B + 0 ↔ F = A.B
↔
95
Álgebra booleana
† Teoremas e propriedades
„ Complementação (óbvia)
† !!X = X
„ Comutatividade (ordem não altera o resultado)
† X + Y = Y + X (“a ordem das parcelas não altera a soma”)
† X . Y = Y . X (“a ordem dos fatores não altera o produto”)
X
!X !!X = X
↔
↔
96
Álgebra booleana
† Teoremas e propriedades
„ Associatividade (agrupamento não altera o resultado)
† X + (Y + Z) = (X + Y) + Z = X + Y + Z
† X.(Y.Z) = (X.Y).Z = X.Y.Z
↔ ↔
↔ ↔
97
Álgebra booleana
† Teoremas e propriedades
„ Distributividade (expansão/fatoração)
† X.(Y + Z) = X.Y + X.Z
† X + Y.Z = (X + Y) . (X + Z) (Cuidado! Não é trivial)
↔
↔
98
Álgebra booleana
† Teoremas e propriedades
„ Distributividade (expansão/fatoração)
† X.(Y + Z) = X.Y + X.Z
† X + Y.Z = (X + Y) . (X + Z) (Cuidado! Não é trivial)
† Exemplo 1
„ F = A.B.C + A.B.D
„ F = A.B.(C + D) (distributividade) 
† Exemplo 2
„ F = A.B.C + !A.B.!C
„ F = B.A.C + B.!A.!C (comutatividade)
„ F = B.(A.C + !A.!C) (distributividade)
99
Álgebra booleana
† Teoremas e propriedades
„ Distributividade
† X.(Y + Z) = X.Y + X.Z
† X + Y.Z = (X + Y).(X + Z) (Cuidado! Não é trivial)
† Prova distributividade não trivial
„ F = (X + Y) . (X + Z)
„ F = (X + Y).X + (X + Y).Z (distributividade)
„ F = X.(X + Y) + Z.(X + Y) (comutatividade)
„ F = X.X + X.Y + Z.X + Z.Y (distributividade)
„ F = X + X.Y + Z.X + Z.Y (propriedade do AND: X.X = X)
„ F = X.1 + X.Y + Z.X + Z.Y (propriedade do AND: X.1 = X)
„ F = X.(1 + Y) + Z.X + Z.Y (distributividade)
„ F = X.(1) + Z.X + Z.Y (propriedade do OR: X + 1 = 1)
„ F = X + Z.X + Z.Y (propriedade do AND: X.1 = X)
„ F = X.1 + Z.X + Z.Y (propriedade do AND: X.1 = X)
„ F = X.(1 + Z) + Z.Y (distributividade)
„ F = X.(1) + Z.Y (propriedade do OR: X + 1 = 1)
„ F = X + Z.Y (propriedade do AND: X.1 = X)
100
Álgebra booleana
† Teoremas e propriedades
„ Absorção
† X + X.Y = X (Cuidado!Não é trivial)
Exemplo: A = 1
Exemplo: A = 0
1 = 1
0
0 0
= 0
S depende só de A
S = A + A.B
S = A 
101
Álgebra booleana
† Teoremas e propriedades
„ Absorção
† X + X.Y = X (Cuidado! Não é trivial)
† Prova
„ F = X + X.Y
„ F = X.1 + X.Y (propriedade do AND: X.1 = X)
„ F = X.(1 + Y) (distributividade)
„ F = X.(1) (propriedade do OR: X + 1 = 1)
„ F = X (propriedade do AND: X.1 = X)
102
Álgebra booleana
† Teoremas e propriedades
„ Exemplos
† F = A.B.C + A.B.!C
† F = A.B.(C + !C) (distributividade)
† F = A.B.(1) (propriedade do OR: X + !X = 1)
† F = A.B (propriedade do AND: X.1=X)
103
Álgebra booleana
† Teoremas e propriedades
„ Exemplos
† F = H.!C + !H.P.!C
† F =!C.H + !C.!H.P (comutatividade)
† F = !C.(H + !H.P) (distributividade)
† F = !C.( (H + !H) . (H + P) ) (distributividade)
† F = !C.( (1) . (H + P) ) (propriedade do OR: X + !X = 1)
† F = !C.(H + P) (propriedade do AND: X.1 = X)
104
Álgebra booleana
† Teoremas e propriedades
„ Exemplos
† F = (!A + B).(A + B) (versão 1)
† F = A.(!A + B) + B.(!A + B) (distributividade)
† F = A.!A + A.B + B.!A + B (distributividade)
† F = 0 + A.B + B.!A + B (propriedade do AND: X.!X = 0)
† F = A.B + B.!A + B (propriedade do OR: X + 0 = X)
† F = B + A.B + !A.B (comutatividade)
† F = B.1 + A.B + !A.B (propriedade do AND: X.1 = X)
† F = B.(1 + A) + !A.B (distributividade)
† F = B.(1) + !A.B (propriedade do OR: X + 1 = 1)
† F = B + !A.B (propriedade do AND: X.1 = 1)
† F = B.1 + !A.B (propriedade do AND: X.1 = 1)
† F = B.(1 + !A) (distributividade)
† F = B.(1) (propriedade do OR: X + 1 = 1)
† F = B (propriedade do AND: X.1 = 1)
105
Álgebra booleana
† Teoremas e propriedades
„ Exemplos
† F = (!A + B).(A + B) (versão 2)
† F = A.(!A + B) + B.(!A + B) (distributividade)
† F = A.!A + A.B + B.!A + B (distributividade)
† F = 0 + A.B + B.!A + B (propriedade do AND: X.!X = 0)
† F = A.B + B.!A + B (propriedade do OR: X + 0 = X)
† F = B + A.B + !A.B (comutatividade)
† F = B.1 + A.B + !A.B (propriedade do AND: X.1 = X)
† F = B.(1 + A + !A) (distributividade)
† F = B.(1) (propriedade do OR: X + 1 = 1)
† F = B (propriedade do AND: X.1 = 1)
106
Álgebra booleana
† Teoremas e propriedades
„ Exemplos
† F = (!A + B).(A + B) (versão 3)
† F = A.(!A + B) + B.(!A + B) (distributividade)
† F = A.!A + A.B + B.!A + B (distributividade)
† F = 0 + A.B + B.!A + B (propriedade do AND: X.!X = 0)
† F = A.B + B.!A + B (propriedade do OR: X + 0 = X)
† F = B + A.B + !A.B (comutatividade)
† F = B + !A.B (absorção: X + XY = X)
† F = B (absorção: X + XY = X)
107
Álgebra booleana
† Teoremas e propriedades
„ OR AND
„ X + 0 = X X . 0 = 0
„ X + 1 = 1 X . 1 = X
„ X + X = X X . X = X
„ X + !X = 1 X . !X = 0
„ !!X = X (Complementação)
„ X + Y = Y + X (Comutatividade)
„ X . Y = Y . X (Comutatividade)
„ X + (Y + Z) = (X + Y) + Z = X + Y + Z (Associatividade)
„ X.(Y.Z) = (X.Y).Z = X.Y.Z (Associatividade)
„ X.(Y + Z) = X.Y + X.Z (Distributividade)
„ X + Y.Z = (X + Y) . (X + Z) (Distributividade)
„ X + X.Y = X (Absorção)
108
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = !A.!B + !A.B
† F = !A.(!B + B) (Distributividade)
† F = !A.(1) (Propriedade do OR: X + !X = 1)
† F = !A (Propriedade do AND: X.1 = X)
109
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = !A.B.C + !A.B.!C + A.C (versão 1)
† F = !A.B.(C + !C) + A.C (distributividade)
† F = !A.B.(1) + A.C (propriedade do OR: X + !X = 1)
† F = !A.B + A.C (propriedade do AND: X.1 = X)
† F = !A.B.C + !A.B.!C + A.C (versão 2)
† F = !A.(B.C + B.!C) + A.C (distributividade)
† F = !A.(B.(C + !C)) + A.C (distributividade)
† F = !A.(B.(1)) + A.C (propriedade do OR: X + !X = 1)
† F = !A.B + A.C (propriedade do AND: X.1 = X)
110
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = !A.B.!C + !A.B.C + A.B.!C + !A.B.!C (versão 1)
† F = !A.B.(!C + C) + A.B.!C + !A.B.!C (distributividade)
† F = !A.B.(1) + A.B.!C + !A.B.!C (X + !X = 1)
† F = !A.B + A.B.!C + !A.B.!C (X.1 = X)
† F = !A.B + B.!C.(A + !A) (distributividade)
† F = !A.B + B.!C.(1) (X + !X = 1)
† F = !A.B + B.!C (X.1 = X)
† F = B.(!A + !C) (distributividade)
111
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = !A.B.!C + !A.B.C + A.B.!C + !A.B.!C (versão 2)
† F = !A.B.!C + !A.B.!C + !A.B.C + A.B.!C (comutatividade)
† F = !A.B.!C + !A.B.C + A.B.!C (OR: X + X = X)
† F = B.!C.(!A + A) + !A.B.C (distributividade)
† F = B.!C.(1) + !A.B.C (OR: X + !X = 1)
† F = B.!C + !A.B.C (AND: X.1 = X)
† F = B.(!C + !A.C) (distributividade)
† F = B.((!C + !A).(!C + C)) (dist: X+Y.Z = (X+Y).(X+Z))
† F = B.((!C + !A).(1)) (OR: X + !X = 1)
† F = B.(!C + !A) (X.1 = X) 
112
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = !A.B.!C + A.B.!C + B.!C.D (versão 1)
† F = B.!C.(!A + A) + B.!C.D (distributividade)
† F = B.!C.(1) + B.!C.D (propriedade do OR: X + !X = 1)
† F = B.!C.(1 + D) (distributividade)
† F = B.!C.(1) (propriedade do OR: X + 1 = 1)
† F = B.!C (propriedade do AND: X.1 = X)
113
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = !A.B.!C + A.B.!C + B.!C.D (versão 2)
† F = B.!C.(!A + A + D) (distributividade)
† F = B.!C.(1 + D) (propriedade do OR: X + !X = 1)
† F = B.!C.(1) (propriedade do OR: X + 1 = 1)
† F = B.!C (propriedade do AND: X.1 = X)
114
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = !A.B.!C + A.B.!C + B.!C.D (versão 3)
† F = B.!C.(!A + A) + B.!C.D (distributividade)
† F = B.!C.(1) + B.!C.D (propriedade do OR: X + !X = 1)
† F = B.!C + B.!C.D (propriedade do AND: X.1 = X)
† F = B.!C (absorção: X + X.Y = X)
115
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = G.!K.!H + !H.D.G + G.!H.K
† F = G.!H.!K + G.!H.D + G.!H.K (comutatividade)
† F = G.!H.(!K + D + K) (distributividade)
† F = G.!H.(!K + K + D) (comutatividade)
† F = G.!H.(1 + D) (OR: X + !X = 1)
† F = G.!H.(1) (OR: X + 1 = 1)
† F = G.!H (AND: X.1 = X)
116
Álgebra booleana
† Teoremas e propriedades
„ Teoremas de De Morgan
† !(X + Y) = !X . !Y
† !(X . Y) = !X + !Y
„ Exemplo
† F = !( (!A + C).(B + !D) )
† F = !(!A + C) + !(B + !D) (De Morgan)
† F = !!A.!C + !B.!!D (De Morgan)
† F = A.!C + !B.D (Complementação)
„ Pode ser estendido para mais de duas variáveis
† !(X + Y + Z) = !X . !Y . !Z
† !(X . Y . Z) = !X + !Y + !Z
117
Álgebra booleana
† Teoremas e propriedades
„ Exemplo
† F = !(A + B).(!A + !B) (Versão 1)
† F = (!A.!B).(!A + !B) (De Morgan)
† F = (!A.!B).!A + (!A.!B).!B (Distributividade)
† F = !A.(!A.!B) + !B.(!A.!B) (Comutatividade)
† F = !A.!A.!B + !B.!A.!B (Associatividade)
† F = !A.!A.!B + !B.!B.!A (Comutatividade)
† F = !A.!B + !A.!B (AND: X.X = X)
† F = !A.!B (OR: X + X = X)
118
Álgebra booleana
† Teoremas e propriedades
„ OR AND
„ X + 0 = X X . 0 = 0
„ X + 1 = 1 X . 1 = X
„ X + X = X X . X = X
„ X + !X = 1 X . !X = 0
„ !!X = X (Complementação)
„ X + Y = Y + X (Comutatividade)
„ X . Y = Y . X (Comutatividade)
„ X + (Y + Z) = (X + Y) + Z = X + Y + Z (Associatividade)
„ X.(Y.Z) = (X.Y).Z = X.Y.Z (Associatividade)
„ X.(Y + Z) = X.Y + X.Z (Distributividade)
„ X + Y.Z = (X + Y) . (X + Z) (Distributividade)
„ X + X.Y = X (Absorção)
„ !(X + Y) = !X . !Y (De Morgan)
„ !(X . Y) = !X + !Y (De Morgan)
119
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = !( !(A + B).!(!C+ B) )
† F = !!(A + B) + !!(!C + B) (De Morgan)
† F = (A + B) + (!C + B) (Complementação)
† F = A + B + !C + B (Comutatividade)
† F = A + B + B + !C (Comutatividade)
† F = A + B + !C (OR: X + X = X)
120
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = A.B.!(!A + B.C)
† F = A.B.(!!A.!(B.C)) (De Morgan)
† F = A.B.(A.!(B.C)) (Complementação)
† F = A.B.(A.(!B + !C)) (De Morgan)
† F = A.B.(A.!B + A.!C) (Distributividade)
† F = A.B.A.!B + A.B.A.!C (Distributividade)
† F = A.A.B.!B + A.A.B.!C (Associatividade)
† F = A.B.!B + A.B.!C (AND: X . X = X)
† F = A.0 + A.B.!C (AND: X . !X = 0)
† F = 0 + A.B.!C (AND: X . 0 = 0)
† F = A.B.!C (OR: X + 0 = X)
121
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = !(C.!B).(A + !C.!A).B
† F = (!C + !!B).(A + !C.!A).B (De Morgan)† F = (!C + B).(A + !C.!A).B (Complementação/AND: X.X = X)
† F = (!C + B).((A + !C).(A + !A)).B (Distributividade)
† F = (!C + B).((A + !C).(1)).B (OR: X + !X = 1)
† F = (!C + B).(A + !C).B (AND: X . 1 = X)
† F = B.(!C + B).(A + !C ) (Comutatividade)
† F = (B.!C + B.B).(A + !C) (Distributividade)
† F = (B.!C + B).(A + !C) (AND: X.X = X)
† F = B.(A + !C) (Absorção: X + X.Y = X)
122
Álgebra booleana
† Teoremas e propriedades
„ Exercício
† F = !(A.B) + !(!A + B).C.!A + A
† F = !A + !B + !(!A + B).C.!A + A (De Morgan)
† F = !A + !B + (!!A.!B).C.!A + A (De Morgan)
† F = !A + !B + A.!B.C.!A + A (Complementação)
† F = !A + !B + A.!A.!B.C + A (Comutatividade)
† F = !A + !B + 0.!B.C + A (AND: X.!X = 0)
† F = !A + !B + 0 + A (AND: X.0 = 0)
† F = !A + !B + A (OR: X + 0 = X)
† F = !A + A + !B (Comutatividade)
† F = 1 + !B (OR: X + !X = 1)
† F = 1 (OR: X + 1 = 1) 
† Independente da combinação das entradas, F é sempre igual a 1
123
Álgebra booleana
† Programação
if ( idade > 18 || (idade > 18 && peso < 100) )
printf(“...”);
if ( idade > 18 )
printf(“...”);
Equivalentes
124
Álgebra booleana
† Programação
† Variáveis booleanas
„ I = idade > 18
„ P = peso < 100
† Equação
„ E = I + (I.P) ( idade > 18 || (idade > 18 && peso < 100) )
„ E = I.1 + I.P (AND: X.1 = X)
„ E = I.(1 + P) (Distributividade)
„ E = I.(1) (OR: X + 1 = 1)
„ E = I (AND: X.1 = X)
„ E = I (idade > 18)
if ( idade > 18 || (idade > 18 && peso < 100) )
printf(“...”);
True or False
125
Álgebra booleana
† Programação
if ( digito == 0 || (digito != 0 && tempo > 100) )
printf(“fim”);
if (digito == 0 || tempo > 100) )
printf(“fim”);
Equivalentes
126
Álgebra booleana
† Programação
† Variáveis booleanas
„ D0 = digito == 0
„ !D0 = digito != 0
„ T = tempo > 100
† Equação
„ E = D0 + (!D0.T) ( digito == 0 || (digito != 0 && tempo > 100) )
„ E = (D0 + !D0).(D0 + T) (distributividade: X + Y.Z = (X+Y).(X+Z) )
„ E = (1).(D0 + T) (OR: X + !X = 1)
„ E = D0 + T (AND: X.1 = X)
„ E = D0 + T (digito == 0 || tempo > 100)
if ( digito == 0 || (digito != 0 && tempo > 100) )
printf(“fim”);
True or False
127
Álgebra booleana
† Como provar a equivalência entre 2 circuitos ?
† Tabela verdade
„ Tabelas verdade iguais → circuitos equivalentes
† Simplificação de equações
1. Simplificando a equação de um dos circuitos chega-se à equação do outro →
circuitos equivalentes
2. Simplificando as equações dos circuitos, chega-se à mesma equação → circuitos
equivalentes
Equivalentes ?
128
Álgebra booleana
† Como provar a equivalência entre 2 circuitos ?
„ Tabela verdade
† Circuito 1 A B C D F
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 0
1 1 1 1 0
129
Álgebra booleana
† Como provar a equivalência entre 2 circuitos ?
„ Tabela verdade
† Circuito 2
B C F
0 0 0
0 1 0
1 0 1
1 1 0
Para comparar com um circuito com mais entradas, a avaliação do 
circuito com menos entradas deve partir das colunas de entradas do 
circuito com mais entradas 
130
Álgebra booleana
† Como provar a equivalência entre 2 circuitos ?
„ Tabela verdade
† Circuito 2 A B C D F
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
Preencher a coluna de saída baseado 
somente nas entradas do circuito. As 
demais entradas são ignoradas.
131
Álgebra booleana
† Como provar a equivalência entre 2 circuitos ?
„ Tabela verdade
† Circuito 2 A B C D F
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 0
1 1 1 1 0
Preencher a coluna de saída baseado 
somente nas entradas do circuito. As 
demais entradas são ignoradas.
132
Álgebra booleana
† Como provar a equivalência entre 2 circuitos ?
„ Tabela verdade
† Comparação A B C D F
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 0
1 1 1 1 0
A B C D F
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 0
1 1 1 1 0
Circuito 1 Circuito 2
Os circuitos são equivalentes.
133
Álgebra booleana
† Como provar a equivalência entre 2 circuitos ?
„ Simplificação de equações
† Circuito 1 
„ F = !A.B.!C + A.B.!C + B.!C.D
† Circuito 2 
„ F = B.!C
† Se a simplificação da equação do circuito 1 resultar na equação do 
circuito 2, então ambos são equivalentes
„ Simplificação
† F = !A.B.!C + A.B.!C + B.!C.D
† F = B.!C.(!A + A + D) (distributividade)
† F = B.!C.(1 + D) (propriedade do OR: X + !X = 1)
† F = B.!C.(1) (propriedade do OR: X + 1 = 1)
† F = B.!C (propriedade do AND: X.1 = X)
† Os circuitos são equivalentes
134
Álgebra booleana
† Como provar a equivalência entre 2 circuitos ?
„ Logisim
135
Álgebra booleana
† Como provar a não-equivalência entre 2 circuitos ?
† Tabela verdade 
„ Tabelas verdade diferentes → circuitos não-equivalentes
Equivalentes ?
136
Álgebra booleana
† Como provar a não-equivalência entre 2 circuitos ?
„ Tabela verdade
† Circuito 1 A B C D F
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 0
1 1 1 1 0
137
Álgebra booleana
† Como provar a não-equivalência entre 2 circuitos ?
„ Tabela verdade
† Circuito 2
B C F
0 0 1
0 1 1
1 0 1
1 1 0
Para comparar com um circuito com mais entradas, a avaliação do 
circuito com menos entradas deve partir das colunas de entradas do 
circuito com mais entradas 
138
Álgebra booleana
† Como provar a não-equivalência entre 2 circuitos ?
„ Tabela verdade
† Circuito 2 A B C D F
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
Preencher a coluna de saída baseado 
somente nas entradas do circuito. As 
demais entradas são ignoradas.
139
Álgebra booleana
† Como provar a não-equivalência entre 2 circuitos ?
„ Tabela verdade
† Circuito 2 A B C D F
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 1
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 0
1 1 1 1 0
Preencher a coluna de saída baseado 
somente nas entradas do circuito. As 
demais entradas são ignoradas.
140
Álgebra booleana
† Como provar a não-equivalência entre 2 circuitos ?
„ Tabela verdade
† Comparação A B C D F
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 0
1 1 1 1 0
Circuito 1 Circuito 2
Os circuitos não são equivalentes.
A B C D F
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 1
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 0
1 1 1 1 0
141
Álgebra booleana
† Como provar a não-equivalência entre 2 circuitos ?
„ Logisim
142
Álgebra booleana
† Derivação de expressões booleanas
„ Até agora
† Obtenção de tabelas verdade a partir de expressões booleanas
† Obtenção de circuitos lógicos a partir de expressões booleanas e 
vice-versa
„ A partir da tabela verdade é possível obter a expressão 
que representa a função booleana através de dois 
métodos
† Soma de produtos (mais usado)
„ Exemplo: F = A.B + !A.C + !C
† Produto de somas
„ Exemplo: F = (X + Y).(!X + Y + Z).(!Y + Z) 
„ Qualquer função booleana pode ser descrita por meio de 
soma de produtos ou produto de somas
143
Álgebra booleana
† Derivação de expressões booleanas
„ Soma de produtos
† Para cada linha da tabela verdade onde a saída é 1, cria-se um 
termo produto
† Em cada termo produto as variáveis de entrada iguais a 0 aparecem 
negadas e aquelas iguais a 1 aparecem não negadas
† Em seguidatodos os temos são somados (OR)
† Exemplo
A B C F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
F = !A.B.!C + !A.B.C + A.!B.C + A.B.!C 
→ !A.B.!C
→ !A.B.C
→ A.!B.C
→ A.B.!C
144
Álgebra booleana
† Derivação de expressões booleanas
„ Produto de somas
† Para cada linha da tabela verdade onde a saída é 0, cria-se um 
termo soma
† Em cada termo soma as variáveis de entrada iguais a 1 aparecem 
negadas e aquelas iguais a 0 aparecem não negadas
† Em seguida todos os temos são multiplicados (AND)
† Exemplo
A B C F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
F = (A+B+C).(A+B+!C).(!A+B+C).(!A+!B+!C) 
→ A+B+C
→ A+B+!C
→ !A+B+C
→ !A+!B+!C
145
Álgebra booleana
† Derivação de expressões booleanas
„ Derivar as expressões por soma de produtos e produto de somas
A B C D F
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 1
1 1 1 0 0
1 1 1 1 1
A B C F
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
A B F
0 0 0
0 1 1
1 0 1
1 1 0
Soma de produtos
- Saída = 1
- Variáveis = 0 aparecem 
negadas na expressão
Produto de somas
- Saída = 0
- Variáveis = 1 aparecem 
negadas na expressão
146
Álgebra booleana
† Derivação de expressões booleanas
„ Derivar as expressões por soma de produtos e produto de somas
A B F
0 0 0
0 1 1
1 0 1
1 1 0
→ !A . B
→ A . !B
→ A + B
→ !A + !B
F = (A + B).(!A + !B) 
F = !A.B + A.!B 
Equações equivalentes
F = (A + B).(!A + !B)
F = (A + B).!A + (A + B).!B (Distributividade)
F = !A.(A + B) + !B.(A + B) (Comutatividade)
F = !A.A + !A.B + !B.A + !B.B (Distributividade)
F = 0 + !A.B + !B.A + 0 (AND: X . !X = 0)
F = !A.B + !B.A (OR: X + 0 = X)
F = !A.B + A.!B (Comutatividade)
147
Álgebra booleana
† Derivação de expressões booleanas
„ Derivar as expressões por soma de produtos e produto de somas
A B C F
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
→ !A . !B . !C
→ !A . !B . C
→ !A . B . !C
→ !A . B . C
→ A . B . !C
→ A . B . C
F = !A.!B.!C + !A.!B.C + !A.B.!C + !A.B.C +
A.B.!C + A.B.C
→ !A + B + C
→ !A + B + !C
F = (!A + B + C).(!A + B + !C)
Equações equivalentes
148
Álgebra booleana
† Derivação de expressões booleanas
„ Derivar as expressões por soma de produtos e produto de somas
A B C D F
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 1
1 1 1 0 0
1 1 1 1 1
→ !A . !B . !C . !D
→ !A . !B . C . D
→ !A . B . C . !D
→ A . !B . !C . D
→ A . B . !C . D
→ A . B . C . D
F = !A.!B.!C.!D + !A.!B.C.D + !A.B.C.!D + 
A.!B.!C.D + A.B.!C.D + A.B.C.D→ A + B + C + !D
→ A + B + !C + D
→ A + !B + C + D
→ A + !B + C + !D
→ A + !B + !C + !D
→ !A + B + C + D
→ !A + B + !C + D
→ !A + B + !C + !D
→ !A + !B + C + D
→ !A + !B + !C + D
F = (A + B + C + !D).(A + B + !C + D).
(A + !B + C + D).(A + !B + C + !D).
(A + !B + !C + !D).(!A + B + C + D).
(!A + B + !C + D).(!A + B + !C + !D).
(!A + !B + C + D).(!A + !B + !C + D)
Equações equivalentes
149
Álgebra booleana
† Derivação de expressões booleanas
„ Projeto de circuitos baseado em tabela-verdade
† A tabela verdade é usada para descrever o comportamento 
do circuito
Tabela verdade
Equação booleana
Especificação
Circuito lógico
150
Álgebra booleana
† Derivação de expressões booleanas
„ Gerador de paridade
† Paridade é um método utilizado para detectar erro na transmissão 
de um conjunto de bits
† Se o número de bits em 1 a ser transmitido é impar, o bit de 
paridade deve ser 1, afim de tornar par o número total de bits em 1
† O receptor verifica o número total de bits em 1 (dados + bit de 
paridade). Se o número de bits em 1 for ímpar, um erro de 
transmissão é detectado
Circuito 
A
a
b
c
P
Circuito 
B
Transmissão paralela de 3 bits (a,b e c) mais o bit de paridade (P)
=1
=1
=1
=1
Ex. PC Ex. Impressora
151
Álgebra booleana
† Derivação de expressões booleanas
„ Gerador de paridade
† Paridade é um método utilizado para detectar erro na transmissão 
de um conjunto de bits
† Se o número de bits em 1 a ser transmitido é impar, o bit de 
paridade deve ser 1, afim de tornar par o número total de bits em 1
† O receptor verifica o número total de bits em 1 (dados + bit de 
paridade). Se o número de bits em 1 for ímpar, um erro de 
transmissão é detectado
Circuito 
A
a
b
c
P
Circuito 
B
Transmissão paralela de 3 bits (a,b e c) mais o bit de paridade (P)
=1
=1
=0
=0
Ex. PC Ex. Impressora
152
Álgebra booleana
† Derivação de expressões booleanas
„ Gerador de paridade
† Paridade é um método utilizado para detectar erro na transmissão 
de um conjunto de bits
† Se o número de bits em 1 a ser transmitido é impar, o bit de 
paridade deve ser 1, afim de tornar par o número total de bits em 1
† O receptor verifica o número total de bits em 1 (dados + bit de 
paridade). Se o número de bits em 1 for ímpar, um erro de 
transmissão é detectado
Transmissão paralela de 3 bits (a,b e c) mais o bit de paridade (P)
a
b
c
P
Circuito 
B
Ex. PC Ex. Impressora
Gera os dados a 
serem transmitidos
Gera o bit de 
paridade
153
Álgebra booleana
† Derivação de expressões booleanas
„ Gerador de paridade
† Tabela verdade
a b c P
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
a
b
c
P
Circuito 
B
Ex. PC Ex. Impressora
154
Álgebra booleana
† Derivação de expressões booleanas
„ Gerador de paridade
† Tabela verdade
a b c P
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
a
b
c
P
Circuito 
B
Ex. PC Ex. Impressora
155
Álgebra booleana
† Derivação de expressões booleanas
„ Gerador de paridade
† Equação booleana
a b c P
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
a
b
c
P
Circuito 
B
Ex. PC Ex. Impressora
P = !a.!b.c + !a.b.!c + a.!b.!c + a.b.c 
→ !a.!b.c
→ !a.b.!c
→ a.!b.!c
→ a.b.c
→ a + b + c
→ a + !b + !c
→ !a + b + !c
→ !a + !b + c
P = (a+b+c).(a+!b+!c).(!a+b+!c).(!a+!b+c)
156
Álgebra booleana
† Derivação de expressões booleanas
„ Gerador de paridade
† Circuito lógico
Negação (equivale a um inversor)
P = !a.!b.c + !a.b.!c + a.!b.!c + a.b.c 
!a.!b.c
!a.b.!c
a.!b.!c
a.b.c
!a.!b.c + !a.b.!c + a.!b.!c + a.b.c
157
Álgebra booleana
† Derivação de expressões booleanas
„ Gerador de paridade
† Circuito lógico
P = (a+b+c).(a+!b+!c).(!a+b+!c).(!a+!b+c)
a+b+c
a+!b+!c
!a+b+!c
!a+!b+c
(a+b+c).(a+!b+!c).(!a+b+!c).(!a+!b+c)
158
Álgebra booleana
† Derivação de expressões booleanas
„ Logisim
159
Álgebra booleana
† Derivação de expressões booleanas
„ Igualdade de 2 números de 2 bits
† A: A1 A0
† B: B1 B0
† Igual ← 1 quando A = B, senão 0
=
IguaisA
B
2
2
160
Álgebra booleana
† Derivação de expressões booleanas
„ Igualdade de 2 números de 2 bits
A1 A0 B1 B0 Iguais
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
161
Álgebra booleana
† Derivação de expressões booleanas
„ Igualdade de 2 números de 2 bits
A1 A0 B1 B0 Iguais
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 1
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 1
→ !A1.!A0.!B1.!B0
→ !A1.A0.!B1.B0
F = !A1.!A0.!B1.!B0 + !A1.A0.!B1.B0 + 
A1.!A0.B1.!B0 + A1.A0.B1.B0
→ A1.!A0.B1.!B0
→ A1.A0.B1.B0
162
Álgebra booleana
† Derivação de expressões booleanas
„ Igualdade de 2 números de 2 bits
F = !A1.!A0.!B1.!B0 + !A1.A0.!B1.B0 + 
A1.!A0.B1.!B0 + A1.A0.B1.B0
163
Álgebra booleana
† Derivação de expressões booleanas
„ Detecção de maioria de votos
† O sistema tem 4 entradas de votos (v1, v2, v3, v4)
† Cada uma é ativada por um votante
„ voto = 0: voto contra
„ voto = 1: voto a favor
† Maioria ← 1 quando a maioria das entradas de votos está
ativa
Maioria
v1
v2
v3v4
164
Álgebra booleana
† Derivação de expressões booleanas
„ Detecção de maioria de votos
v1 v2 v3 v4 Maioria
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
165
Álgebra booleana
† Derivação de expressões booleanas
„ Detecção de maioria de votos
v1 v2 v3 v4 Maioria
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
Maioria = !v1.v2.v3.v4 + v1.!v2.v3.v4 + 
v1.v2.!v3.v4 + v1.v2.v3.!v4 + v1.v2.v3.v4 
→ !v1.v2.v3.v4
→ v1.!v2.v3.v4
→ v1.v2.!v3.v4
→ v1.v2.v3.!v4
→ v1.v2.v3.v4
166
Álgebra booleana
† Derivação de expressões booleanas
„ Detecção de maioria de votos
Maioria = !v1.v2.v3.v4 + v1.!v2.v3.v4 + 
v1.v2.!v3.v4 + v1.v2.v3.!v4 + v1.v2.v3.v4 
167
Álgebra booleana
† Derivação de expressões booleanas
„ Projeto de circuitos baseado em tabela-verdade
† A tabela verdade é usada para descrever o comportamento 
do circuito
Tabela verdade
Equação booleana
Especificação
Circuito lógico
Simplificação
168
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número signed de 4 bits ≥ 5
† A: A3 A2 A1 A0
† A é um número binário em complemento de 2
† MaiorIgual ← 1 quando A ≥ 5
≥ 5
MaiorIgual
A
4
169
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número signed de 4 bits ≥ 5
A3 A2 A1 A0 MaiorIgual
0 0 0 0 0
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
-8 1 0 0 0
-7 1 0 0 1
-6 1 0 1 0
-5 1 0 1 1
-4 1 1 0 0
-3 1 1 0 1
-2 1 1 1 0
-1 1 1 1 1
170
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número signed de 4 bits ≥ 5
→ !A3.A2.!A1.A0
→ !A3.A2.A1.!A0
→ !A3.A2.A1.A0
MaiorIgual = !A3.A2.!A1.A0 + 
!A3.A2.A1.!A0 + !A3.A2.A1.A0
A3 A2 A1 A0 MaiorIgual
0 0 0 0 0 0
1 0 0 0 1 0
2 0 0 1 0 0
3 0 0 1 1 0
4 0 1 0 0 0
5 0 1 0 1 1
6 0 1 1 0 1
7 0 1 1 1 1
-8 1 0 0 0 0
-7 1 0 0 1 0
-6 1 0 1 0 0
-5 1 0 1 1 0
-4 1 1 0 0 0
-3 1 1 0 1 0
-2 1 1 1 0 0
-1 1 1 1 1 0
171
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número signed de 4 bits ≥ 5
MaiorIgual = !A3.A2.!A1.A0 + 
!A3.A2.A1.!A0 + !A3.A2.A1.A0
172
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número signed de 4 bits ≥ 5
„ MaiorIgual = !A3.A2.!A1.A0 + !A3.A2.A1.!A0 + !A3.A2.A1.A0
„ MaiorIgual = !A3.A2.(!A1.A0 + A1.!A0 + A1.A0) (Distributividade)
„ MaiorIgual = !A3.A2.(!A1.A0 + A1.(!A0 + A0)) (Distributividade)
„ MaiorIgual = !A3.A2.(!A1.A0 + A1.(1)) (OR: X + !X = 1)
„ MaiorIgual = !A3.A2.(!A1.A0 + A1) (AND: X . 1 = X)
„ MaiorIgual = !A3.A2.((A0 + A1).(!A1 + A1)) (Distributividade)
„ MaiorIgual = !A3.A2.((A0 + A1).(1)) (OR: X + !X = 1)
„ MaiorIgual = !A3.A2.(A0 + A1) (AND: X . 1 = X)
173
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número signed de 4 bits ≥ 5
„ MaiorIgual = !A3.A2.(A0 + A1)
174
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número par de 0s em um número de 4 bits
† A: A3 A2 A1 A0
† Par0 ← 1 quando A tiver um número par de zeros
† Neste caso, a equação extraida já está na forma mínima
#0s 
par
Par0
A
4
175
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número de 0s par em um número de 4 bits
A3 A2 A1 A0 Par0
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
176
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número de 0s par em um número de 4 bits
A3 A2 A1 A0 Par0
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0
1 1 1 1 1
→ !A3.!A2.!A1.!A0
→ !A3.!A2.A1.A0
→ !A3.A2.!A1.A0
→ !A3.A2.A1.!A0
→ A3.!A2.!A1.A0
→ A3.!A2.A1.!A0
→ A3.A2.!A1.!A0
Par0 = !A3.!A2.!A1.!A0 + 
!A3.!A2.A1.A0 + !A3.A2.!A1.A0 + 
!A3.A2.A1.!A0 + A3.!A2.!A1.A0 + 
A3.!A2.A1.!A0 + A3.A2.!A1.!A0 + 
A3.A2.A1.A0
→ A3.A2.A1.A0
177
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número de 0s par em um número de 4 bits
Par0 = !A3.!A2.!A1.!A0 + 
!A3.!A2.A1.A0 + !A3.A2.!A1.A0 + 
!A3.A2.A1.!A0 + A3.!A2.!A1.A0 + 
A3.!A2.A1.!A0 + A3.A2.!A1.!A0 +
A3.A2.A1.A0
178
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número par de 4 bits
† A: A3 A2 A1 A0
† Par ← 1 quando A é par
Número 
par
Par
A
4
179
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número par de 4 bits
A3 A2 A1 A0 Par
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
180
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número par de 4 bits
A3 A2 A1 A0 Par
0 0 0 0 1
0 0 0 1 0
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 1
1 0 0 1 0
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 1
1 1 1 1 0
→ !A3.!A2.!A1.!A0
→ !A3.!A2.A1.!A0
→ !A3.A2.!A1.!A0
→ !A3.A2.A1.!A0
→ A3.!A2.!A1.!A0
→ A3.!A2.A1.!A0
→ A3.A2.!A1.!A0
→ A3.A2.A1.!A0
Par = !A3.!A2.!A1.!A0 + !A3.!A2.A1.!A0 + 
!A3.A2.!A1.!A0 + !A3.A2.A1.!A0 + 
A3.!A2.!A1.!A0 + A3.!A2.A1.!A0 + 
A3.A2.!A1.!A0 + A3.A2.A1.!A0
181
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número par de 4 bits
Par = !A3.!A2.!A1.!A0 + !A3.!A2.A1.!A0 + 
!A3.A2.!A1.!A0 + !A3.A2.A1.!A0 + 
A3.!A2.!A1.!A0 + A3.!A2.A1.!A0 + 
A3.A2.!A1.!A0 + A3.A2.A1.!A0
182
Álgebra booleana
† Derivação de expressões booleanas
„ Detector de número par de 4 bits
A3 A2 A1 A0 Par
0 0 0 0 1
0 0 0 1 0
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 1
1 0 0 1 0
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 1
1 1 1 1 0
Par = !A0
!A0
183
Álgebra booleana
† Formas canônicas
„ Formas padrão de equações booleanas
† Soma de mintermos
† Produto de maxtermos
„ Mintermo
† Termo produto onde aparecem todas as variáveis da função 
exatamente uma vez (negadas ou não)
† Exemplos considerando a função F(a,b,c)
„ Mintermos: !a.b.c, a.!b.c, a.b.c
„ Não mintermos: a.c, b, !a.b.c.!c
„ Maxtermo
† Termo soma onde aparecem todas as variáveis da função 
exatamente uma vez (negadas ou não)
† Exemplos considerando a função F(a,b,c)
„ Maxtermos: (!a + b + !c), (!b + a + c), (!a + !b + !c)
„ Não maxtermos: (c + b), (!a + b + c + a)
184
Álgebra booleana
† Formas canônicas
„ Gerador de paridade
† Soma de mintermos: P = !a.!b.c + !a.b.!c + a.!b.!c + a.b.c 
† Produto de maxtemos: P = 
(a+b+c).(a+!b+!c).(!a+b+!c).(!a+!b+c)
„ Qualquer equação pode ser passada para a forma 
canônica através de manipulação algébrica utilizando 
teoremas e propriedades da álgebra booleana
† F = A.(B + C)
† F = A.B + A.C (Distributividade)
† F = A.B.1+ A.C.1 (AND: X.1 = X)
† F = A.B.(C + !C) + A.C.(B + !B) (OR: X + !X = 1)
† F = A.B.C + A.B.!C + A.C.B + A.C.!B (Distributividade)
185
Álgebra booleana
† Formas canônicas
„ Representação compacta
† Cada termo (produto ou soma) é representado por um número 
decimal obtido a partir das variáveis da função
† Termos produto: variáveis negadas valem 0 e variáveis normais 
valem 1
„ !A.B.!C → 0102 = 2
„ X.Y → 112 = 3
† Termos soma: variáveis negadas valem 1 e variáveis normais 
valem 0
„ !A + B + !C → 1012 = 5
„ X + Y → 002 = 0
186
Álgebra booleana
† Formas canônicas
„ Soma de mintermos
† P = !a.!b.c + !a.b.!c + a.!b.!c + a.b.c
† P = 0012 + 0102 + 1002 + 1112
† F(a,b,c) = ∑(1,2,4,7)
† O símbolo de somatório significa que os mintermos são somados (OR)
„ Produto de maxtermos
† P = (a+b+c).(a+!b+!c).(!a+b+!c).(!a+!b+c)
† P = 0002 . 0112 . 1012 . 1102
† F(a,b,c) = ∏(0,3,5,6)
† O símbolo de produtório significa que os maxtermos são multiplicados (AND)
187
Álgebra booleana
† Formas canônicas
„ Soma de mintermos
† Par0 = !A3.!A2.!A1.!A0 + !A3.!A2.A1.A0 + !A3.A2.!A1.A0+ 
!A3.A2.A1.!A0 + A3.!A2.!A1.A0 + A3.!A2.A1.!A0 + A3.A2.!A1.!A0 
+ A3.A2.A1.A0 
† Par0 = 00002 + 00112 + 01012 + 01102 + 10012 + 10102 + 11002
+ 11112
† F(A3,A2,A1,A0) = ∑(0,3,5,6,9,10,12,15)
188
Álgebra booleana
† Formas canônicas
„ Soma de mintermos
† F(a,b,c,d) = ∑(15,3,1,7)
† F(a,b,c,d) = 11112 + 00112 + 00012 + 01112
† F(a,b,c,d) = a.b.c.d + !a.!b.c.d + !a.!b.!c.d + !a.b.c.d
„ Produto de maxtermos
† F(a,b,c,d,e) = ∏(21,14,13)
† F(a,b,c,d,e) = 101012 + 011102 + 011012
† F(a,b,c,d) = (!a+b+!c.+d+!e).(a+!b+!c+!d+e).(a+!b+!c+d+!e)
189
Álgebra booleana
† Portas lógicas além das básicas OR, AND e 
inversor
„ NOR (Not OR)
„ NAND (Not AND)
„ XOR (Exclusive OR)
„ XNOR (Exclusive NOR)
190
Álgebra booleana
† Porta lógica NOR (“NOT OR”)
„ Combinação da porta lógica OR e um inversor
A B S
0 0 0
0 1 1
1 0 1
1 1 1
Tabela verdade OR
A B S
0 0 1
0 1 0
1 0 0
1 1 0
Tabela verdade NOR
Indica inversão
≡ S = !(A + B)
Se alguma 
entrada é igual 
a 1, a saída é 0
191
Álgebra booleana
† Porta lógica NOR (“NOT OR”)
„ Forma de onda
S
Se alguma 
entrada é igual 
a 1, a saída é 0
192
Álgebra booleana
† Porta lógica NOR (“NOT OR”)
„ Qualquer circuito lógico pode ser implementado utilizando as 
portas lógicas OR, AND e inversor
„ A partir de portas NOR pode-se obter portas OR, AND e inversor
„ Universal
193
Álgebra booleana
† Porta lógica NAND (“NOT AND”)
„ Combinação da porta lógica AND e um inversor
A B S
0 0 0
0 1 0
1 0 0
1 1 1
Tabela verdade AND
A B S
0 0 1
0 1 1
1 0 1
1 1 0
Tabela verdade NAND
Indica inversão
≡ S = !(A.B)
Se alguma 
entrada é igual 
a 0, a saída é 1
194
Álgebra booleana
† Porta lógica NAND (“NOT AND”)
„ Forma de onda
Se alguma 
entrada é igual 
a 0, a saída é 1
S
195
Álgebra booleana
† Porta lógica NAND (“NOT AND”)
„ Qualquer circuito lógico pode ser implementado utilizando as 
portas lógicas OR, AND e inversor
„ A partir de portas NAND pode-se obter portas OR, AND e inversor
„ Universal
196
Álgebra booleana
† Desenhar o circuito lógico usando apenas NOR e 
NAND
„ F = !(A.B.!(C + D))
197
Álgebra booleana
† Portas lógicas além das básicas OR, AND e 
inversor
„ NOR (Not OR)
„ NAND (Not AND)
„ XOR (Exclusive OR)
„ XNOR (Exclusive NOR)
198
Álgebra booleana
† Porta lógica XOR (Exclusive OR)
„ ou lógico exclusivo
† Símbolos: 
„ A B, A B C
„ Linguagens de programação (e.g. C, Java): ^
† Definição
„ A operação XOR sobre duas variáveis resulta 1 se elas 
tem valores diferentes. Caso contrário (iguais) resulta 0.
199
A B S
0 0 0
0 1 1
1 0 1
1 1 0
Tabela verdadePorta lógica
S = A B
Álgebra booleana
† Porta lógica XOR (Exclusive OR)
„ ou lógico exclusivo
† Símbolos: 
„ A B, A B C
„ Linguagens de programação (e.g. C, Java): ^
† Definição
„ A operação XOR resulta 1 se o número de entradas em 1 é 
ímpar. Caso contrário resulta 0.
200
Porta lógica
S = A B C
A B C S
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
XOR com mais de 
2 entradas tem bug 
no logisim
Álgebra booleana
† Porta lógica XOR (Exclusive OR)
„ A B ≡ !A.B + A.!B
= A B
201
Álgebra booleana
† Porta lógica XOR (Exclusive OR)
„ A B ≡ !A.B + A.!B
if ( (digito != 0 && tempo > 100) || (digito == 0 && tempo <= 100) )
printf(“fim”);
if ( digito == 0 ^ tempo > 100 )
printf(“fim”);
Equivalentes
!A AB !B
printf() só é executado se a expressão de um lado do XOR (^) é verdadeira e a do 
outro lado é falsa
202
Álgebra booleana
† Porta lógica XOR (Exclusive OR)
„ Forma de onda
Se as duas entradas são 
diferentes, a saída é 1
S
203
Álgebra booleana
† Porta lógica XOR (Exclusive OR)
„ Gerador de paridade
a b c P
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
a
b
c
P
Circuito 
B
Ex. PC Ex. Impressora
P = a b c
204
Álgebra booleana
† Porta lógica XOR (Exclusive OR)
„ Verificador de paridade
† Detecta erro na transmissão
a
b
c
P
Circuito 
B
Ex. PC Ex. Impressora
a b c P Erro
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
205
Álgebra booleana
† Porta lógica XOR (Exclusive OR)
„ Verificador de paridade
† Detecta erro na transmissão
a
b
c
P
Circuito 
B
Ex. PC Ex. Impressora
a b c P Erro
0 0 0 0 0
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 1 0 0
0 1 1 1 1
1 0 0 0 1
1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
Erro = a b c P
206
Álgebra booleana
† Porta lógica XOR (Exclusive OR)
„ Detector de número de 1s impar em um número de 8 bits
† A: A7 A6 A5 A4 A3 A2 A1 A0
† Impar1 ← 1 quando A tiver um número impar de 1s, senão 0
† Tabela verdade: 28 = 256 linhas
#1s 
impar
Impar1
A
8
A
207
Álgebra booleana
† Porta lógica XNOR (Exclusive NOR)
„ Combinação da porta lógica XOR e um inversor
„ Função coincidência
A B S
0 0 0
0 1 1
1 0 1
1 1 0
Tabela verdade XOR
A B S
0 0 1
0 1 0
1 0 0
1 1 1
Tabela verdade XNOR
Se as entradas 
são iguais, a 
saída é 1
S = !(A B)
208
Álgebra booleana
† Porta lógica XNOR (Exclusive NOR)
„ !(A B) ≡ !(!A.B + A.!B)
„ XNOR = !(!A.B + A.!B)
„ XNOR = !(!A.B).!(A.!B) (DeMorgan)
„ XNOR = (!!A + !B).(!A + !!B) (DeMorgan)
„ XNOR = (A + !B).(!A + B) (Complementação)
„ XNOR = (A + !B).!A + (A + !B).B (Distributividade)
„ XNOR = !A.(A + !B) + B.(A + !B) (Comutatividade)
„ XNOR = !A.A + !A.!B + B.A + B.!B (Distributividade)
„ XNOR = 0 + !A.!B + B.A + 0 (AND: X.!X = 0)
„ XNOR = !A.!B + B.A (OR: X + 0 = X)
„ XNOR = !A.!B + A.B (Comutatividade)
209
Álgebra booleana
† Porta lógica XNOR (Exclusive NOR)
„ !(A B) ≡ !(!A.B + A.!B) ≡ !A.!B + A.B
210
Álgebra booleana
† Porta lógica XNOR (Exclusive NOR)
„ Igualdade de 2 números de 2 bits
† A: A1 A0
† B: B1 B0
† Igual ← 1 quando A = B, senão 0
=
IguaisA
B
2
2
211
Álgebra booleana
† Porta lógica XNOR (Exclusive NOR)
„ Igualdade de 2 números de 2 bits
A1 A0 B1 B0 Iguais
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 1
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 1
212
Álgebra booleana
† Porta lógica XNOR (Exclusive NOR)
„ Igualdade de 2 números de 8 bits
„ Tabela verdade de 216 = 65536 linhas
1 XNOR de duas entradas por bit
213
Álgebra booleana
† Circuitos com mais de uma saída
„ Tratar separadamente cada saída
† Um circuito para cada saída compartilhando as mesmas entradas
„ Exemplo: circuito com duas saídas: F e G
† F = a.b + !c
† G = a.b + b.c
a.b
Otimização
a.b
214
Álgebra booleana
† Circuitos com mais de uma saída
„ Detecção de maioria de votos a favor e empate
† O sistema tem 4 entradas de votos (v1, v2, v3, v4)
† Cada uma é ativada por um votante
„ voto = 0: voto contra
„ voto = 1: voto a favor
† M ← 1 quando a maioria das entradas de votos está ativa
† e ← 1 quando o número de votos contra e a favor é igual
Mv1
v2
v3
v4
e
215
Álgebra booleana
† Circuitos com mais de uma saída
„ Detecção de maioria de votos a favor e empate
v1 v2 v3 v4 M
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
216
Álgebra booleana
† Circuitos com mais de uma saída
„ Detecção de maioria de votos a favor e empate
v1 v2 v3 v4 M e
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
217
Álgebra booleana
† Circuitos com mais de uma saída
„ Detecção de maioria de votos a favor e empate
v1 v2 v3 v4 M e
0 0 0 0 0 0
0 0 0 1 0 0
0 0 1 0 0 0
0 0 1 1 0 1
0 1 0 0 0 0
0 1 0 1 0 1
0 1 1 0 0 1
0 1 1 1 1 0
1 0 0 0 0 0
1 0 0 1 0 1
1 0 1 0 0 1
1 0 1 1 1 0
1 1 0 0 0 1
1 1 0 1 1 0
1 1 1 0 1 0
1 1 1 1 1 0
e = !v1.!v2.v3.v4 + !v1.v2.!v3.v4 + 
!v1.v2.v3.!v4 + v1.!v2.!v3.v4+ 
v1.!v2.v3.!v4 + v1.v2.!v3.!v4 
M = !v1.v2.v3.v4 + v1.!v2.v3.v4 + v1.v2.!v3.v4 + 
v1.v2.v3.!v4 + v1.v2.v3.v4 
!v1.v2.v3.v4
v1.!v2.v3.v4
v1.v2.!v3.v4
v1.v2.v3.!v4
!v1.v2.v3.v4
!v1.!v2.v3.v4
!v1.v2.!v3.v4
!v1.v2.v3.!v4
v1.!v2.!v3.v4
v1.!v2.v3.!v4
v1.v2.!v3.!v4
218
Álgebra booleana
† Circuitos com mais de uma saída
„ Detecção de maioria de votos a favor e empate
v1 v2 v3 v4 M
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
v1 v2 v3 v4 e
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 1 1
1 0 1 0 1
1 1 0 0 1
!v1.v2.v3.v4
v1.!v2.v3.v4
v1.v2.!v3.v4
v1.v2.v3.!v4
!v1.v2.v3.v4
!v1.!v2.v3.v4
!v1.v2.!v3.v4
!v1.v2.v3.!v4
v1.!v2.!v3.v4
v1.!v2.v3.!v4
v1.v2.!v3.!v4
e = !v1.!v2.v3.v4 + !v1.v2.!v3.v4 + 
!v1.v2.v3.!v4 + v1.!v2.!v3.v4 + 
v1.!v2.v3.!v4 + v1.v2.!v3.!v4 
M = !v1.v2.v3.v4 + v1.!v2.v3.v4 + 
v1.v2.!v3.v4 + v1.v2.v3.!v4 + 
v1.v2.v3.v4 
M = v2.v3.v4 + v1.v3.v4 + v1.v2.v4 + 
v1.v2.v3
219
Álgebra booleana
† Circuitos com mais de uma saída
„ Detecção de maioria de votos a favor e empate
e = !v1.!v2.v3.v4 + !v1.v2.!v3.v4 + 
!v1.v2.v3.!v4 + v1.!v2.!v3.v4 + 
v1.!v2.v3.!v4 + v1.v2.!v3.!v4 
M = v2.v3.v4 + v1.v3.v4 + v1.v2.v4 + 
v1.v2.v3
220
Álgebra booleana
† Circuitos com mais de uma saída
„ Logisim
221
Álgebra booleana
† Circuitos com mais de uma saída
„ Contador de 1s
† Circuito cuja saída apresenta em binário o número de entradas 
em 1
† X ← número de bits iguais a 1
Contador 
de 1s
a
b
c
X
2
222
Álgebra booleana
† Circuitos com mais de uma saída
„ Contador de 1s
† Circuito cuja saída apresenta em binário o número de entradas 
em 1
a b c X1 X0
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
223
Álgebra booleana
† Circuitos com mais de uma saída
„ Contador de 1s
† Circuito cuja saída apresenta em binário o número de entradas 
em 1
a b c X1 X0
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
!a.b.c
a.!b.c
a.b.!c
a.b.c
!a.!b.c
!a.b.!c
a.!b.!c
a.b.c
X1 = !a.b.c + a.!b.c + a.b.!c + a.b.c → b.a + b.c + a.c
X0 = !a.!b.c + !a.b.!c + a.!b.!c + a.b.c
224
Álgebra booleana
† Circuitos com mais de uma saída
„ Contador de 1s
† Circuito cuja saída apresenta em binário o número de entradas 
em 1
X1 = !a.b.c + a.!b.c + a.b.!c + a.b.c → b.a + b.c + a.c
X0 = !a.!b.c + !a.b.!c + a.!b.!c + a.b.c
225
Álgebra booleana
† Circuitos com mais de uma saída
„ Codificador de prioridades
† A saída S indica a entrada de maior prioridade ativa
† A prioridade das entradas é relativa aos seus números
„ R3 > R2 > R1
† Quando nenhuma entrada estiver ativa S ← 0
R1
R2
R3
S
2
Codificador 
de 
prioridade
226
Álgebra booleana
† Circuitos com mais de uma saída
„ Codificador de prioridades
† A saída S indica a entrada de maior prioridade ativa
† A prioridade das entradas é relativa aos seus números
„ R3 > R2 > R1
† Quando nenhuma entrada estiver ativa S ← 0
R3 R2 R1 S1 S0
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
227
Álgebra booleana
† Circuitos com mais de uma saída
„ Codificador de prioridades
† A saída S indica a entrada de maior prioridade ativa
† A prioridade das entradas é relativa aos seus números
„ R3 > R2 > R1
† Quando nenhuma entrada estiver ativa S ← 0
R3 R2 R1 S1 S0
0 0 0 0 0
0 0 1 0 1
0 1 0 1 0
0 1 1 1 0
1 0 0 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1
!R3.R2.!R1
!R3.R2.R1
R3.!R2.!R1
R3.!R2.R1
R3.R2.!R1
R3.R2.R1
S1 = !R3.R2.!R1 + !R3.R2.R1 + R3.!R2.!R1 + 
R3.!R2.R1 + R3.R2.!R1 + R3.R2.R1 
228
Álgebra booleana
† Circuitos com mais de uma saída
„ Codificador de prioridades
† A saída S indica a entrada de maior prioridade ativa
† A prioridade das entradas é relativa aos seus números
„ R3 > R2 > R1
† Quando nenhuma entrada estiver ativa S ← 0
R3 R2 R1 S1 S0
0 0 0 0 0
0 0 1 0 1
0 1 0 1 0
0 1 1 1 0
1 0 0 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1
S0 = !R3.!R2.R1 + R3.!R2.!R1 + R3.!R2.R1 + 
R3.R2.!R1 + R3.R2.R1 
!R3.!R2.R1
R3.!R2.!R1
R3.!R2.R1
R3.R2.!R1
R3.R2.R1
229
Álgebra booleana
† Circuitos com mais de uma saída
„ Codificador de prioridades
† Circuito não simplificado
S1 = !R3.R2.!R1 + !R3.R2.R1 + R3.!R2.!R1 + 
R3.!R2.R1 + R3.R2.!R1 + R3.R2.R1 
S0 = !R3.!R2.R1 + R3.!R2.!R1 + R3.!R2.R1 + 
R3.R2.!R1 + R3.R2.R1 
230
Álgebra booleana
† Circuitos com mais de uma saída
„ Codificador de prioridades
† Circuito simplificado
S1 = R3 + R2
S0 = !R2.R1 + R3
231