Linguagem da Lógica proposicional - Formas normais
Contato
- Jean Paulo Martins (jeanmartins utfpr edu br)
- Sala 105, Bloco S (UTFPR - Campus Pato Branco)
Conteúdo
Formas normais
Dada uma fórmula qualquer $\phi$ na linguagem da lógica proposicional, existe uma fórmula $\psi$ equivalente que está na forma normal. As formas normais são fórmulas com estruturas predefinidas. Tais estruturas são definidas em termos de literais, que são nada mais que uma definição que engloba tanto símbolos proposicionais quanto suas negações. Exemplos de literais.
Definição (literal): Um literal é um símbolo proposicional ou sua negação.
Consideraremos nesta seção dois tipos de formas normais.
Forma normal conjuntiva
Uma fórmula está na forma normal conjuntiva se ela é uma conjunção de disjunção de literais. Para compreendermos essa definição, iremos por partes, primeiro, considere que uma disjunção de literais é qualquer fórmula do tipos
Portanto, a forma normal conjuntiva é a conjunção de diversas fórmulas desse tipo. Como exemplo temos a seguinte fórmulas
Forma normal disjuntiva
Uma fórmula está na forma normal disjuntiva se ela é uma disjunção de conjunção de literais. Uma conjunção de literais, é qualquer fórmula do tipo
Portanto, a forma normal disjuntiva é a disjunção de diversas fórmulas desse tipo. Como exemplo
Conversão para forma normal
Como mencionado no início desta seção, a toda fórmula há uma outra fórmula equivalente escrita na forma normal; tanto conjuntiva quanto disjuntiva. Como podemos garantir que essa afirmação seja verdadeira?
A justificativa para a veracidade dessa afirmação é o fato de que as formas normais conjuntiva e disjuntiva refletem os valores verdade presente em uma tabela-verdade. Como toda fórmula pode ser analizada por uma tabela-verdade, então toda fórmula pode ser escrita na forma normal. Vejamos como isso funciona na prática, considere a seguinte fórmula
Sua tabela verdade possui 8 linhas, e está descrita a seguir:
| $p$ | $q$ | $r$ | $(p\to q)$ | $(p\to q) \land r$ | |
|---|---|---|---|---|---|
| V | V | V | V | V | |
| V | V | F | V | F | |
| V | F | V | F | F | |
| V | F | F | F | F | |
| F | V | V | V | V | |
| F | V | F | V | F | |
| F | F | V | V | V | |
| F | F | F | V | F |
Forma normal disjuntiva (FND)
Vamos primeiro analisar como utilizar a tabela-verdade acima para transformar a fórmula $(p\to q) \land r$ em uma fórmula equivalente na forma normal disjuntiva. Para isso observemos as linhas da tabela que tornam a fórmula verdadeira, as quais estão indicadas por um * na tabela abaixo.
| $p$ | $q$ | $r$ | $(p\to q)$ | $(p\to q) \land r$ | |
|---|---|---|---|---|---|
| * | V | V | V | V | V |
| V | V | F | V | F | |
| V | F | V | F | F | |
| V | F | F | F | F | |
| * | F | V | V | V | V |
| F | V | F | V | F | |
| * | F | F | V | V | V |
| F | F | F | V | F |
Se essas são as únicas atribuições de valores-verdade às variáveis $p, q, r$ que tornam a fórmula verdadeira, podemos as utilizar para definir uma outra fórmula, que sempre será verdadeira quando $(p\to q) \land r$ for verdadeira. Para isso, iremos escrever cada uma dessas linhas como uma conjunção. A primeira linha marcada seria representada pela fórmulas
A segunda linha marcada seria representada portanto como
E seguindo a mesma ideia, a terceira seria
Como cada uma dessas fórmulas representa uma determinada atribuição de valores-verdade que torna a fórmula original verdadeira, a sua disjunção cobre todas as situações de veracidade da fórmula original
Forma normal conjuntiva (FNC)
Para convertermos uma fórmula na forma normal conjuntiva utilizaremos ideia similar à usada anteriormente. No entanto, ao invés de nos focar nas linhas que tornam a fórmula verdadeira, consideraremos àquelas que a torma falsa, as quais estão indicadas na tabela a seguir.
| $p$ | $q$ | $r$ | $(p\to q)$ | $(p\to q) \land r$ | |
|---|---|---|---|---|---|
| V | V | V | V | V | |
| * | V | V | F | V | F |
| * | V | F | V | F | F |
| * | V | F | F | F | F |
| F | V | V | V | V | |
| * | F | V | F | V | F |
| F | F | V | V | V | |
| * | F | F | F | V | F |
A ideia a ser seguida neste caso é que, estas atribuições de valores-verdade são as únicas alternativas em que a fórmula $(p\to q) \land r$ é falsa. Se falharmos em encontrar uma atribuição que se encaixe numa dessas alternativas, então a fórmula, por consequência, será verdadeira. A forma normal conjuntiva dessa fórmula será a conjunção desses casos.
Em resumo, para a fórmula $(p\to q) \land r$ ser verdadeira, todos os casos em que ela poderia ser falsificada (linhas da tabela) devem falhar.
Benefícios das formas normais
Por que nos preocuparíamos em utilizar fórmulas na forma normal conjuntiva, por exemplo? Visto que muitas vezes isso gera fórmulas maiores que a original, não parece evidente tal motivação. No entanto, com uma análise adicional perceberemos que facilmente que a forma normal conjuntiva nos permite muito mais facilmente verificar a satisfabilidade de uma fórmula. Consideremos, como exemplo, a fórmula na forma normal conjuntiva definida a seguir
Por definição da conjunção, esta fórmula completa apenas será verdadeira se cada um de seus conjuctos forem verdadeiros. Por outro lado, cada um dos conjuctos é uma disjunção. Suponhamos agora que queremos verificar se a fórmula é uma tautologia. Para isso, o seguinte lema se aplica:
Lema: Uma disjunção de proposições literais $\ell_1 \lor \ell_2 \lor \dots \lor \ell_n$ é uma tautologia se e somente se exitem $1\leq i, j\leq m$ tais que $\ell_i$ é $\neg\ell_j$.
Em outras palavras, uma disjunção é uma tautologia apenas se contiver um símbolo e sua negação. Como é evidente, do ponto de vista computacional, isso pode ser verificado muito mais facilmente em uma fórmula em forma normal.
Se por outro lado, precisarmos demonstrar que uma fórmula em forma normal conjuntiva é satisfatível, podemos nos basear na seguinte proposição.
Proposição: Seja uma fórmula $\phi$ da lógica proposicional. Então $\phi$ pode ser satisfeita se e somente se $\neg \phi$ não for uma tautologia.
Cláusulas de Horn
As cláusulas de Horn são compostas por no máximo um literal positivo. Este tipo de fórmula posssui características interessantes em termos da verificação de satisfabilidade, que verificaremos depois. Uma cláusula de Horn tem a forma
Deste modo, para satisfazer cláusulas desse tipo, basta atribuir valores-verdade falso para todas as variáveis envolvidas. Como toda cláusula de Horn é a disjunção de vários literais negados, um deles sendo verdadeiro torna toda a cláusula verdadeira.
Exercícios
Transformar as seguinte fórmulas para a forma normal conjuntiva e disjuntiva (FNC, FND), utilizando tabelas-verdade. Verificar se algumas das fórmulas contém cláusulas de Horn.
Referências
Seção 1.3: Pgs. 25-28, Logica - Huth & Ryan (PDF).