Verifique a validade das seguintes fórmulas, utilizando o método da CNF:
Passo 1
O enunciado pede pra checar se a fórmula
é válida (isto é, uma tautologia), usando o método da forma normal conjuntiva (CNF). A ideia é assumir que ela é verdadeira e ver se a negação dá uma CNF insatisfatível.
Passo 2
Primeiro, a gente transforma a implicação em disjunção. Lembrando que
temos
Passo 3
Agora negamos a fórmula equivalente e aplicamos De Morgan:
Isso já está quase em CNF: é a conjunção de duas cláusulas. Em notação de cláusulas, fica
Passo 4
Vamos resolver essas cláusulas:
- Da cláusula
e da cláusula resolvemos sobre , gerando a cláusula . - Não há nenhuma cláusula
para continuar a resolução, então não chegamos à cláusula vazia.
Passo 5
Como não surgiu contradição (não obtivemos cláusula vazia), a negação da fórmula é satisfatível. Logo, a fórmula original não é válida.
Resposta
A fórmula
não é válida.