ÁLGEBRA BOOLEANA

É um recurso matemático para se expressar, analisar e projetar circuitos lógicos. É uma linguagem especial dos circuitos lógicos digitais.  

Um sistema matemático composto por operadores, regras, postulados e teoremas.  Usa funções e variáveis, como na álgebra convencional, que pode assumir apenas um dentre dois valores, 0 (zero), ou 1 (um).  Trabalha com sete operadores básicos AND, OR, NOT, NAND, NOR, EXOR e EXNOR.  Os operadores AND e OR correspondem, respectivamente, às operações de intersecção e união da teoria dos conjuntos.

Uma Expressão Booleana é uma equação que define a saída de um circuito lógico.

A Álgebra Booleana é muito útil no projeto de circuitos lógicos, pois sua aplicação resulta sempre em circuitos que são os mais simples, mais baratos, mais eficientes e mais confiáveis (MTBF maior).  MTBF= Mean Time Between Failures (em inglês) – tempo médio entre falhas.

Postulados (axiomas) booleanos:

São sentenças ou proposições que não são provadas ou demonstradas e são consideradas como verdadeiras, óbvias, ou como um consenso inicial necessários para a construção, ou aceitação de uma teoria.

• P1: X = 0, ou X = 1
• P2: 0 . 0 = 0 
• P3: 1 + 1 = 1 
• P4: 0 + 0 = 0 
• P5: 1 . 1 = 1 
• P6: 1 . 0 = 0 . 1 = 0 
• P7: 1 + 0 = 0 + 1 = 1

Teoremas booleanos:

São sentenças ou proposições ou afirmações que devem ser provadas.

• T1 : Propriedade Comutativa

• T2 : Propriedade Associativa

• T3 : Propriedade Distributiva

• T4 : Identidade

• T5 :

• T6 : Redundância

• T7 :

• T8 :

• T9 :

• T10 :

• T11 : Teorema de Morgan

Tabela da Verdade:

É um mapa onde são colocadas todas as possíveis interpretações (situações, combinações) de um sistema lógico, com seus respectivos resultados para uma expressão booleana qualquer.

Em geral, para N variáveis booleanas de entrada, há 2^N interpretações (combinações) possíveis.

Uma tabela da verdade representa o comportamento tanto do circuito como de sua expressão característica.

1) Tabela da Verdade obtida a partir de  Expressão Booleana

Uma das maneiras de se fazer o estudo de uma função booleana é a utilização da tabela da verdade. Para extrair a tabela da verdade de uma expressão devem-se seguir alguns passos:

a)    Montar o quadro de possibilidades;

b)    Montar colunas para os vários membros da equação;

c)    Preencher estas colunas com os seus resultados;

d)    Montar uma coluna para o resultado final e;

e)    Preencher esta coluna com os resultados finais.

Ilustração:

   Vamos utilizar a seguinte expressão booleana:

Observa-se que a expressão contém 4 variáveis de entrada: A, B, C e D,logo, existem 2⁴ = 16 possibilidades de combinação de entrada.

Portanto, monta-se o quadro de possibilidades com 4 variáveis de entrada, três colunas auxiliares, sendo uma para cada membro da expressão, e uma coluna para o resultado final.

2) Expressão Booleana obtida de Tabela da  Verdade

Obter expressões e circuitos a partir de Tabelas da Verdade, sendo este método mais comum de projetos práticos, pois, geralmente, necessita-se representar situações através de Tabela da Verdade e a partir destas, obter a expressão booleana e consequentemente, o circuito lógico correspondente.

     Ilustração:

     Vamos utilizar a seguinte Tabela da Verdade:

   Observa-se S=1 na tabela e monta-se a expressão correspondente adequada.

  Para obtermos a expressão final basta executar a soma booleana de cada termo     acima:

  Nota-se que o método permite obter, de qualquer tabela da verdade, uma     expressão padrão formada sempre pela soma de produtos.

Portas Lógicas

Os sistemas digitais são baseados em portas lógicas: AND, OR, NOT, NAND, NOR, EXOR, EXNOR.

a) Porta AND

b) Porta OR

c) Porta NOT

Exemplos de implementação de porta NOT utilizando (neste caso) uma porta NAND.

    

d) Porta NAND

e) Porta NOR

     

f) Porta EXOR

g) Porta EXNOR

               Blocos Lógicos Equivalentes:    

Mapa de Karnaugh (Diagrama de Karnaugh)

É utilizado para simplificar uma equação lógica ou para converter uma tabela da verdade para o circuito lógico correspondente.

O método de leitura por "Mapa de Karnaugh" é considerado mais simples que a "álgebra booleana", pois elimina o problema de erro nas simplificações. Porém quando utilizado mais de 6 entradas, esse método se torna complicado, pois fica difícil identificar as células adjacentes no mapa.

Roteiro de simplificação passo-a-passo.

1)  Mapear a tabela da verdade. 

Isto é, construir o Mapa de Karnaugh.  Colocando os 1’s nos quadros que correspondem aos 1’s na Tabela da Verdade e preencher com 0’s o restante dos espaços que sobraram.  Em outras palavras, transferir os dados da tabela da verdade para o Mapa de Karnaugh.

2)  Uma vez que a tabela da verdade esteja mapeada, é preciso agrupar as regiões. Para isso, devem-se considerar os seguintes aspectos:

·      A resolução de um mapa pode ser realizada por saídas iguais a 1 (um), ou a 0 (zero), mas, é mais comum considerar saídas iguais a 1 (um).

·      Um enlace – agrupamento de células adjacentes, com saídas iguais, do qual se pode extrair diretamente uma expressão booleana simplificada – envolvendo uma única célula não resulta em simplificação. Quando não são possíveis enlaces envolvendo mais de uma célula, significa que a expressão não pode ser simplificada algebricamente.

·      Quanto maior o enlace, menor o termo correspondente e, portanto, mais simplificada fica a expressão booleana do Mapa de Karnaugh considerado; e mais simples, com menor probabilidade de falhas, mais barato, será o circuito eletrônico (ou elétrico) a ser montado.

·      Dois enlaces podem ter uma célula em comum.

·      Quanto menor o número de enlaces, menos termos tem a expressão booleana do Mapa de Karnaugh considerado e, portanto, ela fica mais simplificada.

·      Os passos para simplificação consistem em: formar oitavas (possível em diagramas de 4 variáveis); formar quadras (possível em diagramas de 3 e 4 variáveis).

·       Uma oitava agrupada representa maior simplificação que uma quadra, que por sua vez representa maior simplificação que um par, e este maior simplificação que um termo isolado. Portanto, deve-se preferir agrupar em oitava, e se não for possível em quadras e, se também não for possível, em pares, mesmo que alguns elementos já tenham sido considerados em outros agrupamentos. Lembrando que se deve ter o menor número possível de agrupamentos.

·      Sempre que uma ou mais saídas forem irrelevantes (= don’t care), cada uma delas deve ser considerada 0 (zero), ou 1 (um) de forma que os enlaces se tornem maiores para que seus termos correspondentes se tornem menores.

·      A resolução de um Mapa de Karnaugh com enlaces menores do que os possíveis (ou com um número de enlaces maior do que o necessário) resulta, também, em uma expressão booleana correta, porém, não totalmente simplificada.

·         Quando uma variável aparece nas formas barrada e não-barrada em um grupamento (=enlaces), tal variável é eliminada da expressão. As variáveis que não se alteram para todos os quadros do grupamento têm de permanecer na expressão final. 

Em outras palavras:

Após o Mapa de Karnaugh ter sido construído, a próxima tarefa é encontrar os termos mínimos a usar na expressão final. Estes termos são encontrados agrupando conjuntos de 1´s adjacentes no mapa. O agrupamento deve ser retangular e deve ter uma área igual a uma potência de 2 (isto é: 2, 4, 8, …). Os retângulos devem ser os maiores possíveis, sem conter nenhum 0. 

3)  A expressão simplificada será a somatória das regiões (=enlaces, agrupamentos) encontradas.

1) Mapa de Karnaugh para duas variáveis

Vamos considerar a seguinte tabela da verdade, para montar o Mapa de Karnaugh, onde A e B são as entradas e F a saída de um sistema qualquer.

O que faz mudar de estado é o nível lógico 1 (por convenção), logo a expressão correspondente à saída do circuito lógico é:

Vamos simplificar pelo Mapa de Karnaugh.

O Mapa de Karnaugh apresenta a seguinte configuração. Sendo que cada espaço é completado com seu nível lógico equivalente (de acordo com a tabela da verdade).

 

Com mapa pronto, devemos destacar os mintermos, em outras palavras, considerar somente os campos que possuem 1 como solução final. Devem ser agrupados em pares, para isso ocorrer, os elementos devem estar lado-a-lado (=adjacentes); poder ser tanto horizontal, como na vertical.

Portanto, separando em pares temos:

Notamos que os campos selecionados com a cor vermelha, estão na coluna B (barrado, negado). E os campos selecionados com a cor azul estão na linha A.

Portanto, assim formando a expressão simplificada

2) Mapa de Karnaugh para três variáveis

Vamos pegar a tabela da verdade, a seguir, onde A, B e C são entradas e F é a saída:

A expressão da saída antes da simplificação é:

O Mapa de Mapa de Karnaugh fica:

Os agrupamentos (=enlaces) possíveis são como mostra a figura a seguir:

Observamos que os campos com a cor azul, estão na coluna da variável C e linha da variável A (barrado).  Já os elementos com a cor verde pertencem à coluna da variável C (barrado) e linha da variável A. Os elementos com a cor vermelha são da coluna B (barrado) e C.

Então, a expressão de saída simplificada é:

Outro método para construir o Mapa

Mapeando a tabela da verdade:

Idem anterior:

Observamos que os campos com a cor azul, estão na coluna da variável C e linha da variável A (barrado).  Já os elementos com a cor verde pertencem à coluna da variável C (barrado) e linha da variável A. Os elementos com a cor vermelha são da coluna B (barrado) e C.

Então, a expressão de saída simplificada é:

3) Mapa de Karnaugh para quatro variáveis

Uma das formas é utilizar a matriz de 4x4 da seguinte maneira:

Explicando como funciona o mapa:

Cada entrada (sendo elas A, B, C, D), ou suas respectivas negações, correspondem a 8 campos cada.  Vejamos como fica a estrutura do Mapa de Karnaugh.

Vamos considerar a seguinte tabela da verdade, como exemplo, para montar o Mapa de Karnaugh, onde A, B, C, D são as entradas e F a saída de um sistema qualquer.

Mapeando a tabela da verdade, temos:

Lembrando que os enlaces (=agrupamentos) devem ser quadrados, ou retângulos e, também, devem conter quantidades baseadas em potências de 2, (ou seja: 2, 4, 8).

Sendo assim, a expressão simplificada para este exemplo é a seguinte:

Outra maneira para construir o Mapa

Mapeando a tabela da verdade, temo-se:

Portanto, a expressão simplificada para este exemplo é a seguinte:

OBSERVAÇÕES:

1) Para mapas com variáveis de entrada superiores, ou iguais a 3, é interessante conhecer o Código Gray.  Resumidamente, Código Gray – de um número para outro, apenas um bit varia.

2) Quando uma variável aparece nas formas barrada e não-barrada em um grupamento (=enlaces), tal variável é eliminada da expressão. As variáveis que não se alteram para todos os quadros do grupamento têm de permanecer na expressão final.