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:
(a)
;
(a)
Passo 1
O enunciado pede duas coisas para a expressão booleana
As perguntas são:
- Encontrar a forma disjuntiva mínima (mínimo soma-de-produtos) de
usando mapas de Karnaugh. - Indicar quantas formas disjuntivas mínimas diferentes existem para
.
Informações relevantes dadas:
- A expressão original está em soma de produtos (lista de mintermos/termos).
- As variáveis envolvidas são
, e .
Passo 2
Primeiro vamos listar explicitamente os mintermos (os combinacionais de
) que fazem
. Cada produto corresponderá a um mintermo (ou a mais de um, se tiver variáveis com apóstrofo que anulam a dependência):
-
corresponde ao mintermo (bits ). -
corresponde a (bits ). -
tem e , então independe de : cobre ( ) e ( ). -
corresponde a ( ). -
corresponde a ( ), mas esse já foi coberto por .
Portanto o conjunto de mintermos presentes é
Passo 3
Vamos montar o mapa de Karnaugh para três variáveis. Organizando as colunas pelo par
em código Gray
e as linhas por
(linha superior) e
(linha inferior), os mintermos aparecem assim:
- Linha
: colunas correspondem a . Os uns estão em , , . - Linha
: colunas correspondem a . Os uns estão em , .
Em forma de mapa (linha superior
, inferior
; colunas
):
-
: [1, 1, 0, 1] (m0, m1, m3, m2) -
: [0, 0, 1, 1] (m4, m5, m7, m6)
Passo 4
Agora procuramos agrupamentos (grupos de tamanho
sempre potências de 2) para obter implicantes primos:
Possíveis agrupamentos óbvios:
- Grupo horizontal entre
e (linha , colunas e ). Esses dois compartilham e (pois colunas e têm ), logo implicante primo . - Grupo horizontal entre
e (linha , colunas e ). Esses compartilham e , implicante primo . - Grupo horizontal entre
e (linha , colunas e ): compartilham e , implicante primo . - Grupo vertical entre
(linha , col ) e (linha , col ): compartilham a coluna , implicante primo .
Assim, os implicantes primos identificados são:
Passo 5
Determinamos agora quais desses implicantes primos são essenciais (ou seja, cobrem algum mintermo que nenhum outro cobre):
- Mintermo
( ) é coberto apenas por . Logo é essencial. - Mintermo
( ) é coberto apenas por . Logo é essencial. - Mintermo
é coberto por e por (não único). - Mintermo
é coberto por e por (não único). - Mintermo
é coberto por e por (não único).
Portanto os implicantes essenciais já fixos na simplificação são
Passo 6
Após incluir os implicantes essenciais
e
, vemos quais mintermos ainda precisam ser cobertos:
-
e já estão cobertos por . -
e já estão cobertos por . - Resta cobrir
( ).
Para cobrir
há duas opções entre os implicantes primos que contêm
:
- escolher
(cobre e ), ou - escolher
(cobre e ).
Cada escolha junto com os essenciais fornece uma cobertura completa dos mintermos.
Passo 7
Analisando custo/complexidade: cada implicante candidato (
,
,
,
) tem dois literais. As duas alternativas de cobertura finais (usar
ou usar
) resultam em expressões com três termos de dois literais cada — custo igual. Não existem implicantes maiores (grupo de 4) que reduzam o número de termos abaixo de três, porque há cinco mintermos espalhados que impedem um agrupamento maior que cubra todos com menos implicantes. Assim formas com apenas dois produtos não são possíveis.
Passo 8
Conclusão do procedimento com o mapa de Karnaugh: existem exatamente duas escolhas mínimas para completar a cobertura depois dos essenciais, e ambas produzem expressões de três termos (cada termo com 2 literais), portanto ambas são formas disjuntivas mínimas.
Resposta
Número de formas disjuntivas mínimas diferentes: