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
O enunciado pede para verificar se a fórmula de primeira ordem abaixo é válida (verdadeira em toda interpretação) ou então fornecer uma interpretação que a torne falsa:
Estamos trabalhando com equivalências lógicas envolvendo quantificadores e queremos testar sua validade.
Passo 2
Repare que
é equivalente à
pois se existe algum x que satisfaça
, então de fato a condicional exige
; caso contrário, a implicação é trivialmente verdadeira em cada x.
No nosso caso, tomamos
,
e obtemos:
No nosso caso, tomamos
e obtemos:
Passo 3
De forma análoga, o outro lado da equivalência se reescreve como
Portanto a fórmula original equivale a
Não há simetria obrigatória entre esses dois condicionalões, logo não devemos esperar validade geral.
Passo 4
Para construir um contra‐exemplo, basta tomar um domínio unitário e atribuir valores de forma a falsificar a equivalência. Seja a interpretação
definida por:
• Domínio .
• Constrantes de nome interpretam-se como
.
• Predicados avaliados em :
verdadeiro,
falso,
verdadeiro,
falso.
• Domínio
• Constrantes de nome
• Predicados avaliados em
Passo 5
Avaliação na interpretação
:
• é verdadeiro (pois
é verdadeiro).
• é falso (pois
é falso).
Logo o condicional
•
•
Logo o condicional
é
• Por outro lado,
é (F\toV = V.]
Logo a equivalência avaliada fica contradizendo validade.
Logo a equivalência avaliada fica
Passo 6
Portanto a fórmula não é válida em primeira ordem e a interpretação
acima a torna falsa.
Resposta
Não é válida. Por exemplo, na interpretação com domínio
em que
a equivalência vale