Prolog

Prévia do material em texto

Temas dos Seminários 
• Forma Normais 
Princípio da dualidade 
• Método Dedutivo 
 Dedução Natural 
 Tableaux 
 Resolução 
• Argumentos. 
 Definição 
 Validade 
 Argumentos Válidos 
 Regras de Inferência 
Temas dos Seminários 
• Cálculo de Predicados 
 Quantificadores e variáveis 
 Regras de inferência para o 
quantificador universal 
 Regras de inferência para o 
quantificador existencial 
 Teoremas e regras de equivalência do 
quantificador 
 
Temas dos Seminários 
• Aplicações utilizando programação 
em lógica. 
• A linguagem da Lógica de Primeira 
Ordem (L1O) 
• Correção, Completude dos sistemas 
formais. 
• Exemplos de lógicas não clássicas 
e aplicações da lógica. 
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) % predicado binário 
come (cavalo, mato) 
animal (urso) 
animal (peixe) % predicado unário 
animal (raposa) 
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 
 raposa 
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. peixe 
2. quati 
3. raposa 
4. cavalo 
5. peixinho 
6. alga 
7. peixe 
8. peixinho 
9. alga 
10. coelho 
11. mato 
12. mato 
A Linguagem Prolog 
 RECURSÃO (exemplo) 
urso peixe 
urso quati 
urso raposa 
urso cavalo 
urso 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