Álgebra da lógica proposicional

A álgebra da lógica proposicional especifica como os elementos podem ser manipulados em fórmulas. Essas manipulações permitem que sejam geradas fórmulas equivalentes a outras através de simplificações das expressões lógicas.
Antes de mais nada é importante definir o conceito de dual, pois ele forma a base de muitas manipulações possíveis dentro da lógica proposicional.

O dual de uma fórmula definida em termos de símbolos atômicos $(p,q,\dots )$, símbolos de verdade $(V,F)$ e dos conectivos lógicos de conjunção $(\wedge )$ e disjunção $(\vee )$ é obtido substituindo-se todas as ocorrências de:

• $V$ por $F$ e vice-versa
• $\wedge$ por $\vee$ e vice-versa
  Exemplo: o dual da proposição $(p\wedge q)\vee F$ é a proposição $(p\vee q)\wedge V$

Leis de equivalência

A seguir são apresentadas as mais importantes leis de equivalência, acompanhadas de sua forma dual.

Lei	Nome
$p\wedge \neg p\equiv F$	Lei da contradição
$p\vee \neg p\equiv V$	Lei do terceiro excluído
$\begin{array}{r}p\wedge V\equiv p\\ p\vee F\equiv p\end{array}$	Leis da identidade
$\begin{array}{r}p\wedge F\equiv F\\ p\vee V\equiv V\end{array}$	Leis da dominação
$\begin{array}{r}p\wedge p\equiv p\\ p\vee p\equiv p\end{array}$	Leis idempotentes
$\neg \neg p\equiv p$	Dupla negação
$\begin{array}{r}p\wedge q\equiv q\wedge p\\ p\vee q\equiv q\vee p\end{array}$	Leis comutativas
$\begin{array}{r}(p\wedge q)\wedge r\equiv p\wedge (q\wedge r)\\ (p\vee q)\vee r\equiv p\vee (q\vee r)\end{array}$	Leis associativas
$\begin{array}{r}p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)\\ p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)\end{array}$	Leis distributivas
$\begin{array}{r}\neg (p\wedge q)\equiv \neg p\vee \neg q\\ \neg (p\vee q)\equiv \neg p\wedge \neg q\end{array}$	Leis de DeMorgan
$p⟹q\equiv \neg p\vee q$	Definição de $⟹$ em termos de $\vee$ e $\neg$
$p⟺q\equiv (p⟹q)\wedge (q⟹p)$	Definição de $⟺$ em termos de $⟹$ e $\wedge$
$p⟺q\equiv (\neg p\vee q)\wedge (\neg q\vee p)$	Definição de $⟺$ em termos de $\vee$ e $\neg$
$\begin{array}{r}(p\vee (p\wedge q))\equiv p\\ (p\wedge (p\vee q))\equiv p\end{array}$	Leis da absorção
$\begin{array}{r}(p\wedge q)\vee (\neg p\wedge q)\equiv q\\ (p\vee q)\wedge (\neg p\vee q)\equiv q\end{array}$	Generalização das Leis da absorção

Formas normais

Usando as leis de equivalência é possível manipular as proposições e colocá-las em formatos mais desejáveis. Através das formas normais é possível padronizar as proposições compostas, tornando sua identificação comparação mais simples e objetivas.

Para toda fórmula $\beta$ da Lógica proposicional existe uma fórmula $\alpha$ tanto na FNC quanto na FND que é equivalente a $\beta$, ou seja: $\alpha \equiv \beta$.

As formas normais são compostas fundamentalmente por literais organizados dentro de cláusulas (que variam dependendo da forma normal).

• Literais (L): elemento básico das formas normais, um literal é uma formula atômica ($p$) ou a negação de uma fórmula atômica ($\neg p$).

Forma normal conjuntiva (FNC)

Uma Forma Normal Conjuntiva (FNC), ou Forma Clausal, é composta por literais e cláusulas.

• Cláusulas (C): uma cláusula é uma disjunção de literais $L_1\vee L_2\vee \cdots \vee L_n$, onde $n\ge 0$ é o tamanho da cláusula.

Uma fórmula proposicional está na FNC se e somente se ela for uma conjunção de cláusulas, ou seja: $C_1\wedge C_2\wedge \cdots \wedge C_{n}n\ge 1$.

Forma normal disjuntiva (FND)

Uma Forma Normal Disjuntiva (FND) é composta por literais e cláusulas duais.

• Cláusulas duais (C): uma cláusula dual é uma conjunção de literais $L_1\wedge L_2\wedge \cdots \wedge L_n$, onde $n\ge 0$ é o tamanho da cláusula.

Uma fórmula proposicional está na FND se e somente se ela for uma disjunção de cláusulas duais, ou seja: $C_1\vee C_2\vee \cdots \vee C_{n}n\ge 1$.