Sex

09

Fev

2007

11:09

A base dos sistemas de computadores digitais modernos são os circuitos lógicos. Para poder entender como estes sistemas funcionam é preciso ter algum conhecimento da lógica digital e da álgebra booleana. Estes assuntos são muito extensos, geralmente temas de livrões inteiros. Neste capítulo vamos apenas dar uma olhada no feijão com arroz, apenas o suficiente para poder trabalhar com Assembly.

A lógica booleana é a base dos sistemas binários. Usando um sistema de equações booleanas é possível representar qualquer algoritmo ou qualquer circuito eletrônico do computador. Este capítulo será uma breve introdução à álgebra booleana. Analisaremos tabelas lógicas, representação canônica, funções booleanas, simplificação de funções booleanas, desenho lógico, circuitos combinados e sequenciais e equivalência de hardware e software.

A seção que trata da minimização (otimização) de funções lógicas usa Diagramas Veitch ou Diagramas de Karnaugh. As técnicas de otimização utilizadas reduzem o número de termos numa função booleana. É preciso ressaltar que muitos consideram estas técnicas de otimização obsoletas porque a redução do número de termos numa equação não tem mais a importância que lhe era atribuída tempos atrás. Usaremos o método de diagramas como exemplo de otimização, não como uma técnica a ser empregada regularmente. Se você se interessa por projetos de circuitos e otimização, vai precisar consultar outros textos para encontrar técnicas melhores.

Apesar deste capítulo tratar basicamente de hardware, lembre-se de que muitos dos conceitos se referem a equações booleanas (funções lógicas). Alguns exercícios de programação, que serão apresentados em outros capítulos, vão exigir este conhecimento.

Álgebra booleana

George Boole

(1815-1864)

A álgebra booleana é um sistema de dedução matemática restrito aos valores zero e um (falso e verdadeiro). Operadores binários definidos para este conjunto de valores aceitam um par de entradas booleanas e produzem um valor booleano único. Por exemplo, o operador booleano AND aceita duas entradas booleanas e produz uma única saída booleana (o AND lógico das duas entradas).

Para qualquer sistema algébrico existem hipóteses iniciais (ou postulados) que o sistema obedece. Podemos deduzir regras adicionais, teoremas e outras propriedades do sistema a partir do conjunto básico de postulados. Os sistemas de álgebra booleana, idealizada por George Boole (1815-1864), geralmente empregam os seguintes postulados:

• Fechado. O sistema booleano é considerado fechado em relação a um operador binário se, para cada par de valores booleanos, ele produzir um resultado booleano. Por exemplo, o AND lógico está fechado no sistema booleano porque aceita somente operandos booleanos e produz apenas resultados booleanos.
• Comutativo. O operador binário " # " é dito comutativo se A # B = B # A para todos os valores booleanos possíveis de A e B.
• Associativo. Se (A % B) % C = A % (B % C) para todos os valores booleanos de A, B e C, diz-se que o operador binário "%" é associativo.
• Distributivo. Dois operadores binários "%" e "#" são distributivos se A % (B # C) = (A % B) # (A % C) para todos os valores booleanos de A, B e C.
• Identidade. Um valor booleano I é chamado de elemento de identidade em relação a algum operador binário "%" se A % I = A.
• Inverso. Um valor booleano I é chamado de elemento inverso em relação a algum operador binário "%" se A % I = B e B <> A (isto é, B é o valor oposto de A num sistema booleano).

No nosso caso, usaremos os seguintes conjuntos de operadores e valores:

• Os dois valores possíveis no sistema booleano são zero e um. Com frequência chamaremos zero de falso e um de verdadeiro.
• O símbolo "x" representa a operação do AND lógico. Por exemplo, A x B é o resultado da operação lógica AND com os valores booleanos A e B. Quando usamos apenas uma letra para os nomes das variáveis, podemos eliminar o símbolo "x". Portanto, AB também representa o AND lógico das variáveis A e B (que também chamaremos de produto de A e B).
• O símbolo "+" representa a operação lógica OR. Por exemplo, A + B é o resultado da operação lógica OR com os valores booleanos A e B (que também chamaremos de soma de A e B).
• O complemento lógico, a negação, ou NOT é um operador unitário. Usaremos o símbolo " ' " para indicar uma negação lógica. Por exemplo, A' expressa a operação lógica NOT de A.
• Se aparecerem diversos operadores booleanos numa expressão booleana, o resultado da expressão depende da precedência dos operadores. Usaremos a seguinte precedência, da mais alta para a mais baixa, para os operadores booleanos:
  1. parênteses
  2. NOT lógico
  3. AND lógico
  4. OR lógico
  Os operadores AND e OR são associativos à esquerda. Se dois operadores com a mesma precedência forem adjacentes, será preciso avaliá-los da esquerda para a direita. A operação lógica NOT é associativa à direita, mesmo que produza o mesmo resultado usando-se a associação pela direita ou pela esquerda, por se tratar de um operador unitário.

Também usaremos os seguintes postulados:

• (P1) A álgebra booleana é fechada sob as operações AND, OR e NOT.
• (P2) O elemento de identidade relativo a x é um; relativo a + é zero. Não há um elemento de identidade relativo ao NOT lógico.
• (P3) Os operadores x e + são comutativos.
• (P4) x e + são distributivos em relação um ao outro. Isto é, A x (B + C) = (A x B) + (A x C) e A + (B x C) = (A + B) x (A + C).
• (P5) Para cada valor de A existe um valor A' de modo que AA' = 0 e A + A' = 1. Este valor é o complemento lógico (NOT) de A.
• (P6) Tanto x como + são associativos, isto é, (AB)C = A(BC) e (A + B) + C = A + (B + C).

É possível provar todos os teoremas da álgebra booleana usando estes postulados. Não iremos realizar provas formais para todos eles, porém é uma boa idéia familiarizar-se com os mais importantes:

Os teoremas 7 e 8 são conhecidos como Teoremas de DeMorgan, em homenagem ao matemático que os descobriu.

Os teoremas na tabela ao lado aparecem em pares. Cada par (por exemplo, T1 e T2, T3 e T4, etc) formam um dual. Um princípio importante na lógica booleana é o da dualidade. Qualquer expressão válida criada com os postulados e os teoremas da álgebra booleana continua válida se os operadores e as constantes que aparecem na expressão forem trocados. Especificamente, se trocarmos os operadores x e +, e se trocarmos os valores 0 e 1 da expressão, obteremos uma expressão que obedece todas as regras da álgebra booleana. Isto não significa que a expressão dual calcula os mesmos valores; significa apenas que as duas expressões são expressões legais do sistema algébrico booleano. Portanto, este é um modo fácil de gerar um segundo teorema para qualquer fato que seja provado no sistema de álgebra booleana.

Apesar de não provar nenhum dos teoremas apresentados, usaremos estes teoremas para mostrar que duas equações booleanas são idênticas. Esta é uma operação importante quando buscamos representações canônicas de expressões booleanas ou quando simplificamos uma expressão booleana.

Fonte

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