Quais das proposições seguintes são tautologias, quais são contradições e quais são contingências? Justifique.
(\exists x)(\forall y)(P(x, y)) \rightarrow(\forall y)(\exists x)(P(x, y))

Passo 1

O enunciado apresenta a fórmula de lógica de predicados
(\exists x)(\forall y)\,P(x,y)\;\rightarrow\;(\forall y)(\exists x)\,P(x,y)
e pergunta se ela é uma tautologia, contradição ou contingência. Aqui o conteúdo é semântica de lógica de predicados, usando quantificadores e implicação. Vamos mostrar que essa fórmula é verdadeira em toda interpretação, isto é, é uma tautologia.

Passo 2

Para testar se uma fórmula na lógica de predicados é tautologia, verificamos que, em qualquer domínio não vazio e para qualquer interpretação do predicado P, toda vez que o antecedente é verdadeiro, o consequente também será verdadeiro, garantindo que a implicação seja sempre verdadeira.

Passo 3

Suponha que, em alguma interpretação arbitrária,
\;(\exists x)(\forall y)\,P(x,y)
seja verdadeiro. Isso significa que existe um elemento a no domínio tal que, para todo y, P(a,y) é verdadeiro.

Passo 4

Dado esse mesmo elemento a, para cada y fixo temos P(a,y). Logo, para cada y existe um x — precisamente x=a — tal que P(x,y). Em símbolos:
\forall y\,(\exists x)\,P(x,y)
é verdadeiro.

Passo 5

Concluímos que sempre que o antecedente
(\exists x)(\forall y)\,P(x,y)
é verdadeiro, o consequente
(\forall y)(\exists x)\,P(x,y)
também o é. Portanto, a implicação é verdadeira em toda interpretação.

Resposta

A fórmula
(\exists x)(\forall y)\,P(x,y)\;\rightarrow\;(\forall y)(\exists x)\,P(x,y)
é uma tautologia.

Exercícios relacionados