Curso Técnico em Eletrotécnica
Disciplina: Automação Predial e Industrial
Professor: Ronimack Trajano
1
FORMAS CANÔNICAS
A lógica estruturada é baseada na capacidade de escrever equações booleanas de maneira
que ela utilize vários tipos de formas regulares e repetidas. Dois tipos de formas estruturadas são
especialmente úteis em um projeto lógico. Elas são conhecidas como “Soma de produtos” e
“Produto de somas”. Uma expressão em soma de produtos consiste em efetuar operações OR
sobre termos contendo operações AND. A expressão em produto de somas consiste em efetuar
operações AND sobre termos contendo operações OR. Com essa estruturação, as equações podem
ser determinadas pela aplicação da regra de De Morgan.
Se associarmos cada combinação das variáveis de entrada ao seu equivalente em decimal,
cada mintermo pode ser representado por mi, onde i é o decimal associado. De forma similar, cada
maxtermo pode ser representado por Mi, onde i é o decimal associado. A Tabela 1 lista todos os
mintermos e maxtermos de uma função de três variáveis (A, B e C).
Tabela 1 - Minitermos e Maxtermos para uma função de 3 variáveis.
Quando representamos expressões descritas em termos de soma de produtos, é
conveniente introduzirmos o conceito de Minitermo. O minitermo é formado com a operação AND
aplicada a todas as variáveis, em suas formas normais ou complementares. A notação com
minitermos pode ser utilizada para simplificar a aparência de expressões em soma de produtos.
Quando representamos expressões descritas em termos de produto das somas, é
conveniente introduzirmos o conceito de Maxtermo. O maxtermo é formado com a operação OR
aplicada a todas as variáveis, em suas formas normais ou complementares. A notação com
maxtermo pode ser utilizada para simplificar a aparência de expressões em produto de somas.
Considere a função:
( , , )= ̅
̅+ ̅
+
̅+
Nota de aula adaptada das notas de aula Introdução aos Sistemas Digitais (v.2001/1) de José Luís Güntzel e Francisco Assis do
Nascimento e Eletrônica Digital por F. C. C. de Castro.
Esta expressão pode ser expressa em termos de minitermos utilizando a seguinte forma,
onde o símbolo de somatório (∑) indica a operação OR aplicada aos minitermos listados dentro do
parêntese. Cada termo produto construído é denominado minitermo.
( , , )=
(0,3,4,7)
Note que, para um dado minitermo, se substituirmos os valores das variáveis associadas,
obteremos 1. Porém, se substituirmos nesse mesmo minitermo quaisquer outras combinações de
valores, obteremos 0. Dessa forma, se quisermos encontrar a equação para uma função a partir de
sua tabela verdade, basta montarmos um OU entre os minitermos associados aos 1s da função
(também chamados minitermos 1 ).
Considere a função:
( , , ) = ( + + ̅ )( + + )( ̅ + + ̅ )( ̅ + + )
Esta expressão pode ser expressa em termos de maxtermos utilizando a seguinte forma,
onde o símbolo de somatório (∏) indica a operação AND aplicada nos maxtermos listados entre
parêntesis. Cada termo soma construído é denominado maxtermo.
( , , )=
(1,2,5,6)
Note que, para um dado maxtermo, se substituirmos os valores das variáveis associadas,
obteremos 0. Porém, se substituirmos nesse mesmo maxtermo quaisquer outras combinações de
valores, obteremos 1. Dessa forma, se quisermos encontrar a equação para uma função a partir de
sua tabela verdade, basta montarmos um E entre os maxtermos associados aos 0s da função
(também chamados maxtermos 0).
A soma de produtos e o produto de somas descritos apresentam ainda uma característica
bastante particular: em cada termo soma e em cada termo produto todas as variáveis da função
estão presentes. Devido a essa característica, essas formas são chamadas canônicas.
2
SIMPLIFICAÇÃO DE FUNÇÕES BOOLEANAS - MAPAS DE KARNAUGH
O método de simplificação de uma expressão Booleana utilizando soma de produtos (SdP)
para os minitermos, ou produto de somas (PdS) para os maxtermos é de aplicabilidade limitada,
uma vez que é bastante difícil certificar-se que todos os pares de minitermos que podiam ser
simplificados foram determinados. Alternativamente àquele método, há outro método de
simplificação baseado na identificação visual de grupos de minitermos ou maxtermos passíveis de
serem simplificados. No entanto, para que se possam identificar tais grupos, é necessário que os
minitermos sejam dispostos de maneira mais conveniente, o que será explicado a seguir.
Na descrição do método de simplificação literal, foi mencionado que os pares de
minitermos que se diferenciam de somente uma variável são passíveis de simplificação, ou seja, se
o minitermo ̅ ̅ e ̅
se diferenciam apenas da variável “C”, então na soma dos termos essa
variável será eliminada, ou seja, ̅
̅+ ̅
= ̅ ( ̅ + ) = ̅ (1) = ̅ . Observando a ordem
com que os minitermos de uma função Booleana qualquer (com, por exemplo, 3 variáveis)
aparecem na tabela verdade, vemos que, se trocarmos o 3° minitermo com o 4° e trocarmos
também o 7° minitermo com o 8°, obteremos uma nova ordem, na qual quaisquer dois minitermos
adjacentes são passíveis de simplificação. É interessante notar também que o 1° minitermo pode
ser simplificado com o 5°, o 2° minitermo pode ser simplificado com o 6° e assim por diante.
Tabela 2 - Minitermos para uma função de 3 variáveis.
Então, usando o novo ordenamento e rearranjando os minitermos em duas linhas, temos a
seguinte tabela:
Tabela 3 - Tabela de adjacências para uma função de 3 variáveis.
Repare que nessa nova tabela, quaisquer dois minitermos adjacentes (na horizontal ou na
vertical) são passíveis de serem simplificados, pois só se diferenciam de uma variável. É importante
ressaltar que esse conceito de adjacência não está restrito aos limites da tabela, uma vez que os
elementos extremos de uma mesma linha (ou de uma mesma coluna) também são simplificáveis.
Isto implica que a tabela de adjacências de minitermos da Tabela 3 pode e deve ser encarada como
uma figura geométrica tridimensional do tipo “toróide”. A Figura 1 a seguir explicita as relações de
adjacência dos minitermos para uma função de três variáveis.
Figura 1 - Simplificações possíveis entre os minitermos de uma função de 3 variáveis.
É importante ressaltar que o conceito de adjacência é aplicável na horizontal e na vertical,
mas nunca na diagonal. Por exemplo, observe que m 0 e m5 não são adjacentes, pois não estão nem
na mesma linha, nem na mesma coluna.
O processo de simplificação usando a nova disposição inicia pela construção da tabela em
si: os valores da função que se quer simplificar devem ser preenchidos conforme a nova ordem.
Após, identificam-se todos os grupos de minitermos-1 adjacentes entre si. Cada grupo origina um
termo produto, no qual somente as variáveis comuns a todos os minitermos-1 permanecem. Desde
que os grupos de minitermos-1 adjacentes tenham sido corretamente identificados, a simplificação
se torna trivial.
Um mapa de Karnaugh é uma matriz com 2 N células, onde N é o número de variáveis ou
entradas do circuito e onde cada célula está associada a um minitermo ou maxtermo. Para três
variáveis, por exemplo, o mapa de Karnaugh é um conjunto de 8 células, já que existem 8
minitermos ou maxtermos associados. As células do mapa K (leia-se mapa de Karnaugh) são
arrumadas de modo que minitermos logicamente adjacentes sejam, também, graficamente
adjacentes. Dois minitermos são logicamente adjacentes quando diferem pelo estado lógico de
apenas uma única variável.
Figura 2 - Mapas de Karnaugh para funções de 2, 3 e 4 variáveis.
2.1
REPRESENTAÇÃO DE FUNÇÕES NOS MAPAS DE KARNAUGH (MAPA K)
Duas situações podem ocorrer quando se quer representar uma função no mapa K: a
função está na forma canônica ou então na forma reduzida.
Quando a função está na forma canônica de soma de produtos (soma de minitermos)
basta colocar 1 nas células associadas aos minitermos que a compõem e 0 nas restantes.
Quando a forma canônica é de produto de somas (produto de maxtermos) basta colocar 0
nas células associadas aos índices de maxtermos que compõem a função e 1 nos restantes.
2.1.1 SIMPLIFICAÇÃO USANDO OS 1S DO MAPA K
1) As células ocupadas por 1s são identificadas;
2) Formam-se grupos de células logicamente adjacentes ocupadas por 1s;
3) Estes grupos devem conter o maior número possível de células logicamente
adjacentes, mas este número deve ser sempre uma potência de 2. Logo, só é permitida
a formação de grupos que tenham 1, 2, 4, 8, 16, 32, ... elementos;
4) Os grupos devem ter sempre a forma de quadrados ou retângulos;
5) A mesma célula pode participar da formação de dois ou mais grupos diferentes;
6) Os minitermos da coluna da esquerda são adjacentes aos minitermos da coluna da
direita. Os minitermos da linha superior do mapa são, também, adjacentes aos
minitermos da linha inferior;
7) Os minitermos localizados nos vértices do mapa são adjacentes entre si;
8) Sempre que um grupo é formado, a variável que muda de estado é a eliminada. Se o
grupo engloba parte da região “A” e parte da região “A”, a variável A é eliminada.
2.1.2 SIMPLIFICAÇÃO USANDO OS 0S DO MAPA K
1) Grupos de células contendo zeros são formados usando-se as mesmas regras válidas
para a minimização por 1s;
2) Após a leitura dos grupos de zeros, que surgem como produtos lógicos, os mesmos são
complementados, transformando-se em somas lógicas;
3) As somas lógicas são combinadas através da operação produto lógico. Isto resulta
numa função minimizada com a estrutura de produto de somas.
2.1.3 EXEMPLOS:
1) Dadas as representações de minitermos Y(A, B, C, D) = ∏(2,4,10,12,14) e pela tabela
verdade a seguir, apresente a expressão booleana simplificada.
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Y
1
1
0
1
0
1
1
1
1
1
0
1
0
1
0
1
2) Dadas as representações de minitermos ( , , ) = ∑(0,1,3,5,6,7)e pela tabela verdade a
seguir, apresente a expressão booleana simplificada.
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
Y
1
1
0
1
0
1
1
1
3) Dadas as representações de minitermos Y(A, B, C, D) = ∑(0,2,8,10) e pela tabela verdade a
seguir, apresente a expressão booleana simplificada.
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
2.2
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Y
1
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
FUNÇÕES INCOMPLETAMENTE ESPECIFICADAS (DON’T CARE CONDITION)
Durante o projeto lógico, pode ocorrer que algumas condições (combinações) de entradas
de uma função Booleana para as quais não sejam especificadas o seu resultado na saída, por não
afetarem a função no contexto do projeto. Cada condição de entrada cujo valor não é especificado
é sinalizada com “DC” ou com “X” na tabela verdade (ou no mapa de Karnaugh) e são denominadas
condições de don’t care (ou simplesmente, don’t care).
Quando da simplificação de uma função Booleana que contenha condições de don’t care,
essas condições podem e devem ser exploradas no sentido de se obter a máxima simplificação
possível. Para tanto, pode-se assumir cada condição de don’t care como valendo 0 ou 1,
independente das demais condições de don’t care. A escolha do valor (0 ou 1) irá depender do
contexto, mas sempre deverá ocorrer com o objetivo de levar a uma simplificação máxima da
função Booleana.
Vamos supor que um determinado processo industrial a ser controlado por um circuito
lógico tenha uma variável Y representada de minitermos Y(A, B, C, D) = ∑(4,5,6,8,9) +
DC(7,10,11,14,15) e consequente tabela verdade a seguir:
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Y
0
0
0
0
1
1
1
X
1
1
X
X
0
0
X
X
O valor de X atribuído à saída Y em determinadas linhas da tabela verdade significa que,
para os específicos valores lógicos das variáveis A, B, C e D nestas linhas, o valor lógico da saída Y é
irrelevante para o processo controlado (don’t care).
O mapa resultante é:
Mas uma vez que os quadrículos contendo X representam situações irrelevantes ao
processo industrial, podemos atribuir a cada X um valor lógico conveniente no contexto de
minimização lógica de forma a nos permitir agrupar o maior número possível de quadrículos
gerando o menor número possível de agrupamentos.
Nesse sentido para a simplificação máxima desta função, seria conveniente que os valores
de saída X, apresentados nas linhas 2 e 4 do mapa K fossem iguais a 1, visto que não haveria
alterações nas outras saídas do circuito, consequentemente o circuito lógico não sofreria alterações
quanto ao estado das demais saídas. Desse modo, o mapa K poderia ser representado por:
O mapa K para a função com os valores dos X’s atribuídos objetivando a minimização da
função lógica resultante. A função lógica minimizada resulta em = ̅ +
= ⊕ .
Observe que os X’s da linha 3 não foram inclusos na solução final, visto que todos os 1’s já
foram combinados (agrupados).
4) Dadas as representações de minitermos
( , , ) = ∑(0,1,5,6) +
(3,7) e pela tabela
verdade a seguir, apresente a expressão booleana simplificada.
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
Y
1
1
0
X
0
1
1
X
5) Dadas as representações de minitermos
( , , ) = ∑(0,1,5,6) +
verdade a seguir, apresente a expressão booleana simplificada.
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
Y
1
X
X
X
X
0
0
1
(3,7) e pela tabela