Lógica de primeira ordem
First Order Logic (FoL)
Capítulo 8
Fundamentos da IA
Mestrado FEI
Lógica proposicional
 é declarativa
 permite informação disjuntiva e/ou negada
– (ao contrario da maioria das estruturas de dados e base de
dados)
 é composicional:
– o significado de B1,1  P1,2 é derivado do significado de B1,1 e
P1,2
 O significado das sentenças proposicionais é
independente do contexto
– (ao contrário da linguagem natural)
 Possui um poder de expressão limitado
– (ao contrário da linguagem natural)
– E.g., "poços causam brisas em quadrados adjacentes”
• em LP: B1,1 <-> (P1,2 V P21) etc...
– Uma sentença para cada quadrado
FoL: compromisso ontológico
• A lógica proposicional assume mundos
compostos somente por fatos,
• A lógica de primeira ordem (como a
linguagem natural) assume mundos
compostos por
– Objetos: people, houses, numbers, colors,
baseball games, wars, …
– Relações: red, round, prime, brother of,
bigger than, part of, comes between, …
– Funções: father of, best friend, one more
than, plus, …
Sintaxe da FOL
•
•
•
•
•
•
•
Constantes KingJohn, 2, NUS,...
Predicados Brother, >,...
Funções
Sqrt, LeftLegOf,...
Variáveis
x, y, a, b,...
Conectivos , , , , 
Igualdade
=
Quantificadores , 
Símbolos para! Não são a coisa em sí!!
Sintaxe da LPO
Termos
=
função(term1,...,termn)
ou constante ou variável
[referem-se a objetos]
Sentenças atômicas = predicado(term1,...,termn)
ou term1 = term2
[enunciam fatos]
• E.g. sentença atômica,
– Brother(KingJohn,RichardTheLionheart),
– > (Length(LeftLegOf(Richard)), Length(LeftLegOf(KingJohn)))
Sentenças Complexas
• Sentenças complexas são construídas de
sentenças atômicas usando conectivos:
S, S1  S2, S1  S2, S1  S2, S1  S2,
E.g. Sibling(KingJohn,Richard) 
Sibling(Richard,KingJohn)
>(1,2)  <(1,2)
>(1,2)   >(1,2)
Semântica em lógica de
primeira ordem
• A semântica deve relacionar sentenças a modelos a fim de
determinar verdade.
– Para isso precisamos de uma interpretação que especifique quais
objetos, relações e funções são referidos pelos símbolos de constantes,
relações e funções.
• Interpretação é, portanto, um mapeamento entre
símbolos de constantes
símbolos de predicados
símbolos de funções
-->
-->
-->
objetos
relações
funções
• Uma sentença atômica predicate(term1,...,termn) é verdadeira
sse os objetos relativos à term1,...,termn estão contidos na relação
relativa à predicate
Modelos para FOL: Exemplo
Interpretação
• Interpretação: especifica exatamente
quais objetos, relações e funções são
referidos pelos símbolos de constantes,
predicados e funções;
Interpretação
• Interpretação pretendida para o exemplo:
• Ricardo: Ricado coração de leão; Joao: rei João
• Irmão: conjunto de tuplas:
– <Ricardo cor de leao, Rei João>, <Rei João, Ricardo Cor
de leao>
• NaCabeça: relação Na cabeça, que é válida para
coroa e rei Joao;
• Pessoa, Rei, Coroa: conjuntos de objetos
• Perna esquerda: função “perna esquerda”, I.e.:
– <Ricardo cor de leao> -> perna esquerda de Ricardo
– <Rei Joao> -> perna esquerda de Joao
Há várias outras interpretações
possíveis
• E.g. Ricardo -> Coroa, Joao -> perna do rei joao
• 5 objetos no modelos, portanto há 25
interpretações possíveis apenas para os
símbolos Ricardo e Joao
• Confuso?
• Em logica proposicional é possível uma interpretação tal que
ensolarado e nublado sejam verdade
• Cabe a base de conhecimento eliminar modelos
inconsistentes com nosso conhecimento
Semântica em lógica de
primeira ordem
• A verdade de qualquer sentença é determinada
por um modelo e uma interpretação para os
símbolos das sentenças. Então, consequência
lógica, validade, etc são definidas em termos de
todos os modelos possíveis e todas as
interpretações possíveis.
• O n. de elementos pode ser ilimitado
• N. de modelos ilimitado
– Verificação lógica pela enumeração de modelos não
é uma opção.
Sintaxe:
Quantificação Universal ()
• <variáveis> <sentenças>
“Todos os reis são pessoas”:
x Rei(x)  Pessoa(x)
• x P é verdade em um modelo m sse P é verdadeira em
todas as interpretações estendidas.
– Cada interpretação estendida especifica um elemento de
domínio ao qual x se refere
Semântica:
Quantificação Universal ()
• i.e. a quantificação é equivalente à conjunção de
instanciações de P
Rei(KingJohn)  Pessoa(KingJohn)
 Rei(Richard)  Pessoa(Richard)
 Rei(Perna_esq._de_richard)  Pessoa(Perna_esq._de_richard)
 Rei(Coroa)  Pessoa(Coroa) ...
{
São verdadeiras no modelo mas não trazem
nenhuma informação, pois nenhuma das
premissas são verdadeiras!
Equívoco comum
• Tipicamente,  é o principal conectivo para ser
usado com 
• Equívoco comum: usar  como o principal
conectivo com :
x Rei(x)  Pessoa(x)
i.e. “Todos são reis e todos são pessoas”
Sintaxe:
Quantificação existencial
• <variáveis> <sentenças>
– declaração sobre algum objeto sem nomeá-lo
• “Existe uma coroa na cabeça do rei John”:
• x Coroa(x)  NaCabeça(x, John)
Semântica:
Quantificação existencial
• x P é verdade em um modelo m sse P é verdade sendo
x algum objeto possível no modelo;
• Informalmente, é equivalente à disjunção de
instanciações de P
Coroa(John)  NaCabeça(John, John)
 Coroa(Richard)  NaCabeça(Richar, John)
 Coroa(Crown)  NaCabeça(Crown, John)
 ...
Outro equívoco comum...
• Tipicamente,  é o principal conectivo para 
• Equívoco: usar  como o principal conectivo
com :
x Coroa(x)  NaCabeça(x, João)
é verdadeira se x não for coroa (como x diz
que existe pelo menos um, a sentença ser
verdadeira para um outro objeto que não seja
coroa torna esta sentença completamente
irrelevante!)
Propriedades dos
quantificadores
• x y é o mesmo que y x
• x y é o mesmo que y x
• x y não é o mesmo que y x
• x y Loves(x,y)
– “há uma pessoa que ama todas as outras no mundo”
• y x Loves(x,y)
– “todo mundo é amado por alguem”
• Dualidade de quantificadores: são complementares:
• x Likes(x,IceCream)
x Likes(x,IceCream)
•
• x Likes(x,Broccoli)
x Likes(x,Broccoli)
•
Igualdade
• term1 = term2 é verdade em uma interpretação
se e somente se term1 e term2 referem ao
mesmo objeto.
• E.g., definição de Irmão em termos de Genitor:
x,y Irmão(x,y)  [(x = y)  m,f  (m = f) 
Genitor(m,x)  Genitor(f,x)  Genitor(m,y) 
Genitor(f,y)]
Usando FOL
Domínio de parentesco:
• mãe é um ancestral feminino de alguém
m,c Mãe(c) = m  (Feminino(m)  Ancestral(m,c))
– Esta regra não restringe os modelos corretamente,
por que? (este é um erro comum em engenharia de
conhecimento)
• “irmão” é simétrico
x,y irmão(x,y)  irmão(y,x)
• “um avô é genitor de alguém que é pai”
x,y Avô(x,y)   p Pai(p,x)  Genitor(p,y)
– Onde está o erro?
Usando FOL
Domínio de parentesco:
x,y Avô(x,y)   p Pai(p,x)  Genitor(p,y)
Outro erro comum: a ordem do
argumento é inconsistente com o
conceito a ser definido.
Axiomas e teoremas
• Cada sentença anterior é um axioma do
domínio de parentesco;
– utiliza-se um conjunto básico de predicados
segundo os quais outros podem ser definidos
a partir de axiomas.
• Um conjunto de axiomas é uma teoria
lógica
• Fórmulas que são consequência lógica de
um conjunto de axiomas são teoremas
desta teoria;
Usando FOL
Teoria de conjuntos:
• s Set(s)  (s = {} )  (x,s2 Set(s2)  s = {x|s2})
• x,s {x|s} = {}
• x,s x  s  s = {x|s}
• x,s x  s  [ y,s2} (s = {y|s2}  (x = y  x  s2))]
• s1,s2 s1  s2  (x x  s1  x  s2)
• s1,s2 (s1 = s2)  (s1  s2  s2  s1)
• x,s1,s2 x  (s1  s2)  (x  s1  x  s2)
• x,s1,s2 x  (s1  s2)  (x  s1  x  s2)
FOL para Base de
Conhecimento
•
Suponha que um agente no mundo de wumpus, usando uma BC em FOL,
detecta um fedor e uma brisa (mas não brilho) em t=5:
Tell(BC,Percept([Smell,Breeze,None],5))
Ask(BC,a BestAction(a,5))
•
I.e., A BC deduz a melhor ação em t=5?
•
Resposta: Yes, {a/Shoot}
•
•
Dada uma sentença S e uma substituição ,
S denota o resultado da substituição de  em S; e.g.,
substituição (lista de atribuição)
S = Smarter(x,y)
 = {x/Hillary,y/Bill}
 S = Smarter(Hillary,Bill)
• Ask(BC,S) retorna algum/todo  tal que KB |= 
Engenharia de conhecimento
em FOL
1. Identificar uma tarefa;
2. Agregar conhecimento relevante;
3. Definir um vocabulário de predicados, funções,
e constantes (ontologia);
4. Codificar o conhecimento geral sobre o
domínio;
5. Codificar uma descrição da instância
específica do problema;
6. Formular consultas ao procedimento de
inferência e obter respostas;
7. Depurar a base de conhecimento.
Exemplo: domínio de circuitos
eletrônicos
Somador completo de um bit.
Domínio de circuitos eletrônicos
1. Identificar a tarefa
– O circuito adiciona de maneira correta? (verificação
do circuito)
•
Agregar conhecimento relevante;
– Composto de cabos e portas; Tipos de portas (AND,
OR, XOR, NOT)
– Irrelevante: tamanho, forma, cor, ...
•
Decidir um vocabulário
– Alternativas:
Type(X1) = XOR
Type(X1, XOR)
XOR(X1)
Domínio de circuitos eletrônicos
4. Codificar o conhecimento geral sobre o
domínio
–
–
–
–
–
–
–
–
t1,t2 Connected(t1, t2)  Signal(t1) = Signal(t2)
t Signal(t) = 1  Signal(t) = 0
1≠0
t1,t2 Connected(t1, t2)  Connected(t2, t1)
g Type(g) = OR  Signal(Out(1,g)) = 1  n
Signal(In(n,g)) = 1
g Type(g) = AND  Signal(Out(1,g)) = 0  n
Signal(In(n,g)) = 0
g Type(g) = XOR  Signal(Out(1,g)) = 1 
Signal(In(1,g)) ≠ Signal(In(2,g))
g Type(g) = NOT  Signal(Out(1,g)) ≠
Signal(In(1,g))
Domínio de circuitos eletrônicos
5. Codificar uma descrição da instância específica
do problema
Type(X1) = XOR
Type(A1) = AND
Type(O1) = OR
Type(X2) = XOR
Type(A2) = AND
Connected(Out(1,X1),In(1,X2))
Connected(Out(1,X1),In(2,A2))
Connected(Out(1,A2),In(1,O1))
Connected(Out(1,A1),In(2,O1))
Connected(Out(1,X2),Out(1,C1))
Connected(Out(1,O1),Out(2,C1))
Connected(In(1,C1),In(1,X1))
Connected(In(1,C1),In(1,A1))
Connected(In(2,C1),In(2,X1))
Connected(In(2,C1),In(2,A1))
Connected(In(3,C1),In(2,X2))
Connected(In(3,C1),In(1,A2))
Domínio de circuitos eletrônicos
6. Formular consultas ao procedimento de
inferência e obter respostas;
– Que combinações de entradas fariam a
primeira saida de C1 (o bit de soma) ser 0 e a
sengunda saida de C1 (o bit e transporte) ser
1?
i1,i2,i3,o1,o2 Signal(In(1,C1)) = i1  Signal(In(2,C1)) = i2 
Signal(In(3,C1)) = i3  Signal(Out(1,C1)) = 0 
Signal(Out(2,C1)) = 1
Resposta: conjunto de substituições para i1, i2 e i3 (ex. {i1/1,
i2/1, i3/0})
• Depurar a base de conhecimento
Pode ter havido algumas omissões como
10
Testar perguntas com respostas já
conhecidas.