Computação

L´ogica e aplica¸c˜oes: Matem´atica, Ciˆencia da
Computa¸c˜ao e Filosofia
(Vers˜ao Preliminar - Cap´ıtulos 1 a 5)
W.A. Carnielli1, M.E. Coniglio1 e R. Bianconi2
1Departamento de Filosofia
Universidade Estadual de Campinas
C.P. 6133, CEP 13081-970
Campinas, SP, Brasil
E-mail: {carniell,coniglio}@cle.unicamp.br
2Instituto de Matem´atica e Estat´ıstica
Universidade de S˜ao Paulo
C.P. 66281, CEP 05315-970
S˜ao Paulo, SP, Brasil
E-mail: [e-mail]

c Todos os direitos reservados
(Coment´arios e sugest˜oes s˜ao muito bem-vindos)
16 de maio de 2005
Sum´ario
1 Hist´orico e Paradoxos 3
1.1 Os Paradoxos L´ogicos e o Infinito . . . . . . . . . . . . . . . . 3
1.2 Algumas Propriedades Paradoxais do Infinito . . . . . . . . . 4
1.2.1 O Paradoxo de Galileu . . . . . . . . . . . . . . . . . . 4
1.2.2 O Passeio de Cantor e os tipos distintos de infinito . . 5
1.2.3 O Hotel de Hilbert . . . . . . . . . . . . . . . . . . . . 8
1.2.4 O Lema de K¨onig . . . . . . . . . . . . . . . . . . . . 8
1.3 Os Paradoxos L´ogicos . . . . . . . . . . . . . . . . . . . . . . 9
1.3.1 O significado dos paradoxos . . . . . . . . . . . . . . . 9
1.3.2 Paradoxos e antinomias mais conhecidos . . . . . . . 11
1.3.3 O que podemos aprender com os paradoxos? . . . . . 14
2 Linguagem e Semˆantica da l´ogica proposicional cl´assica 15
2.1 Linguagens proposicionais . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Assinaturas e linguagens . . . . . . . . . . . . . . . . . 15
2.1.2 Indu¸c˜ao estrutural . . . . . . . . . . . . . . . . . . . . 20
2.1.3 A linguagem da LPC . . . . . . . . . . . . . . . . . . . 24
2.1.4 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2 Semˆantica da LPC . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.1 Semˆantica dos conectivos . . . . . . . . . . . . . . . . 29
2.2.2 Tautologias, contradi¸c˜oes e contingˆencias . . . . . . . 33
2.2.3 Formas normais . . . . . . . . . . . . . . . . . . . . . . 37
2.2.4 Conjuntos