Algumas das fórmulas a seguir são válidas (tautologias), outras não. Para cada fórmula, demonstre se ela é válida ou defina uma interpretação que a interprete como sendo falsa.
Passo 1
Nesse exercício, a gente precisa verificar se a fórmula de LPO é uma tautologia (válida em toda interpretação) ou não. O conteúdo aqui é lógica de primeira ordem, mais especificamente avaliação de fórmulas em modelos: entender quantificadores, implicação e como construir um contra‐exemplo (interpretação) quando a fórmula não for válida.
Vamos reescrever a fórmula de forma mais clara, assumindo a precedência usual de quantificadores (eles só valem até o parêntese mais próximo) e da seta “→”:
Vamos reescrever a fórmula de forma mais clara, assumindo a precedência usual de quantificadores (eles só valem até o parêntese mais próximo) e da seta “→”:
Assim temos uma sentença fechada (sem variáveis livres). A gente avalia se em todo modelo essa sentença é verdadeira (válida) ou encontra um modelo em que seja falsa.
Passo 2
Uma fórmula fechada da forma
é falsa num modelo se, para todo elemento do domínio, a subfórmula
é falsa. E
é falsa se existe algum
que torna
falsa. Além disso,
é falsa exatamente quando
é verdadeira e
é falsa.
Passo 3
Para mostrar que a sentença não é válida, construímos um modelo
tal que ela dê falsa. Seja o domínio
e definimos a interpretação de
como
Ou seja,
é verdadeira sempre que
está nessa lista.
Passo 4
Agora avaliamos
Para cada candidato
- Se
- Se
Em ambas as tentativas, não existe
Passo 5
Concluímos que há pelo menos um modelo que torna a sentença falsa, portanto ela não é válida.
Resposta
A fórmula não é válida. Um contra‐exemplo é o modelo com domínio
e
, em que a sentença avalia como falsa.