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 x\ 2 < x$ é simples de entender. Assim como $y$ em $\exists y\ 2 < y$. Mas em casos mais complexos, como $\exists x\ z < 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 x\ p$ ou $\exists x\ p$ 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 “$\fvar{a}$” e as ligadas desta “$\bvar{b}$”.

$$ \begin{array}{l} \fvar{x} + 3 > \fvar{y} \cr \exists \bvar{x}\ \bvar{x} > 2 \cr \fvar{x} = \fvar{y} \cr \exists \bvar{x}\ \bvar{x} = \fvar{y} \cr \forall \bvar{x}\ \exists \bvar{y}\ \bvar{x} = \bvar{y} \cr {\fvar{y} / 2} = e^{-1} \lor \exists \bvar{y} \ \forall \bvar{x}\ \bvar{x} > \bvar{y} \cr \del{\forall \bvar{x}\ \bvar{x} = \fvar{y}}\to \fvar{x} < \pi \cr \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 x\ x>2 \equiv \forall y\ y>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

$$\Large p\at{x} $$

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\ \del{2y = x}$ 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\at{x}.$$

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

A escrita “$p\at{x}$” indica que $x$ está condicionada por $p$ ou seja, $p$ é parametrizada por $x$.
Quando $x$ não ocorre livre em $p$ então $p\at{x}$ 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\at{x}: \exists y\ x > y$.
$p\at{x,y}: \neg\del{x = y}$.
$p\at{x}: \neg\del{x = y}$.
$p\at{x,y}: \del{\exists \bvar{x}\ y > \bvar{x}} \land \del{\exists \bvar{y}\ \bvar{y} > x} \land \del{\exists \bvar{z}\ y > \bvar{z} > x}$.
$p\at{x,y}: \del{\exists \bvar{u}\ y > \bvar{u}} \land \del{\exists \bvar{v}\ \bvar{v} > x} \land \del{\exists \bvar{w}\ y > \bvar{w} > x}$.

Substituição

$$ \Large p\subst{x}{t} $$

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\subst{x}{t}$, é 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\subst{x}{t} == p$. Isto é, a substituição “não teve efeito”. Aqui é usada a “igualdade de expressões”, $==$, para mostrar que $p$ e $p\subst{x}{t}$ são sintaticamente a mesma fórmula; os mesmos símbolos, a mesma estrutura, nas mesmas posições.

Exemplos. Substituição

$p: \exists y\ x > y$:
- $p\subst{x}{z}$ é $\exists y\ z > y$.
- $p\subst{y}{w}$ é $\exists y\ x > y$ — porque $y$ não é livre.
$p: \neg\del{x = y}$:
- $p\subst{x}{y}$ é $\neg\del{y = y}$ — Cuidado!
- $p\subst{y}{w}$ é $\neg\del{x = w}$.
$p: \del{\exists \bvar{x}\ y > \bvar{x}} \lor \del{\forall \bvar{y}\ \bvar{y} > x} \to \del{\exists \bvar{z}\ y > \bvar{z} > x}$:
- $p\subst{y}{v}$ é $\del{\exists x\ v > x} \lor \del{\forall y\ y > x} \to \del{\exists z\ v > z > x}$.
- $p\subst{y}{v}\subst{x}{u}$ é $\del{\exists x\ v > x} \lor \del{\forall y\ y > u} \to \del{\exists z\ v > z > u}$.

Efeitos Indesejados das Substituições

Na aritmética, a fórmula $\exists y\ x < 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 y\ x < y$ pode-se substituir a variável $x$ por outro termo qualquer. E em geral, é verdade.

Substituindo $\subst{x}{25041973}$ obtém-se $\exists y\ 25041973 < y$ que é verdade: basta escolher $y = 25041974$.

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

Substituirmos $\subst{x}{y}$ obtém-se $\exists y\ y < 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 y\ q$ ou $\exists y\ q$.
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 y\ q$ ou $\exists y\ q$ 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 y\ q$ ou $\exists y\ q$ 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:

Não ocorrem variáveis em $t$ — isto é, se $t$ é fechado.
Não existem variáveis comuns entre $t$ e $p$.
Nenhuma variável de $t$ está quantificada em $p$.
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{aligned} &\boxed{\cdots \alert{\forall y}\ q\at{x,y} \ \cdots}\cr &\boxed{\cdots \alert{\exists y}\ q\at{x,y} \ \cdots} \end{aligned} $$

Exemplos. Termo livre/não livre

Seja $p$ a fórmula $\boxed{\exists y\ \alert{x} < 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\subst{x}{y^2}$ é 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 $\subst{x}{x+y}$ 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$.