(valor 2,0 ) Aplique o Método de Minimização Tabular de Quine-McCluskey na lista de mintermo seguir e apresente a expressão simplificada (minimizada).
S=\sum_{A, B, C, D}(0,2,7,9,12,13,15)

Passo 1

O enunciado pede: aplicar o Método de Minimização Tabular de Quine–McCluskey à função booleana dada por
S=\sum_{A,B,C,D}(0,2,7,9,12,13,15).
Informações relevantes fornecidas (lista de mintermos): \,0,2,7,9,12,13,15\,. Vou usar a convenção usual de numeração de mintermos com \,A como o bit mais significativo e \,D como o menos significativo.

Passo 2

Primeiro passo prático: escrever cada mintermo em binário com 4 bits (A\,B\,C\,D). Isso é necessário porque o método de Quine–McCluskey trabalha com representações binárias e agrupa termos pelo número de uns.
As conversões são:
\begin{aligned} 0 &= 0000,\\\\ 2 &= 0010,\\\\ 7 &= 0111,\\\\ 9 &= 1001,\\\\ 12 &= 1100,\\\\ 13 &= 1101,\\\\ 15 &= 1111. \end{aligned}
Explicação curta do porquê: cada mintermo é o número decimal correspondente ao padrão de bits A B C D; por exemplo, 9 é 1001 porque 9 = 1\cdot 2^3 + 0\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0.

Passo 3

Agrupo os mintermos pelo número de bits iguais a 1 (isso facilita encontrar pares que diferem em um só bit):
Grupo 0 (zero uns): \;0000 (minterm \,0).
Grupo 1 (um 1): \;0010 (minterm \,2).
Grupo 2 (dois 1s): \;1001 (minterm \,9), \;1100 (minterm \,12).
Grupo 3 (três 1s): \;0111 (minterm \,7), \;1101 (minterm \,13).
Grupo 4 (quatro 1s): \;1111 (minterm \,15).
Regra usada: só podem ser combinados vetores que pertençam a grupos adjacentes (diferença de 1 no número de uns), pois eles podem diferir em exatamente um bit.

Passo 4

Faço a primeira rodada de combinações: combino pares de grupos adjacentes que diferem em exatamente um bit. Quando combino dois termos que diferem em um bit, coloco um traço `` -’’ nesse bit; o traço significa “não importa” (variável eliminada).
Combinações possíveis e o que representam (entre chaves os mintermos cobertos):
  • Combinar 0000 ( 0) com 0010 ( 2) difere só em C. Resultado:
    00-0 \quad\text{que cobre}\;\{0,2\}.
  • Combinar 1001 ( 9) com 1101 ( 13) difere só em B. Resultado:
    1-01 \quad\text{que cobre}\;\{9,13\}.
  • Combinar 1100 ( 12) com 1101 ( 13) difere só em D. Resultado:
    110- \quad\text{que cobre}\;\{12,13\}.
  • Combinar 0111 ( 7) com 1111 ( 15) difere só em A. Resultado:
    -111 \quad\text{que cobre}\;\{7,15\}.
  • Combinar 1101 ( 13) com 1111 ( 15) difere só em C. Resultado:
    11-1 \quad\text{que cobre}\;\{13,15\}.
Anotações didáticas:
  • Sempre verificamos se há exatamente uma posição com 0/1 diferente; se sim, substituímos por `` -’’.
  • Cada combinação cobre os mintermos que eram cobertos pelos dois termos originais.

Passo 5

Tento combinar os termos gerados na rodada anterior (segunda rodada). A regra é a mesma: dois termos com traços podem ser combinados se eles diferem em exatamente um bit nas posições que não são já traço e são idênticos nos demais. Ao testar todas as combinações entre:
00-0,\;1-01,\;110-,\;-111,\;11-1
verifica-se que não existe nenhum par que difira em apenas uma posição além das que já são traço. Portanto não há combinações adicionais — isto significa que todos os termos obtidos na primeira rodada são implicantes primos.
Conclusão: os implicantes primos são:
\begin{aligned} P_1 &= 00-0 \quad(\{0,2\}),\\\ P_2 &= 1-01 \quad(\{9,13\}),\\\ P_3 &= 110- \quad(\{12,13\}),\\\ P_4 &= -111 \quad(\{7,15\}),\\\ P_5 &= 11-1 \quad(\{13,15\}). \end{aligned}

Passo 6

Montamos a tabela (prime–implicant chart) que mostra quais implicantes primos cobrem quais mintermos. Colunas = mintermos; linhas = implicantes primos.
Cobertura:
\begin{aligned} P_1(00-0) &:\; 0,\;2\\\ P_2(1-01) &:\; 9,\;13\\\ P_3(110-) &:\; 12,\;13\\\ P_4(-111) &:\; 7,\;15\\\ P_5(11-1) &:\; 13,\;15 \end{aligned}
Tabela (resumo):
\begin{array}{c|ccccccc} & 0 & 2 & 7 & 9 & 12 & 13 & 15\\hline P_1 & \times & \times & & & & & \\\ P_2 & & & & \times & & \times & \\\ P_3 & & & & & \times & \times & \\\ P_4 & & & \times & & & & \times\\\ P_5 & & & & & & \times & \times \end{array}

Passo 7

Identificamos os implicantes primos essenciais: um implicante primo é essencial se existe pelo menos um mintermo que ele cobre e que nenhum outro implicante primo cobre.
Verificando coluna a coluna:
  • Mintermo \,0 é coberto somente por P_1 P_1 é essencial.
  • Mintermo \,2 é coberto somente por P_1 → confirma P_1 essencial.
  • Mintermo \,7 é coberto somente por P_4 P_4 é essencial.
  • Mintermo \,9 é coberto somente por P_2 P_2 é essencial.
  • Mintermo \,12 é coberto somente por P_3 P_3 é essencial.
  • Para os mintermos \,13 e \,15 existem múltiplas coberturas, mas como já selecionamos P_2, P_3 e P_4, todos os mintermos ficam cobertos:
    • 13 é coberto por P_2 e P_3 (já selecionados),
    • 15 é coberto por P_4 (já selecionado).
Portanto, os implicantes essenciais que formam uma cobertura mínima são:
P_1,\;P_2,\;P_3,\;P_4.
O implicante P_5 não é necessário, pois todos os mintermos já estão cobertos pelos essenciais.

Passo 8

Traduzo cada implicante primo selecionado para a forma algébrica usando variáveis literais \,A,B,C,D (lembre: bit 1 corresponde à variável sem barra; bit 0 corresponde à variável negada \overline{\cdot}). A posição dos bits é (A\,B\,C\,D).
  • P_1 = 00-0 significa A=0,\;B=0,\;C=\text{don’t care},\;D=0. Em expressão: \overline{A}\,\overline{B}\,\overline{D}.
  • P_2 = 1-01 significa A=1,\;B=\text{don’t care},\;C=0,\;D=1. Em expressão: A\,\overline{C}\,D.
  • P_3 = 110- significa A=1,\;B=1,\;C=0,\;D=\text{don’t care}. Em expressão: A\,B\,\overline{C}.
  • P_4 = -111 significa A=\text{don’t care},\;B=1,\;C=1,\;D=1. Em expressão: B\,C\,D.
Somando os produtos (OR entre implicantes) obtemos a expressão minimizada final:
S = \overline{A}\,\overline{B}\,\overline{D} \;+\; A\,\overline{C}\,D \;+\; A\,B\,\overline{C} \;+\; B\,C\,D.

Resposta

\displaystyle S=\overline{A}\,\overline{B}\,\overline{D}+A\,\overline{C}\,D+A\,B\,\overline{C}+B\,C\,D

Exercícios relacionados