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.
(forall y) p(y) (forall x) p(x)

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):
(forall y),p(y)
é equivalente a
(forall x),p(x)
Ou seja, ambas afirmam que p vale para todo elemento do domínio.

Passo 3

Agora avaliamos a implicação:
  • Se forall y,p(y) for verdadeira, então pela equivalência acima forall x,p(x) também é verdadeira, e logo Vto V = V.
  • Se forall y,p(y) for falsa, a implicação Fto Q 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).

Exercícios relacionados