Encontre a forma disjuntiva mínima para as seguintes expressões booleanas usando mapas de Karnaugh e indique o número de formas disjuntivas mínimas diferentes que você consegue encontrar para cada uma delas: (h)
.
Passo 1
O enunciado nos dá a expressão booleana
e pede: (i) encontrar a forma disjuntiva mínima usando mapas de Karnaugh; (ii) indicar o número de formas disjuntivas mínimas diferentes que se conseguem encontrar.
Informações relevantes que extraí da expressão (peguei estes minterms diretamente dos termos dados):
Informações relevantes que extraí da expressão (peguei estes minterms diretamente dos termos dados):
-
cobre os minterms e . -
cobre o minterm . -
cobre o minterm . -
cobre o minterm .
Portanto a função é a soma canônica dos minterms
Passo 2
Vou montar mentalmente o mapa de Karnaugh para três variáveis
. Organização usual (linhas:
; colunas:
em ordem Gray
). A posição dos minterms no mapa é:
- Linha
: colunas correspondem a . - Linha
: colunas correspondem a .
Coloco 1’s nos minterms que temos (peguei esses números dos termos originais):
.
Passo 3
Regras rápidas de Karnaugh (lembrando com linguagem simples):
- Pode agrupar blocos de
's com tamanhos potencia de 2: . - Cada bloco gera um implicante: variáveis que mudam dentro do bloco são eliminadas; as que permanecem constantes aparecem no produto.
- Queremos cobrir todos os
's com o menor número de implicantes (preferência por blocos maiores).
Observando o mapa com os
's em
:
- Os minterms
são exatamente todos os casos com (colunas onde ). Esses quatro formam um bloco de tamanho (2x2). Um bloco de 4 elimina duas variáveis, ficando apenas a variável que é constante: aqui a constante é . Logo esse bloco gera o implicante de uma variável (Interpretação didática: qualquer combinação de e com é na função.) - O minterm restante é
(posição ). Ele pode ser agrupado com (que está em ) formando um bloco de tamanho ao longo da variação de . Esse bloco fixa e , eliminando . O implicante gerado é
Com essas duas escolhas (o bloco de 4 que dá
e o par que dá
) todos os
's são cobertos. Esses implicantes são grandes (máximo possível) e, portanto, candidatos fortes a formar a forma disjuntiva mínima.
Passo 4
Faço também a verificação algébrica, passo a passo, para entender e justificar a simplificação (é bom para a prova):
Começo com
Agrupo os termos que contêm
:
Fatorando
dos três primeiros termos:
Dentro do parêntese, uso
, então
Assim o produto fica
Agora aplico a propriedade de absorção/consenso:
. Tomando
e
,
, temos
Portanto a expressão se reduz para
Passo 5
Justificativa de minimalidade e unicidade (por que não existe outra forma disjuntiva mínima diferente):
- A expressão
tem apenas termos e soma total de literais ( na primeira soma, na segunda). É difícil ter uma soma com menos termos porque a função tem cinco minterms; só possível cobrir todos usando ao menos um implicante de tamanho 4 (que cobre 4 minterms) e outro que cubra o minterm isolado restante — ou então mais termos menores, o que resulta em mais termos no total. - No mapa, o bloco de 4 correspondente à variável
é o único bloco de 4 possível que cobre os quatro minterms com . Para cobrir (o único com ), o único implicante que o cobre sem introduzir minterms externos inválidos é (o par ). Logo, qualquer solução com 2 termos precisa necessariamente ser exatamente e . - Outras coberturas possíveis com mais termos (por exemplo
) não são mínimas em número de termos; elas podem se rearranjar algébrica e automaticamente reduzir para .
Por isso a forma
é minimal em termos de número de termos e literais e é única (até comutação dos somandos, que não conta como forma diferente).
Resposta
Número de formas disjuntivas mínimas diferentes: