Sintaxe da Lógica de Primeira Ordem

A sintaxe da Lógica de Primeira Ordem mantém os conectivos da Lógica Proposicional e adiciona termos para designar objetos e fórmulas para representar relações entre esses objetos.

$$p(a)\forall xp(x)\exists yg(x)=h(x,a)$$

A sintaxe e as regras da Dedução Natural Proposicional continuam válidas.

• São acrescentados termos: constantes, funções e variáveis.
• As fórmulas acrescentam relações e quantificadores às proposições.

Por enquanto definem-se todos estes conceitos novos. Mais tarde são tratadas as regras de dedução e da semântica para a Lógica de Primeira Ordem.

Termos e Fórmulas

$$\begin{array}{c}2,\text{Lua},\text{Loˊgica e Computac¸a˜o},\text{Aragorn},\text{Ariadne}\\ 2>3,\text{Primo}\left(21\right),\text{Sateˊlite}\left(\text{Lua},\text{Terra}\right),\text{Humano}\left(\text{Legolas}\right)\\ \forall x\text{Ana˜o}\left(x\right)\to \exists y\text{Elfo}\left(y\right)\wedge \text{Amigo}\left(x,y\right)\\ \forall p\text{Brisa}\left(p\right)\to \exists y\text{Adjacente}\left(p,y\right)\wedge \text{Poc¸o}\left(y\right)\end{array}$$

• Os termos são definidos por constantes, funções e por variáveis; Identificam objetos.
• As fórmulas são definidas por relações, conectivos e expressões com quantificadores. Tal como as proposições da Lógica Proposicional, descrevem factos.

Termos

Definição (Termo)

Sejam $\mathcal{V},\mathcal{C},\mathcal{F}$ conjuntos de símbolos (para as variáveis, as constantes e as funções, respetivamente). São termos:

• Átomos. Qualquer constante de $\mathcal{C}$ e qualquer variável de $\mathcal{V}$.
• Funções. Se $f_n\in \mathcal{F}$ e $t_1,\dots ,t_n$ forem termos então $f\left(t_1,\dots ,t_n\right)$ é um termo.

Um termo em que não ocorrem variáveis diz-se fechado. Caso contrário diz-se aberto.

Em geral, a aridade faz parte da especificação de cada símbolo funcional $f\in \mathcal{F}$ (e a seguir de cada $r\in \mathcal{R}$). Quando necessário indica-se a aridade com um indice — $f_2$ é binária, $g_7$ é $7$-ária, etc.

Exemplos. Termos

• Átomos: $2$, $\text{Lua}$, $\text{Aragorn}$, $\text{Ariadne}$, $x$.
• Funções: $1+1$, $\text{Sateˊlite}\left(\text{Terra}\right)$, $\sin \left(\frac{\pi }{2}\right)+e^{i\pi }$, $a+x$, $f\left(\right)$.

Não são termos:

• $1+\frac{1}{2}+\frac{1}{4}+\cdots$ é uma expressão infinita.
• $\text{Par}\left(2\right)$ é uma proposição (verdade/falso).
• $x>y$ é uma proposição.
• $\sin$ é um símbolo funcional mas a expressão não está completa.

Fórmulas

Definição (Fórmula)

Sejam $\mathcal{V},\mathcal{C},\mathcal{F}$ como na definição de termos e $\mathcal{R}$ um conjunto de símbolos de relações. São fórmulas:

• Igualdade. Se $a,b$ forem termos, $a=b$ é uma fórmula.
• Conectivos. Se $p,q$ forem fórmulas, $\neg p,p\wedge q,p\vee q,p\to q$ são fórmulas.
• Relações. Se $t_1,\dots ,t_n$ forem termos e $r_n\in \mathcal{R}$ então $r\left(t_1,\dots ,t_n\right)$ é uma fórmula.
• Quantificadores. Se $x$ for uma variável e $p$ uma fórmula, $\forall xp$ e $\exists xp$ são fórmulas.

Exemplos. Fórmulas

• Igualdade. $2=2$, $2=1$, $\text{Lua}=\text{Sateˊlite}\left(\text{Terra}\right)$.
• Conectivos. $\text{Lua}=\text{Sateˊlite}\left(\text{Terra}\right)\wedge \text{Massa}\left(\text{Lua}\right)<\text{Massa}\left(\text{Terra}\right)$.
• Relações. $\text{Par}\left(2\right)\vee x>3$.
• Quantificadores. $\left(\forall x\text{Par}\left(x\right)\right)\to 2<1$.

Não são fórmulas:

• $2$, $\text{Lua}$, $x$, $0+1+2+y$ porque são termos.
• $=$, $<$, $\text{Par}$ são símbolos relacionais mas as expressões estão incompletas.
• $\text{Par}\left(2\right)>4$ é um erro de sintaxe. Se quisermos dizer "Dois é um número par maior que quarto" devemos escrever $\text{Par}\left(2\right)\wedge 2>4$.
• $\text{Par}\left(0\right)\wedge \text{Par}\left(2\right)\wedge \text{Par}\left(4\right)\wedge \cdots$ é uma expressão infinita.

Sobre a Igualdade

• Um uso da igualdade é nas formação de fórmulas, por exemplo, $2+2=4$.
• Outro uso é quando comparamos as expressões "$2+2$" e "$4$" que são, obviamente, diferentes.
• Quando for necessário distinguir o primeiro caso do segundo, usa-se a notação $==$ (dois "$=$") para indicar a igualdade de expressões.

Escrita natural e Escrita formal

A escrita natural de termos e fórmulas comuns é diferente, mas equivalente, à sua escrita formal.

Nesta tabela estão várias expressões apresentadas na escrita natural usadas no dia-a-dia e a respetiva notação formal que segue as definições de termo e de fórmula.

$$\begin{array}{lllr}\text{Escrita }\text{natural}& \text{Escrita }\text{formal}& \text{Tipo}& \text{Resultado}\\ 2+3& \text{Soma}\left(2,3\right)& \text{func¸a˜o}& \text{termo}\\ n<3& \text{Menor}\left(n,3\right)& \text{relac¸a˜o}& \text{foˊrmula}\\ e^x& \text{Exp}\left(x\right)& \text{func¸a˜o}& \text{termo}\\ \sin \left(z\right)& \text{Sin}\left(z\right)& \text{func¸a˜o}& \text{termo}\\ 4=5\frac{4}{5}& 4=\text{Mult}\left(5,\text{Div}\left(4,5\right)\right)& \text{relac¸a˜o}& \text{foˊrmula}\\ \pi \ne 3& \neg \left(\pi =3\right)& \text{relac¸a˜o}& \text{foˊrmula}\\ 2+3\times 4& \text{Soma}\left(2,\text{Mult}\left(3,4\right)\right)& \text{func¸a˜o}& \text{termo}\\ \left(2+3\right)\times 4& \text{Mult}\left(\text{Soma}\left(2,3\right),4\right)& \text{func¸a˜o}& \text{termo}\\ 2+3\vee 4+1& & & \end{array}$$