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 abaixo é válida em lógica de predicados ou, em caso negativo, apresentar uma interpretação que a faça falsa. O conteúdo envolve quantificadores universais e renomeação de variáveis ligadas. Para resolver, vamos usar a noção de equivalência entre fórmulas que só diferem no nome da variável ligada e avaliar semanticamente a implicação.
Passo 2
Note que em lógica de predicados a variável ligada é apenas um rótulo. Podemos trocar y por x sem alterar o significado de ∀y p(y). Assim fazemos a renomeação (α-conversão):
é equivalente a
Ou seja, ambas afirmam que p vale para todo elemento do domínio.
Passo 3
Agora avaliamos a implicação:
- Se
for verdadeira, então pela equivalência acima também é verdadeira, e logo . - Se
for falsa, a implicação sempre vale V (pois falsa implica qualquer coisa é verdadeira).
Assim, em toda interpretação a fórmula fica verdadeira. Portanto ela é válida (sempre assume valor verdade).
Resposta
A fórmula é válida (tautologia).