Álgebra Booleana, Tabelas Verdade e Propriedades Algébricas
Este tópico é fundamental para a compreensão do funcionamento interno dos computadores e circuitos digitais, pois a Álgebra Booleana é a base matemática por trás das operações lógicas realizadas com os valores binários e com ela que construimos nossos circuitos.
Introdução à Álgebra Booleana
- Propósito e Contexto:
A Álgebra Booleana é um ramo da matemática voltado para a lógica binária, onde os valores possíveis são apenas dois: verdadeiro (1) e falso (0). Ela serve como base para a construção de circuitos digitais e para a representação de decisões lógicas em computadores. Seu nome é uma homenagem ao matemático George Boole, que desenvolveu esse sistema lógico no século XIX. - Relevância em Circuitos Digitais:
A Álgebra Booleana permite descrever e projetar o funcionamento de portas lógicas — blocos fundamentais dos circuitos digitais. Portas como AND, OR e NOT operam sobre os valores binários, manipulando sinais de entrada para produzir saídas coerentes com regras lógicas. Combinando essas portas, é possível construir dispositivos complexos, como somadores, registradores, memórias e até processadores completos.
Conceitos Fundamentais e Operadores Booleanos
- Valores Lógicos:
- Verdadeiro (True), geralmente representado por 1.
- Falso (False), geralmente representado por 0.
- Operadores Lógicos Fundamentais: São utilizadas algumas portas lógicas para facilitar as operações visando torná-las mais alto nível, mais pra frente você vai aprender que todas podem ser feitas com NAND.
Os principais são:
- AND (E Lógico): Retorna 1 apenas se ambas as entradas forem 1.
Possíveis sinais: . | e | and | ∧ - OR (OU Lógico): Retorna 1 se pelo menos uma das entradas for 1.
Possíveis sinais: + | ou | or | v - NOT (NÃO Lógico/Inversor): Inverte o valor da entrada (0 → 1, 1 → 0).
Possíveis sinais: ‘ | ¬ | ~ | not | x̅ - XOR (OU Exclusivo): Retorna 1 se apenas uma das entradas for 1.
Possíveis sinais: ⊕ | xor | ^ (em alguns contextos) - Outros Operadores: Cada operador acima (exceto o NOT) possui sua inversão, que funciona da mesma que um NOT após a porta. Elas são: NAND (↑), NOR (↓), XNOR (≡).
Ex: NAND é igual a AND → NOT
(A ↑ B) = ¬(A ∧ B)
- AND (E Lógico): Retorna 1 apenas se ambas as entradas forem 1.
Tabelas Verdade
As tabelas verdade são uma ferramenta essencial na hora de criar circuitos digitais, principalmente mais simples. Ela lista todas as combinações possíveis de entradas e a respectiva saída para cada, assim, sendo possível criar uma expressão booleana para um circuito.
Estrutura: Uma tabela verdade irá conter 2n linhas, sendo n o número de entradas do circuito. Ela deve conter todas as entradas possíveis para o circuito.
Exemplos:
Tabela verdade AND (1 quando A e B são 1)
| A | B | Saída |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Tabela verdade OR (1 quando A ou B são 1)
| A | B | Saída |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Tabela verdade NOT (inverte a entrada)
| A | Saída |
| 0 | 1 |
| 1 | 0 |
Propriedades Algébricas da Álgebra Booleana
Importância:
Permitem simplificar expressões lógicas, otimizando designs de circuitos (menos portas, menor consumo energético).
Lista de Propriedades
- Comutativa:
A + B = B + A
A * B = B * A - Associativa:
A + (B + C) = (A + B) + C
A * (B * C) = (A * B) * C - Distributiva:
A * (B + C) = (A * B) + (A * C)
A + (B * C) = (A + B) * (A + C) - Identidade:
A + 0 = A
A * 1 = A
- Complemento:
A + A′ = 1
A * A′ = 0 - Leis de De Morgan:
(A + B)’ = A’ * B’
(A * B)’ = A’ + B’ - Idempotência:
A + A = A
A * A = A - Absorção:
A + (A * B) = A
A * (A + B) = A
Exemplos de Expressões Booleanas e Simplificação
Construção de Expressões
Expressões booleanas combinam variáveis lógicas e operadores (AND, OR, NOT, etc.) para representar o comportamento de circuitos digitais.
Exemplo 1:
F(A, B, C) = (A AND B) OR (NOT C)
Essa função retorna 1 se A e B forem verdadeiros, ou se C for falso.
Exemplo 2:
F(A, B, C) = (A AND NOT B) OR (B AND C)
Aqui, a saída será 1 se A for 1 e B for 0, ou se B e C forem ambos 1.
Essas expressões representam comportamentos comuns em circuitos, como decisões condicionais, comparações ou ativação de componentes com base em múltiplas entradas.
Objetivos da Simplificação
Simplificar expressões booleanas visa:
- Reduzir o número de portas lógicas necessárias no circuito.
- Diminuir o tempo de processamento (menos níveis de lógica).
- Economizar energia e espaço físico nos chips e placas.
- Facilitar a análise e manutenção do circuito.
Métodos de Simplificação
1. Uso de Propriedades Algébricas
Exemplo 1:
Expressão original:
F = A·B + A·B’
Aplicando a propriedade de absorção:
F = A
Exemplo 2:
Expressão original:
F = (A⋅B⋅C)+(A′⋅B)+(A⋅B⋅C′)+(A⋅B⋅D)+(A⋅B⋅D′)
| Passo | Expressão | Propriedade Utilizada |
| 0 | (A⋅B⋅C)+(A′⋅B)+(A⋅B⋅C′)+(A⋅B⋅D)+(A⋅B⋅D′) | Comutativa |
| 1 | (A⋅B⋅C)+(A⋅B⋅C′)+(A′⋅B)+(A⋅B⋅D)+(A⋅B⋅D′) | Distributiva |
| 2 | (A⋅B)⋅(C+C′)+(A′⋅B)+(A⋅B)⋅(D+D′) | Complemento |
| 3 | (A⋅B)⋅1+(A′⋅B)+(A⋅B)⋅1 | Identidade |
| 4 | A⋅B+A′⋅B+A⋅B | Idempotência |
| 5 | A⋅B+A′⋅B | Distributiva |
| 6 | B⋅(A+A′) | Complemento |
| 7 | B⋅1 | Identidade |
| 8 | B |
2. Mapas de Karnaugh
Mapas de Karnaugh organizam todas as possíveis entradas de uma função booleana em uma tabela visual. Agrupando os 1s adjacentes, é possível encontrar formas mais simples da função. É muito útil para quando se tem a tabela verdade do circuito e quer simplificar a expressão.
Geralmente são utilizados para circuitos com até 4 entradas, após isso ele começa a ficar mais complexo e menos intuitivo de ser utilizado.
Exemplo:
| A | B | C | D | SAÍDA |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 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 | 1 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Para montar o Mapa de Karnaugh, as colunas e linhas adjacentes a um espaço devem respeitar a regra de negar apenas uma das variáveis em relação à do lado.
| CD | CD̅ | C̅D̅ | C̅D | |
| AB | 1 | 1 | 1 | |
| AB̅ | 1 | |||
| A̅B̅ | 1 | 1 | ||
| A̅B | 1 | 1 |
Inclusive, pode-se notar nos exemplos abaixo que quando os 1s estão distribuídos de forma análoga a um tabuleiro de xadrez, pode-se uní-los formando um XOR ou XNOR.
Mapas com diferentes quantidades de variáveis:
2 Variáveis
| B | B̅ | |
| A | 1 | |
| A̅ | 1 |
A̅ ⊕ B
3 Variáveis
| C | C̅ | |
| AB | 1 | |
| AB̅ | 1 | 1 |
| A̅B̅ | 1 | |
| A̅B | 1 |
C v AB̅
4 Variáveis
| CD | CD̅ | C̅D̅ | C̅D | |
| AB | 1 | 1 | ||
| AB̅ | 1 | 1 | ||
| A̅B̅ | 1 | 1 | ||
| A̅B | 1 | 1 |
(A ⊕ B ⊕ C ⊕ D)
5 Variáveis
Para 5 variáveis deve-se montar 2 mapas de 4 variáveis. Um mapa será para quando a quinta variável estiver ligada e o outro para quando ela estiver negada.
S = CD̅E̅ + A̅B̅D̅ + ADE + A̅BD
| CD | CD̅ | C̅D̅ | C̅D | |
| AB | 1 | 1 | ||
| AB̅ | 1 | 1 | ||
| A̅B̅ | 1 | 1 | ||
| A̅B | 1 | 1 |
E
| CD | CD̅ | C̅D̅ | C̅D | |
| AB | 1 | |||
| AB̅ | 1 | |||
| A̅B̅ | 1 | 1 | ||
| A̅B | 1 | 1 | 1 |
¬E
A partir de 6 variáveis, o Mapa de Karnaugh não é viável de se utilizar, sendo recomendado usar as propriedades algébricas para simplificar uma expressão.