🧩 formas normais · CNF e DNF
🧩 formas normais · CNF e DNF
Na lógica matemática e na álgebra booleana, expressões proposicionais podem ser reescritas em formas normais padronizadas. As duas mais importantes são a Forma Normal Conjuntiva (CNF) e a Forma Normal Disjuntiva (DNF). Elas são essenciais para circuitos lógicos, resolução automática de teoremas e simplificação de expressões.
📌 definições preliminares
Literal: uma variável proposicional (\(p\)) ou sua negação (\(\neg p\)).
Cláusula: uma disjunção de literais (ex.: \(p \lor \neg q \lor r\)).
Termo (ou monômio): uma conjunção de literais (ex.: \(p \land \neg q \land r\)).
🔷 Forma Normal Conjuntiva (CNF)
Uma fórmula está na CNF se é uma conjunção de cláusulas:
Ou seja, é um E de OUs. Exemplos:
- \(p \land q\) (cada cláusula tem um literal)
- \((p \lor q) \land (\neg p \lor q)\)
A CNF é usada no método de resolução e em provadores automáticos (SAT solvers).
🔶 Forma Normal Disjuntiva (DNF)
Uma fórmula está na DNF se é uma disjunção de termos (conjunções de literais):
Ou seja, é um OU de Es. Exemplos:
- \(p \lor q\) (cada termo tem um literal)
- \((p \land q) \lor (\neg p \land q)\)
A DNF é natural para expressar tabelas-verdade (soma de produtos).
🔄 conversão para formas normais
Para converter uma expressão qualquer em CNF ou DNF, podemos:
- Eliminar os conectivos \(\rightarrow\) e \(\leftrightarrow\) usando equivalências: \(p \rightarrow q \equiv \neg p \lor q\).
- Mover negações para dentro (Leis de Morgan) até que atinjam apenas variáveis (forma normal negativa).
- Distribuir \(\lor\) sobre \(\land\) para obter CNF, ou \(\land\) sobre \(\lor\) para obter DNF.
Exemplo: Converter \((p \rightarrow q) \land r\) em CNF.
1. Eliminar →: \((\neg p \lor q) \land r\).
2. Já está na forma: conjunção de cláusulas (a segunda cláusula é \(r\), que é um literal, portanto uma cláusula). Resultado: \((\neg p \lor q) \land r\).
Exemplo: Converter \((p \land q) \lor (\neg p \land r)\) em DNF (já está).
📊 obtendo DNF e CNF da tabela-verdade
Uma forma direta de obter as formas normais é usar a tabela-verdade.
DNF (soma dos produtos): Para cada linha onde a fórmula é V, forme um termo (conjunção) com os literais que tornam a linha verdadeira. Depois, disjunte todos esses termos.
CNF (produto das somas): Para cada linha onde a fórmula é F, forme uma cláusula (disjunção) com os literais invertidos (se a variável é V na linha, use sua negação; se F, use a variável). Depois, conjunte todas essas cláusulas.
Considere a tabela para \(p \oplus q\) (ou exclusivo):
| p | q | p⊕q |
|---|---|---|
| V | V | F |
| V | F | V |
| F | V | V |
| F | F | F |
DNF: linhas 2 e 3 → \((p \land \neg q) \lor (\neg p \land q)\).
CNF: linhas 1 e 4 → para a linha 1 (p=V,q=V): \(\neg p \lor \neg q\); para a linha 4 (p=F,q=F): \(p \lor q\). Logo CNF: \((\neg p \lor \neg q) \land (p \lor q)\).
🧠 importância e aplicações
- CNF é a base dos algoritmos SAT (satisfabilidade), usados em verificação de hardware, inteligência artificial e otimização.
- DNF é útil para implementar circuitos lógicos em duas camadas (soma de produtos) e para expressar funções booleanas de forma legível.
- Ambas são formas canônicas: qualquer expressão pode ser convertida, embora a conversão possa ser exponencial no pior caso.
- O problema de converter uma fórmula arbitrária para uma forma normal mínima é NP-difícil, mas a obtenção a partir da tabela-verdade é direta (embora a tabela cresça exponencialmente).
🧪 exemplo completo
Seja a expressão: \((p \rightarrow q) \land (q \rightarrow r) \land (p \lor r)\).
Passo 1: Eliminar →: \((\neg p \lor q) \land (\neg q \lor r) \land (p \lor r)\).
Passo 2: Já está em CNF (conjunção de cláusulas).
Passo 3: Para obter DNF, podemos distribuir \(\lor\) sobre \(\land\) (ou expandir), mas o resultado pode ser longo. A DNF equivalente é:
\((p \land q \land r) \lor (p \land q \land \neg r) \lor (\neg p \land q \land r) \lor (\neg p \land \neg q \land r)\)? (verificar na tabela).
Comentários
Postar um comentário