Universidade Federal de Pernambuco (UFPE)

Centro de Informática (CIn)

Graduação em Ciência da Computação


IF673 - 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, 4th edition, 2004.
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.)

Semestres


Última atualização: 10 de Fevereiro de 2017, 12:15pm GMT-3