Lógica de
Predicados
Sintaxe
O que não é possível
expressar em Lógica Prop.



Todo tricolor é um campeão. Roberto é
tricolor. Logo Roberto é um campeão.
A adição de dois números ímpares
quaisquer é um número par.
Por quê?
Ausências da Lógica
Proposiconal

Quantificadores



todo, qualquer, existe, alguns, nenhum, ...
Sempre estão ligados a variáveis
Objetos


Indivíduos do universo de discurso, sobre o qual
quantificadores podem ser aplicados
Todo tricolor é um campeão. Roberto é tricolor.
Roteiro desta parte do curso



Sintaxe
Semântica
Métodos de prova



Tableaux semânticos
Resolução
Programação em lógica
Lógica de Predicados

Também chamada de



Lógica de 1ª. Ordem
FOL (First-Order Logic)
Extensão da Lógica Proposicional


Novos conectivos (quantificadores)
Novos símbolos para funções, variáveis,
predicados, etc
Alfabeto da Lógica de
Predicados






Símbolos de pontuação: (,)
Símbolos de verdade: false, true
Conjunto enumerável de símbolos para
variáveis: x, y, z, w, x1, y1, x2, z2...
Conjunto enumerável de símbolos para
funções: f, g, h, f1, g1, f2, g2...
Conjunto enumerável de símbolos para
predicados: p, q, r, s, p1, q1, p2, q2...
Conectivos proposicionais: ,v, , 
Aridade

Associado a cada símbolo de função ou
predicado, temos uma aridade



número inteiro, não-negativo k
Indica o número de argumentos da função
ou predicado
Constantes e símbolos proposicionais



Sempre têm k=0
Funções -> constantes
Predicados -> símbolos proposicionais
Notação

Constantes (ou funções zero-árias)


Símbolos (ou predicados zero-ários)


P, Q, R, S, P1, Q1, P2, Q2...
Quantificadores



a, b, c, a1, b1, a2, b2, ...
Universal:  (para todo …)
Existencial:  (existe …)
Os conectivos ,  e ^ são definidos
em função do conjunto completo {,v}
Tipos de perguntas (consultas)

“A capital de Togo é Lome?”



Deve retornar um símbolo de verdade
Sentenças que representam símbolos de
verdade, em Lógica de Predicados, são
chamados de átomos
“Qual a capital da Estônia?”


Deve retornar um objeto
Sentenças que representam objetos são
chamados de termos
Termos

São construídos a partir destas regras:


Variáveis são termos (representam objetos)
Se t1, t2, ..., tn são termos


f é um símbolo de função n-ária,
então f(t1, t2, ..., tn) também é um termo
Exemplos de termos




x, a (constante, função zero-ária)
f(x,a) se e somente se f é binária
g(y, f(x,a), c) se e somente se g é
ternária
+(9,10), -(9,5)



interpretados como 10+9, 9-5
Notação polonesa
h(x,y,z), considerada implicitamente
como ternária
Átomos

São construídos a partir destas regras:


O símbolo de verdade false é um átomo
Se t1, t2, ..., tn são termos


p é um símbolo de predicado n-ária,
então p(t1, t2, ..., tn) é um átomo
Exemplos de átomos

P (símbolo proposicional)




Predicado zero-ário)
p(f(x,a),x) se e somente se p é binário
q(x,y,z) considerado implicitamente como
ternário
Ex: >(9,10), =(9,+(5,4))



interpretados como 10>9, 9=5+4
Interpretados como T
Note os abusos de linguagem


> e = são predicados
+ e – são funções
Fórmulas

São construídos a partir destas regras:




Todo átomo é uma fórmula da Lógica de
Predicados
Se H é fórmula então (H) também é
Se H e G são fórmulas, então (HvG)
também é
Se H é fórmula e x variável, então

((x)H) e ((x)H) são fórmulas
Construção de fórmulas



Átomos p(x), R e false
((p(x)) v R)
Que equivale a (p(x)  R)

também fórmula

((x) p(x)  R)

Expressão = termo v fórmula
Sub-termo



Se E=x, então a variável x é sub-termo de
E
Se E = f(t1,t2,...,tn) então ti e f(t1,t2,...,tn)
são sub-termos de E
Se t1 é sub-termo de t2 e t2 de E, então t1
também é sub-termo de E
Subfórmula

Se H é fórmula





H é uma sub-fórmula
Se H=(G), então G é sub-fórmula de H
Se H é do tipo (EvG), (E^G), (EG) ou
(EG), então E e G são sub-fórmulas de H
Se x é uma variável e Q um quantificador,
H=((Qx)G) então G e ((Qx)G) são subfórmulas de H
Se G é sub-fórmula de H, então toda subfórmula de G também é sub-fórmula de H
Próprios e sub-expressões



Se t é sub-termo de E, e t é diferente
de E, então t é sub-termo próprio de E
Se G é sub-fórmula de H e G e H são
diferentes, então G é sub-fórmula
própria de H
Todo sub-termo ou sub-fórmula é uma
sub-expressão
Literais e formas normais



Literal em lógica de predicados é um
átomo ou sua negação
Uma fórmula está na forma normal
disjuntiva (fnd ou DNF, em inglês) se é
uma disjunção de conjunções de literais
Uma fórmula está na forma normal
conjuntiva (fnc ou CNF, em inglês) se é
uma conjunção de disjunções de literais
Ordem de precedência da
Lógica de Predicados







, 
, 
^,v
G=(x)(y)p(x,y)(z)q(z)^r(y)
representa
H=((((x)((y)p(x,y)))(z)(q(z))^
r(y))
Correspondência entre
quantificadores



((x)H)= ((z)(H))
((x)H)= ((z)(H))
Qualquer quantificador pode ser
definido a partir do outro!
Escopo de um quantificador


Abrangência de seu uso nas subfórmulas
Se E é uma fórmula na Lógica de
Predicados

Se ((x)H) é subfórmula de E


o escopo de (x) é H
Se ((x)H) é subfórmula de E

o escopo de (x) é H
Exemplo de escopo de
quantificadores





G=(x)(y)((z)p(x,y,w,z)
(y)q(z,y,x,z1))
O escopo de (x) é
(y)((z)p(x,y,w,z) (y)q(z,y,x,z1))
O escopo de (y) é
((z)p(x,y,w,z) (y)q(z,y,x,z1))
O escopo de (z) é p(x,y,w,z)
O escopo de (y) é q(z,y,x,z1))
Ocorrência livre e ligada

Se x é uma variável e E uma fórmula,
uma ocorrência de x em E é



Ligada, se x está no escopo de um
quantificador (x) ou (x) em E
Livre, se não for ligada
G=(x)(y)((z)p(x,y,w,z)
(y)q(z,y,x,z1))
Variável livre e ligada

Se x é uma variável e E uma fórmula
que contém x. x é



Ligada em E, se existir uma ou mais
ocorrências ligadas de x em E
Livre em E, se existir uma ou mais
ocorrências livres de x em E
No exemplo anterior, z é livre e ligada!
Símbolos livres

Símbolos livres de uma fórmula são
suas variáveis livres, símbolos de função
e de predicado


Tudo menos os conectivos, variáveis dos
quantificadores, símbolos de verdade e de
pontuação
Ex: O conjunto {w,z,z1,p,q} no exemplo
anterior
Fórmulas fechadas



Fórmulas ditas fechadas não possuem
variáveis livres
O exemplo anterior não é, mas,
adicionando (w), (z) e (z1)...
G1=(w)(z)(z1)(x)(y)
((x)p(x,y,w,z)(y)q(z,y,x,z1)) é
fechada
Fecho de uma fórmula



Se H é fórmula da Lógica de Predicados e
{x1, x2, ..., xn} é o conjunto das
variáveis livres em H
O fecho universal de H, (*)H, é
(x1)(x2)...(xn)


G1 é o fecho universal de G
O fecho existencial de H, (*)H, é
(x1)(x2)...(xn)
Fechos e fórmulas fechadas



G1=(w)(z)(z1)(x)(y)
((x)p(x,y,w,z)(y)q(z,y,x,z1))
Se H é fechada, como não possui
variáveis livres, seus fechos universal e
existencial são iguais a H
H=(*)H=(*)H