Verifique a validade das seguintes fórmulas, utilizando o método da CNF:
Passo 1
O enunciado pede para verificar a validade da fórmula
usando o método de CNF. O conteúdo aqui é lógica proposicional e vamos testar se
é tautologia mostrando que a negação
é insatisfatível quando convertida para CNF.
Passo 2
Para verificar a validade de
, consideramos a negação
e mostramos que
não tem nenhuma interpretação que a torne verdadeira (ou seja, suas cláusulas em CNF entram em contradição).
Passo 3
Escrevendo explicitamente
aplicamos De Morgan a uma disjunção:
Passo 4
Agora eliminamos a implicação
:
Logo
Passo 5
Observamos que
já está em forma normal conjuntiva (CNF): é a conjunção das cláusulas
,
e
.
Passo 6
Verificamos insatisfatibilidade:
da cláusula e da cláusula
deduzimos
,
que contradiz a cláusula . Logo não há interpretação que satisfaça todas as cláusulas.
da cláusula
que contradiz a cláusula
Resposta
A fórmula
é válida, pois a CNF da sua negação é insatisfatível.