Módulo 06a – Análise e Síntese de Circuitos Combinatórios

Prévia do material em texto

1
1
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 1
Módulo 06a – Análise e Síntese de Circuitos 
Combinatórios
Marco Túlio Carvalho de Andrade
Professor Responsável
Versão: 2.0 (Setembro de 2.013)
PCS 2215
Sistemas Digitais I
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 2
Conteúdo
Análise e Síntese de Circuitos Combinatórios
0. Notas e Definições Preliminares.
1. Formas Canônicas.
1.1 Identidades Básicas.
2. Análise de Circuitos Combinatórios
2.1 Circuitos a Portas.
3. Síntese de Circuitos Combinatórios.
3.1 Síntese por Método Algébrico.
3.2 Síntese por Mapa de Karnaugh.
2
2
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 3
Conteúdo
Análise e Síntese de Circuitos Combinatórios
4. Minimização de Circuitos.
4.1 Implicantes primários.
4.1.1 Tabela de Cobertura
4.2 Minimização pelo Método Tabular
4.3 Mapas de Karnaugh Considerando-se os 
“Zeros” das Funções.
4.4 Funções Incompletamente Definidas
5. Exemplos de Aplicação. 
Bibliografia
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 4
0. Notas e Definições Preliminares
Nota 1. - Uma Álgebra de Chaveamento
({F.C.}, , , ~, 0t, 1t) pode ser vista como 
um caso particular de uma estrutura 
algébrica genérica denominada Álgebra de 
Boole, onde o conjunto “S” gerador da 
estrutura é o conjunto de funções de 
chaveamento “{F.C.}”.
3
3
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 5
0. Notas Preliminares
Nota 2. - Álgebra Booleana (ver Complementos de 
Álgebra Boolena) - É uma sêxtupla:
(S, , , ~, fronteira inferior Máxima, 
Fronteira Superior mínima)
Nota 3. - Outra particularização de interesse é a 
Álgebra Booleana constituída pelas Classes de 
Equivalência geradas por funções de chaveamen-
to de n variáveis (x1, x2, ..., xn), onde existe uma 
correspondência biunívoca entre elementos de 
{F.C.} e de {C.E.}:
({C.E.}, , , ~, Ft, Vt)
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 6
0. Notas Preliminares
Nota 4. - Todo teorema de uma Álgebra 
Booleana vale para uma Álgebra de 
Chaveamento.
Definição 1. - Literal - Representa uma 
variável ou uma variável complementada, 
tendo um sentido mais amplo que o de 
variável.
4
4
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 7
0. Notas Preliminares
Definição 2. - Expressões Booleanas geradas sobre 
x1, x2, ..., xn são definidas recursivamente:
1-) 0, 1, x1, x2, ..., xn são expressões Booleanas.
2-) Se X1 e X2 são expressões Booleanas então, 
também também são expressões Booleanas:
(a) (X1) (b) ~X1 (c) X1 ∨ X2 (d) X1 ∧ X2
3-) Se X é uma expressão Booleana gerada sobre 
os símbolos x1, x2, ..., xn então podemos escrever
X = X(x1, x2, ..., xn)
onde cada símbolo xi (ou ~xi) é chamado de um
Literal.
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 8
1. Formas Canônicas
Sejam, a Álgeb. de Chaveamento ({F.C.},,,~,0t,1t) 
e a Álgebra de Boole ({C.E.},,,~,Ft,Vt) das 
formas e Classes Booleanas geradas pelas 
variáveis x1, x2, ..., xn. Seja li uma metavariável que 
pode valer xi ou ~xi.
Definição 1.1 - Produto Canônico (ou minter-
mo) é toda Expressão de Chaveamento (ou 
Booleana) composta pelo Produto de todas 
as variáveis, complementadas ou não:



n
j
jni llllPC
1
21 )(,.,.,.
5
5
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 9
1. Formas Canônicas
Definição 1.2 - Primeira Forma Canônica é 
toda Expressão de Chaveamento (ou Ex-
pressão Booleana) composta pela Soma de 
produtos canônicos, ou de mintermos, dife-
rentes entre si.
Teorema 1.1 - Toda Classe de Equivalência Cn
pode representar-se mediante sua Primeira 
Forma Canônica que é única para esta 
Classe.
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 10
Observações (I):
– Como em um produto canônico intervém 
todas as variáveis, sua interpretação será 
sempre “0” a menos de uma determinada: 
aquela que associe “1” a todas variáveis 
sem “~” e “0” a todas com “~”.
– Portanto cada um dos 2n produtos canôni-
cos serve para representar um, e apenas 
um, dos 2n átomos (ou elementos atômi-
cos).
1. Formas Canônicas
6
6
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 11
1. Formas Canônicas
Observações (II):
– Segundo Teorema da Álgebra de Chaveamento 
todo elemento desta Álgebra distinto de 0 pode 
expressar-se, de maneira única, como uma 
soma de átomos. Logo qualquer classe de 
equivalência distinta de C0 pode expressar-se 
de maneira única como uma soma de átomos.
– Portanto pode-se representar de maneira única 
como uma Soma de Produtos Canônicos, isto 
é, representar na Primeira Forma Canônica
(ou Soma Canônica).
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 12
1. Formas Canônicas
Observações (III) - Existe uma notação abreviada 
para descrever as formas canônicas:
1-) Baseia-se em associar um número decimal a 
cada produto canônico;
2-) Este número é aquele que resulta ao 
interpretar-se como um número binário a 
combinação de “Zeros” e “Uns” das variáveis 
para a qual a interpretação do produto em 
questão é “1”.
3-) Por exemplo: A interpretação de ~x3.x2.x1 é 
“1” para x3=0, x2=1 e x1=1 e “011” em binário é 
“3” em decimal (“m3”). 
7
7
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 13
1. Formas Canônicas
Mintermos para três variáveis:
x3 x2 x1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
m0 = ~x3 ~x2 ~x1
m1 = ~x3 ~x2 x1
m2 = ~x3 x2 ~x1
m3 = ~x3 x2 x1
m4 = x3 ~x2 ~x1
m5 = x3 ~x2 x1
m6 = x3 x2 ~x1
m7 = x3 x2 x1
Mintermos
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 14
1. Formas Canônicas
C0 = ~(C1 + C2 + C4 + C8)
C1 = C1
C2 = C2
C3 = C1 + C2
C4 = C4
C5 = C1 + C4
C6 = C2 + C4
C7 = C1 + C2 + C4
C8 = C8
C9 = C1 + C8
C10 = C2 + C8
C11 = C1 + C2 + C8
C12 = C4 + C8
C13 = C1 + C4 + C8
C14 = C2 + C4 + C8
C15 = C1 + C2 + C4 + C8
x2
0
0
1
1
x1
0
1
0
1
C2
0
0
1
0
C0
0
0
0
0
C1
0
0
0
1
C3
0
0
1
1
C4
0
1
0
0
C5
0
1
0
1
C6
0
1
1
0
C7
0
1
1
1
C1
0
1
0
1
0
C8
1
0
0
0
C9
1
0
0
1
C11
1
0
1
1
C1
2
1
1
0
0
C1
3
1
1
0
1
C1
4
1
1
1
0
C15
1
1
1
1
m0
m1
m2
m3
8
8
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 15
1. Formas Canônicas
Definição 1.3 - Soma Canônica (ou Maxtermo) é to-
da Expressão de Chaveamento (ou Booleana) 
composta pela soma de todas as variáveis, comple-
mentadas ou não:



n
j
jni llllSC
1
21 )(...
Definição1.4- Segunda Forma Canônica é toda Expressão
de Chaveamento (ou Booleana) composta pelo produto de 
somas canônicas, ou de Maxtermos, diferentes entre si.
Teorema 1.2 - Toda Classe de Equivalência Cn pode repre-
sentar-se mediante sua Segunda Forma Canônica que é 
única para esta Classe.
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 16
1. Formas Canônicas
Observações:
 Como em uma soma canônica intervém todas as 
variáveis, sua interpretação será sempre “1”, a 
menos de uma determinada: aquela que associe 
“0” a todas variáveis sem “~” e “1” a todas com 
“~”.
 Em resumo: Qualquer classe de equivalência pode 
também ser expressa de maneira única como um 
Produto de Somas Canônicas, isto é, pode ser 
representada na Segunda Forma Canônica. (ou 
“Produto Canônico”).
9
9
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 17
1. Formas Canônicas
Observações (II) - Existe uma notação abreviada 
para descrever a segunda Forma Canônica:
1-) Baseia-se em associar um número decimal a 
cada soma canônica.
2-) Este número é aquele que resulta ao 
interpretar-se como um número binário a 
combinação de “Zeros” e “Uns” das variáveis 
para a qual a interpretação da soma em questão 
é “0”.
3-) Por exemplo: A interpretação de x3+~x2+~x1
é “0” para x3=0, x2=1 e x1=1 e “011” em 
binário é “3” em decimal (“M3”). 
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 18
1. Formas Canônicas
Maxtermos para três variáveis:
x3 x2 x1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
M0 = x3 + x2 + x1
M1 = x3 + x2 + ~x1
M2 = x3 + ~x2 + x1
M3 = x3 + ~x2 + ~x1
M4 = ~x3 + x2 + x1
M5 = ~x3 + x2 + ~x1
M6 = ~x3 + ~x2 + x1
M7 = ~x3 + ~x2 + ~x1
Maxtermos
10
10
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 19
1. Formas Canônicas
C0 = C7 . C11 . C13 . C14
C1 = C7 . C11 . C13
C2 = C7 . C11 . C14
C3 = C7 . C11
C4 = C7 . C13 . C14
C5 = C7 . C13
C6 = C7 . C14
C7 = C7
C8 = C11 . C13 . C14
C9 = C11 . C13
C10 = C11 . C14
C11 = C11
C12 = C13 . C14
C13 = C13
C14 = C14
C15 = ~(C7 . C11 . C13 . C14)
x2
0
0
1
1
x1
0
1
0
1
C2
0
0
1
0
C0
0
0
0
0
C1
0
0
0
1
C3
0
0
1
1
C4
0
1
0
0
C5
0
1
0
1
C6
0
1
1
0
C7
0
1
1
1
C1
0
1
0
1
0
C8
1
0
0
0
C9
1
0
0
1
C11
1
0
1
1
C1
2
1
1
0
0
C1
3
1
1
0
1
C1
4
1
1
1
0
C15
1
1
1
1
M0
M1
M2
M3
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 20
1. Formas Canônicas
Mintermos e Maxtermos para três variáveis:
x3 x2 x1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
m0 = ~x3 ~x2 ~x1 = ~M0
m1 = ~x3 ~x2 x1 = ~M1
m2 = ~x3 x2 ~x1 = ~M2
m3 = ~x3 x2 x1 = ~M3
m4 = x3 ~x2 ~x1 = ~M4
m5 = x3 ~x2 x1 = ~M5
m6 = x3 x2 ~x1 = ~M6
m7 = x3 x2 x1 = ~M7
M0 = x3 + x2 + x1 = ~m0
M1 = x3 + x2 + ~x1 = ~m1
M2 = x3 + ~x2 + x1 = ~m2
M3 = x3 + ~x2 + ~x1 = ~m3
M4 = ~x3 + x2 + x1 = ~m4
M5 = ~x3 + x2 + ~x1 = ~m5
M6 = ~x3 + ~x2 + x1 = ~m6
M7 = ~x3 + ~x2 + ~x1 = ~m7
Mintermos Maxtermos
11
11
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 21
1. Formas Canônicas
Observações adicionais: A Álgebra de Chavea-
mento ({F.C.}, , , ~, 0t, 1t) tem o mesmo 
número de Funções de Chaveamento que o 
de classes de equivalência da Álgebra 
Booleana ({C.E.}, , , ~, Ft, Vt), que é:
– {F.C.} tem um número de “n-tuplas” 
diferentes em {0,1}n igual a k = 2n e gera 
2k combinações distintas para aplicar cada 
uma destas k “n-tuplas” em {0,1}. 
2
2
n =k
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 22
1. Formas Canônicas
Observações adicionais:
– {C.E.} tem um número de k = 2n produtos 
canônicos com os quais pode-se escrever as 
2k primeiras formas canônicas diferentes.
– Pela definição 4.3 do material adicional de 
Álgebra Booleana, elas são isomorfas.
– Sendo isomorfas existe uma correspondên-
cia biunívoca entre cada Função de Chavea-
mento de ordem “n” e cada classe de equi-
valência de Expressões Booleanas de “n” 
variáveis.
12
12
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 23
1. Formas Canônicas
Observações (continuação): A correspondência é tal 
que se fi e fk estão em correspondência com Ci e Ck
então (fi+fk) e (fi.fk) estarão em correspondência 
com (Ci+Ck) e (Ci.Ck).
Importância na aplicação ao projeto de circuitos 
lógicos:
– A saída de um circuito expressa como uma 
Função de Chaveamento tem infinitas formas 
associadas a uma classe de equivalência.
– Como Engenheiros nos interessa encontrar a 
forma mínima!
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 24
1.1. Identidades Básicas
A seguir são apresentadas identidades básicas para duas 
ou três variáveis:
I1 - x+0=x x.1=x
[Elemento neutro ou identidade]
I2 - x+1=1 x.0=0 
[Elementos máximo/mínimo ou elemento nulo]
I3 - x+~x=1 x.~x=0
[Complemento]
I4 - ~(~x) = x
[Involução]
13
13
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 25
1.1. Identidades Básicas
Mais identidades:
I5 - x + x = x x . x = x
[Idempotência]
I6 - x+y=y+x x.y=y.x
[Comutativa]
I7 - x+(y+z)=(x+y)+z x.(y.z)=(x.y).z
[Associativa]
I8 - x.(y+z)=x.y+x.z x+(y.z)=(x+y).(x+z)
[Distributiva]
I9 - x+x.y=x [I9a] x.(x+y)=x [I9b]
[Absorção ou cobertura]
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 26
1.1. Identidades Básicas
Mais identidades:
I10 - ~(x+y)=~x.~y ~(x.y)=~x+~y
[De Morgan]
I11a-(x+y).(~x+z).(y+z)=(x+y).(~x+z)=x.z+~x.y
I11b - x.y+~x.z+y.z=x.y+~x.z 
[Consenso]
I12 - x . y + x . ~y = x (x + y) . (x + ~y) = x
[Combinação]
I13 - (x+y).(~x+z)= x.z+~x.y
I14 - (x+~x.y)=(x+y) x.(~x+y)=x.y
14
14
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 27
1.1. Identidades Básicas
Exemplo 1.1: Simplificar (x+y+z).(x.~y+y.z+x.~z) =
= x.x.~y+x.y.z+x.x.~z+x.y.~y+y.y.z+x.y.~z+x.~y.z+y.z.z+x.z.~z=
= x.~y + x.y.z + x.~z + x.0 + y.z + x.y.~z + x.~y.z + y.z + x.0 =
= x.(~y + y.z) + x.~z + x.y.~z + y.z + x.~y.z + y.z =
= x.(~y + z) + x.~z(1 + y) + z.(y + x.~y) + y.z =
= x.~y + x.z + x.~z + z.(y + x) + y.z =
= x.~y + x.z + x.~z + y.z + x.z + y.z =
= x.~y + x.z + x.z + x.~z + y.z + y.z =
= x.~y + x.(z + ~z) + y.z =
= x.~y + x.1 + y.z =
= x.~y + x + y.z =
= x + y.z 
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 28
1.1. Identidades Básicas
Exemplo 1.2: Calcular (desenvolver)
f = ~(x.y+~y.z+x.~z)
Exemplo 1.3: Verificar que a expressão
(~y + w.x.z + ~x.z + ~w.x) . (y + w.x + x.z)
é idêntica à expressão
x . (w + y) . (~w + ~y) + z . (x + y)
Exemplo 1.4: Comprovar a validade da identidade I14, 
[(x + ~x.y) = (x+y)],por Diagrama de Venn.
15
15
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 29
1.1. Identidades Básicas
Exemplo 1.4: Comprovar a validade da identidade I14, 
[(x + ~x.y) = (x+y)], por Diagrama de Venn.
~x
y
~x . y
x
x + ~x . y
x + y
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 30
1.1. Identidades Básicas
Maxtermos/mintermos permitem a decomposição 
sistemática de Expressões de Chaveamento em 
subexpressões com subconjuntos das variáveis.
Teorema da Expansão de Shannon:
Qualquer Expressão de Chaveamento do tipo
fn(x1, x2, x3, ..., xn)
pode ser decomposta na Expressão [I15a]
x1 . fn(1, x2, x3, ..., xn) + ~ x1 . fn(0, x2, x3, ..., xn)
ou decomposta em sua Expressão dual [I15b]
[x1+fn(0, x2, x3, ..., xn)] . [ ~ x1+fn(1, x2, x3, ..., xn)]
16
16
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 31
1.1. Identidades Básicas
Exemplo da aplicação de [I15a]:
f3(x1, x2, x3) = x1.f3(1, x2, x3) + ~ x1.f3(0, x2, x3)
f3(x1, x2, x3) = x1.x2.f3(1,1, x3) + x1.~x2.f3(1,0, x3)
+ ~x1.x2.f3(0,1, x3) + ~ x1.~x2.f3(0,0, x3) 
f3(x1, x2, x3)= x1.x2.x3.f3(1,1,1) + x1.x2.~x3.f3(1,1,0)
+ x1.~x2.x3.f3(1,0,1) + x1.~x2.~x3.f3(1,0,0)
+ ~x1.x2.x3.f3(0,1,1) + ~x1.x2.~x3.f3(0,1,0)
+ ~x1.~x2.x3.f3(0,0,1) + ~x1.~x2.~x3.f3(0,0,0)
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 32
1.1. Identidades Básicas
Exemplo da aplicação de [I15b]:
f3(x1, x2, x3)=[x1 + f3(0, x2, x3)].[~ x1 + f3(1, x2, x3)]
f3(x1, x2, x3)=[x1+x2+f3(0,0, x3)].[x1+~x2+f3(0,1, x3)]
.[~x1+x2+f3(1,0, x3)].[~ x1+~x2+f3(1,1, x3)]
f3(x1,x2, x3)=[x1+x2+x3+f3(0,0,0)].[x1+x2+~x3+f3(0,0,1)]
. [x1+~x2+x3+f3(0,1,0)] . [x1+~x2+~x3+f3(0,1,1)]
. [~x1+x2+x3+f3(1,0,0)] . [~x1+x2+~x3+f3(1,0,1)]
. [~x1+~x2+x3+f3(1,1,0)] . [~x1+~x2+~x3+f3(1,1,1)]
17
17
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 33
1.1. Identidades Básicas
Mais Identidades:
(fn
DUAL)DUAL = fn [I16] 
[fn = gn]  [fn
DUAL = gn
DUAL] [I17] 
fDUAL(x1, x2, ..., xn) = ~f(~x1, ~x2, ..., ~xn) [I18a]
fDUAL(x, y, ..., z) = ~f(~x, ~y, ..., ~z) [I18b] 
Exemplo: Dado fn = x.y + ~y.z
fn
DUAL = (x+y) . (~y+z)
~fn=~(x.y+~y.z)=~(x.y).~(~y.z)= (~x+~y) . (y+~z)
Portanto: fn
DUAL(x,y,z) = ~fn(~x,~y,~z)
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 34
2. Análise de Circuitos Combinatórios
Um Circuito Combinatório (ou circuito sem me-
mória) pode ser visto como um dispositivo lógi-
co cuja saída (isto é, o efeito da operação lógica 
que ele realiza) depende apenas das entradas no 
instante presente (isto é, das causas lógicas).
Em vista disto pode-se representar a saída de um 
circuito combinatório por uma função do tipo 
fn(x1, x2, ..., xn), sendo (x1, x2, ..., xn) as entradas 
lógicas. Ou ainda, por uma função do tipo fn(x, 
y, ..., z), sendo (x, y, ..., z) as entradas lógicas.
18
18
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 35
2. Análise de Circuitos Combinatórios
A forma de análise de um Circuito Combinatório
depende do modelo utilizado para especificá-lo:
Diagrama Lógico Expressão de Chaveamento
Estrutura exposta;
comportamento escondido 
(este pode ser extraído)
Comportamento exposto; 
Estrutura escondida
(representa infinitas estruturas)
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 36
2. Análise de Circuitos Combinatórios
Tipicamente extrai-se a Expressão de Chaveamen-
to do Diagrama Lógico, quando então constrói-
se a Tabela da Verdade.
Diagrama Lógico
Identificação exata das opera-
ções algébricas envolvidas:
- Modelo funcional
- Interpretação de Engenharia
Expressão de Chaveamento
Tabela da Verdade
19
19
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 37
2. Análise de Circuitos Combinatórios
Ao analisar um circuito combinatório pode-se 
utilizar um de três procedimentos básicos:
1-) Enumeração de todos os caminhos de propaga-
ção dos sinais de entrada - Levantam-se os cami-
nhos possíveis das entradas para as saídas.
2-) Aplicação da Identidade de Shanonn (I15) - Fi-
xam-se os valores lógicos de uma dada variável xi
gerando-se dois subcircuitos de n-1 variáveis. 
3-) Decomposição - Divide-se o circuito em blocos 
e faz-se a análise no nível de blocos elementares.
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 38
2. Análise de Circuitos Combinatórios
Exemplo 2.1.1 - 1) Enumeração dos caminhos dos 
sinais de entrada:
x1
x2
~x1
~x2
~x1.~x2
x1.x2
x1.x2 + ~x1.~x2
20
20
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 39
Exemplo 2.1.2-2) Aplicação da identidade de Shanonn (I15):
f2(x1, x2) = x1 . f2(1, x2) + ~x1 . f2(0, x2)
2. Análise de Circuitos Combinatórios
[a] x1 = 0  ~x1 = 1  I15a  [b] x1 . f(1, x2) + ~x1 . f(0, x2)
[c] f(1, x2) = x2 e [d] f(0, x2) = ~x2
x1
x2
0
x2
1
~x2
0
~x2
~x2
x1
x2
1
x2
0
~x2
x2
0
x2
Expressão final [e]: x1 . x2 + ~x1 . ~x2
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 40
2. Análise de Circuitos Combinatórios
Exemplo 2.1.3 - 3) Decomposição em blocos 
elementares:
x1
x2
~x1
~x2
x1
x2
x1.x2 + ~x1.~x2
~x1.~x2
x1.x2
~x1.~x2
x1.x2
~x1
~x2
21
21
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 41
2.1. Circuitos a Portas
Definição 2.1.1 - Portas Lógicas:
– Uma porta lógica é uma função de em .
– A porta AND (E) é a função  de em .
– A porta OR (OU) é a função  de em .
– A porta NOT (NÃO) é a função ~ de em .
Definição 2.1.2 - O conjunto {p1, p2, ..., pn} de por-
tas é denominado funcionalmente completo se, 
dado qualquer inteiro positivo n e uma função f 
de em , é possível construir um circuito 
combinatório que compute a função f utilizando 
apenas {p1, p2, ..., pn}.
nZ2 2Z
nZ2 2
Z
nZ2 2
Z
2Z
2Z
nZ2 2Z
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 42
2.1. Circuitos a Portas
Exemplo 2.1.4 - Os teoremas que atestam que toda 
classe de equivalência pode ser gerada a partir da 
primeira e da segunda formas canônicas (1.1 e 1.2) 
permitem mostrar que o conjunto de portas {AND, 
OR, NOT} é funcionalmente completo.
Definição 2.1.3 - Portas lógicas NAND e NOR.
Teorema 2.1.1 - Os conjuntos de portas
{AND, NOT}={NAND} e {OR, NOT}={NOR}
são funcionalmente completos.
NAND NOR
22
22
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 43
2.1. Circuitos a Portas - Análise
Quando o circuito aparece determinado por meio de 
um diagrama de portas lógicas a maneira mais 
eficiente de análise é a decomposição em funções 
intermediárias, da saída para a entrada, ou a 
composição de funções, da entrada para a saída.
x1
x2
x3
f3
f1
f2
x4
x5
f
© Andrade,Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 44
2.1. Circuitos a Portas - Análise
As entradas do circuito anterior são (x1, x2, x3, x4, x5)
e sua saída é o valor lógico f(x1, x2, x3, x4, x5). 
Da saída para a entrada tem-se:
f(x1, x2, x3, x4, x5) = f1(x1, x2) + f2(x3, x4, x5) =
f(x1, x2, x3, x4, x5) = x1. x2 + x3 . f3(x4, x5) =
f(x1, x2, x3, x4, x5) = x1. x2 + x3 . (x4 + x5) =
f(x1, x2, x3, x4, x5) = x1. x2 + x3 . x4 + x3 . x5
x1
x2
x3
f3
f1
f2
x4
x5
f
Exemplo 2.1.5
23
23
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 45
2.1. Circuitos a Portas - Análise
Exemplo 2.1.6 - Análise de circuitos E-OU (OU-E) a 
dois níveis: 
x1
x2
x3
f1
f2
f3
f
x4
x5
x6
x1
x2
x3
f1
f2
f3
f
x4
x5
x6
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 46
2.1. Circuitos a Portas - Análise
Exemplo 2.1.7 - Análise de circuitos XOR: 
x1
x2
f1
x3 fx4
x5




f2 f3
Verifica-se a associatividade da operação, de modo 
que f poderia ser representada por:
f

x1
x3
x2
x5
x4
24
24
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 47
2.1. Circuitos a Portas - Análise
Exemplo 2.1.8 - Análise de circuitos NAND: 
x1
x2
f1
x3 fx4
x5
f2 f3
x1
x2
f1
x3 fx4
x5
f2 f3
Exemplo 2.1.9 - Análise de circuitos NOR: 
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 48
3. Síntese de Circuitos Combinatórios
Síntese
Diagrama
Lógico
Expressão
Algébrica
Tabela da
Verdade
Inter-
pretação
Análise
25
25
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 49
3. Síntese de Circuitos Combinatórios
 Terminologia:
 Engenheiro de Computação - No exercício da 
profissão:
»Envolvimento na realização de Projeto de 
Sistemas Digitais.
 Projeto de Sistemas Digitais - Fases:
»Especificação: requisitos, escopo.
»Modelo: técnicas, métodos de implementação.
»Implementação: simulação, laboratório. 
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 50
3. Síntese de Circuitos Combinatórios
 Projeto de Sistemas Digitais - Necessidade 
de representação:
– Linguagem.
– Diagramas.
 Álgebra Booleana e Álgebra de 
Chaveamento - Aparecem como ferramenta 
aderente ao encaminhamento da solução 
desta classe de problemas. 
 Projeto de Sistemas Digitais - Envolve a 
atividade do Projeto Lógico Digital.
26
26
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 51
3. Síntese de Circuitos Combinatórios
 Projeto Lógico Digital:
– Atividade na qual o projetista de um sistema 
eletrônico digital cria circuitos analisando um 
problema e elaborando sua solução no nível 
conceitual dos Circuitos Lógicos.
 Circuitos Lógicos -
– Circuitos que existem apenas como Abstrações 
Matemáticas:
» Independentes do mundo físico da eletrônica digital;
» Constituídos de associações de Módulos Lógicos 
Funcionais.
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 52
3. Síntese de Circuitos Combinatórios
 Módulos Lógicos Funcionais:
– Associações de Portas Lógicas Fundamentais que 
realizam as Operações Lógicas Primitivas 
definidas na Álgebra de Chaveamento adotada.
 Realização de um Projeto Lógico Digital:
– É o projeto de uma Máquina Abstrata, ou 
Equipamento Matemático, onde as primitivas 
(tijolos da construção) são operações matemáti-
cas.
– O Circuito Lógico pode ser visto como uma 
associação (ou rede) de operadores matemáticos.
27
27
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 53
3. Síntese de Circuitos Combinatórios
Engenharia do Projeto Lógico Digital [Fregni-95]:
– Muda o enfoque do projeto - Parte do princípio de 
que a Finalidade de todo Circuito Lógico é ser 
Materializado em um Circuito Físico.
– Define: Módulos Matemáticos a serem utilizados.
– Estabelece Técnicas e Métodos de implementação.
– Define as Características Físicas do circuito final.
– Projetista usa a Intuição - A ação do Projetista 
deixa de ser exclusivamente mecanizada ou formal 
e este usa sua experiência como ferramenta.
– Projetar passa a ser uma Arte, com método científico! 
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 54
3. Síntese de Circuitos Combinatórios
 Objetivo: Obter a solução mais econômica!
 Solução mais econômica - Difícil de ser definida 
com precisão.
 Critérios possíveis:
– Minimização do número de literais da função de 
chaveamento.
– Minimização do número de interconexões entre 
as portas.
– Minimização do número de pinos do circuito 
integrado a ser eventualmente construído.
28
28
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 55
3.1. Síntese por Método Algébrico
O Teorema da Expansão de Shannon [I15] mostrou 
que pode-se decompor uma Expressão de Chavea-
mento fn(x1, x2, x3, ..., xn) em duas formas canôni-
cas: Soma de Produtos [“SP” - I15a] e
Produto de Somas [“PS” - I15b].
Ex. 3.1. f = x1.x2 + ~x2.x3 pode ser representada por:
f = x1.x2 .~x3 + x1.x2.x3 + x1.~x2.x3 + ~x1.~x2.x3 (SP)
ou por
f=(x1+x2 +x3).(x1+~x2+x3).(x1+~x2+~x3).(~x1+x2+x3) (PS)
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 56
3.1. Síntese por Método Algébrico
Usando a definição de mintermos e maxtermos:
f = x1.x2 .~x3 + x1.x2.x3 + x1.~x2.x3 + ~x1.~x2.x3 (SP)
f = m3 + m7 + m5 + m4 (SP)
f = .
ou
f=(x1+x2 +x3).(x1+~x2+x3).(x1+~x2+~x3).(~x1+x2+x3) (PS)
f= M0 . M2 . M6 . M1 (PS)
f = .
 )7,5,4,3(m
 )6,2,1,0(M
29
29
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 57
3.1. Síntese por Método Algébrico
Teorema 3.1.1 - Uma Expressão de Chaveamento 
do tipo fn(x1, x2, x3, ..., xn) pode ser expressa de 
maneira única como uma soma de mintermos ou 
um produto de maxtermos.
Teorema 3.1.2 - Se a Expressão de Chaveamento 
fn(x1, x2, x3, ..., xn) é expressa como uma soma 
de p mintermos então ela também é expressa co-
mo um produto de (2n - p) maxtermos.
, onde: i  j. 
 )2( pn
j
p
in Mmf
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 58
3.1. Síntese por Método Algébrico
 Síntese por Método Algébrico – Seja um 
sistema e uma especificação deste:
– O processo de síntese consiste na obtenção de 
uma Expressão de Chaveamento do tipo fn(x1, 
x2, x3, ..., xn), que represente o comportamento 
do sistema em questão.
 A especificação pode vir:
– Por meio de linguagem natural (uma descrição 
de seu comportamento lógico, por exemplo).
– Tabela da verdade.
30
30
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 59
3.1. Síntese por Método Algébrico
Exemplo3.1.1 - Sintetizar um circuito de 
chaveamento para detectar os códigos BCD 
correspondentes aos números ímpares.
x1
x3
x2
x4
Detector y
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 60
3.1. Síntese por Método Algébrico
x4 x3 x2 x1
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
~x4 . ~x3 . ~x2 . x1
y
0
0
0
0
0
1
1
1
1
1
~x4 . ~x3 . x2 . x1
~x4 . x3 . ~x2 . x1
~x4 . x3 . x2 . x1
x4 . ~x3 . ~x2 . x1
Soma Produtos Produto Somas
x4 + x3 + x2 + x1
x4 + x3 + ~x2 + x1
x4 + ~x3 + x2 + x1
x4 + ~x3 + ~x2 + x1
~x4 + x3 + x2 + x1
Exemplo 3.1.1
31
31
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 61
3.1. Síntese por Método Algébrico
Exemplo 3.1.1 - Soma de Produtos: y = ~x4.~x3.~x2.x1 + 
~x4.~x3.x2.x1+~x4.x3.~x2.x1+~x4.x3.x2.x1+x4.~x3.~x2.x1
y
x1
x2x3x4
x1
x2x3x4
x1
x2x3x4
x1
x2x3x4
x1
x2x3x4
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 62
3.1. Síntese por Método Algébrico
Ex3.1.1-Produto de Somas: y=(x4+x3+x2+x1).(x4+x3+~x2+x1) 
.(x4+~x3+x2+x1).(x4+~x3+~x2+x1).(~x4+x3+x2+x1)
y
x1
x2x3x4
x1
x2x3x4
x1
x2x3x4
x1
x2x3x4
x1
x2x3x4
32
32
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 63
3.2. Síntese por Mapa de Karnaugh
Um Mapa de Karnaugh pode ser considerado como 
uma representação modificada de uma Tabela da 
Verdade, em n dimensões. Consegue-se visualizar 
propriedades explícitas por meio de padrões e/ou 
estruturas que permitem simplificações nas fun-
ções de chaveamento, com complexidade de repre-
sentação proporcional ao número de variáveis.
Célula - É um mintermo ou um Maxtermo.
Células Adjacentes - Duas células são adjacentes quan-
do diferem apenas no valor de uma variável.
Adjacências - Grupamentos (retangulares ou quadrados) 
de 2n células adjacentes.
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 64
3.2. Síntese por Mapa de Karnaugh
Mapa de Karnaugh - Obtenção e interpretação 
para duas variáveis:
~x2
~x1 (0) (2)
(1) (3)
x2
x1
~x2
~x1
x2
x1
~x2 x2Conjunto Universal
f=~x2.~x1
x2
0 1x1
0
1
1
f=x2.~x1
x2
0 1x1
0
1
1
f=~x2.x1
x2
0 1x1
0
1 1
f=x2.x1
x2
0 1x1
0
1 1
Mintermos
33
33
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 65
3.2. Síntese por Mapa de Karnaugh
Mapa de Karnaugh - Interpretação das Leis de De 
Morgan para duas variáveis:
f=x2.x1
x2
0 1x1
0
1
x2
0 1x1
0
1 1
x2
0 1x1
0
1 11
1
f = ~(x2 . x1) = ~x2 + ~x1 = ~x2 + ~x1
1 1 1
x2
0 1x1
0
1
1
1
x2
0 1x1
0
1
11
f=x2+x1
x2
0 1x1
0
1
x2
0 1x1
0
1
x2
0 1x1
0
11
f= ~(x2 + x1) = ~x2 . ~x1 = ~x2 . ~x1
1 1
x2
0 1x1
0
1
1
1
x2
0 1x1
0
1
111
1
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 66
3.2. Síntese por Mapa de Karnaugh
Mapa de Karnaugh - Representação de alguns 
Conectivos Lógicos para duas variáveis:
x2 x2
0 1x1
0
1
1 1
1 1
Conjunto Universal f=x2ORx1
0 1x1
0
1
1
f=x2XORx1
0 1
1
f=x2ANDx1
0 1
111
1
0 1
1 1
1 1
Conjunto Universal f=x2NORx1
0 1
f=x2NXORx1
0 1
1
f=x2NANDx1
0 1
11 1 1
1
x2
x1
0
1
x2
x1
0
1
x2
x1
0
1
x2
x1
0
1
x2
x1
0
1
x2
x1
0
1
34
34
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 67
3.2. Síntese por Mapa de Karnaugh
Mapa de Karnaugh - Representação:
x1
0 1
(0) (1)
Uma variável
x2
0 1x1
0
1
(0) (2)
(1) (3)
Duas variáveis
x3x2
00 01 11 10x1
0
1
(0) (2) (6) (4)
(1) (3) (7) (5)
Três variáveis
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 68
3.2. Síntese por Mapa de Karnaugh
Mapa de Karnaugh - Representação:
Três variáveis: x3,x2,x1
x3x2
00 01 11 10x1
0
1
(0) (2) (6) (4)
(1) (3) (7) (5)
~x1
x1
x3~x2x3x2~x3x2~x3~x2
x3~x2x3x2
~x3x2 ~x3~x2~x1
x1
35
35
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 69
3.2. Síntese por Mapa de Karnaugh
Mapa de Karnaugh - Representação:
x4x3
00 01 11 10x2x1
00
01
11
10
(0) (4) (12) (8)
(1) (5) (9)(13)
(3) (7) (15)
(2) (6) (14)
(11)
(10)
Quatro variáveis
x4x3
00 01 11 10x2x1
00
01
11
10
x4x3
00 01 11 10 x2x1
00
01
11
10
(0) (4) (12) (8)
(1) (5) (9)(13)
(3) (7) (15)
(2) (6) (14)
(11)
(10)
(16) (20) (28) (24)
(17) (21) (25)(29)
(19) (23) (31)
(18) (22) (30)
(27)
(26)
x5 = 0 x5 = 1
Cinco variáveis
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 70
3.2. Síntese por Mapa de Karnaugh
Mapa de Karnaugh - Representação:
Quatro variáveis
x4x3
00 01 11 10x2x1
00
01
11
10
(0) (4) (12) (8)
(1) (5) (9)(13)
(3) (7) (15)
(2) (6) (14)
(11)
(10)
00 01 11 10
00
01
11
10
(0) (4) (12) (8)
(1) (5) (9)(13)
(3) (7) (15)
(2) (6) (14)
(11)
(10)
x3
x4
x1
x2
36
36
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 71
3.2. Síntese por Mapa de Karnaugh
Mapa de Karnaugh para Seis Variáveis:
x4x3
00 01 11 10x2x1
00
01
11
10
x4x3
00 01 11 10 x2x1
00
01
11
10
(0) (4) (12) (8)
(1) (5) (9)(13)
(3) (7) (15)
(2) (6) (14)
(11)
(10)
(16) (20) (28) (24)
(17) (21) (25)(29)
(19) (23) (31)
(18) (22) (30)
(27)
(26)
x5 = 0 x5 = 1
x4x3
00 01 11 10
00
01
11
10
x2x1
x4x3
00 01 11 10
00
01
11
10
x2x1
(32) (36) (44) (40)
(33) (37) (41)(45)
(35) (39)(47)
(34) (38) (46)
(43)
(42)
x6 = 0
x6 = 1
x6 = 0
x6 = 1
x5 = 0 x5 = 1
(48) (52) (60) (56)
(49) (57)
(51) (55) (63)
(50) (54) (62)
(59)
(58)
(53) (61)
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 72
Exercício 3.2.1 - Determinar o menor conjunto de adja-
cências que cubra (ou contenha) todos os mintermos das 
funções de três variáveis dadas:
3.2. Síntese por Mapa de Karnaugh
x3x2
00 01 11 10x1
0
1
1 1
1 1
0
0 0
0
x3x2
00 01 11 10x1
0
1
1 10
1 1
1
00
x3x2
00 01 11 10x1
0
1 1 10 0
1 10 0
37
37
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 73
3.2. Síntese por Mapa de Karnaugh
Exercício 3.2.2 - Determinar o menor conjunto de adja-
cências que cubra (ou contenha) todos os mintermos das 
funções de quatro variáveis dadas:
x4x3
00 01 11 10x2x1
00
01
11
10
1
1
1
1 1
1
1 1
0 0 0 0
0 0
0
0
x4x3
00 01 11 10x2x1
00
01
11
10
1
1
1
1
1
1
1
1
0 0
0 0
0
0
0 0
© Andrade, Corrêa, Gomie Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 74
3.2. Síntese por Mapa de Karnaugh
Cubo-r (“cubo de ordem r” ou “cubo erre”) - É o 
elemento básico em um Mapa de Karnaugh. Sua 
definição pode ser gerada de maneira indutiva:
Cubo-0: Em um Mapa de Karnaugh de n variáveis, 
uma entrada qualquer com “1” (isto é, uma célula 
ou um mintermo) é um Cubo-0.
Cubo-1: Em um Mapa de Karnaugh de n variáveis 
sejam dois Cubos-0 que diferem apenas no valor 
de uma variável (Cubos-0 adjacentes). As n-1 va-
riáveis em que dois Cubos-0 adjacentes são con-
cordantes definem um Cubo-1.
38
38
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 75
3.2. Síntese por Mapa de Karnaugh
Cubo-r - Analogia com representações geométricas 
de variáveis contínuas:
x10 1
x = 2,37
0 1 2 3x1
(2,37 ; 1,2)
0 1 2 3x1
x2
1
2
x1
(0,0) (0,1)
(1,0) (1,1)
x2
(x2,x1)Duas
variáveis
Uma
variável
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 76
3.2. Síntese por Mapa de Karnaugh
Cubo-r (r 1): Em um Mapa de Karnaugh de n 
variáveis sejam dois Cubos-(r-1) diferindo exa-
tamente no valor de uma variável (denominados 
Cubos-(r-1) adjacentes). As n-r variáveis em 
que dois Cubos adjacentes são concordantes 
definem um Cubo-r.
Cubo-r - Analogia com representações geométri-
cas de variáveis contínuas. Exemplo com a 
função:
)7,6,3,2,0(),,( 321 
p
in mxxxf
39
39
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 77
3.2. Síntese por Mapa de Karnaugh
x1(0,0,0)
x2
(0,0,1)
(1,1,0) (1,1,1)
x3
(0,1,0) (0,1,1)
(1,0,0)
(1,0,1)
m0 m1
m2 m3
m7m6
m5
m4
(x3,x2,x1)
Cubos-0 possíveis para uma 
função de três variáveis
Três variáveis
(2,37;1,2;2)
0 1 2 3x1
x2
11
2
2
x3
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 78
3.2. Síntese por Mapa de Karnaugh
Exemplo: Cubos-0 da 
função de três variáveis.
Exemplo: Cubos-1 da 
função de três variáveis.
(1,1,1)m7
(0,0,0)
(0,1,1)(0,1,0)
m0
m2 m3
(x3,x2,x1)
(1,1,0)m6
0,0,0
0,1,1
1,1,1
0,1,0
0,X,0
0, 1,X
X, 1,1
(x3,x2,x1)
1,1,0
X,1,0
1,1,X
40
40
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 79
3.2. Síntese por Mapa de Karnaugh
Exemplo: Cubo-2 da função de três variáveis.
Cubo-2
213321 ~~),,( xxxxxxfn 
0,X,0
0, 1,X
X, 1,1
(x3,x2,x1)
X,1,0
1,1,X
Cubo-1
)7,6,3,2,0(),,( 321 
p
in mxxxf
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 80
4. Minimização de Circuitos
No momento de simplificar-se um circuito é conve-
niente determinar uma topologia (ou formato) de 
circuito antes de definir-se o critério para o signi-
ficado de mais simples possível. Vejamos as im-
plementações de três formas distintas da seguinte 
função:
)14,13,10,9,6,5(
p
in mf
123123124124 ~~~~ xxxxxxxxxxxxfn 
)~~)(( 121234 xxxxxxfn 
41
41
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 81
4. Minimização de Circuitos
Qual é a forma mais simples (I)?
fn
x1x2x3x4
x1x2x3x4
x1x2x3x4
x1x2x3x4
x1x2x3x4
x1x2x3x4
m5
m6
m9
m10
m13
m14
(I)
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 82
4. Minimização de Circuitos
Qual é a forma mais simples (II e III)?
fn
(II) (III)
fn x4
x3
x2
x1
x2
x1
x1x2x4
x1x2x4
x1x2x3
x1x2x3
42
42
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 83
4.1. Implicantes Primários
Implicante Primário: Um Cubo é um IP –
implicante primário – se ele não estiver 
incluído em nenhum outro Cubo de ordem 
superior.
Uma função de chaveamento pode ser representada 
por uma soma de todos os seus implicantes primá-
rios. Esta representação especial em Soma de Pro-
dutos é denominada Soma Completa.
Tal representação não é necessariamente a função de 
chaveamento minimizada, porém é um passo 
importante para a minimização.
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 84
4.1. Implicantes Primários
Implicante Primário Essencial: Seja Ipj um 
implicante primário e seja fn uma função 
expressa na forma da soma de todos os seus 
Ipi. Ipj é um Implicante Primário Essencial
(IPE) se Ipj contiver um cubo qualquer não 
contido na somatória dos Ipi.
Os IPEs deverão estar presentes em uma realização 
mínima para fn. Se estes IPEs cubrirem fn total-
mente então o problema de minimização está con-
cluído.
43
43
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 85
4.1.1. Tabela de Cobertura
Tabela de Cobertura: Se ocorrer o caso 
de que os IPE’s não cubram fn totalmen-
te, então deve-se usar algum procedi-
mento que permita descobrir os IP’s 
(dentre os não essenciais), que façam 
parte da expressão mínima:
Expressão Mínima = 
= IPE1 + IPE2 + … + IPEn + [(Demais Implicantes)]
Um destes procedimentos denomina-se 
Tabela de Cobertura.
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 86
4.1.1. Tabela de Cobertura
Considere-se o exemplo de uma função definida por 
seu Mapa de Karnaugh, onde o custo (k) é igual ao 
número de Literais do IP. Para descobrir os demais 
implicantes realiza-se um processo de redução da 
Tabela de Cobertura:
1-) Por meio da eliminação das células já cobertas por 
IPE’s;
2-) Encontrando-se implicantes de menor custo (k) 
possível e que cobrem o maior número de células. 
Diz-se que estes implicantes dominam os demais.
44
44
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 87
4.1.1. Tabela de Cobertura
Exemplo – Função dada por seu Mapa de Karnaugh:
IPE’s:
IPE1 = ~x4.x1
IPE2 = x4.~x3.~x1
x
4
x
3
00 01 11 10x2
x
1
00
01
11
10
1
0
1
1
0
1
0 1
0 0
1
1
0 0
11
IPE1
IPE2
*: Células não
cobertas por 
nenhum outro 
cubo que seja o
maior possível.
x
4
x
3
00 01 11 10x2
x
1
00
01
11
10
1
0
1*
1
0
1*
0 1
0 0
1
1*
0 0
11
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 88
4.1.1. Tabela de Cobertura
Todos os IP’s:
IPE’s:
IP1 = IPE1 = ~x4.x1
IP2 = IPE2 = x4.~x3.~x1
Demais IP’s:
IP3 = ~x4.~x3.~x2
IP4 = ~x3.~x2.~x1
IP5 = x3.~x2.x1
IP6 = x4.x3.~x2
IP7 = x4.~x2.~x1
IP1=IPE1 IP2=IPE2
x
4
x
3
00 01 11 10x2
x
1
00
01
11
10
1
0
1*
1
0
1*
0 1
0 0
1
1*
0 0
11
IP7
IP3 IP6
IP4
IP5
45
45
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 89
4.1.1. Tabela de Cobertura
Tabela de Cobertura- Para aplicação do processo de redução:
Obs: Lembrar que o custo (k) é igual ao número de Literais do Implicante.
IP1=IPE1
IP2=IPE2
IP7
IP3
IP6
IP4
IP5
0Implicantes
X
1 3 5 7 8 Custo(k)1012 13
X X X 2
3
3
3
3
3
3
X X
X X
X X
X X
X X
XX
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 90
4.1.1. Tabela de Cobertura
Tabela de Cobertura - Após processo de redução: 
fmín = IP1 + IP2 + IP3 + IP6
OU
IP1 + IP2 + IP4 + IP6
(k=2+3+3+3=11)
(k=2+3+3+3=11)
IP7
IP3
IP6
IP4
IP5
0Implicantes Custo(k)12 13
3
3
3
3
3
X
X X
X
X
X
IP6
domina
IP5
e IP7
IP3 e IP4
são
indiferentes
(k e m0 iguais)
46
46
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 91
4.2 Minimização pelo Método Tabular
Exemplo: Procedimento de extração dos Implican-
tes Primários pelo método tabular. Dada a 
Função:
)15,12,10,8,7,5,4,2,0(
p
in mf
x4x3
00 01 11 10x2x1
00
01
11
10
1 1 1 1
1
1
1 1
1
x4x3
00 01 11 10x2x1
00
01
11
10
(0) (4) (12) (8)
(1) (5) (9)(13)
(3) (7) (15)
(2) (6) (14)
(11)
(10)
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 92
4.2 Minimização pelo Método Tabular
Passo 1 -Listam-se os mintermos de fn com a nota-
ção Cubo-0 correspondente (Ex:m7=~x4x3x2x1).
Agrupam-se os Cubos-0 de modo que:
– No primeiro grupo todos possuam zero 1’s.
– No segundo grupo todos possuam um 1, etc.
Identificam-se pares de Cubos-0 compatíveis, isto é, 
que exista um Cubo-1 que os contenha. 
Define-se uma operação entre Cubos-0 compatíveis 
para gerar o Cubo-1 que os contém. Os Cubos-0 
são marcados com “” e os Cubos-1 gerados 
colocados em outra tabela para o passo 2.
47
47
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 93
4.2 Minimização pelo Método Tabular
Exemplo – Método Tabular de extração dos 
Implicantes Primários :
Passo 1
0 0 0 0
x4 x3 x2 x1
(0)
(4)
(12)
(8)
(5)
(7)
(15)
(2)
(10)
0 0 1 0
0 1 0 0
1 0 0 0
0 1 0 1
1 0 1 0
1 1 0 0
0 1 1 1
1 1 1 1









© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 94
4.2 Minimização pelo Método Tabular
Passo 2 - Os Cubos-1 gerados pelo Passo 1 são 
agrupados, de maneira que os elementos do pri-
meiro grupo possuem zero 1’s, os do segundo 
grupo um 1, etc. É utilizado o mesmo procedi-
mento de operação entre Cubos-1 para gerar 
Cubos-2 para o passo 3.
Passo 3 - O procedimento é análogo aos anterio-
res. Como não são gerados Cubos-3 para este 
exemplo termina-se o algoritmo de geração de 
Implicantes Primários.
48
48
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 95
4.2 Minimização pelo Método Tabular
Exemplo - Método Tabular de extração dos Implicantes 
Primários:
Passo 2
0 0 - 0
x4 x3 x2 x1
(0,2)
(2,10)
0 - 0 0
- 0 0 0
- 0 1 0
0 1 0 -
- 1 0 0
1 0 - 0
1 - 0 0
0 1 - 1
(7,15) - 1 1 1
(0,4)
(0,8)
(5,7)
(8,12)
(4,5)
(4,12)
(8,10)
Passo 3
- 0 - 0
x4 x3 x2 x1
(0,2,8,10)
- - 0 0(0,4,8,12)
f = ~x4x3~x2 + ~x4x3x1 + x3x2x1 +
+ ~x3~x1 + ~x2~x1







IPE1IPE2
IPE3IP4IP5
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 96
4.2 Minimização pelo Método Tabular
Verificar se há necessidade dos termos (4,5) ou 
(5,7) dado que:
– 4  (0,4,8,12) e 5  (5,7).
Ou outra maneira de ver é que:
– 5  (4,5) e 7  (7,15).
f = ~x4x3~x2 + ~x4x3x1 + x3x2x1 + ~x3~x1 + ~x2~x1
(4,5) (5,7) (7,15) (0,2,8,10) (0,4,8,12)
IPE1IPE2IPE3IP4IP5
49
49
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 97
4.2 Minimização pelo Método Tabular
fmín = ~x4x3x1 + x3x2x1 + ~x3~x1 + ~x2~x1
x
4
x
3
00 01 11 10x
2
x
1
00
01
11
10
0
7
5
8
10*
4 12*
15*
IPE2
(0,2*,8,10*)
2*
IPE1
(0,4,8,12*)
IPE3
(7,15*)
IP4
(5,7)
IP5
(4,5)
IPE1IPE2IPE3IP4
fmín = ~x4x3~x2 + x3x2x1 + ~x3~x1 + ~x2~x1
OU
IPE1IPE2IPE3IP5
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 98
4.3 Mapas de Karnaugh Considerando-se os Zeros das Funções
Até o momento identificamos Adjacências –
isto é, grupamentos (retangulares ou quadra-
dos) de 2n células (mintermos) adjacentes, 
para as quais o valor da Função é 1.
Pode-se identificar outro tipo de Adjacências
– isto é, grupamentos (retangulares ou qua-
drados) de 2n células (Maxtermos) adjacen-
tes, para as quais o valor da Função é 0.
50
50
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 99
4.3 Mapas de Karnaugh Considerando-se os Zeros das Funções
Exemplos:
x4x3
00 01 11 10x2x1
00
01
11
10
0
0
1
1
0
1
1
1
0 1
1 1
1
1
1 1
x2
x4
f = x2 + x4
Realmente, considerando-se os uns chega-se ao 
mesmo valor.
x4x3
00 01 11 10x2x1
00
01
11
10
1
1
1
0
0
1
1
1
1 1
0 1
0
1
1 1
~x1
f = ~x1 + ~x3
~x3
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 100
4.3 Mapas de Karnaugh Considerando-se os Zeros das Funções
Dicas: 1-) Constrói-se o Mapa de Karnaugh
de ~f; 2-) Escreve-se a expressão de ~f, 
considerando-se os uns (mintermos); 3-) 
Complementa-se ~f, obtendo-se f.
Na prática nem se chega a construir 
o Mapa de ~f, define-se o Mapa 
de f considerando-se os Zeros
(Maxtermos); Lembrar que os 
Maxtermos, identificados por 
seus índices, estão nas mesmas 
posições que os mintermos.
x4x3
00 01 11 10x2x1
00
01
11
10
(0) (4) (12) (8)
(1) (5) (9)(13)
(3) (7) (15)
(2) (6) (14)
(11)
(10)
Maxtermos
M0=x4 + x3 + x2 + x1
51
51
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 101
4.3 Mapas de Karnaugh Considerando-se os Zeros das Funções
Exercício – Considerando-se os Zeros das Funções, 
determinar a expressão de chaveamento das 
seguintes funções:
x4x3
00 01 11 10x2x1
00
01
11
10
0
1
0
1
1
0
1
0
1 1
1 1
1
1
1 1
x4x3
00 01 11 10x2x1
00
01
11
10
1
0
1
1
0
1
0
1
1 1
1 1
0
1
1 1
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 102
4.4 Funções Incompletamente Definidas
Funções Incompletamente Definidas – São 
aquelas que, por razões diversas, tem o do-
mínio de interesse de respostas menor que o 
conjunto de combinações de todas suas en-
tradas. São funções para as quais não impor-
ta (Don’t Care - X) que, para algumas com-
binações de entradas, a saída possa valer 0 
ou 1 (X).
Pode-se tirar proveito deste grau de liberdade 
escolhendo-se o valor mais adequado de X
para se obter a expressão mínima possível. 
52
52
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 103
4.4 Funções Incompletamente Definidas
Funções Incompletamente Definidas – Exemplo:
 Quer-se sintetizaro Circuito2 de maneira que:
x1

f1
fn
f2
Circuito2
x2
x3
x3
x2
)7,6,4,3,1(mf
p
in 
 Observa-se que a função f1=x3.x2 já foi fornecida, 
e que fn=f1+f2.
 Por meio dos Mapas de Karnaugh faz-se a análise 
de quais mintermos podem ser don’t care (X).
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 104
4.4 Funções Incompletamente Definidas
 Pode-se ver que a função f2 deverá fornecer 1’s nas 
posições m1, m3 e m4, e não importa seu valor 
lógico (1 ou 0) nas posições m6 e m7 (onde foi 
anotado um X). Procura-se a melhor distribuição de 
0’s e 1’s para os X’s, de maneira que se obtenha a 
menor expressão de chaveamento.
+
x1
0 1x3x2
00
01
11
10
(0) (1)
(2) (3)
(6) (7)
(4) (5)
x1
0 1x3x2
00
01
11
10
1
1
1 1
1
=
x1
0 1x3x2
00
01
11
10
1 1
x1
0 1x3x2
00
01
11
10
1
1
X X
1
)]}7,6(X)4,3,1(m[f{)}7,6(mf{)7,6,4,3,1(mf
p
i
p
i2
p
i1
p
in 
fn f1 f2
53
53
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 105
4.4 Funções Incompletamente Definidas
 Para sintetizar a soma mínima é preciso:
1. Marcar os Implicantes Primários (IP’s) considerando-
se as células X’s como se tivessem valor 1;
2. Eliminar os IP’s que cubram apenas células X’s e 
apagar os X’s do Mapa de Karnaugh;
3. Eliminar IP’s contidos em outros deixando apenas os 
IP’s Essenciais (IPE’s).
1 2 3x1
0 1x3x2
00
01
11
10
1
1
X X
1
x1
0 1x3x2
00
01
11
10
1
1
1
x1
0 1x3x2
00
01
11
10
1
1
1
1
x1.~x3
~x1.x3
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 106
4.4 Funções Incompletamente Definidas
Funções Incompletamente Definidas – Exemplo:
 Por meio da análise de quais mintermos podem ser 
Don’t Care (X) nos Mapas de Karnaugh e a 
aplicação de técnicas de minimização conhecidas 
(identificação do Implicantes primários Essenciais 
– IPE’s) pode-se sintetizar o Circuito2:
x1

f1
fn
f2
Circuito2
x2
x3
x3
x2
54
54
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 107
5. Exemplos de Aplicação: 5.1. Somador
1-) Análise – Fornece-se o circuito lógico e pede-se 
para extrair a Expressão Algébrica e a Tabela da 
Verdade, interpretando-se suas Funções de 
Engenharia.
2-) Síntese:
a.) Pela Função de Engenharia – A partir da espe-
cificação funcional vão sendo desenvolvidos os 
módulos constituintes dos sistema.
b.) Por Mapa de Karnaugh – O funcionamento do 
circuito é especificado por uma Tabela da 
Verdade, da qual, por Mapa de Karnaugh, são 
extraídas as expressões algébricas .
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 108
5. Exemplos de Aplicação: 5.2. Half Adder Full Adder
x y c s
1 1 1 0
1 0 0 1
0 1 0 1
0 0 0 0
s
c
x
y
“Half Adder” - Equivale a um circuito 
“meio-somador” de dois dígitos binários.
55
55
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 109
5. Exemplos de Aplicação:
5.2. Meio Somador - Somador Completo
xi
yi
ci
ci+1
s
Meio Somador
sint
cint
x
y
Meio Somador
sint
cint
x
y
Somador Completo
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 110
5. Exemplos de Aplicação:
5.3. Soma de Dois Números
M = x3x2x1 N = y3y2y1
Meio
Somador
Somador
Completo
x1
x2
y1
y2
x3
y3
Somador
Completo
s
c
s
c
s
c
z1
z2
z3
z4
56
56
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 111
Bibliografia
Dias, Francisco José de Oliveira; “Introdução aos circuitos 
de Chaveamento”; Apostila, PEL/EPUSP, 1.989.
Ercegovac, Milos D.; Lang, Tomás; “Digital Systems and 
Hardware/Firmware Algorithms”; John Wiley, 1.985.
Fernández, Gregório; Saez Vacas, Fernando; 
“Fundamentos de Informática”, Alianza Editorial, 
Colección Alianza Informática, 1.987.
Fregni, Edson; Saraiva, Antônio Mauro; “Engenharia do 
Projeto Lógico Digital”, Editora Edgard Blucher, 1.995.
Gersting, Judith L.; “Fundamentos Matemáticos Para a 
Ciência da Computação”, LTC - Livros Técnicos e 
Científicos Editora S. A., 1.995.
© Andrade, Corrêa, Gomi e Margi 2.013 < Análise e Síntese de Circuitos Combinatórios > PCS 2215 Sistemas Digitais I 112
Bibliografia
Guerra Vieira, Antônio Hélio; Dias, Francisco José de 
Oliveira “Notas de Aula de PEL 213 - Circuitos de 
Chaveamento”, Apostila, EPUSP, 1.979.
Hill, Frederic and Peterson, Gerald; “Introduction To 
Switching Theory and Logical Design”, John Wiley Sons, 
1.974.
Mendelson, Elliott; “Álgebra Booleana e Circuitos de 
Chaveamento”, Coleção Schaum, Editora McGraw-Hill, 
1.977.
Ranzini, Edith; Fregni, Edson; “Notas de Aula de PCS 214 -
Teoria da Comutação: Introdução aos Circuitos Digitais”, 
Apostila, EPUSP, 1.996.
Tremblay, J. P. and Monohar, R.; “Discrete Mathematical 
Structures With Applications to Computer Science”, 
McGraw-Hill, 1.975.