Álgebra de Boole e Funções Lógicas

Introdução

Vimos, no artigo anterior, as tabelas da verdade e as operações que podemos realizar. Agora, vamos espreitar o estudo da álgebra de Boole e funções lógicas pois, na realidade, o que encontramos no mundo dos circuitos digitais, são circuitos com várias entradas e com uma saída (ou mais), cujo valor irá depender dos valores de entrada.

Imagine-se um controlador do motor de um elevador. A saída do controlador, para colocar o motor em marcha para subir, deverá ficar activa (a 1) quando se verificarem as condições, ou estados:

• Um botão de chamada para um dos pisos superiores foi actuado
• O elevador estiver parado
• A porta do elevador estiver fechada
• Entre outros (estamos a simplificar)

Assim, e ainda de forma simplificada, se considerarmos uma função “F” para o nosso motor, e as entradas A, B e C, em que:

• “A” indica se um botão de chamada foi actuado;
• “B” indica se o elevador está em movimento e
• “C” se a porta está aberta.

Podemos definir a função como:

f(a,b,c) = a  . b . c

Esta função é uma função lógica e poderá ser lida como “F” igual a “A” AND (NOT “B”) AND (NOT “C”), e como só temos operadores AND, facilmente concluimos que “F” é apenas verdade (F = 1) quando:

• A = 1 (o botão de chamada está a ser actuado)
• B = 0 (O elevador não está em movimento)
• C = 0 (O elevador não tem a porta aberta)

A seguinte tabela mostra-nos os operadores que encontramos nestes funções e as respectivas funções lógicas.

A . B , A x B, AB	A AND B
A + B	A OR B
A ⊕ B	A XOR B
A	NOT A

Considere-se agora que temos uma função lógica definida por:

f(a,b,c) = a + (b ⊕ c)

Note que temos uma operação entre parêntesis, pelo que terá que ser executada primeiro. Determinemos os valores possíveis de “F” de acordo com a seguinte tabela:

A	B	C	C	B ⊕ C	F = A + (B ⊕ C)
0	0	0	1	1	1
0	0	1	0	0	0
0	1	0	1	0	0
0	1	1	0	1	1
1	0	0	1	1	1
1	0	1	0	0	1
1	1	0	1	0	1
1	1	1	0	1	1

Repare que introduzimos todas as combinações possíveis das variáveis de entrada A, B e C, determinámos “NOT C”, em seguida vimos os resultados de B ⊕ C ( B XOR (NOT C)) e, finalmente, fizemos o OR entra a entrada “A” e o resultado do XOR, obtendo todos os valores possíveis de F.

Note ainda que, estando nós a trabalhar com o mundo digital, ou seja, com números binários, o domínio de qualquer função booleana é sempre o conjunto {0.1} e o contra-domínio estará também contido neste conjunto.

Propriedades da álgebra de Boole

Vamos agora conhecer algumas propriedades da álgebra de Boole, onde iremos encontrar semelhanças com a nossa álgebra comum. Já agora, e como acontece com o produto e a divisão, a operação AND tem sempre prioridade em relação ao OR. Mas lembre-se que os símbolos + e . (ou x) não significam aqui uma soma ou uma multiplicação mas sim as operações lógicas OR e AND! Lembre-se ainda que estamos num domínio binário, de 0’s e 1’s.

Propriedades das operações AND e OR:
Associativa do AND	A . (B . C) = (A . B) . C
Associativa do OR	A + (B + C) = (A + B) + C
Comutativa do AND	A . B = B . A
Comutativa do OR	A + B = B + A
Distributiva do AND sobre o OR	A . (B + C) = (A . B) + (A . C)
Distributiva do OR sobre o AND	A + (B . C) = (A + B) . (A + C)
Absorção no AND	A . (A + B) = A
Absorção no OR	A + (A . B) = A
Elemento netutro no AND	A . 1 = A
Elemento neutro no OR	A + 0 = A
Elemento absorvente no AND	A . 0 = 0
Elemento absorvente no OR	A . 1 = 1
Elemento complementar no AND	A . A = 0
Elemento complementar no OR	A + A = 1
Idempotência no AND	A x A = A
Idempotência no OR	A + A = A
Dupla negação	A = A

Podemos encontrar algumas propriedades estranhas, como a distributiva da operação OR (+) com o AND (.), pois na álgebra comum não existe nenhuma propriedade distributiva da soma em relação à multiplicação. Mas não estamos na nossa álgebra comum, estamos em álgebra de Boole e todas estas propriedades podem ser demonstradas.

Relativamente à operação XOR, temos algumas destas propriedades como válidas também, especialmente a comutativa e a associativa. Vamos ver algumas propriedades e transformações específicas desta operação:

• A ⊕ A = 0 ; A ⊕ 0 = A
• A ⊕ A = 1 ; A ⊕ 1 = A (lembre-se do exemplo com o XOR no artigo anterior)
• A ⊕ B = (A . B) + (A . B)
• A ⊕ B = (A . B) . (A + B)

Vamos demonstrar a penúltima transformação, recorrendo às tabelas da verdade:

A	B	A ⊕ B	B	A . B	A	A . B	A . B + A . B
0	0	0	1	0	1	0	0
0	1	1	0	0	1	1	1
1	0	1	1	1	0	0	1
1	1	0	0	0	0	0	0

Tente demonstrar a última transformação.

Leis de De Morgan

As leis de De Morgan (ou apenas leis de Morgan) são muito conhecidas no mundo dos circuitos digitais. Com elas, facilmente podemos encontrar circuitos equivalentes e/ou simplificar funções lógicas.

Temos então, segundo De Morgan, as seguintes equivalências:

• A . B = A + B
• A + B = A . B

Vamos demonstrar a primeira lei de Morgan usando tabelas da verdade:

A	B	A . B	A . B	A	B	A + B
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Tente demonstrar a segunda lei de Morgan.

Próximo artigo

Referências:

• Wikipedia: Boolean algebra

Este artigo foi escrito com a antiga grafia.