Lógica Matemática

e Demonstrações

Fundamentos, Técnicas de Prova e Aplicações

Uma apostila para estudantes de

Matemática, Física, Computação e Engenharias

July 12, 2026

2
Contents

Prefácio 5

1 Fundamentos da Lógica Matemática 7

1.1 O que é lógica? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Argumentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Proposições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Conectivos lógicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.1 Negação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Conjunção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.3 Disjunção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.4 Condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.5 Bicondicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.6 Precedência dos conectivos . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Tabelas-verdade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Tautologias, contradições e contingências . . . . . . . . . . . . . . . . . . . 14
1.6 Equivalência lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7 Leis de De Morgan e negação de proposições compostas . . . . . . . . . . . 16
1.8 Tradução entre linguagem natural e linguagem simbólica . . . . . . . . . . 18
1.9 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.9.1 Soluções dos exercícios . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 Regras de Inferência e Lógica de Predicados 23

2.1 Introdução: da equivalência à inferência . . . . . . . . . . . . . . . . . . . 23
2.2 Regras de inferência fundamentais . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.1 Cadeias de inferência . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Lógica de predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.1 Predicados e variáveis . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.2 Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.3 Negação de quantificadores . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.4 Ordem dos quantificadores . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.5 Tradução de sentenças matemáticas . . . . . . . . . . . . . . . . . . 30
2.4 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3 Demonstrações Matemáticas 33
3.1 O que é uma demonstração? . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Demonstração direta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 Estrutura lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Demonstração por contraposição . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.1 Estrutura lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Demonstração por contradição . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4.1 Estrutura lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3
4 Contents

3.5 Demonstração por casos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.5.1 Estrutura lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.6 Demonstrações construtivas e não construtivas . . . . . . . . . . . . . . . . 41
3.7 Existência e unicidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.8 Demonstrações envolvendo conjuntos . . . . . . . . . . . . . . . . . . . . . 43
3.9 Demonstrações envolvendo funções . . . . . . . . . . . . . . . . . . . . . . 44
3.10 Demonstrações envolvendo divisibilidade e desigualdades . . . . . . . . . . 46
3.11 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4 Indução Matemática e Estratégias de Resolução 49

4.1 Motivação da indução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2 O princípio da indução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Indução forte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4 Indução estrutural: uma breve introdução . . . . . . . . . . . . . . . . . . 54
4.5 Como matemáticos constroem demonstrações . . . . . . . . . . . . . . . . 54
4.5.1 Como iniciar uma prova . . . . . . . . . . . . . . . . . . . . . . . . 55
4.5.2 Como interpretar hipóteses . . . . . . . . . . . . . . . . . . . . . . . 55
4.5.3 Como descobrir o caminho da demonstração . . . . . . . . . . . . . 55
4.5.4 Trabalhar de trás para frente . . . . . . . . . . . . . . . . . . . . . 56
4.5.5 Criação de lemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.5.6 Escolha da técnica adequada . . . . . . . . . . . . . . . . . . . . . . 57
4.6 Erros comuns e falácias lógicas . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.7 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5 Aplicações da Lógica nas Demonstrações Matemáticas 61

5.1 Álgebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Análise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3 Teoria dos Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.4 Geometria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.5 Matemática Discreta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.6 Física Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6 Exercícios Gerais 69
6.1 Nível básico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.2 Nível intermediário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.3 Nível avançado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Prefácio

Este texto nasce de uma convicção simples, mas frequentemente subestimada nos cursos
iniciais de graduação: a matemática não é apenas um conjunto de fórmulas e algoritmos,
mas uma linguagem de raciocínio rigoroso. Antes de calcular, integrar, resolver equações
ou construir modelos, o estudante de Matemática, Física, Computação ou Engenharia
precisa aprender a argumentar corretamente. É essa habilidade – a de construir
e reconhecer demonstrações válidas – que separa o cálculo mecânico da compreensão
matemática genuína.
A lógica matemática fornece o esqueleto sobre o qual toda demonstração é construída.
Compreender os conectivos lógicos, os quantificadores, as regras de inferência e as difer-
entes técnicas de demonstração não é um exercício acadêmico isolado: é a ferramenta que
permite ao estudante ler um livro de Análise, entender uma prova em Álgebra Linear,
verificar a correção de um algoritmo ou justificar um resultado físico a partir de axiomas.
Esta apostila foi escrita com um objetivo duplo. Primeiro, apresentar de maneira completa
e rigorosa os fundamentos da lógica proposicional e da lógica de predicados. Segundo – e
talvez mais importante – desenvolver no leitor a capacidade ativa de construir demon-
strações: reconhecer qual técnica utilizar, como interpretar hipóteses, como planejar o
caminho de uma prova e como evitar os erros lógicos mais comuns.
Ao longo dos seis capítulos, procuramos sempre motivar os conceitos antes de formalizá-
los, interpretar intuitivamente cada definição, demonstrar rigorosamente cada resultado e
ilustrar com exemplos comentados passo a passo. Nenhuma passagem relevante é omitida
sob o pretexto de que "é fácil ver"; pelo contrário, o compromisso deste texto é com a
explicitação completa do raciocínio.
Desejamos que esta apostila sirva não apenas como material de consulta, mas como um
verdadeiro guia de iniciação ao pensamento matemático rigoroso.

Bons estudos.

5
6 Contents
Capítulo 1

Fundamentos da Lógica Matemática

1.1 O que é lógica?

A palavra lógica vem do grego logos, que pode ser traduzido como "palavra", "razão"
ou "discurso". Em matemática, a lógica é o estudo sistemático dos princípios que gover-
nam o raciocínio válido: como, a partir de certas afirmações aceitas como verdadeiras
(as premissas), podemos obter novas afirmações (as conclusões) de maneira segura, sem
cometer erros de raciocínio.
Antes de qualquer formalização, é importante que o estudante compreenda por que a
lógica é indispensável para a matemática. Considere a seguinte situação cotidiana:

"Se chover, então a rua fica molhada. A rua está molhada. Logo, choveu."

Esse argumento parece razoável à primeira vista, mas é, na verdade, logicamente in-
válido – a rua pode estar molhada por outros motivos (um caminhão-pipa, por exemplo).
A lógica matemática nos dá ferramentas precisas para distinguir argumentos como este,
que apenas parecem corretos, de argumentos genuinamente válidos, cuja conclusão é uma
consequência necessária das premissas, independentemente do conteúdo específico das
afirmações envolvidas.
Essa distinção – entre a forma de um argumento e o seu conteúdo – é a marca registrada
da lógica matemática. Um argumento é válido (ou não) por causa de sua estrutura, e
essa estrutura pode ser estudada de maneira abstrata, independentemente de estarmos
falando de chuva, números ou conjuntos.

1.1.1 Argumentos
Definição 1.1 Argumento
Um argumento é uma sequência finita de proposições P1 , P2 , . . . , Pn , chamadas pre-
missas, seguida de uma proposição Q, chamada conclusão, na qual se afirma que Q
decorre logicamente de P1 , . . . , Pn .

Representamos um argumento esquematicamente por

P1 , P2 , . . . , Pn ∴ Q,

onde o símbolo ∴ é lido "logo" ou "portanto".

7
8 Chapter 1. Fundamentos da Lógica Matemática

Definição 1.2 Validade

Um argumento é válido quando, sempre que todas as premissas P1 , . . . , Pn forem
verdadeiras, a conclusão Q também é necessariamente verdadeira. Isto é, não existe
nenhuma situação (nenhuma atribuição de valores de verdade) em que as premissas
sejam todas verdadeiras e a conclusão seja falsa.

Observação 1.3
É fundamental distinguir validade de verdade. A validade é uma propriedade da
forma do argumento; a verdade é uma propriedade do conteúdo de cada proposição
isolada. Um argumento pode ser válido mesmo que suas premissas sejam falsas, e pode
ser inválido mesmo que premissas e conclusão sejam, por acaso, todas verdadeiras.
O que a validade garante é a transmissão da verdade: se as premissas forem
verdadeiras, então a conclusão é necessariamente verdadeira.

Exemplo 1.4
Considere o argumento:

Todo número par maior que 2 é composto. 17 é um número par maior que
2. Logo, 17 é composto.

Este argumento é válido (a conclusão decorre logicamente das premissas, respeitando

a forma "todo A é B; x é A; logo x é B"), embora sua segunda premissa seja falsa (17
não é par). A validade da forma não é afetada pela falsidade do conteúdo; apenas nos
impede de concluir que 17 é de fato composto a partir deste argumento em particular.

O objetivo central deste capítulo, e de boa parte desta apostila, é fornecer meios precisos
para verificar a validade de argumentos, começando pelo estudo da lógica proposicional.

1.2 Proposições
Definição 1.5 Proposição
Uma proposição é uma sentença declarativa à qual se pode atribuir exatamente
um dentre dois valores de verdade: verdadeiro (V) ou falso (F), mas nunca ambos
simultaneamente e nunca nenhum dos dois.

Essa é a suposição central da lógica clássica (ou bivalente), sobre a qual toda esta
apostila se apoia: toda proposição tem exatamente um valor de verdade, mesmo que não
saibamos, no momento, qual é esse valor.

Exemplo 1.6
São proposições:
(a) "2 + 2 = 4" (proposição verdadeira);
(b) "7 é um número primo par" (proposição falsa, pois o único primo par é 2);
(c) "Existem infinitos números primos" (proposição verdadeira, como demon-
straremos futuramente);
1.3. Conectivos lógicos 9

(d) "A conjectura de Goldbach é verdadeira" (é uma proposição, ainda que atual-
mente não se saiba, com demonstração, se seu valor de verdade é V ou F – o
que importa é que ela possui um valor de verdade definido, mesmo que descon-
hecido).

Exemplo 1.7
Não são proposições:
(a) "Que horas são?" (sentença interrogativa, não declarativa);
(b) "Estude mais!" (sentença imperativa);
(c) "x + 2 = 5" (sentença aberta: seu valor de verdade depende do valor não
especificado da variável x; trataremos essas sentenças, chamadas predicados,
no Capítulo 2);
(d) "Esta frase é falsa" (o famoso paradoxo do mentiroso: se fosse verdadeira, se-
ria falsa, e vice-versa – não podemos atribuir-lhe um único valor de verdade
consistente, de modo que não é uma proposição no sentido lógico usual).

Observação 1.8
Denotaremos proposições por letras minúsculas: p, q, r, s, . . . , eventualmente com
índices. Diremos "seja p a proposição “tal coisa”" para introduzir uma variável proposi-
cional associada a uma sentença específica.

1.3 Conectivos lógicos

Proposições simples (chamadas atômicas) podem ser combinadas por meio de conec-
tivos lógicos para formar proposições mais complexas (chamadas moleculares ou com-
postas). O valor de verdade de uma proposição composta depende unicamente dos val-
ores de verdade das proposições atômicas que a compõem e da forma como os conectivos
as combinam – nunca do "significado" das proposições atômicas. Essa é a essência do
chamado princípio de composicionalidade (ou funcionalidade de verdade) da lóg-
ica clássica.

1.3.1 Negação

Definição 1.9 Negação

Dada uma proposição p, a negação de p, denotada ¬p (lê-se "não p"), é a proposição
que é verdadeira quando p é falsa, e falsa quando p é verdadeira.

A tabela-verdade da negação é:
p ¬p
V F
F V
10 Chapter 1. Fundamentos da Lógica Matemática

Exemplo 1.10
Se p = "hoje chove", então ¬p = "hoje não chove". Se p = "5 é primo" (V), então
¬p = "5 não é primo" (F).

1.3.2 Conjunção
Definição 1.11 Conjunção
Dadas proposições p e q, a conjunção de p e q, denotada p ∧ q (lê-se "p e q"), é a
proposição que é verdadeira se, e somente se, p e q são ambas verdadeiras.

p q p∧q
V V V
V F F
F V F
F F F

1.3.3 Disjunção
Definição 1.12 Disjunção inclusiva
Dadas proposições p e q, a disjunção (inclusiva) de p e q, denotada p ∨ q (lê-se "p
ou q"), é a proposição que é verdadeira se, e somente se, pelo menos uma das
proposições p, q é verdadeira.

p q p∨q
V V V
V F V
F V V
F F F

Observação 1.13
Em português coloquial, a palavra "ou" costuma ser usada em seu sentido exclu-
sivo (um ou outro, mas não ambos), como em "vou de ônibus ou de carro". Em
matemática, salvo indicação contrária, "ou" é sempre inclusivo: p ∨ q é verdadeira
mesmo quando p e q são ambas verdadeiras. Quando se deseja o sentido exclusivo,
utiliza-se o conectivo ou exclusivo, denotado p⊻q, definido por p⊻q ≡ (p∨q)∧¬(p∧q),
verdadeiro exatamente quando p e q têm valores de verdade distintos.

1.3.4 Condicional
O conectivo condicional é, dentre todos, o que mais frequentemente gera confusão inicial,
e por isso merece atenção especial.
1.3. Conectivos lógicos 11

Definição 1.14 Condicional

Dadas proposições p e q, o condicional de p para q, denotado p → q (lê-se "se p,
então q"), é a proposição que é falsa apenas quando p é verdadeira e q é falsa; em
todos os outros casos, é verdadeira.

p q p→q
V V V
V F F
F V V
F F V

Na proposição p → q, p é chamada de antecedente (ou hipótese) e q de consequente

(ou tese).

Observação 1.15 Por que o condicional é definido dessa forma?

As duas primeiras linhas da tabela são intuitivas: se "p implica q" e p é verdadeira,
esperamos que q também seja (senão a implicação seria quebrada); se p é verdadeira
e q é falsa, a implicação é claramente falsa. As duas últimas linhas, em que p é falsa,
são menos intuitivas e merecem justificativa cuidadosa.
Considere a afirmação: "se n é múltiplo de 4, então n é múltiplo de 2". Essa afirmação
deve ser verdadeira para todo número inteiro n, incluindo aqueles em que n não é
múltiplo de 4 (por exemplo, n = 6, que é múltiplo de 2 mas não de 4: aqui p é falsa e q
é verdadeira, e a implicação deve valer – terceira linha da tabela) e incluindo também
n = 7 (que não é múltiplo de 4 nem de 2: aqui p é falsa e q é falsa, e ainda assim
a implicação "se 7 fosse múltiplo de 4, seria múltiplo de 2" não é contradita por esse
caso – quarta linha da tabela).
Em outras palavras, quando o antecedente p é falso, a implicação p → q não é "testada"
por aquele caso específico, e por convenção (chamada de verdade vácua, do inglês
vacuous truth) declaramos a implicação verdadeira. Essa convenção é essencial para
que o condicional se comporte de maneira uniforme e seja compatível com o modo
como quantificadores universais funcionam, como veremos no Capítulo 2.

Observação 1.16 Formas equivalentes de enunciar p → q

As seguintes expressões em português são todas formas de expressar p → q:
• "Se p, então q";
• "p é condição suficiente para q";
• "q é condição necessária para p";
• "q, se p";
• "p somente se q";
• "p implica q".
Reconhecer essas variações é essencial para traduzir corretamente enunciados
matemáticos para a linguagem simbólica, tarefa que exercitaremos amplamente ao
longo desta apostila.
12 Chapter 1. Fundamentos da Lógica Matemática

Definição 1.17 Recíproca, contrapositiva e inversa

Dado o condicional p → q, definimos:
• sua recíproca: q → p;
• sua contrapositiva: ¬q → ¬p;
• sua inversa: ¬p → ¬q.

Veremos adiante que p → q e sua contrapositiva ¬q → ¬p são logicamente equivalentes

(têm sempre o mesmo valor de verdade), ao passo que a recíproca e a inversa não são,
em geral, equivalentes ao condicional original. Esse fato é a base lógica da técnica de
demonstração por contraposição, que estudaremos detalhadamente no Capítulo 3.

1.3.5 Bicondicional
Definição 1.18 Bicondicional
Dadas proposições p e q, o bicondicional de p e q, denotado p ↔ q (lê-se "p se,
e somente se, q"), é a proposição que é verdadeira exatamente quando p e q têm o
mesmo valor de verdade.

p q p↔q
V V V
V F F
F V F
F F V

Observação 1.19
Note que p ↔ q é verdadeira exatamente quando (p → q) ∧ (q → p) é verdadeira –
fato que verificaremos formalmente mais adiante por meio de tabela-verdade. Essa
observação justifica a estratégia usual para demonstrar uma afirmação da forma "p
se, e somente se, q": demonstra-se separadamente que p ⇒ q (a chamada "ida") e que
q ⇒ p (a chamada "volta").

1.3.6 Precedência dos conectivos

Para evitar ambiguidades ao escrever fórmulas sem excesso de parênteses, adotamos a
seguinte ordem de precedência (da maior para a menor):
¬ > ∧ > ∨ >→>↔.
Ou seja, ¬ liga-se mais fortemente à proposição que o segue; ∧ tem prioridade sobre ∨; e
ambos têm prioridade sobre → e ↔.
Exemplo 1.20
A fórmula
¬p ∨ q ∧ r → s
deve ser lida como

(¬p) ∨ (q ∧ r) → s.
1.4. Tabelas-verdade 13

Recomenda-se, mesmo conhecendo as regras de precedência, o uso liberal de parênteses

para tornar fórmulas complexas mais legíveis.

1.4 Tabelas-verdade

Definição 1.21 Tabela-verdade

A tabela-verdade de uma proposição composta é uma tabela que lista, para cada
combinação possível de valores de verdade das proposições atômicas que a constituem,
o valor de verdade resultante da proposição composta.

Se uma proposição composta envolve n proposições atômicas distintas, sua tabela-verdade

possui 2n linhas, uma para cada combinação possível de valores V/F.

Exemplo 1.22
Construamos a tabela-verdade de (p ∧ q) → (p ∨ q).
Como há duas proposições atômicas (p e q), a tabela terá 22 = 4 linhas.

p q p ∧ q p ∨ q (p ∧ q) → (p ∨ q)
V V V V V
V F F V V
F V F V V
F F F F V
Note que a última coluna é sempre verdadeira, independentemente dos valores de p
e q. Proposições com essa propriedade recebem um nome especial, que definiremos a
seguir.

Exemplo 1.23
Construamos a tabela-verdade de ¬(p ∧ q) ↔ (¬p ∨ ¬q), que é exatamente uma das
Leis de De Morgan que estudaremos na Seção 1.7.

p q p ∧ q ¬(p ∧ q) ¬p ¬q ¬p ∨ ¬q
V V V F F F F
V F F V F V V
F V F V V F V
F F F V V V V
Comparando a quarta coluna (¬(p ∧ q)) com a sétima (¬p ∨ ¬q), observamos que são
idênticas em todas as linhas. Logo, o bicondicional ¬(p∧q) ↔ (¬p∨¬q) é verdadeiro
em todas as linhas – outro exemplo de tautologia.
14 Chapter 1. Fundamentos da Lógica Matemática

1.5 Tautologias, contradições e contingências

Definição 1.24 Tautologia

Uma proposição composta é uma tautologia quando é verdadeira em todas as linhas
de sua tabela-verdade, isto é, para toda atribuição possível de valores de verdade às
suas proposições atômicas.

Definição 1.25 Contradição

Uma proposição composta é uma contradição quando é falsa em todas as linhas de
sua tabela-verdade.

Definição 1.26 Contingência

Uma proposição composta é uma contingência quando não é nem tautologia nem
contradição, isto é, assume o valor V em pelo menos uma linha e o valor F em pelo
menos outra.

Exemplo 1.27
A proposição p ∨ ¬p (princípio do terceiro excluído) é uma tautologia:

p ¬p p ∨ ¬p
V F V
F V V

Já a proposição p ∧ ¬p (princípio da não contradição, em sua forma negada) é

uma contradição:
p ¬p p ∧ ¬p
V F F
F V F
A proposição p → q é uma contingência: como vimos, ela é falsa apenas quando
p é V e q é F, e verdadeira nos demais casos – portanto assume ambos os valores,
dependendo da linha.

Observação 1.28
Tautologias desempenham papel central na lógica matemática: como veremos na Seção
1.6, elas correspondem exatamente às equivalências lógicas e, no Capítulo 2, às
regras de inferência válidas. Verificar que uma fórmula é uma tautologia é, em
essência, verificar que um determinado padrão de raciocínio é sempre correto, não
importando o conteúdo específico envolvido.
1.6. Equivalência lógica 15

1.6 Equivalência lógica

Definição 1.29 Equivalência lógica

Duas proposições compostas P e Q são logicamente equivalentes, denotado P ≡ Q,
quando possuem exatamente a mesma tabela-verdade, isto é, quando P ↔ Q é
uma tautologia.

Observação 1.30
Note a diferença sutil entre ≡ e ↔: o bicondicional ↔ é um conectivo que combina
duas proposições para formar uma terceira proposição (que pode ser V ou F depen-
dendo da linha); já ≡ é uma relação metalinguística entre proposições, que afirma
que P ↔ Q é sempre verdadeira (uma tautologia). Em outras palavras, P ≡ Q é uma
afirmação sobre as proposições P e Q, não uma nova proposição composta por elas.

A seguir, listamos as equivalências lógicas fundamentais, todas verificáveis por tabela-

verdade (deixamos várias verificações como exercício).

Teorema 1.31 Equivalências lógicas fundamentais

Sejam p, q, r proposições quaisquer, T uma tautologia e F uma contradição. Valem
as seguintes equivalências:
(i) Dupla negação: ¬(¬p) ≡ p;
(ii) Idempotência: p ∧ p ≡ p; p ∨ p ≡ p;
(iii) Comutatividade: p ∧ q ≡ q ∧ p; p ∨ q ≡ q ∨ p;
(iv) Associatividade: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r); (p ∨ q) ∨ r ≡ p ∨ (q ∨ r);
(v) Distributividade: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r); p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r);
(vi) Leis de De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q;
(vii) Identidade: p ∧ T ≡ p; p ∨ F ≡ p;
(viii) Dominação: p ∨ T ≡ T ; p ∧ F ≡ F ;
(ix) Absorção: p ∨ (p ∧ q) ≡ p; p ∧ (p ∨ q) ≡ p;
(x) Terceiro excluído: p ∨ ¬p ≡ T ;
(xi) Não contradição: p ∧ ¬p ≡ F ;
(xii) Condicional como disjunção: p → q ≡ ¬p ∨ q;
(xiii) Negação do condicional: ¬(p → q) ≡ p ∧ ¬q;
(xiv) Contraposição: p → q ≡ ¬q → ¬p;
(xv) Bicondicional: p ↔ q ≡ (p → q) ∧ (q → p).

Proof. Demonstraremos os itens (vi) [primeira Lei de De Morgan] e (xiv) [contraposição]

por tabela-verdade; os demais itens ficam propostos como exercício, seguindo o mesmo
método.

Item (vi): já verificamos anteriormente, na tabela da Seção 1.5, que ¬(p ∧ q) e ¬p ∨ ¬q

possuem a mesma coluna de valores de verdade em todas as quatro linhas possíveis. Logo,
por definição, ¬(p ∧ q) ≡ ¬p ∨ ¬q.
16 Chapter 1. Fundamentos da Lógica Matemática

Item (xiv): construímos a tabela-verdade conjunta de p → q e ¬q → ¬p:

p q p → q ¬p ¬q ¬q → ¬p
V V V F F V
V F F F V F
F V V V F V
F F V V V V

Comparando a terceira coluna com a sexta, vemos que são idênticas em todas as linhas.
Logo, p → q ≡ ¬q → ¬p. ■

Observação 1.32
A equivalência (xii), p → q ≡ ¬p ∨ q, é extremamente útil na prática: ela permite
reescrever qualquer condicional em termos de negação e disjunção, o que muitas vezes
facilita a manipulação algébrica de fórmulas lógicas e, como veremos, a negação de
proposições condicionais.

Exemplo 1.33
Vamos usar as equivalências do Teorema anterior para simplificar a fórmula

¬(p → q) ∨ (p ∧ q).

Pelo item (xiii), ¬(p → q) ≡ p ∧ ¬q. Substituindo:

¬(p → q) ∨ (p ∧ q) ≡ (p ∧ ¬q) ∨ (p ∧ q).

Pela distributividade (item (v), na direção contrária – fatorando p):

(p ∧ ¬q) ∨ (p ∧ q) ≡ p ∧ (¬q ∨ q).

Pelo terceiro excluído (item (x)), ¬q ∨ q ≡ T . Logo, pela identidade (item (vii)):

p ∧ (¬q ∨ q) ≡ p ∧ T ≡ p.

Concluímos que ¬(p → q) ∨ (p ∧ q) ≡ p, um resultado nada óbvio à primeira vista,

mas obtido rigorosamente por uma cadeia de equivalências elementares. Esse método
– manipular fórmulas por meio de equivalências conhecidas, em vez de recorrer sempre
a tabelas-verdade – será usado extensivamente ao longo desta apostila e é análogo,
em espírito, à simplificação algébrica de expressões.

1.7 Leis de De Morgan e negação de proposições com-

postas
As Leis de De Morgan merecem destaque especial por sua importância prática: elas nos
dizem como negar conjunções e disjunções, uma habilidade essencial para, por exemplo,
construir demonstrações por contradição ou por contraposição (Capítulo 3), nas quais é
necessário negar corretamente a tese de um teorema.
1.7. Leis de De Morgan e negação de proposições compostas 17

Teorema 1.34 Leis de De Morgan

Para quaisquer proposições p, q:

¬(p ∧ q) ≡ ¬p ∨ ¬q e ¬(p ∨ q) ≡ ¬p ∧ ¬q.

Em palavras: a negação de uma conjunção é a disjunção das negações, e a

negação de uma disjunção é a conjunção das negações. Uma forma mnemônica
de lembrar: a negação "distribui-se" sobre ∧ e ∨, mas troca um conectivo pelo outro.
Exemplo 1.35
Vamos negar a proposição: "n é par e n é maior que 10".
Simbolicamente, se p: "n é par" e q: "n é maior que 10", a proposição é p ∧ q. Por
De Morgan:
¬(p ∧ q) ≡ ¬p ∨ ¬q,
isto é: "n não é par ou n não é maior que 10" (equivalentemente, "n é ímpar ou
n ≤ 10").
Um erro comum é negar incorretamente como "n é ímpar e n ≤ 10" – essa negação
estaria trocando o conectivo ∨ por ∧, o que não é a negação correta. Basta observar
um contraexemplo: se n = 6 (par e não maior que 10), a proposição original p ∧ q
é falsa (pois q é falsa), logo sua negação deveria ser verdadeira. Testando a negação
incorreta "n é ímpar e n ≤ 10" com n = 6: "6 é ímpar" é falso, portanto a conjunção
é falsa – mas deveria ser verdadeira! Isso confirma que a negação incorreta está, de
fato, errada, enquanto a negação correta ("n é ímpar ou n ≤ 10") é verdadeira para
n = 6, como deveria ser.

Corolário 1.36
A negação do condicional é: ¬(p → q) ≡ p ∧ ¬q.

Proof. Pela equivalência (xii) do Teorema 1.1, p → q ≡ ¬p ∨ q. Logo,

¬(p → q) ≡ ¬(¬p ∨ q).

Aplicando De Morgan ao lado direito:

¬(¬p ∨ q) ≡ ¬(¬p) ∧ ¬q ≡ p ∧ ¬q,

usando a dupla negação na última passagem. Portanto, ¬(p → q) ≡ p ∧ ¬q. ■

Observação 1.37
Este corolário será usado repetidamente no Capítulo 3: para demonstrar p → q por
contradição, supomos a negação da tese, isto é, supomos p ∧ ¬q – ou seja, supomos
simultaneamente que a hipótese p vale e que a conclusão q é falsa – e buscamos derivar
uma contradição.

Exemplo 1.38
Vamos negar a proposição: "se n é primo, então n = 2 ou n é ímpar".
Aqui p: "n é primo", e o consequente é q ∨ r, com q: "n = 2" e r: "n é ímpar". A
18 Chapter 1. Fundamentos da Lógica Matemática

proposição completa é p → (q ∨ r).

Pelo Corolário anterior:


¬ p → (q ∨ r) ≡ p ∧ ¬(q ∨ r).

Aplicando De Morgan a ¬(q ∨ r):

¬(q ∨ r) ≡ ¬q ∧ ¬r.

Logo:

¬ p → (q ∨ r) ≡ p ∧ ¬q ∧ ¬r,
isto é: "n é primo, n ̸= 2, e n é par" (usando ¬r: "n não é ímpar", equivalente a "n
é par"). Em suma, a negação da afirmação original é: "n é primo, n é diferente de 2,
e n é par".

1.8 Tradução entre linguagem natural e linguagem sim-

bólica
Uma das habilidades mais importantes a serem desenvolvidas neste início de curso é a
capacidade de traduzir corretamente sentenças em português (ou qualquer língua natural)
para a linguagem simbólica da lógica, e vice-versa. Essa habilidade será a base para a
leitura e escrita de enunciados matemáticos precisos.

Exemplo 1.39
Traduza para linguagem simbólica: "Não é o caso que, se estudo, então não passo no
exame".
Sejam p: "estudo" e q: "passo no exame". A sentença "se estudo, então não passo" é
p → ¬q. A sentença completa é a negação desta: ¬(p → ¬q).
Podemos simplificar usando o Corolário 1.1 (com q substituído por ¬q):

¬(p → ¬q) ≡ p ∧ ¬(¬q) ≡ p ∧ q.

Ou seja, a sentença original equivale, de forma simplificada, a: "estudo e passo no

exame". Isso é intuitivamente satisfatório: negar "se estudo, não passo" é afirmar que
de fato estudo e, apesar disso, passo.

Exemplo 1.40
Traduza para português, de forma natural: (p ∧ ¬q) → r, onde p: "o número é par",
q: "o número é primo", r: "o número é igual a 2".
Uma tradução literal seria: "Se o número é par e o número não é primo, então o número
é igual a 2". Isso, porém, está logicamente incorreto como afirmação matemática
(por exemplo, n = 4 é par e não primo, mas 4 ̸= 2) – o que ilustra que a tradução
correta de uma fórmula não garante que a proposição resultante seja verdadeira;
apenas garante que a tradução está fielmente representada. Cabe ao matemático,
em seguida, investigar separadamente se a proposição traduzida é de fato verdadeira.
1.9. Exercícios 19

Observação 1.41
Um erro frequente ao traduzir enunciados é confundir "p somente se q" com "p se
q". Lembre-se: "p somente se q" traduz-se como p → q, enquanto "p se q" traduz-se
como q → p. Preste atenção especial a essa inversão, pois é fonte comum de erros em
provas.

1.9 Exercícios
Exercício 1.42. Determine se cada sentença abaixo é uma proposição. Em caso afir-
mativo, diga se é (ou pode-se afirmar que é) verdadeira ou falsa:
(a) "3 é maior que π";
(b) "Feche a porta, por favor";
(c) "x2 − 1 = 0";
(d) "Todo número natural maior que 1 possui um divisor primo";
(e) "Esta sentença possui exatamente sete palavras".
Solução 1.43. A solução do exercícios dados acima estão a seguir.
(a) Preposição
(b) Não é uma preposição
(c) Preposição
(d) Preposição
(e) Preposição
Exercício 1.44. Construa a tabela-verdade completa das seguintes proposições e clas-
sifique cada uma como tautologia, contradição ou contingência:
(a) (p → q) ∨ (q → p);
(b) (p ∧ q) ∧ ¬(p ∨ q);
(c) (p → q) ∧ (p ∧ ¬q);
(d) p → (q → r) ↔ (p ∧ q) → r .

Exercício 1.45. Utilizando as equivalências lógicas do Teorema 1.1, simplifique ao

máximo as seguintes proposições, indicando qual equivalência é usada em cada passo:
(a) ¬(¬p ∨ ¬q) ∨ (p ∧ q);
(b) (p ∨ q) ∧ (p ∨ ¬q);
(c) ¬ p → (p ∨ q) .

Exercício 1.46. Escreva a negação de cada proposição a seguir, simplificando o máximo

possível usando as Leis de De Morgan e as demais equivalências vistas:
(a) "n é par e n é divisível por 3";
20 Chapter 1. Fundamentos da Lógica Matemática

(b) "Se x > 0, então x2 > 0 ou x = 1";

(c) "x ≤ 0 ou (x > 0 e x é irracional)".

Exercício 1.47. Demonstre, usando tabelas-verdade, os itens (iii), (v) e (ix) do Teorema
1.1 (comutatividade, distributividade e absorção).

Exercício 1.48. Escreva a recíproca, a contrapositiva e a inversa de cada condicional

abaixo, e em cada caso diga (informalmente, apelando à sua intuição matemática) se a
recíproca é ou não verdadeira, supondo o condicional original verdadeiro:
(a) "Se n é múltiplo de 6, então n é múltiplo de 2";
(b) "Se x = 3, então x2 = 9";
(c) "Se um quadrilátero é um quadrado, então é um retângulo".

Exercício 1.49. Traduza cada sentença para linguagem simbólica, definindo claramente
as proposições atômicas envolvidas:
(a) "É necessário que n seja par para que n2 seja par, mas isso não é suficiente";
(b) "Nem x é positivo, nem y é negativo";
(c) "x é solução da equação somente se x = 1 ou x = −1".

Exercício 1.50. Mostre, usando tabela-verdade, que a proposição (p → q) ∧ ¬q → ¬p

 

é uma tautologia. (Esta tautologia será revisitada no Capítulo 2 sob o nome de Modus
Tollens.)
1.9. Exercícios 21

1.9.1 Soluções dos exercícios

22 Chapter 1. Fundamentos da Lógica Matemática
Capítulo 2

Regras de Inferência e Lógica de Predi-

cados

2.1 Introdução: da equivalência à inferência

No Capítulo 1, aprendemos a verificar se uma proposição composta é uma tautologia e
a reconhecer quando duas proposições são logicamente equivalentes. Agora damos um
passo além: em vez de comparar proposições entre si, estudaremos como derivar novas
proposições verdadeiras a partir de proposições já aceitas como verdadeiras. Esse é o
cerne de toda demonstração matemática.

Definição 2.1 Regra de inferência

Uma regra de inferência é um argumento válido de forma geral, isto é, um esquema

P1 , P2 , . . . , Pn ∴ Q

tal que a proposição (P1 ∧ P2 ∧ · · · ∧ Pn ) → Q é uma tautologia. Dizemos, nesse caso,

que Q é uma consequência lógica de P1 , . . . , Pn .

Observação 2.2
Essa definição estabelece a ponte fundamental entre os dois capítulos: verificar que
uma regra de inferência é válida é, precisamente, verificar que uma certa proposição
condicional é uma tautologia – tarefa que já sabemos realizar por tabela-verdade. As
regras de inferência que apresentaremos a seguir foram todas verificadas dessa forma,
e o leitor é convidado a confirmar algumas delas nos exercícios.

2.2 Regras de inferência fundamentais

Teorema 2.3 Modus Ponens

A seguinte regra de inferência é válida:

p → q, p ∴ q.

23
24 Chapter 2. Regras de Inferência e Lógica de Predicados

Proof. Devemos mostrar que (p → q) ∧ p → q é uma tautologia.

 

 
p q p → q (p → q) ∧ p (p → q) ∧ p → q
V V V V V
V F F F V
F V V F V
F F V F V

A última coluna é sempre V. Logo, a implicação é uma tautologia, e o Modus Ponens é

uma regra de inferência válida. ■

Observação 2.4
Modus Ponens (do latim, "modo que afirma") é, sem dúvida, a regra de inferência
mais utilizada em matemática: sempre que sabemos que "se p então q" e verificamos
que p de fato ocorre, concluímos q. Praticamente toda aplicação de um teorema
previamente demonstrado a um caso particular é uma instância do Modus Ponens.

Exemplo 2.5
Sabemos que "se n é divisível por 4, então n é divisível por 2" (teorema já estabele-
cido) e que "20 é divisível por 4" (fato verificável diretamente). Por Modus Ponens,
concluímos: "20 é divisível por 2".

Teorema 2.6 Modus Tollens

A seguinte regra de inferência é válida:

p → q, ¬q ∴ ¬p.

Proof.  Este resultado já foi verificado no Exercício 1.8 do capítulo anterior: (p →



q) ∧ ¬q → ¬p é uma tautologia, como se verifica diretamente por tabela-verdade (a única

linha em que (p → q) e ¬q são ambas verdadeiras é quando p = F, q = F , e nesse caso
¬p = V ). ■

Observação 2.7
Modus Tollens ("modo que nega") é a base lógica da técnica de demonstração por
contraposição, que estudaremos detalhadamente no Capítulo 3: para provar p → q, é
logicamente equivalente (pelo item (xiv) do Teorema 1.1) provar ¬q → ¬p.

Exemplo 2.8
Sabemos que "se um número é natural e primo maior que 2, então é ímpar" e obser-
vamos que "18 não é ímpar". Por Modus Tollens, concluímos que "18 não é (natural,
primo e maior que 2) simultaneamente" – de fato, 18 não é primo.

Teorema 2.9 Silogismo hipotético

A seguinte regra de inferência é válida:

p → q, q → r ∴ p → r.
2.2. Regras de inferência fundamentais 25

Proof. Suponhamos que as premissas p → q e q → r sejam ambas verdadeiras (caso

contrário, nada há a demonstrar, pois a implicação de interesse é vácua). Para mostrar
que p → r é verdadeira, suponhamos p verdadeira (se p for falsa, p → r é automaticamente
verdadeira, por vacuidade). Como p → q é verdadeira e p é verdadeira, por Modus
Ponens concluímos q verdadeira. Como q → r é verdadeira e q é verdadeira, novamente
por Modus Ponens concluímos r verdadeira. Logo, sempre que p é verdadeira (sob as
premissas dadas), r também é, o que mostra que p → r é verdadeira. ■

Observação 2.10
Esta demonstração ilustra um estilo de prova ligeiramente diferente do uso direto de
tabelas-verdade: um argumento semântico, que analisa diretamente o significado dos
valores de verdade envolvidos, em vez de enumerar exaustivamente todas as linhas.
Ambos os estilos são rigorosos; o argumento semântico costuma ser mais esclarece-
dor e é o estilo predominante em demonstrações matemáticas reais, como veremos
amplamente no Capítulo 3.

Teorema 2.11 Silogismo disjuntivo

A seguinte regra de inferência é válida:

p ∨ q, ¬p ∴ q.

Proof. Suponha p ∨ q verdadeira e ¬p verdadeira (isto é, p falsa). Como p ∨ q é verdadeira

e p é falsa, pela definição da disjunção (verdadeira quando pelo menos uma das partes é
verdadeira), q deve ser verdadeira. ■

Teorema 2.12 Regras adicionais

São válidas as seguintes regras de inferência, cujas demonstrações (por tabela-verdade
ou argumento semântico) ficam propostas como exercício:
(i) Adição: p ∴ p ∨ q;
(ii) Simplificação: p ∧ q ∴ p;
(iii) Conjunção: p, q ∴ p ∧ q;
(iv) Dilema construtivo: (p → q) ∧ (r → s), p ∨ r ∴ q ∨ s;
(v) Resolução: p ∨ q, ¬p ∨ r ∴ q ∨ r.

2.2.1 Cadeias de inferência

Na prática, uma demonstração raramente aplica uma única regra de inferência; ao con-
trário, encadeia várias regras sucessivamente, partindo das premissas até alcançar a con-
clusão desejada. Chamamos esse encadeamento de dedução formal ou cadeia de in-
ferência.

Exemplo 2.13
Considere as premissas:
1. p → q
2. q → r
3. ¬r
 26 Chapter 2. Regras de Inferência e Lógica de Predicados

Vamos deduzir ¬p por uma cadeia de inferências, justificando cada passo.

Passo 1: De (1) e (2), por Silogismo Hipotético, obtemos p → r.
Passo 2: De p → r (Passo 1) e ¬r (premissa 3), por Modus Tollens, obtemos ¬p.
Logo, ¬p é consequência lógica das três premissas dadas.

Exemplo 2.14
Considere as premissas:
1. Se estudo lógica, então compreendo demonstrações (p → q).
2. Se compreendo demonstrações, então terei sucesso em Análise (q → r).
3. Não terei sucesso em Análise, ou obterei uma boa nota final (¬r ∨ s).
4. Não obterei uma boa nota final (¬s).
Vamos deduzir "não estudo lógica" (¬p).
Passo 1: De (3) ¬r ∨ s e (4) ¬s, por Silogismo Disjuntivo (rearranjando ¬r ∨ s como
s ∨ ¬r por comutatividade, e usando ¬s), obtemos ¬r.
Passo 2: De (1) p → q e (2) q → r, por Silogismo Hipotético, obtemos p → r.
Passo 3: De p → r (Passo 2) e ¬r (Passo 1), por Modus Tollens, obtemos ¬p.
Concluímos "não estudo lógica". Esta cadeia de três passos ilustra como argumentos
aparentemente complexos podem ser decompostos em aplicações sucessivas de regras
elementares – exatamente o que ocorre, em escala muito maior, em demonstrações
matemáticas complexas.

2.3 Lógica de predicados

A lógica proposicional, embora fundamental, é insuficiente para capturar boa parte do
raciocínio matemático. Considere o argumento clássico:

Todo ser humano é mortal. Sócrates é um ser humano. Logo, Sócrates é

mortal.

Este argumento é intuitivamente válido, mas a lógica proposicional, que trata proposições
como blocos indivisíveis, é incapaz de analisar sua estrutura interna: não há como expres-
sar "todo x" dentro da linguagem que construímos no Capítulo 1. Precisamos, portanto,
de uma linguagem mais expressiva: a lógica de predicados (também chamada lógica
de primeira ordem).

2.3.1 Predicados e variáveis

Definição 2.15 Predicado
Um predicado é uma sentença que contém uma ou mais variáveis e que se torna uma
proposição (isto é, adquire um valor de verdade definido) quando as variáveis são sub-
stituídas por elementos específicos de um determinado conjunto, chamado universo
de discurso.

Denotamos um predicado com uma variável por P (x), lido "x satisfaz P " ou simplesmente
"P de x". Predicados com múltiplas variáveis são denotados P (x, y), P (x, y, z), etc.
2.3. Lógica de predicados 27

Definição 2.16 Universo de discurso

O universo de discurso (ou domínio) de uma variável é o conjunto de todos os
valores que essa variável pode assumir. A especificação do universo de discurso é
essencial: o valor de verdade de sentenças quantificadas (que veremos a seguir) de-
pende crucialmente de qual é o universo considerado.

Exemplo 2.17
Seja P (x): "x2 − 4 = 0", com universo de discurso R. Temos:
• P (2) é verdadeira, pois 22 − 4 = 0;
• P (−2) é verdadeira, pois (−2)2 − 4 = 0;
• P (3) é falsa, pois 32 − 4 = 5 ̸= 0.
Note que P (x), isoladamente (sem substituição de x por um valor específico, e sem
quantificação, que veremos a seguir), não é uma proposição: não podemos atribuir-
lhe um único valor de verdade, pois este depende do valor (não especificado) de x.

Exemplo 2.18
Seja Q(x, y): "x < y", com universo de discurso N × N. Temos Q(2, 5) verdadeira e
Q(7, 3) falsa. Note que Q(x, y) e Q(y, x) não são, em geral, equivalentes (a relação
"<" não é simétrica): Q(2, 5) ̸= Q(5, 2) em valor de verdade.

2.3.2 Quantificadores
Os predicados tornam-se proposições completas por meio da substituição de suas var-
iáveis por valores específicos, ou por meio de quantificação, que afirma algo sobre todos
os elementos do universo, ou sobre a existência de algum elemento com determinada
propriedade.

Definição 2.19 Quantificador universal

O quantificador universal, denotado ∀ (lido "para todo"), aplicado a um predicado
P (x) com universo de discurso U , produz a proposição

∀x ∈ U, P (x),

que é verdadeira se, e somente se, P (x) é verdadeira para cada elemento x de U ,
sem exceção.

Definição 2.20 Quantificador existencial

O quantificador existencial, denotado ∃ (lido "existe"), aplicado a um predicado
P (x) com universo de discurso U , produz a proposição

∃x ∈ U, P (x),

que é verdadeira se, e somente se, existe pelo menos um elemento x de U para o
qual P (x) é verdadeira.
28 Chapter 2. Regras de Inferência e Lógica de Predicados

Observação 2.21
Um terceiro quantificador, útil na prática, é o quantificador de existência e uni-
cidade, denotado ∃! (lido "existe um único"), definido por
   
∃!x ∈ U, P (x) ≡ ∃x ∈ U, P (x) ∧ ∀x, y ∈ U, (P (x) ∧ P (y)) → x = y .

Ou seja: existe ao menos um elemento satisfazendo P , e quaisquer dois elementos

que satisfaçam P devem ser, na verdade, o mesmo elemento. Retomaremos este
quantificador ao tratarmos de demonstrações de existência e unicidade, no Capítulo
3.

Exemplo 2.22
Considere o universo de discurso N = {0, 1, 2, 3, . . . }.
(a) ∀n ∈ N, n ≥ 0 é verdadeira (todo natural é não negativo);
(b) ∀n ∈ N, n2 > n é falsa (falha para n = 0 e n = 1: um único contraexemplo já
basta para tornar falsa uma afirmação universal, como discutiremos abaixo);
(c) ∃n ∈ N, n2 = 4 é verdadeira (basta n = 2);
(d) ∃n ∈ N, n + 1 = n é falsa (nenhum natural satisfaz essa equação);
(e) ∃!n ∈ N, n2 = 9 é verdadeira (o único natural que satisfaz é n = 3; note que,
se o universo fosse Z, a unicidade falharia, pois −3 também satisfaria n2 = 9).

Observação 2.23 Como refutar uma afirmação universal

Para mostrar que ∀x ∈ U, P (x) é falsa, basta exibir um único elemento a ∈ U tal
que P (a) seja falsa. Tal elemento é chamado contraexemplo. Essa é, em essência, a
estratégia de refutação mais direta em matemática, e será revisitada extensivamente
no Capítulo 3.

Observação 2.24 Quantificadores múltiplos e a estrutura de ∀

Uma sutileza importante: ∀x ∈ U, P (x) é uma conjunção generalizada: se U =
{a1 , . . . , an } fosse finito, teríamos ∀x ∈ U, P (x) ≡ P (a1 ) ∧ P (a2 ) ∧ · · · ∧ P (an ).
Analogamente, ∃x ∈ U, P (x) é uma disjunção generalizada: ∃x ∈ U, P (x) ≡
P (a1 )∨P (a2 )∨· · ·∨P (an ). Essa observação, embora informal para universos infinitos,
ajuda a entender por que as regras de negação de quantificadores (a seguir) são versões
generalizadas das Leis de De Morgan.

2.3.3 Negação de quantificadores

Teorema 2.25 Negação de quantificadores
Para qualquer predicado P (x) com universo de discurso U :


¬ ∀x ∈ U, P (x) ≡ ∃x ∈ U, ¬P (x),


¬ ∃x ∈ U, P (x) ≡ ∀x ∈ U, ¬P (x).

Proof. Justificamos semanticamente (a verificação por tabela-verdade não se aplica dire-

tamente, pois quantificadores não são conectivos proposicionais no sentido do Capítulo 1,
2.3. Lógica de predicados 29

mas o argumento a seguir é igualmente rigoroso).

Para a primeira equivalência: ¬ ∀x ∈ U, P (x) é verdadeira exatamente quando não é

o caso que P (x) vale para todo x ∈ U , ou seja, exatamente quando existe algum x ∈ U
para o qual P (x) falha, isto é, para o qual ¬P (x) é verdadeira. Mas essa é exatamente
a condição de verdade de ∃x ∈ U, ¬P (x). Logo, as duas proposições são verdadeiras
exatamente nas mesmas circunstâncias, isto é, são logicamente equivalentes.
A segunda equivalência segue de maneira análoga: ¬ ∃x ∈ U, P (x) é verdadeira exata-

mente quando não existe x ∈ U satisfazendo P (x), isto é, quando todo x ∈ U satisfaz
¬P (x), que é a condição de verdade de ∀x ∈ U, ¬P (x). ■

Observação 2.26
Esta é, de fato, uma generalização das Leis de De Morgan: assim como ¬(p ∧ q) ≡
¬p∨¬q troca ∧ por ∨ ao negar, temos que ¬∀ troca-se por ∃¬; e assim como ¬(p∨q) ≡
¬p ∧ ¬q, temos ¬∃ trocando-se por ∀¬. A negação sempre "empurra" o sinal ¬
para dentro, trocando o tipo de quantificador (ou de conectivo) e negando
o predicado (ou proposição) interno.

Exemplo 2.27
Negue a proposição: "Todo número primo é ímpar" (∀n ∈ U, primo(n) → ímpar(n),
onde U é o conjunto dos números naturais maiores que 1).
Pela regra de negação do quantificador universal:

¬ ∀n, primo(n) → ímpar(n) ≡ ∃n, ¬ primo(n) → ímpar(n) .

Pela negação do condicional (Corolário 1.1):

¬ primo(n) → ímpar(n) ≡ primo(n) ∧ ¬ímpar(n) ≡ primo(n) ∧ par(n).

Logo, a negação completa é:

∃n, primo(n) ∧ par(n),

isto é: "Existe um número primo que é par". Esta afirmação é, de fato, verdadeira
(basta tomar n = 2), o que confirma – consistentemente com nossa expectativa – que
a afirmação original ("todo primo é ímpar") é falsa, pois sua negação é verdadeira.

2.3.4 Ordem dos quantificadores

Quando múltiplos quantificadores aparecem em uma mesma sentença, a ordem em que
aparecem é crucial e, em geral, não pode ser alterada sem mudar o significado (e o
valor de verdade) da proposição.

Exemplo 2.28
Considere o universo de discurso R e as duas sentenças:

(A) ∀x ∈ R, ∃y ∈ R, y > x versus (B) ∃y ∈ R, ∀x ∈ R, y > x.

30 Chapter 2. Regras de Inferência e Lógica de Predicados

A sentença (A) afirma: "para todo real x, existe um real y maior que x" – isto é,
não há um "maior número real"; sempre podemos encontrar um número maior que
qualquer x dado (por exemplo, y = x+1 sempre serve). Esta afirmação é verdadeira.
A sentença (B) afirma: "existe um real y que é maior que todo real x" – isto é, existe
um "maior número real" que supera todos os outros simultaneamente. Esta afirmação
é falsa: dado qualquer candidato a y, o número y + 1 é maior que y, contradizendo
que y seja maior que todo x (em particular, maior que x = y + 1).
Este exemplo mostra, de maneira contundente, que trocar a ordem de ∀ e ∃ pode trans-
formar uma afirmação verdadeira em falsa. A intuição correta é: em ∀x ∃y P (x, y), o
elemento y pode (e geralmente deve) depender de x – lemos "para cada x, existe um
y (que pode depender de x) tal que..."; já em ∃y ∀x P (x, y), o mesmo y deve funcionar
simultaneamente para todos os valores de x – um único y "universal".

Observação 2.29
Uma regra segura (mas não universalmente válida em sentido inverso) é a seguinte:
∃y ∀x P (x, y) implica ∀x ∃y P (x, y) (se existe um y que serve para todos os x, então
em particular, para cada x, este mesmo y serve). A recíproca, como o exemplo anterior
demonstra, é falsa em geral.

Observação 2.30
Quando os quantificadores são do mesmo tipo (ambos ∀ ou ambos ∃), a ordem pode
ser trocada livremente sem alterar o valor de verdade: ∀x ∀y P (x, y) ≡ ∀y ∀x P (x, y), e
∃x ∃y P (x, y) ≡ ∃y ∃x P (x, y). O cuidado é necessário apenas quando quantificadores
de tipos diferentes estão envolvidos.

2.3.5 Tradução de sentenças matemáticas

Exemplo 2.31
Traduza para linguagem simbólica a definição de função contínua em um ponto
(que o leitor revisitará, com mais profundidade, em um curso de Análise): "f é con-
tínua em a se, para todo ε > 0, existe δ > 0 tal que, para todo x, se |x − a| < δ, então
|f (x) − f (a)| < ε".


∀ε > 0, ∃δ > 0, ∀x, |x − a| < δ → |f (x) − f (a)| < ε .
Note a estrutura ∀∃∀: para cada margem de erro ε (por menor que seja), deve existir
uma margem δ (que pode depender de ε) tal que todo x suficientemente próximo de
a (a menos de δ) tenha imagem suficientemente próxima de f (a) (a menos de ε).
A ordem dos quantificadores aqui é absolutamente essencial: δ depende de ε, e essa
dependência é precisamente capturada pela ordem ∀ε ∃δ (e não o contrário).

Exemplo 2.32
Traduza: "Todo número racional pode ser escrito como razão de dois inteiros, com
denominador não nulo".
2.4. Exercícios 31

Sendo Q o universo de discurso da variável q e Z o universo das variáveis a, b:

∀q ∈ Q, ∃a, b ∈ Z, b ̸= 0 ∧ q = ab .

Exemplo 2.33
Traduza e depois negue: "Existe um número natural que é maior que todos os demais
números naturais".
∃n ∈ N, ∀m ∈ N, (m ̸= n → n > m).
Negando, aplicamos as regras sucessivamente:



¬ ∃n ∀m (m ̸= n → n > m) ≡ ∀n ¬ ∀m (m ̸= n → n > m) ≡ ∀n ∃m ¬(m ̸= n → n > m).

Usando a negação do condicional:

¬(m ̸= n → n > m) ≡ (m ̸= n) ∧ ¬(n > m) ≡ (m ̸= n) ∧ (n ≤ m).

Logo, a negação completa é:

∀n ∈ N, ∃m ∈ N, (m ̸= n ∧ n ≤ m),

isto é: "para todo natural n, existe outro natural m (diferente de n) tal que n ≤
m" – ou seja, nenhum natural é o maior de todos, pois sempre existe outro (por
exemplo, maior ou igual). Esta afirmação é, de fato, verdadeira nos naturais, o que
é consistente com a afirmação original ser falsa.

2.4 Exercícios
Exercício 2.34. Verifique, por meio de argumento semântico (como o utilizado na
demonstração do Silogismo Hipotético), a validade das regras de inferência do Teorema
2.3: Adição, Simplificação, Conjunção, Dilema Construtivo e Resolução.

Exercício 2.35. Dadas as premissas

1. ¬p ∨ q

2. ¬q ∨ r

3. p

deduza r por uma cadeia de inferências, justificando cada passo com o nome da regra
utilizada.

Exercício 2.36. Dadas as premissas

1. Se o algoritmo termina, então ele produz uma saída correta (p → q);

2. Se ele produz uma saída correta, então o programa foi bem testado (q → r);

3. O programa não foi bem testado (¬r);

32 Chapter 2. Regras de Inferência e Lógica de Predicados

deduza logicamente que "o algoritmo não termina", indicando as regras de inferência
utilizadas em cada passo.

Exercício 2.37. Considere o universo de discurso Z. Determine o valor de verdade (V

ou F) de cada proposição, justificando:
(a) ∀n ∈ Z, n2 ≥ 0;
(b) ∃n ∈ Z, n2 = −1;
(c) ∀n ∈ Z, ∃m ∈ Z, n + m = 0;
(d) ∃m ∈ Z, ∀n ∈ Z, n + m = n.

Exercício 2.38. Negue cada uma das seguintes proposições, simplificando ao máximo:
(a) ∀x ∈ R, x2 > 0;
(b) ∃x ∈ R, ∀y ∈ R, x + y = y;
(c) ∀ε > 0, ∃N ∈ N, ∀n ≥ N, |an − L| < ε (esta é a definição de limite de sequência,
que o leitor revisitará em Análise);
(d) ∀n ∈ N, n > 2 → ∃p primo, p | n .

Exercício 2.39. Traduza cada sentença para a linguagem simbólica da lógica de predi-
cados, especificando claramente universos de discurso:
(a) "Todo número inteiro é a soma de quatro quadrados perfeitos" (Teorema de La-
grange);
(b) "Não existe um maior número primo";
(c) "Para cada número real positivo, existe uma raiz quadrada real";
(d) "A equação x2 + 1 = 0 não possui solução real".

Exercício 2.40. Explique, com um exemplo diferente do apresentado no texto, por que
a sentença ∀x ∃y P (x, y) não é, em geral, equivalente a ∃y ∀x P (x, y).

Exercício 2.41. avançado Mostre que a proposição ∃x ∀y P (x, y) → ∀y ∃x P (x, y) é sem-

pre verdadeira (para qualquer predicado P e universo não vazio), mas que sua recíproca
não é, em geral, verdadeira. (Sugestão: para a primeira parte, argumente semanticamente,
como fizemos com o Silogismo Hipotético; para a segunda, exiba um contraexemplo.)
Capítulo 3

Demonstrações Matemáticas

3.1 O que é uma demonstração?

Chegamos ao coração desta apostila. Os dois capítulos anteriores forneceram a linguagem
(proposições, predicados, quantificadores) e a gramática (conectivos, regras de inferência)
da lógica matemática. Agora usaremos essas ferramentas para compreender profunda-
mente o que é, estruturalmente, uma demonstração matemática, e para dominar as
principais técnicas empregadas para construí-las.

Definição 3.1 Demonstração

Uma demonstração (ou prova) de uma proposição Q, a partir de um conjunto de
premissas (axiomas, definições e teoremas previamente estabelecidos) P1 , . . . , Pn , é
uma sequência finita de proposições

Q1 , Q2 , . . . , Qk = Q

tal que cada Qi é ou (a) uma das premissas Pj , ou (b) um axioma ou definição, ou
(c) uma consequência lógica de proposições anteriores na sequência, obtida por uma
regra de inferência válida (como as estudadas no Capítulo 2).

Observação 3.2
Esta definição é, em certo sentido, o ideal formal de uma demonstração – o que se
estuda rigorosamente em lógica matemática e teoria da demonstração. Na prática
do dia a dia matemático, as demonstrações são escritas em linguagem natural (com
símbolos matemáticos), omitindo os passos mais elementares e óbvios (como aplicações
triviais de Modus Ponens), mas toda demonstração matemática correta pode, em
princípio, ser expandida até essa forma totalmente formal. É esse fato que confere
às demonstrações matemáticas seu caráter de certeza absoluta, em contraste com
argumentos empíricos ou indutivos das ciências naturais.

A maior parte dos teoremas matemáticos tem a forma de um condicional (possivelmente

com quantificadores universais):

∀x ∈ U, H(x) → T (x),

onde H(x) é a hipótese e T (x) é a tese. Demonstrar tal teorema significa mostrar
que, para qualquer elemento x do universo U que satisfaça a hipótese H(x), a tese
T (x) também é satisfeita. É essa estrutura – hipótese e tese, ligadas por um condicional

33
34 Chapter 3. Demonstrações Matemáticas

universalmente quantificado – que organiza a quase totalidade das técnicas apresentadas

neste capítulo.
Observação 3.3 Estratégia geral para provar afirmações universais
Para demonstrar ∀x ∈ U, P (x), a estratégia padrão é: tomar um elemento arbitrário
(porém fixo) x ∈ U , e demonstrar P (x) usando apenas propriedades genéricas de
x enquanto elemento de U – nunca propriedades particulares que só um elemento
específico teria. Como x foi tomado arbitrariamente, a conclusão P (x) valerá para
qualquer escolha de x, e portanto para todos os elementos de U . Essa é a chamada
regra de generalização universal, e será usada implicitamente em praticamente
todas as demonstrações desta apostila.

3.2 Demonstração direta

3.2.1 Estrutura lógica
A demonstração direta é a técnica mais natural para provar um condicional p → q:
assume-se p como verdadeira e, por uma cadeia de implicações e regras de inferência
válidas, deriva-se q.
Observação 3.4 Quando utilizar
A demonstração direta é a primeira técnica a ser tentada sempre que a hipótese p
fornece informação suficientemente concreta e manipulável (por exemplo, uma equação
algébrica, uma definição explícita) para se progredir diretamente rumo à tese q.
Quando a hipótese é "negativa" (por exemplo, "x não é racional") ou quando é difícil
ver como progredir diretamente, outras técnicas (contraposição, contradição) costu-
mam ser mais eficazes, como discutiremos nas seções seguintes.

Observação 3.5 Por que funciona

A validade da demonstração direta é assegurada precisamente pelo Modus Ponens
(Teorema 2.1): se estabelecemos uma cadeia p → r1 → r2 → · · · → q (cada implicação
devidamente justificada), então, por aplicações sucessivas de Modus Ponens (ou, de
forma mais direta, pelo Silogismo Hipotético generalizado), obtemos p → q.

Definição 3.6 Números pares e ímpares

Um número inteiro n é par quando existe k ∈ Z tal que n = 2k. Um número inteiro
n é ímpar quando existe k ∈ Z tal que n = 2k + 1.

Proposição 3.7
Se n é um inteiro par, então n2 é par.

Proof. Suponhamos que n seja par. Pela Definição 3.1, existe k ∈ Z tal que n = 2k.
Elevando ao quadrado:
n2 = (2k)2 = 4k 2 = 2(2k 2 ).
Como k ∈ Z, temos que 2k 2 ∈ Z; chamando m = 2k 2 ∈ Z, obtemos n2 = 2m, com m ∈ Z.
Pela Definição 3.1, isso significa exatamente que n2 é par. ■
3.3. Demonstração por contraposição 35

Observação 3.8
Note a estrutura cuidadosa da demonstração: (1) traduzimos a hipótese "n é par"
para sua forma algébrica precisa, via definição; (2) manipulamos algebricamente; (3)
reconhecemos que o resultado tem a forma exigida pela definição de "par"; (4) con-
cluímos. Cada uma dessas etapas é necessária e nenhuma pode ser omitida em uma
demonstração rigorosa, ainda que, em textos mais avançados, alguns desses passos
sejam condensados.

Proposição 3.9
Se a e b são inteiros ímpares, então a + b é par.

Proof. Suponhamos que a e b sejam ímpares. Pela Definição 3.1, existem j, k ∈ Z tais
que a = 2j + 1 e b = 2k + 1. Somando:
a + b = (2j + 1) + (2k + 1) = 2j + 2k + 2 = 2(j + k + 1).
Como j, k ∈ Z, temos j + k + 1 ∈ Z. Denotando m = j + k + 1 ∈ Z, obtemos a + b = 2m,
com m ∈ Z, o que significa, pela Definição 3.1, que a + b é par. ■

Proposição 3.10
Se a divide b e b divide c (com a, b, c ∈ Z, b ̸= 0), então a divide c.

Definição 3.11 Divisibilidade

Dados a, b ∈ Z, dizemos que a divide b, denotado a | b, quando existe k ∈ Z tal que
b = ak.

Proof. Suponhamos a | b e b | c. Pela Definição 3.2, existem k1 , k2 ∈ Z tais que

b = ak1 e c = bk2 .
Substituindo a primeira igualdade na segunda:
c = bk2 = (ak1 )k2 = a(k1 k2 ).
Como k1 , k2 ∈ Z, temos k1 k2 ∈ Z. Denotando m = k1 k2 ∈ Z, obtemos c = am, com
m ∈ Z, o que significa, pela Definição 3.2, que a | c. ■

Observação 3.12
Esta última proposição estabelece a transitividade da relação de divisibilidade, pro-
priedade que será usada livremente em capítulos e cursos posteriores (por exemplo, em
Teoria dos Números) sem nova demonstração, exatamente como fazemos com teoremas
já estabelecidos.

3.3 Demonstração por contraposição

3.3.1 Estrutura lógica
Pelo item (xiv) do Teorema 1.1, sabemos que p → q ≡ ¬q → ¬p. A demonstração
por contraposição explora essa equivalência: em vez de demonstrar diretamente p → q,
36 Chapter 3. Demonstrações Matemáticas

demonstra-se (diretamente) o condicional equivalente ¬q → ¬p, isto é: assume-se que a

tese q é falsa e demonstra-se que, necessariamente, a hipótese p também é falsa.

Observação 3.13 Por que funciona

A técnica é válida precisamente porque p → q e ¬q → ¬p são logicamente equiva-
lentes (Teorema 1.1, item xiv): demonstrar uma é logicamente o mesmo que demon-
strar a outra. Não há, portanto, nenhuma "perda de rigor" ao optar pela contraposição
– é apenas uma escolha estratégica de qual condicional é mais fácil de demonstrar di-
retamente.

Observação 3.14 Quando utilizar

A contraposição é particularmente útil quando a tese q envolve uma negação (de modo
que ¬q se torna uma afirmação "positiva" e mais manipulável), ou quando a hipótese
p é difícil de usar diretamente, mas sua negação ¬p fornece uma via mais clara para
a manipulação algébrica ou lógica.

Proposição 3.15
Seja n ∈ Z. Se n2 é par, então n é par.

Proof. Demonstraremos a contrapositiva: se n não é par (isto é, n é ímpar), então n2

não é par (isto é, n2 é ímpar).
Suponhamos que n seja ímpar. Pela Definição 3.1, existe k ∈ Z tal que n = 2k +1. Então:

n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1.

Como k ∈ Z, temos 2k 2 + 2k ∈ Z. Denotando m = 2k 2 + 2k ∈ Z, obtemos n2 = 2m + 1,

com m ∈ Z, o que significa, pela Definição 3.1, que n2 é ímpar.
Como a contrapositiva foi demonstrada, e p → q ≡ ¬q → ¬p, concluímos que a proposição
original é verdadeira: se n2 é par, então n é par. ■

Observação 3.16
Vale a pena comparar esta demonstração com uma tentativa de prova direta: partindo
de "n2 é par", isto é, n2 = 2m para algum m ∈ Z, não há um caminho algébrico
evidente para concluir que n = 2k para algum k (não podemos, em geral, "tirar a
raiz quadrada" de forma a preservar a estrutura inteira de maneira simples). Já a
contrapositiva parte de uma hipótese explícita e manipulável (n ímpar, isto é, n =
2k+1) e chega facilmente à conclusão desejada. Este exemplo ilustra perfeitamente por
que a escolha da técnica de demonstração é uma decisão estratégica, não meramente
formal.

Proposição 3.17
Sejam a, b ∈ Z. Se ab é ímpar, então a é ímpar e b é ímpar.

Proof. Demonstraremos a contrapositiva. A negação da tese "a é ímpar e b é ímpar" é,

por De Morgan, "a é par ou b é par". Devemos, portanto, demonstrar: se a é par ou b é
par, então ab é par.
3.4. Demonstração por contradição 37

Por demonstração por casos (técnica que formalizaremos na Seção 3.5), consideremos
separadamente as duas possibilidades da disjunção.
Caso 1: a é par. Então existe k ∈ Z tal que a = 2k. Logo, ab = (2k)b = 2(kb). Como
k, b ∈ Z, temos kb ∈ Z; denotando m = kb, obtemos ab = 2m, ou seja, ab é par.
Caso 2: b é par. De maneira inteiramente análoga (trocando os papéis de a e b), existe
k ∈ Z tal que b = 2k, e ab = a(2k) = 2(ak), com ak ∈ Z, logo ab é par.
Em ambos os casos, ab é par, o que estabelece a contrapositiva e, portanto, a proposição
original. ■

3.4 Demonstração por contradição

3.4.1 Estrutura lógica
A demonstração por contradição (também chamada redução ao absurdo, do latim
reductio ad absurdum) é uma das técnicas mais poderosas e versáteis da matemática.
Para demonstrar uma proposição Q (não necessariamente um condicional), supõe-se ¬Q
como hipótese adicional e busca-se derivar uma contradição – isto é, uma proposição da
forma R ∧ ¬R, para alguma proposição R.
Teorema 3.18 Validade lógica da demonstração por contradição
Para demonstrar que uma proposição Q é verdadeira, basta demonstrar que ¬Q → F
é verdadeira, onde F denota uma contradição (proposição sempre falsa).

Proof. Suponhamos que ¬Q → F seja verdadeira. Como F é sempre falsa, e o condicional

¬Q → F é verdadeiro, pela tabela-verdade do condicional (a única forma de p → q ser
verdadeira com q falso é p também ser falso) concluímos que ¬Q deve ser falsa. Mas se
¬Q é falsa, então, pela dupla negação, Q é verdadeira.
Alternativamente, e de forma equivalente: a proposição (¬Q → F ) → Q é uma tautologia,
como se verifica diretamente por tabela-verdade:

Q ¬Q ¬Q → F (¬Q → F ) → Q
V F V V
F V F V

(lembrando que F é sempre falsa). A última coluna é sempre V, confirmando a tautologia.

■

Observação 3.19 Quando utilizar e por que funciona

A demonstração por contradição é especialmente útil para provar afirmações de não
√
existência ou impossibilidade (como "não existe o maior número primo", ou " 2
não é racional"), situações em que é difícil imaginar uma construção direta, mas
é natural explorar as consequências de supor o contrário. Sua validade lógica está
assegurada pelo Teorema 3.1: negar a tese e chegar a uma contradição é logicamente
equivalente a demonstrar a tese diretamente.
38 Chapter 3. Demonstrações Matemáticas

Observação 3.20 Limitações

A demonstração por contradição, apesar de poderosa, é frequentemente considerada
menos elegante e menos informativa que uma demonstração direta ou por con-
traposição, pois não revela explicitamente por que a afirmação é verdadeira, apenas
que sua negação é impossível. Sempre que uma demonstração direta ou por contra-
posição estiver disponível de forma natural, ela costuma ser preferível. Além disso, em
certas correntes da lógica (o intuicionismo), a demonstração por contradição pura
– especialmente quando usada para provar afirmações de existência – é consider-
ada problematica, pois não fornece um método construtivo para exibir o objeto cuja
existência se afirma (voltaremos a esse ponto na Seção 3.7).

Teorema 3.21
√
2 é irracional.
√
Proof. Suponhamos, por contradição, que 2 seja racional. Então existem inteiros a, b,
com b ̸= 0, tais que
√ a
2= ,
b
e podemos supor, sem perda de generalidade, que a fração ab está em sua forma irre-
dutível, isto é, que mdc(a, b) = 1 (caso contrário, simplificamos a fração até que isso
ocorra; tal simplificação é sempre possível pois o processo de divisão pelo máximo divisor
comum termina em um número finito de passos).
Elevando ambos os lados ao quadrado:

a2
2= =⇒ a2 = 2b2 .
b2
Isso mostra que a2 é par (pois é igual a 2b2 , que tem a forma 2 · (inteiro)). Pela Proposição
3.4 (demonstrada por contraposição na seção anterior), como a2 é par, segue que a é par.
Logo, existe k ∈ Z tal que a = 2k.
Substituindo na equação a2 = 2b2 :

(2k)2 = 2b2 =⇒ 4k 2 = 2b2 =⇒ b2 = 2k 2 .

Isso mostra que b2 também é par, e novamente pela Proposição 3.4, segue que b é par.
Concluímos que tanto a quanto b são pares. Mas isso contradiz o fato de que
mdc(a, b) = 1 (se ambos fossem pares, 2 seria um divisor comum de a e b, maior que
1, contradizendo a irredutibilidade da fração).
Chegamos a uma contradição (a√ saber: mdc(a, b) = 1 e 2 | mdc(a,
√ b), simultaneamente).
Logo, a suposição inicial de que 2 é racional é falsa. Portanto, 2 é irracional. ■

Observação 3.22
Esta demonstração, atribuída aos matemáticos gregos antigos (possivelmente à escola
pitagórica), é um dos exemplos mais célebres e mais antigos de demonstração por
contradição na história da matemática, e ilustra perfeitamente a estrutura: (1) negar
a tese; (2) manipular algebricamente até encontrar uma afirmação que contradiz uma
3.5. Demonstração por casos 39

hipótese ou fato já estabelecido; (3) concluir que a negação da tese é impossível, e

portanto a tese original é verdadeira. Note também como esta demonstração utiliza
um resultado anterior (Proposição 3.4) – ilustrando como o edifício da matemática se
constrói por acumulação de resultados, cada um se apoiando nos anteriores.

Teorema 3.23 Euclides

Existem infinitos números primos.

Proof. Suponhamos, por contradição, que existam apenas finitos números primos. Então
podemos listá-los todos: p1 , p2 , . . . , pn (para algum n ∈ N).
Considere o número
N = p1 · p2 · · · pn + 1.
Como N > 1, pelo Teorema Fundamental da Aritmética (que assumimos aqui como
conhecido; será revisitado em cursos de Teoria dos Números), N possui pelo menos um
divisor primo, digamos q.
Afirmamos que q não pode ser nenhum dos primos p1 , . . . , pn da lista original. De fato,
suponha, por contradição adicional (uma segunda redução ao absurdo, aninhada dentro
da primeira), que q = pi para algum i ∈ {1, . . . , n}. Então q divide o produto p1 p2 · · · pn
(pois q = pi é um dos fatores) e, por hipótese, q divide N = p1 · · · pn + 1. Pela Proposição
de divisibilidade (se q divide dois números, divide sua diferença – fato que se demonstra
facilmente a partir da Definição 3.2, e que deixamos como exercício), q divide

N − p1 p2 · · · pn = 1.

Mas nenhum número primo divide 1 (pois todo primo é, por definição, maior que 1, e um
divisor de 1 deve ser, no máximo, igual a 1 em valor absoluto). Isso é uma contradição.
Logo, q é um primo que não pertence à lista p1 , . . . , pn , contradizendo a suposição de que
essa lista contém todos os números primos.
Concluímos que a suposição inicial (existem apenas finitos primos) é falsa. Portanto,
existem infinitos números primos. ■

Observação 3.24
Esta é outra demonstração clássica, também atribuída a Euclides. Note a estrutura
elegante: não construímos explicitamente um "próximo primo maior", mas mostramos
que, para qualquer lista finita e completa hipotética, é possível encontrar um primo
fora dela – uma contradição direta com a completude da lista.

3.5 Demonstração por casos

3.5.1 Estrutura lógica
Muitas vezes, a hipótese de um teorema, ou a natureza do universo de discurso, permite
uma divisão natural em um número finito de casos exaustivos e mutuamente exclu-
sivos (ou não necessariamente exclusivos, mas que cobrem todas as possibilidades). A
40 Chapter 3. Demonstrações Matemáticas

demonstração por casos consiste em demonstrar a tese separadamente em cada um

desses casos.
Teorema 3.25 Validade lógica da demonstração por casos
Sejam p1 , p2 , . . . , pk proposições tais que p1 ∨ p2 ∨ · · · ∨ pk é verdadeira (isto é, os casos
são exaustivos), e suponha que pi → q seja verdadeira para cada i = 1, . . . , k. Então
q é verdadeira.

Proof. Faremos a demonstração para k = 2; o caso geral segue por indução no número
de casos (técnica que formalizaremos no Capítulo 4), aplicando repetidamente o mesmo
argumento.
Suponha p1 ∨ p2 verdadeira, e suponha p1 → q e p2 → q ambas verdadeiras. Como p1 ∨ p2
é verdadeira, ao menos uma das proposições p1 , p2 é verdadeira.
Se p1 é verdadeira: como p1 → q é verdadeira, por Modus Ponens, q é verdadeira.
Se p2 é verdadeira: como p2 → q é verdadeira, por Modus Ponens, q é verdadeira.
Em ambas as situações possíveis (dado que p1 ∨ p2 é verdadeira), concluímos q. Logo, q
é verdadeira. ■

Observação 3.26 Quando utilizar

A demonstração por casos é indicada quando a hipótese naturalmente se subdivide
(por exemplo, "n é par ou ímpar", "x > 0, x = 0, ou x < 0", "a divide b ou
não divide"), e quando cada subcaso, embora mais simples que o problema original,
requer um argumento distinto. É essencial verificar que os casos considerados são de
fato exaustivos (cobrem todas as possibilidades) – omitir um caso é um erro lógico
grave, que discutiremos na Seção 4.6.

Proposição 3.27
Para todo n ∈ Z, o número n2 + n é par.

Proof. Como todo inteiro é par ou ímpar (fato que assumiremos aqui; formalmente
decorre da divisão euclidiana), consideramos dois casos.
Caso 1: n é par. Então n = 2k para algum k ∈ Z. Logo,

n2 + n = (2k)2 + 2k = 4k 2 + 2k = 2(2k 2 + k).

Como 2k 2 + k ∈ Z, concluímos que n2 + n é par.

Caso 2: n é ímpar. Então n = 2k + 1 para algum k ∈ Z. Logo,

n2 + n = (2k + 1)2 + (2k + 1) = (4k 2 + 4k + 1) + (2k + 1) = 4k 2 + 6k + 2 = 2(2k 2 + 3k + 1).

Como 2k 2 + 3k + 1 ∈ Z, concluímos que n2 + n é par.

Como todo inteiro n é par ou ímpar (casos exaustivos), e em ambos os casos n2 + n é par,
concluímos que n2 + n é par para todo n ∈ Z. ■
3.6. Demonstrações construtivas e não construtivas 41

Proposição 3.28
Para todo x ∈ R, |x| ≥ x (onde |x| denota o valor absoluto de x).

Definição 3.29 Valor absoluto

Para x ∈ R, o valor absoluto de x é definido por
(
x, se x ≥ 0,
|x| =
−x, se x < 0.

Proof. Pela Definição 3.3, consideramos os dois casos possíveis para x ∈ R.

Caso 1: x ≥ 0. Então, pela definição, |x| = x. Logo, |x| ≥ x (com igualdade).
Caso 2: x < 0. Então, pela definição, |x| = −x. Como x < 0, temos −x > 0 > x, logo
−x > x, ou seja, |x| > x, e em particular |x| ≥ x.
Como todo real satisfaz x ≥ 0 ou x < 0 (casos exaustivos e mutuamente exclusivos), e
em ambos os casos |x| ≥ x, concluímos que |x| ≥ x para todo x ∈ R. ■

3.6 Demonstrações construtivas e não construtivas

Definição 3.30 Demonstração construtiva
Uma demonstração construtiva de uma afirmação de existência ∃x ∈ U, P (x) é
aquela que exibe explicitamente (ou fornece um procedimento explícito para construir)
um elemento particular a ∈ U satisfazendo P (a).

Definição 3.31 Demonstração não construtiva

Uma demonstração não construtiva de ∃x ∈ U, P (x) é aquela que estabelece a
existência de tal x sem exibir explicitamente um elemento particular – por exemplo,
argumentando por contradição que a não existência seria impossível, sem, no processo,
revelar quem é o elemento.

Exemplo 3.32 Demonstração construtiva

Afirmação: existe um número natural par maior que 1000000.
Demonstração: O número 1000002 = 2 × 500001 é par (pela Definição 3.1, com
k = 500001) e é maior que 1000000. Logo, x = 1000002 satisfaz a propriedade
desejada, o que demonstra a existência afirmada. ■
Esta é uma demonstração construtiva: exibimos explicitamente o objeto cuja existên-
cia estava sendo afirmada.

Teorema 3.33
Existem números irracionais a, b tais que ab é racional.
√
√ 2
Proof. Consideremos o número 2 . Este número é ou racional ou irracional (pelo
√ √2
Princípio do Terceiro Excluído, Teorema 1.1, item (x), aplicado à proposição " 2 é
42 Chapter 3. Demonstrações Matemáticas

racional"). Analisamos os dois casos.

√ √2 √ √
Caso 1: 2 é racional. Neste caso, tomamos a = b = 2. Como√ 2 é irracional
√ 2
(Teorema 3.2), temos a, b irracionais, e por√hipótese deste caso, ab = 2 é racional. A
afirmação está demonstrada, com a = b = 2.
√ √2 √ √2
Caso 2: 2 é√irracional. Neste caso, tomamos a = 2 (irracional, por hipótese
deste caso) e b = 2 (irracional, pelo Teorema 3.2). Calculamos:
 √ √2
b
√ 2 √ √2·√2 √ 2
a = 2 = 2 = 2 = 2,
√
√ 2 √
que é racional. A afirmação está demonstrada, com a = 2 eb= 2.
Em ambos os casos (exaustivos, pelo terceiro excluído), exibimos a, b irracionais com ab
racional. Logo, tais números existem. ■

Observação 3.34
Esta é uma demonstração não construtiva, ainda que estruturada como uma demon-
stração por casos: não sabemos, ao final da prova, qual dos dois casos de fato
√ √2
ocorre (isto é, não sabemos, com os métodos elementares aqui apresentados, se 2
é racional ou irracional) – e, ainda assim, a demonstração é completamente rigorosa e
válida: em qualquer dos dois casos possíveis (e eles esgotam todas as possibilidades,
pelo terceiro excluído), a existência afirmada se verifica. Este é um exemplo célebre e
instrutivo de como a lógica clássica permite estabelecer existência sem necessariamente
revelar o objeto que a testemunha. (Observe que, de fato, sabe-se hoje, por resultados
√ √2
mais avançados de teoria dos números transcendentes, que 2 é irracional – e, de
fato, transcendente, pelo Teorema de Gelfond-Schneider – mas isso é irrelevante para
a validade da demonstração acima, que não depende de sabermos qual caso ocorre.)

3.7 Existência e unicidade

Muitos teoremas afirmam não apenas que um objeto com certa propriedade existe, mas
que ele é único. Como formalizado na Observação 2.2, a afirmação "existe um único x
tal que P (x)" (simbolicamente ∃!x, P (x)) desmembra-se em duas partes lógicas distintas,
e a demonstração correspondente deve, portanto, ter duas partes bem definidas.
Observação 3.35 Estrutura de uma demonstração de existência e unicidade
Para demonstrar ∃!x ∈ U, P (x), procede-se em duas etapas:
1. Existência: exibe-se (construtivamente ou não) algum a ∈ U tal que P (a) é
verdadeira.
2. Unicidade: supõe-se que a, b ∈ U satisfazem ambos P (a) e P (b), e demonstra-
se que necessariamente a = b (tipicamente, esta parte é conduzida como uma
demonstração direta ou por contradição).
Nenhuma das duas etapas, isoladamente, é suficiente: mostrar apenas existência não
descarta a possibilidade de haver múltiplos objetos com a propriedade P ; mostrar
apenas unicidade (isto é, que quaisquer dois objetos satisfazendo P são iguais) não
3.8. Demonstrações envolvendo conjuntos 43

garante que algum objeto de fato satisfaça P – poderia não haver nenhum.

Teorema 3.36
Para todo a, b ∈ R com a ̸= 0, existe um único x ∈ R tal que ax + b = 0.

b
Proof. Existência. Considere x = − (bem definido, pois a ̸= 0 por hipótese). Substi-
a
tuindo na equação:
 
b
ax + b = a − + b = −b + b = 0.
a
Logo, x = −b/a satisfaz a equação, o que estabelece a existência.
Unicidade. Suponhamos que x1 , x2 ∈ R satisfaçam ambos ax1 + b = 0 e ax2 + b = 0.
Subtraindo as duas equações:

(ax1 + b) − (ax2 + b) = 0 − 0 =⇒ a(x1 − x2 ) = 0.

Como a ̸= 0 (hipótese do teorema), e o produto de dois reais é zero apenas quando pelo
menos um dos fatores é zero (propriedade dos números reais, que assumimos conhecida),
concluímos que x1 − x2 = 0, isto é, x1 = x2 .
Como demonstramos existência e unicidade, concluímos que existe um único x ∈ R sat-
isfazendo ax + b = 0. ■

3.8 Demonstrações envolvendo conjuntos

A teoria dos conjuntos oferece um terreno fértil para a aplicação das técnicas de demon-
stração estudadas, especialmente porque as operações e relações entre conjuntos são
definidas diretamente em termos de quantificadores e conectivos lógicos.

Definição 3.37 Subconjunto

Dados conjuntos A e B, dizemos que A é subconjunto de B, denotado A ⊆ B,
quando
∀x, (x ∈ A → x ∈ B).

Definição 3.38 Igualdade de conjuntos

Dois conjuntos A e B são iguais, denotado A = B, quando A ⊆ B e B ⊆ A.

Observação 3.39 Estratégia padrão para A ⊆ B

Pela Definição 3.4, demonstrar A ⊆ B é, essencialmente, demonstrar uma afirmação
universal condicional: toma-se um elemento arbitrário x ∈ A e demonstra-se (direta-
mente, na maioria dos casos) que x ∈ B. Já demonstrar A = B requer duas demon-
strações de inclusão, em ambas as direções – exatamente como uma demonstração de
bicondicional requer as duas "metades" (→ e ←), como observado na Seção 1.4.
44 Chapter 3. Demonstrações Matemáticas

Definição 3.40 Operações com conjuntos

Dados conjuntos A, B (subconjuntos de um universo U ):

A∩B = {x : x ∈ A∧x ∈ B}, A∪B = {x : x ∈ A∨x ∈ B}, Ac = {x ∈ U : x ∈

/ A}.

Proposição 3.41
Para quaisquer conjuntos A, B: (A ∩ B)c = Ac ∪ B c .

Proof. Demonstraremos a igualdade de conjuntos mostrando as duas inclusões.

(i) (A ∩ B)c ⊆ Ac ∪ B c . Seja x ∈ (A ∩ B)c arbitrário. Pela Definição 3.5, isso significa
x∈/ A ∩ B, isto é, ¬(x ∈ A ∧ x ∈ B). Pelas Leis de De Morgan (Teorema 1.2):

¬(x ∈ A ∧ x ∈ B) ≡ (x ∈
/ A) ∨ (x ∈
/ B).

Logo, x ∈ / A ou x ∈/ B, isto é, x ∈ Ac ou x ∈ B c , ou seja, x ∈ Ac ∪ B c . Como x era

arbitrário, concluímos (A ∩ B)c ⊆ Ac ∪ B c .

(ii) Ac ∪ B c ⊆ (A ∩ B)c . Seja x ∈ Ac ∪ B c arbitrário. Então x ∈ Ac ou x ∈ B c , isto é,

x∈ / A ou x ∈/ B. Novamente por De Morgan (na direção inversa):

(x ∈
/ A) ∨ (x ∈
/ B) ≡ ¬(x ∈ A ∧ x ∈ B),

isto é, x ∈
/ A ∩ B, ou seja, x ∈ (A ∩ B)c . Como x era arbitrário, concluímos Ac ∪ B c ⊆
(A ∩ B)c .

Das duas inclusões (i) e (ii), pela Definição 3.4 de igualdade de conjuntos, concluímos
(A ∩ B)c = Ac ∪ B c . ■

Observação 3.42
Esta proposição – uma das Leis de De Morgan para conjuntos – ilustra de maneira
exemplar a tese central desta apostila: a demonstração é, em essência, uma tradução
direta, passo a passo, das Leis de De Morgan proposicionais (Teorema 1.2) para o
contexto de conjuntos, mediada apenas pelas definições de pertinência, união, inter-
seção e complemento. A lógica proposicional não é uma ferramenta auxiliar externa
à teoria dos conjuntos – ela é o mecanismo interno que faz a teoria dos conjuntos
funcionar.

3.9 Demonstrações envolvendo funções

Definição 3.43 Injetividade
Uma função f : A → B é injetiva quando

∀x1 , x2 ∈ A, f (x1 ) = f (x2 ) → x1 = x2 .

3.9. Demonstrações envolvendo funções 45

Definição 3.44 Sobrejetividade

Uma função f : A → B é sobrejetiva quando

∀y ∈ B, ∃x ∈ A, f (x) = y.

Observação 3.45
Note que a definição de injetividade é frequentemente demonstrada por contra-
posição: em vez de mostrar diretamente "f (x1 ) = f (x2 ) → x1 = x2 ", muitas vezes é
mais natural mostrar a contrapositiva "x1 ̸= x2 → f (x1 ) ̸= f (x2 )".

Proposição 3.46
A função f : R → R dada por f (x) = 3x − 5 é injetiva.

Proof. Sejam x1 , x2 ∈ R arbitrários, e suponhamos f (x1 ) = f (x2 ) (demonstração direta

da definição de injetividade). Então:
3x1 − 5 = 3x2 − 5.
Somando 5 a ambos os lados: 3x1 = 3x2 . Dividindo ambos os lados por 3 (possível, pois
3 ̸= 0): x1 = x2 .
Como x1 , x2 eram arbitrários satisfazendo f (x1 ) = f (x2 ), e concluímos x1 = x2 , está
demonstrado que f é injetiva. ■

Proposição 3.47
A função g : R → R dada por g(x) = x2 não é injetiva.

Proof. Para refutar a afirmação universal "∀x1 , x2 ∈ R, g(x1 ) = g(x2 ) → x1 = x2 ", basta
um contraexemplo (Observação 2.1). Tome x1 = 1 e x2 = −1. Temos g(x1 ) = 12 = 1 e
g(x2 ) = (−1)2 = 1, logo g(x1 ) = g(x2 ); porém x1 = 1 ̸= −1 = x2 . Logo, a condição de
injetividade falha para este par, e g não é injetiva. ■

Proposição 3.48
A função f : R → R dada por f (x) = 3x − 5 é sobrejetiva.

Proof. Seja y ∈ R arbitrário (demonstração direta da definição de sobrejetividade, que

começa fixando um elemento arbitrário do contradomínio). Devemos exibir x ∈ R tal que
f (x) = y, isto é, 3x − 5 = y. Resolvendo para x:
y+5
x= .
3
Como y ∈ R, temos x = (y + 5)/3 ∈ R, e é imediato verificar que
 
y+5
f (x) = 3 − 5 = (y + 5) − 5 = y.
3
Como y era arbitrário e exibimos x ∈ R com f (x) = y (demonstração construtiva),
concluímos que f é sobrejetiva. ■
46 Chapter 3. Demonstrações Matemáticas

3.10 Demonstrações envolvendo divisibilidade e desigual-

dades
Proposição 3.49
Para todo n ∈ N, se n ≥ 1, então n2 ≥ n.

Proof. Seja n ∈ N arbitrário com n ≥ 1. Como n ≥ 1 > 0, podemos multiplicar ambos

os lados da desigualdade n ≥ 1 por n (multiplicação por um número positivo preserva o
sentido da desigualdade, propriedade dos reais que assumimos conhecida):

n·n≥n·1 =⇒ n2 ≥ n.

Como n era arbitrário (satisfazendo n ≥ 1), concluímos n2 ≥ n para todo n ≥ 1. ■

Proposição 3.50
Sejam a, b, c ∈ Z. Se a | b e a | c, então a | (b + c).

Proof. Suponhamos a | b e a | c. Pela Definição 3.2, existem k1 , k2 ∈ Z tais que b = ak1

e c = ak2 . Somando:
b + c = ak1 + ak2 = a(k1 + k2 ).
Como k1 , k2 ∈ Z, temos k1 + k2 ∈ Z; denotando m = k1 + k2 , obtemos b + c = am, com
m ∈ Z, ou seja, a | (b + c). ■

Teorema 3.51 Desigualdade das médias aritmética e geométrica, caso n = 2

Para todos a, b ∈ R com a, b ≥ 0:
a+b √
≥ ab.
2
√ √
Proof. Como a,√ as raízes quadradas a e b estão bem definidas em R. Considere
b ≥ 0,√
o número real ( a − b)2 . Como todo quadrado de número real é não negativo (fato
elementar: se t ≥ 0, t2 ≥ 0; se t < 0, t2 = (−t)2 com −t > 0, logo t2 > 0; em ambos os
casos t2 ≥ 0), temos: √
√
( a − b)2 ≥ 0.
Expandindo o quadrado:
√ √ √
a − 2 a b + b ≥ 0 =⇒ a + b ≥ 2 ab,
√ √ √
usando que a b = ab (propriedade das raízes quadradas de números não negativos).
Dividindo ambos os lados por 2 (positivo, preserva a desigualdade):

a+b √
≥ ab.
2
■
3.11. Exercícios 47

Observação 3.52
Esta demonstração ilustra uma técnica algébrica recorrente: partir de um fato triv-
ialmente verdadeiro (aqui, "todo quadrado é não negativo") e manipulá-lo algebrica-
mente até obter a desigualdade desejada. Esse tipo de raciocínio "de trás para frente"
na fase de descoberta da demonstração (ainda que apresentado, na versão final, "para
frente") será discutido detalhadamente no Capítulo 4.

3.11 Exercícios
Exercício 3.53. Demonstre diretamente: se m e n são inteiros pares, então mn é
divisível por 4.

Exercício 3.54. Demonstre por contraposição: se n2 é divisível por 3, então n é divisível

por 3 (com n ∈ Z). (Sugestão: a contrapositiva deve considerar os casos n = 3k + 1 e
n = 3k + 2.)

Exercício 3.55. Demonstre por contradição que não existem inteiros a, b tais que
6a + 9b = 1. (Sugestão: considere a divisibilidade por 3.)

Exercício 3.56. Demonstre por casos: para todo n ∈ Z, o número n3 − n é divisível

por 6. (Sugestão: considere os casos de n módulo 2 e módulo 3, ou utilize a fatoração
n3 − n = (n − 1)n(n + 1) e analise a paridade e divisibilidade por 3 do produto de três
inteiros consecutivos.)

Exercício 3.57. Demonstre que existe um número real irracional elevado a um expoente
irracional que resulta em um número irracional, sem usar demonstração por casos como no
Teorema 3.4 – ou seja, encontre um exemplo explícito e construtivo. (Sugestão: considere
√ √ √ 2√2 √ √2 2
a = 2 e b = 2 2, sabendo que 2 = ( 2 ) ; ou pesquise outra combinação.)

Exercício 3.58. Demonstre que existe um único número real x tal que x3 = 8, especifi-
cando cuidadosamente as etapas de existência e unicidade.

Exercício 3.59. Sejam A, B, C conjuntos. Demonstre, mostrando a dupla inclusão:

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Exercício 3.60. Seja f : R → R dada por f (x) = x3 . Demonstre que f é injetiva e

sobrejetiva (isto é, bijetiva).

Exercício 3.61. avançado Demonstre que, para todo √ n ∈ N com n ≥ 2, se n não é

primo, então n possui um divisor primo p com p ≤ n. (Sugestão: use o fato de que
todo n ≥ 2 possui um√divisor primo, e considere o menor divisor d > 1 de n; mostre por
contradição que d ≤ n.)

Exercício 3.62. avançado Utilizando a desigualdade das médias (Teorema 3.5), demon-
1
stre que, para todo x > 0, x + ≥ 2, com igualdade se, e somente se, x = 1.
x
48 Chapter 3. Demonstrações Matemáticas
Capítulo 4

Indução Matemática e Estratégias de Res-

olução

4.1 Motivação da indução

Considere a seguinte afirmação: "para todo n ∈ N com n ≥ 1,

n(n + 1)
1 + 2 + 3 + ··· + n = .
2

" Trata-se de uma afirmação universal sobre um universo infinito (N). Nenhuma das
técnicas do Capítulo 3 – demonstração direta, contraposição, contradição, ou casos –
parece, à primeira vista, aplicável de maneira direta: não há uma manipulação algébrica
óbvia que produza a fórmula fechada n(n+1)
2
a partir apenas da definição da soma, e uma
demonstração "caso a caso" exigiria verificar infinitos casos, um para cada n, o que é
impossível em tempo finito.

A saída para esse impasse é uma técnica de demonstração fundamentalmente distinta,

especificamente adequada para afirmações indexadas pelos números naturais: o Princípio
da Indução Matemática. A ideia intuitiva é a de um efeito dominó: se a primeira peça
cai, e sabemos que sempre que uma peça cai, a peça seguinte também cai, então
concluímos que todas as peças, em sequência infinita, cairão – sem que seja necessário
verificar, peça por peça, individualmente.

4.2 O princípio da indução

Teorema 4.1 Princípio da Indução Matemática – PIM
Seja P (n) um predicado definido para n ∈ N (ou, mais geralmente, para n ≥ n0 , onde
n0 ∈ Z é um inteiro inicial fixado). Suponha que:
(i) (Base da indução) P (n0 ) é verdadeira;
(ii) (Passo indutivo) para todo k ≥ n0 , se P (k) é verdadeira (hipótese de in-
dução), então P (k + 1) é verdadeira.
Então P (n) é verdadeira para todo n ≥ n0 .

49
50 Chapter 4. Indução Matemática e Estratégias de Resolução

Observação 4.2 Por que o princípio da indução funciona – justificativa in-

tuitiva
O Princípio da Indução Matemática é, tipicamente, adotado como um axioma da
teoria dos números naturais (um dos Axiomas de Peano), e não é demonstrado a partir
de princípios mais elementares neste curso introdutório; no entanto, sua plausibilidade
pode ser compreendida da seguinte maneira: a base estabelece P (n0 ); o passo indutivo,
aplicado com k = n0 , dá P (n0 + 1); aplicado novamente com k = n0 + 1, dá P (n0 + 2);
e assim sucessivamente. Como todo natural n ≥ n0 é alcançado após um número finito
de aplicações sucessivas do passo indutivo a partir de n0 , concluímos P (n) para todo
tal n. O PIM formaliza e legitima esse processo "infinito" de aplicações sucessivas em
uma única e rigorosa etapa de raciocínio finito (a demonstração dos itens (i) e (ii),
cada um dos quais é uma afirmação única, não uma coleção infinita de afirmações).

Observação 4.3 Estrutura de uma demonstração por indução

Para demonstrar ∀n ≥ n0 , P (n) por indução, a demonstração deve conter, obrigato-
riamente, três partes claramente identificadas:
1. Base da indução: verificar diretamente que P (n0 ) é verdadeira (geralmente
uma verificação simples, por substituição direta);
2. Hipótese de indução: enunciar explicitamente a suposição "P (k) é verdadeira,
para um certo k ≥ n0 arbitrário, porém fixo";
3. Passo indutivo: demonstrar, usando a hipótese de indução (e tipicamente
também manipulação algébrica ou lógica adicional), que P (k + 1) é verdadeira.
Ao final, conclui-se, invocando o Princípio da Indução Matemática, que P (n) vale
para todo n ≥ n0 .

Teorema 4.4
Para todo n ∈ N com n ≥ 1,

n(n + 1)
1 + 2 + ··· + n = .
2

n(n + 1)
Proof. Seja P (n) o predicado "1+2+· · ·+n = ". Demonstraremos ∀n ≥ 1, P (n)
2
por indução.

Base (n = 1): O lado esquerdo é 1 (soma de um único termo). O lado direito é

1 · (1 + 1) 2
= = 1. Como ambos os lados são iguais a 1, P (1) é verdadeira.
2 2
Hipótese de indução: Suponhamos que, para um certo k ≥ 1 (arbitrário, porém fixo),

k(k + 1)
1 + 2 + ··· + k =
2

seja verdadeira.

Passo indutivo: Devemos demonstrar P (k + 1), isto é,

(k + 1)(k + 2)
1 + 2 + · · · + k + (k + 1) = .
2
4.2. O princípio da indução 51

Partindo do lado esquerdo e usando a hipótese de indução para substituir a soma parcial
1 + 2 + · · · + k:
k(k + 1)
1 + 2 + · · · + k + (k + 1) = +(k + 1).
2 }
| {z
hipótese de indução

Colocando (k + 1) em evidência (somando as frações sobre denominador comum 2):

k(k + 1) k(k + 1) + 2(k + 1) (k + 1)(k + 2)
+ (k + 1) = = ,
2 2 2
que é exatamente o lado direito de P (k + 1). Logo, P (k + 1) é verdadeira.
Pelo Princípio da Indução Matemática, P (n) é verdadeira para todo n ≥ 1. ■

Observação 4.5
Note, mais uma vez, como cada passagem algébrica foi justificada explicitamente
(colocação em evidência, soma de frações), sem apelar a "é fácil ver que". Essa é a
marca de uma demonstração por indução bem escrita: a base é verificada com todo
cuidado, a hipótese de indução é enunciada com precisão, e o passo indutivo deixa
claro exatamente onde e como a hipótese de indução é utilizada – no exemplo
acima, destacamos explicitamente esse ponto com um sublinhado (underbrace).

Teorema 4.6
Para todo n ∈ N, n ≥ 0: 2n > n.

Proof. Seja P (n): "2n > n". Demonstramos por indução, com base em n0 = 0.
Base (n = 0): 20 = 1 > 0. Logo, P (0) é verdadeira.
Hipótese de indução: suponha 2k > k para um certo k ≥ 0 fixo.
Passo indutivo: devemos mostrar 2k+1 > k + 1. Partindo de 2k+1 :
2k+1 = 2 · 2k .
Pela hipótese de indução, 2k > k, logo (multiplicando ambos os lados por 2 > 0, o que
preserva a desigualdade):
2 · 2k > 2k.
Assim, 2k+1 > 2k. Resta mostrar que 2k ≥ k + 1, o que, somado à desigualdade anterior,
daria 2k+1 > k + 1 (por transitividade da relação >, aplicada a 2k+1 > 2k e 2k ≥ k + 1).
De fato, 2k ≥ k + 1 ⇐⇒ k ≥ 1.
Aqui é necessário um cuidado: a desigualdade k ≥ 1 não decorre da hipótese de indução
k ≥ 0 diretamente para k = 0. Tratamos esse caso à parte: se k = 0, então k + 1 = 1, e
queremos 2k+1 = 21 = 2 > 1 = k + 1, o que é verdade diretamente (verificação direta, sem
uso da hipótese de indução). Se k ≥ 1, a cadeia de desigualdades acima (2k+1 > 2k ≥ k+1)
se aplica integralmente, dando 2k+1 > k + 1.
Em ambos os subcasos (k = 0 e k ≥ 1), concluímos 2k+1 > k + 1, isto é, P (k + 1).
Pelo Princípio da Indução Matemática, 2n > n para todo n ≥ 0. ■
52 Chapter 4. Indução Matemática e Estratégias de Resolução

Observação 4.7
Este exemplo ilustra uma sutileza comum em demonstrações por indução: por vezes, o
passo indutivo requer, ele próprio, uma pequena demonstração por casos, como fizemos
acima. Isso não compromete o rigor da indução; apenas mostra que as técnicas do
Capítulo 3 e a indução matemática combinam-se livremente dentro de uma mesma
demonstração – reforçando, mais uma vez, que as técnicas de demonstração não são
compartimentos estanques, mas ferramentas que se articulam conforme a necessidade.

Proposição 4.8
Para todo n ∈ N com n ≥ 1, o número 7n − 1 é divisível por 6.

Proof. Seja P (n): "6 | (7n − 1)".

Base (n = 1): 71 − 1 = 6 = 6 · 1, logo 6 | 6, e P (1) é verdadeira.
Hipótese de indução: suponha que, para um certo k ≥ 1 fixo, 6 | (7k − 1), isto é, existe
m ∈ Z tal que 7k − 1 = 6m.
Passo indutivo: devemos mostrar 6 | (7k+1 − 1). Escrevemos:

7k+1 − 1 = 7 · 7k − 1 = 7 · 7k − 7 + 6 = 7(7k − 1) + 6.

Pela hipótese de indução, 7k − 1 = 6m; substituindo:

7k+1 − 1 = 7(6m) + 6 = 6(7m + 1).

Como m ∈ Z, temos 7m + 1 ∈ Z; denotando m′ = 7m + 1, obtemos 7k+1 − 1 = 6m′ , com

m′ ∈ Z, ou seja, 6 | (7k+1 − 1), isto é, P (k + 1).
Pelo Princípio da Indução Matemática, 6 | (7n − 1) para todo n ≥ 1. ■

4.3 Indução forte

Em certas situações, o passo indutivo de P (k) ⇒ P (k +1) (indução simples) é insuficiente,
pois demonstrar P (k + 1) pode exigir a hipótese de que P (j) vale para diversos (ou
todos os) valores anteriores j ≤ k, não apenas para o valor imediatamente anterior. Para
esses casos, dispomos de uma variante logicamente equivalente, porém tecnicamente mais
flexível: a indução forte.
Teorema 4.9 Princípio da Indução Forte
Seja P (n) um predicado definido para n ≥ n0 . Suponha que:
(i) (Base) P (n0 ) é verdadeira;
(ii) (Passo indutivo forte) para todo k > n0 , se P (j) é verdadeira para todo j
com n0 ≤ j < k (hipótese de indução forte), então P (k) é verdadeira.
Então P (n) é verdadeira para todo n ≥ n0 .

Observação 4.10 Equivalência entre indução simples e indução forte

Pode-se demonstrar (e é um resultado padrão em Fundamentos da Matemática) que
o Princípio da Indução Forte é logicamente equivalente ao Princípio da Indução
4.3. Indução forte 53

Matemática (simples) apresentado na Seção 4.2 – cada um pode ser deduzido do outro.
A escolha entre um e outro é, portanto, puramente uma questão de conveniência
na exposição da demonstração: usa-se indução forte quando o passo indutivo
naturalmente requer acesso a mais de um caso anterior.

Teorema 4.11 Existência de fatoração em primos

Todo número natural n ≥ 2 pode ser escrito como produto de um ou mais números
primos.

Proof. Seja P (n): "n pode ser escrito como produto de um ou mais primos". Demon-
stramos ∀n ≥ 2, P (n) por indução forte.

Base (n = 2): 2 é primo, e um número primo é, trivialmente, "produto de um único

primo" (o próprio). Logo, P (2) é verdadeira.

Hipótese de indução forte: suponha que, para um certo k > 2, P (j) seja verdadeira
para todo j com 2 ≤ j < k, isto é, todo natural entre 2 e k − 1 (inclusive) pode ser escrito
como produto de primos.

Passo indutivo: devemos mostrar P (k). Há dois casos (demonstração por casos dentro
do passo indutivo, novamente ilustrando a combinação de técnicas):

Caso 1: k é primo. Então k é, trivialmente, produto de um único primo (ele mesmo),

e P (k) vale.

Caso 2: k não é primo. Por definição de número composto, existem a, b ∈ N com

2 ≤ a, b < k tais que k = ab (se não existisse tal fatoração não trivial, k seria primo por
definição, contradizendo a hipótese deste caso). Como 2 ≤ a < k e 2 ≤ b < k, a hipótese
de indução forte se aplica a ambos: P (a) e P (b) são verdadeiras, isto é, a e b podem ser
escritos como produtos de primos:

a = p1 p2 · · · pr , b = q1 q2 · · · qs ,

com pi , qj primos. Logo,

k = ab = p1 p2 · · · pr · q1 q2 · · · qs ,

que é um produto de primos (a concatenação das duas listas). Logo, P (k) vale.

Em ambos os casos, P (k) é verdadeira. Pelo Princípio da Indução Forte, P (n) vale para
todo n ≥ 2. ■

Observação 4.12
Note por que a indução simples seria inadequada aqui: no Caso 2, precisamos da
hipótese de indução aplicada tanto a a quanto a b, dois números que, em geral, não
são iguais a k − 1 (o único caso coberto pela hipótese de indução simples) – podem
ser quaisquer valores entre 2 e k − 1. É exatamente esse tipo de situação – em que
o passo indutivo depende de múltiplos casos anteriores, não necessariamente do caso
imediatamente anterior – que torna a indução forte a ferramenta correta.
54 Chapter 4. Indução Matemática e Estratégias de Resolução

4.4 Indução estrutural: uma breve introdução

A indução matemática, como apresentada acima, aplica-se a afirmações indexadas pelos
naturais. Uma generalização importante, especialmente relevante em Matemática Disc-
reta e Ciência da Computação, é a indução estrutural, aplicável a objetos definidos
recursivamente (isto é, por meio de casos base e regras de construção a partir de obje-
tos menores), como fórmulas lógicas, árvores, listas, ou expressões aritméticas.

Observação 4.13 Princípio da indução estrutural, informalmente

Se um conjunto de objetos S é definido recursivamente por (a) uma coleção de casos
base e (b) uma coleção de regras de construção que produzem novos elementos de
S a partir de elementos já existentes em S, então, para demonstrar que todo elemento
de S satisfaz uma propriedade P , basta demonstrar: (i) todo caso base satisfaz P ; (ii)
para cada regra de construção, se os objetos usados como entrada satisfazem P , então
o objeto produzido pela regra também satisfaz P .

Exemplo 4.14
Considere o conjunto F das fórmulas proposicionais (Capítulo 1), definido recursiva-
mente por:
• Caso base: toda variável proposicional p, q, r, . . . é uma fórmula em F ;
• Regras de construção: se φ, ψ ∈ F , então ¬φ, (φ ∧ ψ), (φ ∨ ψ), (φ → ψ) e
(φ ↔ ψ) também pertencem a F .
Vamos demonstrar, por indução estrutural, que toda fórmula em F possui um número
igual de parênteses de abertura e de fechamento.
Casos base: uma variável proposicional isolada não contém nenhum parêntese; logo,
o número de parênteses de abertura (0) é igual ao de fechamento (0).
Passo indutivo (regra ¬): suponha que φ tenha a parênteses de abertura e a
de fechamento (hipótese de indução estrutural: mesmo número). Então ¬φ tem ex-
atamente os mesmos parênteses de φ (a negação não introduz novos parênteses, por
convenção de notação), logo continua com a de cada tipo – números iguais.
Passo indutivo (regra ∧, e analogamente ∨, →, ↔): suponha que φ tenha
a parênteses de abertura e a de fechamento, e que ψ tenha b de abertura e b de
fechamento (hipótese de indução estrutural, aplicada a ambas as subfórmulas). Então
(φ ∧ ψ) tem a + b + 1 parênteses de abertura (os de φ, os de ψ, mais o parêntese
externo de abertura) e a + b + 1 de fechamento (analogamente) – novamente números
iguais.
Por indução estrutural, toda fórmula em F possui número igual de parênteses de
abertura e de fechamento.

4.5 Como matemáticos constroem demonstrações

Até aqui, apresentamos as técnicas de demonstração já em sua forma final, polida e
organizada. Esta seção trata de algo diferente e igualmente importante: o processo –
muitas vezes confuso, exploratório e não linear – pelo qual um matemático descobre
uma demonstração antes de escrevê-la de forma polida.
4.5. Como matemáticos constroem demonstrações 55

4.5.1 Como iniciar uma prova

Diante de um teorema a ser demonstrado, da forma H → T (hipótese implica tese), o
primeiro passo é sempre o mesmo, independentemente da técnica que se pretenda usar ao
final:

1. Escrever explicitamente a hipótese H, traduzindo-a, se necessário, para sua

forma matemática precisa (usando definições formais, como fizemos ao traduzir
"par" para "n = 2k" ao longo do Capítulo 3);

2. Escrever explicitamente a tese T , da mesma forma;

3. Identificar o que precisa ser mostrado para se chegar de H a T – isto é, qual

é a "distância lógica" entre hipótese e tese, e que definições, teoremas anteriores ou
manipulações algébricas podem preencher essa distância.

Observação 4.15
Um erro extremamente comum entre estudantes iniciantes é começar a escrever ma-
nipulações algébricas antes de ter escrito claramente hipótese e tese em sua forma
matemática precisa. Isso frequentemente leva a demonstrações confusas, circulares,
ou que silenciosamente assumem aquilo que deveriam provar (um erro lógico que dis-
cutiremos na Seção 4.6).

4.5.2 Como interpretar hipóteses

Toda hipótese matemática – "n é par", "f é contínua", "A ⊆ B" – deve ser desem-
pacotada em sua definição formal antes de ser manipulada. O estudante experiente
desenvolve o hábito de perguntar, diante de cada hipótese: "o que exatamente esta
afirmação me garante, em termos de objetos concretos (números, conjuntos, funções) que
posso manipular algebricamente ou logicamente?"

Exemplo 4.16
Diante da hipótese "f : R → R é uma função crescente", o estudante deve lembrar
(ou consultar) a definição formal:

∀x1 , x2 ∈ R, x1 < x2 → f (x1 ) < f (x2 ),

e reconhecer que essa hipótese, em uma demonstração, tipicamente será usada instan-
ciando x1 , x2 por valores específicos relevantes ao problema em questão (uma aplicação
do quantificador universal a casos particulares, procedimento inverso à generalização
universal mencionada na Observação 3.1).

4.5.3 Como descobrir o caminho da demonstração

Não existe um algoritmo garantido para descobrir demonstrações (de fato, resultados de
lógica matemática, como o Teorema da Incompletude de Gödel e problemas de indecidibil-
idade, mostram limites fundamentais a qualquer processo mecânico geral de demonstração
automática). No entanto, algumas estratégias heurísticas são amplamente úteis:
56 Chapter 4. Indução Matemática e Estratégias de Resolução

• Trabalhar com exemplos pequenos e concretos antes de tentar o caso geral,

buscando um padrão que sugira o argumento geral;
• Desenhar diagramas (especialmente úteis em geometria e teoria dos conjuntos);
• Perguntar qual técnica de demonstração parece mais promissora (Seção
4.5, abaixo), com base na forma lógica do enunciado;
• Verificar se o resultado desejado é consequência de um teorema já con-
hecido, aplicado de forma direta ou com pequena adaptação;
• Considerar a negação da tese e ver que informação isso fornece (mesmo que a
demonstração final não seja por contradição, esse exercício mental frequentemente
ilumina a estrutura do problema).

4.5.4 Trabalhar de trás para frente

Uma técnica heurística poderosa, especialmente para problemas algébricos e de desigual-
dades, é iniciar a investigação (não necessariamente a versão final e escrita da demon-
stração) a partir da tese, e perguntar: "que afirmação, se verdadeira, implicaria ime-
diatamente esta tese?" Repetindo esse processo, retrocede-se passo a passo até alcançar
algo que decorra diretamente da hipótese ou de fatos já conhecidos.

Exemplo 4.17
a2 + b 2
Deseja-se mostrar que, para a, b > 0 com a ̸= b, vale > ab.
2
a2 + b 2
Trabalhando de trás para frente: a tese é > ab, equivalente (multipli-
2
cando por 2) a a + b > 2ab, equivalente (subtraindo 2ab) a a2 − 2ab + b2 > 0, que
2 2

reconhecemos como (a − b)2 > 0. Esta última afirmação é verdadeira, pois a ̸= b

implica a − b ̸= 0, e o quadrado de um número real não nulo é sempre estritamente
positivo.
Tendo descoberto o caminho "de trás para frente", escrevemos agora a demonstração
formal, para frente, como é costume em textos matemáticos:

Proposição 4.18
a2 + b 2
Para todos a, b ∈ R com a, b > 0 e a ̸= b: > ab.
2

Proof. Como a ̸= b, temos a − b ̸= 0, e portanto (o quadrado de um número real não

nulo é estritamente positivo):
(a − b)2 > 0.
Expandindo o quadrado:

a2 − 2ab + b2 > 0 =⇒ a2 + b2 > 2ab.

Dividindo ambos os lados por 2 (positivo, preserva a desigualdade):

a2 + b 2
> ab.
2
4.5. Como matemáticos constroem demonstrações 57

Observação 4.19
Note que a demonstração final, escrita "para frente", não menciona em nenhum mo-
mento o processo de descoberta "de trás para frente" que a originou – ela simplesmente
parte de um fato verdadeiro (o quadrado de um número não nulo é positivo) e cam-
inha diretamente até a tese. Essa é uma característica típica da matemática escrita: o
processo de descoberta (muitas vezes tortuoso, cheio de tentativas e erros) é geral-
mente distinto da apresentação final (linear, organizada, elegante). Reconhecer
essa distinção é essencial para não se frustrar diante da aparente "genialidade instan-
tânea" das demonstrações em livros-texto: por trás de cada demonstração elegante,
geralmente houve um processo de exploração menos elegante.

4.5.5 Criação de lemas

Problemas complexos frequentemente se tornam mais tratáveis quando divididos em
partes menores. Um lema é, precisamente, um resultado auxiliar, demonstrado sepa-
radamente, que serve como um "tijolo" na construção de uma demonstração maior (o
Teorema principal). A estratégia de identificar e isolar lemas é uma das ferramentas mais
importantes na construção de demonstrações sofisticadas.
Exemplo 4.20
√
Voltando à demonstração de que 2 é irracional (Teorema 3.2), note como ela se
apoiou fundamentalmente na Proposição 3.4 ("se n2 é par, então n é par"), demon-
strada separadamente, como um lema auxiliar. Sem isolar esse fato como um resul-
tado autônomo, a demonstração do Teorema 3.2 seria muito mais confusa e difícil de
acompanhar, pois misturaria dois argumentos√ distintos (um sobre paridade em geral,
outro sobre a irracionalidade específica de 2) em um único bloco de texto.

4.5.6 Escolha da técnica adequada

Observação 4.21 Guia heurístico para escolha de técnica
Embora não haja regras absolutas, os seguintes indícios são úteis para orientar a
escolha inicial de técnica de demonstração:
• Se a tese é uma afirmação universal com hipótese concreta e manipulável:
tente demonstração direta primeiro;
• Se a tese envolve uma negação, ou a contrapositiva parece mais concreta que o
enunciado original: considere contraposição;
• Se a tese afirma impossibilidade, não existência, ou unicidade, ou se supor
a negação parece fornecer informação útil e concreta: considere contradição;
• Se a hipótese (ou o universo de discurso) se subdivide naturalmente em casos
distintos: considere demonstração por casos;
• Se a tese é indexada por n ∈ N (ou é sobre objetos definidos recursivamente):
considere indução (simples, forte, ou estrutural);
• Se a tese é uma afirmação de existência: pergunte-se se é possível exibir o
objeto explicitamente (construtiva) ou se apenas um argumento indireto está
58 Chapter 4. Indução Matemática e Estratégias de Resolução

disponível (não construtiva).

4.6 Erros comuns e falácias lógicas

O estudo de erros lógicos frequentes é tão instrutivo quanto o estudo das técnicas corretas,
pois permite ao estudante reconhecer e evitar armadilhas de raciocínio que, superficial-
mente, parecem válidas.

Observação 4.22 Afirmação do consequente

Um erro lógico comum é concluir p a partir de p → q e q. Isso não é uma regra de
inferência válida (diferentemente do Modus Ponens): a proposição (p → q) ∧ q → p
não é uma tautologia, como o leitor pode verificar diretamente por tabela-verdade
(falha quando p = F, q = V ). Esse erro é chamado afirmação do consequente, e já
ilustramos sua natureza falaciosa no exemplo da introdução do Capítulo 1 ("se chove,
a rua molha; a rua está molhada; logo, choveu").

Observação 4.23 Negação do antecedente

Outro erro comum é concluir ¬q a partir de p → q e ¬p. A proposição (p →


q) ∧ ¬p → ¬q não é uma tautologia (falha quando p = F, q = V ). Esse erro é



chamado negação do antecedente: saber que "se chove, a rua molha" e que "não
está chovendo" não permite concluir que "a rua não está molhada" (poderia estar
molhada por outro motivo).

Observação 4.24 Petição de princípio – circular reasoning

Ocorre quando a demonstração de uma afirmação Q utiliza, em algum ponto – direta
ou indiretamente, muitas vezes disfarçada por reformulações – a própria afirmação Q
(ou uma afirmação logicamente equivalente a Q) como se já fosse conhecida. Esse erro é
particularmente traiçoeiro porque, superficialmente, a demonstração parece progredir
de forma válida.

Exemplo 4.25 Petição de princípio

Considere a seguinte "demonstração" (incorreta) de que "todo número ímpar ao
quadrado é ímpar":

"Seja n ímpar. Então n2 também é ímpar, pois o quadrado de um número

ímpar é sempre ímpar. Logo, n2 é ímpar."

Esta "demonstração" é circular: a frase "o quadrado de um número ímpar é sempre

ímpar" é exatamente a afirmação que se deseja demonstrar, apenas reformulada,
e não uma justificativa independente. Uma demonstração correta precisaria, como
fizemos na Proposição correspondente (análoga à Proposição 3.1, mas para o caso
ímpar), escrever n = 2k + 1 explicitamente e expandir algebricamente n2 , mostrando
que o resultado tem a forma 2m + 1.
4.7. Exercícios 59

Observação 4.26 Generalização precipitada

Ocorre quando se conclui uma afirmação universal ∀x, P (x) com base na verificação
de P (x) para apenas alguns casos particulares, sem uma demonstração que cubra
todos os casos do universo de discurso.

Exemplo 4.27 Generalização precipitada

Considere o polinômio p(n) = n2 − n + 41. Calculando:

p(1) = 41, p(2) = 43, p(3) = 47, p(4) = 53, . . .

Todos esses valores são primos, e de fato p(n) é primo para todo n de 1 a 40. Seria
tentador concluir, precipitadamente, que "p(n) é primo para todo n ∈ N". Porém,
isso é falso: para n = 41,

p(41) = 412 − 41 + 41 = 412 = 1681 = 41 × 41,

que não é primo (é o quadrado de 41). Este exemplo (atribuído a Euler) é um alerta
célebre contra a generalização precipitada: a verificação de um grande número de casos
particulares, por mais impressionante que seja, não constitui uma demonstração
da afirmação universal correspondente.

Observação 4.28 Ambiguidade na negação de quantificadores

Um erro comum, já mencionado na Seção 2.4, é negar incorretamente uma afirmação
universal ∀x, P (x) como ∀x, ¬P (x) (em vez da forma correta, ∃x, ¬P (x)). Esse erro,
embora sutil, é logicamente grave e compromete inteiramente demonstrações por con-
traposição ou contradição, pois a hipótese sob a qual se trabalha (a negação, incorre-
tamente formulada) não é, de fato, a negação lógica correta da tese.

Observação 4.29 Caso não exaustivo em demonstrações por casos

Ao empregar a demonstração por casos (Seção 3.5), é essencial verificar que os casos
considerados são, de fato, exaustivos – isto é, que cobrem todas as possibilidades
permitidas pela hipótese. Esquecer um caso invalida completamente a demonstração,
mesmo que os casos considerados estejam corretos.

4.7 Exercícios
Exercício 4.30. Demonstre, por indução matemática, que para todo n ≥ 1:
n(n + 1)(2n + 1)
12 + 22 + · · · + n2 = .
6

Exercício 4.31. Demonstre, por indução, que para todo n ≥ 1, a soma dos n primeiros
números ímpares positivos é n2 , isto é: 1 + 3 + 5 + · · · + (2n − 1) = n2 .

Exercício 4.32. Demonstre, por indução, que para todo n ≥ 0, 3 | (4n − 1).

Exercício 4.33. Demonstre, por indução, a desigualdade de Bernoulli: para todo n ≥ 0

e todo x ∈ R com x > −1, (1 + x)n ≥ 1 + nx.
60 Chapter 4. Indução Matemática e Estratégias de Resolução

Exercício 4.34. avançado A sequência de Fibonacci é definida por F1 = F2 = 1 e

Fn = Fn−1 + Fn−2 para n ≥ 3. Demonstre, por indução forte, que para todo n ≥ 1,
Fn < 2n .

Exercício 4.35. avançado Utilizando indução forte, demonstre que todo número natural
n ≥ 1 pode ser escrito de maneira única como soma de potências distintas de 2 (isto é,
a existência e unicidade da representação binária). Divida sua demonstração claramente
em uma parte de existência e uma parte de unicidade.

Exercício 4.36. Identifique o erro lógico em cada um dos seguintes argumentos, nome-
ando a falácia correspondente:
(a) "Se um quadrilátero é um quadrado, então tem quatro lados iguais. Este quadrilátero
tem quatro lados iguais. Logo, é um quadrado."
(b) "Se n é múltiplo de 6, então n é múltiplo de 2. 15 não é múltiplo de 6. Logo, 15
não é múltiplo de 2."
√
Exercício 4.37. Um estudante afirma ter demonstrado que " n2 + n nunca é um
número inteiro para n ≥ 1" verificando os casos n = 1, 2, 3, 4, 5. Explique, usando os
conceitos desta seção, por que essa não é uma demonstração válida, e (caso consiga)
forneça uma demonstração correta ou um contraexemplo.

Exercício 4.38. avançado Reflita e escreva, em suas próprias palavras (não mais que
um parágrafo), sobre a diferença entre o processo de descoberta de uma demonstração e
sua apresentação final, ilustrando com um exemplo de sua escolha (pode reutilizar um
exemplo já visto em outro capítulo, desde que explique com suas próprias palavras o
processo heurístico de "trabalhar de trás para frente" ou outra estratégia discutida nesta
seção).
Capítulo 5

Aplicações da Lógica nas Demonstrações

Matemáticas

Este capítulo tem um objetivo específico: mostrar que a lógica e as técnicas de demon-
stração estudadas nos Capítulos 1 a 4 não são um exercício isolado e abstrato, mas a
ferramenta viva por trás de resultados centrais em diversas áreas da matemática. Em
cada seção, apresentaremos um resultado genuíno de uma área específica, junto com sua
demonstração completa e um comentário explícito sobre qual técnica lógica foi empregada
e por quê.

5.1 Álgebra
Proposição 5.1
Sejam a, b elementos de um corpo (por exemplo, R ou Q). Se ab = 0, então a = 0 ou
b = 0.

Proof. Demonstraremos por casos, dividindo conforme a = 0 ou a ̸= 0.

Caso 1: a = 0. Neste caso, a disjunção "a = 0 ou b = 0" é imediatamente verdadeira
(pois sua primeira parte já é verdadeira), e nada mais há a demonstrar.
Caso 2: a ̸= 0. Como estamos em um corpo, todo elemento não nulo possui um inverso
multiplicativo; seja a−1 o inverso de a. Multiplicando ambos os lados da igualdade ab = 0
por a−1 (à esquerda):
a−1 (ab) = a−1 · 0.
Pela associatividade da multiplicação no corpo, o lado esquerdo é (a−1 a)b = 1 · b = b; o
lado direito, pela propriedade de que todo elemento multiplicado por 0 resulta em 0, é 0.
Logo, b = 0, e a disjunção "a = 0 ou b = 0" é verdadeira (pela segunda parte).
Em ambos os casos (exaustivos, pois todo elemento é 0 ou não é), concluímos a = 0 ou
b = 0. ■

Observação 5.2
Esta propriedade – conhecida como "ausência de divisores de zero" em um corpo – é
utilizada constantemente ao "cancelar fatores" em equações algébricas (por exemplo,
ao resolver (x − 1)(x − 3) = 0 concluindo x = 1 ou x = 3). Observe a estrutura lógica:
a demonstração por casos aqui reflete exatamente a estrutura da disjunção presente

61
62 Chapter 5. Aplicações da Lógica nas Demonstrações Matemáticas

na tese.

Proposição 5.3
O elemento neutro da adição em um grupo é único.

Proof. Esta é uma demonstração de unicidade (Seção 3.6). Suponhamos que e1 e e2

sejam ambos elementos neutros do grupo (G, +), isto é, satisfazem, para todo x ∈ G:
x + e1 = e1 + x = x e x + e2 = e2 + x = x. Devemos mostrar e1 = e2 .
Considere a soma e1 + e2 . Por um lado, como e2 é neutro, aplicando a propriedade de e2
com x = e1 :
e1 + e2 = e1 .
Por outro lado, como e1 é neutro, aplicando a propriedade de e1 com x = e2 :

e1 + e2 = e2 .

Das duas igualdades (ambas para a mesma expressão e1 + e2 ), concluímos, por transitivi-
dade da igualdade:
e1 = e1 + e2 = e2 =⇒ e1 = e2 .
■

Observação 5.4
Note a estrutura típica de demonstrações de unicidade em Álgebra: supõe-se a ex-
istência de dois objetos com a propriedade desejada e demonstra-se, por manipulação
direta usando as próprias definições (aqui, a definição de elemento neutro), que eles
devem coincidir.

5.2 Análise
Definição 5.5 Limite de sequência
Uma sequência (an )n∈N de números reais converge para L ∈ R, denotado
limn→∞ an = L, quando

∀ε > 0, ∃N ∈ N, ∀n ≥ N, |an − L| < ε.

Proposição 5.6 Unicidade do limite

Se (an ) converge para L1 e para L2 , então L1 = L2 .

Proof. Demonstraremos por contradição. Suponhamos, por absurdo, que L1 ̸= L2 . Então

|L1 − L2 |
|L1 − L2 | > 0; seja ε = > 0.
2
Como an → L1 , aplicando a Definição 5.1 com este ε, existe N1 ∈ N tal que, para todo
n ≥ N1 , |an − L1 | < ε.
Como an → L2 , analogamente, existe N2 ∈ N tal que, para todo n ≥ N2 , |an − L2 | < ε.
5.3. Teoria dos Conjuntos 63

Tome n = max{N1 , N2 } (que satisfaz simultaneamente n ≥ N1 e n ≥ N2 , pela definição

de máximo). Para este n, valem ambas as desigualdades |an − L1 | < ε e |an − L2 | < ε.
Pela desigualdade triangular:

|L1 − L2 | = |L1 − an + an − L2 | ≤ |an − L1 | + |an − L2 | < ε + ε = 2ε = |L1 − L2 |.

Obtivemos |L1 − L2 | < |L1 − L2 |, isto é, a proposição |L1 − L2 | < |L1 − L2 |, que é uma
contradição (nenhum número real é estritamente menor que si mesmo).
Logo, a suposição L1 ̸= L2 é falsa. Portanto, L1 = L2 . ■

Observação 5.7
Esta demonstração ilustra perfeitamente o estilo característico das demonstrações em
Análise: manipulação cuidadosa de quantificadores (∀ε ∃N ∀n), escolha estratégica de
um valor específico de ε (aqui, ε = |L1 − L2 |/2, escolhido exatamente para que a
contradição final apareça de forma limpa), e o uso da desigualdade triangular como
ferramenta algébrica central. A técnica de demonstração empregada – contradição – foi
escolhida porque a hipótese "L1 ̸= L2 " fornece uma quantidade concreta (|L1 − L2 | >
0) que pode ser explorada para construir o ε apropriado, algo que não seria tão natural
em uma tentativa de demonstração direta.

Proposição 5.8
Toda sequência convergente é limitada.

Proof. Suponha que an → L. Aplicando a Definição 5.1 com ε = 1 (uma escolha

específica, permitida pois a definição vale para todo ε > 0, em particular ε = 1), existe
N ∈ N tal que, para todo n ≥ N , |an − L| < 1. Pela desigualdade triangular, para n ≥ N :

|an | = |an − L + L| ≤ |an − L| + |L| < 1 + |L|.

Assim, todos os termos a partir de aN estão limitados por 1 + |L|. Os termos restantes,
a1 , . . . , aN −1 (uma quantidade finita), possuem, cada um, seu próprio valor absoluto, e o
conjunto finito {|a1 |, . . . , |aN −1 |} possui um máximo, digamos M0 (todo conjunto finito
não vazio de reais possui máximo). Tomando

M = max{M0 , 1 + |L|},

temos |an | ≤ M para todo n ∈ N (para n < N , por definição de M0 e M ; para n ≥ N ,

pela desigualdade acima). Logo, (an ) é limitada. ■

5.3 Teoria dos Conjuntos

Proposição 5.9
Para conjuntos A, B, C: se A ⊆ B e B ⊆ C, então A ⊆ C.

Proof. Demonstração direta. Seja x ∈ A arbitrário (estratégia padrão para demonstrar

inclusão, Observação 3.3). Como A ⊆ B (hipótese) e x ∈ A, pela Definição 3.4 de
64 Chapter 5. Aplicações da Lógica nas Demonstrações Matemáticas

subconjunto, x ∈ B. Como B ⊆ C (hipótese) e x ∈ B (acabamos de concluir), novamente

pela Definição 3.4, x ∈ C.
Como x ∈ A era arbitrário e concluímos x ∈ C, está demonstrado que ∀x, (x ∈ A → x ∈
C), isto é, A ⊆ C. ■

Observação 5.10
Compare esta demonstração com a do Silogismo Hipotético (Teorema 2.3): a estrutura
lógica é idêntica – de x ∈ A → x ∈ B e x ∈ B → x ∈ C, concluímos x ∈
A → x ∈ C, exatamente como de p → q e q → r concluímos p → r. Isso não
é coincidência: a inclusão de conjuntos é definida, precisamente, em termos de um
condicional universalmente quantificado, e portanto herda diretamente as propriedades
lógicas dos condicionais estudadas no Capítulo 2.

Teorema 5.11 Cantor

Não existe função sobrejetiva f : A → P(A), onde P(A) denota o conjunto das partes
de A (o conjunto de todos os subconjuntos de A).

Proof. Demonstraremos por contradição. Suponha, por absurdo, que exista uma função
sobrejetiva f : A → P(A).
Considere o conjunto
D = {x ∈ A : x ∈
/ f (x)}.
Note que D é, por construção, um subconjunto de A, isto é, D ∈ P(A).
Como f é sobrejetiva (hipótese de contradição) e D ∈ P(A), pela Definição 3.7 de sobre-
jetividade, existe a ∈ A tal que f (a) = D.
Agora, perguntamos: a ∈ D ou a ∈/ D? Pelo Princípio do Terceiro Excluído (Teorema 1.1,
item x), uma das duas alternativas ocorre; analisamos ambas (demonstração por casos,
aninhada dentro da demonstração por contradição).
Caso 1: a ∈ D. Pela definição de D (D = {x ∈ A : x ∈ / f (x)}), a ∈ D significa
precisamente a ∈ / f (a). Mas f (a) = D, logo a ∈
/ D. Isso contradiz diretamente a
suposição deste caso (a ∈ D).
Caso 2: a ∈ / D. Como D = {x ∈ A : x ∈ / f (x)}, dizer que a ∈ / D significa que a não
satisfaz a condição definidora de D, isto é, ¬(a ∈/ f (a)), ou seja, a ∈ f (a). Mas f (a) = D,
logo a ∈ D. Isso contradiz diretamente a suposição deste caso (a ∈ / D).
Em ambos os casos (que são exaustivos, pelo terceiro excluído), chegamos a uma con-
tradição. Logo, a suposição de que existe tal função sobrejetiva f é falsa.
Portanto, não existe função sobrejetiva f : A → P(A). ■

Observação 5.12
Este é o célebre Teorema de Cantor, um dos resultados mais profundos e influentes
da teoria dos conjuntos, com consequências centrais para a compreensão de diferentes
"tamanhos" de infinito (cardinalidades). Note a estrutura lógica extremamente cuida-
dosa: a construção do conjunto D (uma espécie de "conjunto diagonal", análogo, em
5.4. Geometria 65

espírito, ao paradoxo do mentiroso mencionado no Capítulo 1, mas aqui domesticado

rigorosamente dentro de uma demonstração por contradição válida) e a análise por ca-
sos de a ∈ D versus a ∈
/ D, cada um levando a uma contradição direta – exemplificam
de maneira exemplar como as técnicas lógicas dos capítulos anteriores se combinam
em um resultado matemático profundo.

5.4 Geometria
Teorema 5.13 Pitágoras
Em um triângulo retângulo com catetos a, b e hipotenusa c, vale a2 + b2 = c2 .

Proof. Apresentamos uma demonstração clássica por rearranjo de áreas. Considere um

quadrado de lado a + b. Dentro dele, posicione quatro cópias congruentes do triângulo
retângulo de catetos a, b e hipotenusa c, dispostas de modo que formem, no centro, um
quadrado menor de lado c (esta construção geométrica específica é padrão e pode ser
verificada diretamente por meio de um desenho cuidadoso).
A área do quadrado grande, de lado a + b, é (a + b)2 . Por outro lado, essa mesma área
pode ser calculada como a soma das áreas das quatro cópias do triângulo, mais a área do
quadrado central de lado c:
 
2 ab
(a + b) = 4 · + c2 = 2ab + c2 .
2
Expandindo o lado esquerdo:

a2 + 2ab + b2 = 2ab + c2 .

Subtraindo 2ab de ambos os lados:

a2 + b 2 = c 2 .

Observação 5.14
Esta demonstração é um exemplo de demonstração direta apoiada em um ar-
gumento geométrico-visual, combinado com manipulação algébrica (expansão do
quadrado do binômio e cancelamento de termos). Ilustra como, em Geometria, ar-
gumentos visuais rigorosos (quando devidamente formalizados, como a decomposição
de áreas aqui utilizada) constituem demonstrações legítimas, desde que cada etapa –
inclusive a afirmação sobre como as áreas se relacionam – seja justificada.

Proposição 5.15
A soma dos ângulos internos de um triângulo é 180◦ .

Proof. Considere um triângulo ABC, com ângulos internos α (em A), β (em B) e γ (em
C). Trace, pelo vértice C, uma reta r paralela ao lado AB (tal reta existe e é única, pelo
Postulado das Paralelas de Euclides).
66 Chapter 5. Aplicações da Lógica nas Demonstrações Matemáticas

Como r é paralela a AB, e o segmento AC é uma transversal a essas duas retas paralelas,
os ângulos alternos internos são congruentes (propriedade de retas paralelas cortadas por
uma transversal): o ângulo entre r e AC (do lado de A) é congruente a α.
Analogamente, como BC é transversal às paralelas r e AB, o ângulo entre r e BC (do
lado de B) é congruente a β.
Os três ângulos ao longo da reta r, no ponto C – o ângulo congruente a α, o ângulo γ
(interno ao triângulo, entre AC e BC), e o ângulo congruente a β – formam, juntos, um
ângulo raso (isto é, somam 180◦ ), pois estão dispostos ao longo de uma reta.
Logo, α + γ + β = 180◦ , isto é, a soma dos ângulos internos do triângulo é 180◦ . ■

Observação 5.16
Esta é uma demonstração direta clássica, apoiada crucialmente no Postulado das
Paralelas (um axioma da geometria euclidiana) e na propriedade dos ângulos alternos
internos. Observe como a demonstração constrói um objeto auxiliar (a reta r) – uma
técnica comum em Geometria, análoga, em espírito, à criação de lemas discutida na
Seção 4.5: introduzir um elemento auxiliar que não está no enunciado original, mas
que torna o argumento tratável.

5.5 Matemática Discreta

Definição 5.17 Coeficiente binomial
Para n, k ∈ N com 0 ≤ k ≤ n, o coeficiente binomial nk é definido como o número

de subconjuntos de tamanho k de um conjunto com n elementos, e é dado pela fórmula

 
n n!
= .
k k!(n − k)!

Proposição 5.18 Relação de Pascal

Para n ≥ 1 e 1 ≤ k ≤ n − 1:
     
n n−1 n−1
= + .
k k−1 k

Proof. Apresentamos uma demonstração combinatória (também chamada demon-

stração por dupla contagem): interpretamos ambos os lados da igualdade como respostas
à mesma pergunta de contagem, contada de duas maneiras distintas.
Considere um conjunto S com n elementos, e fixe um elemento particular x ∈ S. Queremos
contar o número
de subconjuntos de S com exatamente k elementos – essa contagem é,
por definição, nk (lado esquerdo da igualdade).
Por outro lado, todo subconjunto de S com k elementos ou contém x, ou não contém
x (dicotomia exaustiva e mutuamente exclusiva, demonstração por casos). Contamos
separadamente cada categoria:
Subconjuntos de tamanho k que contêm x: escolher tal subconjunto equivale a
5.6. Física Matemática 67

escolher
os k − 1 elementos restantes (além de x) dentre os n − 1 elementos de S \ {x}.

Há n−1
k−1
maneiras de fazer essa escolha.
Subconjuntos de tamanho k que não contêm x: escolher tal subconjunto equivale

a escolher todos os k elementos dentre os n − 1 elementos restantes de S \ {x}. Há n−1
k
maneiras.
Como as duas categorias são exaustivas e mutuamente exclusivas (um subconjunto contém
x ou não contém, nunca ambos), o total de subconjuntos de tamanho k é a soma das duas
contagens:      
n n−1 n−1
= + .
k k−1 k
Como ambos os lados contam exatamente o mesmo conjunto de objetos (os subconjuntos
de tamanho k de S), a igualdade está demonstrada. ■

Observação 5.19
A demonstração combinatória (por dupla contagem) é uma técnica de demonstração
distinta das apresentadas no Capítulo 3, embora se apoie fundamentalmente na
demonstração por casos: em vez de manipular diretamente a fórmula algébrica de
n
(o que também seria possível, por manipulação direta de fatoriais), interpretamos


k
ambos os lados da igualdade como respostas a uma mesma pergunta combinatória,
contada de duas formas. Esse estilo de argumento é extremamente comum e poderoso
em Matemática Discreta e Combinatória.

5.6 Física Matemática

Proposição 5.20 Conservação da energia mecânica – caso unidimensional
simplificado
Considere uma partícula de massa m > 0 movendo-se sob a ação de uma força con-
dU
servativa F (x) = − , onde U é a energia potencial. Então a energia mecânica total
dx
1 2 dE
E = mv + U (x) é constante ao longo do movimento (isto é, = 0).
2 dt

dv dU
Proof. Pela Segunda Lei de Newton, F = ma, isto é, m =− (usando a hipótese
dt dx
de que a força é conservativa, isto é, derivada de um potencial U ).
1
Calculamos a derivada temporal da energia mecânica E(t) = mv(t)2 + U (x(t)), usando
2
a regra da cadeia:
dE dv dU dx
= mv + · .
dt dt dx dt
dx dU
Como = v (definição de velocidade), o segundo termo é · v. Substituindo, no
dt dx
dv dU
primeiro termo, m = − (pela Segunda Lei de Newton, acima):
dt dx
 
dE dU dU dU dU
=v − + · v = −v +v = 0.
dt dx dx dx dx
68 Chapter 5. Aplicações da Lógica nas Demonstrações Matemáticas

dE
Logo, = 0, isto é, a energia mecânica E é constante ao longo do tempo. ■
dt

Observação 5.21
Esta demonstração é um exemplo de demonstração direta em Física Matemática:
partimos de uma lei física fundamental (a Segunda Lei de Newton, aqui tomada como
axioma físico) e, por meio de manipulação algébrica e de cálculo diferencial (regra da
cadeia), chegamos à conclusão de que uma quantidade específica (a energia mecânica)
permanece constante. A estrutura lógica – hipóteses (lei de Newton, força conserva-
tiva) implicando uma tese (conservação de E) – é rigorosamente idêntica à estrutura
de qualquer teorema matemático estudado neste texto; o que distingue esta demon-
stração de uma demonstração "puramente matemática" é apenas a natureza física das
hipóteses envolvidas (leis empíricas, e não axiomas puramente lógicos ou conjuntistas),
não a forma lógica do argumento.

Observação 5.22 Síntese do capítulo

Ao longo deste capítulo, vimos a mesma "gramática" lógica – demonstração direta,
por contraposição, por contradição, por casos, por indução, e mesmo variantes espe-
cializadas como a dupla contagem combinatória – reaparecer, com roupagens distintas,
em Álgebra, Análise, Teoria dos Conjuntos, Geometria, Matemática Discreta e Física
Matemática. Essa recorrência não é acidental: como afirmamos desde o Prefácio, a
lógica matemática é a linguagem comum sobre a qual todas essas áreas se apoiam.
Dominar essa linguagem – seu vocabulário (proposições, predicados, quantificadores)
e sua gramática (regras de inferência, técnicas de demonstração) – é, portanto, um
investimento que rende frutos em toda a formação matemática subsequente do estu-
dante, independentemente da área de especialização que venha a escolher.
Capítulo 6

Exercícios Gerais

Este capítulo final reúne uma coleção ampla de exercícios que integram todos os temas
estudados nesta apostila: lógica proposicional, lógica de predicados, regras de inferên-
cia, técnicas de demonstração (direta, contraposição, contradição, casos, indução) e a
construção autônoma de provas. Os problemas estão organizados em três níveis de difi-
culdade crescente. Nenhuma solução é apresentada: o objetivo é que o leitor exercite, de
forma autônoma, as habilidades desenvolvidas ao longo dos capítulos anteriores.

6.1 Nível básico

Exercício 6.1. Construa a tabela-verdade de (p ∧ ¬q) ∨ (¬p ∧ q) e determine se é
tautologia, contradição ou contingência.

Exercício 6.2. Determine se o argumento a seguir é válido, construindo a tabela-verdade

correspondente: p → q, q ∴ p.

Exercício 6.3. Traduza para linguagem simbólica: "n é par se, e somente se, n + 1 é
ímpar".

Exercício 6.4. Negue a proposição: "Todos os alunos da turma passaram no exame".

Exercício 6.5. Considerando o universo de discurso N, determine o valor de verdade de

∃n ∈ N, n2 = 2n.

Exercício 6.6. Aplique Modus Ponens às premissas: "Se x é solução da equação, então
x2 − 4 = 0" e "x = 2 é solução da equação".

Exercício 6.7. Demonstre diretamente que a soma de dois números pares é par.

Exercício 6.8. Demonstre diretamente que, se n é múltiplo de 5, então n2 é múltiplo

de 5.

Exercício 6.9. Escreva a contrapositiva da afirmação: "se x2 é irracional, então x é

irracional", e diga se você acredita que a afirmação original é verdadeira.

Exercício 6.10. Demonstre por indução que, para todo n ≥ 1: 2 + 4 + 6 + · · · + 2n =

n(n + 1).

69
70 Chapter 6. Exercícios Gerais

Exercício 6.11. Verifique se o seguinte argumento é válido: "Todo número primo maior
que 2 é ímpar. 9 é ímpar. Logo, 9 é primo." Justifique sua resposta.

Exercício 6.12. Dê um exemplo de proposição que seja verdadeira, mas cuja recíproca
seja falsa.

6.2 Nível intermediário

Exercício 6.13. Demonstre, usando as equivalências lógicas do Capítulo 1, que (p →
r) ∧ (q → r) ≡ (p ∨ q) → r.

Exercício 6.14. Sejam as premissas: p → (q ∨ r), ¬q, ¬r. Deduza ¬p, indicando
claramente as regras de inferência utilizadas em cada passo.

Exercício 6.15. Traduza para linguagem simbólica e depois negue: "Para todo número
real x, existe um número real y tal que x + y = 0, mas não existe x tal que, para todo y,
xy = 1".

Exercício 6.16. Demonstre por contraposição: se n ∈ Z e n3 é par, então n é par.

Exercício 6.17. Demonstre por contradição que não existe o menor número real positivo
(isto é, para todo real x > 0, existe um real y com 0 < y < x).

Exercício 6.18. Demonstre por casos: para todo n ∈ Z, n2 + n + 1 é ímpar. (Sugestão:

considere os casos n par e n ímpar.)

Exercício 6.19. Sejam A e B conjuntos. Demonstre que A ⊆ B se, e somente se,

A ∪ B = B. (Sugestão: demonstre as duas direções do bicondicional separadamente.)

Exercício 6.20. Demonstre que a função h : R \ {0} → R \ {0} dada por h(x) = 1/x é
injetiva e sobrejetiva.
1 1 1
Exercício 6.21. Demonstre por indução que, para todo n ≥ 1: 1 + + + · · · + n−1 =
2 4 2
1
2 − n−1 .
2
Exercício 6.22. Demonstre, usando a Desigualdade das Médias (Teorema 3.5) ou outro
1 1 1
método de sua escolha, que, para a, b, c > 0 com a + b + c = 1: + + ≥ 9.
a b c
Exercício 6.23. Um estudante escreveu a seguinte "demonstração" de que todo número
natural é igual ao seu sucessor menos 1: "Seja n um natural qualquer. Sabemos que n + 1
é o sucessor de n. Logo, n = (n + 1) − 1, que é o que queríamos demonstrar." Critique
esta demonstração: ela é logicamente válida? Ela é informativa? Compare com o conceito
de petição de princípio discutido no Capítulo 4.

Exercício 6.24. Demonstre, por indução forte, que todo número natural n ≥ 2 é primo
ou pode ser escrito como produto de dois naturais menores, cada um maior ou igual a 2
(não é necessário demonstrar a fatoração completa em primos, apenas este passo).
6.3. Nível avançado 71

6.3 Nível avançado

Exercício 6.25. Demonstre que, para todo n ∈ N, o número n5 − n é divisível por 30.
(Sugestão: fatore n5 − n e utilize divisibilidade por 2, 3 e 5 separadamente, combinando
demonstração por casos e resultados de divisibilidade.)
√
Exercício 6.26. Demonstre√ que 3 é irracional, adaptando cuidadosamente a estrutura
da demonstração de que 2 é irracional (Teorema 3.2). Identifique explicitamente em
qual ponto da demonstração original a propriedade "2 é primo" foi essencial, e verifique
que a propriedade análoga para 3 permite adaptar o argumento.

Exercício 6.27. Demonstre que não existem inteiros positivos a, b, c tais que a2 +
b2 = 3c2 , exceto a = b = c = 0. (Sugestão: utilize descida infinita, uma variante da
demonstração por contradição combinada com indução forte, analisando a paridade ou
divisibilidade por 3 de a, b, c.)

Exercício 6.28. Utilizando indução matemática, demonstre a fórmula do binômio de

Newton: para todo n ∈ N e a, b ∈ R,
n  
n
X n n−k k
(a + b) = a b ,
k=0
k

utilizando a Relação de Pascal (Proposição 5.5) no passo indutivo.

Exercício 6.29. Demonstre, por indução estrutural (Seção 4.4), que toda árvore binária
com n nós internos possui exatamente n + 1 folhas, onde uma árvore binária é definida
recursivamente como: (caso base) uma única folha; ou (regra de construção) um nó interno
com duas subárvores binárias como filhas.

Exercício 6.30. Considere a afirmação: "para todo conjunto finito não vazio S de
números reais, S possui um elemento máximo". Demonstre esta afirmação por indução
forte no número de elementos de S, tomando cuidado especial com a base da indução (con-
juntos unitários) e com o passo indutivo (comparação entre o máximo de um subconjunto
e um novo elemento adicionado).

Exercício 6.31. Demonstre que, para todo conjunto finito S com |S| = n, o conjunto
das partes P(S) possui exatamente 2n elementos. (Sugestão: por indução em n; no passo
indutivo, relacione P(S ∪ {x}), para um novo elemento x ∈/ S, com P(S), dividindo os
subconjuntos de S ∪ {x} conforme contenham ou não x – uma estratégia semelhante à
demonstração da Relação de Pascal, Proposição 5.5.)

Exercício 6.32. Reconstrua, com todos os detalhes lógicos explícitos (identificando

claramente hipótese, tese, técnica de demonstração empregada, e cada passagem algébrica
ou lógica), uma√demonstração completa de que, para todo n ≥ 1, se n não é um quadrado
√ então n é irracional. (Sugestão: generalize cuidadosamente o argumento usado
perfeito,
para 2, prestando atenção especial a onde a hipótese "n não é quadrado perfeito" é
utilizada.)

Exercício 6.33. Analise criticamente a seguinte afirmação, decidindo se é verdadeira ou

falsa e demonstrando sua resposta com rigor completo: "para todos os conjuntos A, B, C,
72 Chapter 6. Exercícios Gerais

se A ∪ B = A ∪ C, então B = C". Caso a afirmação seja falsa, exiba um contraexemplo

explícito; caso seja verdadeira sob alguma hipótese adicional razoável, identifique tal
hipótese e demonstre a versão corrigida.

Exercício 6.34. síntese final Escolha um teorema de qualquer disciplina que você esteja
cursando atualmente (Física, Cálculo, Álgebra Linear, ou outra), enuncie-o com precisão
(identificando claramente hipótese e tese, e traduzindo-o, na medida do possível, para a
notação lógica e de quantificadores estudada nesta apostila), e escreva uma demonstração
completa e rigorosa, identificando explicitamente qual(is) técnica(s) de demonstração den-
tre as estudadas no Capítulo 3 (direta, contraposição, contradição, casos, existência e
unicidade) e no Capítulo 4 (indução) você utilizou, e por que essa escolha foi apropriada.

Fim da apostila. Esperamos que este material tenha fornecido não apenas um conjunto
de técnicas formais, mas uma nova maneira de enxergar a matemática: como um edifício
de raciocínios rigorosos, construído tijolo a tijolo, sobre os alicerces sólidos da lógica.