Aprenda › Tema 2

Álgebra de Boole: leis, De Morgan e simplificação

Leitura de 7 min · Equipe bitGateLab

A álgebra de Boole é a linguagem com que se descrevem e se transformam os circuitos digitais. Cada expressão corresponde a um arranjo de portas, e cada lei que você aplica para simplificá-la se traduz em portas economizadas. Aqui você vai revisar os postulados, as leis mais úteis, os teoremas de De Morgan e como simplificar uma expressão passo a passo, justificando cada movimento.

Variáveis e operações

Uma variável booleana só assume os valores 0 e 1. Há três operações básicas: o complemento (A, porta NOT), o produto lógico (A·B ou AB, porta AND) e a soma lógica (A + B, porta OR). Quando não há parênteses, a ordem de precedência é: primeiro o complemento, depois o produto e por último a soma. Assim, A + BC significa A + (B·C), como na álgebra comum.

Postulados

Toda a álgebra se apoia em alguns poucos postulados. Observe que eles vêm em pares: um para a soma e outro para o produto.

Postulado	Forma com soma	Forma com produto
Elemento neutro	A + 0 = A	A · 1 = A
Comutativo	A + B = B + A	AB = BA
Distributivo	A + BC = (A + B)(A + C)	A(B + C) = AB + AC
Complemento	A + A = 1	A · A = 0

Princípio da dualidade: se uma igualdade é verdadeira, também é verdadeira a que se obtém trocando + por · e 0 por 1 (sem mexer nas variáveis nem nas suas barras). Por isso cada lei tem uma versão "gêmea". Repare na distributiva da soma, A + BC = (A + B)(A + C): ela não existe na álgebra dos números reais, mas aqui é perfeitamente válida.

Leis e teoremas úteis

Dos postulados se deduzem estas regras, que são as que você mais vai usar ao simplificar:

Lei	Forma com soma	Forma com produto
Idempotência	A + A = A	AA = A
Elemento nulo	A + 1 = 1	A · 0 = 0
Involução	A = A
Associativa	A + (B + C) = (A + B) + C	A(BC) = (AB)C
Absorção	A + AB = A	A(A + B) = A
Absorção do complemento	A + AB = A + B	A(A + B) = AB
Adjacência	AB + AB = A	(A + B)(A + B) = A
Consenso	AB + AC + BC = AB + AC	(A + B)(A + C)(B + C) = (A + B)(A + C)

Qualquer uma dessas leis pode ser comprovada com uma tabela-verdade: se as duas colunas coincidem em todas as linhas, a igualdade é verdadeira. Por exemplo, para A + AB = A: com A = 0 os dois lados valem 0, seja qual for o valor de B; com A = 1 os dois valem 1. A absorção do complemento é demonstrada assim: A + AB = (A + A)(A + B) = 1·(A + B) = A + B, usando a distributiva da soma.

Teoremas de De Morgan

Estes dois teoremas dizem como "quebrar" uma barra longa:

A · B = A + B (o complemento de um produto é a soma dos complementos).
A + B = A · B (o complemento de uma soma é o produto dos complementos).

A regra prática: ao partir a barra, troque a operação que estava embaixo dela (· por + ou + por ·) e negue cada termo. Funciona com qualquer quantidade de variáveis: ABC = A + B + C.

A	B	AB	A + B	A + B	AB
0	0	1	1	1	1
0	1	1	1	0	0
1	0	1	1	0	0
1	1	0	0	0	0

Em circuitos, De Morgan diz que uma NAND equivale a uma OR com bolinhas nas entradas, e uma NOR equivale a uma AND com bolinhas nas entradas. É a base para converter qualquer projeto para somente NAND ou somente NOR, como se explica em portas lógicas.

Exemplo 1: aplicar De Morgan. Simplifique F = AB + C.

A barra longa cobre uma soma: AB + C = AB · C.
Quebre a barra do produto: AB = A + B.
Resultado: F = (A + B)C = AC + BC.

Verificação com A = 1, B = 1, C = 0: a expressão original dá 1 + 0 = 0; o resultado dá (0 + 0)·1 = 0. Com A = 0, B = 1, C = 0: original 0 + 0 = 1; resultado (1 + 0)·1 = 1.

Simplificação algébrica passo a passo

Simplificar é reduzir o número de termos e de literais (cada ocorrência de uma variável, negada ou não). Menos literais significa menos entradas de porta. Não existe um algoritmo único com álgebra pura; estas táticas funcionam quase sempre:

Procure pares de termos que diferem em uma única variável e aplique a adjacência.
Coloque o fator comum em evidência e procure um A + A = 1 escondido.
Se um termo está contido em outro, elimine-o por absorção.
Você pode duplicar um termo (idempotência) para combiná-lo com dois vizinhos diferentes.

Exemplo 2. Simplifique F = AB + AB + AB.

Fatore os dois primeiros: AB + AB = A(B + B) = A·1 = A.
Fica F = A + AB.
Absorção do complemento: A + AB = A + B.

F = A + B. Você passou de três portas AND, uma OR de três entradas e dois inversores para uma única OR.

Exemplo 3: função maioria. Simplifique F = ABC + ABC + ABC + ABC.

Por idempotência, ABC = ABC + ABC + ABC. Escreva três cópias para combinar cada uma com um vizinho.
ABC + ABC = BC(A + A) = BC.
ABC + ABC = AC(B + B) = AC.
ABC + ABC = AB(C + C) = AB.

F = AB + AC + BC. Vale 1 quando pelo menos duas das três entradas valem 1: é um circuito de votação. Você verá que é também a saída de carry do somador completo.

Exemplo 4: distributiva da soma. Simplifique F = (A + B)(A + C).

Multiplique: AA + AC + AB + BC = A + AC + AB + BC.
Fatore A: A(1 + C + B) + BC.
Elemento nulo: 1 + C + B = 1, de modo que fica A + BC.

É justamente o postulado distributivo da soma lido ao contrário.

Erros comuns

Aplicar De Morgan sem trocar a operação: AB não é AB, é A + B.
"Cancelar" termos como na álgebra comum. Em Boole não existem subtração nem divisão: de A + B = A + C não se conclui que B = C.
Esquecer a precedência: A + BC não é (A + B)C.
Quebrar apenas uma parte de uma barra longa. A barra de AB + C afeta toda a soma; trabalhe da barra mais externa para dentro.
Parar cedo demais. Depois de cada passo, verifique se sobrou algo que possa ser absorvido ou um termo de consenso redundante.

Experimente no simulador

Uma simplificação correta produz um circuito com exatamente a mesma tabela-verdade do original. O simulador permite comprovar isso sem fazer a tabela à mão.

Monte no editor o circuito original de um exemplo, como AB + AB + AB, com suas entradas e sua saída.
Gere a tabela-verdade dele e anote-a.
Em outra saída do mesmo desenho, monte a versão simplificada (A + B) com as mesmas entradas.
Mude as entradas por todas as combinações e observe que as duas saídas sempre coincidem.
Peça a expressão simplificada a partir da tabela e compare-a com a que você obteve à mão.

Exercícios

Simplifique F = AB + AB + AB.
Resposta
AB + AB = A. Em seguida, A + AB = A + B (absorção do complemento). F = A + B = AB: é uma NAND.
Simplifique F = A + B.
Resposta
De Morgan: A · B = AB.
Simplifique F = A(A + B) + B(B + C).
Resposta
Por absorção, A(A + B) = A e B(B + C) = B. F = A + B.
Demonstre o teorema do consenso: AB + AC + BC = AB + AC.
Resposta
Escreva BC = BC(A + A) = ABC + ABC. Então AB + ABC = AB (absorção) e AC + ABC = AC (absorção). Fica AB + AC.