Questão 3 (2 pts.). Considere a sentença:
\varphi=\forall x \forall y(\neg((x<y) \vee(y<x)) \rightarrow(x=y))
  1. determine se \varphi é uma sentença aberta ou fechada, justificando sua resposta, e expresse \varphi em palavras,
  2. negue \varphi, mostrando todos os passos para colocar a fórmula em forma tal que a negação apareça na frente de apenas fórmulas atômicas e expresse \neg \varphi em palavras.

Passo 1

O enunciado pede duas coisas:
  1. Determinar se \varphi é uma sentença aberta ou fechada, justificando a resposta, e traduzir \varphi para palavras.
  2. Negar \varphi, mostrando todos os passos necessários para transformar a negação de modo que ela apareça apenas na frente de fórmulas atômicas, e traduzir \neg\varphi para palavras.
A fórmula dada é
\varphi=\forall x \forall y(\neg((x<y) \vee(y<x)) \rightarrow(x=y)).

Passo 2

O que significa uma fórmula ser aberta ou fechada (explicação didática):
  • Uma fórmula tem variáveis que podem ser “livres” ou “ligadas (bound)”.
  • Uma variável é ligada quando aparece dentro do escopo de um quantificador que a usa (por exemplo, \forall x ou \exists x).
  • Uma fórmula é fechada (também chamada de sentença) se não houver variáveis livres nela — isto é, todas as variáveis estão ligadas por quantificadores.
  • Uma fórmula é aberta se existe pelo menos uma variável livre.
    Exemplo simples: a fórmula x+1>0 é aberta (tem a variável livre x). A fórmula \forall x (x+1>0) é fechada (a variável x está ligada pelo quantificador).

Passo 3

Aplicando isso a \varphi:
  • A fórmula tem quantificadores \forall x e \forall y no início, e dentro do corpo aparecem apenas as variáveis x e y.
  • Cada ocorrência de x e y está no escopo dos respectivos quantificadores \forall x e \forall y. Portanto não há variáveis livres.
    Conclusão: \varphi é uma fórmula fechada (uma sentença). (Justificativa: todos os nomes de variável são ligados por quantificadores universais no início.)

Passo 4

Expressando \varphi em palavras (tradução literal e interpretação intuitiva):
  • Fórmula simbólica:
\varphi=\forall x \forall y(\neg((x<y) \vee(y<x)) \rightarrow(x=y)).
  • Tradução em palavras: “Para todos x e para todos y, se não vale que x<y ou y<x, então x=y.”
  • Interpretação intuitiva: sempre que duas coisas não estão relacionadas por < em nenhum dos sentidos (ou seja, nem x<y nem y<x é verdadeiro), então essas duas coisas são iguais. Em termos de ordens, diz que não existem dois elementos distintos que sejam incomparáveis — se eles não se relacionam por < em nenhum sentido, então são o mesmo elemento.

Passo 5

Agora vamos negar \varphi e levar a negação até aparecer só em frente a fórmulas atômicas, passo a passo. Primeiro escrevemos a negação diretamente:
\neg\varphi=\neg\forall x \forall y\big(\neg((x<y) \vee(y<x)) \rightarrow(x=y)\big).
Regra que vamos usar: a negação passa por um quantificador universal transformando-o em existencial:
\neg\forall u\,\psi \equiv \exists u\,\neg\psi.
Aplicando essa regra ao primeiro quantificador \forall x e ao segundo \forall y:

Passo 6

Aplicando a troca de quantificadores (duas vezes):
\neg\varphi = \exists x\,\neg\forall y\big(\neg((x<y) \vee(y<x)) \rightarrow(x=y)\big)
\neg\varphi = \exists x\exists y\,\neg\big(\neg((x<y) \vee(y<x)) \rightarrow(x=y)\big).
(Explicação: a negação de \forall x\forall y torna-se \exists x\exists y e a negação desloca-se para o corpo.)

Passo 7

Agora precisamos remover a negação que está em frente de uma implicação. Usamos a equivalência lógica:
\neg(P\rightarrow Q)\equiv P\land\neg Q.
Aqui P é \neg((x<y)\vee(y<x)) e Q é (x=y). Aplicando a equivalência:
\neg\big(\neg((x<y)\vee(y<x)) \rightarrow (x=y)\big) \equiv \neg((x<y)\vee(y<x)) \land \neg(x=y).
Substituindo na expressão com quantificadores:
\neg\varphi = \exists x\exists y\big(\neg((x<y)\vee(y<x)) \land \neg(x=y)\big).
(Explicação: a negação de uma implicação significa que a hipótese ocorre e a conclusão falha.)

Passo 8

Ainda temos uma negação em frente de uma disjunção dentro de \neg((x<y)\vee(y<x)). Aplicamos a Lei de De Morgan para disjunção:
\neg(A\vee B)\equiv \neg A \land \neg B.
Tomando A como (x<y) e B como (y<x), obtemos:
\neg((x<y)\vee(y<x)) \equiv \neg(x<y) \land \neg(y<x).
Substituindo:
\neg\varphi = \exists x\exists y\big(\neg(x<y) \land \neg(y<x) \land \neg(x=y)\big).
Agora a negação aparece apenas imediatamente em frente de fórmulas atômicas (x<y), (y<x), (x=y). Portanto chegamos à forma desejada.

Passo 9

Expressando \neg\varphi em palavras (tradução e interpretação):
  • Fórmula simbólica final:
\neg\varphi = \exists x\exists y\big(\neg(x<y) \land \neg(y<x) \land \neg(x=y)\big).
  • Tradução em palavras: “Existem x e y tais que não vale x<y, e não vale y<x, e além disso x\neq y.”
  • Interpretação intuitiva: existem dois elementos distintos que são incomparáveis pelo predicado < — isto é, há x e y diferentes para os quais nem x<y nem y<x é verdadeiro. Em termos de ordens, isso nega a propriedade de totalidade que \varphi expressava.

Resposta

\varphi é uma sentença fechada (todas as variáveis x,y estão ligadas pelos quantificadores \forall x\forall y). Em palavras: “Para todos x e y, se não é verdade que x<y ou y<x, então x=y.”\n
\neg\varphi = \exists x\exists y\big(\neg(x<y) \land \neg(y<x) \land \neg(x=y)\big). Em palavras: “Existem x e y tais que nem x<y nem y<x e, além disso, x\neq y.”

Exercícios relacionados