Encontre a forma disjuntiva mínima para as seguintes expressões booleanas dadas como soma de mintermos usando mapas de Karnaugh e indique o número de formas disjuntivas mínimas diferentes que você consegue encontrar para cada uma delas:
(a) \alpha=\sum m(3,6,7,13,14,15);

Passo 1

O enunciado dá a função booleana como soma de mintermos
\alpha=\sum m(3,6,7,13,14,15).
O que ele pede:
  • Encontrar a forma disjuntiva mínima (forma soma de produtos minimizada) usando mapas de Karnaugh.
  • Indicar o número de formas disjuntivas mínimas diferentes que forem encontradas.
Informações relevantes fornecidas (peguei os números dos mintermos do enunciado):
  • Os mintermos são os índices \{3,6,7,13,14,15\}.
  • Como o maior índice é 15, isso corresponde a uma função de 4 variáveis. Vou chamar as variáveis, do bit mais significativo para o menos significativo, de A,B,C,D. Assim cada mintermo m(i) corresponde a um produto (AND) de literais de A,B,C,D segundo a representação binária de i.

Passo 2

Converter cada mintermo para a forma canônica (produto de literais) — escrevo o binário de 4 bits e a expressão correspondente:
  • 3 = 0011 m(3)=\overline{A}\,\overline{B}\,C\,D.
  • 6 = 0110 m(6)=\overline{A}\,B\,C\,\overline{D}.
  • 7 = 0111 m(7)=\overline{A}\,B\,C\,D.
  • 13=1101 m(13)=A\,B\,\overline{C}\,D.
  • 14=1110 m(14)=A\,B\,C\,\overline{D}.
  • 15=1111 m(15)=A\,B\,C\,D.
Explicando rápido a ideia do mapa de Karnaugh (didático):
  • O mapa de 4 variáveis é uma grade 4\times4 onde as linhas são os pares AB em ordem Gray (00,01,11,10) e as colunas são CD em ordem Gray (00,01,11,10).
  • Cada célula corresponde a um índice 0 a 15. Dois mintermos são adjacentes no mapa se diferem em exatamente uma variável; ao agrupar células adjacentes em potências de 2 (1,2,4,8…) podemos eliminar variáveis e obter implicantes maiores (menos literais).
  • Objetivo: cobrir todas as células com 1s usando o mínimo de implicantes prime (preferir grupos maiores).
Coloco agora os índices nas células (linhas AB, colunas CD) — isso ajuda a visualizar os 1s:
\begin{array}{c|cccc} & CD=00 & CD=01 & CD=11 & CD=10\\hline AB=00 & 0 & 1 & 3 & 2\\\ AB=01 & 4 & 5 & 7 & 6\\\ AB=11 & 12 & 13 & 15 & 14\\\ AB=10 & 8 & 9 & 11 & 10 \end{array}
Marcam-se 1s nas células com índices \{3,6,7,13,14,15\}.

Passo 3

Achar agrupamentos possíveis e os implicantes resultantes (regra prática: agrupar em potências de dois e eliminar a(s) variável(is) que mudam entre as células do grupo).
Analiso agrupamentos úteis:
  • Observando as quatro células com índices 6,7,14,15 (formam um bloco 2\times2 que ocupa linhas AB=01 e AB=11 e colunas CD=10 e CD=11). Nessas quatro células temos sempre B=1 e C=1, enquanto A e D variam. Logo esse bloco produz o implicante
    B\,C.
    (Explicação: ao combinar mintermos que diferem apenas em A e/ou D acabamos eliminando A e D, sobrando B e C.)
  • Há uma dupla vertical entre as células m(3) e m(7) (indices 3 e 7 — mesmas colunas CD=11, linhas AB=00 e AB=01). Nestas duas, A é 0 em ambas, C=1,D=1; somente B varia. Isso dá o implicante
    \overline{A}\,C\,D.
    (Regra: duas células que diferem em uma variável eliminam essa variável, aqui B foi eliminada.)
  • Há uma dupla horizontal entre m(13) e m(15) (índices 13 e 15 — mesma linha AB=11, colunas CD=01 e CD=11). Nessas duas, A=1,B=1,D=1 é comum, C varia; assim o implicante é
    A\,B\,D.
Observações sobre outros implicantes possíveis (mas menos interessantes porque são menores ou redundantes):
  • Pode-se formar duplas 6\&7 \overline{A}\,B\,C, ou 7\&15 B\,C\,D, ou 14\&15 A\,B\,C, ou 6\&14 B\,C\,\overline{D}. Mas muitos desses implicantes são subcasos do implicante maior B\,C (o bloco 2\times2 que encontrei covers 6,7,14,15).
  • A regra prática do mapa: preferir blocos maiores (aqui o bloco de 4 que dá B\,C é melhor que duas duplas que dariam implicantes com mais literais).

Passo 4

Identificar implicantes essenciais:
  • Um implicante é essencial se ele contém alguma célula 1 que nenhum outro implicante prime contém.
  • A célula m(3) (índice 3) só é coberta pelo implicante \overline{A}\,C\,D (não existe outro grupo maior que a contenha). Logo \overline{A}\,C\,D é essencial.
  • A célula m(13) (índice 13) só é coberta pelo implicante A\,B\,D (apenas o par 13\&15 dá algo que contenha 13). Logo A\,B\,D é essencial.
  • As quatro células 6,7,14,15 podem ser cobertas pelo implicante único maior B\,C; também poderiam ser cobertas por combinações de pares, mas B\,C é um único implicante que cobre todas com menos literais. Assim B\,C é o implicante preferível para cobrir esses quatro.
Portanto uma cobertura mínima (cobrindo todas as 1s com o mínimo de termos e preferindo implicantes maiores) é:
B\,C \;+\; \overline{A}\,C\,D \;+\; A\,B\,D.
Faço uma checagem rápida: cada mintermo está coberto?
  • 3=\overline{A}\overline{B}C D é coberto por \overline{A} C D.
  • 6=\overline{A}B C\overline{D} é coberto por B C.
  • 7=\overline{A}B C D é coberto por B C (ou por \overline{A} C D, mas já está coberto).
  • 13=A B \overline{C} D é coberto por A B D.
  • 14=A B C \overline{D} é coberto por B C.
  • 15=A B C D é coberto por B C and also by A B D and by others, but já está coberto.

Passo 5

Discutir a unicidade/minimalidade das formas encontradas:
  • A expressão obtida tem três termos: B C (2 literais), \overline{A} C D (3 literais) e A B D (3 literais) — total de 2+3+3=8 literais.
  • Poderiam existir outras coberturas com também três termos? Sim: por exemplo escolher implicantes menores em vez de B C, como B C\overline{D} (cobre 6,14), B C D (cobre 7,15) e manter \overline{A} C D e A B D — mas aí seriam 4 termos. Ainda é possível formar alternativa de 3 termos usando B C\overline{D}, \overline{A} C D e A B D — isso cobre tudo com 3 termos também. Porém essa alternativa tem total de literais 3+3+3=9, maior que 8.
  • Como critério de mínima forma disjuntiva por Karnaugh usa-se: primeiro minimizar número de termos e, entre expressões com o mesmo número de termos, minimizar o total de literais (preferir implicantes maiores). Pela esse critério, a expressão com B C (o bloco de 4) é melhor porque reduz o número total de literais.
  • Conclusão sobre o número de formas mínimas: se o critério for estritamente “mínimo número de produtos” pode haver alternativas com o mesmo número de termos; mas com o critério usual (minimizar termos e depois literais) a expressão encontrada é a única que atinge o menor número de literais total. Assim, reporto que há uma forma disjuntiva mínima sob o critério padrão de K-map.

Resposta

\alpha = B\,C + \overline{A}\,C\,D + A\,B\,D
Número de formas disjuntivas mínimas (pelo critério padrão de Karnaugh: primeiro minimizar número de termos e depois minimizar literais): 1

Exercícios relacionados