plp-aula-LPO-prolog

Prévia do material em texto

Paradigmas de Linguagens de 
Programação
LPO e PROLOG
2
Tópicos
 Programação em lógica:
 Lógica de primeira ordem.
 Prolog.
 Exemplos.
3
Paradigma lógico
 Idéias chave da programação em lógica:
 Descrever objetos e relações entre objetos.
 Aplicar o sistema de programação para fazer 
conclusões.
 Ex. “Maria ama João”
4
Lógica de primeira ordem
 Termo é uma expressão lógica que se 
refere a um objeto.
 São termos:
 Constante (ex: mae, maria, joao).
 Variável (ex: X).
 Função (ex: marido(maria)).
 Predicados são relações entre termos:
 ama(maria, joao).
 pai(marido(maria), joao).
5
Lógica de primeira ordem
 Sentenças atômicas (ou fórmula atômica ou 
átomo) expressam fatos
 Sentença atômica é formada por um predicado
 mae(maria)
 Sentença atômica pode ter termos complexos como 
argumentos:
 pai(marido(maria), joao)
 Sentença complexa é formada por sentenças 
atômicas ligadas via conectivos lógicos:
 ¬, ^, v, →, ↔
6
Lógica de primeira ordem
 Quantificador universal
 Para todos
∀ x rei(x)→pessoa(x)
 Quantificador existencial
 Pelo menos um
∃ x filhode(x,Maria)
7
Lógica de primeira ordem
 Cláusula de Horn:
 Uma cláusula de Horn é uma sentença na forma:
(∀x) P1(x) ^ P2(x) ^ ... ^ Pn(x) => Q(x) 
onde 
 Há 0 ou mais Pis e 0 ou 1 Q.
 Os Pis e Q são literais positivos (ou seja, 
não-negados).
 Equivalentemente: P1(x) ∨ P2(x) … ∨ Pn(x) onde os 
 Pi’s são todos atômicos e no máximo um deles é 
positivo.
 Cláusulas de Horn representam uma subconjunto 
do conjunto de sentenças representáveis em LPO.
8
Lógica de primeira ordem
 Mecanismo de inferência:
 Resolução é uma regra de inferência que permite 
que novas proposições sejam computadas a partir de 
proposições conhecidas.
 Se há variáveis nas proposições deve-se encontrar 
valores para as variáveis que permitam o casamento 
correto de termos = unificação.
 Os valores temporários atribuídos as variáveis para permitir 
unificação são chamados instanciações.
 Se ocorre uma falha no processo de instanciação de 
uma variável então ocorre retrocesso, com 
instanciação de novo valor para a variável.
9
Prolog
10
Prolog
 O nome Prolog para a linguagem foi 
escolhido por Philippe Roussel como uma 
abreviação de “PROgrammation en 
LOGique”. 
 Foi criada em meados de 1972 por Alain 
Colmerauer e Philippe Roussel, baseados 
no conceito de Robert Kowalski da 
interpretação procedimental das cláusulas 
de Horn. 
11
Prolog
 Toda linguagem de programação em 
lógica é baseada em uma lógica:
 Ex: Prolog é baseada em um sub-conjunto da 
lógica de primeira ordem.
 A Programação em Lógica faz parte do 
paradigma de programação denominado 
declarativo ou descritivo, neste,
 deve-se implementar uma descrição do 
problema e não um conjunto de instruções.
12
Prolog
 Um programa Prolog constitui-se de uma 
coleção de:
 fatos (base de dados) e 
 regras (relações lógicas).
 Esses itens descrevem o domínio de um 
determinado problema. 
 Esta descrição do problema é avaliada por um 
interpretador, o qual utilizando um mecanismo 
de inferência realiza deduções em busca de 
conclusões válidas para consultas realizadas 
pelos usuários.
13
Prolog
 Implementações diferem em sintaxe:
 Ciao Prolog
 http://www.clip.dia.fi.upm.es/Software/Ciao
 GNU Prolog 
 http://gnu-prolog.inria.fr
 YAP Prolog 
 http://www.ncc.up.pt/~vsc/Yap
 SWI Prolog 
 http://www.swi-prolog.org
14
Prolog
 Sintaxe swi-prolog:
 Para usar o SWI-Prolog, deve-se criar o arquivo 
fonte, com a terminação ‘pl’, e carregá-lo a partir do 
interpretador.
 Para iniciar o programa basta clicar duas vezes sobre 
o programa fonte, ou carregar um programa 
digitando-se o nome do arquivo fonte a ser carregado 
entre colchetes. 
 A seguir escrevem-se as consultas a serem 
executadas contra a base de conhecimento 
carregada. 
 Todas as linhas de comando digitadas na janela do 
interpretador devem terminar com um ponto (‘.’). 
 Para terminar deve-se usar o predicado halt. 
15
Prolog
 Sintaxe swi-prolog:
 Variáveis: iniciadas com letras maiúsculas ou _
 Ex: X, Lista, _Nome
 _ (sozinho) significa variável anônima, não interessa valor de 
unificação para esta variável.
 Não variáveis:
 Atômicas: 
 Constantes: joão, maria
 Inteiros: 1, 6, -3
 Números em ponto flutuante: 5.3, 2.4
 Listas: seqüência de elementos
 [a,b,c], [a | b,c]
16
Prolog
 Comandos write e read:
 write(‘Teste’). % imprime Teste na tela.
 writef(formato, argumentos) 
 %w – imprime o termo
 %d – imprime o termo ignorando seu tipo, \n é impresso como string
 %s – imprime o termo como string
 \n – cria nova linha
 writef("O valor de X é %d.\n Já Y é %d.", [1, 2]).
 read(X). %lê um valor no dispositivo de entrada e unifica (atribui) o valor com a 
variável X.
 Comentários:
 % comentário
 /* comentário */
17
Prolog
 Fatos em Prolog:
 mulher(maria).
 homem(joao).
 mae(maria, joao).
 pai(pedro, joao).
 Regras em Prolog:
 Lado esquerdo: conclusão da regra
 Lado direito: premissas da regra
 Conjunção: ;
 Disjunção: ,
pais(X, Y) :- mae(X, Y) ; pai(X,Y).
avo(X, Z) :- pais(X,Y) , pais(Y,Z).
conclusão :- premissas 
18
Prolog
 Consultas em Prolog:
?- mulher(maria).
?- homem(joao).
?- mae(maria, joao).
?- pai(pedro, joao).
?- pai(X, joao).
?- mulher(Y).
?- mulher(maria), homem(pedro).
 Respostas: yes, no ou instanciação de variáveis.
19
Prolog
 Consultas em Prolog:
 BC:
 homem(pedro).
 homem(joao).
 mulher(maria).
 mulher(ana).
 Consultas:
 homem(pedro).
 yes
 homem(carlos).
 no
 homem(X).
 X=pedro; X=joao.
20
Prolog
 As únicas verdades são aquelas que podem ser 
provadas.
 Não existe conhecimento do mundo que não 
está especificado na sua base de conhecimento.
 Qualquer consulta que não pode ser provada é 
presumida ser falsa.
?- mulher(rafaela).
no.
?- homem(fred).
no.
21
Mecanismo de inferência
 Consultas são denominadas objetivos.
 Quando um objetivo é uma proposição 
composta, cada um dos fatos é chamado um 
subobjetivo.
 Para provar que um objetivo é verdadeiro 
o mecanismo de inferência deve encontrar 
uma cadeia de regras de inferência e/ou 
fatos na BC que conecte o objetivo a um 
ou mais fatos da BC.
22
Mecanismo de inferência
 Exemplo: consulta Q
 Q é objetivo:
 Q deve estar na BC ou
 Mecanismo de inferência deve encontrar um fato P1 e uma 
seqüência de proposições P2, P3, ..., Pn tal que:
P2 :- P1
P3 :- P2
...
Q :- Pn
 O mecanismo de encontrar os Ps, quando eles 
existem, é basicamente uma comparação entre 
termos.
23
Mecanismo de inferência
 Consulta:
 homem(bob).
 Fácil de se determinar se verdadeiro ou falso, o objetivo é 
comparado com os fatos e regras na BC:
 Se o fato 
?- homem(bob). 
 Pertence a BC a prova é trivial.
 Se a BC contém
?- pai(bob).
?- homem(X) :- pai(X).
 O mecanismo de inferência deve encontrar essas duas 
proposições e unificar a variável X temporariamente com bob.
24
Mecanismo de inferência
 Há duas formas de corresponder um dado 
objetivo com um fato na BC:
 Encadeamento para frente: o mecanismo de 
inferência começa com os fatos e regras na BC e 
tenta encontrar uma seqüência de correspondências 
que levam ao objetivo.
 Funciona melhor quando o número de respostas possíveis é 
grande.
 Encadeamento para trás: o mecanismo de 
inferência começa com o objetivo e tenta encontrar 
uma seqüência de correspondências que levam a 
fatos na BC.
 Funciona bem quando há um conjunto pequeno de 
respostas possíveis. 
25
Mecanismo de inferência Exemplo:
 Consulta:
?- homem(bob).
 BC:
?- pai(bob).
?- homem(X) :- pai(X).
 Por encadeamento para frente:
 Encontra a primeira proposição “pai(bob).” e corresponde com a 
parte direita da regra “homem(X) :- pai(X).” instanciando X=bob. 
Então corresponde o lado esquerdo da regra com o objetivo.
 Por encadeamento para trás:
 Encontra primeiro a regra “homem(X) :- pai(X).” e corresponde o 
objetivo com parte esquerda da regra instanciando X=bob. Então 
corresponde lado direito da regra com proposição “pai(bob).”
26
Mecanismo de inferência
 Quando o objetivo tem mais de uma 
estrutura, a busca pela solução pode se 
dar:
 Em largura: trabalha todos os subobjetivos 
em paralelo.
 Em profundidade: encontra uma seqüência 
completa de proposições para o primeiro 
subobjetivo antes de buscar soluções para os 
demais. 
27
Mecanismo de inferência
 Quando um objetivo está sendo processado e 
um subobjetivo falha (não se consegue provar 
sua verdade), então volta-se para o subobjetivo 
anterior ao que apresentou falha e tenta 
encontrar uma nova solução para este 
subobjetivo.
 Uma nova solução para o subobjetivo resulta de 
uma nova instanciação para suas variáveis.
 Essa volta ao subobjetivo anterior é chamada 
retrocesso. 
28
Mecanismo de inferência
 Exemplo:
 Consulta:
?- homem(X), amigo(X,joana).
 BC:
 homem(joao).
 homem(jose).
 homem(manuel).
 homem(carlos).
 amigo(maria,joana).
 O mecanismo de inferência deve encontrar todos os homens 
antes de provar que o objetivo não pode ser satisfeito. 
 Se trocasse ordem dos subobjetivos seria mais eficiente 
(considerando que joana tem menos amigos na BC do que o 
número de homens).
29
Mecanismo de inferência
 Prolog:
 Resolução.
 Encadeamento para trás.
 Busca em profundidade.
 Retrocesso.
30
Aritmética
 Prolog possui definidos operadores para as quatro 
operações: +, -, *, /
 O resultado de uma operação é obtido com o operador 
is
 Exemplos:
?- X is 2+3.
X = 5.
?- X is 4-1.
X = 3.
?- X is 2*3.
X = 6.
?- X is 9/2.
X = 4.5.
31
Aritmética
 Operadores de comparação: >, <, >=, <=, =:= 
(igual), =/=(diferente)
 Note:
1+2=2+1. % verifica se dois objetos são iguais
No
1+2=:=2+1 %verifica se o resultado da operação é igual
Yes
1+A=B+2.
A=2
B=1.
32
Listas
 Listas: 
 Um dos tipos de dados mais úteis existentes 
na linguagem Prolog. 
 Uma lista é uma seqüência ordenada de uma 
quantidade qualquer de elementos. 
 Os elementos de uma lista podem ser de 
qualquer tipo, tais como, números ou átomos.
[azul, amarelo, vermelho, branco].
33
Listas
 Listas:
 Uma lista vazia é representada por [ ].
 Listas não vazias podem ser divididas em duas 
partes, são elas:
 cabeça - corresponde ao primeiro elemento da lista.
 cauda - corresponde aos elementos restantes da lista.
 É possível separar as partes de uma lista utilizando 
uma barra vertical, assim, pode-se escrever 
 Lista = [cabeça | cauda]. 
 [a | b, c] = [a, b, c].
34
Listas
 Membros da lista:
 Para se verificar se um determinado elemento 
pertence à uma lista deve-se utilizar a relação 
member(x,y) :
?- member( a , [ a , b , c ] ) .
Yes
?- member( a , [ [ a , b ] , c ] ) .
No
?- member ( [ a , b ] , [ [ a , b ] , c ] ) .
Yes
35
Exemplos
36
Exemplo 1
 Exemplo de programa simples em prolog (BF): 
gosta(josé, peixe).
gosta(josé, maria).
gosta(maria, livro).
gosta(joão, livro). 
 Apresente as seguintes questões ao 
interpretador Prolog e anote as respostas:
?-gosta(josé, peixe).
?-gosta(josé, dinheiro).
?-gosta(maria, josé).
?-gosta(maria, livro).
?-possui(joão, livro).
37
Exemplo 2
 Considere a seguinte base de conhecimento:
gosta(joão, flores).
gosta(joão, maria).
gosta(paulo, maria).
 Qual a resposta ao ser realizada a questão:
?-gosta(joão, X).
38
Exemplo 3
 Considere a seguinte base de conhecimento:
genitor(jaques, benedicte).
genitor(miriam, benedicte).
genitor(jaques, carolina).
genitor(miriam, carolina).
mulher(miriam).
mulher(benedicte).
mulher(carolina).
homem(jaques).
irmã(X, Y) :- genitor(Z, X), genitor(Z, Y), mulher(X), X =\= Y. 
 Qual a resposta ao serem realizadas as questões:
?-irmã(benedicte, carolina).
?-irmã(benedicte, Quem).
39
Exemplo 4
 Verifique o funcionamento do programa 
abaixo, que pergunta seu nome e o 
imprime. 
dialogo :- nl, nl, 
writef("Qual e' o seu nome?"),
read(Nome),
writef("Ola %t", [Nome]), nl.
40
Exercício 1
 Considere o conjunto de fatos dados com 
predicados para homem, mulher, e pais. 
Formule regras para pai, mãe, filhos, irmã, 
irmão e avós.
41
Exercício 1
% Conjunto de fatos
homem(carlos).
homem(julio).
homem(mauricio).
mulher(alice).
mulher(carolina).
mulher(luiza).
mulher(sofia).
pais(carlos,alice).
pais(sofia,alice).
pais(carlos,carolina).
pais(sofia,carolina).
pais(julio,mauricio).
pais(carolina,mauricio).
pais(julio,luiza).
pais(carolina,luiza).
Carlos Sofia
AliceCarolinaJulio
Mauricio Luiza
42
Solução 1
% Conjunto de regras
mae(X,Y) :- pais(X,Y), mulher(X).
pai(X,Y) :- pais(X,Y), homem(X).
filhos(Y,X) :- pais(X,Y).
irma(X,Y) :- pais(Z,X), pais(Z,Y), mulher(X), not(X 
= Y).
irmao(X,Y) :- pais(Z,X), pais(Z,Y), homem(X), 
not(X = Y).
avos(X,Z) :- pais(X,Y), pais(Y,Z).
43
Exercício 2
 Com relação ao programa Prolog dado a seguir 
responda:
 Quais as respostas para as seguintes consultas?
 come(urso,peixinho).
 come(raposa,coelho).
 come(guaxinim,X).
 come(X,grama).
 come(urso, X), come(X,coelho).
 presa(X), not(come(raposa,X)).
 Formule regras para as seguintes relações:
 herbívoro;
 carnívoro.
 Utilizando as regras criadas, elabore consultas para:
 Quais animais são herbívoros?
 Quais animais são carnívoros?
 Quais animais herbívoros são presas de uma raposa?
44
Exercício 2
% Base de fatos
animal(urso).
animal(peixe) .
animal(peixinho).
animal(guaxinim).
animal(raposa).
animal(coelho).
animal(veado).
animal(lince).
planta(alga).
planta(grama).
come(urso,peixe) .
come(peixe,peixinho).
come(peixinho,alga).
come(guaxinim,peixe).
come(urso,guaxinim).
come(urso,raposa).
come(raposa,coelho).
come(coelho,grama).
come(urso,veado).
come(veado,grama).
come(lince,veado).
% Base de regras
presa(X) :- come(_,X), animal(X).
45
Solução 2
 come(urso,peixinho).
 false.
 come(raposa,coelho).
 true.
 come(guaxinim,X).
 X = peixe.
 come(X,grama).
 X = coelho.
 come(urso, X), come(X,coelho).
 X = raposa.
 presa(X), not(come(raposa,X)).
 X = peixe.
46
Solução 2
% Base de regras
herbivoro(X) :- come(X,Y), planta(Y).
carnivoro(X) :- come(X,Y), animal(Y).
47
Solução 2
 Quais animais são herbívoros?
 herbivoro(X).
 X = peixinho ;
 X = coelho ;
 X = veado ;
 false.
 Quais animais são carnívoros?
 carnivoro(X).
 X = urso ;
 X = peixe ;
 X = guaxinim ;
 X = urso ;
 X = urso ;
 X = raposa ;
 X = urso ;
 X = lince.
 Quais animais herbívoros são 
presas de uma raposa?
 herbivoro(X),come(raposa,X).
 X = coelho ;
 false.
48
Bibliografia
 Russell, S & Norvig, P. Inteligência 
Artificial. Prentice Hall, 2004. 
http://aima.cs.berkeley.edu/
 Swi-prolog
http://www.swi-prolog.org
 Apostilas:
http://www.dsc.ufcg.edu.br/~logica/PROLOG/apostila
-prolog.pdf
 
 
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 42
	Slide 43
	Slide 45
	Slide 46
	Slide 48