Formas Normais

$i ⋀ j ⋁ c_{ij} i ⋁ j ⋀ c_{ij}$

Objectivos

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): $⋁_{i} ⋀_{j} c_{ij}$ em que cada $c_{ij}$ é uma literal.
Qualquer proposição $p$ é equivalente a uma proposição na forma normal conjuntiva (FNC): $⋀_{i} ⋁_{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

$i ⋁ 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:

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

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

$p v v f f q v f v f q \leftrightarrow \neg p f v v f \land c_{ij} p \land \neg q \neg p \land q L_{i} L_{2} L_{3}$ portanto $q \leftrightarrow \neg p \equiv (p \land \neg q) \lor (\neg p \land q) \equiv L_{2} \lor L_{3} \equiv ⋁ ⋀ c_{ij}$

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

No conjunto de linhas ${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ó é $v$ na linha $L_{2}$ ;
$\neg p \land q$ só é $v$ na linha $L_{3}$ .

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

Cálculo da Forma Normal Conjuntiva

$i ⋀ 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:

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

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

$p v v f f q v f v f q \leftrightarrow \neg p f v v f \land c_{ij} \neg p \lor \neg q p \lor q L_{i} \overline{L_{1}} \overline{L_{4}}$ portanto $q \leftrightarrow \neg p \equiv (\neg p \lor \neg q) \land (p \lor q) \equiv \overline{L_{1}} \land \overline{L_{4}} \equiv ⋀ ⋁ c_{ij}$

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

No conjunto de linhas ${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ó é $f$ na linha $L_{1}$ , ie é $v$ nas linhas $L_{2}, L_{3}$ e $L_{4}$ ;
$p \lor q$ só é $f$ na linha $L_{3}$ , ie é $v$ nas linhas $L_{1}, L_{2}$ e $L_{3}$ .

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

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 $v / f$ ) qualquer: $f : {v, f}^{n} \to {v, f}$

Por exemplo $f (x_{1}, x_{2}, x_{3}) = x_{1} \lor (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 $x_{1} v v v v f f f f x_{2} v v f f v v f f x_{3} v f v f v f v f f (x_{1}, x_{2}, x_{3}) v v v v v f v v$

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.

$x_{1} v v v v f f f f x_{2} v v f f v v f f x_{3} v f v f v f v f f (x_{1}, x_{2}, x_{3}) v v v v v f v v \overline{L_{i}} x_{1} \lor \neg x_{2} \lor x_{3}$

Portanto $f (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 (x_{2} \to x_{3})$ são equivalentes. Isso pode ser feito de duas formas distintas:

Com duas provas DNP: $x_{1} \land \neg x_{2} \land x_{3} ⊣⊢ x_{1} \lor (x_{2} \to x_{3})$ .
Com uma tabela: $x_{1} \lor (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.

$x v v v v f f f f y v v f f v v f f z v f v f v f v f f (x, y, z) v f f v v v f f$

Lógica e Computação

Formas Normais

Cálculo da Forma Normal Disjuntiva

Cálculo da Forma Normal Conjuntiva

Completude Funcional