Formas Normais

$$\Huge \bigwedge_{i}\bigvee_{j} c_{ij} \qquad \bigvee_{i}\bigwedge_{j} c_{ij} $$

Objetivos

• Simplificar a linguagem lógica, descartando a necessidade do conectivo $\to$.
• Normalizar a estrutura das proposições.
• Usufruir computacionalmente da normalização e simplificação.

Definição (Literal, FND, FNC)

• Uma literal é uma proposição atómica ou a negação de uma proposição atómica.
• Qualquer proposição $p$ é equivalente a uma proposição na forma normal disjuntiva (FND): $\alert{\bigvee}_{i}\bigwedge_{j} c_{ij}$ em que cada $c_{ij}$ é uma literal.
• Qualquer proposição $p$ é equivalente a uma proposição na forma normal conjuntiva (FNC): $\alert{\bigwedge}_{i}\bigvee_{j} c_{ij}$ em que cada $c_{ij}$ é uma literal.

As formas normais usam apenas os conectivos $\land, \lor$ e $\neg$ (e este último apenas nas literais). Além disso os conectivos $\land$ e $\lor$ estão agrupados de forma “regular”.

Estas duas propriedades são importantes porque simplificam substancialmente a representação e processamento algorítmico de proposições.

Cálculo da Forma Normal Disjuntiva

$$\Huge \alert{\bigvee_{i}}\bigwedge_{j} c_{ij} $$

A designação “disjuntiva” indica que esta forma é uma disjunção ($\lor$) de conjunções de literais.

Um processo para se obter a FND de uma proposição $p$ é o seguinte:

1. Fazer a tabela da proposição $p$, atendendo às colunas com os átomos e com a proposição.
2. Em cada linha onde a proposição $p$ é $\ndT$, construir uma conjunção ($\land$):
   1. Para cada átomo $a$ que é $\ndT$ nessa linha, “contribuir” para a conjunção com $a$;
   2. Para cada átomo $a$ que é $\ndF$ nessa linha, “contribuir” para a conjunção com $\neg a$.
3. Fazer a disjunção ($\lor$) de todas as conjunções.

Exemplo: FND de $q \liff \neg p$.

$$ \begin{array}{cc|c|cc} p & q & q \liff \neg p & \land c_{ij} & L_i \cr \hline \ndT & \ndT & \ndF \cr \ndT & \ndF & \alert{\ndT} & p \land \neg q & L_2 \cr \ndF & \ndT & \alert{\ndT} & \neg p \land q & L_3 \cr \ndF & \ndF & \ndF \end{array} $$ portanto $$ \begin{aligned} q \liff \neg p &\equiv \del{p \land \neg q} \alert{\lor} \del{\neg p \land q} \ &\equiv L_2 \alert{\lor} L_3 \ &\equiv \alert{\bigvee}\bigwedge c_{ij} \end{aligned} $$

Intuitivamente, primeiro determina-se em que linhas a proposição $q \liff \neg p$ é $\ndT$?:

• No conjunto de linhas $\set{L_2, L_3}$.

Depois descreve-se a união dessas linhas ($L_i$). E cada linha é unicamente identificada pela parte conjuntiva ($\land c_{ij}$):

• $p \land \neg q$ só é $\ndT$ na linha $L_2$;
• $\neg p \land q$ só é $\ndT$ na linha $L_3$.

A FND de $p$ descreve a união das linhas em que $p$ é $\ndT$.

Cálculo da Forma Normal Conjuntiva

$$\Huge \alert{\bigwedge_{i}}\bigvee_{j} c_{ij} $$

A designação “conjuntiva” indica que esta forma é uma conjunção ($\land$) de disjunções de literais.

Um processo para se obter a FNC de uma proposição $p$ é o seguinte:

1. Fazer a tabela da proposição $p$, atendendo às colunas com os átomos e com a proposição.
2. Em cada linha onde a proposição $p$ é $\ndF$, construir uma disjunção ($\lor$):
   1. Para cada átomo $a$ que é $\ndT$ nessa linha, “contribuir” para a disjunção com $\neg a$;
   2. Para cada átomo $a$ que é $\ndF$ nessa linha, “contribuir” para a disjunção com $a$.
3. Fazer a conjunção ($\land$) de todas as disjunções.

Exemplo: FNC de $q \liff \neg p$.

$$ \begin{array}{cc|c|cc} p & q & q \liff \neg p & \land c_{ij} & L_i \cr \hline \ndT & \ndT & \alert{\ndF} & \neg p \lor \neg q & \overline{L_1} \cr \ndT & \ndF & \ndT \cr \ndF & \ndT & \ndT \cr \ndF & \ndF & \alert{\ndF} & p \lor q & \overline{L_4} \end{array} $$ portanto $$ \begin{aligned} q \liff \neg p &\equiv \del{\neg p \lor \neg q} \alert{\land} \del{p \lor q} \cr &\equiv \overline{L_1} \alert{\land} \overline{L_4} \cr &\equiv \alert{\bigwedge}\bigvee c_{ij} \end{aligned} $$

Intuitivamente, primeiro determina-se em que linhas a proposição $q \liff \neg p$ é $\ndF$?:

• No conjunto de linhas $\set{L_1, L_4}$.

Depois descreve-se a interseção dos complementos de cada uma dessas linhas ($\overline{L_i}$). O complemento de cada linha é unicamente identificado pela parte disjuntiva ($\lor c_{ij}$):

• $\neg p \lor \neg q$ só é $\ndF$ na linha $L_1$, ie é $\ndT$ nas linhas $L_2, L_3$ e $L_4$;
• $p \lor q$ só é $\ndF$ na linha $L_3$, ie é $\ndT$ nas linhas $L_1, L_2$ e $L_3$.

A FNC de $p$ descreve a interseção de linhas em que $\neg p$ é $\ndF$.

Completude Funcional

Uma das aplicações práticas das formas normais consiste na descrição de qualquer função booleana.

Isto é, dada uma função booleana (os argumentos e o valor são $\ndT/\ndF$) qualquer: $$ f : \set{\ndT, \ndF}^n \rightarrow \set{\ndT, \ndF} $$

Por exemplo $$ f\at{x_1, x_2, x_3} = x_1 \lor \del{x_2 \to x_3} $$

Esta descrição da função na forma de uma proposição é importante porque assim pode-se aplicar a Dedução Natural Proposicional para estudar a função.

Mas também pode acontecer estar disponível apenas uma “tabela” dessa função. Por exemplo $$ \begin{array}{ccc|c} x_1 & x_2 & x_3 & f\del{x_1, x_2, x_3} \cr \hline \ndT & \ndT & \ndT & \ndT \cr \ndT & \ndT & \ndF & \ndT \cr \ndT & \ndF & \ndT & \ndT \cr \ndT & \ndF & \ndF & \ndT \cr \ndF & \ndT & \ndT & \ndT \cr \ndF & \ndT & \ndF & \ndF \cr \ndF & \ndF & \ndT & \ndT \cr \ndF & \ndF & \ndF & \ndT \end{array} $$

Neste caso, em que não é dada uma proposição para descrever a função, também não pode ser utilizada a Dedução Natural Proposicional.

Importa então de resolver o seguinte problema: “Dada uma função na forma de uma tabela, é possível encontrar uma proposição que descreva essa função? Se sim, como obter tal proposição?”

Teorema (Completude funcional) Qualquer função booleana pode ser representada por uma proposição usando apenas os conectivos $\neg$, $\lor$ e $\land$.

Demonstração.

Basta aplicar a cálculo da FNC ou da FND à tabela da função.

Exemplo. Encontrar uma proposição que descreveva uma dada função booleana.

$$ \begin{array}{ccc|c|c} x_1 & x_2 & x_3 & f\del{x_1, x_2, x_3} & \overline{L_i} \cr \hline \ndT & \ndT & \ndT & \ndT \cr \ndT & \ndT & \ndF & \ndT \cr \ndT & \ndF & \ndT & \ndT \cr \ndT & \ndF & \ndF & \ndT \cr \ndF & \ndT & \ndT & \ndT \cr \ndF & \ndT & \ndF & \ndF & x_1 \lor \neg x_2 \lor x_3\cr \ndF & \ndF & \ndT & \ndT \cr \ndF & \ndF & \ndF & \ndT \end{array} $$

Portanto $$ f\at{x_1, x_2, x_3} = x_1 \land \neg x_2 \land x_3 $$

Fica como exercício mostar que $x_1 \land \neg x_2 \land x_3$ e $x_1 \lor \del{x_2 \to x_3}$ são equivalentes. Isso pode ser feito de duas formas distintas:

1. Com duas provas DNP: $x_1 \land \neg x_2 \land x_3 \dashv \vdash x_1 \lor \del{x_2 \to x_3}$.
2. Com uma tabela: $x_1 \lor \del{x_2 \to x_3} \equiv x_1 \land \neg x_2 \land x_3$.

O Teorema de Completude e Validade garante que qualquer uma destas duas formas é suficiente.

Exercício: Encontre uma proposição para representar a função booleana dada na tabela seguinte.

$$ \begin{array}{ccc|c} x & y & z & f\at{x, y, z} \cr \hline \ndT & \ndT & \ndT & \ndT \cr \ndT & \ndT & \ndF & \ndF \cr \ndT & \ndF & \ndT & \ndF \cr \ndT & \ndF & \ndF & \ndT \cr \ndF & \ndT & \ndT & \ndT \cr \ndF & \ndT & \ndF & \ndT \cr \ndF & \ndF & \ndT & \ndF \cr \ndF & \ndF & \ndF & \ndF \end{array} $$