Universidade Estadual de Feira de Santana

Departamento de Ciências Exatas

Período Letivo 2011.1

Plano de Ensino

EXA 802 – LÓGICA PARA COMPUTAÇÃO – Turmas 01

prof. Angelo Loula e prof. Haroldo Benatti

Notas de Aula: ver Anexos ao final da página

Carga Horária

60 horas

Pré-requisitos

Não tem

Ementa

Sentido lógico-matemático convencional dos conectivos. Argumentos. Lógica sentencial. Regras de formação de fórmulas. Sistemas dedutivos. Completeza, consistência e coerência. Decidibilidade da lógica sentencial. A lógica de predicados de primeira ordem. Valores-verdade. Funções de avaliação.

Apresentação

A lógica matemática está presente na computação desde o início da área, fundamentando a teoria da computação, permitindo provas automáticas de argumentos, representando conhecimento, servindo de base para a álgebra relacional e banco de dados, especificando e verificando propriedades de programas, além de outras possíveis relações. Como colocam Reeves e Clarke (2003, p.1):

There are many reasons why a computer scientist should need to study logic. Not only has it historically formed the roots of computer science, both Church's and Turing's work being motivated by the decision problem for first-order logic, but nowadays we are finding conversely that computer science is generating an explosion of interest in logic, with the desire to automate reasoning and the necessity to prove programs correct.

Basically, logic is about formalizing language and reasoning, and computer science addresses similar problems with the extra task, having formalized them, of expressing those formalizations, in the technical sense of producing mechanisms which follow the rules that they lay down. This, indeed, has led to the recent use of computer science for investigating logics in an experimental way, exploring some of them much more thoroughly than was possible when the 'computer' was a person rather than a machine.

Objetivos, Habilidades e Competências

Objetivo Geral:

Compreensão dos cálculos da lógica proposicional e da lógica de primeira ordem.

Objetivos específicos / Habilidades:

Formalização de problemas e sentenças em lógica seguindo sintaxe;

Determinação de valor verdade de fórmulas e argumentos baseando-se na semântica;

Avaliação de validade de fórmulas e argumentos usando sistemas de prova;

Compreensão e aplicação de conceitos da lógica matemática.

Competências:

Desenvolvimento do raciocínio lógico-matemático, baseado no rigor e na observação;

Desenvolvimento de pensamento dedutivo;

Expressar-se com objetividade, clareza e precisão.

Habilidades:

Formalizar linguagem natural em linguagem formal;

Avaliar sentenças e argumentos quanto a sua validade;

Deduzir conseqüências lógicas de sentenças válidas.

Conteúdo Programático

Lógica Proposicional (Sentencial):

Introdução: argumento, valor verdade, conseqüência lógica, equivalência, inferência;

Sintaxe: alfabeto, fórmulas, tradução;

Semântica: modelo, interpretação, validade, tautologia, tabela-verdade;

Formas Normais (conjuntiva e disjuntiva);

Sistemas de Prova:

    Argumentos e Regras de Inferência;

    Sistema de dedução natural;

    Tablô; 

    Resolução; 

          Correção, Completude, Decidibilidade;

Lógica de Primeira Ordem (Predicativa):

Introdução: compromisso ontológico;

Sintaxe: quantificadores e tradução;

Semântica: domínios e interpretação;

Sistemas de Prova:

            Dedução Natural;

            Tablô;

            Resolução e Unificação;

Tópicos Avançados em Lógica.

Metodologia

Aulas teóricas expositivas e aulas práticas de exercícios.

Avaliação

Neste semestre, faremos três provas teóricas. A média das provas corresponderá a média final.

Calendário

Acesse também Portal do Aluno.

Referências

Bibliografia Básica:

 Cezar Mortari. Introdução à Lógica. São Paulo: Editora da UNESP, 2001. (Número de Chamada: 16 M861)

 João Nunes de Souza. Lógica para ciência da computação: fundamentos de linguagem, semântica e sistemas de dedução. Rio de Janeiro: Campus, 2002. (Número de Chamada: 004.42 S716)

 Flávio Soares Correa da Silva, Marcelo Finger, Ana Cristina Vieira de Melo. Lógica para Computação. 1. ed. São Paulo: Thomson Learning, 2006. (Número de Chamada: 004.42 S58l)

 Paulo Roberto Margutti Pinto.  Introdução a lógica simbólica.   Belo Horizonte: Ed. UFMG, 2001. (Número de Chamada: 16 P73i)

Leituras Complementares:

 Jair Minoro Abe, Alexandre Scalzitti, João Inácio da Silva Filho. Introdução à lógica para a ciência da computação. São Paulo: Arte & Ciência, 2002. (Número de Chamada: 51:681.3.06 A119i)

 Stuart Russell, Peter Norvig. Inteligência artificial. Rio de Janeiro : Elsevier, 2004. (Número de Chamada: 004.8 R925a)

 Guilherme Bittencourt. Inteligência artificial: ferramentas e teorias. Florianópolis: Ed. da UFSC, 2001. (Número de Chamada: 004.8 B543i 2. ed)

 J. Gallier. Logic for Computer Science: Foundations of Automatic Theorem Proving. Nova Iorque: J. Wiley & Sons, 2003. Disponível em: http://www.cis.upenn.edu/~jean/gbooks/logic.html

 Steve Reeves, Mike Clarke. Logic for Computer Science. 2003. Nova edição de Addison-Wesley, 1990. Disponível em: http://www.cs.waikato.ac.nz/~stever/LCS.html

 Michael Huth, Mark Ryan.  Lógica em ciência da computação: modelagem e argumentação sobre sistemas.  2. ed Rio de Janeiro: LTC, 2008 (Número de  Chamada: 004 H967l 2. ed)

 John Nolt, Dennis Rohatyn. Lógica. São Paulo: Makron Books do Brasil, McGraw-Hill, 1991.