Baixe o app para aproveitar ainda mais
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
Compartilhar