Fundamentos da matemática

Universidade Federal de Sergipe
Centro de Ciencias Exatas e Tecnologia
Departamento de Matemática

Material Didático para a disciplina

Fundamentos de Matemática
Paulo de Souza Rabelo

Aracaju - SE
2013

Sumário

1

Introdução

1

2

Noções de Lógica
2.1 Cálculo Proposicional
2.1.1 Conjunção
2.1.2 Disjunção
2.1.3 Negação
2.1.4 Implicações
2.1.5 Se, e somente se
2.2 Tautologias e Contradições
2.3 Quantificadores
2.4 Validade de Argumentos
2.4.1 Tabela-Verdade
2.4.2 Regras de Inferência
2.4.3 Árvore de Refutação
2.4.4 Argumentos envolvendo quantificadores

4
4
5
6
7
7
9
9
10
12
13
14
16
18

3

Técnicas de Provas
3.1 O Método Direto
Prova por Contradição (Redução ao Absurdo)
Provas tipo P se, e somente se, Q
Prova por Casos
Provas de Existência
Provas de Unicidade
Uso de Contra-Exemplos
3.2 Indução Matemática

28
30
32
34
35
36
38
40
41

4

Conjuntos
4.1 Uma pausa para o rigor

46
51

5

Relações
5.1 Relações de Equivalência
5.2 Relação de Ordem

55
56
60

6

Funções

63

7

Cardinalidade

68 ii C APÍTULO 1

Introdução

O que é Lógica? Lógica é a ciência que estuda pricípios e métodos de inferência, tendo o objetivo principal de determinar em que condições certas coisas se seguem (são consequências), ou não, de outras. Obviamente, como definição, isso deixa bastante a desejar: precisamos explicitar o que é "inferência", por exemplo, e o que se quer dizer com "se seguem"ou "consequência".
Vamos começar com o problema apresentado no seguinte mini-conto de fadas:
Há não muito tempo atrás, num país distante, havia um velho rei que tinha três filhas, inteligentíssimas e de indescritível beleza, chamadas Guilhermina,
Genoveva e Griselda. Sentindo-se perto de partir desta para melhor, e sem saber qual das filhas designar como sua sucessora, o velho rei resolveu submetê-las a um teste. A vencedora não apenas seria a nova soberana, como ainda receberia a senha da