Lógica de predicados como uma linguagem formal

A nossa discussão até então, envolveu apenas a codificação de sentenças como fórmulas da lógica de predicados. Para isso, foi necessário compreender os uso de variáveis, quantificadores e predicados. Dissemos que essa discussão foi informal pois não foram descritas as regras gramaticais de formação das fórmulas válidas. Assunto desta seção.

O primeiro passo para a formalização da linguagem da lógica de predicados é a identificação/classificação de seus componentes. Essa classificação nos mostra, inicialmente, que há dois tipos de coisas envolvidas em toda fórmula da lógica de predicados. As primeiras são:

Objetos aos quais estamos referenciando:
- Variáveis $x$ e $y$.
- Símbolos funcionais $m(x)$, $g(x,y)$, $a$, $p$

Toda expressão na lógica de predicados que se refere a um objeto é chamada um termo. O segundo tipo de componentes na lógica de predicados denotam valores lógicos

Valores lógicos, fórmulas
- $J(x, m(x))$ ($J$ é um predicado) é uma fórmula, embora $x$ e $m(x)$ sejam termos.

Um vocabulário predicado consiste em dois conjuntos:

Um conjunto de símbolos predicados $P$
Um conjunto de símbolos funcionais $F$ (incluindo constantes: funções $0$-árias)

Termos

Os termos da linguagem são feitos de variáveis, símbolos constantes e funções aplicadas a ambos. De modo geral, as regras de construção dos termos estão definidas a seguir:

Qualquer variável é um termo
Se $c\in F$ é uma função $0$-ária, então $c$ é um termo
Se $t_1,t_2,\dots,t_n$ são termos e $f\in F$ é $n$-ária, com $n> 0$, então $f(t_1,t_2,\dots,t_n)$ é um termo.
Nada mais é um termo.

Exemplo

Suponha os símbolos funcionais $n, f$ e $g$, respectivamente $0$-ário, unário, binário. De acordo com as regra de construção de termos bem formados, temos que :

$n$, $f(x)$, $g(x,f(y))$ são termos
$n(x)$, $f$, $g(x)$ não são termos.

Ou seja, o número de parâmetros deve corresponder à definição da função.

Fórmulas

A escolha dos conjuntos $P$ e $F$ depende do que queremos expressar, portanto, dependem do contexto. Porém, ainda sim podemos definir as fórmulas bem formadas sobre esses conjuntos de forma indutiva.

Se $Q\in P$ é um predicado $n$-ário com $n\geq 1$ e se $t_1, t_2, \dots, t_n$ são termos sobre $F$, então $Q(t_1, t_2, \dots, t_n)$ é uma fórmula
Se $\phi$ é uma fórmula, então $(\neg\phi)$ também é
Se $\phi$ e $\psi$ são fórmulas, então $(\phi\land\psi)$, $(\phi\lor\psi)$ e $(\phi\to\psi)$ também são
Se $\phi$ é uma fórmula e $x$ é uma variável, então $(\forall x\phi)$ e $(\exists x\phi)$ são fórmulas

Em resumo, podemos escrever:

Exemplo

Verifique se a fórmula a seguir é bem formada

$\forall x ((P(x)\to Q(x)) \land S(x,y))$ $\exists x( P(y,z) \land (\forall y (\neg Q(y,x) \lor P(y,z))))$

Prioridades

Na prática, muitas vezes preferimos ignorar alguns parenteses, em troca de melhor visibilidade. Nessas situações a prioridade dos quantificadores/operadores deve ser levada em consideração:

$\neg$, $\forall y$, $\exists y$ tem prioridade mais alta;
depois vem os símbolos $\lor$ e $\land$;
por fim, temos $\to$