Aprenda › Tema 3

Tabelas-verdade e formas canônicas: Σm e ΠM

Leitura de 8 min · Equipe bitGateLab

Quase todos os problemas de projeto digital começam com um enunciado em palavras ("o alarme toca se...") que se converte em uma tabela-verdade. O passo seguinte é tirar dessa tabela uma equação que você possa construir com portas. Aqui você vai aprender o método sistemático para fazer isso: os mintermos e maxtermos, as formas canônicas de soma de produtos e produto de somas, e a notação compacta Σm e ΠM usada nos livros, nos simuladores e nos mapas de Karnaugh.

Como se ordena uma tabela-verdade

Com n variáveis há 2ⁿ linhas. Elas são escritas em ordem binária crescente, com a primeira variável como bit mais significativo. Assim, cada linha fica identificada por um número decimal: em uma tabela de A, B e C, a linha A = 1, B = 0, C = 1 é a 101₂ = 5. Esse número é o que você vai usar como índice de mintermo ou maxtermo, portanto a ordem das variáveis importa: se você muda a ordem, mudam os números.

Mintermos e soma de produtos

Um mintermo é um produto (AND) que contém todas as variáveis, cada uma delas uma única vez, negada ou não. Ele é montado assim: a variável que vale 1 naquela linha vai sem barra e a que vale 0 vai com barra. O mintermo vale 1 unicamente na sua linha e 0 em todas as outras. É chamado de m_i, em que i é o número da linha.

Linha	A	B	C	Mintermo	Maxtermo
0	0	0	0	m₀ = ABC	M₀ = A + B + C
1	0	0	1	m₁ = ABC	M₁ = A + B + C
2	0	1	0	m₂ = ABC	M₂ = A + B + C
3	0	1	1	m₃ = ABC	M₃ = A + B + C
4	1	0	0	m₄ = ABC	M₄ = A + B + C
5	1	0	1	m₅ = ABC	M₅ = A + B + C
6	1	1	0	m₆ = ABC	M₆ = A + B + C
7	1	1	1	m₇ = ABC	M₇ = A + B + C

Se você soma (OR) os mintermos de todas as linhas em que a função vale 1, obtém uma equação que vale 1 exatamente nessas linhas. Essa é a soma de produtos canônica (SOP, da sigla em inglês) ou primeira forma canônica. Em notação compacta, escreve-se F = Σm(lista de linhas com 1).

Maxtermos e produto de somas

Um maxtermo é uma soma (OR) que contém todas as variáveis. A regra é a oposta: a variável que vale 0 na linha vai sem barra e a que vale 1 vai com barra. Um maxtermo vale 0 unicamente na sua linha. É chamado de M_i (com M maiúsculo).

Se você multiplica (AND) os maxtermos de todas as linhas em que a função vale 0, obtém uma equação que vale 0 exatamente ali e 1 no restante: o produto de somas canônico (POS) ou segunda forma canônica. Escreve-se F = ΠM(lista de linhas com 0).

O mintermo e o maxtermo da mesma linha são complementos: m_i = M_i. Por isso, se você conhece a lista Σm de uma função, a lista ΠM é formada por todos os números que não aparecem nela.

Exemplo 1: da tabela às duas formas. Uma função de três variáveis vale 1 nas linhas 1, 3, 6 e 7.

#	A	B	C	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

Notação compacta: F = Σm(1, 3, 6, 7) = ΠM(0, 2, 4, 5).
Soma de produtos canônica: F = ABC + ABC + ABC + ABC.
Produto de somas canônico: F = (A + B + C)(A + B + C)(A + B + C)(A + B + C).
Simplifique a SOP: ABC + ABC = AC e ABC + ABC = AB. Assim, F = AC + AB.

Verificação na linha 5 (A = 1, B = 0, C = 1): AC = 0 e AB = 0, portanto F = 0, como na tabela.

Qual forma é mais conveniente?

As duas formas descrevem a mesma função, mas não têm o mesmo tamanho. Use a que tiver menos termos: se a função tem poucos uns, a Σm é mais curta; se tem poucos zeros, a ΠM é mais curta. Com 8 linhas, uma função com 2 uns tem uma SOP de 2 termos e uma POS de 6.

A implementação também importa. Uma soma de produtos é montada com portas AND que alimentam uma OR, e essa estrutura de dois níveis se converte diretamente em NAND-NAND. Um produto de somas é montado com portas OR que alimentam uma AND, e se converte em NOR-NOR.

Exemplo 2: do enunciado à equação. Um tanque tem três sensores de nível: A (baixo), B (médio) e C (alto). Cada sensor dá 1 quando a água o alcança. Uma lâmpada de "nível inválido" deve acender quando a combinação é fisicamente impossível: um sensor mais alto ativo com um mais baixo inativo.

Combinações válidas (ABC): 000, 100, 110, 111. Ou seja, linhas 0, 4, 6 e 7.
A lâmpada acende nas demais: F = Σm(1, 2, 3, 5).
Equivalente: F = ΠM(0, 4, 6, 7).
Simplifique: m₁ + m₃ = AC, m₁ + m₅ = BC, m₂ + m₃ = AB. Usando m₁ e m₃ duas vezes (idempotência), F = BC + AB.

Confira: a linha 1 (001) dá BC = 1; a linha 2 (010) dá AB = 1; a linha 3 (011) dá AB = 1; a linha 5 (101) dá BC = 1. Em 000, 100, 110 e 111 os dois termos valem 0. Lê-se "C ativo sem B" ou "B ativo sem A".

O complemento de uma função

Se F = Σm(1, 3, 6, 7), seu complemento vale 1 onde F vale 0: F = Σm(0, 2, 4, 5). Isso é útil quando você quer a POS simplificada: simplifica F como soma de produtos e depois aplica De Morgan. Por exemplo, F = AC + AB (confira com as linhas 0, 2, 4 e 5), e ao complementar fica F = (A + C)(A + B). Se você multiplica: AB + AC + BC, e pelo consenso isso é AB + AC, o mesmo resultado do exemplo 1.

Para se aprofundar nessas manipulações, revise a álgebra de Boole; para simplificar de forma gráfica, continue com os mapas de Karnaugh.

Erros comuns

Inverter a regra das barras: nos mintermos o 0 leva barra; nos maxtermos é o 1 que leva barra.
Colocar em ΠM as linhas em que a função vale 1. ΠM lista os zeros, Σm lista os uns.
Mudar a ordem das variáveis entre a tabela e a equação. Com a ordem C, B, A a linha "5" já não é a mesma.
Esquecer uma variável em um termo canônico. Um mintermo de quatro variáveis sempre tem quatro literais; se tem menos, já está simplificado e não é canônico.

Experimente no simulador

O módulo de tabela-verdade permite inserir uma função linha por linha e ver de imediato suas formas canônicas e a equação simplificada, de modo que você pode conferir cada passo feito à mão.

Crie uma tabela de três entradas e uma saída.
Marque com 1 as linhas 1, 3, 6 e 7 do exemplo 1 e deixe o restante em 0.
Observe as expressões Σm e ΠM geradas e compare-as com as suas.
Converta a tabela em circuito e mude as entradas para confirmar que a saída segue a tabela.
Repita com o problema do tanque e verifique se a lâmpada acende somente nas combinações impossíveis.

Exercícios

Escreva o mintermo m₉ e o maxtermo M₉ de uma função de quatro variáveis A, B, C, D.
Resposta
9 = 1001. m₉ = ABCD e M₉ = A + B + C + D.
Se F(A, B, C) = Σm(0, 1, 5), escreva F em notação ΠM.
Resposta
F = ΠM(2, 3, 4, 6, 7).
Obtenha a soma de produtos canônica de uma função de duas variáveis que vale 1 somente quando A e B são iguais, e simplifique-a se for possível.
Resposta
F = Σm(0, 3) = AB + AB. Não se reduz: é a XNOR.
Escreva o produto de somas canônico de F(A, B, C) = Σm(1, 2, 3, 4, 5, 6, 7).
Resposta
Só vale 0 na linha 0, portanto F = ΠM(0) = A + B + C. Uma única OR de três entradas.