Programação em Lógica - paginas.fe.up.ptpaginas.fe.up.pt/~eol/LP/1011/documents/Teoricas/PL1.pdf · Programação em Lógica • História e Fundações da Programação em Lógica

1Eugénio Oliveira

MIEIC 2010/2011 1

A partir do livro “The Art of Prolog”, L.Sterling e E .Shapiro inicialmente por Gabriel David

Acrescentado e modificado por

Eugénio Oliveira

Mestrado Integrado em ENGENHARIA INFORMÁTICA da Faculdade de Engenharia da

Universidade do Porto

Programação em Lógica• História e Fundações da Programação em Lógica

• Conceitos da Programação em Lógica

• A Linguagem Prolog

• Técnicas Avançadas de Programação em Prolog

• Metodologias de Programação em Lógica

• Programação com Restrições

Prolog - 2

História e Fundações da Programação em Lógica

� Lógica Computacional

� Frege e o “Begriffsschrift”• Cálculo de predicados ; Conceitos como funções sempre verdadeiras

•As críticas de H. Poincaré (matemático e físico)• Mat. não é um ramo da Lógica e inclui a intuição

• Provar: Informalidade Versus Formalidade

• B. Russel & A.Whitehead: “Principia Mathematica”• inspirado no trabalho de Frege (resolvendo paradoxo)

• derivar todas as verdades matemáticas dos axiomase regras de inferência em lógica simbólica

MIEIC 2010/2011

2Eugénio Oliveira

Prolog - 3

� Derivabilidade� Regras de Inferência:

A� B, ~B~A


A� B, AB

• Modus PonensMP:

• Modus TolensMT:

A Λ BA,B

A, BA Λ B

• And Elimination:AE:

• And Inclusion:AI:

MIEIC 2010/2011

Prolog - 4

• Instanciação Universal

A(t)

x A(x)V


V� Exemplo: x, ∃ y : Gosta (x,y)

Verdade: ∃y, Gosta(credor(z), y)

Não se pode inferir: ∃y, Gosta (credor(y),y)

t é livre para a variável x se e só se x não ocorre no âmbito de um quantificador de qualquer variável em t

MIEIC 2010/2011

3Eugénio Oliveira

Prolog - 5

� Inferência:� Um procedimento de inferência é uma estratégia para a

escolha das derivações possíveisem cada estado.

• Um exemplo são as Cadeias de Markov

• Consideramos aqui só a inferência incremental


� Implicação Lógica:• Um conjunto de Fórmulas CF implica logicamente uma

Fórmula F (CF F), se e só se, qualquer interpretação que satisfaça CF também satisfaz F (Godel 1930)

MIEIC 2010/2011

Prolog - 6

• Uma Prova de F a partir de CF é uma sequência finita na qual F é o último elemento, e qualquer outro elemento ou pertence a CF, ou é um axioma lógico, ou o resultado da aplicação de MP a fórmulas anteriores da sequência.

• Podemos dizer que Prova é a Derivaçãoconsiderando os axiomas lógicos e só a aplicação de MP


� Provabilidade:• Provar versus Testar

• Teorema: Se (CF F), então há uma Prova finita de F partindo de CF

MIEIC 2010/2011

4Eugénio Oliveira

Prolog - 7

� Provabilidade:• O conceito de Provabilidade é importante porque sugere

como automatizar a determinação da Implicação Lógica

• Quando de CF se prova F ou ~F, a implicação Lógica é Decidível.

• Mas pode acontecer que não o seja.

CF F CF F


MIEIC 2010/2011

Prolog - 8

Lógica e Computação

� Lógica� linguagem precisa para a expressãodos objectivos, conhecimento e

“assunções” (suposições)

� fundamento para a dedução de consequências a partir de premissas

� limitada apenas pela capacidade humana de raciocínio

� Computação� também requer uma formulação precisa de objectivos e “assunções”

� dificuldades iniciais de construção: desenho da linguagem de instrução das máquinas dominada pelo hardware

� seguiram-se linguagens cada vez mais estruturadas e abstractas, mas essencialmente baseadas na arquitectura de von Neumann

MIEIC 2010/2011

5Eugénio Oliveira

Prolog - 9

Lógica e Computação

� Suporte Lógico-Computacional da Informação:

O caminho:

� Cálculo de Predicados

� Formas Normal Prenex

� Princípio da Resolução

� Cláusulas de Horn

� Linguagem Prolog

MIEIC 2010/2011

Prolog - 10

Lógica

� Lógica Proposicional

� Proposições

� Conectivas Lógicas: Λ ∪� ↔ ∼↔ ∼↔ ∼↔ ∼

� A � B significa ~A ∪ B

� A ↔↔↔↔ B significa (A Λ B) ∪ (~A Λ ~B)

� Expressão A1:(P Λ Q) � (R ↔↔↔↔ (~S))Se {P,Q,R,S} {T,F,T,T} então A1= T

MIEIC 2010/2011

6Eugénio Oliveira

Prolog - 11

Lógica

� Predicados expressam Proposições sobre Objectos• Exemplo:

– Gosta(Rui, Maria)– Verbo(X,V(X))

� Variáveis: são introduzidas por Quantificadores:• ∃∃∃∃ V

� Lógica de Predicados:� Objectos representados por Termos

• Termos:– Constantes– Variáveis– Termos compostos:

• Símbolo Funcional• Argumentos (Termos)

MIEIC 2010/2011

Prolog - 12

Fórmulas Lógicas

� Eliminação de Implicações:• X (Humano(X) � Ser(X)) X (~Humano(X) ∪ Ser(X))

� Mover as Negações(das fórmulas não atómicas)• ~(Desumano(Rui) Λ Ser(Rui)) ~Desumano(Rui) ∪ ~Ser(Rui)• ~( X Pessoa(X)) ∃ X ~Pessoa(X)• ~( ∃ X Marciano(X)) X ~Marciano(X)

� Forma Normal Prenex� Fórmulas Lógicas na forma:

• (Q1 X1) (Q2 X2) … (Qn Xn) (M)

• Qi Xi são as variáveis quantificadas formando o Prefixo• M é a Matriz, contendo nenhum quantificador

V

V

V

V

MIEIC 2010/2011

7Eugénio Oliveira

Prolog - 13

Fórmulas Lógicas

• Mover os quantificadores:

∀x F(x) ∧ ∀x G(x) ≡ ∀x ( F(x) ∧ G(x))

∃ x F(x) ∪ ∃ x G(x) ≡ ∃ x (F(x) ∪ G(x))∀x F(x) ∪ ∀x G(x) ≡/ ∀x ( F(x) ∪ G(x))∃ x F(x) ∧ ∃ x G(x) ≡/ ∃ x (F(x) ∧ G(x))

• Transformação em Fórmula Normal Prenex:

• Exemplo: ∀x P(x) ⇒ ∃ x Q(x) ≡ ~ ∀x P(x) ∪ ∃ x Q(x) ≡∃ x ~P(x) ∪ ∃ x Q(x) ≡ ∃ x (~P(x) ∪ Q(x))

onde ∃ x é o Prefixo e (~P(x) ∪ Q(x)) a Matriz da FNP

MIEIC 2010/2011

Prolog - 14

Paradigma

� Exemplo - conhecimento (dois axiomas):1 humano(Platão)2 ∀x humano(X) → mortal(X)

� problemamortal(Platão)?

� Sim! É uma consequência lógicados axiomas� eliminação do universal e modus ponens

� Programação em Lógica� derivada de um modelo abstracto, natural para o raciocínio humano,

independente de máquinas concretas� exprimir o conhecimentorelevante e as “assunções” como axiomas

lógicos; formalizar o problema como uma expressãológica a ser provada a partir dos axiomas

MIEIC 2010/2011

8Eugénio Oliveira

Prolog - 15

Automatização

� Pré-processamentodas Fórmulas Lógicas:

� Putman, Davis (USA) e Pravitz (Suécia)� Uma Fórmula Lógica de 1ª Ordem pode ser transformada na Forma

Normal Prenex� A Matriz da FNP pode transformar-se na Forma Normal Conjuntiva� Os Quantificadores Existênciais do Prefixo são eliminados pelas

Fórmulas de Skolem

� Processo de Automatização da ProvaLógica:� Falsificação das Fórmulas: Herbrandt (1930)

� Programação em Computador da prova da inconsistência da negação de uma Fórmula Lógica:

Gilmore (1960)

MIEIC 2010/2011

Prolog - 16

“Skolemização”

� Se nenhumQuantificador Universal (∀) aparece antes de Qi (∃∃∃∃), escolhe-se uma Constante C não usada e substitui-se todos as Xi por C eliminando-seQi (quatificador ∃∃∃∃ ).

� Se existirem na fórmula m Quantificadores Universais (∀) antes de Qi, substitui-se Xi por uma Função de m argumentos, f(X1…Xm) eliminando-seQi

� Resulta assim uma Forma Standard de “Skolem”

� Transformações de Skolem:

� Seja a Fórmula na FNP: Q1X1 … QnXnM (Matriz naF.N.Conjuntiva)

� Seja Qi um Quantificador Existêncial (∃∃∃∃ ): 1=< i =< n

MIEIC 2010/2011

9Eugénio Oliveira

Prolog - 17

“Skolemização”

• Exemplo e contra-exemplo:• ∃∃∃∃x Mulher(X) ∧ Mãe(X,eva)

Mulher(C) ∧ Mãe(C,eva) “existe C mãe de eva”• Mas:∀X (Humano(X) ⇒ ∃∃∃∃Y Mãe(Y,X))∀X (Humano(X) ⇒ Mãe(C,X)) ERRO!!∀X (Humano(X) ⇒ Mãe(f(X) ,X))

• As fórmulas agora só contêm Quantificadores Universaise,portanto, não traduzindo qualquer informação podem-se eliminar.

• Passar à Forma Normal Conjuntiva :•Usam-se as Propriedades distributivas :

(A∧B)∪ C ≡ (A ∪ C ) ∧ (B∪ C )A ∪ (B ∧ C ) ≡ (A ∪ B ) ∧ (A∪ C )

MIEIC 2010/2011

Prolog - 18

Forma Clausal

• Na Forma Normal Conjuntiva , a ordem pela qual são escritos os literais é irrelevante, logo: A ∧ B ∧ C ∧ D é uma colecção de Cláusulas:

{ A, B, C, D }

• FORMA CLAUSAL: •Colecçãode Cláusulas formadas, cada uma delas, por dijunções de literais.

• Separando em cada cláusula os literais negados e os não negados, (a ordem é indiferente), obtêm-se, outra forma de escrever uma cláusula•por exemplo:

(~A2 ∪ ~B2) ∪(A1 ∪ B1 ∪ C1) ~(A2 ∧ B2) ∪(A1 ∪ B1 ∪ C1) (A2 ∧ B2) ⇒ (A1 ∪ B1 ∪ C1)

MIEIC 2010/2011

10Eugénio Oliveira

Prolog - 19

Forma Clausal

• Ex: Se todos os alunos respeitam alguém, então esse alguém é professor∀x (∀y (Aluno(y) ⇒ Respeita(y,x)) ⇒Prof(x) )∀x (∀y (~Aluno(y) ∪ Respeita(y,x)) ⇒Prof(x) )∀x (~∀y (~Aluno(y) ∪ Respeita(y,x)) ∪ Prof(x) )

•Forma Clausal:Cláusula C1: ( Aluno(f(x)) ∪ Prof(x)) Cláusula C2: (~Respeita(f(x),x) ∪ Prof(x))ou ainda: Respeita(f(x),x) ⇒Prof(x)

∀x (∃y ~ (~Aluno(y) ∪ Respeita(y,x)) ∪ Prof(x) )∀x (∃y (Aluno(y) ∧ ~Respeita(y,x)) ∪ Prof(x)∀x ( (Aluno(f(x)) ∧ ~Respeita(f(x),x)) ∪ Prof(x) )( Aluno(f(x)) ∪ Prof(x)) ∧ (~Respeita(f(x),x) ∪ Prof(x))

MIEIC 2010/2011

Prolog - 20

Forma Clausal

� Cláusula:

� Expressão lógica na forma:

� B1 ∪ B2 ∪… ∪ Bn � A1 Λ A2 Λ … Λ Am

� Onde Ai e Bi são Fórmulas atómicas e as Variáveis são consideradas quantificadas Universalmente

� n, m >0

MIEIC 2010/2011

11Eugénio Oliveira

Prolog - 21

Demonstração Automática

� Demonstração Automática de Teoremas

� AXIOMAS TEOREMA

� CLÁUSULAS CONSEQUÊNCIA LÓGICA

� Princípio da Resolução(Robinson) para a Lógica Proposicional:

• Para quaisquer duas Cláusulas C1 e C2, havendo um Literal L1 em C1 complementarde um Literal L2 em C2, então eliminam-se ambos e constrói-se a Cláusula resolventecom a Dijunção dos restantes Literais.

MIEIC 2010/2011

Prolog - 22

Demonstração Automática� Exemplo:

C1: P ∪ R� Resolvente: R ∪ Q

C2: ~P ∪ Q� A resolvente é a consequênciaLógica

{

{

{

� Exemplo:C1: chove

(resolvente) � cláusulavaziaou contradiçãoC2: ~chove

� Exemplo:C1: ~P ∪ QC2: ~Q (resolvente)� ~PC3: P �� Cláusula vazia ou contradição

� Suposições�� Conclusão ou ~Conclusãoinconsistentecom Suposições� Resolver Problemas≡≡≡≡ Demonstrar Teoremas≡ ≡ ≡ ≡ Executar Programas

MIEIC 2010/2011

12Eugénio Oliveira

Prolog - 23

Exemplo

C6: ~Frio (quero provar que está Frio)

~Primavera ∪ ~Chove ∪ Frio ~Frio

~Primavera ∪ ~Chove Primavera

~Chove ~Mau_tempo ∪ Chove

~Mau_tempo Mau_tempo

inconsistência��

C1:Primavera

C2: ~Primavera ∪ ~Chove∪ Frio

C3: ~Inverno∪ Chove

C4: ~Mau_tempo∪ Chove

C5: Mau_tempo

Frio é a Consequência Lógica das Cláusulas C1 a C5

MIEIC 2010/2011

Prolog - 24

Fundamento do Prolog

� 1965 Robinson: Princípio da Resolução� base matemática das provas desenvolvida no contexto dos

sistemas de demonstração de teoremas

� Cláusula de Horn� A �� B1 Λ B2 Λ ... Λ Bn

� Leitura declarativa� A é verdadeiro se todos os Bi's forem verdadeiros

� Conhecimento: colecção de cláusulas de Horn

� Sistema de inferência� prova construtiva de um objectivo (A) a partir dos axiomas

� só baseada no algoritmo daunificação e no princípio daresolução

MIEIC 2010/2011

13Eugénio Oliveira

Prolog - 25

Origens do Prolog

� Anos70 Kowalski: leitura procedimentalda cláusula de Horn:� para resolver/executar A, resolver/executar B1 e B2 e ... Bn

� A é visto como a cabeça de um procedimento e os Bi's o corpo

� Anos70 Colmerauer(Marselha): implementação� sistema demonstrador de teoremas chamado Prolog

(Programmation en Logique)

� 1978/79 Edinburgo� primeiras implementações eficientes de Prolog;

estabelecimento de um estilo

� 1981 projecto japonêsda Quinta Geração de Computadores� construir máquinas para executar directamente Prolog

MIEIC 2010/2011

Prolog - 26

Programa em Lógica

� Programa em Lógica- colecção de axiomas ou regras (cláusulas de Horn) que definem relações entre objectos

� Computação- dedução de consequências do programa

� Significado do programa- conjunto de consequências definido pelo programa

� Arte da Programação em Lógica- construirprogramas concisos e elegantes, que tenham o significado pretendido

MIEIC 2010/2011

14Eugénio Oliveira

Prolog - 27

A interpretação é convencional, mas essencial para a compreensão da formulação do problema.

Factos

Notas:

� nada se diz sobre o recíproco

� nomes de predicados e de objectos começam com minúscula (átomos)

� predicados primeiro, objectos em lista ordenada

� ponto final

� relação ou predicado gosta� objectos ou indivíduos joao, maria� facto gosta( joao, maria ).� interpretação O João gosta da Maria.

MIEIC 2010/2011

Prolog - 28

soma( 0, 0, 0 ).

soma( 0, 1, 1 ).

soma( 0, 2, 2 );

soma( 1, 0 ,1 ).

soma( 1, 1, 2 ).

Família

Soma

Um conjunto de factos é um programa� descreve umasituação.

Programas simples

pai( terach, abraao ). homem( terach ).pai( terach, nachor ). homem( abraao ).pai( terach, haran ). homem( nachor ).pai( abraao, isaac ). homem( haran ).pai( haran, lot ). homem( isaac ).pai( haran, milcah ). homem( lot ).pai( isaac, jacob ). homem( jacob ).pai( haran, yiscah ). mulher( sara ).

mulher( milcah ).mae( sara, isaac ). mulher( yiscah ).

MIEIC 2010/2011

15Eugénio Oliveira

Prolog - 29

Um facto G.afirma que o objectivo G é verdadeiro.

Uma pergunta G?interroga se o objectivo é verdadeiro.

Perguntas

� pergunta ou objectivo (goal)� sintacticamente semelhante a um facto

gosta( joao, maria )? ou?- gosta( joao, maria )

� sistema responde 'yes' se existir no programa o factogosta( joao, maria ).

MIEIC 2010/2011

Prolog - 30

� Um objectivo é verdadeiro relativamente a um programa, se for uma sua consequência lógica.

� O resultado de uma pergunta é uma consequência lógica de um facto idêntico.

� Operacionalmente: procurar um facto no programa que seja idêntico à pergunta.

Regra da identidade: de G. deduzir G

Regra de dedução 1: identidade

pai( abraao, isaac ).pai( haran, lot ).…mulher( sara ).mulher( milcah ).mulher( yiscah ).

mulher(abraao)

americano( obama )

programapai( abraao, isaac )conclusão

MIEIC 2010/2011

16Eugénio Oliveira

Prolog - 31

Respostas negativas

� Resposta 'no' - significa que o objectivo não é consequência lógica do programa, mas nada diz sobre a sua veracidade.

� possível interpretação de 'no': • tanto quanto sei, não, i.e,

• não consegui provar o objectivo com os factos de que disponho.

Ex: (programa da Família)pai( abraao, isaac )?

yesmulher(abraao )?

noamericano( obama )?

no

MIEIC 2010/2011

Prolog - 32

Realidade Programa

A se B.C se A.B.

Ι

Ι

computação

ConclusõesA, B, C

Programas para quê?

MIEIC 2010/2011

17Eugénio Oliveira

Prolog - 33

Interpretação

� indivíduos — constantes e termos

� afirmações— factos e objectivos� relacionam indivíduos; são verdadeiras ou falsas

� Se a interpretação I dos factos representados no programa for correcta, então todas as conclusõescomputadas a partir do programa correspondem, nessa interpretação, a afirmações também verdadeiras� mesmo que não directamente observáveis - daí o carácter

“ inteligente”destas

MIEIC 2010/2011

Prolog - 34

� Ex: de quem é que Abraão é pai?� fazer perguntas com os vários indivíduos até obter uma

resposta 'yes'• pai( abraao, lot )? no• pai( abraao, milcah )? no• pai( abraao, isaac )? yes

� ou perguntar• pai( abraao, X )?

� significando:• existe algum indivíduo X que faça com que o objectivo seja uma

consequência lógica do programa?

� resultado:• X = isaac

Variável - representa um indivíduo (uma entidade) nãoespecificado(a) [não uma posição de memória].

Uma variável resume muitas perguntas.

pergunta existencialvariáveis nas perguntas são implicitamente existenciais

Nota: começa com maiúscula.

Variável lógica

MIEIC 2010/2011

18Eugénio Oliveira

Prolog - 35

1) Constantes e variáveis são termos2) Termos compostos são termos:

functor e lista de argumentos

nome/aridade termosnome( joao, costa ) nome/2

lista( a, lista( b, nil ) ) lista/2

s(0) s/1

a(X,5)

arv( arv(nil,3,nil), 5, R) arv/3

• termos base (ground)-sem variáveis

• termos não base (nonground)- com variáveis- estruturas incompletas

5

3 R

nil nil

Termos• são a única estrutura de dados• interpretação de um termo é um indivíduo (uma entidade)• um predicado é V ou F (não confundir com termo)

Termos

MIEIC 2010/2011

Prolog - 36

Substituição - conjunto finito de pares Xi=tiX i variável, ti termo,

X i ≠ X j para todo o i ≠ j e

X i não ocorre em tj para todo i, j

Substituição

� Ex: θ = { X = isaac } e G= pai( abraao, X )

� aplicação da substituição θ aos argumentos de G

� Gθ = pai( abraao, X )θ = pai( abraao, isaac ).� A é instância de B, se há uma substituição θ tal que A=Bθ� não existe a noção de atribuição

MIEIC 2010/2011

19Eugénio Oliveira

Prolog - 37

Exemplos de substituição

� Ex: possui( joao, livro( lusiadas, autor( luis, camoes) ) ).� livro( lusiadas, autor( luis, camoes) ) é um termo cuja

interpretação dá um indivíduo, um exemplar dos Lusíadas

� possui( joao, X )?

� X= livro( lusiadas, autor( luis, camoes ) )

� possui( Nome, livro( Obra, autor( _, camoes ) ) )?� Quem possui alguma obra do Camões ?� Nome= joao, Obra= lusiadas

� o símbolo_ é umavariável anónimae portanto nãoaparece na resposta.

� as respostas dadas pelo Prolog são substituições.

MIEIC 2010/2011

Prolog - 38

Generalização- uma pergunta existencial P é uma consequêncialógica de uma sua instância, Pθ, para qualquer substituiçãoθ.

Regra de dedução 2: generalização

� de pai( abraao, isaac ) concluir pai( abraao, X ), pois existe um X (X= isaac) que torna este verdadeiro

� operacionalmente, para responder a uma pergunta existencial com variáveis, procurarum facto que seja uma instânciadessa pergunta; a resposta é essa instância, representada pela substituição respectiva

pai( abraao, X )

pai( abraao, isaac ).programa

conclusão

X= isaac

MIEIC 2010/2011

20Eugénio Oliveira

Prolog - 39

Soluções múltiplas

� Podem existir soluções múltiplas: quais as soluções de soma( A, B, 4 )?� {A=0, B=4}, {A=1, B=3}, {A=2, B=2},

� {A=3, B=1}, {A=4, B=0}

� Quais as soluções de soma( A, A, 4 )?� a substituição de A na pergunta é feita só de uma vez,

pelo que o significado é

� qual o número que somado consigo próprio dá 4?, {A=2}

MIEIC 2010/2011

Prolog - 40

Instanciação- de um factouniversalmente quantificado P, deduzir umasuainstânciaPθ, para qualquer substituiçãoθ.

Regra de dedução 3: instanciação

� Suponha-se que todos os elementos da Família gostam de maná.� gosta( abraao, mana ).� gosta( terach, mana ). � •••

� Em vez disto, pode-se usar um facto universal.� gosta( X, mana ).

� A variável resume muitos factos.

� As variáveis nos factos estão universalmente quantificadas.

MIEIC 2010/2011

21Eugénio Oliveira

Prolog - 41

Exemplos de instanciação

� Operacionalmente:� pergunta semvariáveis — encontrar um factode que a pergunta

seja instância

� Ex: incluir o facto soma( 0, X, X ) no programa significa que o 0 é o elemento neutro da adição. Permite responder “yes” à

pergunta soma(0,2,2).

gosta( abraao, mana )

gosta( X, mana).programa

conclusão

MIEIC 2010/2011

Prolog - 42

Combinação de regras

soma( 0, 3, 3 )

soma( 0, X, X ).programa

instância comum

soma( 0, 3, Y )conclusão

Y= 3

� Ex: soma( 0, 3, Y ), a partir do facto soma( 0, X, X ) e dainstância comum soma( 0, 3, 3), responde {Y=3} (substituiçõessem variáveis da pergunta, não aparecem na resposta)

� Operacionalmente:� perguntacom variáveis — procurar umainstância comumà

pergunta e ao facto, o que envolve dois passos: instanciação (do facto para a instância) e generalização (da instância para a pergunta). C é instância comum a A e Bse C=A θ1 =B θ2

MIEIC 2010/2011

22Eugénio Oliveira

Prolog - 43

Perguntas conjuntivas

� pergunta conjuntiva é aquela que possui mais do que um objectivo

• pai( abraao, isaac ), mae( sara, isaac )?

� vírgula = conjunção

� resposta a perguntas sem variáveis é a conjunção das respostas a cada objectivo

� perguntas com variáveis partilhadas por váriosobjectivos

• pai( haran, X ), homem (X )?• Haran tem algum filho homem?

� o alcance da variável é a pergunta conjuntiva

� também estas variáveis são existenciais

MIEIC 2010/2011

Prolog - 44

Variáveis partilhadas� Operacionalmente, para resolver A1, A2, ..., An?

encontrar uma substituição θθθθ tal que A1 θ, A2 θ, ... An θ sejam instâncias sem variáveis de factos no programa.� solução de pai( haran, X ), homem (X )? { X=lot}� Uso: restrição — de entre os filhos de Haran escolher só os

homens. Ou escolher dos homens os que são filhos de Haran.

� Outro exemplo diferente de uso de variáveis partilhadas:• Ex: pai( terach, X), pai( X, Y )?

� - escolhe os filhos de Terach que por sua vez têm filhos, i.e., netos. Ou de todos os pais aqueles que são filhos de Terach.

� Há várias soluções.{X=abraão, Y=isaac} e {X=haran, Y=lot}

MIEIC 2010/2011

23Eugénio Oliveira

Prolog - 45

Regra - define uma nova relaçãoem termos das relações existentes.

Regras

� dá um nome a uma pergunta conjuntiva; transforma-a numa pergunta simples

• avo( X, Y ) ← pai( X, Z ), pai( Z, Y ),

� forma geral das cláusulas de Horn• (cabeça) (corpo)• facto A ←• regra A ← B1, B2, ... Bn

• pergunta ← B

� leituraprocedimental� a pergunta ← avo( terach, Y )� é traduzida por ← pai( terach, Z ), pai( Z, Y )� e reduzida a ← pai( haran, Y ) {Z=haran}� para concluir ← { Z=haran, Y=lot}

MIEIC 2010/2011

Prolog - 46

Leitura declarativa


� regra vista como um axioma lógico� ← denota implicação lógica

� lê-se: para todo o X, Y e Z, X é avôde Y se X for o paide Z e Z o paide Y

� as variáveis nas regras (caso particular: factos) são quantificadas universalmente

� leitura alternativa: para todo o X e Y, X é avô de Y se existirum Z tal que X seja o pai de Z e Z o pai de Y

MIEIC 2010/2011

24Eugénio Oliveira

Prolog - 47

Equivalências

� ∀X ∀Y ∀Z avo( X, Y) ←←←← pai( X, Z ), pai( Z, Y )

� ∀X ∀Y ∀Z avo( X, Y) ∨∨∨∨ ~[ pai( X, Z ), pai( Z, Y )]

� ∀X ∀Y avo( X, Y) ∨ ∀∀∀∀Z ~[ pai( X, Z ), pai( Z, Y )]

� ∀X ∀Y avo( X, Y) ∨ ~∃∃∃∃Z: [ pai( X, Z ), pai( Z, Y )]

� ∀X ∀Y avo( X, Y) ←←←← ∃Z: [ pai( X, Z ), pai( Z, Y )]

� só as variáveis dos objectivos da pergunta interessam para a expressão da substituição

� variáveis nas perguntas (cláusulas só com corpo) são portanto existenciais


� justificação da segunda leitura� equivalências: a ←←←← b ≡≡≡≡ a ∨∨∨∨ ~b; ∀∀∀∀X p(X) ≡≡≡≡ ~∃∃∃∃x ~p(X)

MIEIC 2010/2011

Prolog - 48

Regra de dedução 4: modus ponens

� Lei do modus ponens universal permite as deduçõesvia regras� diz que da regra

• R= (A ← B1, B2, ..., Bn) (contendo variáveis)

� e dos factos• B'1. B'2. .... B'n.

� se pode deduzir A' se A' ← B'1, B'2, ..., B'n for uma instânciade R.

� [identidade e instanciação são casos particulares]

� Um programa em lógica é um conjunto finito de regras.

MIEIC 2010/2011

25Eugénio Oliveira

Prolog - 49

Consequência lógica

� Um objectivo quantificado existencialmente G é uma consequência lógica de um programa P, se existir uma cláusula em P com uma instância sem variáveis

A ← B1, B2, ..., Bn, n≥0,

tal que B1, B2, ..., Bn sejam consequênciaslógicas de P e A uma instânciade G.

� responder a perguntas é aplicar (redução) o modus ponensda frente para trás o número de vezes necessáriopara ir do objectivo até aos factos

a) escolhendo uma instância do objectivo e

b) uma regra para aplicar, recursivamente.

MIEIC 2010/2011

Prolog - 50


� Ex. de Interpretação de uma Fórmula Lógica A1:(P Λ Q) � (R ↔↔↔↔ (~S))Se {P,Q,R,S} {T,F,T,T} então A1= T

� A Fórmula A1 está sob aquela Interpretação.

� Uma fórmula Falsa sob todas as Interpretações diz-se INCONSISTENTE� Uma Fórmula diz-se CONSISTENTE se não for Inconsistente

A2 é o Modus Ponens e logo é Válida

� Uma Fórmula lógica verdadeira sob todasas Interpretações diz-se VÁLIDA

� Ex:A2 ((P�Q) Λ P) � Q� P Q A2

F F TF T TT F TT T T

MIEIC 2010/2011

26Eugénio Oliveira

Prolog - 51


• Definição: dadas as Fórmulas Lógicas F1…Fn e G, G é uma Consequência Lógicade F1 … Fn se e só se para qualquer Interpretação na qual F1…Fn são verdadeiras, G também o é.

• G é uma consequência lógica de F1…Fn se e só se ( (F1Λ…ΛFn) � G) for uma fórmula VÁLIDA

~(F1 Λ …Λ Fn) ∪ G~(~(F1 Λ … Λ Fn) ∪ G ) tem sempre o valor Falso• G é uma Consequência Lógicade F1…Fn se e só se(F1 Λ …Λ Fn Λ ~G) for Inconsistente

MIEIC 2010/2011

Prolog - 52

Procedimento- colecção de regras com o mesmo predicado na cabeça.

Procedimentos

� para obter todos os netos • avos( X, Y ) ← pai( X, Z ), pai( Z, Y ).

• avos( X, Y ) ← pai( X, Z ), mae( Z, Y ).

• avos( X, Y ) ← mae( X, Z ), pai( Z, Y ).

• avos( X, Y ) ← mae( X, Z ), mae( Z, Y ).

� outra representação, mais compacta1 progenitor( X, Y ) ← pai( X, Y ).

2222 progenitor( X, Y ) ← mae( X, Y ).

3 avos( X, Y ) ← progenitor( X, Z ), progenitor( Z, Y ).

� progenitor/2 tem duas alternativas — é uma forma de representardijunção

MIEIC 2010/2011

27Eugénio Oliveira

Prolog - 53

resolvente- pergunta conjuntiva com os objectivos ainda em processamento

traçado- evolução da computação, com a indicação de

a) objectivo seleccionado

b) regra escolhida para a redução

c) substituição associada

∇ - resolvente vazia (= true)

Traçado de uma execução

avos( X, jacob ) 3

progenitor( X, Z ), progenitor( Z, jacob ) 1

progenitor( X, Z ), pai( Z, jacob)

progenitor( X, isaac ) 2 {Z= isaac }

mae( X, isaac ) {Z= isaac }

∇ {Z= isaac, X= sara}

1 progenitor( X, Y ) ← pai( X, Y ).2 progenitor( X, Y ) ← mae( X, Y ).3 avos( X, Y ) ← progenitor( X, Z ), progenitor( Z, Y ).…. …. …

MIEIC 2010/2011

Prolog - 54

Outro traçado de execução

avos( X, jacob ) 3

progenitor( X, Z ), progenitor( Z, jacob ) 1pai( X, Z ), progenitor( Z, jacob )

progenitor( isaac, jacob ) 1 { X=abraao, Z= isaac }

pai( isaac, jacob ) { X=abraao, Z= isaac }{ X=abraao, Z= isaac}

∇

MIEIC 2010/2011

28Eugénio Oliveira

Prolog - 55

livro( Titulo, autor( Proprio, camoes), data(1585, Mes, Dia)) )

livro( lusiadas, autor( luis, Apelido), Data )

θθθθ = {Titulo=lusiadas, Proprio=luis, Apelido=camoes,

Data= data(1585, Mes, Dia)}

Unificação

� um termo T é uma instância comumde T1 e T2 se existirem substituições θ1 e θ2 tais que T=T1θ1 e T=T2θ2

� um termo S é mais geraldo que um termo T, se T for uma instância de Se Snão for uma instância de T

� um termo S é uma variante de um termo T se se puderem converter um no outro por simples renomeação de variáveis

� um unificador de dois termos é uma substituição que torna os dois termos iguais

MIEIC 2010/2011

Prolog - 56

Algoritmo de unificação

� o algoritmo de unificaçãoproduz o unificador ou reporta falha� baseia-se na comparação de functores e na tentativa de unificar

os respectivos argumentos, propagando cada substituição a todas as ocorrências de variáveis

� o resultado é o unificador mais geral possível (a respectiva instância é a mais geral de todas as instâncias)

� verificação de ocorrência - para unificar uma variável X com um termo T, T não pode conter X [não há unificador mais geral para X e s(X)]

MIEIC 2010/2011

29Eugénio Oliveira

Prolog - 57

Interpretador abstracto

Entrada programa Pobjectivo G

Saída Gθθθθ, se existir, ou falhaAlgoritmo

• inicializar a resolventepara ser o (conjunto de) objectivo(s) G• Enquanto a resolvente não estiver vaziaFazer

– escolher um objectivoA da resolvente e uma cláusula

A' ← B1, B2, ..., Bn n≥0

em P tal que A e A' unifiquem com unificadorθθθθ(sair do ciclo se não existirem tais objectivo e cláusula)

– remover A da resolvente e adicionar-lhe B1, B2, ..., Bn

– aplicarθ à resolvente e a G

• se a resolvente estiver vazia devolver G, se não reportar falha

MIEIC 2010/2011

Prolog - 58


Programa: pai(abraão,isaac). homem(isaac).

pai(haran,lot). homem(lot).

pai(haran,milcah). mulher(milcah).

pai(haran, yiscah). mulher(yiscah).

filho(X,Y) ← pai(Y,X), homem(X).

filha(X,Y) ← pai(Y,X), mulher(X).

Objectivo: filho(lot,haran)?

Traçado: resolvente: filho(lot,haran)

resolvente diferente de vazia

selecciona: filho(lot,haran)

selecciona em P:filho(lot,haran) ← pai(haran,lot), homem(lot).

Nova resolvente: pai(haran,lot), homem(lot)

MIEIC 2010/2011

30Eugénio Oliveira

Prolog - 59


Traçado: Nova resolvente: pai(haran,lot), homem(lot) resolvente diferente de vazia

selecciona: pai(haran,lot)

selecciona em P: pai(haran,lot).

Nova resolvente: homem(lot)

resolvente diferente de vazia

selecciona: homem(lot)

selecciona em P: homem(lot).

Nova resolvente: vazia

Saída: “YES”

MIEIC 2010/2011

Prolog - 60

Bases de dados

� conjunto de factos = base de dados(BD extensiva)

regras = vistas(BD intensiva)

� predicado só com factos = relação

pai( Pai, Filho ), mae( Mae, Filho ), homem( Pessoa ),mulher( Pessoa ) [esquemas]

� definição de vistas

progenitor( P, Filho ) ← pai (P, Filho ).progenitor( P, Filho ) ← mae( P, Filho ).irmao( X, Y ) ←

progenitor( P, X ), progenitor( P, Y ), homem( X ), X \= Y.tio( Tio, Sob ) ← irmao( Tio, P ), progenitor( P, Sob ).antepassado( A, X ) ← progenitor( A, X ).antepassado( A, X ) ← progenitor( A, Y ), antepassado( Y, X ).

MIEIC 2010/2011

31Eugénio Oliveira

Prolog - 61

not G é verdadeiro relativamente a um programa P

se G não for uma consequência lógica de P

PL vs BD relacionais

� programação em lógica— extensão ao modelo relacional, fornece uma linguagem integrada de acesso aos dados, e de programação de aplicações

� operações básicas� reunião

r_uniao_s( X1, ..., Xn ) ← r( X1, ..., Xn )r_uniao_s( X1, ..., Xn ) ← s( X1, ..., Xn )

� diferença• requer um predicado de negação

r_menos_s( X1, ..., Xn ) ← r( X1, ..., Xn ), not s( X1, ..., Xn )

MIEIC 2010/2011

Prolog - 62

Operações da álgebra relacional

� produto cartesiano

r_vezes_s( X1, ..., Xm, Xm+1, ..., Xm+n )

← r( X1, ..., Xm ), s( Xm+1, ..., Xm+n )

� projecção (ex: relação r entre 1º e 3º args )

r13( X1, X3 ) ← r( X1, X2, X3 )

� selecção (ex: os tuplos em que o 2º arg é maior que o 3º arg)

r1( X1, X2, X3 ) ← r( X1, X2, X3 ), X2 > X3

� operações derivadas� intersecção

r_inter_s( X1, ..., Xn ) ← r( X1, ..., Xn ), s( X1, ..., Xn )� junção natural

r_join_s( X1, X2, X3 ) ← r( X1, X2 ), s( X2, X3 )

MIEIC 2010/2011

32Eugénio Oliveira

Prolog - 63

Estilo de programação

� dois estilos1) exprimir a informação à custa de relaçõesentre indivíduos

atómicos

2) codificar informação em termos, indivíduos complexos e manipular estruturas

� arte: encontrar o adequado nível de abstracção� esconder os detalhes da representação —independência dos

dados

� evidenciar associações entre indivíduos, evitando redundâncias — normalização

MIEIC 2010/2011

Prolog - 64

Representação de informação

� Representar o facto de o João possuir um exemplar dos Lusíadas de Luís de Camões, editado em 1940.

� Codificação em termos complexos, com poucos predicados� possui( joao, livro( lusiadas, autor( luis, camoes), 1940 ) ).

� Quem possui livros editados em 1940?

?- possui( X, livro( _, _, 1940 ) ).

� Codificação baseada em predicados, com termos simplesescritor( 1, luis, camoes). livro( 427, lusiadas, 1940 ).autor( 1, 427). pessoa(1002, joao ). possui( 1002, 427 ).

� ?- possui( CodP, CodL), pessoa( CodP, X ), livro(CodL, _, 1940).

MIEIC 2010/2011

33Eugénio Oliveira

Prolog - 65

Tipos� não existe noção independente de tipo; existem

predicados que definem implicitamente tipos� tipo — conjunto de termos

� definição de tipo — (muitas vezes) predicado unário

� tipos pessoa ou homem definido como o conjunto dos termos X tais que pessoa(X) ou homem(X) é verdade

� tipos recursivossimples — definidos por programas em lógica unários recursivos

• inteiros, listas, árvores binárias� inteiros: predicado de tipo

% natural( X ) i.e. X é um número natural% sn(0) denota n

natural( 0 ).natural( s(X) ) ← natural( X ).

� s(X) representa o sucessorde X

MIEIC 2010/2011

Prolog - 66

� traço de um objectivo

s(s(0)) ≤ s(0)s(0) ≤ 0 • este objectivo não tem redução porque não unifica com nenhuma

cabeça de cláusula — o traçado falha ( para suceder teria que terminar em ∇)

Aritmética

� relação de ordem% X ≤ Y ← se X e Y são números naturais e X ≤ Y (notação infixa de '≤'( X, Y ) )

0 ≤ X ← natural( X ).s(X) ≤ s(Y) ← X ≤ Y

MIEIC 2010/2011

34Eugénio Oliveira

Prolog - 67

Adição

� operação de adição como relaçãoternária

% soma( X, Y, Z ) ← se X, Y e Z são números naturais e Z é a soma de X e Y

soma( 0, X, X ) ← natural( X ).

soma( s(X), Y, s(Z) ) ← soma( X, Y, Z ).

� definição de tipo recursivo permite forma compacta para a adição, em vez da explícita

MIEIC 2010/2011

Prolog - 68

Múltiplos usos

� uso relacional (invertido)soma( s(0), Y, s(s(s(0)))soma( 0, Y, s(s(0)) ) { X=0, Z= s(s(0)) }∇ { Y= X=s(s(0)) }� note como se define o resultado e se pergunta as parcelas

� usofuncionalsoma( s(s(0)), s(0), X )soma( s(0), s(0), Z1 ) { X = s( Z1) }soma( 0, s(0), Z2 ) { Z1 = s(Z2), X = s(s(Z2)) } ∇ { Z2 = s(0), Z1 = s(s(0)), X = s(s(s(0))) }� note como se constrói um termo para devolver em X, à custa de o

manteraberto com uma variável e da unificação que causainstanciação parcial

soma( 0, X, X ) ← natural( X ).soma( s(X), Y, s(Z) ) ← soma( X, Y, Z ).

MIEIC 2010/2011

35Eugénio Oliveira

Prolog - 69

Várias soluções

� Traçado com soluções múltiplassoma( X, Y, s(s(s(0))) )∇ { X= 0, Y= s(s(s(0))) };soma( X, Y, s(s(s(0))) )soma( X1, Y, s(s(0)) ) { X= s(X1) }∇ { X1= 0, Y= s(s(0)) }etc.

;{no}

� pede-se uma nova solução com um sinal “;”

soma( 0, X, X ) ← natural( X ).soma( s(X), Y, s(Z) ) ← soma( X, Y, Z ).

MIEIC 2010/2011

Prolog - 70

Significadode um programa P, M(P), é o conjuntodos Significado de um programaP, M(P), é o conjunto dos objectivos completamente instanciados dedutíveis de P.

Significado

� esquema da relação/predicado descreve o significadopretendidoM, também definido emtermos de objectivosna relação� relativamente ao significado pretendido

• programa correcto M(P) ⊆⊆⊆⊆ M

• programa completoM ⊆⊆⊆⊆ M(P)

� Pretendem-se: programas correctos e completosM=M(P)

MIEIC 2010/2011

36Eugénio Oliveira

Prolog - 71

•(a, •(b, []) ) [a | [b | []] ] [a, b]

a

b []

••

cabeça cauda

formal par elementos

[a].(a,[]) [a|[]] [a]

.(a, .(b, .(c, []))) [a|[b|[c | []] [a, b, c]

.(a, X) [a|X] [a|X]

.(a, .(b, X)) [a | [b | X] ] [a,b| X]

Listas

Lista — estrutura de dados binária em que o 1º argumento é um elementoe o 2º recursivamenteo resto da lista; a base da recursão é a lista vazia []Representações

b []

MIEIC 2010/2011

Prolog - 72

% lista( Xs ) i.e. Xs é uma lista

lista( [] ).

lista([X | Xs] ) ←←←← lista( Xs ).

� definição de tipo

lista( [1,2,3] ) ← lista( [2,3] )

R: { X= 1, Xs=[2,3] }

�membro de uma lista% member( X, Xs ) i.e. X é um elemento

da lista Xs

member( X, [X|Xs] ) ← lista( Xs ).

member(X, [Z| Xs] ) ← member( X, Xs ).

omite-se

• nomes das variáveis são arbitrários e locais às regras

• mas convém ter uma disciplina

Manipulação de listas

member(b, [a,b,c]).

R: yes

member(X, [a,b,c] )

R: { X= a } ou {X=b} ou {X = c}

member(b, Xs)

R: { Xs= [b]} ou {Xs = [X, b|Z]}

MIEIC 2010/2011

37Eugénio Oliveira

Prolog - 73

Predicados sobre listas

� Comprimento de uma lista% comp( Xs, N ) ← a lista Xs tem N elementoscomp( [], 0 ).comp( [X| Xs], s(N) ) ← comp(Xs, N ).

� Prefixo e sufixo de uma lista% prefixo( Ps, Xs ) ← Ps é uma sublista consecutiva

no início da lista Xs

prefixo( [], Xs ) .

prefixo( [X|Xs], [X| Ys] ) ← prefixo( Xs, Ys ).

[1,2],[1,2,3]

% sufixo (Ss,Xs) i.e. Ss é uma sublista no fim de Xs

sufixo( Xs, Xs ) .

sufixo( Xs, [Y| Ys] ) ← sufixo( Xs, Ys ).

[2,3],[1,2,3]

MIEIC 2010/2011

Prolog - 74

% append( Xs, Ys, Zs ) ← se Zs for o resultado da concatenacao de Xs e Ys% append( Xs, Ys, Zs ) ← se Zs for o resultado da concatenacao de Xs e Ys

append( [], Ys, Ys ).

append( [X|Xs], Ys, [X|Zs] ) ← append( Xs, Ys, Zs ).

append( [a,b], [c,d], Zs0 )

append( [b], [c,d], Zs1 ) { Zs0= [a|Zs1] }

append( [], [c,d], Zs2 ) { Zs1= [b|Zs2] }

∇ { Zs2= [c,d] }

R: Zs = [a,b,c,d]

append( Xs, [c,d], [a,b,c,d] )

append( Xs1, [c,d], [b,c,d] ) { Xs= [a|Xs1] }

append( Xs2, [c,d], [c,d] ) { Xs1= [b|Xs2] }

∇ { Xs2= [ ] }

R: Xs = [a,b]

� Uso do programa de modo funcional e relacional:

Concatenação

� partição de uma lista• append( Xs, Ys, [a,b,c,d] )

� tem múltiplas soluções e aplicações variadas• member( X, Xs ) ← append( As, [X|Ys], Xs )

:- member(3, [1,3,4,2])

MIEIC 2010/2011

38Eugénio Oliveira

Prolog - 75

Aplicações da concatenação

� Sublistas% sublista( Sub, Lista ) ← Sub é uma sublista de Lista% prefixo de sufixo

sublista( Sub, Lista ) ← prefixo( Sub, Xs ), sufixo( Xs, Lista ).% ou

sublista(Xs, AsXsBs ) ←append( As, XsBs, AsXsBs ), append( Xs, Bs, XsBs)

[c,2], [a,b,c,2,4]

� Inverter uma lista% inverte( Lista, Inv ) ← Inv é o resultado de inverter Lista% algoritmo ingénuoinverte( [], [] ).inverte( [X| Xs], Zs ) ← inverte( Xs, Ys ), append( Ys, [X], Zs ).

[a,b,c,2,4], Zs

MIEIC 2010/2011

Prolog - 76

inverte( [b,c,d], L )

inverte( [c,d],L0 )

inverte( [d], [d] )

inverte( [], [] )

append([d], [c], [d,c] ) append([c], [b], [c,b] )

append([], [d], [d] )

append( L0 , [b],L )

append([], [b], [b] )append([], [c], [c] )

Dimensão da árvore de prova quadrática no número de elementos da lista a inverter.

Árvore de prova

� Árvore de prova — os nóssão os objectivos reduzidos durante a computação; a raizé o objectivo da pergunta; há arcosde cada nó para todosos nós obtidos daquele por um passo de redução.

� Resulta mais declarativa do que o traçado; mostra as razões da dedução.

[d,c,b]

[d,c,b][d,c] [d,c]

MIEIC 2010/2011

39Eugénio Oliveira

Prolog - 77

• traçadoinverte( [b,c,d],[] )

inverte( [c,d], [b] )

inverte( [d], [c,b] )

inverte( [], [d,c,b] )

∇

Evitar a concatenação

Inverter sem concatenação (tentativa)

% inverte( Lista, Inv ) ← Inv é o resultado de inverter Lista

% algoritmo sem append

inverte( [X| Xs], Acc ) ← inverte( Xs, [X|Acc] ).

inverte( [], Acc ).

Iniciamos o Acumulador a []

� inverteu, mas ... e o resultado?

Objectivo

MIEIC 2010/2011

Prolog - 78

• traçadoinverte( [b,c,d],Ys ) inverte( [b,c,d],[], Ys ) inverte( [c,d], [b], Ys )inverte( [d], [c,b], Ys )inverte( [], [d,c,b], Ys )

∇ { Ys= [d,c,b] }

Acumuladores

� Inverter sem concatenação usando acumulador para extrair o resultado (por unificação no último passo)

% inverte( Lista, Inv ) ← Inv é o resultado de inverter Lista

% algoritmo com acumulador (argumento suplementar)

inverte( Xs, Ys ) ← inverte( Xs, [], Ys ).

inverte( [X| Xs], Acc, Ys ) ← inverte( Xs, [X|Acc], Ys ).

inverte( [], Ys, Ys ).

� este traçado corresponde a uma árvore de tamanho linear no número de elementos da lista

MIEIC 2010/2011

40Eugénio Oliveira

Prolog - 79

Filtro

% apaga( Lista, X, SemXs ) ← a lista SemXs é Lista com todos os X removidos

apaga( [X| Xs], X, Ys ) ← apaga( Xs, X, Ys ).apaga( [Z| Xs], X, [Z|Ys] ) ← X≠Z, apaga( Xs, X, Ys ).apaga( [], X, [] ).

� A condição X≠Z na segunda regra é essencial para obter resultados correctos

MIEIC 2010/2011

Prolog - 80

Ordenação

particao( [X| Xs ], Y, [X| Ls], Mas ) ← X =< Y, particao( Xs, Y, Ls, Mas ).

particao( [X| Xs ], Y, Ls, [X| Mas] ) ← X > Y, particao( Xs, Y, Ls, Mas ).

particao( [], Y, [], [] ).

% quicksort( Xs, Ys ) ← a lista Ys é uma permutação ordenada de Xs

quicksort( [X| Xs], Ys ) ←particao( Xs, X, Menores, Maiores ),

quicksort( Menores, Mes),

quicksort( Maiores, Mas ),

append( Mes, [X| Mas], Ys ).

quicksort( [], []

MIEIC 2010/2011

41Eugénio Oliveira

Prolog - 81

Árvores Binárias

� Árvore binária- estrutura duplamente recursiva% arvore(Arv ) i.e. Arv é uma árvore

arvore( []).

arvore( arv(Elem, Esq, Dir) ) ← arvore( Esq ), arvore( Dir ).

% membro_arv( X, A ) i.e. X é um elemento da árvore binária A

membro_arv( X, arv(X,E,D) ).

membro_arv( X, arv(Z,E,D) ) ← membro_arv(X, E ).

membro_arv( X, arv(Z,E,D) ) ← membro_arv(X, D)

% pre_ordem( Arv, Pre ) ← Pre é uma travessia em preordem da árvore Arv

pre_ordem( arv(X,E,D), Pre ) ← pre_ordem( E, Es ), pre_ordem( D, Ds ),append( [X| Es], Ds, Pre ).

pre_ordem( void, [] ).

% isomorfa(Arv1, Arv2 ) ← Arv1 e Arv2 são isomorfas

isomorfa( void, void ).

isomorfa( arv(X,Esq1,Dir1), arv(X,Esq2,Dir2) ) ← isomorfa( Esq1, Esq2), isomorfa(Dir1, Dir2 ).

isomorfa( arv(X,Esq1,Dir1), arv(X,Esq2,Dir2) ) ← isomorfa( Esq1, Dir2), isomorfa(Dir1, Esq2 ).

MIEIC 2010/2011

Prolog - 82

resolvente- pergunta conjuntiva com os objectivos ainda em processamento

traçado- evolução da computação, com a indicação de

a) objectivo seleccionado

b) regra escolhida para a redução

c) substituição associada

∇ - resolvente vazia (= true)

Traçado de uma execução

avos( X, jacob ) 3

progenitor( X, Z ), progenitor( Z, jacob ) 1

progenitor( X, Z ), pai( Z, jacob)

progenitor( X, isaac ) 2 {Z= isaac }

mae( X, isaac ) {Z= isaac }

∇ {Z= isaac, X= sara}


MIEIC 2010/2011

42Eugénio Oliveira

Prolog - 83

Árvore de pesquisa

� Árvore de pesquisa de um objectivo G relativamente a um programa P� raiz da árvore: G

� nós: resolventes, com um objectivo seleccionado

� arcos a sair de um nó: um por cada cláusula de P cuja cabeça unifica com o objectivo seleccionado no nó

� cada caminho na árvore, desde a raiz: computação de G por P

� folhas: nós de sucesso, se corresponderem a resolventes vazias; nós de falha se o objectivo selecionado não puder ser reduzido

MIEIC 2010/2011

Prolog - 84

avos( X, jacob )

progenitor( X, Z ), progenitor( Z, jacob )

progenitor( X, Z ), pai( Z, jacob) progenitor( X, Z ), mae( Z, jacob)

{X= abraao}

progenitor( X, isaac )

mae( X, isaac )pai( X, isaac )

{Z= isaac }

{X= sara}

∇ ∇

sucessoX=abraao, Z=isaac

sucessoX=sara, Z=isaac

falha

Árvore de pesquisa do Jacob


MIEIC 2010/2011

43Eugénio Oliveira

Prolog - 85

avos( X, jacob )

progenitor( X, Z ), progenitor( Z, jacob )

pai( X, Z ), progenitor( Z, jacob) mae( X, Z ), progenitor( Z, jacob)

{X= abraao}

pai( X, Z ), mae( Z, jacob )

pai( X, Z ), pai( Z, jacob)

∇sucesso

X=abraao, Z=isaacsucesso

X=sara, Z=isaac

Outra árvore de pesquisa

pai( X, isaac )

{Z= isaac}

falha{X= sara}

mae( X, Z ), mae( Z, jacob )

mae( X, Z ), pai( Z, jacob)

∇

mae( X, isaac )

{Z= isaac}

falha


MIEIC 2010/2011

Prolog - 86

Características destas árvores

� conclusão principal: o número de nós de sucesso é o mesmo em todas elas

� uma árvore de pesquisa resume todas as respostas; chama-se de pesquisaporque um interpretador concreto terá que ter uma estratégia para percorrer a árvore em busca de soluções (pesquisa em profundidade, em largura, em paralelo, ...)

� árvore de pesquisa: independente do critério de selecção de cláusulas(tem todas as alternativas)

� podem existir várias árvores de pesquisa diferentespara o mesmo objectivo e o mesmo programa, conforme o critério de selecção dos objectivos

MIEIC 2010/2011

44Eugénio Oliveira

Prolog - 87

append( Xs, [c,d], Ys)

append( Xs1, [c,d], Ys1) ∇

{Xs= [], Ys= [c,d]}{Xs= [X|Xs1], Ys= [X|Ys1]}


{Xs1= [], Ys1= [c,d]}{Xs1= [X1|Xs2], Ys1= [X1|Ys2]}


{Xs2= [], Ys2= [c,d]}{Xs2= [X2|Xs3], Ys2= [X2|Ys3]}

°°°

°°°

Computações infinitas

� ramos infinitos na árvore correspondem a computações sem fim

� uma pesquisa em profundidadepode perder-se num ramo infinito

� avaliar a complexidadede uma pergunta: (interpretadores que pesquisem sequencialmente toda a árvore) é mais realista analisar o número de nós da árvore de pesquisa do que da árvore de prova (esta inclui não determinismo)

append( [], Ys, Ys ).

append( [X|Xs], Ys, [X|Zs] ) ← append( Xs, Ys, Zs ).

MIEIC 2010/2011

Prolog - 88

Negação por falha� os programas em lógica descrevem o que é verdade; o falso é omitido� certas relações são mais fáceis de especificar com a negação

dijunto( Xs, Ys ) ← not ( member( X, Xs ), member( X, Ys ) )� para obter conclusões negativas: assunção do mundo fechado CWA

� not Gé uma consequência do programa P se G não for uma consequência de P (mesmo que G dê ramo infinito),

Dedução usando negação por falha: not G é uma consequência de P se G estiver no conjunto de falha finita de P

falha falha

� árvore de pesquisa finitamente falhada: não contém nós de sucesso nemramos infinitos

� conjuntode falha finita do programa P: conjunto dos objectivos que têmuma árvore finitamente falhada relativamente a P

� árvore finitamente falhada: progenitor( isaac, X )pai( isaac, X ) mae(isaac, X)

MIEIC 2010/2011

Documents

Programação em Lógica - paginas.fe.up.ptpaginas.fe.up.pt/~eol/LP/1011/documents/Teoricas/PL1.pdf · Programação em Lógica • História e Fundações da Programação em Lógica