Ementa

• Introdução à Programação em Lógica (PL).
• Aplicações de PL à Inteligência Artificial.
• Linguagens Lógicas Concorrentes.
• Linguagens Lógicas com Restrições.
• Implementação de Linguagens Lógicas.
• Paralelismo em Sistemas de PL.

Bibliografia

• Peter M. Kogge, ``The Architecture of Symbolic Computers'', McGraw-Hill.
• William Clocksin and Chris Mellish, ``Programming in Prolog'', Springer-Verlag.
• Leon Sterling and Ehud Shapiro, ``The Art of Prolog'', MIT Press.
• Ivan Bratko, ``Prolog Programming for Artificial Intelligence'', Addison-Wesley.
• Hassan Aït-Kaci, ``Warren's Abstract Machine - A Tutorial Reconstruction'', MIT Press.
• Pascal van Hentenrick, ``Constraint Satisfaction in Logic Programming'', MIT Press.
• Steve Gregory, ``Parallel Logic Programming in Parlog'',

Bibliografia

• Peter van Roy, ``1983-1993-The Wonder Years of Sequential Prolog Implementation'', JLP, 1994, V. 20, pp. 385-441.
• Ehud Shapiro, ``The Family of Concurrent Logic Programming Languages'', ACM Computing Surveys, 1989, V. 21, N. 3, pp. 412-510.

Motivação

• Linguagem de alto nível.
• Poder de expressão.
• Formal.
• Manipulação fácil de símbolos.
• Prova de Teoremas e Processamento de Linguagem Natural.

Prova de Teoremas ou Dedução Automática

• Representação do conhecimento de forma declarativa, em lógica matemática.
• Mecanismo de inferência (provador de teoremas) deduz soluções para os problemas.
• Exceto para classes de problemas muito restritas, o espaço de busca pode crescer exponencialmente.
• Requer estratégias de busca inteligentes.
• Pouco sucesso após muito trabalho nos anos 60.

O que faz programação em lógica ser diferente de prova de teoremas?

• Programação em Lógica é Programação!
• Programador se preocupa com a eficiência e praticidade (roda e termina em tempo polinomial?)
• Utilização de uma lógica restrita (Cláusulas de Horn).
• Mecanismo de inferência simples e eficiente.
• Algoritmo = Lógica + Controle.
• Controle pode ser ignorado quando ``lemos'' o programa de forma declarativa.

Conceitos Básicos em Lógica

• Computação: método de ``raciocínio formal''.
• ``objetos'' do raciocínio: sentenças sobre o mundo ( fatos ou regras).
• ``Computação lógica'': usa o conjunto de sentenças para predizer ou computar a validade ou falsidade de outras senetenças.

Conceitos Básicos em Lógica

• Modelo computacional básico: máquina de inferência.
• Fatos: entidades básicas em lógica, assume-se que são verdadeiros (axiomas).
• Exs: o preço deste livro é 49 reais, às 5 horas do dia 13/03/98 está chovendo, o fatorial de 3 é 6.
• Forma de expressar fatos: relações.
• Relação: conjunto de tuplas.
• Cada tupla: conjunto de objetos que compartilham as mesmas características ou possuem a mesma propriedade.
• Ex: relação cor-do-cabelo(Ines,cast-escuro)

Conceitos Básicos em Lógica

• Outras formas de relações: ``Se A é um fato, então B também é um fato''.
• Contradições não são permitidas: A é um fato e A não é um fato.
• Uma tupla não pode estar numa relação e ao mesmo tempo não estar.
• Inferência: conclui que uma sentença é verdadeira através da verificação de que outras sentenças são verdadeiras, sem ter que procurar exaustivamente pelo conjunto total de sentenças. Ex: Se x é pai de alguma criança, então x é pai.

  Vítor é pai de Mariana.

• Não necessário procurar por todas as tuplas e-pai para provar que Vítor é pai.

1#1

Sistemas de Lógica Formal

• Sintaxe + Semântica.
• Fórmulas bem formadas: expressões sintaticamente válidas na linguagem.
• Conjunto de símbolos permitidos:
  • constantes;
  • funções;
  • predicados;
  • variáveis lógicas;
  • conectivos lógicos: implicação, conjunção, disjunção, negação, relacionais;
  • quantificadores.

Regras de Inferência

• Fórmulas bem formadas: expressões sintaticamente válidas na linguagem.