Um breve curso de Álgebra Booleana

24/10/2023

Um breve curso de Álgebra Booleana

Sumário:

Aqui está um pequeno guia para ajudá-lo a encontrar os tópicos mencionados neste post:

O que é Álgebra Booleana

Em linhas gerais Álgebra Booleana é um importante ramo da Álgebra, diferenciando-se de outras concepções de álgebra por fazer uso de operadores lógicos em lugar dos convencionais operadores aritméticos (que simbolizam, por exemplo, adição e muliplicação), bem como por adotar variáveis que assumem valores “verdadeiro” ou “falso”, em lugar de outras noções, como números e vetores.

A Álgebra Booleana foi primeiramente introduzida pelo matemático inglês George Boole (1815-1864), em meados do século XIX, como uma forma de sistematizar de maneira matemática e operacional, princípios da lógica proposicional e da análise dos valores de proposições lógicas. Desta forma, expressões e sentenças da lógica proposicional clássica possuem equivalentes na Álgebra Booleana, podendo-se utilizar a última para o cálculo (mais para avaliação) de tais expressões. Posteriormente a definição de Álgebra Booleana seria extendida por outros matemáticos, se tornando mais moderna e abstrata na forma de uma estrutura matemática, possuindo relação com a noção matemática de reticulados, como pode ser visto em contextos de Álgebra Abstrata.

Por que usamos Álgebra Booleana

Agora falando um pouco sobre os principais usos da Álgebra Booleana, além das motivações já citadas, uma das mais conhecidas aplicações de tal álgebra é no estudo e análise de circuitos elétricos bi-estáveis, como os circuitos lógicos, que constituem parte imprescindível de sistemas eletrônicos e computadores modernos. Para tal aplicação faz-se uso de um tipo especial de Álgebra Booleana, que será tema dos próximos tópicos, conhecida como “Álgebra Booleana de dois valores”.

Definições Formais

A Álgebra Booleana de dois valores

Uma álgebra booleana é definida como uma estrutura que contemple um conjunto de valores base, duas operações binárias, as quais convencionamos chamar de “E” e “Ou”, e dois valores pertencentes ao conjunto inicial que são responsáveis por representar “verdadeiro” e “falso”. Já no caso da Álgebra Booleana de dois valores, o conjunto base de valores nada mais será do que um conjunto contendo os números 0 e 1, que servirão também para representar os valores de “falso” e “verdadeiro”, respectivamente. Neste texto operações “Ou” serão representadas com o sinal + (ou seja, A Ou B será representado como A + B), enquanto operações “E” serão representadas com a multiplicação dos valores (ou seja A E B será representado como AB ou A·B, enquanto a operação será representada por ·).

Além disso, qualquer álgebra booleana deverá obedecer às seguintes condições (axiomas):

  1. (a) Fechamento com respeito à operação Ou (ou seja, ao realizar a operação Ou com dois elementos do conjunto base da álgebra, seu resultado também deve estar em tal conjunto);

    (b) Fechamento com respeito à operador E.

  2. (a) Deve existir no conjunto base um elemento identidade para a operação Ou (que no caso é o 0, pois 1 + 0 = 0 + 1 = 1 e também 0 + 0 = 0 + 0 = 0);

    (b) Deve existir no conjunto base um elemento identidade para a operação E (que no caso é o 1, pois 1 · 1 = 1 · 1 = 1 e também 0 · 1 = 1 · 0 = 0).

  3. Comutatividade com respeito a ambas as operações, isto é, x + y = y + x e x·y = y·x.

  4. Distributividade da operação E sobre operações Ou e vice-versa, isto é, x·(y+z) = x·y + x·z e x + (y·z) = (x + y)·(x + z).

  5. Para todo elemento no conjunto base, digamos x ∈ B, existe um elemento x' ∈ B - que chamamos de complemento de x -, que obedece às propriedades:

    (a) x + x' = 1 (ou seja, se x é verdadeiro, x' é falso);

    (b) x · x' = 0 (novamente, se x é verdadeiro, x' é falso).

  6. Existem no mínimo dois elementos distintos no conjunto base.

No caso da álgebra de dois valores, o conjunto base será formado apenas pelos elementos 1 e 0, sendo suficiente para obedecer a tais condições, como é possível verificar. Assim, quando dizemos que um valor x pertence à álgebra booleana, significa que seu valor poderá ser um dos dois: 1 ou 0, de modo que x' assumirá o outro valor.

Tabelas Verdade

Para visualizar melhor como as operações da Álgebra Booleana de dois valores se comportam mediante os valores disponíveis, dispomos de um método chamado “Tabela Verdade”, em que representamos as variáveis envolvidas em uma operação nas primeiras colunas e o resultado da operação na coluna final, utilizando as linhas para descrever cada possibilidade de valor para cada variável, que, no caso, assumem os valores 0 ou 1.

Montando a tabela verdade da operação “E”, obtemos:

x y xy
0 0 0
0 1 0
1 0 0
1 1 1

Já para a tabela verdade da operação “Ou”, obtemos:

x y x + y
0 0 0
0 1 1
1 0 1
1 1 1

Enquanto a representação do valor complementar fica:

x x'
0 1
1 0

Propriedades e Teoremas

A Dualidade

Importante conceito das diversas álgebras booleanas possíveis, o Princípio da Dualidade afirma que qualquer expressão álgebrica construída em uma álgebra booleana, e que siga os axiomas anteriormente discutidos, é equivalente à expressão obtida ao trocar as operações “E” por “Ou” e vice-versa, e as identidades de cada operação, sendo tal expressão chamada de expressão dual. No caso da Álgebra Booleana de dois valores, fazemos isso ao trocar os sinais + e · de uma expressão por · e +, bem como por trocar os 1’s por 0’s.

Exemplo: A expressão (x + y)·z possui como expressão dual x·y + z.

Teoremas

A seguir estão alguns teoremas que são válidos para a Álgebra Booleana de dois valores, representados juntamente de sua versão dual. A demonstração dos teoremas recai essencialmente no uso dos axiomas das álgebras booleanas, e ficam de exercício para o leitor interessado. Também pode ser interessante montar as tabelas verdade dos teoremas, para melhor visualização de suas propriedades.

Teorema 1:

x + x = x, e seu dual x · x = x.

Teorema 2:

x + 1 = 1, e seu dual x · 0 = 0.

Teorema 3 (Involução):

(x')' = x.

Teorema 4 (Associatividade):

x + (y + z) = (x + y) + z, e seu dual x(yz) = (xy)z.

Teorema 5 (Leis de Morgan):

(x + y)' = x’y', e seu dual (xy)' = x' + y'.

Teorema 6 (Absorção):

x + xy = x, e seu dual x(x + y) = x.

Funções Booleanas

Funções Booleanas, tais quais outras funções matemáticas, são expressões formadas por variáveis pertencentes ao conjunto base da álgebra booleana em questão, podendo assumir diversos valores a depender dos valores assumidos individualmente por cada variável. No caso das álgebras booleanas de dois valores, suas variáveis assumem o valor 1 ou o valor 0.

Exemplo: Uma Função Booleana poderia ser F(x, y, z) = xyz', cujos valores poderiam ser representados por uma tabela verdade, por exemplo. Neste caso, se x = 1, y = 1 e z = 0, o valor calculado seria: F(1, 1, 0) = 1 · 1 · (0)' = 1 · 1 · 1 = 1.

Funções Booleanas de destaque

Algumas Funções Booleanas recebem nomes especiais, tendo como base os valores que estas assumem em relação à suas variáveis. A seguir temos uma tabela que reúne algumas delas:

Nome Funções Booleanas Efeitos
Complemento (NOT) F = x' Resulta no complemento de x
E (AND) F = xy Resulta em x E y
Ou (OR) F = x + y Resulta em x Ou y
Ou exclusivo (XOR) F = xy' + x’y Resulta em 1 se x = 1 ou y = 1, mas não ambos ao mesmo tempo.
Negação do E (NAND) F = (xy)' Resulta no complemento de x E y
Negação do Ou (NOR) F = (x + y)' Resulta no complemento de x Ou y
Negação exclusiva do Ou (XNOR) F = xy + x’y' Resulta na versão exclusiva do NOR
Implicação F = x' + y Resulta em “Se x, então y”
Restrição F = xy' Resulta em “x mas não y”

Deduzindo Fórmulas para Funções Booleanas

Agora que já vimos algumas propriedades das Funções Booleanas e também de suas operações básicas, um importante aspecto que devemos investigar consiste em como encontrar Funções Booleanas que correspondam com resultados esperados para cada valor de cada variável envolvida. Com o auxílio dessas técnicas, podemos modelar o comportamento da função para cada valor de suas variáveis usando tabelas verdade, e a partir disso montar sua Função Booleana equivalente com razoável facilidade.

Soma dos Termos Mínimos

Consideremos uma variável pertencente a uma álgebra booleana de dois valores. Naturalmente, tal variável pode se apresentar em sua forma “normal”, digamos x, ou em sua forma complementar, x', de modo que, se analisarmos as possíveis expressões que uma operação “E” entre duas variáveis booleanas podem assumir, obtemos as seguintes expressões: xy, x’y, xy' e x’y', em que x e y representam tais variáveis consideradas. Note que consideramos o valor “normal” de cada variável e também sua forma complementar, sendo ambas relevantes na verificação de todas as possibilidades. A cada uma dessas expressões obtidas damos o nome de “Termo Mínimo”, ou, em inglês, “Minterm”, ou, ainda, “Produto Padrão” (por sua representação lembrar uma multiplicação). Extendendo essa noção, podemos obter expressões dos Termos Mínimos de qualquer conjunto de variáveis booleanas que desejarmos, sempre lembrando de realizar operações “E” entre as possíveis variáveis e considerar seus valores complementares.

Exemplo: Se tivermos uma Função Booleana de 3 valores, digamos, F(x, y, z), os Termos Mínimos de suas variáveis serão dados pelas expressões: xyz, xyz', xy’z, x’yz, xy’z', x’yz', x’y’z e x’y’z'.

De modo geral podemos saber de antemão a quantidade de Termos Mínimos de um conjunto de n variáveis, bastando realizar o cálculo de 2 elevado à potência de n (Por que será? Tente verificar por si mesmo).

Agora resta a pergunta, “Como Termos Mínimos podem auxiliar na dedução de Funções Booleanas?”. A resposta é mais simples do que parece, porém não tão trivial. Existe uma propriedade da Álgebra Booleana de dois valores que afirma ser possível expressar qualquer Função Booleana como várias operações “Ou” (ou Somas) realizadas entre os Termos Mínimos das variáveis envolvidas. Para fazer uso dessa propriedade utilizamos o método da “Soma dos Termos Mínimos”.

Após a montagem da tabela verdade com os valores esperados da função desejada para cada um dos possíveis valores das variáveis, selecionamos apenas as linhas da tabela verdade em que a Função possui valor 1.

Uma vez encontradas todas as linhas/combinações de variáveis, basta analisarmos os valores de cada variável em cada uma de tais linhas e compor expressões de “Termos Mínimos” com cada uma delas. Se o valor de uma variável numa das linhas selecionadas for 1, escrevemos a própria variável, já se for 0, colocamos seu complementar.

De posse de todos os Termos Mínimos envolvidos, realizamos operações “Ou” (que é representado com + “como se fosse” uma soma) entre cada um deles e obteremos a dedução da função desejada, concluindo o método.

O texto ainda está um pouco abstrato, vejamos um exemplo:

Se a tabela verdade da função desejada for:

x y z F(x, y, z)
0 0 0 0
0 0 1 1
0 1 0 0
1 0 0 1
0 1 1 1
1 0 1 0
1 1 0 1
1 1 1 0

Podemos ver que as segunda, quarta, quinta e sétima linhas têm a função com valor final 1. Assim, precisamos montar os Termos Mínimos para essas linhas:

  • Para a segunda linha, temos x = 0, y = 0 e z = 1, logo, seu termo mínimo correspondente será: x’y’z;
  • Para a quarta linha, temos x = 1, y = 0 e z = 0, logo, seu termo mínimo correspondente será: xy’z';
  • Para a quinta linha, temos x = 0, y = 1 e z = 1, logo, seu termo mínimo correspondente será: x’yz;
  • Para a sétima linha, temos x = 1, y = 1 e z = 0, logo, seu termo mínimo correspondente será: xyz'.

Desta forma, a expressão desejada será formada ao realizarmos a operação “Ou” entre cada um dos Termos Mínimos:

F(x, y, z) = x’y’z + xy’z' + x’yz + xyz'

Que será a expressão final.

Produto dos Termos Máximos

De forma análoga aos Termos Mínimos, podemos desenvolver o conceito Termos Máximos, ou Maxterms, do inglês, ou ainda, “Somas Padrão”, que podem ser obtido da mesma forma que os Termos Mínimos, diferindo-se no fato de que no lugar de operações “E” entre cada uma das n variáveis, temos operações “Ou”. No exemplo a seguir, similar ao realizado com os Termos Mínimos, investigaremos mais sobre os Termos Máximos:

Exemplo: Seja a Função Booleana de 3 valores F(x, y, z), os Termos Máximos de suas variáveis serão dados pelas expressões: (x + y + z), (x + y + z'), (x + y' + z), (x' + y + z), (x + y' + z'), (x' + y + z'), (x' + y' + z) e (x' + y' + z'). Como podemos observar, são as versões duais das expressões obtidas no exemplo anterior.

Semelhante à propriedade utilizada com os Termos Mínimos, podemos utilizar os Termos Máximos para escrever qualquer Função Booleana, só que desta vez, utilizaremos o método do “Produto dos Termos Máximos”. Em tal método, percorremos a tabela verdade em busca das linhas/combinações de valores das variáveis envolvidas, que resultem em valor da Função igual a 0.

De posse das linhas, escrevemos as expressões dos Termos Máximos substituindo variáveis de valor 1 na linha, por seu valor normal, e variáveis de valor 0 na linha, por seu complementar, unindo as variáveis por operações “Ou” encadeadas (como fazemos com os Termos Máximos).

Tendo todas as combinações, realizamos o produto das expressões obtidas, isto é, realizamos a operação “E” entre cada uma das expressões, obtendo a função desejada.

Deduzindo a expressão do exemplo da seção anterior com o método do “Produto dos Termos Máximos”, teríamos o seguinte processo:

Seja a tabela verdade da função desejada dada por:

x y z F(x, y, z)
0 0 0 0
0 0 1 1
0 1 0 0
1 0 0 1
0 1 1 1
1 0 1 0
1 1 0 1
1 1 1 0

Podemos ver que as primeira, terceira, sexta e oitava linhas têm a funão com valor final 1. Assim, precisamos montar os Termos Máximos para essas linhas:

  • Para a primeira linha, temos x = 0, y = 0 e z = 0, logo, seu termo mínimo correspondente será: x' + y' + z';
  • Para a terceira linha, temos x = 0, y = 1 e z = 0, logo, seu termo mínimo correspondente será: x' + y + z';
  • Para a sexta linha, temos x = 1, y = 0 e z = 1, logo, seu termo mínimo correspondente será: x + y' + z;
  • Para a sétima linha, temos x = 1, y = 1 e z = 1, logo, seu termo mínimo correspondente será: x + y + z.

Desta forma, a expressão desejada será formada ao realizarmos a operação “E” entre cada um dos Termos Máximos:

F(x, y, z) = (x' + y' + z')(x' + y + z')(x + y' + z)(x + y + z)

Que será a expressão desejada.

Conclusão

Chegamos ao fim deste - não tão - breve curso de Álgebra Booleana, com ênfase em Álgebra Booleana de dois valores. Espero que tenha gostado e quem sabe aprendido algo novo sobre esta parte tão importante para a análise de expressões lógicas e, posteriormente, para a análise de circuitos lógicos. Para descobrir mais detalhes sobre esse ramo da Álgebra, recomendo dar uma olhada nos livros presentes nas Referências, ambos em inglês. O primeiro livro é mais matemático e abstrato, proporcionando uma visão mais técnica, enquanto o segundo é mais voltado para cursos de engenharia, tendo explicações mais simples e mais concretas, além de menos provas e/ou provas simplificadas de alguns teoremas.

Referências

  • Livro “Abstract Algebra: Theory and Applications”, de Thomas W. Judson, disponível gratuitamente em: http://abstract.ups.edu/

  • Livro “Digital Logic and Computer Design”, de M. Morris Mano.


Comentarios: