Ensino Superior
Lógica Matemática e Computacional
7 – Introdução à Programação Lógica
Amintas Paiva Afonso
SUMÁRIO
1. Lógica e Programação de
Computadores
2. A Linguagem Prolog








Fatos
Consultas
Regras
Regra de Inferência: Resolução
Exemplo de Programa e Consultas
Recursão
Principais Aplicações
O Significado dos Programas Prolog
Lógica e Programação de
Computadores
• Na lógica de predicados usamos regras de
inferência para demonstrar que uma tese é
conseqüência de determinadas hipóteses
• Programação em Lógica e especificamente a
linguagem Prolog – Progamming in Logic –
também pode provar teses a partir de
hipóteses
• A linguagem Prolog inclui: predicados,
conectivos lógicos e regras de inferência Princípio da Resolução
Lógica e Programação de
Computadores
• Prolog é uma linguagem declarativa ao
invés de procedimental.
• Um programa Prolog consiste na
declaração (ou descrição de uma
interpretação) de hipóteses que são
verdadeiras em uma interpretação.
Lógica e Programação de
Computadores
• O conjunto de declarações que forma um
programa Prolog é chamada a base de
dados (BD) desse programa.
• Para determinar se uma tese (consulta do
usuário à BD) é ou não verdadeira, Prolog
aplica suas regras de inferência na BD sem
a necessidade de instruções adicionais por
parte do programador.
Lógica e Programação de
Computadores
• BD convencionais descrevem apenas
fatos.
“Oscar é um avestruz”
• As sentenças de um Programa em
Lógica, além de descrever fatos, permite
a descrição de regras.
“Todo avestruz é um ave”
• Havendo regras, novos fatos podem ser
deduzidos.
“Oscar é uma ave”
Lógica e Programação de
Computadores
• Ponto focal da programação em lógica:
 identificar computação com dedução – a
execução de um programa limita-se à
pesquisa da refutação das sentenças do
programa (BD) mais a negação da
sentença consulta - “uma refutação é a
dedução de uma contradição”
Lógica e Programação de
Computadores
• As sentenças de um programa
prolog são expressas por cláusulas.
• Tipos de cláusulas: fatos e regras
 Fato: declaração de uma verdade
incondicional
 Regra: condição que deve ser
satisfeita para que um declaração seja
considerada verdadeira
A Linguagem Prolog
• Programar em Prolog consiste em:
 Declarar alguns fatos sobre objetos e
suas relações.
 Definir algumas regras sobre objetos e
suas relações.
 Fazer consultas sobre objetos e suas
relações.
A Linguagem Prolog
FATOS
• Os fatos permitem definir os
predicados:
- Exemplo: um sistema ecológico para
especificar a cadeia alimentar
come (urso, peixe)
come (urso, raposa)
come (cavalo, mato)
animal (urso)
animal (peixe)
animal (raposa)
% predicado binário
% predicado unário
A Linguagem Prolog
CONSULTAS
• De posse do programa Prolog (base de dados,
podemos fazer consultas .
Exemplos:
? come (cavalo, mato)
Resposta: yes
? come (urso, coelho)
Resposta: no
? come (urso, X)
Resposta: peixe
coelho
A Linguagem Prolog
REGRAS
• Uma regra é a descrição de um
predicado através de uma implicação
Exemplo: “um animal é presa se é comido
por outro animal”.
come(Y,X) ^ animal(X) -> presa(X)
em Prolog:
presa(X) :- come(Y,X), animal(X)
A Linguagem Prolog
REGRAS e CONSULTAS
• Acrescentando a nova regra à BD podemos
fazer novo tipo de consulta
come (urso, peixe)
come (urso, raposa)
% predicado
binário
come (cavalo, mato)
animal (urso)
animal (peixe)
% predicado
unário
animal (raposa)
presa(X) :- come(Y,X), animal(X) % regra
?-presa(x)
resposta: peixe e raposa
A Linguagem Prolog
REGRA DE INFERÊNCIA: RESOLUÇÃO
• As regras e os fatos de um programa
prolog correspondem à fórmulas de 1a
ordem transformada em Cláusulas de
Horn.
• Prolog trata as regras como sendo
quantificadas universalmente.
• A regra de inferência usada pelo
interpretador prolog é a regra da
resolução.
Como foi obtida a resposta do exemplo
anterior?
A Linguagem Prolog
REGRA DE INFERÊNCIA: RESOLUÇÃO
• Observe que a regra (Cláusula de Horn)
presa(X) :- come(Y,X), animal(X)
Corresponde a wff
xy(come(Y,X) ^ animal(X)) -> presa(X)
Corresponde a cláusula
~(come(X,Y) ^ animal(X)) v presa(x)
~come(X,Y) v ~animal(X) v presa(x)
A Linguagem Prolog
REGRA DE INFERÊNCIA: RESOLUÇÃO
• Regra da resolução:
Duas cláusulas de Horn são resolvidas
em uma nova cláusula se uma delas
contiver um predicado negado que
corresponda a um predicado não-negado
na outra cláusula.
A nova cláusula elimina o termo de
correspondência e fica disponível para
uso em resposta a pergunta.
As variáveis são substituídas por
constantes associadas de maneira
consistente.
A Linguagem Prolog
REGRA DE INFERÊNCIA: RESOLUÇÃO
• ? presa(X)
 O Prolog procura, na BD, por uma regra com o predicado
presa(X) como o conseqüente
 Busca outras cláusulas que possam ser resolvidas com a regra
 Faz as substituições das variáveis na cláusula regra
1. ~come(X,Y) v ~animal(X) v presa(X)
2. come(urso,peixe)
3. ~animal(peixe) v presa(peixe) {resolvente de 1 e 2}
4. animal (peixe)
5. presa (peixe)
{resolvente de 3 e 4}
 Refaz o processo procurando na BD outra cláusula a resolver
com a cláusula da regra.
Encontrará come(urso,peixe)
A Linguagem Prolog
REGRA DE INFERÊNCIA: RESOLUÇÃO
•
Outro exemplo: acrescentando à BD a regra: “x é caçado se é presa”
caçado(X) :- presa(X)
Como é feita a consulta que segue?
? caçado(X)
 a regra na forma simbólica é:
presa(X) -> caçado(X)
 a cláusula correspondente é:
~(presa(X) v caçado(X)
 essa cláusula é resolvida com a da regra de definição de presa e
seguindo a resolução obtém as respostas:
peixe
raposa
A Linguagem Prolog
EXEMPLO DE PROGRAMA E CONSULTAS
come (urso, peixe)
come (peixe,peixinho)
come (peixinho,alga)
come (quati,peixe)
come(urso,quati)
come (urso, raposa)
come(raposa,coelho)
come (coelho, mato)
come(urso,cavalo)
come(cavalo,mato)
come(gato-selvagem,cavalo)
animal(urso)
animal(peixe)
animal(peixinho)
animal(quati)
animal(raposa)
animal(coelho)
animal(cavalo)
animal(gato-selvagem)
planta(mato)
planta(alga)
presa(X) :- come(Y,X),
animal(X)
A Linguagem Prolog
EXEMPLO DE PROGRAMA E CONSULTAS
• Consultas e respostas:
? animal(coelho)
yes
? come(gato-selvagem,mato)
no
? come(X,peixe)
urso
quati
? come(X,Y),planta(Y)
peixinho alga
coelho mato
cavalo mato
A Linguagem Prolog
EXEMPLO DE PROGRAMA E CONSULTAS
• Consultas e respostas (continuação):
? presa(X)
peixe
peixinho
peixe
quati
raposa
coelho
cavalo
cavalo
A Linguagem Prolog
RECURSÃO
• As regras em Prolog são
implicações lógicas
 Podem depender de fatos:
presa(X) :- come(X,Y),animal(X)
 Podem depender de outras regras:
caçado(X) :- presa(X)
 Podem depender da própria regra:
com definição recursiva
A Linguagem Prolog
RECURSÃO
•
Exemplo: usar a BD ecológica para definir a relação
na-cadeia-alimentar(X,Y)
com o significado:
”Y está na cadeia alimentar de X”
que por sua vez pode significar duas coisas:
1. X come Y diretamente
2. X come algum animal que come algum animal
que come algum animal ... que come Y
A Linguagem Prolog
RECURSÃO (exemplo)
• O caso 2. pode ser reescrito como:
2’. “X come Z e Y está na cadeia
alimentar de Z”
• O caso 1. é o ponto de parada da regra
recursiva
• A regra incorpora os casos 1 e 2’:
na_cadeia_alimentar(X,Y) :- come(X,Y)
na_cadeia_alimentar(X,Y) :- come(X,Z),
na_cadeia_alimentar(Z,Y)
A Linguagem Prolog
RECURSÃO (exemplo)
? na_cadeia_alimentar(urso,Y)
resposta:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
peixe
quati
raposa
cavalo
peixinho
alga
peixe
peixinho
alga
coelho
mato
mato
A Linguagem Prolog
RECURSÃO (exemplo)
urso
urso
urso
urso
urso
peixe
quati
raposa
cavalo
peixe
peixe
peixinho
peixinho
alga
A Linguagem Prolog
PRINCIPAIS APLICAÇÕES DA LINGUAGEM
• Sistemas Baseados em
Conhecimentos
• Sistemas de Base de Dados
• Sistemas especialistas
• Processamento de Linguagem
Natural
• Educação
• Modelagem de arquiteturas não
convencionais
A Linguagem Prolog
O SIGNIFICADO DOS PROGRAMAS PROLOG
• Um programa Prolog possui três interpretações
semânticas básicas:
 Interpretação declarativa.
Entende-se que as cláusulas que definem um
programa descrevem uma teoria de primeira
ordem.
 Interpretação procedimental.
As cláusulas são vistas como entrada para um
método de prova.
 Interpretação operacional.
As cláusulas são vistas como comandos para
um procedimento particular de prova por
refutação.
A Linguagem Prolog
O SIGNIFICADO DOS PROGRAMAS PROLOG
• Proveito das alternativas semânticas:
 Declarativa: Permite a modelagem do
problema
simplificando
a
tarefa
de
programação
 Procedimental: Permite que o programador
identifique e descreva o problema em
subproblemas através de uma série de
chamadas a procedimentos
 Operacional: Permite controle da execução
através da ordenação das cláusulas e
objetivos
A Linguagem Prolog
O SIGNIFICADO DOS PROGRAMAS PROLOG
• Proveito das alternativas semânticas:
O programador deve se concentrar no
significado declarativo. Em problemas de
maior complexidade os aspectos
operacionais não podem ser ignorados
A Linguagem Prolog
O SIGNIFICADO DOS PROGRAMAS PROLOG
• Bibliografia
 Judith L. Gersting: Fundamentos
Matemáticos para a Ciência da
Computação, LTC Editora, 3a edição,
1995.
 Luiz A. M. Palazzo: Introdução à
Programação PROLOG, Editora da
Universidade Católica de
Pelotas/UCPEL - Pelotas