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 lógica de predicados
(∃x)(∃y) p(x, y) → (∃y) p(y, y)
é válida (sempre verdadeira) ou, caso contrário, fornecer uma interpretação que a torne falsa. Vamos usar conhecimento de validade e falsificabilidade de fórmulas com quantificadores.
Passo 2
Precisamos lembrar que uma fórmula é válida se for verdadeira em toda interpretação possível. Se encontrarmos pelo menos uma interpretação (domínio e relação p) em que a fórmula fique falsa, então ela não é válida.
Passo 3
Construímos uma interpretação contra-exemplo: tomemos o domínio D={a,b} e definimos a relação p de modo que apenas p(a,b) seja verdadeira, e todos os outros pares (a,a), (b,a), (b,b) sejam falsos. Nesse caso temos:
(∃x)(∃y) p(x,y) é verdadeiro pois p(a,b) é verdadeiro.
(∃y) p(y,y) é falso pois p(a,a) e p(b,b) são falsos.
Logo a implicação antecedente→consequente fica falsa.
Passo 4
Como achamos uma interpretação que torna a fórmula falsa, concluímos que ela não é válida em lógica de predicados. Não há necessidade de mais contraprovas, pois basta um contra-exemplo para demonstrar não validade.
Resposta
A fórmula não é válida. Por exemplo, na interpretação com D={a,b} e p(a,b) verdadeiro (todos os outros p(u,v) falsos), o antecedente é verdadeiro e o consequente é falso, fazendo a implicação ser falsa.