Introdução à Lógica Computacional – TIN0105

Obrigatória – 60 horas – 4 créditos
Pré-requisitos: nenhum
Professor Responsável: Alexandre Andreatta

Objetivos da Disciplina

Capacitar o aluno a utilizar as linguagens proposicional e de predicados para expressar conhecimento. Prepara o aluno para aplicar métodos de teste de consistência de conjuntos de proposições compostas ou de sentenças nas duas linguagens. Qualificar o aluno na demonstração a validade de argumentos. Habilitar o aluno a fazer demonstrações simples por indução matemática. Capacitar o aluno a reconhecer e realizar definições recursivas, e a calcular as formas fechadas de funções recursivas simples.

Ementa

Lógica proposicional e álgebra booleana. Lógica de predicados. Indução. Recursão.

Conteúdo Programático

• Lógica Formal
  • Proposições, fórmulas bem formadas e Equivalências. Tautológicas. Formas Normais (Conjuntiva e Disjuntiva). Definição de interpretação. Tabela verdade e árvores de decisão.
  • Validade de Argumentos Proposicionais. Definição de Sistemas Formais. Completude e correção de sistemas formais.
  • Lógica Proposicional: Regras de inferência da dedução Natural. Regras adicionais. Regra da Resolução e uso de refutação.
  • Correlação entre Lógica Proposicional e Álgebra Booleana. Minimização de termos de funções booleanas na forma normal disjuntivas: mapas de Karnaugh e Algoritmo de Quine-McCluskey.
  • Quantificadores, Predicados e expressividade da linguagem de predicados com funções e sem funções no conjunto universo. Definição do conjunto de fórmulas da linguagem.
  • Definição de interpretação em Lógica de Predicados.
  • Definição de variáveis livres, sentenças, substituição de termos.
  • Equivalências tautológicas relativas a fórmulas com quantificadores.
  • Validade de Argumentos com Predicados.
  • Lógica de Predicados: regras de inferência compartilhadas com a lógica proposicional. Regras de inferência específicas: particularizações e generalizações universais e existenciais.
  • “Noções de Programação em Lógica” (não obrigatório).
• Indução
  • Definição
  • Primeiro Princípio da Indução; Segundo Princípio da Indução
  • Demonstrações por indução
• Recursão
  • Definições recursivas de conjuntos, seqüências, operações e algoritmos
  • Resolução de equações recursivas simples por expansão
  • Resolução de recursões lineares homogêneas (não obrigatório)
  • Máximo Divisor Comum, Algoritmo de Euclides

Metodologia

Aulas expositivas de conteúdo teórico, com a realização de exercícios ao longo das aulas.

Avaliação

São três ao longo do período constando dos assuntos ministrados até o momento da prova. Se esta média M for maior ou igual a 7,0 (sete) o aluno estará aprovado, caso contrário deverá realizar prova final (PF). Neste caso, a nota final será composta pela média entre PF e M. Se a média final for inferior a 5,0 (cinco) o aluno estará reprovado, sendo superior ou igual, estará aprovado.

Bibliografia  Básica

• ROSEN, Kenneth H., Matemática Discreta e suas Aplicações, 6ªEedição. São Paulo: Mc Graw Hill.
• HUTH e RYAN, M., Lógica em Ciência da Computação – Modelagem e Argumentação Sobre Sistemas. LTC, 2008.
• ENDERTON, H., A Mathematical Introduction to Logic. 2ª Ed., Harcourt/Academic Express, 2001.

Bibliografia Complementar

• GERSTING, Judith L., Fundamentos Matemáticos para a Ciência da Computação. 5ªEed. ou superior. Rio de Janeiro: LTC.
• CORREIA DA SILVA, F.S.,FINGER,M.,MELO,A.C.V., A Lógica para Computação. Editora Thomson.
• CLOCKSIN, W.F., MELLISH,C.S., Programming in Prolog. 5th Ed., Springer, 2003.
• SOUZA, João Nunes de. Lógica para Ciência da Computação: fundamentos de linguagem, semântica e sistemas de dedução. Editora Campus