Álgebra booleana
Todo circuito digital — da ULA do seu processador à memória RAM — é construído com AND, OR, NOT e variações. A álgebra de Boole é a matemática que torna isso possível: um sistema com apenas dois valores (0 e 1) e leis que permitem raciocinar sobre eles com precisão.
Dois valores. Infinitas possibilidades.
George Boole, em 1854, mostrou que o raciocínio lógico podia ser expresso com equações matemáticas. Um século depois, Claude Shannon percebeu que essas equações mapeavam perfeitamente para circuitos elétricos: corrente = 1, sem corrente = 0.
Três operações fundamentais constroem tudo o mais: AND (ambos verdadeiros → verdadeiro), OR (pelo menos um → verdadeiro), NOT (inverte). O XOR (ou exclusivo) e as portas universais NAND e NOR derivam dessas três.
Explore todas as portas lógicas
Alterne os valores de A e B e veja a saída de cada porta em tempo real. A linha da tabela-verdade correspondente é destacada.
| A | B | AND | OR | XOR | NOT | NAND | NOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Leis da álgebra de Boole
// Álgebra de Boole: as leis fundamentais // Identidades A AND 0 = 0 A OR 1 = 1 A AND 1 = A A OR 0 = A // Complemento A AND NOT(A) = 0 A OR NOT(A) = 1 // Idempotência A AND A = A A OR A = A // Leis de De Morgan — fundamentais para simplificar circuitos NOT(A AND B) = NOT(A) OR NOT(B) // NAND NOT(A OR B) = NOT(A) AND NOT(B) // NOR // Distributividade A AND (B OR C) = (A AND B) OR (A AND C) A OR (B AND C) = (A OR B) AND (A OR C) // Por que NAND é universal? Qualquer porta vira NAND: NOT(A) = NAND(A, A) A AND B = NAND(NAND(A,B), NAND(A,B)) A OR B = NAND(NAND(A,A), NAND(B,B))
Operações binárias em código
// Operações binárias em código // C — bitmask: verificar, setar, limpar, inverter bits uint8_t flags = 0b00101100; flags & (1 << 2) // testa bit 2 → 4 (set) flags | (1 << 0) // seta bit 0 → 0b00101101 flags & ~(1 << 3) // limpa bit 3 → 0b00100100 flags ^ (1 << 5) // inverte bit 5 → 0b00001100 // Python — mesma sintaxe, inteiros de precisão arbitrária n = 0b1010 n & 0b1100 # AND → 0b1000 n | 0b0101 # OR → 0b1111 n ^ 0b1111 # XOR → 0b0101 ~n # NOT → -11 (complemento de 2) n >> 1 # shift direita → 0b0101 (divide por 2) n << 1 # shift esquerda → 0b10100 (multiplica por 2) // Trick clássico: contar bits setados (popcount) def popcount(n): count = 0 while n: count += n & 1 n >>= 1 return count # ou: bin(n).count('1')
Avaliador de expressões booleanas
Mini projeto: escreva uma função eval_bool(expr, vals) que recebe uma string como "A AND (B OR NOT C)" e um dicionário {"A":1,"B":0,"C":1} e retorna o resultado. Use recursão ou shunting-yard para parsear a precedência.
Projeto principal: implemente um simplificador de expressões booleanas via Mapas de Karnaugh para até 4 variáveis. Dada uma tabela-verdade (lista de mintermos), retorne a expressão SOP (soma de produtos) mínima. Visualize o mapa 4×4 e os grupos no terminal com cores.
Desafio extra: pesquise o algoritmo Quine-McCluskey. Implemente-o para N variáveis (sem o limite de 4 do K-map) e compare a saída com a versão K-map para os mesmos casos de teste.
Teste sua intuição
Onde você encontra isso
CPUs — ULA e comparadores
A Unidade Lógica e Aritmética do seu processador é um circuito de portas lógicas. Adição, subtração, comparação de inteiros — tudo são operações de álgebra booleana em hardware. A seção seguinte mostra como construir um somador completo com apenas AND, XOR e OR.
Criptografia — XOR e one-time pad
O XOR é a operação central de muitos cifras simétricas. No one-time pad (matematicamente perfeito), cada bit da mensagem é XORado com um bit de chave aleatória. Cifras como ChaCha20 e AES usam XOR extensivamente. XOR é usado porque é sua própria inversa: (A XOR K) XOR K = A.
FPGA — programando em lógica
FPGAs (Field-Programmable Gate Arrays) são chips com milhões de blocos lógicos reconfiguráveis. Você programa em VHDL ou Verilog descrevendo equações booleanas — e o hardware literalmente se reconfigura para implementar seu circuito. São usados em datacenters (Bing, Azure), processamento de sinal e protótipos de CPUs.