aula1 OK

Prévia do material em texto

Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
“Circuitos Digitais”
Algebra Booleana e Func¸o˜es Lo´gicas
Prof Daniel Chaves
Universidade Federal Fluminense/PURO - Departamento de Computac¸a˜o
2º Semestre, 2011
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Aula
1 A´lgebra Booleana
2 Diagrama de Venn Para Representac¸a˜o de Postulados e
Teoremas
3 Princı´pios e Teoremas
4 Func¸o˜es Booleanas
5 Ana´lise de Circuitos Digitais
6 Sı´ntese de Circuitos Digitais
7 Sı´ntese de Circuitos Digitais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Elementos da a´lgebra booleana
Definic¸a˜o
Uma a´lgebra booleana e´ um sistema alge´brico fechado contendo um
conjunto K de dois ou mais elementos e os dois operadores · e +;
alternativamente, para todo a e b em K , a · b pertence a K e a + b
tambe´m pertence a K (“+” e´ chamado de OR e “·” e´ chamado de
AND).
Existeˆncia dos elementos 1 e 0
Existem elementos u´nicos 1 (UM) e 0 (ZERO) no conjunto K tal que
para todo a ∈ K
a + 0 = a,
a · 1 = a,
onde 0 e´ o elemento identidade para operac¸a˜o + e 1 e´ o elemento
identidade para operac¸a˜o ·
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Elementos da a´lgebra booleana
Comutatividade das operac¸o˜es + e ·
Para todo a,b ∈ K
a + b = b + a,
a · b = b · a.
Associatividade das operac¸o˜es + e ·
Para todo a,b, c ∈ K
a + (b + c) = (a + b) + c,
a · (b · c) = (a · b) · a.
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Elementos da a´lgebra booleana
Distributividade de + sobre · e · sobre +
Para todo a,b ∈ K
a + (b · c) = (a + b) · (a + c),
a · (b + c) = (a · b) + (a · c).
Existeˆncia do complemento
Para todo a ∈ K existe um u´nico elemento chamado a¯
(complemento de a) em K tal que
a + a¯ = 1,
a · a¯ = 0.
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Simplificando a Notac¸a˜o
Omitindo notac¸a˜o para simplificando a representac¸a˜o
Na exposic¸a˜o que segue iremos omitir o sinal · referente a
operac¸a˜o AND, assim
a + b · c = (a + b) · (a + c)
a + bc = (a + b)(a + c)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Analisando os Conceitos - Diagrama de Venn
O diagrama de Venn
Disponibiliza um me´todo gra´fico para interpretar os postulados.
O que e´ possı´vel pela a´lgebra de conjuntos ser uma a´lgebra
booleana na qual:
Os conjuntos correspondem a elementos de K
A operac¸a˜o intersec¸a˜o ∩ corresponde a operac¸a˜o AND “·”
A operac¸a˜o unia˜o ∪ corresponde a operac¸a˜o OR “+”
Os elementos agora sa˜o interpretados como conjunto fechados
conectados em nosso diagrama de Venn
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Analisando os Conceitos - Diagrama de Venn
Algumas representac¸o˜es empregando diagrama de Venn
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Analisando os Conceitos - Diagrama de Venn
Distributividade
a+ (b · c) = (a+ b) · (a+ c),
a · (b + c) = (a · b) + (a · c).
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Analisando os Conceitos - Diagrama de Venn
Distributividade
a+ (b · c) = (a+ b) · (a+ c),
a · (b + c) = (a · b) + (a · c).
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Analisando os Conceitos - Diagrama de Venn
Distributividade
a+ (b · c) = (a+ b) · (a+ c),
a · (b + c) = (a · b) + (a · c).
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Analisando os Conceitos - Diagrama de Venn
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Princı´pio da Dualidade
Princı´pio da Dualidade
Se uma expressa˜o e´ va´lida em uma a´lgebra booleana, a
expressa˜o dual tambe´m e´ va´lida.
Obtendo o dual
A expressa˜o dual e´ obtida substituindo os operac¸o˜es +
por ·, as operac¸o˜es · por +, todos os 1’s por 0’s, e todos os
0’s por 1’s
A localizac¸a˜o dos pareˆnteses na˜o deve ser alterada
Exemplo
a + (bc) = (a + b)(a + c)⇒ a(b + c) = ab + ac
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Teoremas Fundamentais da A´lgebra Booleana
Premissas
Nos teoremas que seguem, as letras a,b, c, ... representam
elementos da a´lgebra booleana
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Teoremas Fundamentais da A´lgebra Booleana
Idempotente
a + a = a
a · a = a
Elementos nulos para + e ·
a + 1 = 1
a · 0 = 0
Involuc¸a˜o
¯¯a = a
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Teoremas Fundamentais da A´lgebra Booleana
Absorc¸a˜o
Na˜o ha´ similar no sistema alge´brico convencional
a + ab = a,
a · (b + a) = a.
Exercı´cio: Visualizar empregando Diagrama Venn
Exemplos
(X + Y ) + (X + Y )Z = X + Y
AB¯(AB¯ + B¯C) = AB¯
AB¯C + B¯ = B¯
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Teoremas Fundamentais da A´lgebra Booleana
Propriedades dos elementos 0 e 1
OR AND COMPLEMENTO
a + 0 = a a · 0 = 0 0¯ = 1
a + 1 = 1 a · 1 = a 1¯ = 0
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Teoremas Fundamentais da A´lgebra Booleana
Eliminando elementos extras
a + a¯b = a + b
a(a¯ + b) = ab
Exemplos
B + AB¯C¯D = B + AC¯D
Y¯ (X + Y + Z ) = Y¯ (X + Z )
(X + Y )((X + Y ) + Z ) = (X + Y )Z
AB + (AB)CD¯ = AB + CD¯
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Teoremas Fundamentais da A´lgebra Booleana
Eliminando elementos extras
ab + ab¯ = a
(a + b)(a + b¯) = a
Exemplos
ABC + AB¯C = AC
(AD + B + C)(AD + (B + C)) = AD
Exercı´cio
(W¯ +X¯ +Y¯ +Z¯ )(W¯ +X¯ +Y¯ +Z )(W¯ +X¯ +Y +Z¯ )(W¯ +X¯ +Y +Z )
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Teoremas Fundamentais da A´lgebra Booleana
Eliminando elementos extras
ab + ab¯c = ab + ac
(a + b)(a + b¯ + c) = (a + b)(a + c)
Exemplos
xy + xy¯(w¯ + z¯) = xy + x(w¯ + z¯)
(x¯ y¯ + z)(w + x¯ y¯ + z¯) = (x¯ y¯ + z)(w + x¯ y¯)
(A¯ + B¯ + C¯)(B¯ + C)(A + B¯) = B¯
wy¯ + wx¯y + wxyz + wxz¯ = w
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Teoremas Fundamentais da A´lgebra Booleana
Teorema de DeMorgan
a + b = a¯ · b¯
a · b = a¯ + b¯
Generalizac¸a˜o
a1 + a2 + . . . + an = a¯1 · a¯2 · . . . · a¯n
a1 · a2 · . . . · an = a¯1 + a¯2 + . . . + a¯n
Exemplos
a + bc = a¯b¯ + a¯c¯
X + Y¯ = X¯ · Y
a(b + z(x + a¯)) = a¯ + b¯(z¯ + x¯)
a(b + c) + a¯b = b¯(a¯ + c¯)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Teoremas Fundamentais da A´lgebra Booleana
Teorema de DeMorgan
Se X = a + b, enta˜o X¯ = (a + b). Como X · X¯ = 0 e X + X¯ = 1. Se
X · Y = 0 e X + Y = 1, enta˜o Y = X¯ ja´ que o complemento de X e´
u´nico. Portanto, fazendo Y = a¯b¯ podemos provar o teorema testando
X · Y e X + Y
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Teoremas Fundamentais da A´lgebra Booleana
Teorema do Consenso
ab + a¯c + bc = ab + a¯c
(a + b)(a¯ + c)(b + c) = (a + b)(a¯ + c)
Exemplos
AB + A¯CD + BCD = AB + A¯CD
(a + b¯)(a¯ + c)(b¯ + c) = (a + b¯)(a¯ + c)
ABC + A¯D + B¯D + CD = ABC + A¯D + B¯D
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Suma´rio
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
A´lgebra booleana bina´ria K = {0, 1}
Os postulados apresentados sa˜o gerais, para um conjunto K com
nu´mero arbitra´rio de elementos. Nos concentraremos no caso
bina´rio, por ser o adequado para o modelamento de circuitos de
chaveamento
Func¸a˜o booleana
Sejam X1,X2, . . . ,Xn varia´veis booleanos, ou seja, podem assumir os
valores 0, 1. Empregaremos a notac¸a˜o f (X1,X2,. . . ,Xn) para
representar uma func¸a˜o booleana nas varia´veis X1,X2, . . . ,Xn. Se C
e´ o conjunto possı´vel de n-u´plas bina´rias, enta˜o f : C → {0, 1}.
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Possı´veis func¸o˜es booleanas com n varia´veis
Como ha´ n varia´veis booleanos, cada uma pode assumir os valores
{0, 1}, logo ha´ um total de 2n combinac¸o˜es. Para cada n-u´pla de 0′s
e 1′s podemos associar os valores {0, 1}, portanto, com n varia´veis
temos um total de 22
n
Possı´veis func¸o˜es com n = 0, 1
Para n = 0 (func¸o˜es constantes)
f0 = 0 f1 = 1
Para n = 1
f0 = 0 f2 = A
f1 = A¯ f3 = 1
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Possı´veis func¸o˜es com n = 2
Representac¸a˜o geral
fi(A,B) = i3AB + i2AB¯ + i1A¯B + i0A¯B¯,
onde (i)10 = (i3i2i1i0)2
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Representac¸a˜o similar
Listando todas as possı´veis expresso˜es booleanas
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Valor da func¸a˜o em uma n-u´pla especı´fica
Para A = 1, B = C = 0, determinamos o valor de
f (A,B,C) = AB + A¯C + AC¯
empregando os teoremas e postulados da a´lgebra booleana
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Tabela Verdade - Representac¸a˜o equivalente
Determinac¸a˜o do valor da func¸a˜o booleana para todas as possı´veis
combinac¸o˜es de valores de entrada, listadas em forma de tabela
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Tabela Verdade - Representac¸a˜o equivalente
Podendo ser empregado ca´lculo proposicional, onde os atoms sa˜o
as varia´veis booleanas, com ∨ ∼ OR, ∧ ∼ AND e ¬ ∼ complementar
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Tabela Verdade - Analisando func¸o˜es booleanas
Seja a func¸a˜o booleana
f (A,B,C) = AB + A¯C + AC¯
podemos determina-la em cada valor do seu domı´nio empregando
tabela verdade
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Forma SOP
Soma de Produto (SOP): Construı´do pela soma (OR) de termos
produto (AND). Cada termo produto e´ formado por varia´veis
complementadas ou na˜o complementadas (chamadas de literais)
f (A,B,C,D) = AB¯C + B¯D¯ + A¯CD¯
Forma POS
Produto de Soma (POS): Construı´do pelo produto (AND) de termos
soma (OR). Cada termo soma e´ formado pela forma complementada
ou na˜o complementadas de literais
f (A,B,C,D) = (A¯ + B + C)(B¯ + C + D¯)(A + C¯ + D)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Forma canoˆnicas SOP e POS
Soma de Especificam formas u´nicas para representac¸a˜o de uma
func¸a˜o, ou seja, func¸o˜es com representac¸o˜es canoˆnicas diferentes
sa˜o diferentes. As seguintes representac¸o˜es sa˜o de uma mesma
func¸a˜o?
f (a,b, c) = ab + a¯c + bc
f (a,b, c) = abc + abc¯ + a¯c + bc + a¯bc
Forma canoˆnicas SOP - Mintermos
Mintermo:Para uma func¸a˜o com n varia´veis, o termo produto contem
cada um dos literais em sua forma complementada ou na˜o comple-
mentada
Forma canoˆnica: Todos os termos produto sa˜o mintermos
f (A,B,C) = A¯BC¯ + ABC¯ + A¯BC + ABC
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Codificac¸a˜o de mintermos
Empregado na simplificac¸a˜o da representac¸a˜o de func¸o˜es
booleanas, pela codificac¸a˜o dos mintermos pelo valor nume´rico (em
bina´rio) no qual o mintermo assume o valor “1” (varia´veis
complementadas devem assumir o valor “0” e na˜o complementadas
o valor “1”)
Varia´veis na˜o complementadas 1
Varia´veis complementadas 0
Para o co´digo fazer sentido (ser bem definido) o ordem das varia´veis
dos mintermos deve ser estabelecida e mantida para todos os
mintermos
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
f (A,B,C) = m2 + m3 + m6 + m7
Na forma de lista
f (A,B,C) =
∑
m(2, 3, 6, 7)
Especificando as formas: Representac¸a˜o SOP canoˆnica, por
mintermos, por lista de mintermos
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
A ordem das varia´veis
A ordem das varia´veis estabelecida no processo de codificac¸a˜o dos
mintermos interfere na representac¸a˜o. Consideremos os
representac¸o˜es SOP canoˆnicas equivaleˆntes
fα(A,B,C) = A¯BC¯ + ABC¯ + A¯BC + ABC
fβ(B,C,A) =
∑
m(2, 3, 6, 7) = A¯B¯C + AB¯C + A¯BC + ABC
A ordem dos literais na representac¸a˜o da func¸a˜o, definem a ordem
dos literais no processo de codificac¸a˜o
fβ(A,B,C) =
∑
m(1, 3, 5, 7)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Forma imediata para determinac¸a˜o da tabela verdade
A func¸a˜o so´ assume valores “1” para as sequeˆncias bina´rias
que codificam os mintermos empregados em sua
representac¸a˜o (considerando a ordem do co´digo)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Lista de mintermos - A func¸a˜o e seu complemento
O complementar de uma func¸a˜o assume valores “1” nas sequeˆncias
onde a func¸a˜o assume o valor zero, e vice-verc¸a. Assim,
f (X1, . . . ,Xn) · f¯ (X1, . . . ,Xn) = 0 e f (X1, . . . ,Xn) + f¯ (X1, . . . ,Xn) = 1.
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Forma imediata para determinac¸a˜o da tabela verdade
A func¸a˜o so´ assume valores “1” para as sequeˆncias bina´rias
que codificam os mintermos empregados em sua
representac¸a˜o (considerando a ordem do co´digo)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Exemplo
Considerar a func¸a˜o
f (A,B,C,D) = A¯B¯C¯D¯ + A¯B¯C¯D + A¯BCD¯ + A¯BCD
Determine a lista de mintermos para a complementar
f¯ (A,B,C,D).
Exercı´cio
Determine a lista de mintermos associado a expressa˜o
AB + AB
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Forma canoˆnicas POS - Maxtermos
Maxtermos:Para uma func¸a˜o com n varia´veis, o termo soma contem
cada um dos literais em sua forma complementada ou na˜o comple-
mentada
Forma canoˆnica: Todos os termos soma sa˜o maxtermos
f (A,B,C) = (A + B + C)(A + B + C¯)(A¯ + B + C)(A¯ + B + C¯)
forma canoˆnica com quatro maxtermos
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Codificac¸a˜o de maxtermos
Empregado na simplificac¸a˜o da representac¸a˜o de func¸o˜es
booleanas, pela codificac¸a˜o dos maxtermos pelo valor nume´rico (em
bina´rio) no qual o mintermo assume o valor “0” (varia´veis
complementadas devem assumir o valor “1” e na˜o complementadas
o valor “0”)
Varia´veis na˜o complementadas 0
Varia´veis complementadas 1
Para o co´digo fazer sentido (ser bem definido) o ordem das varia´veis
dos maxtermos deve ser estabelecida e mantida para todos os
maxtermos
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
f (A,B,C) = (A + B + C)(A + B + C¯)(A¯ + B + C)(A¯ + B + C¯)
f (A,B,C) = M0 + M1 + M4 + M5
Na forma de lista
f (A,B,C) =
∏
M(0, 1, 4, 5)
Especificando as formas: Representac¸a˜o POS canoˆnica, por
maxtermos, por lista de maxtermos
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Forma imediata para determinac¸a˜o da tabela verdade
A func¸a˜o so´ assume valores “0” para as sequeˆncias bina´rias
que codificam os maxtermos empregados em sua
representac¸a˜o (considerando a ordem do co´digo)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´nteseSı´ntese
Func¸o˜es Lo´gicas
Relac¸a˜o entre lista de mintermos e maxtermos
Considerando-se func¸o˜es definidas sobre treˆs varia´veis
booleanas, trata-se da mesma func¸a˜o?∑
m(2, 3, 6, 7) =
∏
M(0, 1, 4, 5)
Exercı´cio
Definida a func¸a˜o
f (A,B,C) = (A + B + C¯)(A + B¯ + C¯)(A¯ + B + C¯)(A¯ + B¯ + C¯),
construir a tabela verdade da func¸a˜o, expressando-a atrave´s
de sua lista de mintermos e maxtermos
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Relac¸a˜o mintermos e maxtermos
Para um mesmo co´digo, os mintermos e maxtermos sa˜o iguais
a na˜o ser pela substituic¸a˜o de “·” por “+” e “+” por “·”, de
complementado para na˜o complementado, e por fim, de na˜o
complementado para complementado
m¯1 = A¯B¯C = A + B + C¯ = M1
e vice-verc¸a. Portanto,
m¯i = Mi
M¯i = ¯¯mi = mi
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Exercı´cio
Determinar a relac¸a˜o entre as listas de maxtermos da func¸a˜o
f (A,B,C) e seu complemento
f (A,B,C) =
∏
M(1, 3, 5, 7)
Observe que,
f (A,B,C) · f¯ (A,B,C) = 0
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Determinando a forma canoˆnica - Teorema da expansa˜o de
Shannon
f (x1, x2, . . . , xn) = x1 · f (1, x2, . . . , xn) + x¯1 · f (0, x2, . . . , xn)
f (x1, x2, . . . , xn) = [x1 + f (0, x2, . . . , xn)] · [x¯1 + f (1, x2, . . . , xn)]
Exercı´cio
Converter a func¸a˜o a seguir para forma canoˆnica SOP
f (A,B,C) = AB + AC¯ + A¯C
Exercı´cio
Converter a func¸a˜o a seguir para forma canoˆnica POS
f (A,B,C) = A(A + C¯)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Func¸o˜es Lo´gicas
Func¸a˜o na˜o completamente especificada
Algumas sequencias de entra nunca ocorrem. Portanto,
considera-las ou na˜o na simplificac¸a˜o das expresso˜es lo´gicas
na˜o ira´ gerar comportamento inesperado do circuito associado
Tais sequeˆncias sa˜o chamadas de don’t care
Podem surgir porqueˆ jamais ocorrera˜o como entrada do circuito,
ou ocorrem mas o valor assumido pela func¸a˜o na ocorreˆncia
desta sequencia na˜o importa. E´ o caso de um circuito cuja
entrada e´ decorrente de um co´digo BCD
Exercı´cio
Escrever a expressa˜o SOP e POS canoˆnicas, simplificando-a em
seguida
f (A,B,C) =
∑
m(0, 3, 7) + d(4, 5)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos
Circuitos Lo´gicos Digitais
Composic¸a˜o serial ou paralela de dispositivos eletroˆnicos de
chaveamento chamados de portas lo´gicos, ou implementados
atrave´s de dispositivos lo´gicos programa´veis
Portas Lo´gicas
Dispositivos eletroˆnicos que operam a taxa de nano-segundos,
empregados na implementac¸a˜o de func¸o˜es lo´gicas
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos
Func¸o˜es Lo´gicas e Circuitos Lo´gicos
As varia´veis lo´gicas sa˜o interpretadas como entradas das
portas lo´gicas (com valores lo´gicos associados a nı´veis de
tensa˜o alto ou baixo nas entradas das portas)
As func¸o˜es lo´gicas sa˜o saı´das de portas ou sistemas de portas,
com valor lo´gico associado a valores de tensa˜o alto ou baixo na
saı´da de uma porta
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos
Sinais Ele´tricos e Valores Lo´gicos
Tabelas verdade em data books especificando o funcionamento
de circuitos possuem suas entradas definidas como nı´veis
alto(H) e baixo(L) de tensa˜o
A escolha de que valores lo´gicos (0 ou 1) representar com estes
valores de tensa˜o e´ uma escolha do projetista
Lo´gica Positivo
O valor lo´gico 1 e´ associado ao nı´vel de tensa˜o alto (H) e o valor
lo´gico 0 ao nı´vel de tensa˜o baixo (L)
Lo´gica Negativa
O valor lo´gico 1 e´ associado ao nı´vel de tensa˜o baixo (L) e o valor
lo´gico 0 e´ associado ao nı´vel de tensa˜o alto (H)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos
Nomenclatura
Sinal Ativo alto: Um sinal que e´ ativado em nı´vel lo´gico 1
quando o nı´vel de tensa˜o de entrada e´ alto (lo´gica positiva).
Neste caso a representac¸a˜o do sinal encontra-se na forma na˜o
complementada, e.g.: a,b, c
Sinal Ativo baixo: Um sinal que e´ ativado em nı´vel lo´gico 1
quando o nı´vel de tensa˜o de entrada e´ baixo (lo´gica negativa).
Neste caso a representac¸a˜o do sinal encontra-se na forma
complementada, e.g.: a¯, b¯, c¯
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos
Sı´mbolo das Portas Lo´gicas e Paraˆmetros
As portas lo´gicas sa˜o representadas por sı´mbolos que
incluem as entradas e as saı´das. O nu´mero de entradas
de uma porta lo´gica e´ chamado de fan-in, sendo
tipicamente dois, treˆs, quatro ou oito. Para nu´meros
maiores de entradas, empregam-se os dispositivos lo´gicos
programa´veis
Pequenos cı´rculos (Bubbles) nas entradas ou saı´das das
portas lo´gicas, indicam que estes sinais sa˜o ativos-baixo.
A auseˆncia de cı´rculos indica que o sinal e´ ativo-alto
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Exemplo de Encapsulamento
Encapsulamento DIP com quatro portas NAND de duas
entradas. Comercialmente identificado como 7400
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Porta AND com Lo´gica Positiva
A saı´da assume nı´vel lo´gico 1 quando “ambas ” as entradas
estivem em nı´vel lo´gico 1
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Porta OR com Lo´gica Positiva
A saı´da assume nı´vel lo´gico 1 quando “uma ” das entradas
estiver em nı´vel lo´gico 1
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Porta NOT
Complementa a varia´vel de entrada. Se essa e´ ativa-alta,
passa a ser ativa-baixa, e vice-versa. O bubble sempre sera´
colocado no lado em que a varia´vel e´ ativa-baixo
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos
Lo´gica Positiva versos Lo´gica Negativa
Na tabela do dispositivo (expressa como H e L), devemos
substituir H → 1 e L→ 0 para lo´gica positiva, enquanto H → 0
e L→ 1 para lo´gica negativa
Lo´gica Positiva versos Lo´gica Negativa
Assim, uma porta lo´gica AND implementa uma porta lo´gica OR
quando consideramos lo´gica negativa. De forma ana´loga, uma
porta lo´gica OR implementa uma porta lo´gica AND quando
consideramos lo´gica negativa
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos
Lo´gica Positiva versos Lo´gica Negativa
Assim, uma porta lo´gica AND implementa uma porta lo´gica OR
quando consideramos lo´gica negativa. De forma ana´loga, uma
porta lo´gica OR implementa uma porta lo´gica AND quando
consideramos lo´gica negativa
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos
Lo´gica Positiva versos Lo´gica Negativa
Assim, uma porta lo´gica AND implementa uma porta lo´gica OR
quando consideramos lo´gica negativa. De forma ana´loga, uma
porta lo´gica OR implementa uma porta lo´gica AND quando
consideramos lo´gica negativa
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos
Exemplo
Sistema contra inceˆndio, composto por dois detectores de
fumac¸a, dois sprinkler e um sistema de discagem telefoˆnica
automa´tico. Por motivos de seguranc¸a e´ empregada lo´gica
negativa.
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Porta NAND
A saı´da assume nı´vello´gico 0 (ativa-baixo) quando ambas as
entradas estiverem em nı´vel lo´gico 1 (ativas-alto)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Porta NAND
A saı´da assume nı´vel lo´gico 0 (ativa-baixo) quando ambas as
entradas estiverem em nı´vel lo´gico 1 (ativas-alto)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Porta NOR
A saı´da assume nı´vel lo´gico 0 (ativa-baixo) quando pelo menos
uma das entradas estiver em nı´vel lo´gico 1 (ativas-alto)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Porta NOR
A saı´da assume nı´vel lo´gico 0 (ativa-baixo) quando pelo menos
uma das entradas estiver em nı´vel lo´gico 1 (ativas-alto)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Portas NAND e NOR
Sa˜o ditas primitivas ou funcionalmente completa pois a partir
delas e´ possı´vel implementar as portas AND, OR e NOT
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Portas NAND e NOR
Sa˜o ditas primitivas ou funcionalmente completa pois a partir
delas e´ possı´vel implementar as portas AND, OR e NOT
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Porta XOR (OU-exclusivo)
Saı´da em nı´vel lo´gico 1 quando uma, e so´ uma, entrada for igual a 1
fXOR(a,b) = a⊕ b = ab¯ + a¯b
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Porta XOR (OU-exclusivo)
Saı´da em nı´vel lo´gico 1 quando uma, e so´ uma, entrada for igual a 1
fXOR(a,b) = a⊕ b = ab¯ + a¯b
Propriedades adicionais
a⊕b=(a¯+b¯)(a+b)
a⊕a=0
a⊕a¯=1
a⊕0=a
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Porta XOR (OU-exclusivo)
Saı´da em nı´vel lo´gico 1 quando uma, e so´ uma, entrada for igual a 1
fXOR(a,b) = a⊕ b = ab¯ + a¯b
Propriedades adicionais
a⊕1=a¯
a¯⊕b¯=a⊕b
a⊕b=b⊕a
a⊕(b⊕c)=(a⊕b)⊕c
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Circuitos Lo´gicos - Sı´mbolos
Porta XNOR
A saı´da assume nı´vel lo´gico 1 quando as entradas assumem o
mesmo valor lo´gico
fXNOR = f¯XOR(a,b) = a� b = a¯b¯ + ab
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Projeto de Circuitos
Converter uma descric¸a˜o atrave´s de palavras (especificac¸o˜es)
de uma determinada func¸a˜o a ser implementada para um
conjunto de equac¸o˜es lo´gicas a serem implementadas com
portas lo´gicas, PLD’s, ou outros elementos lo´gicos
(microprocessadores,...)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Ana´lise de Circuitos
Dada uma implementac¸a˜o em hardware, e´ obtida uma
descric¸a˜o do circuitos na forma de expresso˜es lo´gicas,
tabela verdade, diagramas de tempo, ou outra descric¸a˜o
que capture o comportamento do circuito
Atrave´s de um processo analı´tico, o comportamento do
circuito e´ determinado, pode-se verificar se este satisfaz
os requisitos de projeto
A descric¸a˜o obtida pode ser empregada para
determinar-se outro circuito que implemente o mesmo
comportamento, e.g.: que possua um menor nu´mero de
portas lo´gicas ou seja implementado atrave´s de outros
elementos
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Me´todo alge´brico
Qualquer circuito lo´gico implementa func¸o˜es ou expresso˜es
lo´gicas, obtida esta representac¸a˜o do comportamento do
circuito, podemos empregar a´lgebra booleana para manipular a
representac¸a˜o reescrevendo-a em uma forma que satisfac¸a
nossos necessidades
Elementos constituintes
Qualquer expressa˜o lo´gica pode ser escrita empregando
as operac¸o˜es AND, OR e NOT
Portanto, qualquer circuito pode ser realizado atrave´s de
elementos primitivos (portas NAND e/ou NOR)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Exemplo
Determine uma expressa˜o lo´gica simplificada e especifique o circuito
correspondente para o seguinte circuito lo´gico
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Exemplo
Determine uma expressa˜o lo´gica simplificada e especifique o circuito
correspondente para o seguinte circuito lo´gico
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Me´todo da tabela verdade
A tabela verdade de um circuito pode ser obtida
progressivamente pela determinac¸a˜o do comportamento de
cada uma de suas portas, empregando esta informac¸a˜o parcial
para determinac¸a˜o da soluc¸a˜o final do circuito
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Ana´lise do Diagrama de Tempo
O objetivo e´ capturar o comportamento do circuito pela estimulado do
circuito com os possı´veis valores de entrada e observac¸a˜o da
resposta do circuito para estas entradas
O comportamento do circuito e´ apresentado em um diagrama
de tempo, de onde podemos extrair uma expressa˜o lo´gica ou
tabela verdade
Permite o estudo dos efeitos do atraso de propagac¸a˜o no
funcionamento do circuito
Diagrama de Tempo
Representac¸a˜o gra´fica da relac¸a˜o entre os sinais de entrada e saı´da
de um circuito lo´gico. Um diagrama de tempo especificado
adequadamente, pode conter toda a informac¸a˜o apresentada pela
tabela verdade
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Exemplo
O circuito abaixo e´ estimulado com uma sequencia de entradas,
produzindo o diagrama de tempo apresentado. Empregando lo´gica
positiva, determinar a tabela verdade e lista de mintermos para as
func¸o˜es fα(A,B,C) e fβ(A,B,C) implementadas pelo circuito
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Tempo de Propagac¸a˜o
No caso anterior, o comportamento de nosso circuito era
idealizado. Na˜o foram considerados os tı´picos atrasos de
propagac¸a˜o decorrentes das limitac¸o˜es fı´sicas dos dispositivos
empregados no projeto desses circuitos
O projeto de circuitos digitais envolve elementos fı´sicos,
portanto com limitac¸o˜es e caracterı´sticas que devem ser
consideradas na hora do projeto
Atraso de propagac¸a˜o
Restric¸o˜es de fan-in e fan-out
Consumo de poteˆncia
Dimenso˜es e peso
Atraso de propagac¸a˜o e restric¸o˜es de fan-in e fan-out possuem
implicac¸a˜o direta no projeto do circuito (topologia do circuito)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Tempo de Propagac¸a˜o
Atraso na resposta do circuito (variac¸a˜o na saı´da) como decorreˆncia
de uma variac¸a˜o dos sinais de entrada
Dependeˆncia
Fatores tı´picos que influenciam no tempo de propagac¸a˜o sa˜o:
Complexidade do circuito
Tecnologia empregada na construc¸a˜o das portas logicas
Fan-out (nu´mero de entradas de outras portas conectadas a
uma u´nica saı´da)
Temperatura
Tensa˜o do chip
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Paraˆmetros
Ha´ doisparaˆmetros de propagac¸a˜o que devem ser considerados,
sendo especificados em databooks
tPLH= Tempo de propagac¸a˜o, de nı´vel-baixo para nı´vel-alto da
saı´da
tPHL= Tempo de propagac¸a˜o, de nı´vel-alto para nı´vel-baixo da
saı´da
Com tPLH e tPHL medidos do tempo em que ha´ variac¸a˜o da entrada
para o tempo da variac¸a˜o correspondente de saı´da
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Paraˆmetros
Quando na˜o ha´ necessidade de uma informac¸a˜o de atraso precisa,
podemos considerar o paraˆmetro me´dio
tPD =
tPLH + tPHL
2
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Propagac¸a˜o e Tecnologia de Implementac¸a˜o
O tempo de propagac¸a˜o depende da tecnologia empregada na
implementac¸a˜o da porta lo´gica. Abaixo o caso de uma NAND
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Propagac¸a˜o e Portas Lo´gicas
O tempo de propagac¸a˜o depende da porta lo´gica
implementada. Abaixo empregamos a tecnologia TTL
Low-Power Schottky
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Exemplo
Uma sequeˆncia de sinais de entrada sa˜o aplicados ao circuito
abaixo, produzindo o diagrama temporal apresentado. Cada porta
possui um tempo de propagac¸a˜o tPD. Determinar a tabela verdade e
expressa˜o lo´gica mı´nima do circuito.
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Ana´lise de Circuitos Lo´gicos Combinacionais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Objetivo
Emprego de a´lgebra booleana, portas lo´gicas, tabela verdade
e diagrama de tempo para sı´ntese de circuitos digitais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Redes AND-OR e NAND
Emprego de portas AND para implementar os termos produto
e de portas OR para implementar a soma. Para seu emprego a
expressa˜o deve estar na forma de soma de produtos (SOP).
fδ(p,q, r , s) = pr¯ + qrs + p¯s
pode ser diretamente implementada com redes AND-OR.
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Redes AND-OR e NAND
fδ(p,q, r , s) = pr¯ + qrs + p¯s
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Redes OR-AND e NOR
Emprego de portas OR para implementar os termos soma e de
portas AND para implementar o produto. Para seu emprego a
expressa˜o deve estar na forma de produtos de soma (POS).
f�(A,B,C,D) = (A¯ + B + C)(B + C + D)(A¯ + D)
pode ser diretamente implementada com redes OR-AND.
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Redes OR-AND e NOR
f�(A,B,C,D) = (A¯ + B + C)(B + C + D)(A¯ + D)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Circuitos com dois nı´veis
O sinal de entrada deve passar por dois nı´veis de portas antes
que influencie a saı´da. O primeiro nı´vel contem a porta que
produz a saı´da. As entradas do circuito ficam conectadas ao
segundo nı´vel.
Circuitos com mu´ltiplos nı´veis
Quando portas NOT sa˜o empregadas na entrada, uma rede de
treˆs nı´veis e´ produzida. Uma rede possui n nı´veis quando pelo
menos uma entrada precisa passar por n portas antes de
alcanc¸ar a saı´da.
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Implementac¸a˜o de redes SOP e POS
Quando as forma complementada e na˜o complementada
das varia´veis esta´ disponı´vel, uma func¸a˜o lo´gica sempre
pode ser implementada com uma rede de dois nı´veis
Quando so´ uma forma esta´ disponı´vel, poderemos ter que
implementa-la empregando uma rede com treˆs nı´veis.
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Redes multi-nı´vel
Restric¸o˜es de fan-in podem obrigar a implementac¸a˜o de
func¸o˜es lo´gicas empregando mu´ltiplos nı´veis
f (a,b, c,d ,e) = abcde
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Procedimento Geral - Rede NAND e OR
1 Expressar a func¸a˜o como lista de mintermos (maxtermos)
2 Escrever os mintermos (maxtermos) na forma alge´brica
3 Simplificar a func¸a˜o na forma SOP (POS) empregando
algebra booleana
4 Utilizar os Teoremas (DeMorgan e Involuc¸a˜o) abaixo para
transformar a expressa˜o na formulac¸a˜o com NAND (NOR)
a + b = a¯b¯ (ab = a¯ + b¯), ¯¯a
5 Desenhar o diagrama do circuito NAND (NOR)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Exemplo
Implementar a func¸a˜o
fφ(X ,Y ,Z ) =
∑
m(0, 3, 4, 5, 7)
com portas NAND
Exemplo
Implementar a func¸a˜o
fφ(X ,Y ,Z ) =
∑
m(0, 3, 4, 5, 7)
com portas NOR
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Circuitos AOI
Circuitos AND-OR-Inverter (AOI), implementado com portas
AND alimentando uma porta NOR a qual esta´ associada a
saı´da do circuito.
Aplicac¸a˜o de Circuitos AOI
Identificados pelo nu´mero de entradas de suas portas
AND constituintes, e.g.: 2-2-2 AOI (possui treˆs portas AND
com duas entradas), 2-2-3-4 AOI (possui duas portas and
com duas entradas, uma com treˆs e uma com quatro).
Circuitos AOI com portas AND de duas entradas podem
ser empregados como seletores de sinais (ou fontes de
informac¸a˜o), empregando algumas linhas para selecionar
entradas especı´ficas (sinais de selec¸a˜o), e outras como
entradas das fontes de sinal
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Procedimento de FATORAC¸A˜O
Aplicado para obtenc¸a˜o de circuitos onde o sinal pode
propagar por mais de dois nı´veis de portas lo´gicas (formas
com mu´ltiplos nı´veis)
Necessitam de menos hardware, portanto, sa˜o mais
econoˆmicos (menos hardware)
Tambe´m podem ser empregados em casos onde ha´
limitac¸a˜o de fan-in
Empregado para reduzir o nu´mero de literais por porta
lo´gica (por termo produto (SOP), ou termos soma (POS)),
ate´ o nu´mero que satisfac¸a os requisitos da aplicac¸a˜o
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Empregar Fatorac¸a˜o Para Implementar
fλ(A,B,C,D) = AB¯ + AD¯ + AC¯
f (a,b, c,d) =
∑
m(8, 13)
Booleana Venn Extenso˜es Func¸a˜o booleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
Booleana Venn Extenso˜es Func¸a˜obooleana Ana´lise Sı´ntese Sı´ntese
Sı´ntese de Circuitos Digitais
	Álgebra Booleana
	Diagrama de Venn Para Representação de Postulados e Teoremas
	Princípios e Teoremas
	Funções Booleanas
	Análise de Circuitos Digitais
	Síntese de Circuitos Digitais
	Síntese de Circuitos Digitais