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 tutorial 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 combinatórios e sequenciais e equivalência de hardware e software (assustado com tanto assunto novo?)
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.
![]() |
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:
No nosso caso, usaremos os seguintes conjuntos de operadores e valores:
Também usaremos os seguintes postulados:
É possível provar todos os teoremas da álgebra booleana usando estes postulados. Não iremos realizar provas formais de todos eles, porém é uma boa idéia familiarizar-se com os mais importantes:
| Teorema | |
| T1 | A + A = A |
| T2 | A x A = A |
| T3 | A + 0 = A |
| T4 | A x 1 = A |
| T5 | A x 0 = 0 |
| T6 | A + 1 = 1 |
| T7 | (A + B)' = A'B' |
| T8 | (A x B)' = A' + B' |
| T9 | A + AB = A |
| T10 | A(A + B) = A |
| T11 | A + A'B = A + B |
| T12 | A'(A + B') = A'B' |
| T13 | AB + AB' = A |
| T14 | (A' + B')(A' + B) = A' |
| T15 | A + A' = 1 |
| T16 | AA' = 0 |
Os teoremas 7 e 8 são conhecidos como Teoremas de DeMorgan, em homenagem ao matemático que os descobriu.
Os teoremas na tabela acima 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 computa 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.
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 um único caracter 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 o seguinte booleano:
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 d representar uma função booleana é através de tabelas lógicas. No capítulo anterior utilizamos estas tabelas para representarem 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 acima citada, existem três variáveis de entrada, e não somente 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 significante ou da esquerda e A é o bit menos significante 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 significante e C é o menos significante. 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 |
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 ^ 4 ou 16 funções diferentes. Com três variáveis de entrada existem 2^(2^3) = 2^8 ou 256 funções possíveis. Quatro variáveis de entrada criam 2^(2^4) ou 2^16 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 destas funções:
| 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 isso, 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 5 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.
É possível transformar uma expressão booleana numa expressão equivalente aplicando-se os postulados e os teoremas da álgebra booleana. Esta transformação é importante quando queremos converter uma dada expressão para a forma canônica (uma forma padronizada). Também é importante quando queremos diminuir o número de literais (variáveis plicadas e não plicadas) ou os termos de uma expressão. Minimizar termos e expressões pode ser importante porque os circuitos elétricos geralmente são constituídos por componentes individuais que implementam cada termo ou literal de uma dada expressão. Minimizando a expressão, o projetista usa menos componentes elétricos, reduzindo o custo do sistema. Infelizmente não existem regras que possam ser aplicadas na otimização de uma dada expressão. A capacidade de otimizar depende essencialmente da experiência de cada um. Entretanto, alguns exemplos podem mostrar as possibilidades que existem:
|
|
As operações algébricas também podem ser usadas para outros fins e não só para simplificarem expressões booleanas como mostrado nos exemplos acima. Por exemplo, para se obter formas canônicas (que raramente são ótimas).
Uma vez que existe um número finito de funções booleanas para n variáveis de entrada mas é possível construir um número infinito de expressões com estes n valores de entrada, fica claro que existam infinitas expressões lógicas equivalentes (isto é, produzem o mesmo resultado quando recebem as mesmas entradas). Para ajudar a eliminar possíveis confusões, os projetistas lógicos geralmente especificam uma função booleana usando a forma canônica ou padrão. Para cada uma das funções booleanas dadas existe uma única forma canônica. Isto elimina confusões que possam ocorrer quando se lida com funções booleanas. Na verdade existem várias formas canônicas diferentes. Discutiremos apenas duas e empregaremos apenas a primeira. A primeira é chamada de soma de mintermos e a segunda é o produto de maxtermos. Usando o princípio da dualidade, é muito fácil fazer a conversão entre estas duas formas. Um termo é uma variável ou o produto (AND lógico) de várias literais diferentes. Por exemplo, se há duas variáveis, A e B, então existem oito termos possíveis: A, B, A', B', A'B', A'B, AB' e AB. Para três variáveis tem-se 26 termos diferentes: A, B, C, A', B', C', A'B', A'B, AB', AB, A'C', A'C, AC', AC, B'C', B'C, BC', BC, A'B'C', AB'C', A'BC', ABC', A'B'C, AB'C, A'BC e ABC. Percebe-se que, na medida em que o número de variáveis aumenta, o número de termos aumenta drasticamente. Um mintermo é um produto contendo exatamente n literais. Por exemplo, os mintermos de duas variáveis são A'B', AB', A'B e AB. Da mesma forma, os mintermos para três variáveis são A'B'C', AB'C', A'BC', ABC', A'B'C, AB'C, A'BC e ABC. Em geral existem 2^n mintermos para n variáveis. O conjunto de mintermos possíveis é muito fácil de ser gerado porque os mintermos correspondem à sequência dos números binários:
| Equivalente binário (CBA) | Mintermo |
| 000 | A'B'C' |
| 001 | AB'C' |
| 010 | A'BC' |
| 011 | ABC' |
| 100 | A'B'C |
| 101 | AB'C |
| 110 | A'BC |
| 111 | ABC |
Podemos especificar qualquer função booleana usando a soma (OR lógico) de mintermos. Dada a função F248 = AB + C, a forma canônica equivalente é ABC + A'BC + AB'C + A'B'C + ABC'. Podemos mostrar algebricamente que estas duas formas são equivalentes:
ABC + A'BC + AB'C + A'B'C + ABC'= BC(A + A') + B'C(A + A') + ABC'= BC1 + B'C1 + ABC' = C(B + B') + ABC' = C + ABC' = C + AB
Obviamente a forma canônica não é uma forma ótima. Por outro lado, uma grande vantagem da soma de mintermos da forma canônica é que fica muito fácil gerar a tabela lógica para a função. Além disso, também fica muito fácil gerar a equação lógica a partir da tabela lógica. Para construir a tabela lógica a partir da forma canônica basta transformar cada mintermo num valor binário substituindo as variáveis plicadas por 0 e as não plicadas por 1. Depois é só colocar um 1 na posição correspondente (especificada pelo valor binário do mintermo) na tabela lógica. Valores sem correspondência recebem o valor 0 na tabela lógica. Vamos inicialmente converter os mintermos da função F248 em valores binários:
| Mintermos | CBA + CBA' + CB'A + CB'A' + C'BA |
| Valor binário | 111 110 101 100 011 |
Agora é só localizar os valores binários dos mintermos na tabela lógica e atribuir-lhes o valor 1. Valores sem correspondência recebem o valor 0:
| C | B | A | F = AB + C |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
O caminho inverso, ou seja, criar uma função lógica a partir de uma tabela lógica, também é fácil. Inicialmente precisamos localizar todas as entradas da tabela que contenham 1. Na tabela acima existem cinco destas entradas. O número das entradas contendo 1 determina o número de mintermos da equação canônica. Para criar cada um dos mintermos, basta substituir os 1s por A, B ou C e os 0s por A', B' ou C'. Depois é preciso calcular a soma destes itens. No exemplo acima, F248 contém 1 para CBA = 111, 110, 101, 100 e 011. Portanto, F248 = CBA + CBA' + CB'A + CB'A' + C'BA. O primeiro termo, CBA, corresponde à última entrada da tabela. Como as operações lógicas OR e AND são comutativas, podemos rearranjar os termos dos mintermos (CBA = ABC = ACB, etc) além de rearranjar os mintermos na soma (CBA + CBA'... = CBA' + CBA...).
Este processo funciona igualmente bem para qualquer número de variáveis. Considere a função F53504 = ABCD + A'BCD + A'B'CD + A'B'C'D. Colocando 1 nas posições apropriadas da tabela lógica obtemos o seguinte:
| D | C | B | A | F = ABCD + A'BCD + A'B'CD + A'B'C'D |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Talvez o jeito mais fácil de gerar a forma canônica de uma função booleana seja criar primeiro a tabela lógica desta função e depois gerar a forma canônica da tabela. Usaremos esta técnica, por exemplo, quando fizermos a conversão das duas formas canônicas deste capítulo. Entretanto, calcular a soma dos mintermos algebricamente também é uma coisa simples. O uso da lei distributiva e do teorema 15 (A + A' = 1) facilitam a tarefa. Considere a F248 = AB + C. Esta função possui dois termos, AB e C, mas que não são mintermos. Os mintermos representam cada uma das variáveis possíveis na forma plicada ou não plicada. Podemos converter o primeiro termo para uma soma de mintermos da seguinte maneira:
AB = AB x 1 pelo T4 = AB x (C + C') pelo T15 = ABC + ABC' pela lei distributiva = CBA + C'BA pela lei associativa
Da mesma forma, podemos converter o segundo termo da F248 para uma soma de mintermos:
C = C x 1 pelo T4 = C x (A + A') pelo T15 = CA + CA' pela lei distributiva = CA1 + CA'1 pelo T4 = CA x (B + B') + CA' (B + B') pelo T15 = CAB + CAB' + CA'B + CA'B' pela lei distributiva = CBA + CBA' + CB'A + CB'A' pela lei associativa
A última etapa destas duas conversões, a de rearranjar os termos, é opcional. Para obter a forma canônica final da F248 precisamos apenas somar os resultados destas duas conversões:
F248 = (CBA + C'BA) + (CBA + CBA' + CB'A + CB'A') = CBA + CBA' + CB'A + CB'A' + C'BA
Outro modo de criar a forma canônica é através dos produtos de maxtermos. Um maxtermo é a soma (OR lógico) de todas as variáveis de entrada, plicadas ou não plicadas. Por exemplo, considere a seguinte função lógica G de três variáveis:
G = (A + B + C) x (A' + B + C) x (A + B' + C)
Assim como na soma de mintermos, existe um produto de maxtermos para cada uma das funções lógicas possíveis. Deste modo, para cada produto de maxtermos existe uma soma de mintermos equivalente. Na verdade, a função G é equivalente a:
F248 = CBA + CBA' + CB'A + CB'A' + C'BA = AB + C
Criar a tabela lógica do produto dos maxtermos não é mais difícil do que criá-la a partir da soma dos mintermos. Para isto, usa-se o princípio da dualidade. Lembre-se, o princípio da dualidade diz para trocar AND por OR e zeros por uns (e vice versa). Portanto, para fazer a tabela lógica, precisamos primeiro intercambiar as literais plicadas e não plicadas. Na função G isto seria:
G = (A' + B' + C') x (A + B' + C') x (A' + B + C')
O próximo passo é intercambiar os operadores lógicos OR e AND. Isto produz:
G = A'B'C' + AB'C' + A'BC'
Finalmente, é preciso intercambiar todos os zeros e uns. Isto significa que, nas itens da tabela lógica que correspondem aos termos, devem ser colocados 0 e, nos restantes, 1. As linhas com 000, 001 e 010 devem conter 0, as restantes devem conter 1. Observe que é a mesma tabela lógica da função F248.
A conversão destas duas formas canônicas pode ser feita com facilidade criando-se a tabela lógica para uma delas e, a partir desta tabela, gerando-se a outra forma. Por exemplo, considere a função com duas variáveis F7 = A + B. A soma da forma de mintermos é F7 = A'B + AB' + AB. A tabela lógica é a seguinte:
| B | A | F7 = A + B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Trabalhando ao contrário para obter o produto dos maxtermos, localizamos todas as linhas que tenham resultado 0. Esta é apenas a entrada onde A e B são 0. Isto nos dá o primeiro passo, onde G = A'B'. Agora é preciso inverter as variáveis, o que nos dá G = AB. Pelo princípio da dualidade, invertemos os operadores lógicos OR e AND, obtendo G = A + B. Esta é a forma canônica do produto dos maxtermos.
Trabalhar com produtos de maxtermos é um pouco mais atrapalhado do que com somas de mintermos, este texto geralmente fará uso da soma de mintermos. Além disso, a soma de mintermos é mais utilizada em trabalhos sobre lógica booleana.
Texto pesado pra caramba pra aprendiz de feiticeiro mas, para qualquer escovador de bits, nenhum susto. Pra projetista de circuito eletrônico então, apenas o bê-a-bá. Se você teve dificuldade para acompanhar o texto, uma sugestão: lápis e papel. Releia todos os tópicos e faça o máximo possível de exercícios. Solte a imaginação e ponha a cabeça para funcionar porque aí vem mais.