A álgebra booleana é um sistema matemático com dois valores (zero e um) e com três operadores lógicos (AND, OR e NOT). O sistema booleano é fechado em relação a estas três operações, isto é, dados operandos booleanos, estes operadores sempre produzem um resultado booleano. As operações lógicas AND e OR são comutativas, ou seja, os operandos podem trocar de posição que o resultado permanece o mesmo. As operações lógicas AND e OR são associativas, isto é, A AND (B AND C) é igual a (A AND B) AND C. O mesmo vale para o OR lógico. As operações lógicas AND e OR também são distributivas, o que quer dizer que A AND (B OR C) é igual a (A AND B) OR (A AND C). Da mesma forma, A OR (B AND C) é igual a (A OR B) AND (A OR C). O valor 1 é o elemento de identidade em relação ao AND lógico, o valor zero é o elemento de identidade em relação ao OR lógico. Para qualquer valor booleano A existe um outro valor A' que não é igual a A (é o inverso de A). A OR A' é 1 (ou A + A' = 1) e A AND A' é zero (ou A x A' = 0). Estas declarações formam os postulados básicos do sistema algébrico booleano. É possível provar todos os teoremas e fatos do sistema booleano usando este conjunto de postulados.

Q02.01 - Qual é a regra (postulado) que podemos usar para provar que A AND (B AND C) é igual a (A AND B) AND (A AND C)?

Q02.02 - Qual é a regra (postulado) que podemos usar para mostrar que A AND (B AND C) é igual a (A AND B) AND C?

Usando os postulados acima podemos provar com facilidade vários teoremas importantes da álgebra booleana. Os teoremas mais importantes são:

T1: A + A = A          T8: (AB)' = A' + B'
T2: A x A = A          T9: A + AB = A
T3: A + 0 = A          T10: A x (A + B) = A
T4: A x 1 = A          T11: A + A'B = A + B
T5: A x 0 = 0          T12: A' x (A+B') = A'B'
T6: A + 1 = 1          T13: AB + AB' = A
T7: (A+B)' = A'B'      T14 (A' + B') x (A' + B) = A'

Q02.03 - No capítulo 1 você aprendeu que pode usar a operação lógica AND para zerar vários bits numa string de bits. Qual dos teoremas acima descreve esta operação?

Q02.04 - No capítulo 1 você aprendeu que pode usar a operação lógica OR para forçar o valor um em vários bits numa string de bits. Qual dos teoremas acima descreve esta operação?

Uma função booleana, ou expressão, é um conjunto de literais combinadas com os operadores lógicos AND e OR. Uma literal é o valor zero ou 1, ou uma variável plicada (por exemplo, A') ou não plicada (por exemplo, A). A plica (ou linha, como falamos) indica uma negação lógica (NOT). Exemplos de funções booleanas típicas incluem:

F = AB + C          G = A(B + C)          H = A'B'C + ABC'

Dados os valores para A, B e C, podemos calcular os valores das funções acima. Por exemplo, se A=0, B=1 e C=1, então F = 0 x 1 + 1 = 0 + 1 = 1. Da mesma forma, G = 0 x (1 + 1) = 0 x 1 = 0. E, por último, podemos calcular H = 1 x 0 x 1 + 0 x 1 x 0 = 0 + 0 = 0. Entretanto, avaliar funções booleanas desta forma é chato e sujeito a erros. Como é provável que se confunda alguns valores fazendo cálculos mentais, uma solução melhor e mais segura é procurar a resposta numa tabela.

Como existem apenas dois valores booleanos, é possível relacionar todos os valores que uma função booleana possa produzir. Por exemplo, a função F acima usa três variáveis independentes, A, B e C. Dadas n variáveis, cada uma tendo dois valores distintos, há 2ⁿ combinações possíveis dos valores destas variáveis. Portanto, existem oito (2³) combinações possíveis de A, B e C como entradas da função F. Sabendo disto, fica fácil criar uma tabela que mostre todas as entradas possíveis de uma dada função (ou funções) e colocar os resultados desta função na tabela. Uma tabela deste tipo é chamada de tabela verdade.

Para construir uma tabela verdade, comece listando todas as combinações possíveis das variáveis que aparecem na função. As três funções deste exemplo têm três variáveis de entrada. Neste caso, comece listando os oito valores binários de três bits, que vão de 0 a 7.

Por convenção, trataremos a variável A como o bit menos significativo e a variável C como o bit mais significativo do número binário. O próximo passo é calcular os valores para cada função. Para a função F calculamos o seguinte:

F(C,B,A) = AB + C
------------------------
F(0,0,0) = 0 x 0 + 0 = 0
F(0,0,1) = 1 x 0 + 0 = 0
F(0,1,0) = 0 x 1 + 0 = 0
F(0,1,1) = 1 x 1 + 0 = 1
F(1,0,0) = 0 x 0 + 1 = 1
F(1,0,1) = 1 x 0 + 1 = 1
F(1,1,0) = 0 x 1 + 1 = 1
F(1,1,1) = 1 x 1 + 1 = 1

O próximo passo é inserir os valores encontrados na tabela verdade na coluna correspondente. Para a função F os valores são:

Q02.05 - Para a função G, quais são os valores?

Q02.06 - Para a função H, quais são os valores?

Considere a função F = AB + C'D'. Como esta função usa quatro valores de entrada, existem 2⁴ (16) possíveis combinações diferentes das entradas. Listando estes valores obtemos:

J(D, C, B, A) = AB + C'D'
J(0, 0, 0, 0) = 0x0 + 1x1 = 1
J(0, 0, 0, 1) = 0x1 + 1x1 = 1
J(0, 0, 1, 0) = 1x0 + 1x1 = 1
J(0, 0, 1, 1) = 1x1 + 1x1 = 1
J(0, 1, 0, 0) = 0x0 + 1x0 = 0
J(0, 1, 0, 1) = 0x1 + 1x0 = 0
J(0, 1, 1, 0) = 1x0 + 1x0 = 0
J(0, 1, 1, 1) = 1x1 + 1x0 = 1
J(1, 0, 0, 0) = 0x0 + 0x1 = 0
J(1, 0, 0, 1) = 0x1 + 0x1 = 0
J(1, 0, 1, 0) = 1x0 + 0x1 = 0
J(1, 0, 1, 1) = 1x1 + 0x1 = 1
J(1, 1, 0, 0) = 0x0 + 0x0 = 0
J(1, 1, 0, 1) = 0x1 + 0x0 = 0
J(1, 1, 1, 0) = 1x0 + 0x0 = 0
J(1, 1, 1, 1) = 1x1 + 0x0 = 1

Q02.07 - Construa a tabela verdade da função J.

Para funções booleanas complexas, com muitos termos e operações diferentes, é possível escrever um programa simples que gera automaticamente a tabela verdade. O programa LOGICEV é um bom exemplo, você verá adiante.

Não é surpresa nenhuma que as expressões booleanas possam ser manipuladas algebricamente. Usando os teoremas mostrados no tópico A álgebra booleana, podemos transformar uma expressão booleana numa outra expressão equivalente. Existem duas razões para proceder desta forma: para simplificar expressões complexas ou para transformá-las na forma canônica.

Para demonstrar como se usa transformações algébricas para simplificar uma expressão, o exemplo seguinte está ao contrário. Nele, uma equação simples é transformada algebricamente numa equação complexa. O processo de simplificação é apenas o inverso desta mesma sequência de transformações:

F = ab + c                              função original
  = ab*1 + c                            pelo T4
  = ab(c + c') + c                      lei dos inversos (P5)
  = abc + abc' + c                      lei distributiva (P4)
  = abc + abc' + c + 0                  pelo T3
  = abc + abc' + c + bc*0               pelo T5
  = abc + abc' + c + a'bca              lei dos inversos (P5)
  = a(bc + bc' + a'bc) + c              lei distributiva (P4)
  = a(bc + bc' + a'bc) + c*1            pelo T4
  = a(bc + bc' + a'bc) + c(b+b')        lei dos inversos (P5)
  = a(bc + bc' + a'bc) + cb + cb'       lei distributiva

Obviamente podemos continuar o processo e tornar esta expressão cada vez mais complexa. O importante é saber que esta complexidade pode ser reduzida usando os mesmos passos ao contrário. Infelizmente não existe uma algoritmo simples que descreva este procedimento. É uma questão habilidade que depende de experiência e de tentativa e erro. A seguir, vamos tentar simplificar a seguinte equação lógica para o segmento número quatro de um display de sete segmentos:

Tentando otimizar a expressão, o truque é combinar termos que contenham versões plicadas e não plicadas da variável. Na expressão acima, podemos usar a lei distributiva para combinar D'C'B'A' e DC'B'A', obtendo (D+D')C'B'A'. Uma vez que a lei dos inversos diz que D + D' é 1, isto reduz estes dois termos para o termo único C'B'A'. Portanto, uma versão simplificada de S₄ é:

Depois, podemos usar a lei distributiva nos dois últimos termos para reduzí-la para:

Este último passo aumentou o número de termos de três para quatro, mas reduziu o número total de operações necessárias para calcular o resultado da função. A versão anterior precisava de oito operações AND e de duas operações OR, a atual precisa apenas de seis operações AND e de duas operações OR.

Q02.08 - Indique as regras aplicadas em cada uma das etapas da simplificação de S₀ = D'C'B'A' + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'A' + DC'B'A.
A primeira etapa resultou em S₀ = D'C'B'A' + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'A' + DC'B'A' + DC'B'A.

Q02.09 - S₀ = C'B'A'(D + D') + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'A' + DC'B'A

Q02.10 - S₀ = C'B'A' + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'A' + DC'B'A

Q02.11 - S₀ = C'B'A' + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'(A' + A)

Q02.12 - S₀ = C'B'A' + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'

Q02.13 - S₀ = C'B'A' + D'C'B(A' + A) + D'CB'A + D'CBA' + D'CBA + DC'B'

Q02.14 - S₀ = C'B'A' + D'C'B + D'CB'A + D'CBA' + D'CBA + DC'B'

Q02.15 - S₀ = C'B'A' + D'C'B + D'CB'A + D'CB(A' + A) + DC'B'

Q02.16 - S₀ = C'B'A' + D'C'B + D'CB'A + D'CB + DC'B'

Q02.17 - S₀ = C'B'A' + D'C'B + D'CB'A + D'CB + D'CB + DC'B'

Q02.18 - S₀ = C'B'A' + D'B(C' + C) + D'CB'A + D'CB + DC'B'

Q02.19 - S₀ = C'B'A' + D'B + D'CB'A + D'CB + DC'B'

Q02.20 - S₀ = C'B'A' + D'B + D'C(B'A + B) + DC'B'

Q02.21 - S₀ = C'B'A' + D'B + D'C(A + B) + DC'B'

Q02.22 - S₀ = C'B'A' + D'B + D'CA + D'CB + DC'B'

Q02.23 - S₀ = C'B'A' + D'B x 1 + D'CA + D'CB + DC'B'

Q02.24 - S₀ = C'B'A' + D'B(1 + C) + D'CA + DC'B'

Q02.25 - S₀ = C'B'A' + D'B(1) + D'CA + DC'B'

Q02.26 - S₀ = C'B'A' + D'B + D'CA + DC'B'

Q02.27 - S₀ = C'B'(A' + D) + D'B + D'CA

Q02.28 - S₀ = C'B'(A' + D) + D'(B + CA)

Otimizar um circuito geralmente significa reduzir o número de operações ou os termos de uma expressão booleana. Entretanto, este não é sempre o caso. Algumas vezes uma operação de otimização acaba aumentando os termos ou as operações. Imagine um engenheiro que esteja projetando um circuito que precisa calcular A + B. O engenheiro pode usar uma porta OR, como o circuito integrado (CI) 74LS32. Este CI possui quatro portas OR. De forma semelhante, o chip 75LS08 possui quatro portas lógicas AND e o chip 74LS04 possui seis portas inversoras. Agora imagine que o engenheiro tenha um 74LS04 com três inversores não usados, um 78LS08 com uma porta AND livre e nenhuma porta OR disponível no circuito. Para obter a função OR necessária, ele poderia adicionar um 78LS32 no circuito, mas isto aumentaria o custo do mesmo. Se quiser reduzir o custo e o número de componentes (isto é, otimizar o custo ao invés do número de termos ou operações), ele poderia sintetizar a operação OR da seguinte maneira:

ou seja, o engenheiro poderia usar dois inversores para inverter os valores de A e B, depois usar uma porta AND e, finalmente, usar um terceiro inversor para inverter a saída da porta AND.

Q02.29 - Quais são os teoremas que apoiam a igualdade acima, ou seja, que A + B = (A' x B')'?

Quando se otimiza equações lógicas para criar um circuito eletrônico, a simples redução do número de termos e operadores nem sempre é a solução mais efetiva em termos de custo. Por outro lado, quando se implementa uma função lógica no software, a solução ótima provavelmente será aquela que usar o menor número de operações.

Q02.30 - Otimize a função F = AB + A' para minimizar o número de operações.

Como existem infinitas funções booleanas equivalentes, usaremos a forma canônica da soma de mintermos para especificar funções lógicas. Para cada uma das funções lógicas existe uma soma de mintermos única. A soma de mintermos é conveniente porque é fácil criar uma tabela verdade a partir da equação lógica e, além do mais, é fácil construir a equação lógica com soma de mintermos a partir da tabela verdade.

Um mintermo é um termo no qual todas as variáveis de uma expressão booleana estão presentes na forma plicada ou não plicada. Numa função booleana de quatro variáveis o mintermo será composto por quatro literais (lembre-se, um literal é uma variável plicada ou não plicada). Como cada uma das variáveis pode assumir um de dois estados (plicada ou não plicada), existem 2ⁿ possíveis mintermos diferentes para uma função de n variáveis. Isto corresponde ao número de entradas da tabela verdade.

Cada mintermo na forma canônica corresponde a uma entrada de valor 1 na tabela verdade. A soma de mintermos é o OR lógico de todos os mintermos presentes numa tabela verdade (isto é, o "endereço" de cada entrada da tabela que contenha 1). Por exemplo, considere a tabela verdade ao lado. Esta tabela verdade contém uns nas casa endereçadas por C'B'A, C'BA', C'BA, CB'A e CBA'. Estes "endereços correspondem aos mintermos. A soma dos mintermos é o OR lógico destes mintermos, portanto, a função para a tabela verdade acima é C'B'A + C'BA' + C'BA + CB'A + CBA'.

Q02.31 - Qual é a forma canônica (soma de mintermos) da tabela verdade acima?

Q02.32 - Qual é a forma canônica da tabela verdade acima?

Q02.33 - Qual é a forma canônica da tabela verdade acima?

Criar uma tabela verdade a partir de uma forma canônica é tão fácil quanto. Só é preciso preencher todas as entradas da tabela verdade cujos endereços correspondam aos mintermos. A equação F = C'B'A' + C'BA + CBA + CB'A', por exemplo, dá a seguinte tabela verdade:

Q02.34 - Construa a tabela para F = CBA + C'BA' + CBA' + C'BA

Q02.35 - Construa a tabela para F = C'B'A' + C'B'A + C'BA' + C'BA + CBA

Q02.36 - Construa a tabela para F = DC'BA + DC'B'A' + DCBA + D'CBA