College Online
0%

Álgebra Booleana e Mapas de Karnaugh

Módulo 1 · Aula 3 ~22 min de leitura Nível: Intermediário

Vídeo da aula estará disponível em breve

Postulados e teoremas da álgebra booleana

A álgebra booleana é o sistema matemático que fundamenta toda a lógica digital. Diferente da álgebra comum, aqui as variáveis assumem apenas dois valores: 0 e 1. As operações fundamentais são AND (·), OR (+) e NOT (̅).

Propriedades fundamentais
IDENTIDADE:
  A + 0 = A          A · 1 = A

ELEMENTO NULO:
  A + 1 = 1          A · 0 = 0

IDEMPOTÊNCIA:
  A + A = A          A · A = A

COMPLEMENTO:
  A + A̅ = 1          A · A̅ = 0

INVOLUÇÃO (dupla negação):
  (A̅)̅ = A

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)

ABSORÇÃO:
  A + A·B = A        A·(A+B) = A

CONSENSO:
  A·B + A̅·C + B·C = A·B + A̅·C
i
Dualidade Observe que cada teorema tem um "dual" obtido trocando AND por OR, 0 por 1, e vice-versa. Esse princípio de dualidade significa que se um teorema é verdadeiro, seu dual também é. Isso corta pela metade o número de provas necessárias.

Teoremas de De Morgan

Os teoremas de De Morgan são provavelmente as identidades mais usadas em projetos digitais. Eles permitem converter entre AND e OR passando a negação para dentro ou fora:

De Morgan
Teorema 1: (A · B)̅ = A̅ + B̅
  "A negação de um AND é o OR das negações"

Teorema 2: (A + B)̅ = A̅ · B̅
  "A negação de um OR é o AND das negações"

Generalizado para n variáveis:
  (A₁ · A₂ · ... · Aₙ)̅ = A̅₁ + A̅₂ + ... + A̅ₙ
  (A₁ + A₂ + ... + Aₙ)̅ = A̅₁ · A̅₂ · ... · A̅ₙ

Prova por tabela-verdade (2 variáveis):
  A  B │ A·B  (A·B)̅ │ A̅  B̅  A̅+B̅
  ─────┼────────────┼────────────
  0  0 │  0     1   │  1  1   1  ✓
  0  1 │  0     1   │  1  0   1  ✓
  1  0 │  0     1   │  0  1   1  ✓
  1  1 │  1     0   │  0  0   0  ✓

Formas canônicas: SOP e POS

Qualquer função booleana pode ser expressa em duas formas canônicas:

Soma de Produtos (SOP — Sum of Products)

Cada linha da tabela-verdade onde a saída é 1 gera um mintermo — um produto (AND) de todas as variáveis, cada uma complementada ou não conforme seu valor naquela linha. A função é o OR de todos os mintermos.

Exemplo SOP
Tabela-verdade:
  A  B  C │ F
  ────────┼───
  0  0  0 │ 0
  0  0  1 │ 1  → mintermo: A̅·B̅·C  (m₁)
  0  1  0 │ 0
  0  1  1 │ 1  → mintermo: A̅·B·C  (m₃)
  1  0  0 │ 0
  1  0  1 │ 1  → mintermo: A·B̅·C  (m₅)
  1  1  0 │ 1  → mintermo: A·B·C̅  (m₆)
  1  1  1 │ 0

SOP canônica: F = A̅·B̅·C + A̅·B·C + A·B̅·C + A·B·C̅
Notação compacta: F = Σm(1, 3, 5, 6)

Produto de Somas (POS — Product of Sums)

Cada linha onde a saída é 0 gera um maxtermo — uma soma (OR) de todas as variáveis, complementadas inversamente. A função é o AND de todos os maxtermos.

Exemplo POS
Mesma função F, agora olhando as linhas com F = 0:

  A  B  C │ F
  ────────┼───
  0  0  0 │ 0  → maxtermo: (A+B+C)      (M₀)
  0  1  0 │ 0  → maxtermo: (A+B̅+C)      (M₂)
  1  0  0 │ 0  → maxtermo: (A̅+B+C)      (M₄)
  1  1  1 │ 0  → maxtermo: (A̅+B̅+C̅)      (M₇)

POS canônica: F = (A+B+C)·(A+B̅+C)·(A̅+B+C)·(A̅+B̅+C̅)
Notação compacta: F = ΠM(0, 2, 4, 7)

Simplificação algébrica

Formas canônicas geralmente não são mínimas. A simplificação reduz o número de portas necessárias no circuito:

Exemplo de simplificação
F = A̅·B̅·C + A̅·B·C + A·B̅·C + A·B·C̅

Passo 1: Agrupar termos que diferem em 1 variável
  A̅·B̅·C + A·B̅·C = B̅·C·(A̅ + A) = B̅·C
  A̅·B̅·C + A̅·B·C = A̅·C·(B̅ + B) = A̅·C

Passo 2: Combinar
  F = B̅·C + A̅·C + A·B·C̅

Passo 3: Verificar se há mais simplificações
  B̅·C + A̅·C = C·(B̅ + A̅) = C·(A·B)̅   (De Morgan)

Hmm, isso não simplifica mais. Outra abordagem:
  F = A̅·C + B̅·C + A·B·C̅
  F = C·(A̅ + B̅) + A·B·C̅
  F = C·(A·B)̅ + A·B·C̅

Se X = A·B, temos F = C·X̅ + X·C̅ = C ⊕ (A·B)
Simplificação final: F = C ⊕ (A·B)

Mapas de Karnaugh

O mapa de Karnaugh (K-map) é um método gráfico para simplificar funções booleanas. Funciona organizando os mintermos em uma grade onde células adjacentes diferem em apenas uma variável (código Gray), permitindo identificar visualmente agrupamentos para simplificação.

K-map de 2 variáveis

K-map 2 variáveis
         B=0   B=1
  A=0 │  m₀  │  m₁  │
  A=1 │  m₂  │  m₃  │

Exemplo: F = Σm(1, 2, 3)

         B=0   B=1
  A=0 │  0   │  1   │  ← grupo horizontal: m₁ (A̅·B)
  A=1 │  1   │  1   │  ← grupo horizontal: m₂, m₃ (A)
       └──────┘
        grupo vertical: m₁, m₃ (B)

Agrupamentos possíveis:
  {m₂, m₃} → A     (B varia, logo B some)
  {m₁, m₃} → B     (A varia, logo A some)

F = A + B  (cobertura mínima)

K-map de 3 variáveis

K-map 3 variáveis
Colunas em código Gray!
            BC
         00   01   11   10
  A=0 │  m₀ │ m₁ │ m₃ │ m₂ │
  A=1 │  m₄ │ m₅ │ m₇ │ m₆ │

Exemplo: F = Σm(1, 3, 5, 6)

            BC
         00   01   11   10
  A=0 │  0  │  1  │  1  │  0  │
  A=1 │  0  │  1  │  0  │  1  │

Agrupamentos:
  {m₁, m₃, m₅} — não é potência de 2, não pode!

  Grupos válidos (tamanho = potência de 2):
  {m₁, m₃} → A̅·C      (2 células)
  {m₁, m₅} → B̅·C      (2 células)
  {m₆}     → A·B·C̅    (1 célula, não simplifica)

Cobertura mínima: F = B̅·C + A·B·C̅
  (cobre m₁,m₅ com B̅·C e m₆ com A·B·C̅, falta m₃)

Melhor: F = A̅·C + B̅·C + A·B·C̅
  Ou usando a relação XOR: F = C ⊕ (A·B)

K-map de 4 variáveis

K-map 4 variáveis
              CD
           00   01   11   10
  AB=00 │  m₀ │ m₁ │ m₃ │ m₂ │
  AB=01 │  m₄ │ m₅ │ m₇ │ m₆ │
  AB=11 │ m₁₂│ m₁₃│ m₁₅│ m₁₄│
  AB=10 │  m₈ │ m₉ │ m₁₁│ m₁₀│

Exemplo: F = Σm(0, 2, 5, 7, 8, 10, 13, 15)

              CD
           00   01   11   10
  AB=00 │  1  │  0  │  0  │  1  │
  AB=01 │  0  │  1  │  1  │  0  │
  AB=11 │  0  │  1  │  1  │  0  │
  AB=10 │  1  │  0  │  0  │  1  │

Grupos:
  {m₀, m₂, m₈, m₁₀} → B̅·D̅  (4 cantos formam grupo!)
  {m₅, m₇, m₁₃, m₁₅} → B·D

Resultado: F = B̅·D̅ + B·D = B ⊙ D (XNOR)

Regra: o mapa é um TORO — bordas opostas são adjacentes!
*
Regras para agrupamento em K-maps
  • Grupos devem conter 1, 2, 4, 8 ou 16 células (potências de 2)
  • Grupos devem ser retangulares
  • Cada célula com 1 deve pertencer a pelo menos um grupo
  • Grupos maiores resultam em expressões mais simples
  • Bordas opostas são adjacentes (o mapa "enrola")
  • Don't cares (X) podem ser incluídos em grupos se ajudar

Condições don't care

Em muitas situações práticas, certas combinações de entrada nunca ocorrem ou sua saída é irrelevante. Essas são representadas como X (don't care) e podem ser tratadas como 0 ou 1, o que for mais conveniente para simplificação.

Exemplo com don't care
Detector de números BCD ≥ 5:
Entradas: A, B, C, D (4 bits)
Saída: 1 se o número BCD ≥ 5

BCD válidos: 0-9. Combinações 10-15 nunca ocorrem → don't care

              CD
           00   01   11   10
  AB=00 │  0  │  0  │  0  │  0  │  (0,1,3,2)
  AB=01 │  0  │  1  │  1  │  1  │  (4,5,7,6)
  AB=11 │  X  │  X  │  X  │  X  │  (12,13,15,14)
  AB=10 │  1  │  1  │  X  │  X  │  (8,9,11,10)

Usando Xs estrategicamente:
  {m₅,m₇,m₁₃,m₁₅} → B·D = grupo de 4 (usando X)
  {m₆,m₇,m₁₄,m₁₅} → B·C = grupo de 4 (usando X)
  {m₈,m₉,m₁₀,m₁₁,m₁₂,m₁₃,m₁₄,m₁₅} → A = grupo de 8

Resultado: F = A + B·C + B·D
Sem don't cares seria mais complexo!

No harness.os

Álgebra booleana e simplificação são fundamentais em software:

Exercícios

  1. Simplificação algébrica: Simplifique F = A̅·B̅·C + A̅·B·C + A·B̅·C + A·B·C usando apenas os teoremas de álgebra booleana. Verifique o resultado com uma tabela-verdade.
  2. K-map de 4 variáveis: Use um mapa de Karnaugh para simplificar F = Σm(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14). Desenhe o mapa, marque os agrupamentos e escreva a expressão mínima SOP.
  3. Don't care: Projete um circuito que converte um dígito BCD de entrada (4 bits) no padrão de segmentos para o segmento "a" de um display de 7 segmentos (segmento de cima, ativo para 0,2,3,5,6,7,8,9). Use K-map com don't cares para as entradas 10-15.

Resumo

Verifique seu entendimento

Pelo teorema de De Morgan, qual é a expressão equivalente a (A + B + C)̅?

  • A̅ + B̅ + C̅
  • A̅ · B̅ · C̅
  • A · B · C
  • (A̅ · B̅ · C̅)̅