Tutoriais e Programação
AoA - Cap.2 - Funções booleanas e tabelas lógicas
|
Qua 21 Fev 2007 20:59 |
- Detalhes
- Categoria: Art of Assembly
- Atualização: Domingo, 19 Abril 2009 13:02
- Autor: vovó Vicki
- Acessos: 12642
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 F0 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 F0, 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:
| C | B | A | F = ABC | F = AB + C | F = A + BC |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| Múltiplas funções com 3 variáveis | |||||
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 24 ou 16 funções diferentes. Com três variáveis de entrada existem 2(2^3) = 28 ou 256 funções possíveis. Quatro variáveis de entrada criam 2(2^4) ou 216 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:
| Função | Descrição |
|---|---|
| 0 | Zero ou Desligado. Sempre retorna zero, independentemente dos valores de entrada A e B |
| 1 | NOR lógico (NOT (A OR B)) = (A + B)' |
| 2 | Inibição = BA' (B NOT A). Também equivalente a B > A ou A < B |
| 3 | NOT A. Ignora B e retorna A' |
| 4 | Inibição = AB' (A NOT B). Também equivalente a A > B ou B < A |
| 5 | NOT B. Retorna B' e ignora A |
| 6 | OR-exclusivo (XOR) = A [+] B. Também equivalente a A <> B. |
| 7 | NAND lógico (NOT (A AND B)) = (A x B)' |
| 8 | AND lógico = A x B. Retorna A AND B. |
| 9 | Equivalência = (A = B). Também conhecida como NOR-exclusivo (NOT OR-exclusivo) |
| 10 | Cópia de B. Retorna o valor de B e ignora o valor de A |
| 11 | Implicação, B implica A = A + B'. (se B então A). Também equivalente a B >= A |
| 12 | Cópia de A. Retorna o valor de A e ignora o valor de B |
| 13 | Implicação, A implica B = B + A' (se A então B). Também equivalente a A >= B |
| 14 | OR lógico = A + B. Retorna A OR B |
| 15 | Um ou Ligado. Sempre retorna um, independentemente dos valores de entrada de A e B |
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.