Qua

21

Fev

2007

19:59

Uma expressão booleana é uma sequência de zeros, uns e literais separados por operadores booleanos.

Uma literal é um nome de variável plicada (negada) ou não plicada (por exemplo, A é não plicada; A' é plicada e se lê A linha). Aqui, para nós, todos os nomes de variáveis serão uma única letra do alfabeto. Uma função booleana é uma expressão booleana específica; ela geralmente receberá o nome "F" e possivelmente um subescrito. Por exemplo, considere a seguinte booleana:

F0 = AB + C

Esta função calcula o AND lógico de A e B e depois efetua o OR lógico entre o resultado e C. Se A = 1, B = 0 e C = 1, então F₀ retorna o valor 1, pois (1 x 0) + 1 = 1.

Outro modo de representar uma função booleana é através de tabelas lógicas. No capítulo anterior utilizamos estas tabelas para representar as funções AND e OR. Eram as seguintes:

Para operadores binários e duas variáveis de entrada, esta forma de tabela lógica é muito natural e conveniente. No entanto, se considerarmos a função F₀, existem três variáveis de entrada e não apenas duas. Felizmente existe um jeito fácil de construir tabelas lógicas para três ou mais variáveis. O exemplo seguinte mostra um dos modos de fazer isto para funções com três ou quatro variáveis:

Nas tabelas lógicas acima, as quatro colunas cinza representam as quatro combinações possíveis de zeros e uns para A e B (B é o bit mais significativo ou da esquerda e A é o bit menos significativo ou da direita). Na segunda tabela, as quatro linhas cinza representam as quatro combinações possíveis de zeros e uns para as variáveis C e D, onde D é o bit mais significativo e C é o menos significativo. A tabela abaixo mostra uma outra forma de representar tabelas lógicas. Esta forma tem duas vantagens em relação às formas mostradas acima - é mais fácil de ser preenchida e permite a representação compacta de duas ou mais funções:

Observe que a tabela lógica acima contém os valores para três funções distintas de três variáveis. Apesar de podermos criar uma variedade infinita de funções booleanas, elas não são todas únicas. Por exemplo, F = A e F = AA são duas funções diferentes. No entanto, pelo teorema dois, fica fácil demonstrar que estas duas funções são equivalentes, isto é, ambas fornecem exatamente a mesma saída para todas as combinações de entrada. Se fixarmos o número de variáveis de entrada, há um número finito de funções booleanas únicas possíveis. Por exemplo, existem apenas 16 funções booleanas únicas com duas entradas e existem apenas 256 funções booleanas possíveis com três variáveis de entrada. Dadas n variáveis de entrada, existem 2^{(2^n)} funções booleanas únicas com estes n valores de entrada. Para duas variáveis de entrada, 2^{(2^2)} é o mesmo que 2⁴ ou 16 funções diferentes. Com três variáveis de entrada existem 2^{(2^3)} = 2⁸ ou 256 funções possíveis. Quatro variáveis de entrada criam 2^{(2^4)} ou 2¹⁶ ou 65.536 funções booleanas únicas. Quando lidamos com apenas 16 funções booleanas, é fácil dar um nome para cada função. A tabela a seguir lista as 16 funções booleanas possíveis com duas variáveis de entrada e alguns dos nomes mais comuns das mesmas:

Acima de duas variáveis de entrada existem funções demais para nomear. Devido a isto, vamos referenciá-las com números. Por exemplo, F8 refere-se ao AND lógico de A e B para a função com duas entradas e F14 é a operação lógica OR. É claro que o único problema é determinar o número da função. Por exemplo, dada a função de três variáveis F = AB + C, qual é o número que lhe corresponde? Este número é fácil de calcular usando-se a tabela lógica da função (veja a tabela Múltiplas funções com 3 variáveis acima). Se tratarmos os valores de A, B e C como bits de um número binário, com C sendo o mais significante e A o menos significante, eles produzem os números binários que vão de 0 a 7. Para cada sequência binária existe um resultado da função, que pode ser zero ou um. Se tomarmos os resultados obtidos para a função F = AB + C como bits, do bit mais significativo até o menos significativo, obtemos o número binário 1 1 1 1 1 0 0 0. Transformando este binário em decimal obtemos o valor 248, justamente o número da função. Ou seja, das 256 funções possíveis, esta é a de número 248: F248 = AB + C.

Fonte

• Art of Assembly de Randall Hyde.
• Tradução meio que livre da vovó Vicki.