Tratamento das Variáveis

As variáveis são uma das novidades da Lógica de Primeira Ordem em relação à Lógica Proposicional. Embora intuitivamente comuns, nos termos formais há uma série de cuidados necessários com as variáveis.

Ocorrências Ligadas e Ocorrências Livres

• A definição de fórmula (de primeira ordem) não é simples.
  • Envolve relações, conectivos, e termos que, por sua vez são baseados em constantes, variáveis e funções.
• As variáveis têm um papel especial e delicado.

Intuitivamente, o papel da variável $x$ na fórmula $\exists x2<x$ é simples de entender. Assim como $y$ em $\exists y2<y$. Mas em casos mais complexos, como $\exists xz<x$, há influências entre $z$ e $x$.

Essas influências podem ter consequências indesejadas pelo que é necessário descrever e lidar com essas influências.

Definição (Ocorrência Ligada e Ocorrência Livre)

Numa fórmula $\forall xp$ ou $\exists xp$ qualquer ocorrência de $x$ em $p$ diz-se ligada. As ocorrências não ligadas dizem-se livres.

Exemplo. Ocorrências Ligadas e Ocorrências Livres

Nesta lista de fórmulas as ocorrências livres estão assinaladas desta forma "$a$" e as ligadas desta "$b$".

$$\begin{array}{l}x+3>y\\ \exists xx>2\\ x=y\\ \exists xx=y\\ \forall x\exists yx=y\\ y/2=e^{-1}\vee \exists y\forall xx>y\\ \left(\forall xx=y\right)\to x<\pi \end{array}$$

Nota. Uma variável pode ocorrer livre e ligada numa fórmula — a classificação "livre/ligada" diz respeito a cada ocorrência de cada variável.

Há uma analogia entre as fórmulas com ocorrências ligadas e os somatórios.

Intuitivamente, uma ocorrência ligada pode ser sintaticamente trocada por outra:

$$\forall xx>2\equiv \forall yy>2.$$

Tal como em expressões mais comuns, envolvendo somatórios:

$$\sum _{i=1}^{10}3i=\sum _{j=1}^{10}3j.$$

Condições e Parâmetros

$$p\left(x\right)$$

• Uma ocorrência livre condiciona a variável. Na fórmula $x<2$ a variável $x$ ocorre livre e essa ocorrência condiciona os valores que $x$ pode ter.
• Considerando a fórmula, a ocorrência da variável livre parametriza a fórmula. Para $\exists y\left(2y=x\right)$ ser verdadeira é necessário que $x$ seja um número par.

Definição (Condição, Parâmetro)

Quando a variável $x$ ocorre livre na fórmula $p$ diz-se que $p$ é uma condição em $x$ ou que $x$ é um parâmetro de $p$ e escreve-se $$p\left(x\right).$$

Nota. A expressão "$p(x)$" não é uma fórmula; "$p$" é que é.

• A escrita "$p\left(x\right)$" indica que $x$ está condicionada por $p$ ou seja, $p$ é parametrizada por $x$.
• Quando $x$ não ocorre livre em $p$ então $p\left(x\right)$ não condiciona $x$.
• Mas, por exemplo, a fórmula $x>0$ condiciona $x$; tem de ser positivo.

Exemplo. Condições e Parâmetros

• $p\left(x\right):\exists yx>y$.
• $p\left(x,y\right):\neg \left(x=y\right)$.
• $p\left(x\right):\neg \left(x=y\right)$.
• $p\left(x,y\right):\left(\exists xy>x\right)\wedge \left(\exists yy>x\right)\wedge \left(\exists zy>z>x\right)$.
• $p\left(x,y\right):\left(\exists uy>u\right)\wedge \left(\exists vv>x\right)\wedge \left(\exists wy>w>x\right)$.

Substituição

$$p\left\{x/t\right\}$$

Uma variável pode ser intuitivamente interpretada como uma "marca" a ser substituida por um valor.

Na fórmula $x^2-4=0$ a variável $x$ representa um valor arbitrário ou desconhecido. Por exemplo, se "$x$ tiver o valor $2$", então a fórmula $x^2-4=0$ passa a $2^2-4=0$ que, na aritmética, é "verdade".

Interessa formalizar esta "transformação" de $x^2-4=0$ em $2^2-4=0$, substituindo a variável $x$ pelo termo $2$.

Definição (Substituição)

Sejam $p$ uma fórmula, $x$ uma variável e $t$ um termo.

A substituição em $p$ de $x$ por $t$, escrita $p\left\{x/t\right\}$, é a fórmula que se obtém substituindo em $p$ todas as ocorrências livres de $x$ por $t$.

Se $x$ não ocorre livre em $p$ então $p\left\{x/t\right\}==p$. Isto é, a substituição "não teve efeito". Aqui é usada a "igualdade de expressões", $==$, para mostrar que $p$ e $p\left\{x/t\right\}$ são sintaticamente a mesma fórmula; os mesmos símbolos, a mesma estrutura, nas mesmas posições.

Exemplos. Substituição

• $p:\exists yx>y$:
  • $p\left\{x/z\right\}$ é $\exists yz>y$.
  • $p\left\{y/w\right\}$ é $\exists yx>y$ — porque $y$ não é livre.
• $p:\neg \left(x=y\right)$:
  • $p\left\{x/y\right\}$ é $\neg \left(y=y\right)$ — Cuidado!
  • $p\left\{y/w\right\}$ é $\neg \left(x=w\right)$.
• $p:\left(\exists xy>x\right)\vee \left(\forall yy>x\right)\to \left(\exists zy>z>x\right)$:
  • $p\left\{y/v\right\}$ é $\left(\exists xv>x\right)\vee \left(\forall yy>x\right)\to \left(\exists zv>z>x\right)$.
  • $p\left\{y/v\right\}\left\{x/u\right\}$ é $\left(\exists xv>x\right)\vee \left(\forall yy>u\right)\to \left(\exists zv>z>u\right)$.

Efeitos Indesejados das Substituições

Na aritmética, a fórmula $\exists yx<y$ é verdadeira: dado um número $x$ qualquer, existe outro número maior. Se $x=41$ fazendo, por exemplo, $y=x+1=42$ mostra que existe um número maior que esse $x$.

Isto sugere que na fórmula $\exists yx<y$ pode-se substituir a variável $x$ por outro termo qualquer. E em geral, é verdade.

• Substituindo $\left\{x/25041973\right\}$ obtém-se $\exists y25041973<y$ que é verdade: basta escolher $y=25041974$.

Sem cuidado na substituição podem resultar efeitos inesperados ou indesejados.

• Substituirmos $\left\{x/y\right\}$ obtém-se $\exists yy<y$, que é uma fórmula falsa: nenhum número é menor que ele próprio!

Interessa distinguir as substituições "inócuas" das que provocam estes efeitos inesperados ou até indesejados.

Definição (Variável Afetada, Termo Livre)

Sejam $p$ uma fórmula e $x$ uma variável em $p$.

• Variável Afetada. A variável $x$ é afetada por $y$ em $p$, ou $y$ afeta $x$ em $p$, se, em $p$, há uma ocorrência livre de $x$ numa sub-fórmula de $p$ da forma $\forall yq$ ou $\exists yq$.
• Termo Livre. O termo $t$ é livre para $x$ em $p$ se nenhuma variável de $t$ afeta $x$ em $p$.

Isto é:

• A variável $y$ não afeta $x$ em $p$ se
  • Em nenhuma sub-fórmula de $p$ da forma $\forall yq$ ou $\exists yq$ a variável $x$ ocorre livre.
• O termo $t$ não é livre para $x$ em $p$ se $t$ tem uma variável que afeta $x$. Isto é, se:
  1. A variável $y$ ocorre em $t$ e
  2. Numa sub-fórmula $\forall yq$ ou $\exists yq$ de $p$ há uma ocorrência livre de $x$.

Critérios Simples para Termos Livres/Não Livres

Estas definições envolvem uma fórmula e duas variáveis e são um pouco confusas.

Sejam $p$ uma fórmula e $x$ uma variável em $p$. Um termo $t$ é livre para $x$ se:

1. Não ocorrem variáveis em $t$ — isto é, se $t$ é fechado.
2. Não existem variáveis comuns entre $t$ e $p$.
3. Nenhuma variável de $t$ está quantificada em $p$.
4. Onde as variáveis de $t$ estão quantificada em $p$, não ocorre $x$.

Um termo $t=\boxed{\cdots y\cdots }$ não é livre para $x$ em $$\begin{array}{rl}& \boxed{\cdots \forall yq\left(x,y\right)\cdots }\\ & \boxed{\cdots \exists yq\left(x,y\right)\cdots }\end{array}$$

Exemplos. Termo livre/não livre

Seja $p$ a fórmula $\boxed{\exists yx<y}$ — $x$ é livre, $y$ ligada e $y$ afeta $x$.

• O termo $3w$ é livre para $x$ porque $3w$ e $p$ não têm variáveis comuns.
• Nenhuma variável do termo $z+x$ está quantificada em $p$. Portanto $z+x$ é livre para $x$ em $p$.
• $y^2$ não é livre para $x$ porque $y$ afeta $x$; $p\left\{x/y^2\right\}$ é a fórmula $\exists y\boxed{y^2}<y$.
• Pela mesma razão, o termo $x+y$ não é livre para $x$ em $p$; Substituindo $\left\{x/x+y\right\}$ em $p$ produz a fórmula $\exists y\boxed{x+y}<y$.

Nota. Com $3w$ e $z+x$ obtêm-se condições em $w$ e $z,x$ mas não com $y^2$ nem com $x+y$.