Universidade Federal de Pernambuco (UFPE)
Centro de Informática (CIn)
Graduação em Ciência da Computação
consistência? decidibilidade? satisfatibilidade? conseqüência lógica? validade lógica? validade contingente?
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.
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.
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