Introdução a
Programação em Lógica e Prolog
Jacques Robin
CIn-UFPE
O que é a Programação em Lógica?

Para a IA: um paradigma de representação do conhecimento e

Para a engenharia de software: um paradigma de especificação de


raciocínio automático
software e de programação
Para os bancos de dados: um modelo conceitual de dados
Para a teoria da computação: um conjunto de lógicas
c:Lógica
L1
Clássica dos
Predicados

L1ch:Lógica
Clássica de
Horn da
1a ordem
L1nh:Lógica
não-monótona
de Horn da
1a ordem
Lógica da
Programação
em Lógica
Visão unificadora trans-disciplinar de várias área da computação
Metáfora da programação em lógica

Teoria lógica = Base de Conhecimento (BC)
• Axiomas e regras da teoria lógica = BC estática
• Teoremas da teoria lógica = BC dinâmica

deduzidos a partir dos axiomas e das regras
• Máquina de inferência = provador de teorema

Teoria lógica = modelo de software = implementação de software
•
•
•
•
•

Programar = apenas declarar axiomas e regras
Execução do programa = construção de prova de teorema
Compilador/interpretador = provador de teorema
Estrutura de controle (única) = mecanismo de dedução automática
Disparar execução do programa = perguntar verdade de um teorema
Teoria lógica = Banco de Dados (BD)
• Definir dados = declarar axiomas e regras
• Consultar BD = perguntar verdade de um teorema
Aplicações da programação em lógica

Inteligência Artificial
• Representação do
conhecimento
• Sistemas especialistas
• Planejamento
• Aprendizagem de máquina
• Processamento de linguagem
natural
• Sistemas multi-agentes
• Robótica
• Matemática computacional
simbólica

Sistemas Distribuídos e
Internet
• Comércio eletrónico
• Recuperação, filtragem e
extração de informação

Engenharia de Software
• Prototipagem rápida de
software complexos
• Especificações formais
executáveis
• Programação por resolução de
restrições
• Programação multi-paradigma
de alto-nível

Banco de Dados
• BD dedutivos e DOO
• Mineração de Dados e
Descoberta de Conhecimento
• Integração de Dados e
Interoperabilidade
O que é Prolog?
Primeira e mais divulgada linguagem do paradigma da
Programação em Lógica (PL)
 Operacionalização simples, prática e eficiente da
metáfora da PL, embora teoricamente impura
 Padrão ISO
 Maioria das outras linguagens de PL são extensões de
Prolog
 Surgiu na década de 70
 Na moda na década de 80 (o Java da época )
 Hoje permanece pouco divulgado e usado na indústria

Representação do conhecimento
Procedimentos
Programação Imperativa
Lógica
Provadores de Teoremas
Regras
Shells de Sistemas Especialistas
Classes/Objetos
Redes Semânticas
Classes/Objetos + Procedimentos
Programação OO Frames
Classes/Objetos + Lógica
Lógicas descritivas
Regras + Procedimentos
Sistemas de Produção
Regras + Classes/Objetos + Procedimentos
Sistemas de Produção OO
Regras + Lógica
Programação em lógica
Regras + Classes/Objetos + Lógica
Programação em lógica OO
Lógica dos predicados como formalismo de
representação do conhecimento

Vantagens:
• Muito versátil e expressivo
• Com semântica declarativa bem definida
• Com grande número de mecanismos de inferência dedutivos com
propriedades formais e custos computacionais muito bem conhecidos

Porque então L1C não vingou como FRC padrão?
• De fato vingou a nível teórico, já que cada novo FRC proposto acaba ser
re-estudado em termos lógicos
• Desvantagens práticos:



Não é intuitiva para especialistas do domínio de aplicação do sistema
inteligente (médico, advogado, lingüista, engenheiro, etc.)
Oferece variedade de modelagens excessiva (muita fórmulas sintaticamente
diferentes porém semanticamente equivalentes)
Prova de teoremas em L1C é computacionalmente inviável para grandes bases
de conhecimento
West é criminoso? em lógica dos predicados:
variantes sintáticas
( P,W,N american(P) 
weapon(W)  nation(N) 
hostile(N)  sells(P,N,W)
 criminal(P))
 ( W owns(nono,W)  missile(W))
 ( W owns(nono,W)  missile(W)
 sells(west,nono,W))
 american(west)
 nation(nono)
 enemy(nono,america)
 ( W missile(W)  weapon(W))
 ( N enemy(N,america)
 hostile(N))
 nation(america)
( ( P,W,N criminal(P)  american(P) 
weapon(W)  nation(N)  hostile(N))
 ( W owns(nono,W)  missile(W1))
 ( W sells(west,nono,W) 
owns(nono,W)  missile(W))
 ( P american(P)  P = west)
 ( N nation(N)  N = nono)
 ( W weapon(W))  missile(W))
 ( N1,N2 N1=nono  N2=america 
emeny(N1,N2))
 ( N  hostile(N) 
enemy(N,america))
 ( N nation(N)  N = america))
Regras de shell de sistemas especialistas

IF premissa THEN conclusão
• Premissas e conclusão em linguagem pseudo-natural com
conectivas genécias IF_THEN, AND, OR, ISA, HAS e outras
dependente do domínio ligando nomes de entidades (classes) e
propriedades (atributos) do domínio

Vantagens:
• Intuitivas para especialista do domínio de aplicação
• Variedade mais restrita de modelagens

Desvantagens:
• Atalha nível da formalização no processo de engenharia de
conhecimento
• Semântica declarativa ambígua
• Mecanismo de dedução ad-hoc com propriedades e formais e
custos computacionais mal conhecidos
West é criminoso?
Lógica x Regras “intuitivas” de shell
Em lógica dos predicados:
( P,W,N american(P) 
weapon(W)  nation(N) 
hostile(N)  sells(P,N,W)
 criminal(P))
 ( W owns(nono,W) 
missile(W))
 ( W owns(nono,W) 
missile(W)
 sells(west,nono,W))
 american(west)
 nation(nono)
 enemy(nono,america)
( X missile(W) 
weapon(W))
 ( X enemy(N,america)
 hostile(N))
 nation(america)


Com shell de sistema especialista:
Base de regras:
IF P ISA american AND W ISA weapon AND
N ISA nation AND N IS hostile AND
P sells W TO N
THEN P IS criminal
IF W ISA missile AND nono HAS W
THEN west sells W TO nono
IF W ISA missile THEN W ISA weapon
IF america HAS enemy N THEN N IS hostile
Base de fatos iniciais:
west ISA american
nono ISA nation
america ISA nation
america HAS enemy nono
nono HAS m1
m1 ISA missile
Engenharia de uma base de conhecimento
• Entrevistas
estruturadas
com especialista
• Preparação de dados
• Ontologias
• Linguagens
semi-formais
de representação
do conhecimento
Elicitação do conhecimento
Nível do conhecimento:
• Nos termos do especialista do domínio de aplicação
• Linguagem natural, Notações gráficas ad-hoc
Formalização do conhecimento
Nível formal:
Nível semi-formal:
• Notação textual estruturada padrão (ex, XML)
• Notação gráfica padrão (ex, UML)
• Validação com especialista
• Compiladores
• Máquinas de
inferências
• Aprendizagem
de Máquina
formais
de representação
do conhecimento
• Aprendizagem
de Máquina
• Notação sem ambigüidade com
semântica definida matematicamente
(ex, lógica, probabilidades)
• Verificação de consistência
Implementação do conhecimento
Nível da implementação:
• Linguagens
• Codificação em uma linguagem de programação
• Teste de protótipo
Problema com regras não baseadas na lógica
Mundo
Representação
fatos
sentenças
segue-se ??
deriva
fatos
sentenças
Formas normais da lógica dos predicados

Forma normal conjuntiva:
• Conjunção de cláusulas disjuntiva, i.e., de disjunção de formulas atômicas
positivas ou negadas
• (P11  ...  Pi1  C11  ...  Ci1)  ...  (Pn1  ...  Pk1  Cn1  ...  Ck1)
• Dispensa conectivas ,  e , torna  implícito

Formal norma implicativa:
• conjunção de cláusulas implicativas, i.e., de implicações de conjunção de
formulas atômicas positivas para disjunção de formulas atômicas positivas
• (P11  ...  Pi1  C11  ...  Ci1)  ...  (Pn1  ...  Pk1  Cn1  ...  Ck1)
• Dispensa conectivas ,  e , torna  implícito

São equivalentes pela definição da implicação: (P  C)  (P  C)
(P11  ...  Pi1  C11  ...  Ci1)  ...  (Pn1  ...  Pk1  Cn1  ...  Ck1)
 ((P11  ...  Pi1)  (C11  ...  Ci1))  ...  ((Pn1  ...  Pk1)  (Cn1  ...  Ck1))
 (P11  ...  Pi1  C11  ...  Ci1)  ...  (Pn1  ...  Pk1  Cn1  ...  Ck1)
Prolog puro: Lógica de Horn L1ch
Programa Prolog = formula da Lógica de Horn L1ch sem
predicado de igualdade
 Formula de L1ch:

• Formula da lógica dos predicados em forma normal implicativa
com clausulas de conclusão única
• (P11  ...  Pi1  C1)  ...  (Pn1  ...  Pk1  Cn)

L1ch  L1h:
• Algumas formulas da lógica dos predicados não tem formula de
Horn equivalente
• ex, animalLover(X)  animal(Y)  kills(X,Y).
Programação em lógica como formalismo de
representação do conhecimento


Meio termo entre lógica dos predicados e regras “intuitivas” de shell
Vantagens para aquisição de conhecimento:
• Formula da lógica de Horn tem mapeamento direto com de bases fatos e
de regras intuitivas de shell de sistemas especialistas
• Representação mais simples e intuitiva do que lógica sem atalhar nível da
formalização
• Reduz consideravelmente número de paráfrases sintáticas

Vantagens para máquina de inferência:
• Raciocínio dedutivo correto e semi-completo: a refutação por resolução
• Espaço de busca da refutação por resolução muito menor em lógica de
Horn do que é lógica dos predicados (eficiência)

Perda de expressividade em comparação da lógica dos predicados:
• Facilmente contornável para maioria das aplicações de IA
• Uso prático principal dos provadores de teoremas da lógica dos
predicados: engenharia de software formal e matemática computacional,
não IA
Unificação

Exemplos:
• unif(conhece(joao,X),conhece(Y,leandro)) =
{X/Leandro,Y/joao}
• unif(conhece(joao,X),conhece(X,leandro) = fail
• unif(conhece(joao,X),conhece(Y,mae(Y)) =
{Y/joao, X/mae(joao)}
• unif(conhece(joão,X),conhece(Y,Z)) = {Y/João, X/Z}, ou
{Y/joão, X/Z, W/zelda} ou {Y/joão, X/joão, Z/joão} ...


Unificador mais geral: com menor número de variáveis
instanciadas
Substituição mínima: com menor número de pares Var/const
Cláusulas Prolog x Cláusulas de Horn

Fatos Prolog:
• Cláusulas de Horn com premissa única T implícita
• Escritos C. Com semântica: T  C

Regras Prolog:
• Outras cláusulas de Horn
• Escrita C :- P1, ... ,Pn. Com semântica: P1  ...  Pn  C
• Escopo das variáveis = uma cláusula

Premissas de várias cláusulas com a mesma conclusão são
implicitamente disjuntivas
• Semântica de: C :- P1, ... ,Pn. C :- Q1, ... ,Qm, é:
(P1  ...  Pn  C)  (Q1  ...  Qm  C)
 ((P1  ...  Pn )  C)  ((Q1  ...  Qm ))  C) (p+c).(q+c)
 ((P1  ...  Pn )  (Q1  ...  Qm ))  C
pq + c
 ((P1  ...  Pn )  (Q1  ...  Qm ))  C
 ((P1  ...  Pn )  (Q1  ...  Qm ))  C
West é criminoso? em lógica dos predicados

Requisitos em inglês
1. It is crimimal for an American to
sell weapons to an hostile country
2. Nono owns missiles
3. Nono acquires all its missiles from
West
4. West is American
5. Nono is a nation
6. Nono is an enemy of the USA
0. Is West a crimimal?

Em lógica da 1a ordem
1.  P,W,N american(P)  weapon(W) 
nation(N)  hostile(N) 
sells(P,N,W)  criminal(P)
2.  W owns(nono,W)  missile(W)
3.  W owns(nono,W)  missile(W) 
sells(west,nono,W)
7.  X missile(W)  weapon(W)
8.  X enemy(N,america)  hostile(N)
4. american(west)
5. nation(nono)
6. enemy(nono,america)
9. nation(america)
West é criminoso?
em formal normal implicativa

Em lógica da 1a ordem
1.  P,W,N american(P)  weapon(W)
 nation(N)  hostile(N) 
sells(P,N,W)  criminal(P)
2.  W owns(nono,W)  missile(W)
3.  W owns(nono,W)  missile(W) 
sells(west,nono,W)
7.  X missile(W)  weapon(W)
8.  X enemy(N,america) 
hostile(N)
4. american(west)
5. nation(nono)
6. enemy(nono,america)
9. nation(america)

Em formal normal
american(P)  weapon(W) 
nation(N)  hostile(N) 
sells(P,N,W)  criminal(P)
owns(nono,m1)
missile(m1)
owns(nono,W)  missile(W) 
sells(west,nono,W)
missile(W)  weapon(W)
enemy(N,america)  hostile(N)
american(west)
nation(nono)
enemy(nono,america)
nation(america)
West é criminoso? em Prolog

Em Lógica de Horn:
american(P)  weapon(W) 
nation(N)  hostile(N) 
sells(P,N,W) => criminal(P)
owns(nono,m1)
missile(m1)
owns(nono,W)  missile(W) 
sells(west,nono,W)
missile(W)  weapon(W)
enemy(N,america)  hostile(N)
american(west)
nation(nono)
enemy(nono,america)
nation(america)

Em Prolog:
criminal(P) :- american(P), weapon(W),
nation(N), hostile(N),
sells(P,N,W).
owns(nono,m1).
missile(m1).
sells(west,nono,W) :- owns(nono,W),
missile(W).
weapon(W) :- missile(W).
hostile(N) :- enemy(N,america).
american(west).
nation(nono).
enemy(nono,america).
nation(america).
West é criminoso? busca
criminal(P) :- american(P), weapon(W),
nation(N), hostile(N),
sells(P,N,W).
owns(nono,m1).
missile(m1).
sells(west,nono,W) :- owns(nono,W),
missile(W).
weapon(W) :- missile(W).
hostile(N) :- enemy(N,america).
american(west).
nation(nono).
enemy(nono,america).
nation(america).
criminal(west)? <- yes.
•american(west)? -> yes.
•weapon(W)? <- W = m1.
missile(W)? -> W = m1.
•nation(N)? -> N = nono.
•hostile(nono)? <- yes.
enemy(nono,america)? -> yes.
•sells(west,nono,m1)? <- yes.
owns(nono,m1)? -> yes.
missile(m1)? -> yes.

West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(P)
american(P)
weapon(W)
nation(N)
hostile(N)
sells(P,N,W)
sells(west,nono,W)
missile(W)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(P)
weapon(W)
nation(N)
hostile(N)
sells(P,N,W)
sells(west,nono,W)
missile(W)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(W)
nation(N)
hostile(N)
sells(west,N,W)
sells(west,nono,W)
missile(W)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(W)
nation(N)
hostile(N)
sells(west,N,W)
sells(west,nono,W)
missile(W)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(W)
nation(N)
hostile(N)
sells(west,N,W)
sells(west,nono,W)
missile(W)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(W)
nation(N)
hostile(N)
sells(west,N,W)
sells(west,nono,W)
missile(W)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(W)
nation(N)
hostile(N)
sells(west,N,W)
sells(west,nono,W)
missile(W)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(W)
nation(N)
hostile(N)
sells(west,N,W)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(N)
hostile(N)
sells(west,N,W)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(N)
hostile(N)
sells(west,N,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(N)
hostile(N)
sells(west,N,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(N)
hostile(N)
sells(west,N,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(N)
sells(west,N,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
enemy(N,america)
nation(nono)
nation(america)
enermy(nono,america)
owns(nono,W)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
enemy(N,america)
nation(nono)
nation(america)
enermy(nono,america)
owns(nono,W)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,m1)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,m1)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,m1)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,m1)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,m1)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,m1)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,m1)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,m1)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,m1)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,m1)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,m1)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,m1)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,m1)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,m1)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,m1)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)? yes
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,m1)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,america)
owns(nono,m1)
enermy(nono,america)
owns(nono,m1)
West é criminoso ? backtracking
criminal(P) :- american(P), weapon(W),
nation(N), hostile(N),
sells(P,N,W).
owns(nono,m1).
missile(m1).
sells(west,nono,W) :- owns(nono,W),
missile(W).
weapon(W) :- missile(W).
hostile(N) :- enemy(N,america).
american(west).
nation(america).
enemy(nono,america).
nation(nono).
criminal(west)? <- yes.
•american(west)? -> yes.
•weapon(W)? <- W = m1.
missile(W)? -> W = m1.
•nation(N)? -> N = america.
•hostile(america)? <- no.
enemy(america,america)? -> no.
•backtrack: nation(N),
N \ {america}? -> N = nono.
•hostile(nono)? <- yes.
enemy(nono,america)? -> yes.
•sells(west,nono,m1)? <- yes.
owns(nono,m1)? -> yes.
missile(nono,m1)? -> yes.
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(N)
hostile(N)
sells(west,N,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(america)
nation(nono)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(N)
hostile(N)
sells(west,N,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(america)
nation(nono)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(america)
hostile(N)
sells(west,N,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(america)
nation(nono)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(america)
hostile(america)
sells(west,america,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
enemy(N,america)
nation(america)
nation(nono)
enermy(nono,america)
owns(nono,W)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(america)
hostile(america)
sells(west,america,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
enemy(N,america)
nation(america)
nation(nono)
enermy(nono,america)
owns(nono,W)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(america)
hostile(america)
sells(west,america,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
enemy(N,america)
nation(america)
nation(nono)
enermy(nono,america)
owns(nono,W)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(america)
hostile(america)
sells(west,america,m1)
sells(west,nono,W)
missile(m1)
enemy(N,america)
owns(nono,W)
fail
american(west)
missile(m1)
nation(america)
nation(nono)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(america)
hostile(america)
sells(west,america,m1)
sells(west,nono,W)
backtrack
missile(m1)
enemy(N,america)
owns(nono,W)
fail
american(west)
missile(m1)
nation(america)
nation(nono)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(N)
backtrack
hostile(N)
sells(west,N,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
enemy(N,america)
nation(america)
nation(nono)
enermy(nono,america)
owns(nono,W)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(N)
hostile(N)
sells(west,N,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
enemy(N,america)
nation(america)
nation(nono)
enermy(nono,america)
owns(nono,W)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(N)
sells(west,N,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
enemy(N,america)
nation(america)
nation(nono)
enermy(nono,america)
owns(nono,W)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para trás
criminal(west)?
criminal(west)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
enemy(N,america)
nation(america)
nation(nono)
enermy(nono,america)
owns(nono,W)
owns(nono,m1)
Algoritmo da máquina de inferência Prolog
Tentar unificar termo do objetivo Oi corrente com as
cabeças das claúsulas da BC, na ordem de escritura
 Seja C a 1a cabeça a se unificar com Oi via subsituição :

• se C for um fato, devolve: T e  como resultado
• se C for conclusão da regra C :- P1, ..., Pn, então:



o novo objetivo corrente Oi+1 = P1
se P1 for verdade, então recursivamente tentar provar P2, ..., Pn
Se nenhuma cabeça das claúsulas da BC se unifica com Oi:
• devolver F como resultado, e
• retroceder, buscando uma prova alternativa para Oi-1, o último
objetivo provado antes de Oi
West é criminoso?
Encadeamento de regras para frente
criminal(west)?
criminal(P)
american(P)
weapon(W)
nation(N)
hostile(N)
sells(P,N,W)
sells(west,nono,W)
missile(W)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(N,america)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para frente
criminal(west)?
criminal(P)
american(P)
weapon(W)
nation(N)
hostile(N)
sells(P,N,W)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,N)
owns(nono,m1)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para frente
criminal(west)?
criminal(P)
american(P)
weapon(m1)
nation(N)
hostile(N)
sells(P,N,W)
sells(west,nono,W)
missile(W)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,N)
owns(nono,W)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para frente
criminal(west)?
criminal(P)
american(P)
weapon(m1)
nation(N)
hostile(N)
sells(P,N,W)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enemy(nono,N)
owns(nono,m1)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para frente
criminal(west)?
criminal(P)
american(P)
weapon(m1)
nation(N)
hostile(nono)
sells(P,N,W)
sells(west,nono,W)
missile(W)
american(west)
missile(m1)
nation(nono)
nation(america)
owns(nono,W)
enemy(nono,N)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para frente
criminal(west)?
criminal(P)
american(P)
weapon(m1)
nation(N)
hostile(nono)
sells(P,N,W)
sells(west,nono,W)
missile(m1)
american(west)
missile(m1)
nation(nono)
nation(america)
owns(nono,m1)
enemy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para frente
criminal(west)?
criminal(P)
american(P)
weapon(m1)
nation(N)
hostile(nono)
sells(P,N,W)
sells(west,nono,m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para frente
criminal(west)?
criminal(P)
american(west)
weapon(m1)
nation(nono)
hostile(nono)
sells(west,nono,m1)
sells(west,nono,m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para frente
criminal(west)?
criminal(west)
weapon(m1)
hostile(nono)
sells(west,nono,m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enermy(nono,america)
owns(nono,m1)
West é criminoso?
Encadeamento de regras para frente
criminal(west)? yes
criminal(west)
weapon(m1)
hostile(nono)
sells(west,nono,m1)
american(west)
missile(m1)
nation(nono)
nation(america)
enermy(nono,america)
owns(nono,m1)
Prolog, refutação e resolução

Mecanismo de inferência de Prolog:
• forma particular de refutação por resolução
• com estratégia de resolução linear de entrada, i.e., a cada passo sempre
resolvendo uma das clausulas iniciais (base de conhecimento e negação da
consulta), varrendo as candidatas na ordem de escritura do programa de
cima para baixo
• com outra clausula sendo a última a ter sido derivada
• escolhendo os literais na ordem de escritura das premissas de esquerda
para direita





Estratégia com bom compromisso simplicidade/eficiência
Criar a árvore de prova por meio de cima para baixo em
profundidade primeira
Em caso de falha, efetua um retrocesso linear e sistemático
Encadeia as regras para trás
É dirigido pelos objetivos
West é criminoso? Prova Prolog como
refutação com resolução SLD
(american(P)  weapon(W) 
nation(N)  hostile(N) 
sells(P,N,W)  criminal(P))
//1
 (T  owns(nono,m1))
//2a
 (T  missile(m1))
//2b
 (owns(nono,W)  missile(W)
 sells(west,nono,W))
//3
 (T  american(west))
//4
 (T  nation(nono))
//5
 (T  enemy(nono,america))
//6
 (missile(W)  weapon(W))
//7
 (enemy(N,america)
 hostile(N))
//8
 (T  nation(america))
//9
 (criminal(west)  F)
//0
1. Resolver 0 com 1 unificando P/west:
american(west)  weapon(W)  nation(N) 
hostile(N)  sells(west,N,W)  F
2. Resolver 10 com 4:
weapon(W)  nation(N)  hostile(N) 
sells(west,N,W)  F
3. Resolver 11 com 7:
missile(W)  nation(N)  hostile(N) 
sells(west,N,W)  F
4. Resolver 12 com 2b unificando W/m1:
nation(N)  hostile(N)  sells(west,N,m1)  F
5. Resolver 13 com 5 unificando N/nono:
hostile(nono)  sells(west,nono,m1)  F
6. Resolver 14 com 8 unificando N/nono:
enemy(nono,america)  sells(west,nono,m1)  F
7. Resolver 15 com 6: sells(west,nono,m1)  F
8. Resolver 16 com 3 unificando W/m1:
owns(nono,m1)  missile(m1)  F
9. Resolver 17 com 2a: missile(m1)  F
10. Resolver 18 com 2b: F
//10
//11
//12
//13
//14
//15
//16
//17
//18
Prolog devolve a primeira resposta
g1(a).
g21(a).
g3(a).
g4(a).
g1(b).
g21(b).
g22(b).
g3(b).
g(X) :- g1(X), g2(X).
g(X) :- g3(X), g4(X).
g2(X) :- g21(X), g22(X).
$ prolog
?- consult(“g.pl”).
yes
?- g(U).
U=b
?- ;
U=a
?- ;
no
?- halt.
$
Forçar o backtracking
para obter todas as respostas
g1(a).
g21(a).
g3(a).
g4(a).
g1(b).
g21(b).
g22(b).
g3(b).
g(X) :- g1(X), g2(X).
g(X) :- g3(X), g4(X).
g2(X) :- g21(X), g22(X).
g(U)? <- U = b.
 g1(U)? -> U = a.
 g2(a)? <- no.
• g21(a)? -> yes.
• g22(a)? -> no.

g1(U), U \ {a}? -> U = b.

g2(b)? <- yes.
• g21(b)? -> yes.
• g22(b)? -> yes.
;

g1(U), U \ {a,b} ? -> no.
Backtracking em cascatas
g1(a).
g21(a).
g3(a).
g4(a).
g1(b).
g21(b).
g22(b).
g3(b).
g(X) :- g1(X), g2(X).
g(X) :- g3(X), g4(X).
g2(X) :- g21(X), g22(X).
g(U), g \ {g1,g2}? <- U = a.


;
g3(U)? -> U = a.
g4(a)? -> yes.

g3(U), U \ {a}? -> U = b.

g4(b)? -> no.
g3(U), U \ {a,b}? -> no.
g(U), g \ {g1,g2 ; g3,g4}? -> no.

Prolog puro:
sem atribuição, nem predicado de igualdade

Em Prolog, = é o operador de unificação explícita:
•
•
•

é uma consulta lógica que retorno verdadeiro ou falso e potencialmente instância
variáveis
não é um operador de atribuição como na programação imperativa
não é um predicado de declaração de igualdade como na lógica dos predicados
?- geber = senior -> no.
?- prof(X,disc(Y,dept(di,ufpe))) = prof(geber,disc(ia,Z)).
-> X = geber, Y = ia, Z = dept(di,ufpe).
prof(ia,di,ufpe,geber). musico(senior).
?- geber = senior, prof(ia,di,ufpe,X), musico(X). -> no.
e não: X = geber = senior.
prof(ia,di,ufpe,pessoa(geber,_). musico(pessoa(_,senior)).
pessoa(geber, senior).
?- prof(ia,di,ufpe,X), musico(X). -> X = pessoa(geber,senior).
Prolog: listas



[ e ]: início e fim de lista
, separação entre eltos
|: separação entre 1o elto e resto da lista
açúcar sintático para predicado .(Head,Tail)
ex.: [a,[b,c],d] açúcar sintático para .(a,.(.(b,.(c,[])),.(d,[])))
?- [a,b,X,p(Y,C)] = [Head|Tail]
Head = a, Tail = [b,X,p(Y,C)]
?- [[p(X),[a]],q([b,c])] = [[H|T1]|T2]
H = p(X), T1 = [[a]], T2 = [q([b,c])]
member(X,[X|_]).
member(X,[_|Z]) :- member(X,Z).
?- member(b,[a,b,c]) -> yes.
?- member(X,[a,b,c]) -> X = a ; X = b ; X = c ; no.
Programação relacional:
vários usos do mesmo predicado

Definiçaõ única:
append([],L,L).
append([H|T1],L,[H|T2]) :- append(T1,L,T2).

Uso como verificador:
?- append([a,b],[c],[a,b,c]). -> yes.
?- append([a,b],[c],[a]). -> no.

Uso como instanciador:
?- append([a,b],[c],R). -> R = [a,b,c].
?- append(H,[c],[a,b,c]). -> H = [a,b].

Uso como resolvedor de restrições:
?- append(X,Y,[a,b,c]). -> X = [], Y = [a,b,c] ; -> X = [a], Y = [b,c] ...

Uso como enumerador:
?- append(X,Y,Z). -> X = [], Y =[], Z = [] ; -> X = [_], Y = [], Z = [_] ...

Implementa sozinha funcionalidades de 8 métodos imperativos!
Programação procedimental
x programação em lógica
1.
2.
3.
4.
Modelagem estrutural
Modelagem comportamental
Codificar estruturas de dados
Codificar passo a passo
estruturas de controle
5. Compilar/interpretar programa
6. Executar programa
A. Declarar o que é verdade
(fatos e regras)
B. Compilar/interpretar programa
C. Fazer consulta sobre verdade
de um fato
A = 1+3
C=6
Programação declarativa:
• não há necessidade de 2 e 4 !
• estrutura de controle única
(dedução automática) embutida
no compilador/interpretador
usada para todos os problemas !
Aspectos de Prolog fora
da Lógica Clássica de Horn da 1a ordem
Acrescentados por necessidades práticas de
programação
 Semântica imperativa ou funcional, de lógicas não
clássicas ou clássicas de ordem superior
 Negação por falha: not
 Controle e poda da busca: ! (cut), repeat, ...
 Entrada/saída: read, write, ...
 Atribuição aritmética: is
 Modificação dinâmica da base de conhecimento: assert,

retract

Meta-programação: var, =.., name, list
Prolog: aritmética

3 tipos de operadores built-in aritméticos:
• calculadores (n-ários infixos): +, -, *, /, mod
• comparadores (binários infixos): =:=, =\=, <, >, =<, >=
• o atribuídor is: Variável is ExpressãoAritmética

Expressão aritmética:
• fórmula atômica contendo apenas números e calculadores
aritméticos
• todos os argumentos dos calculadores e comparadores devem ser
instanciados com expressões aritméticas
Prolog: exemplos de aritmética 1
> ?- 1 + 1 < 1 + 2.
yes
> ?- 1 + 3 =:= 2 + 2.
yes
> ?- 1 + 3 = 2 + 2.
no
> ?- 1 + A = B + 2.
A=2
B=1
yes
> ?- 1 + A =:= B + 2.
Error
> ?- A = 2, B = 1, 1 + A =:= B + 2.
A=2
B=1
yes
> ?- C = 1 + 2.
C = 1+2
yes
> ?- C is 1 + 2.
C=3
yes
> ?- C is D, D = 1 + 2.
Error.
> ?- D = 1 + 2, C is D.
D=1+2
C=3
yes
> ?- -1+2 = +(-(1),2).
no
> ?- -1+2 =:= +(-(1),2).
yes
Prolog: exemplos de aritmética 2
fac(0,1) :- !.
fac(I,O) :- I1 is I - 1,
fac(I1,O1), O is I * O1.
?- fac(1,X).
X=1
yes
?- fac(3,X).
X=6
yes
?- fac(5,X).
X = 120
yes
?
sum([],0).
sum([H|T],N) :- sum(T,M),
N is H + M.
?- sum([2,1,3,1],S).
S=7
yes
?- sum([2,10,1],S).
S = 13
yes
?
Evitar backtracking inútil: ! (o Cut)
Operador built-in de poda da árvore de prova
 Logicamente sempre verificado
 Com efeito colateral de impedir backtracking:

• na sua esquerda na cláusula que ocorre
• em outras cláusulas com a mesma conclusão

ex: A :- B, C, D.
•
•
C :- M, N, !, P, Q.
C :- R.
impede backtracking P -> N
permite backtracking N -> M, Q -> P,
D -> (R xor Q), (P xor R) -> B
• R tentado:
 unicamente se M ou N falha
 nunca se P ou Q falha
sign(-2,Y)
Exemplo de Cut
sign(X,-1) :- X<0, !.
sign(X,0) :- X=0, !.
sign(X,1) :- X>0.
?- sign(-2,Y).
Y=-1
yes
?- sign(0,Y).
Y=0
yes
Y=-1
Y=0
Y=1
-2 < 0, !
-2=0, !
-2 > 0
!
fail
fail
yes
Sub-árvore podada
sign(0,Y)
Y=-1
Y=0
Y=1
0 < 0, !
0=0, !
0>0
fail
!
fail
yes
Sub-árvore
podada
Perigos do Cut
member(X,[X|_]).
member(X,[_|Z]) :- member(X,Z).
add2set1(E,Si,_) :- member[E,Si], !.
add2set1(E,Si,[E|Si]).
member(X,[X|_]).
member(X,[_|Z]) :- member(X,Z).
add2set1(E,Si,So) :- member[E,Si], !, So=Si.
add2set1(E,Si,[E|Si]).
?- add2set1(a,[a,b],So).
yes, So=[a,b]
?- add2set1(c,[a,b],So).
yes, So=[c,a,b]
?- add2set1(a,[a],[a,a]).
yes
?- add2set1(a,[a,b],So).
yes, So=[a,b]
?- add2set1(c,[a,b],So).
yes, So=[c,a,b]
?- add2set1(a,[a],[a,a]).
no
• Programas com cuts não possuem semântica declarativa em lógica de Horn.
• Apenas uma semântica procedimental, como um programa imperativo.
Prolog: exemplos de teste de tipos
?- var(X).
X = _3
yes
?- var(2).
no
?- var(a).
no
?- var(p(a,X)).
no
?- nonvar(2), nonvar(p(2,X,a)).
X = _11
yes
?- X is 2 + 3, var(X).
no
?- var(X), X is 2 + 3.
X=5
yes
numberp(Term) :- integer(Term).
numberp(Term) :- real(Term).
structp(Term) :- nonvar(Term),
not atomic(Term).
listp(Term) :- nonvar(Term),
listp1(term).
listp1([]).
listp1([H|T]) :- listp1(T).
factp(Term) :- strucp(Term),
not listp(Term).
Prolog: conversão de tipos
name(Átomo,Caracteres):
 conversão bi-direcional entre
átomo e cadeia de caracteres
que constitui o seu nome
list(CódigosAscii,Caracteres):
 conversão bi-direcional entre
um lista de inteiros vistos
como códigos ascii e cadeia de
caracteres correspondente
Fato =.. Lista:
 conversão bi-direcional entre
fato e lista, funtor sendo
cabeça e argumentos sendo
resto
?- name(A,"blabla").
A = blabla
?- name(blabla,S).
S = "blabla"
?- list(X,"bla").
X = [98,108,97]
?- list([98,108,97],Y).
Y = "bla”
?- p(a,X,c) =.. Y.
X = _5, Y = [p,a,_5,c]
?- Y =.. [p,a,X,c].
Y = p(a,_20,c), X = _20
Prolog: entrada/saída 1

Ler/escrever estrutura de dados dificilmente pode ser
visto como resultando de uma dedução:
• E/S não se integre naturalmente no paradigma de PL
• requer predicados extra-lógicos sem semântica declarativa em L1

Predicados built-in de Prolog para E/S:
• sempre verificados
• cumprem sua tarefa por efeitos colaterais
• não podem ser re-satisfeitos por backtracking
Prolog: entrada/saída 2
Ler e escrever termos: read, write, display.
 Ler e escrever caracteres: get, get0, put.
 Formatar a saída legívelmente: nl, tab.
 Ligar um canal de E/S com a tela ou com arquivos:
tell, telling, told, see, seeing, seen .
 Carregar arquivo fonte no ambiente do
interpretador: consult, reconsult


ex.: ?- read(X), Z is X + 1, write(Z).
2.
3
X = 2, Z = 3; no
?
Prolog: failure-driven loop
Loop gerada por backtracking forçado com fail e repeat.
 repeat sempre verificado e re-verificado no backtracking
(true sempre verificado mas falha no backtracking)

consult(File) :- see(File), consult-loop, seen.
consult-loop :- repeat, read(Clause), process(Clause), !.
process(X) :- end_of_file(X), !.
process(Clause) :- assert(Clause), fail.
Hipóteses sobre completude
da base de conhecimento


Dado uma base de conhecimento lógica B, existem sentenças lógicas
S (consultas Ask) tal que nem S, nem S é conseqüência lógica de B
Exemplo:
B = {ônibusPara(garanhuns,10:00), ônibusPara(salgueiro,12:00)}
S = ônibusPara(garanhuns,12:00)
B | S e B | S



Resposta a tal consulta depende da hipótese sobre a completude da
informação na BC feita pela máquina de inferência
Hipótese de mundo aberto (BC suposta incompleta ):
•
•
se B | S e B | S, então Ask(S) = unknown
provadores de teorema em cálculo dos predicados e pelas lógicas descritivas
•
se B | S e B | S, então Ask(S) = False
Hipótese de mundo fechado (BC suposta completa ):
• programação em lógica, sistemas de produção e bancos de dados
Hipótese do mundo fechado


Concluir Ask(S) = False apenas a partir de B | S não é uma
inferência dedutivamente correta
Epistemologicamente:
• Ask(S) = False concluído a partir de B | S,
• é mais fraco do que Ask(S) = False derivado a partir de B | S

É uma forma limitada de:
• Abdução
• Raciocínio por default
• Raciocínio não monótono

Maioria da máquinas de inferência que utilizam a hipótese do mundo
fechado:
• Não armazenam fatos negativos nas suas BC, i.e., não há ações Tell(S)
• Nem são capaz de deduções da forma B | S, apenas B | S
Hipótese do mundo fechado
e manutenção da verdade

Manutenção da verdade:
• Manter consistência de B depois de Tell(S,t)
• Requer Retract(S´,t+1), S´, S foi utilizada na prova de S´

Ask(S,t) = False porque B(t) | S:
• é apenas uma hipótese por default
• pode ser revisada na luz de nova evidência
• ex, no caso de Tell(S´,t+1) com B(t+1) = B(t)  {S´} | S

Ask(S,t) False porque B(t) | S:
• é uma dedução provada
• não pode ser revisada na luz de novos fatos
• ex, Tell(S´,t+1) com B(t+1) = B(t)  {S´} | S
é contraditório com B(t) | S
Negação por falha
Prolog permite uso da negação for falha (operador not )
em consultas e em premissas de regras
 Não permite negação por falha em fatos ou conclusão de
regras
 not L = T concluído a partir de P | L
 Diferente de L = T concluído a partir de P | L
 Quando encontra objetivo not L, Prolog tenta provar L

• se conseguir, conclui not L = fail
• se não conseguir, conclui not L = true
Uso da negação por falha para
raciocínio por default
ave(piupiu).
papa_leguas(bipbip).
ave(X) :- papa_leguas(X).
voa1(X) :- ave(X), not papa_leguas(X).
voa2(X) :- not papa_leguas(X), ave(X).
?- voa1(X).
X = piupiu
yes
?- ;
no.
?- voa2(X).
no.
Perigos do uso ingênuo da negação por falha
edge(a,b).
sink(X) :- not edge(X,Y).
?- sink(a)
no.
?- sink(b)
yes.
? sink(X)
no.
Estilo recomendado para evitar
semântica não intuitiva e loops
Evitar:
 Regras universais (non ground) antes de fatos instanciados (ground)
 Regras recursivas antes da regra de caso base
 Premissas recursivas antes das premissas não recursivas
 Premissas negadas antes ou sem premissas positivas compartilhando
as mesmas variáveis (floundering)
 Recursão através da negação (stratificação)
 Conclusão com variável X de profundidade p junto com premissa com
variável X de profundidade q  p antes de outra premissa com
variável X de profundidade r  p (occur-check)
 Cuts em casos não excludentes
Semântica declarativa de programas Prolog





Semântica de
P1: {ônibusPara(garanhuns,10:00). ônibusPara(salgueiro,12:00)}.
Com hipótese do mundo aberto seria:
X,Y ((X=garanhuns  Y=10:00)  (X=salgueiro  Y=12:00))
 ônibusPara(X,Y))
Mas com a hipótese do mundo fechado de Prolog, é de fato:
X,Y ((X=garanhuns  Y=10:00) (X=salgueiro  Y=12:00))
 ônibusPara(X,Y))
Semântica de P2:
{prof(geber). prof(jacques). aluno(Y) :- not prof(Y).}
X (prof(X)  X=geber  X=jacques)
 X (aluno(X)  Y (X=Y  prof(Y))
Uso dual de Prolog para sistema inteligente

Como formalismo de
representação do conhecimento
Maquina de
Ask
Base de
Inferência:
Conhecimento:
Compilador/
Tell
Fatos e Regras
Interpretador
Prolog
Retract
Prolog

Como linguagem de
programação
Ask
Base de
Conhecimento:
Tell
sentenças em
formalismo F Retract
Maquina de
Inferência
implementando
em Prolog
raciocínio R
em formalismo F
Maquina de
Inferência:
Compilador/
Interpretador
Prolog
Implementação Prolog de máquina de
inferência encadeando regras
Codificação da base de fatos
•
fact(TermoProlog).
Codificação da base de regras
•
•
•
if P1 conj ... conj Pn then C onde
P1 ... Pn e C são termos Prolog
conj é and ou or
Codificação das consultas
•
forward deriva todos os fatos
Exemplo de base de conhecimento
if hallWet and kitchenDry then leakInBathroom
if hallWet and bathroonDry then problemInKitchen
if windowClosed or noRain then noWaterFromOutside
if problemInKitchen and noWaterFromOutside
then leakInKitchen
Exemplos de consulta
?- forward
Derive: problemInKitchen
Derive: noWaterFromOutside
Derive: leakInKitchen
No more facts
?- is_true(leak_in_kitchen).
yes
Implementação Prolog de máquina de
inferência encadeando regras
Para frente:
::::-
op( 800, fx, if).
op( 700, xfx, then).
op( 300, xfy, or).
op( 200, xfy, and).
forward :- new_derived_fact(P), !,
write('Derived: '), write(P), nl, assert(fact(P)),
forward ; write('No more facts').
new_derived_fact(Concl) :- if Cond then Concl,
not fact(Concl), composed_fact(Cond).
composed_fact(Cond) :- fact(Cond).
composed_fact(Cond1 and Cond2) :composed_fact(Cond1), composed_fact(Cond2).
composed_fact(Cond1 or Cond2) :composed_fact(Cond1) ; composed_fact(Cond2).
Pata trás:
::::-
op( 800, fx, if).
op( 700, xfx, then).
op( 300, xfy, or).
op( 200, xfy, and).
is_true( P) :- fact( P).
is_true( P) :- if Condition then P,
is_true( Condition).
is_true( P1 and P2) :- is_true( P1), is_true( P2).
is_true( P1 or P2) :- is_true( P1) ; is_true( P2).
Prolog x Programação OO

Funcionalidades built-in:
• + unificação e busca
• - tipos, herança e encapsulamento

Ontologicalmente:
• Entidade Atómica (EA): em OO, valor de tipo built-in
em Prolog, átomo (argumento ou predicado)
• Entidade Composta (EC): em OO, objeto
em Prolog, fato
• Relação simples entre EC e EA: em OO, atributo de tipo built-in
em Prolog, posição em um predicado
• Relação simples entre ECs: em OO, atributo de tipo objeto
em Prolog, predicado
• Relação complexa entre entidades: em OO, método
em Prolog, conjunto de regras
Vantagens de Prolog

Como formalismo de
representação do conhecimento
• Intuitividade das regras com
rigor formal da lógica
• Teoria muito completa sobre
semântica, corretude e
completude da inferência,
limites de expressividade,
complexidade etc.
• Compiladores muito eficientes
• Versátil, serve de base para
grande maioria dos mecanismos
de inferência da IA

Como linguagem de
programação
• Declarativo com semântica
formal
• Conciso
• Eficiente
• De nível suficientemente alto
para implementação rápida e
concisa de máquinas de
inferência
• Computacionalmente completo
• Versátil, serve como linguagem
de programação, de script e de
definição e consulta de dados
Limitações de Prolog

Como formalismo de
representação do conhecimento
• Objetos compostos com
restrições complexas
• Raciocínio com hipótese do
mundo aberto
• Conhecimento procedimental e
numérico
• Tratamento da incerteza
• Atualização da base de
conhecimento (Tell e Retract)
com semântica declarativa
• Especificação declarativa de
estratégia de busca

Como linguagem de
programação
• Recursos muito limitados para:


Estruturação de objetos
complexos
Programação de larga escala
• Sem recursos para interfaces
gráfica, programação
concorrente e distribuída
• Baixa integração com
metodologias e ferramentas de
desenvolvimento de larga
divulgação

UML, RUP, Java, XML, .net,
web services, BD O-R, etc.
Extensões de Prolog

PL tabelada, ex, XSB
PL tipada, ex, Mercury
PL funcional, ex, -Prolog
PL de ordem superior, ex, Hilog
PL orientada a objetos, ex, F-Logic
PL multi-paradigma, ex, LIFE
PL com restrições, ex, Eclipse
PL concorrente, ex, BinProlog
PL distribuída, ex, Jinni
BD dedutivos, ex, Transaction Logic

Disciplinas:









•
•
Paradigmas de linguagens computacionais
Programação declarativa e banco de
dados inteligentes

PL com negação explícita
PL com disjunções
PL abdutiva
PL indutiva
PL probabilista

Disciplinas:




•
•
•
Agentes autônomos e
sistemas multiagentes
Engenharia do
conhecimento e sistemas
especialistas
Aprendizagem de máquina