Upload
andre-pitombeira
View
461
Download
0
Embed Size (px)
Citation preview
Equipe: André Pitombeira
Fernando Helton
Francisco Humberto
Niltemberg Carvalho
Rainara Maia
• Expressar programas na forma de lógica simbólica e usar processo de inferência lógica para produzir resultados.
• Os programas lógicos são declarativos, não são baseados em procedimentos.
• A sintaxe das linguagens de programação lógica é diferente da sintaxe das linguagens imperativas e das funcionais.
• A semântica, por sua vez, tem pouca semelhança com a dos programas em linguagem imperativa.
• Antes de discutir a programação lógica, precisamos investigar sua base: a lógica formal.
• Uma proposição é uma declaração que pode ou não ser verdadeira. A lógica formal foi desenvolvida para fornecer um método de descrever proposições, com o objetivo de permitir que estas sejam verificadas quanto a sua validade.
• A lógica simbólica pode ser usada para três necessidades básicas da lógica formal: expressar as proposições, as relações entre estas e descrever como novas proposições podem ser inferidas de outras que se presumem verdadeiras.
• Existe uma estreita relação entre a lógica formal e a matemática, os axiomas da teoria dos números e dos conjuntos são o conjunto inicial de proposições presumidas como verdadeiras.
• A forma particular de lógica simbólica usada para programação lógica é o cálculo de predicados.
• ProposiçõesConsiste em objetos e nas relações de objetos entre si, esses objetos são representados por termos simples, constantes ou variáveis. Uma constante é um símbolo que representa um objeto. Uma variável é um símbolo que pode representar diferentes objetos. As proposições mais simples, chamadas proposições atômicas, consistem em termos compostos, que é formado por duas partes: um functor, o símbolo de função que nomeia a relação e uma lista ordenada de parâmetros. Por exemplo:
homem(jake)gosta(bob, bife)
• ProposiçõesAs proposições compostas têm duas ou mais proposições atômicas, ligadas por conectores lógicos ou operadores:
Nome Símbolo Exemplo Significado
Negação ¬ ¬a Não a
Conjunção ∩ a∩b a e b
Disjunção U aUb a ou b
Equivalência ≡ a b≡ a é equivalente a b
Implicação ⊃ a b ⊃ a implica b
• Variáveis podem aparecer em proposições, mas somente quando introduzidas por quantificadores. O cálculo de predicados inclui dois quantificadores:
• Exemplo: X. (mulher(x)) ∀ ⊃ humano(x))• ∃ X.(mãe(mary, X) ∩ homem(X))
Nome Exemplo Significado
Universal ∀ XP Para todo X, P é verdadeiro
Existencial ∃ X.P Existe um valor de X tal que P seja verdadeiro
• Forma Clausal• Um problema é que há muitas maneiras diferentes de
declarar proposições com o mesmo significado, ou seja, há muita redudância. Para simplificar as coisas uma forma padrão de proposições é desejável. A clausal, uma forma relativamente simples de proposições, é uma dessas formas. Uma proposição nessa forma tem a seguinte sintaxe:
B1 U B2 U … U Bn C A2 ∩ A2 ∩ … ∩ Na
onde A e B são termos, o significado é se todos os As forem verdadeiros, pelo menos um B será verdadeiro.
• O lado direito de uma proposição na forma clausal é chamado antecedente. O esquerdo, consequente; isso porque é a consequência da verdade de seu antecedente. Exemplo:
pai(louis, beto) U pai(louis, nara) C pai(beto, bob) ∩ mãe (nara, bob) ∩ avô(louis, bob)
É um método para expressar coleções de proposições.
Estas coleções são usadas para determinar se fatos interessantes ou úteis podem ser inferidos a partir da mesma.
• Resolução é uma regra de inferência que permite a computação das proposições inferidas a partir das proposições dadas.
• Este método é muito utilizado na demonstração de teoremas.
Suponhamos duas proposições:P1 c P2Q1 c Q2
Se P1 é igual a Q2, poderíamos reescrever substituindo P1 e Q2 por T:
T c P2
Q1 c T
Tendo que:T c P2Q1 c T
Poderíamos dizer que:Q1 c P2
• Este processo de a partir das proposições dadas:
• P1 c P2• Q1 c Q2
• Inferir que:• Q1 c P2
• É chamado resolução.
• Outro exemplo, a partir de:
mais velho(Joane, Jake) c mãe(Joane, Jake)
mais sábio(Joane, Jake) c mais velho(Joane, Jake)
• Inferirmos que:
mais sábio(Joane, Jake) c mãe(Joane, Jake)
• A mecânica dessa construção de resolução é simples: os termos que aparecem do lado esquerdo são unidos por um E para formar o lado esquerdo da nova proposição. Então, a mesma coisa é feita para obter o lado direito dela. Em seguida, o termo que aparece em ambos os lados é removido.
Porém a resolução é mais complexa do que os exemplos mostram. Em particular, a presença de variáveis em proposições exige que a resolução encontre valores para essas variáveis permitindo que o processo de comparação seja bem-sucedido. Este processo de determinação dos valores é chamado de unif icação. A atribuição temporária de valores a variáveis para permitir a unificação é chamada instanciação.
Uma propriedade importante da resolução é a capacidade de detectar qualquer inconsistência em um conjunto de proposições. Essa propriedade permite que a resolução seja usada para demostrar teoremas. Esta prova é feita por contradição, as proposições originais são chamadas de hipóteses, e a negação do teorema é chamada de meta.
• Um problema do processo de resolução é o tempo necessário para tal. O tempo necessário para encontrar uma inconsistência pode ser enorme.
• A demonstração de teoremas é a base da programação lógica. Grande parte do que é computado pode ser expresso na forma de uma lista de fatos dados e de relações como hipóteses, e uma meta a ser inferida a partir das hipóteses, usando resolução.
• As cláusulas de Horn, simplificam ainda mais o processo de resolução. Elas podem estar somente em duas formas: com uma única proposição atômica no lado esquerdo, ou com o lado esquerdo vazio.
• O lado esquerdo de uma fórmula clausal pode ser chamado de cabeça, e as cláusulas de Horn que possuem lado esquerdo pode ser chamada de cláusula de Horn encabeçada.
gosta(bob, truta) c gosta(bob, peixe) ^ peixe(truta)
• As cláusulas de Horn com o lado esquerdo vazio são ditas sem-cabeça.
pai(bob, Jake)
• Termos;• Instruções Relativas a Fatos;• Instruções Relativas a Regras;• Instruções Relativas a Metas;• Processo de Inferência do Prolog;• Aritmética Simples;• Estruturas de Listas.
• Como em outra linguagens de Programação o Prolog consiste em um conjunto de instruções , que podem ser em alguns casos muito complexas. Todas são construídas a partir de termos.
• Termo: Em Prolog é uma constante, uma variável ou uma estrutura.
• Constante: É um átomo ou um número inteiro.• Átomo: É uma cadeia de letras, de dígitos e de grifos que
se inicia com uma letra minúscula ou uma cadeia de quaisquer caracteres ASCII imprimíveis delimitados por apóstrofos.
• Variável: É qualquer cadeia de letras, de dígitos e de grifos que se inicia com uma letra maiúscula. As variáveis não são vinculadas a tipos por declarações, são por instanciação, que ocorre somente no processo de resolução. As instanciações duram somente o tempo necessário para a prova ou refutação de uma proposição.
• Estrutura: Representam as proposições atômicas do cálculo de predicados, e sua forma geral é a mesma: functor(lista de parâmetros).
• O Prolog tem duas formas de instrução básicas que correspondem as Cláusulas de Horn sem e com cabeça de cálculo de predicados.
• A forma mais simples de cláusulas de Horn sem cabeça no Prolog é uma estrutura simples, interpretada como uma asserção incondicional ou como um fato.
• Logicamente, fatos são simplesmente proposições consideradas verdadeiras.
• Exemplo:mulher(rainara).
homem(fernando).mulher(adriana).homem(andre).
pai(fernando, andre).pai(fernando, rainara).mae(adriana, andre).
mae(adriana, rainara).
• A outra forma básica de instrução Prolog para construir o banco de dados é a cláusula de Horn com cabeça. Forma relacionada a um teorema da matemática conhecido, a partir do qual se pode tirar uma conclusão sobre se o conjunto de determinadas condições é satisfeito. O lado direito é o antecedente, ou a parte se (if), e o lado esquerdo é o conseqüente, ou a parte então (then).
• Conjunções: Contém termos múltiplos separados por operações AND lógica, que é implícita. A vírgula pode ser considerada o AND:
mulher(rainara), f i lho (rainara).
• Forma geral de construção de cláusula de Horn com cabeça:• Conseqüência_1 :- expressão_antecedente
• Leia-se: a “ conseqüência_1 poderá ser concluída se a expressão antecedente for verdadeira ou puder torna-se verdadeira por meio de alguma instanciação de suas variáveis”.
• antepassado(adriana, rainara) :- mãe(adriana, rainara).
• Obs: As cláusula de Horn são chamadas regras porque declaram regras de implicação entre proposições.
• Utilizadas para provar Teoremas, que queremos que o sistema prove ou desaprove. Essas proposições são chamadas metas ou consultas. A sintaxe é idêntica as cláusulas de Horn sem cabeça.
homem(fred).
• O sistema poderá responder com yes ou no.
pai (x, mike).
• O sistema tentará, pela unificação, encontrar uma instanciação de x que resulta em um valor verdadeiro para a meta.
• As consultas são chamadas metas. Quando uma meta é uma proposição composta, cada um dos fatos (estruturas) é chamado submeta. Para provar que ela é verdadeira, o processo de inferência deve encontrar um encadeamento de regras de inferência e/ou de fatos no banco de dados que ligam a meta a um ou mais fatos no banco de dados.
• O processo de provar uma submeta é feito por um processo de comparação de proposições, às vezes é chamado de casamento.
• Encadeamento Progressivo: Inicia com a meta e tenta encontra uma seqüência de proposições coincidentes que levam a algum conjunto de fatos originais no banco de dados.
• Encadeamento Retrogrado: Funciona bem quando há um conjunto razoavelmente pequeno de respostas candidatas. As implementações em Prolog usam o encadeamento retrogrado para resolução de problemas, porque seus projetistas achavam que ele era melhor para uma classe maior de problemas.
• Primeiramente pela profundidade: Localiza uma seqüência completa de proposições – uma prova – referente à primeira submeta antes de trabalhar nas outras.
• Primeiramente pela largura: Trabalha em todas as submetas de determina meta de maneira paralela.
• Backtracking: Uma nova solução é encontrada ao iniciar a procura onde a busca anterior dessa submeta interrompeu-se.
• O Prolog suporta variáveis de números inteiros e seus respectivos cálculos.
+(7, x)
• O Prolog permite uma sintaxe mais abreviada para cálculos aritméticos com o operador is. Este toma uma expressão aritmética como seu operando direito e variável como seu operando esquerdo.
A is B / 17 + C.
• Exemplo simples do uso de computações numéricas em Prolog:• Suponhamos conhecer as velocidades médias de diversos automóveis em
uma pista de corrida particular e a quantidade de tempo que eles permanecem na pista. Essa informação básica pode ser codificada como fatos, e a relação entre velocidade, tempo e distancia pode ser escrita como uma regra.
• velocidade(ford, 100).• velocidade(chevy, 105).• velocidade(dodge, 95).• velocidade(volvo, 80).• tempo(ford, 20).• tempo(chevy, 21).• tempo(dodge, 24).• tempo(volvo, 24).• Distancia(x, y) :- velocidade(x, Velocidade), tempo(x, Tempo), y is Velocidade * tempo.
• Consulta: distancia(chevy, Distancia_do_Chevy).
• Estrutura de dados básica é a lista. Elas são sequências de qualquer numero de elementos, em que estes podem ser átomos ou quaisquer outros termos, inclusive outras listas. O Prolog usa uma sintaxe convencional para especificar listas. Os elementos delas são separados por vírgulas, e a lista inteira é delimitada por colchetes, como em:
[maçã, ameixa seca, uvas, kumquat]
Uma lista pode ser criada como uma estrutura simples, como em:
nova_lista([maçã, ameixa seca, uvas, kumquat]) .
• Algumas operações são necessárias para lidar com lista. Um exemplo é a operação append. Os dois parâmetros para a operação append no código são as duas listas a serem anexadas e o terceiro parâmetro é a lista resultante:
append([Cabeça|Lista_1], Lista_2, [Cabeça, Lista_3]) append(Lista_1, Lista_2, Lista_3).
• A função append cria uma nova lista na terceira lista passada como parâmetro, concatenando as duas primeiras listas passadas como parâmetros.
38
• Controle de Ordem de ResoluçãoDependendo do problema, a intervenção do programador é muito importante para o programa ficar mais eficiente devido ao modo de inferência.
A ordem como as cláusulas são escritas podem levar a laços infinitos.
Ex: f(X, Y) : - f(Z, Y), g(X, Z).
/* Semelhante ao problema que um analisador
descendente recursivo tem com regras gramaticais
recursivas à esquerda */
39
• Controle de Ordem de ResoluçãoUso do comando cut, especificado por ‘!’ para limitar o backtracking, em prol da eficiência
Ex1.: a, b, ! , c, d. /* Se a e b forem ‘ true ’ e c falhar, então a
meta inteira falhará */
Ex2.: membro(Elemento, [Elemento | _ ] ) : - ! .membro(Elemento, [ _ | Lista]) : -
membro(Elemento, Lista).
% ‘_’ indica variável livre ou anônima
40
• Pressuposição de Mundo FechadoO Prolog é na verdade um sistema true / fail e não um sistema true / falsePois, quando não consegue provar que uma meta é verdadeira ele pressupõe que a meta deve ser falsa.
• O Problema da NegaçãoAs cláusulas de Horn evitam conclusões negativas
B ← A1 ∧ A2 ∧ . . . ∧ An
Se todas as proposições A forem verdadeiras, B também é, porém independente da verocidade ou
falsidade de qualquer um ou de todos os As, não se pode concluir que B é falso.
42
• Limitações Intrínsecas
Ineficiente para resolução de problemas de características iterativas ou procedimentais
43
• Sistemas de Gerenciamento de Banco de Dados RelacionaisPrincipal vantagem: Capacidade Dedutiva
• Sistemas EspecialistasDiminuir incosistencias e falta de completude
• Processamento de Linguagem Natural• Educação
Em particular crianças até 07 anos de idadeÉ mais fácil ensina-lás do que um programador
experiente em linguagem imperativa
44
Demonstração prática das seguintes aplicações:
• Problema da Torre de Hanói• Problema das Rainhas• APES (Sistema Especialista para construção
de outros sistemas especialistas)• Uso do Delphi 5.0 com Visual Prolog 5.2
45
• Programas em Prolog são conjuntos de instruções basicamente escritos em forma de Cláusulas de Horn
• Paradigma Declarativo• Baseado na Lógica Formal
Menos erros e menos manutenção• Programas Concisos
Tempo de desenvolvimento reduzidoBoa ferramenta para prototipação
• Forma alternativa para solução de problemas