Prévia do material em texto
1 Lógica Matemática Aula 08: Introdução à Programação Prolog Objetivo (s) da Aula 08: introduzir os conceitos básicos da linguagem de programação lógica Prolog. 8.1 Introdução Prolog (Programming in Logic) é uma linguagem de programação utilizada para resolver problemas que envolvem objetos e as relações entre eles. Seus conceitos básicos incluem fatos, perguntas, variáveis, conjunções e regras, enquanto os conceitos avançados abrangem listas e recursividade (onde uma função chama a si mesma para resolver problemas que podem ser divididos em subproblemas menores). 8.2 Programação Lógica Na programação procedural (Procedimental), um programa é composto por um algoritmo e estruturas de dados, onde a lógica do programa segue uma sequência de passos para atingir um objetivo. Já a programação imperativa é um paradigma de programação que foca em instruções sequenciais para o computador executar, especificando como alcançar um objetivo. Na programação lógica, o algoritmo é formado por lógica e controle, e o programa é definido como a combinação de lógica, controle e estruturas de dados. Em linguagens de programação lógica, como Prolog, a programação é feita de forma declarativa, ou seja, especifica-se o que deve ser computado, em vez de como deve ser computado. 8.3 Programação em Prolog Programar em Prolog envolve três etapas principais: declarar fatos sobre objetos e seus relacionamentos, definir regras que descrevem esses objetos e seus relacionamentos, e fazer perguntas para consultar esses fatos e regras. Dessa forma, Prolog permite que o programador descreva o conhecimento e as relações de maneira lógica e consulte o sistema para obter respostas (PALAZZO, A. M. 1997). 8.4 Definindo Relações por Fatos A Figura 8.1 mostra um exemplo de relação familiar: 2 Lógica Matemática Figura 8.1. Um exemplo de relação familiar, onde cada conexão indica uma relação de progenitor entre os membros. No contexto do Prolog, o fato de que Abraão ser progenitor de Isaque pode ser representado da seguinte forma: • progenitor(abraão, isaque). Nesse exemplo, "progenitor" é o nome da relação, e "abraão" e "isaque" são os argumentos que representam os indivíduos envolvidos na relação familiar. A árvore familiar completa em Prolog é: • progenitor(sara, isaque). • progenitor(abraão, isaque). • progenitor(abraão, ismael). • progenitor(isaque, esaú). • progenitor(isaque, jacó). • progenitor(jacó, josé). Este programa consiste em seis cláusulas, cada uma declarando um fato sobre a relação de progenitor entre os membros da família. Por exemplo, a cláusula progenitor(abraão, isaque). representa uma instância particular da relação progenitor em Prolog. Esta instância é também chamada de relacionamento específico entre dois indivíduos. Em termos gerais, uma relação é definida como o conjunto de todas as suas instâncias, ou seja, todas as combinações específicas que satisfazem essa relação. Em Prolog, a ordem dos argumentos em uma relação é definida arbitrariamente, mas 3 Lógica Matemática deve ser mantida de forma consistente para evitar confusões no significado. Por exemplo, a cláusula progenitor(abraão, isaque) indica que "Abraão é progenitor de Isaque". Já a cláusula progenitor(isaque, abraão) indicaria que "Isaque é progenitor de Abraão". Note que progenitor(abraão, isaque) e progenitor(isaque, abraão) não têm o mesmo significado, pois a inversão dos argumentos altera o sentido da relação. Os nomes das relações e de seus argumentos em Prolog são arbitrários, ou seja, as expressões progenitor(abraão, isaque) e a(b, c) seriam semanticamente equivalentes, desde que os significados sejam atribuídos da mesma forma — onde “a” significa “progenitor”, “b” significa “abraão” e “c” significa “isaque”. No entanto, é prática comum que o programador escolha nomes significativos para facilitar a compreensão do código. Quando o programa em Prolog é interpretado ou compilado, é possível fazer perguntas sobre a relação progenitor. em um console de consultas. Por exemplo, para verificar se Isaque é o pai de Jacó, pode-se comunicar essa pergunta ao Prolog digitando: • ?- progenitor(isaque,jacó). Como esse fato foi previamente declarado na base de dados do programa, Prolog encontra a correspondência e responde “yes” ou “true”. Essa resposta indica que a relação consultada é verdadeira de acordo com os fatos inseridos no programa. Outra pergunta que pode ser feita é ?- progenitor(ismael, jacó). Prolog responderá "no" ou “false”, pois o programa não contém nenhuma informação que indique Ismael como progenitor de Jacó. Da mesma forma, ao perguntar ?- progenitor(jacó, moisés). Prolog também responderá "no", pois não há nenhum fato na base de dados que defina Jacó como progenitor de Moisés. Perguntas mais interessantes também podem ser feitas, como: "Quem é o progenitor de Ismael?". Em Prolog, essa consulta seria realizada da seguinte forma: ?- progenitor(X, ismael). Nesse caso, Prolog não responderá apenas "yes" ou "no". Em vez disso, ele fornecerá o valor de X que torna a afirmação verdadeira. Assim, a resposta será: X = abraão, indicando que Abraão é o progenitor de Ismael, conforme definido nos fatos do programa. A pergunta "Quais os filhos de Isaque?" pode ser feita em Prolog da seguinte forma: ?- progenitor(isaque, X). Neste caso, há mais de uma resposta possível. Prolog fornecerá 4 Lógica Matemática primeiro uma solução: X = esaú. Se o usuário desejar outra resposta, pode solicitar mais uma solução digitando ";", e Prolog encontrará: X = jacó. Caso sejam requisitadas mais soluções, Prolog responderá "no", indicando que todas as soluções possíveis foram exauridas (ou seja, não há mais filhos de Isaque definidos no programa). Perguntas mais amplas também podem ser feitas, como: "Quem é o progenitor de quem?" Reformulando, isso significa encontrar valores para X e Y onde X é o progenitor de Y. Em Prolog, a consulta seria: ?- progenitor(X, Y). Prolog encontrará todos os pares de progenitor-filho e os exibirá um de cada vez. As soluções são mostradas individualmente, por exemplo: • X = sara Y = isaque; • X = abraão Y = isaque; • X = abraão Y = ismael; • ... Caso o usuário queira interromper as respostas, basta pressionar [Enter] em vez de ";". Perguntas mais complexas também podem ser feitas em Prolog, como: "Quem é o avô de José?" Como nosso programa não conhece diretamente a relação "avô", essa pergunta precisa ser dividida em duas etapas: (1) "Quem é o progenitor de José?" (assumindo que seja um Y); (2) "Quem é o progenitor de Y?" (assumindo que seja um X). Essa pergunta composta pode ser expressa em Prolog como: ?- progenitor(Y, josé), progenitor(X, Y). Prolog responderá com: X = isaque, Y = jacó. Isso indica que Isaque é o avô de José, e Jacó é o pai de José (Figura 7.2). 5 Lógica Matemática Figura 7.2. A imagem mostra uma relação familiar onde X é o avô de José. X é o progenitor de Y, e Y é o progenitor de José. A seta tracejada indica a relação de avô entre X e José. 8.5 Pontos Importantes Em Prolog, o nome de uma relação deve começar com uma letraminúscula. A relação é escrita primeiro, seguida dos argumentos separados por vírgulas e colocados entre parênteses, com um ponto final “.” ao final do fato. Definir uma relação é simples, como a relação progenitor, onde n-tuplas de objetos que satisfazem a relação são declaradas. O usuário pode, então, fazer perguntas ao sistema Prolog sobre as relações definidas no programa. Um programa Prolog é composto por cláusulas, cada uma terminando com um ponto final. Os argumentos nas relações podem ser objetos específicos (como "abraão" e "isaque") ou objetos gerais (como "X" e "Y"). Os primeiros são chamados átomos, enquanto os segundos são chamados variáveis. A aridade de uma relação refere-se ao número de argumentos que possui e é indicada por uma barra seguida desse número. Por exemplo, progenitor/2 indica que a relação progenitor tem 2 argumentos, ou seja, aridade 2. Em Prolog, perguntas consistem em uma ou mais cláusulas. Uma sequência de cláusulas, como progenitor(X, esaú), progenitor(X, jacó), representa a conjunção das cláusulas, significando que "X é progenitor de Esaú" e "X é progenitor de Jacó". A resposta a uma pergunta pode ser positiva (a pergunta é satisfatível e teve sucesso) ou negativa (a pergunta é insatisfatível e falhou). Se houver várias respostas que satisfazem uma pergunta, Prolog encontra todas as possíveis. O usuário pode pressionar Enter para aceitar uma resposta ou usar ponto-e-vírgula “;” para buscar mais respostas. 6 Lógica Matemática 8.6 Definindo Relações por Regras Nosso programa sobre famílias pode ser expandido de várias maneiras. Podemos adicionar informações sobre o sexo das pessoas envolvidas na relação progenitor. Por exemplo: • mulher(sara). • homem(abraão). • homem(isaque). • homem(ismael). • homem(esaú). • homem(jacó). • homem(josé). As relações mulher e homem são relações unárias, pois se aplicam a apenas um objeto (uma pessoa), indicando uma propriedade simples de sim/não, como "Sara é uma mulher". Em contraste, uma relação binária, como progenitor, define um relacionamento entre pares de objetos. Alternativamente, podemos expressar a mesma informação usando uma relação binária chamada sexo, que associa cada pessoa ao seu gênero: • sexo(sara,feminino). • sexo(abraão,masculino). • sexo(isaque,masculino). • sexo(ismael,masculino). • sexo(esaú,masculino). • sexo(jacó,masculino). • sexo(josé,masculino). Para representar a afirmação “Sara é uma mulher” em Prolog, podemos usar diferentes abordagens, cada uma com suas próprias vantagens e limitações. A primeira opção é mulher(sara)., que permite responder à pergunta “Quem é mulher?”, mas não permite responder “Qual o sexo de Sara?”. Outra opção é sexo(sara, feminino)., que permite responder tanto “Quem é mulher?” quanto “Qual o sexo de Sara?”, mas não 7 Lógica Matemática permite responder “Qual a propriedade de Sara que tem o valor feminino?”. Uma abordagem mais abrangente é propriedade(sara, sexo, feminino)., que utiliza uma representação de objeto-atributo-valor, permitindo responder a todas as perguntas, como “Quem é mulher?”, “Qual o sexo de Sara?” e “Qual a propriedade de Sara que tem o valor feminino?”. Essa última abordagem é mais flexível para consultas complexas. Para estender o programa em Prolog, podemos introduzir a relação filho_geral como o inverso da relação progenitor. Uma forma de fazer isso é definir filho_geral de maneira semelhante à relação progenitor, enumerando uma lista de fatos, como: • filho_geral(isaque,sara). • filho_geral(isaque,abraão). • filho_geral(ismael,abraão). No entanto, podemos definir a relação filho_geral de forma mais elegante: para todo X e Y, Y é um filho_geral de X se X é um progenitor de Y. Em Prolog, essa regra é escrita como: • filho_geral(Y, X) :- progenitor(X, Y). Essa cláusula pode ser lida como: "Para todo X e Y, se X é progenitor de Y, então Y é filho_geral de X". Em Prolog, cláusulas como filho_geral(Y, X) :- progenitor(X, Y). são chamadas de regras (rules). A diferença importante entre fatos e regras é que um fato é sempre verdadeiro de forma incondicional, enquanto regras especificam coisas que são verdadeiras apenas se alguma condição for satisfeita (Figura 7.3). Figura 8.3. A imagem mostra a estrutura de uma regra em Prolog. A cabeça (filho_geral(Y, X)) é a conclusão da regra, e o corpo (progenitor(X, Y)) é a condição necessária para que a conclusão seja verdadeira. O operador :- separa a cabeça (lado esquerdo) do corpo (lado direito). 8 Lógica Matemática Para incluir a especificação da relação mãe em Prolog, usamos o seguinte fundamento lógico: "Para todo X e Y, X é a mãe de Y se X é um progenitor de Y e X é uma mulher." Traduzindo para Prolog, isso fica: • mãe(X, Y) :- progenitor(X, Y), mulher(X). A vírgula entre duas condições indica uma conjunção, significando que ambas as condições devem ser verdadeiras para que a regra seja aplicada. Em Prolog, uma regra é composta por uma cabeça e um corpo, conectados pelo símbolo :-, chamado de "neck", formado por dois pontos e um hífen. Esse símbolo é lido como "se". Por exemplo, na regra mãe(X, Y) :- progenitor(X, Y), mulher(X)., lê-se que "X é mãe de Y se X é progenitor de Y e X é mulher". 8.7 Grafos Definindo Relações Relações como progenitor, filho_geral e mãe podem ser representadas visualmente por diagramas que seguem algumas convenções (Figura 7.4). Nesses diagramas: • Nós nos grafos correspondem a objetos (argumentos das relações); • Arcos entre nós correspondem a relações binárias (2 argumentos); • Arcos são orientados apontando do primeiro argumento da relação para o segundo argumento; • Relações unárias são indicadas nos diagramas simplesmente marcando os objetos correspondentes com o nome da relação; • As relações sendo definidas são representadas por arcos tracejados. Figura 7.4. A imagem apresenta três diagramas de relações familiares em Prolog. No primeiro diagrama, X é progenitor de Y (indicado por um arco sólido), e Y é filho_geral de X (representado por um arco tracejado). No segundo diagrama, X é progenitor de Y e também é uma mulher, formando a relação de mãe com Y (indicado pelo arco tracejado). No terceiro diagrama, X é progenitor de Y, que por sua vez é progenitor de Z; assim, X é considerado avô_geral de Z (também indicado por um arco tracejado). 9 Lógica Matemática Cada diagrama deve ser interpretado da seguinte forma: se as relações representadas pelos arcos sólidos são verdadeiras, então a relação indicada pelo arco tracejado também é verdadeira. Assim, a relação avô_geral pode ser expressa em Prolog como: • avô_geral(X,Z) :- progenitor(X,Y), progenitor(Y,Z). Isso significa que X é avô_geral de Z se X é progenitor de Y e Y é progenitor de Z. 8.8 Layout de um Programa Prolog Prolog oferece liberdade na formatação do layout do programa. No entanto, é importante que o código tenha um aspecto compacto e, principalmente, seja fácil de ler. Por isso, é uma prática comum escrever a cabeça de uma cláusula e cada condição do corpo em linhas separadas. Além disso, as condições são normalmente deslocadas para separar visualmente a cabeça do corpo da regra, facilitando a leitura e compreensão do programa. Por exemplo, arelação avô_geral(X, Z) :- progenitor(X, Y), progenitor(Y, Z). deve ser escrita em um formato mais legível: A relação irmão pode ser definida da seguinte maneira: "Para todo X e Y, X é irmão de Y se ambos têm um progenitor em comum e X é um homem." Em Prolog, isso é expresso como: Note que a expressão "ambos X e Y têm um progenitor em comum" é representada ao definir que algum Z é o progenitor de X e, ao mesmo tempo, o progenitor de Y. Programas em Prolog podem ser expandidos facilmente pela adição de novas cláusulas, que podem ser de três tipos: fatos, regras e perguntas. Fatos declaram algo que é sempre verdadeiro, enquanto regras definem algo que é verdadeiro sob determinadas avô_geral(X, Z) :- progenitor(X, Y), progenitor(Y, Z). irmão(X, Y) :- progenitor(Z, X), progenitor(Z, Y), homem(X). 10 Lógica Matemática condições. Perguntas permitem ao usuário consultar o programa sobre o que é verdadeiro. Cada cláusula em Prolog possui uma cabeça e um corpo; o corpo é uma lista de condições separadas por vírgulas, indicando uma conjunção. Fatos têm uma cabeça e um corpo vazio; perguntas contêm apenas o corpo; e regras possuem uma cabeça e um corpo não vazio. Durante a computação em Prolog, uma variável pode ser substituída por um objeto, o que significa que a variável foi instanciada. Variáveis são universalmente quantificadas e geralmente interpretadas como “Para todo”. No entanto, leituras alternativas são possíveis para variáveis que aparecem apenas no corpo da cláusula. Por exemplo, a regra temfilhos(X) :- progenitor(X, Y). pode ser lida de duas formas: "Para todo X e Y, se X é progenitor de Y, então X tem filhos" ou "Para todo X, X tem filhos se existe algum Y tal que X é progenitor de Y". 8.9 Regras Recursivas Uma regra recursiva em programação (e especialmente em Prolog) é uma regra que se refere a si mesma para resolver problemas que podem ser divididos em subproblemas semelhantes. Em outras palavras, uma regra recursiva utiliza uma definição baseada em um caso base (não recursivo) e um caso recursivo. As regras recursivas são úteis para definir relações hierárquicas, como relações de parentesco (ancestralidade), estruturas de dados (árvores e listas), e para resolver problemas complexos que podem ser decompostos em subproblemas menores de forma repetitiva. Para definir uma relação de ancestral em Prolog, podemos usar regras recursivas. Regras recursivas podem ser aplicadas para definir a relação de ancestralidade. Essa relação será estabelecida por meio de duas regras principais: a primeira regra será o caso base, que não é recursivo, e a segunda será o caso recursivo. Assim, para todo X e Z, X é considerado um ancestral de Z se X for um progenitor de Z. Em termos de notação, isso é representado como: ancestral(X, Z) :- progenitor(X, Z) (Figura 7.5). 11 Lógica Matemática Figura 8.5. A imagem mostra dois elementos, X e Z, onde uma seta sólida indica que X é o "progenitor" de Z e uma seta tracejada indica que X é o "ancestral" de Z. Para todo X e Z, X é um ancestral de Z se existe algum Y tal que X é um progenitor de Y e Y é um ancestral de Z. Formalmente, isso pode ser representado como: ancestral(X, Z) :- progenitor(X, Y), ancestral(Y, Z) (Figura 7.6). Figura 8.6. A imagem mostra um diagrama onde "X" é progenitor de "Y", e "Y" é progenitor de outros nós intermediários até "Z". Uma seta tracejada conecta "X" a "Z", indicando que "X" é um ancestral de "Z" através dessa cadeia de progenitores. O predicado ancestral (X, Z) é definido com base em duas regras: • Caso base: ancestral(X, Z) :- progenitor(X, Z). Isso significa que X é ancestral de Z se X é progenitor direto de Z. • Caso recursivo: ancestral(X, Z) :- progenitor(X, Z), ancestral(Y, Z). Isso significa que X é ancestral de Z se X é progenitor de Y e Y é ancestral de Z. Podemos então perguntar: quais são os descendentes de Sara? Ao realizar a consulta ?- ancestral(sara, X)., obtemos: 12 Lógica Matemática • X = isaque; • X = esaú; • X = jacó; • X = josé. Isso indica que os decendentes de Sara são Isaque, Esaú, Jacó e José. 13 Lógica Matemática Vídeos Vídeo 01 – Como usar Prolog https://www.youtube.com/watch?v=omLANiMqbuY Vídeo 02 – Introdução a Prolog https://www.youtube.com/watch?v=omLANiMqbuY Vídeo 03 - Iniciando Prolog https://www.youtube.com/watch?v=ycHLj12bm0M Vídeo 04 - Prolog curso completo em videoaulas (ver até a 5ª aula) https://www.youtube.com/watch?v=x_ahRnd1gTI&list=PLZ-Bk6jzsb- OScKa7vhpcQXoU2uxYGaFx https://www.youtube.com/watch?v=omLANiMqbuY https://www.youtube.com/watch?v=omLANiMqbuY https://www.youtube.com/watch?v=ycHLj12bm0M https://www.youtube.com/watch?v=x_ahRnd1gTI&list=PLZ-Bk6jzsb-OScKa7vhpcQXoU2uxYGaFx https://www.youtube.com/watch?v=x_ahRnd1gTI&list=PLZ-Bk6jzsb-OScKa7vhpcQXoU2uxYGaFx 14 Lógica Matemática Atividade Avaliativa 06: Após a leitura da apostila referente a “Introdução PROLOG”, responder a tarefa repassada no ambiente Virtual SIGAA. Vale 1,0 ponto. Acompanhe o Fórum interativo no AVA-SIGAA. Por meio do Fórum você poderá tirar dúvidas quanto ao conteúdo da disciplina e das Atividades Avaliativas. 15 Lógica Matemática e Aula 08: Prova NAP2 1. BISPO, C. A. F; CASTANHEIRA, L. B; FILHO, O. M. S. F. Introdução a Lógica Matemática. São Paulo: Cengage Learning, 2011. 2. SOUZA, J. N. Lógica para Ciência da Computação – Uma Introdução Sucinta. 2ª. Edição. Rio de Janeiro: Elsevier, 2008. 3. GERSTING, J. L. Fundamentos Matemáticos para a Ciência da Computação. 5ª. Edição. Rio de Janeiro: LTC, 2004. 4. PALAZZO, A. M. Introdução à Programação PROLOG. Pelotas: UCPEL, 1997. Nesta Unidade I, vimos que ... Os sistemas de informação podem assumir os mais diversos formatos, desde os mais simples até os mais extremamente complexos, mas continuam presentes e indispensáveis em todos os segmentos da sociedade e seu entendimento é primordial para quem vai se tornar um profissional da área. Pudemos aprender nesta unidade: • Sistemas de Informações Gerenciais nas Organizações; • Sistemas de Suporte à Decisão nas Organizações; • Sistema de Suporte Executivo nas Organizações; Nesta Unidade II, vimos ... Estudamos como verificar se as fórmulas proposicionais seguem um padrão de sintaxe correto, garantindo a sua validade. Também exploramos as tabelas verdade, entendendo sua importância, como construí-las e analisando exemplos práticos de aplicação. Além disso, abordamos os princípios básicos da programação lógica, incluindo exemplos que ilustram sua aplicação nesse paradigma de programação. Discutimos conceitos fundamentais, como o funcionamento da lógica, a formulação de expressões, fatos e regras, destacando a utilidade e a estrutura desse tipode programação. 16 Lógica Matemática Aula 09: Prova NAP2 Objetivo (s) da Aula 09: realizar a avaliação NAP2. Aula 12: Avaliação Substitutiva Nota de Avaliação Parcial – NAP2: será disponibilizada no SIGAA uma atividade de PROLOG e Lógica Matemática valendo 6,0 (seis pontos). 19h às 22h - Atividade assíncrona através do Módulo Atividades do SIGAA (AVA) 17 Lógica Matemática Aula 10: Prova AS Objetivo (s) da Aula 10: realizar a avaliação AS. Avaliação Substitutiva: será disponibilizada no SIGAA – como tarefa - sendo uma prova com 10 (dez) questões de múltipla escolha valendo 10,0 (dez pontos). A prova cai todo o conteúdo da disciplina.