Logica de Predicados

Fórmulas, Interpretações, Validade e Regras de Dedução Fórmulas da Lógica de Predicados

Como já visto para lógica proposicional, antes de definir a linguagem precisamos de um alfabeto (i.e., conjunto de símbolos). Utilizaremos os seguintes conjuntos de símbolos:

• Variáveis individuais: u, v, x, y, z
• Constantes individuais: a, b, c, d, e
• Símbolos de funções: f, g, h
• Letras predicativas: P, Q, R, S, T
• Símbolos conetivos: ¬, →, ∧, ∨, ↔
• Símbolos de quantificação: ∀, ∃
• Símbolos de pontuação: (, )

O número de argumentos para um predicado ou função normalmente verificaremos no contexto.
Um predicado sem nenhum argumento é considerado uma proposição.
Um termo é uma variável, uma constante;
Uma fórmula atômica é um predicado aplicado à argumentos que são termos.

Por exemplo, p(x,a). Se P é um símbolo predicativo de aridade n e t1,t2,...,tn são termos, então P(t1,t2,...,tn) é uma fórmula atômica.
Podemos definir as fbf (well-formed formulas) da lógica de predicados como segue:

• Toda fórmula atômica é uma fbf
• Se W é uma fórmula, então ¬W também é uma fórmula
• Se W e V são e x é uma variável, então as seguintes expressões são fbfs: ¬W,(W ∧V),(W ∨V),(W→V),(W↔V),∃xWe∀xW
• Nada mais é fórmula...

Quando um quantificador ocorre em uma fbf, ele influência a ocorrência de alguma variável quantificada. A extensão dessa influência é chamada escopo do quantificador, que definimos como segue:
• Na fbf ∃x W , W é o escopo do quantificador ∃x.
• Na fbf ∀x W , W é o escopo do quantificador ∀x.

Por exemplo, observe o escopo de ∃x na fbf ∃x p(x, y) → q(x). O escopo é p(x, y). pois esta fórmula é o mesmo que (∃x p(x, y) → q(x)). Por outro lado, o escopo de ∃x na fórmula ∃x (p(x, y) → q(x)) é p(x, y) → q(x).

Uma ocorrência da variável x na fbf é dita ligada se ela esta no escopo de ∃x ou ∀x, ou se ela é a própria variável quantificada. Caso contrário, uma ocorrência de x é dita livre na fbf. Por exemplo, considere a fbf