Lógica para Ciência da Computação
By João Nunes de Souza
- Publisher: Campus
- Number of Pages: 317
- Publication Date: 2002
- ISBN-10 / ASIN: 8535210938
- ISBN-13 / EAN: 9788535210934
Prefácio
O que é Lógica? O que significa estudar Lógica? Qual a sua definição? Ao iniciar este estudo, vários autores apresentam definições populares sobre o tema. Conforme [Mendelson, 1987]: Lógica é a análise de métodos de raciocínio. No estudo desses métodos a Lógica está interessada principalmente na forma e não no conteúdo dos argumentos. Considere por exemplo os argumentos: · Todo homem é mortal. Sócrates é um homem. Portanto, Sócrates é mortal. · Todo cão late. Totó é um cão. Portanto, Totó late. Do ponto de vista da Lógica, esses argumentos têm a mesma estrutura ou forma. · Todo X é Y. Z é X. Portanto, Z é Y. A Lógica é o estudo de tais estruturas. Alguns autores [Andrews, 1996] dizem que a Lógica é essencialmente o estudo da natureza do raciocínio e as formas de incrementar sua utilização. No excelente livro Convite à Filosofia [Chauí, 2002] é apresentada a definição: “Lógica: conhecimento das formas gerais e regras do pensamento correto e verdadeiro, independentemente dos conteúdos pensados; regras para demonstração científica verdadeira; regras para pensamentos não-científicos; regras sobre o modo de expor o conhecimento; regras para verificação da verdade ou falsidade de um pensamento, etc.” A finalidade deste livro não é o estudo da Lógica do ponto de vista filosófico, mas a apresentação dos principais fundamentos da Lógica clássica necessários aos estudantes de Computação e áreas correlatas. Entretanto, mesmo considerando este contexto restrito, ao longo do estudo proposto neste livro, o leitor é convidado a checar a definição acima sempre que possível. O leitor verificará que as regras citadas na definição da Lógica têm aplicações imediatas em Computação. A Lógica clássica considerada neste livro é apenas uma entre as inúmeras lógicas existentes. Entretanto, o seu estudo é importante, pois é a introdução clássica ao estudo de todas as lógicas. Dessa forma, este livro é também uma introdução ao estudo dos fundamentos de Lógica Matemática e de suas aplicações em inúmeras áreas da Computação, Matemática, Filosofia, etc. O livro não requer nenhum pré-requisito, nem mesmo maturidade matemática, podendo ser utilizado como texto em disciplinas introdutórias de graduação. Mesmo sendo introdutório, dá-se ênfase na apresentação matemática rigorosa e no desenvolvimento de demonstrações mais elementares. Algumas demonstrações que requerem técnicas mais avançadas são omitidas como, por exemplo, o teorema da completude na Lógica de Predicados. Nestes casos são relatadas apenas algumas análises de resultados. O livro começou a ser escrito a partir de notas de aulas das disciplinas de Lógica para Ciência da Computação, lecionadas na graduação e na pós-graduação, a partir de 1991 até os dias atuais, na Universidade Federal de Uberlândia. Em mais de dez anos lecionando Lógica para alunos de graduação e pós-graduação, foi possível determinar com clareza suas dificuldades. Nesse sentido, podem ser omitidas demonstrações que requerem habilidades técnicas dos alunos iniciantes, mas os conceitos fundamentais devem ser enfatizados. Para os alunos da pós-graduação o enfoque é diferente. Neste caso são consideradas com detalhes todas as demonstrações; os exercícios mais difíceis e o livro podem ser complementados com outras referências. Partindo de inúmeras dúvidas dos alunos e de questões elaboradas em provas, são propostos mais de 700 itens de exercícios com sugestões e soluções dos mais importantes. Eles formam o complemento da teoria apresentada e são indispensáveis para um melhor aprendizado da Lógica. O material elaborado durante as aulas tomou a forma de livro em janeiro de 1997, em Sergipe. Inicialmente nos quiosques das praias de Atalaia e Sarney, em Aracaju, sob a brisa do mar e tomando água de coco. Depois, no sertão, em Nossa Senhora das Dores, sob um calor de 39,9° C. Este livro é dividido em duas partes. Na primeira, é considerada a Lógica Proposicional clássica e na segunda a Lógica de Predicados clássica. A divisão da Lógica em Proposicional e de Predicados é uma divisão freqüentemente seguida pela maioria dos autores. Em cada parte, o estudo da Lógica segue, fundamentalmente, os três passos básicos: 1. Especificação de uma linguagem, a partir da qual o conhecimento é representado. Nesta representação são considerados os conceitos de sintaxe e semântica associados à linguagem. 2. Estudo de métodos que produzam ou verifiquem as fórmulas ou argumentos válidos. Tem-se a verificação do conceito semântico de validade a partir de expressões sintáticas da linguagem. 3. Definição de sistemas de dedução formal, onde são consideradas as noções de prova e conseqüência lógica. A noção de prova estabelece formas para a derivação de novos argumentos a partir daqueles representados previamente, o que também define a noção de conseqüência lógica. O Capítulo 1 considera o estudo da linguagem da Lógica Proposicional, que corresponde ao passo 1 no estudo da Lógica Proposicional. A semântica da Lógica Proposicional é considerada nos Capítulos 2 e 3. O estudo de alguns mecanismos que verificam argumentos válidos é visto no Capítulo 4. O Capítulo 5 apresenta um estudo introdutório do princípio da indução finita. Este é um dos principais conceitos utilizados em Matemática e Ciência da Computação, e sua utilização ocorre em várias partes do restante do livro. No Capítulo 6, por exemplo, que trata das relações semânticas dos conectivos da Lógica Proposicional, há várias demonstrações que utilizam o princípio da indução finita. No Capítulo 7 são considerados dois sistemas de dedução formal. Um sistema axiomático e o sistema de dedução natural de Gentzen. Há vários tipos de sistemas de dedução estudados na lógica clássica. Os sistemas formais apresentados no Capítulo 7 são simples e apresentam as noções de prova e conseqüência lógica, indicadas no passo 3 do estudo da Lógica. Concluindo o estudo da Lógica Proposicional, o Capítulo 8 considera os métodos de dedução tableaux semânticos e resolução na Lógica Proposicional, que são mais adequados à implementação em computadores. Na segunda parte do livro tem-se uma seqüência de passos análoga àquela apresentada até o Capítulo 8, só que neste caso é considerada a Lógica de Predicados. O Capítulo 9 apresenta a linguagem da Lógica de Predicados, considerando apenas os elementos sintáticos. A semântica e os mecanismos que verificam fórmulas válidas na Lógica de Predicados são considerados nos Capítulos 10 e 11. O Capítulo 12 apresenta uma extensão do sistema de dedução axiomática estudado no Capítulo 7, considerando conceitos da Lógica de Predicados. Nos Capítulos 13 e 13 são apresentados os sistemas de dedução tableaux semânticos e resolução na Lógica de Predicados. O último capítulo considera os métodos de dedução utilizados em programação lógica, que são casos particulares da resolução na Lógica de Predicados. Este livro pode ser utilizado como texto básico em diversas disciplinas de Lógica. Uma disciplina de dois semestres para alunos do início da graduação pode considerar até o Capítulo 8 no primeiro semestre e o restante do livro no segundo semestre. Em um curso elementar, demonstrações sobre completude e correção podem ser omitidas. Neste caso, são consideradas apenas demonstrações elementares que utilizam a indução finita. As demonstrações sobre equivalência de diferentes tipos de indução finita, por exemplo, são omitidas. Nos dois casos, é necessário enfatizar os exercícios, que são fundamentais para o entendimento dos conceitos apresentados. O material deste livro também pode ser utilizado em uma disciplina semestral de final de graduação, que apresentaria toda a Lógica Proposicional e de Predicados. Neste caso, talvez o tempo não seja suficiente para a apresentação de todos os conceitos, definições e soluções de exercícios em sala de aula. Uma boa parte de trabalho deve ser proposta aos alunos. Em uma leitura rápida, apenas considerando os conceitos fundamentais da Lógica, alguns capítulos como 5, 6, 11, 12 e 15 podem até ser omitidos, sem se comprometer, por isso, o entendimento do resto do livro. Em disciplinas de pós-graduação este livro pode ser utilizado como referência para a introdução dos conceitos. Nesse caso é recomendável complementar o estudo com outros livros que tratam de resultados e demonstrações que também são fundamentais na Lógica e que não são consideradas com profundidade neste livro. Finalmente, este livro pode ser utilizado não apenas por alunos de Ciência da Computação, mas por todos aqueles que se interessam pelo conhecimento da Lógica, como filósofos, matemáticos, físicos, engenheiros, advogados, etc. Agradeço aos meus alunos de Ciência da Computação da Universidade Federal de Uberlândia, aproximadamente 900, que nos últimos anos utilizaram este livro e deram sugestões para o seu aprimoramento. O pessoal da Faculdade de Computação também deve ser lembrado. A minha família é a lógica que fundamenta todo este trabalho servindo como inspiração. João Paulo e Tiago certamente ainda não compreendem o conteúdo deste livro, mas ajudaram. Meu tio sempre foi um padrão para o meu comportamento. Como reconhecimento, os nomes de vários alunos, amigos e colegas aparecem nos exercícios. | 
