Universidade Federal de Pernambuco (UFPE)
Centro de Informática (CIn)
Graduação em Ciência da Computação

IF312 - Lógica para Computação

Descrição:

Você sabe o que é:

consistência? decidibilidade? satisfatibilidade? conseqüência lógica? validade lógica? validade contingente?

De que trata o curso?

Uma introdução às técnicas do chamado raciocínio dedutivo usando as ferramentas da Lógica Matemática. A Lógica Matemática estuda as noções de validade e consistência de argumentos utilizando elementos da Matemática, tais como a teoria dos conjuntos e a álgebra booleana.

Após o curso, o estudante terá um conhecimento mínimo sobre: sistemas formais; relação entre linguagens formais e as "realidades" que elas descrevem (modelos e interpretações); validade de argumentos; satisfatibilidade; sistemas de valoração-verdade; inconsistência; corretude, completude e incompletude de sistemas dedutivos; conseqüência lógica; lógica de predicados; decidibilidade.

Em poucas palavras

Estudaremos:
(i) potencialidades (e limites) do método formal-dedutivo de representação e raciocínio sobre uma "realidade";
(ii) a fundamentação das noções de prova e refutação da validade de argumentos;
(iii) os fundamentos da representação simbólica, e da noção de conseqüência lógica.

Importância para o profissional da Informática

A noção de procedimento efetivo, que deu origem às primeiras "máquinas abstratas de computação efetiva" (como, por exemplo, a chamada Máquina de Turing, o primeiro modelo de computador programável por software, e que deu origem à chamada Tese de Church que afirma que qualquer função efetivamente computável pode ser computável por uma Máquina de Turing apropriadamente definida) está intimamente ligada à noção de "dedução em um sistema formal (simbólico)", como concebido por Gottlob Frege, o mentor da Lógica Moderna, justamente porque esta última veio como a implementação do sonho do filósofo Leibniz (século XVII) de criar uma máquina de verificação da validade de argumentos.

Além do mais, o conceito de máquina de processamento simbólico e as noções de representação e manipulação simbólica, fundamentais para qualquer estudioso da ciência da computação, são estudados no curso de forma abstrata e bastante geral, independente da linguagem utilizada para a representação.

(Para algumas considerações sobre a influência da Lógica Matemática na fundamentação dos conceitos básicos da Ciência da Computação, ver História da Computação (por Cléuzio Fonseca Filho), particularmente o item Evolução dos Conceitos.)

Conteúdo do Curso
(0. Revisão (quando necessário!): Estruturas Matemáticas (ordens parciais; reticulados; ideais; filtros))
1. Lógica Proposicional.
2. Lógica de Predicados.

Bibliografia Básica
1. Logic and Structure, Dirk van Dalen, Springer, 3rd augmented edition, 1994 (Corrected 2nd printing 1997).
2. A Shorter Model Theory, Wilfrid Hodges, Cambridge University Press, 1997.
3. Language, Proof and Logic, Jon Barwise & John Etchemendy, Seven Bridges Press, 2000. (Acompanha o software educativo Tarski's World)

(Obs.: Visite a página "Ementa" para ver mais detalhes sobre as fontes bibliográficas.)
2001.2 2001.1 2000.2 2000.1 1999.2 1999.1 1998.2 1998.1 1997.2 1997.1

Última atualização: 14 de Dezembro de 2001, 11:10hs