Programação em Lógica

Prévia do material em texto

Programação em Lógica 
Prof. Marco Túlio de Oliveira Valente 
Prof. César Francisco de Moura Couto 
Prof. Pedro Felipe 
 
2 
Programação em Lógica 
§  Paradigma Imperativo: 
§  Programas: mapeamento de entradas em saídas 
§  Modelo computacional: von Neumann (variáveis, 
atribuição, comando de repetição etc)‏ 
§  Estilo procedimental (“como fazer”)‏ 
§  Paradigma Lógico: 
§  Programas especificam conhecimento a respeito de um 
problema e não uma seqüência de passos 
§  Modelo computacional: lógica matemática 
§  Estilo declarativo (“o que fazer”)‏ 
§  Programação simbólica (não-numérica)‏ 
§  Computação: verificar se uma consulta pode ser 
deduzida a partir das relações do programa. 
3 
Programação em Lógica: Exemplo 
§  Programa: 
avo(X, Y) :- pai(X, Z), pai(Z, Y). 
avo(X, Y) :- pai(X, Z), mae(Z, Y). 
pai(carlos, joao). 
pai(joao, jose). 
§  Computação: resposta a consultas 
§  avo(carlos, jose) - avo(carlos, joao) 
§  yes no 
§  avo(X,jose) - avo(manoel,carlos)‏ 
§  X= carlos no 
4 
PROLOG 
§  Origem: 
§  Universidade de Marseille e Edinburgh (década 70) ‏ 
§  Objetivo: ferramenta para experimentos em IA e para 
definição de gramáticas. 
§  Valores: 
§  Constantes. Exemplos: maria, 125 
§  Estruturas (tuplas rotuladas). Exemplos: ponto (5,6), 
data(01,01,2000) ‏ 
§  Listas. Exemplos: [1,2,3], [maria, jose, joao] 
§  Variáveis (identificadores que iniciam por uma letra 
maiúscula). Exemplos: X, Y, Estudante 
5 
Cláusulas de Horn 
§  Programa: uma coleção de Cláusulas de Horn 
§  Cláusulas de Horn: 
§  Subconjunto das cláusulas da lógica de predicados 
§  Forma geral: B :- A1, A2, ..., An. 
 onde cada Ai é uma relação da forma Ri (.....)‏ 
§  Interpretação: se as condições A1, A2, ... e An forem 
verdadeiras, então a conclusão B é verdadeira 
§  Se fosse procedimental: if condições then conclusão 
§  Se n = 0, a cláusula é chamada de fato 
§  Se n > 0, a cláusula é chamada de regra 
§  Toda cláusula termina com um “.” 
 
6 
Exemplo 1 
estrela(sol). 
estrela(sirius). 
orbita(venus, sol). 
orbita(terra, sol). 
orbita(marte, sol). 
orbita(lua, terra). 
orbita(phobos, marte). 
orbita(deimos, marte). 
planeta(B) :- orbita(B, sol). 
satélite(B) :- orbita(B, P), planeta(P). 
Consultas: 
orbita(venus, sol) ? 
Yes 
orbita(B, marte) ? 
B= phobos, B = deimos 
orbita(B, venus) ? 
No 
planeta(mercúrio) ? 
No 
planeta(X) ? 
X = venus, X = terra, X = marte 
satélite(X) ? 
X = lua, X = phobos, 
X = deimos 
 
7 
Exemplo 2 
§  Programa: 
gosta(maria, peixe). 
gosta(pedro, vinho). 
gosta(maria, vinho). 
gosta(pedro, maria). 
§  Consultas: 
§  Quem gosta de peixe ? 
gosta (X, peixe) ‏ 
§  Pedro e Maria se gostam ? 
gosta (pedro, maria), gosta (maria, pedro)‏ 
§  Existe algo que Pedro e Maria (ambos) gostem ? 
gosta (pedro, X), gosta (maria, X)‏ 
8 
Unificação 
§  Algoritmo utilizado em Prolog para determinar se existe 
uma maneira de instanciar as variáveis de dois predicados 
de modo a torná-los iguais. 
§  Exemplos: 
§  p (X, Y) e q (X, Y) ⇒ No 
§  p (X, Y) e p (joao, jose) ⇒ X= joao; Y=jose 
§  p (X, Y) e p (joao, Z) ⇒ X= joao; Y=Z 
§  p (X, X) e p (1, 1) ⇒ X = 1 
§  p (X, X) e p (1, W) ⇒ X = 1; W = 1 
§  p (X, X) e p (1, 2) ⇒ No 
§  p (X, X, 2) e p (1, W, W) ⇒ No 
§  p (G, jose) e p (X, Y) ⇒ X = G, Y = jose 
9 
Algoritmo de Resolução 
§  Busca em profundidade em uma árvore de pesquisa 
§  Resolução de um objetivo: 
§  Lista de cláusulas é pesquisada de cima para baixo 
§  Se unificação com lado esquerdo de uma cláusula for 
bem sucedida então: 
§  Passa-se a tentar resolver os sub-objetivos do lado 
direito desta cláusula (da esquerda para a direita)‏ 
§  Resolução inclui retrocesso (backtracking) para pesquisa 
de outras respostas (resultantes de unificações 
alternativas)‏ 
§  Resolução falha se todas as alternativas forem exploradas 
sem sucesso. 
§  Resolução é sujeita à ordem em que as cláusulas foram 
escritas 
10 
Resolução: Exemplo 1 
§  Programa: 
homem(francisco). 
mae(joao, roberta). 
pai(joao, paulo). 
mae(francisco, roberta). 
pai(francisco, paulo). 
pais(X, M, P) :- mae(X, M), pai(X, P). 
irmao(X, Y) :- homem(Y), pais(X, M, P), pais(Y,M, P). 
§  Consulta: 
?- irmao (joao, francisco)‏ 
11 
Resolução: Exemplo 1 
irmao(joao,francisco)
homem(francisco) pais(joao,M,P) pais(francisco,M,P)
mae(joao,M) pai(joao,P)
mae(joao,roberta) pai(joao,paulo)
mae(francisco,roberta) pai(francisco,paulo)
X= joao, Y= francisco
M= roberta P= paulo
12 
Resolução: Exemplo 2 
§  Programa: 
gosta(maria, peixe). gosta(maria, vinho). 
gosta(pedro, vinho). gosta(pedro, maria). 
§  Consulta: gosta (maria, X), gosta(pedro,X)‏ 
 
gosta(maria,X),gosta(pedro,X)
gosta(maria,peixe)
X=peixe
gosta(pedro,peixe)
falha (backtracking)
gosta(maria,X),gosta(pedro,X)
gosta(maria,vinho)
X=vinho
gosta(pedro,vinho)
13 
Cláusulas Recursivas 
§  Exemplo: 
pai(carlos,madalena). 
mae(madalena,manoel). 
pai(manoel,felipe). 
pais(X,Y) :- pai(X,Y). 
pais(X,Y) :- mae(X,Y). 
descendente(X,Y):- pais(Y,X). % caso base da recursao 
descendente(X,Y):- % passo recursivo 
 pais(Z,X), descendente(Z,Y). 
 
 
14 
Variáveis Anônimas 
§  Variável Anônima (“_”): variável cujo valor não é importante 
§  Exemplo: Caso pretenda-se saber apenas se Paulo tem 
filhos 
?- pai(paulo,_)‏ 
 yes 
?- pai(paulo,X)‏ 
 X=pedro; X=maria; X=simao 
 
15 
Listas 
§  Notação: 
[1, 2, 3, 4] 
[1, [2 , 3], 4] % lista com elementos lista 
[] % lista vazia 
 [ H | T ] % lista com cabeça H e cauda T 
§  Exemplos de unificação envolvendo listas: 
?- [X | Y] = [a, b, c]. ⇒ X=a Y=[b, c] 
?- [X | [Y | Z]] = [a, b, c, d]. ⇒ X=a; Y=b; Z=[c, d] 
?- [X | Y ] = [a] ⇒ X= a; Y= [] 
?- [X,Y | Z] = [a, b, c,d] ⇒ X= a; Y=b; Z= [c,d] 
16 
Listas: Exemplos 
§  Exemplo 1: Verificar se elemento pertence a uma lista 
pertence(X, [ X | _ ] ). 
pertence(X, [ _ | L ] ) :- pertence(X, L). 
§  Exemplo 2: Concatenação de duas listas 
concatena( [], L, L). 
concatena( [ X | L1 ], L2, [ X | L3 ]) :- concatena (L1, L2, 
L3). 
§  Exemplo 3: Verificar se duas listas são iguais 
 igual([],[]). 
 igual([ X | L1], [X | L2] ) :- igual(L1, L2). 
§  Exemplo 4: Remoção de elemento de uma lista 
 remove (X, [X | L], L). 
 remove (X, [ Y | L1 ], [ Y | L2 ] ) :- remove (X, L1, L2). 
17 
Expressões Aritméticas 
§  Exemplo 1: Operador “is” 
densidade(X,Y) :- populacao(X,P), area(X,A), Y is P/A. 
§  Exemplo 2: MDC (Algoritmo de Euclides)‏ 
mdc(X,X,X). 
mdc(X,Y,Z):- X > Y, W is X-Y, mdc(W,Y,Z). 
mdc(X,Y,Z):- Y > X, W is Y-X, mdc(X,W,Z). 
§  Exemplo 3: Fatorial 
fatorial(0, 1). 
fatorial(X, Y) :- X1 is X-1, fatorial(X1, Y1), Y is X*Y1. 
§  Exemplo 4: Soma dos elementos de uma lista 
soma ([],0). 
soma ([X | L], S) :- soma (L, S1), S is S1+X. 
18 
 
Gramática da Língua Inglesa 
§  A gramática abaixo gera um subconjunto de palavras da 
língua inglesa 
 <sentence> ::= <noun phrase> <verb phrase> . 
 <noun phrase> ::= <determiner> <noun> | <determiner> <adjective> <noun> 
 <verb phrase> ::= <verb> | <verb> <noun phrase> 
 <determiner> ::= a | the 
 <noun> ::= boy | cat 
 <adjective> ::= big | lazy 
 <verb> ::= saw | ate 
19 
 
Parser em Prolog 
sentence(S,[]):- nounphrase(S,S1), verbphrase(S1,S2), dot(S2, []). 
 
nounphrase(NP,X):- determiner(NP,S1), noun(S1,X). 
nounphrase(NP,X):- determiner(NP,S1), adjective(S1,S2), noun(S2,X). 
verbphrase(VP,X):-verb(VP,S1), nounphrase(S1,X). 
 
dot(['.'|X], X). 
 
noun([boy|X],X). 
noun([cat|X],X). 
 
verb([ate|X],X). 
verb([saw|X],X). 
 
adjective([big|X],X). 
adjective([lazy|X],X). 
 
determiner([the|X],X). 
determiner([a|X],X). 
20 
 
Regras da gramática em Prolog 
§  Usando o operador de definição de gramática, --> 
sentence --> nounphrase, verbphrase, ['.']. 
nounphrase --> determiner, noun. 
nounphrase --> determiner, adjective, noun. 
verbphrase --> verb, nounphrase. 
noun --> [boy]. 
noun --> [cat]. 
verb --> [ate]. 
verb --> [saw]. 
adjective -->[big]. 
adjective -->[lazy]. 
determiner --> [a]. 
determiner --> [the].