Carlos - Matematica Discreta

Prévia do material em texto

Matemática Discreta 
Notas de Aula - versão 1.0 
Baseado no Livro “Matemática discreta y sus aplicaciones”, Kenneth H. Rosen, quinta edição. 
Prof. Carlos R. P. Dionisio 
 
1. Lógica e Demonstração 
Neste capitulo, faremos uma revisão dos fundamentos da matemática discreta, entre eles 
a lógica, conjuntos e funções. As regras da lógica especificam o significado dos 
enunciados matemáticos. Por exemplo, estas regras nos ajudam a entender e raciocinar 
enunciados como “Existe um número inteiro que não é a soma do quadrado de dois 
números inteiros” ou “Para todo inteiro positivo n, a soma dos inteiros positivos menor 
ou igual a n é �(� + 1)/2”. A lógica é a base de todo raciocínio matemático com 
aplicações em inteligência artificial, a programação computacional, as linguagens de 
programação, etc. 
Para entender matemáticas devemos entender o que é que constitui um argumento 
matemático correto, ou seja, uma demonstração. As demonstrações são importantes não 
somente em matemáticas, também em vários tópicos da ciência da computação como, 
por exemplo, verificação de programas, análise de algoritmos e sistemas de segurança. 
1.1. Lógica 
As regras da lógica fornecem um significado preciso aos enunciados 
matemáticos ou sentenças matemáticas. Estas regras se usam para distinguir 
entre argumentos válidos e não válidos. 
Proposições: Uma proposição é uma sentença declarativa que é verdadeira ou 
falsa, porem não ambas. 
Exemplo 1: Todas as seguintes sentenças são proposições: 
1. Bruxelas é a capital da União Europeia. 
2. Toronto é a capital de Canada. 
3. 1 + 1 = 2. 
4. 2 + 2 = 3. 
As proposições 1 e 3 são verdadeiras, enquanto que a 2 e 4 são falsas. 
Exemplo 2: Todas as seguintes sentenças não são proposições: 
1. Que horas são? 
2. Lê isto com atenção. 
3. � + 1 = 2. 
4. � + � = �. 
As sentenças 1 e 2 não são proposições porque não são declarativas. As 
sentenças 3 e 4 não são proposições porque não são nem verdadeiras nem 
falsas. 
A área da lógica que trata de proposições é chamada de lógica proposicional. 
Muitos enunciados matemáticos se constroem combinando uma ou mais 
proposições. As novas proposições, chamadas proposições compostas, se 
formam a partir das existentes usando operadores lógicos. 
 
Definição 1: Seja p uma proposição. O enunciado “Não se cumpre p” é outra 
proposição chamada de negação de p. A negação de p se denota mediante ¬� 
(também denotada por �). 
 
Exemplo 3: Obtenha a negação do enunciado “Hoje é sexta feira”. 
1. Não se cumpre que hoje é sexta feira. 
2. Hoje não é sexta feira. 
Obs.: De forma estrita, os enunciados relacionados com tempos variáveis não 
são proposições, a não ser que se assuma um tempo fixo. 
 
Uma tabela de verdade mostra as relações entre os valores de verdade das 
proposições. A Tabela 1 mostra a tabela de verdade para a negação de uma 
proposição p. 
 
Tabela 1. Tabela de verdade para 
a negação de uma proposição. 
� ¬� 
V F 
F V 
 
Definição 2: Sejam p e q proposições. A proposição “p e q”, denotada por �˄�, 
é a proposição que é verdadeira quando p e q são verdadeiras e falsa em 
qualquer outro caso. A proposição �˄� é chamada de conjunção de p e q. 
 
A tabela de verdade para �˄� é mostrado na Tabela 2. 
 
Tabela 2. Tabela de verdade para a conjunção de 
duas proposições. 
� � �˄� 
V V V 
V F F 
F V F 
F F F 
 
Exemplo 4: Obtenha a conjunção das proposições p e q no caso em que p é o 
enunciado “Hoje é sexta feira” e q é “Hoje chove”. 
1. Hoje é sexta feira e hoje chove. 
 
A proposição é verdadeira as sextas feiras com chuva e falsa qualquer dia que 
não seja sexta feira e as sextas feiras que não chove. 
 
Definição 3: Sejam p e q proposições. A proposição “p ou q”, denotada por �˅�, 
é a proposição que é falsa quando p e q são falsos e verdadeiro em qualquer 
outro caso. A proposição �˅� é chamada de disjunção de p e q. 
 
A tabela de verdade para �˅� é mostrado na Tabela 3. 
 
Tabela 3. Tabela de verdade para a disjunção de 
duas proposições. 
� � �˅� 
V V V 
V F V 
F V V 
F F F 
 
Uma disjunção é verdadeira quando ao menos uma das proposições é verdadeira. 
 
Exemplo 5: Obtenha a disjunção das proposições p e q no caso em que p é o 
enunciado “Hoje é sexta feira” e q é “Hoje chove”. 
1. Hoje é sexta feira ou hoje chove. 
Esta proposição é verdadeira qualquer dia que seja sexta feira ou chova 
(incluindo as sextas feiras que chove). É somente falsa os dias que não são sexta 
feira e não chove. 
 
Definição 5: Sejam p e q proposições. A implicação � → � é a proposição que é 
falsa quando p é verdadeira e q é falsa e verdadeira em qualquer outro caso. 
Nesta implicação p é chamada hipótese (ou premissa) e q é chamada de teses ou 
conclusão. 
 
A tabela de verdade para a implicação � → � é mostrado na Tabela 5. 
 
Tabela 5. Tabela de verdade para a implicação 
� → �. 
� � � → � 
V V V 
V F F 
F V V 
F F V 
 
Uma forma útil de entender o valor de verdade de uma implicação é pensar em 
uma obrigação ou contrato. Por exemplo, a promessa que muitos políticos fazem 
para serem eleitos é: 
 “Se eu for eleito, diminuirei os impostos”. 
Somente quando o politico é eleito e não diminui os impostos, podem seus 
votantes dizer que o politico não cumpriu sua promessa eleitoral. 
 
A continuação, mostramos mais exemplos de implicação: 
1. Se hoje fizer sol, então iremos para a praia. 
2. Se hoje é sexta feira, então 2 + 3 = 5. 
3. Se hoje é sexta feira, então 2 + 3 = 6. 
 
Definição 6: Sejam p e q proposições. A bicondicional � ↔ � é a proposição 
que é verdadeira quando p e q tem os mesmos valores de verdade e falsa em 
qualquer outro caso. 
A tabela de verdade para � ↔ � é mostrado na Tabela 6. 
Tabela 6. Tabela de verdade para a bicondicional 
� ↔ �. 
� � � ↔ � 
V V V 
V F F 
F V F 
F F V 
 
Observe que a bicondicional é verdadeira quando as implicações � → � e � → � 
são verdadeiras. Por isso, a terminologia “p se, e somente se, q” se usa para a 
bicondicional. 
 
Exemplo 8: Seja p a sentença “Você pode tomar o voo” e seja q a sentença 
“Compras um bilhete”. Então, � ↔ � é o enunciado “Você pode tomar o voo se 
e somente se compras um bilhete”. 
Esta proposição é verdadeira se p e q são ambas verdadeiras ou falsas. É falsa 
quando p e q tem valores de verdade diferentes. 
 
Considere a seguinte sentença “Se terminas de comer a comida, podes comer a 
sobremesa”. Ela é equivalente a “Podes comer a sobremesa se e somente se 
terminas de comer a comida”. Devido a imprecisão da linguagem natural, 
devemos incluir o reciproco de uma sentença. 
 
Precedência de Operadores Lógicos 
 
Podemos construir formulas usando o operador negação e os operadores lógicos 
definidos anteriormente. Geralmente, vamos utilizar parênteses para especificar 
a ordem em que devem aplicar-se os operadores lógicos numa formula. A Tabela 
7 mostra os níveis de precedência dos operadores lógicos. 
 
Tabela 7. Precedência dos 
operadores lógicos. 
Operador Precedência 
¬ 1 
˄ 2 
˅ 3 
→ 4 
↔ 5 
 
Por exemplo: 
1. ¬�˄� denota (¬�)˄�. 
2. �˄�˅� denota (�˄�)˅�. 
3. �˅� → � denota (�˅�) → �. 
 
Tradução de Frases da Linguagem Natural 
 
Uma das razoes para traduzir frases da linguagem natural a expressões com 
variáveis proposicionais e conectivos lógicos, é a ambiguidade da linguagem 
natural. Este processo é chamado de formalização. 
 
Exemplo 9: Formalize a seguinte frase “Você pode ter acesso a internet dentro 
do campus somente se estudas ciência da computação ou não eres aluno de 
primeiro ano”. 
Utilizaremos variáveis proposicionais para representarcada parte da frase e 
determinar os conectivos lógicos apropriados entre eles. Seja 
�: Você pode ter acesso a internet dentro do campus 
�: estudas ciência da computação 
�: eres aluno de primeiro ano 
 
Considerando que “somente se” é uma forma de expressar uma implicação, a 
frase pode ser representada como � → (�˅¬�). 
 
Exemplo 10: Formalize a seguinte frase “Você não pode entrar na montanha 
russa se tens altura menor que 1,20 m, a não ser que tenhas mais de 16 anos”. 
 
�: Você pode entrar na montanha russa 
�: tens altura menor que 1,20 m 
�: tens mais de 16 anos 
 
A frase pode ser formalizada como (�˄¬�) → ¬�. 
 
1.2. Equivalências Proposicionais 
 
Na construção de argumentos matemáticos se empregam com frequência 
métodos que produzem proposições com o mesmo valor de verdade que uma 
formula dada. 
 
Definição 1: Uma formula que é sempre verdadeira, não importa os valores de 
verdade das proposições que a compõem, se denomina tautologia. Uma formula 
que é sempre falsa se denomina contradição. Finalmente, uma proposição que 
não é uma tautologia nem uma contradição se denomina contingencia. 
 
Exemplo 1: Considere as tabelas de verdade de �˅¬� e �˄¬�. Como �˅¬� é 
sempre verdadeira é uma tautologia. Como �˄¬� é sempre falso é uma 
contradição. 
 
Equivalências Lógicas 
 
As formulas que tem os mesmos valores de verdade em todos os casos possíveis 
são chamados logicamente equivalentes. 
 
Definição 2: Dizemos que as proposições p e q são logicamente equivalentes se 
� ↔ � é uma tautologia. A notação � ≡ � denota que p e q são logicamente 
equivalentes. 
 
O símbolo ⇔ se usa as vezes no lugar de ≡ para denotar uma equivalência 
lógica. 
 
Exemplo 2: Mostre que ¬(�˅�) e ¬�˄¬� são logicamente equivalentes. 
 
As tabelas de verdade para estas proposições se mostram na Tabela 2. 
 
Tabela 2. Tabelas de verdade para ¬(�˅�) e ¬�˄¬�. 
� � �˅� ¬(�˅�) ¬� ¬� ¬�˄¬� 
V V V F F F F 
V F V F F V F 
F V V F V F F 
F F F V V V V 
 
Como os valores de verdade das proposições ¬(�˅�) e ¬�˄¬� correspondem 
para todas as combinações possíveis de valores de verdade para p e q, então 
¬(�˅�) ↔ ¬�˄¬� é uma taulologia e estas proposições são logicamente 
equivalentes. 
 
Exemplo 3: Mostre que as proposições � → � e ¬�˅� são logicamente 
equivalentes. 
 
Exemplo 4: Mostre que as proposições �˅(�˄�) e (�˅�) ˄(�˅�) são 
logicamente equivalentes. 
 
 
 
 
 
Tabela 4. Tabelas de verdade para �˅(�˄�) e (�˅�) ˄(�˅�). 
 
� � � �˄� �˅(�˄�) �˅� �˅� (�˅�) ˄(�˅�) 
V V V V V V V V 
V V F F V V V V 
V F V F V V V V 
V F F F V V V V 
F V V V V V V V 
F V F F F V F F 
F F V F F F V F 
F F F F F F F F 
 
 
As equivalências logicas da Tabela 5, assim como outras que foram 
estabelecidas (Tabelas 6 e 7), podem ser utilizadas para construir novas 
equivalências logicas. Numa formula, uma proposição pode ser substituída por 
outra que seja logicamente equivalente sem mudar o valor de verdade da 
formula. 
 
Tabela 5. Equivalências Logicas 
 
Equivalência Nome 
�˄� ≡ � �˅� ≡ � Leis da identidade 
�˅� ≡ � �˄� ≡ � Leis da dominação 
�˅� ≡ � �˄� ≡ � 
Lei idempotente 
¬(¬�) ≡ � 
Lei da dupla negação 
�˅� ≡ �˅� �˄� ≡ �˄� 
Leis da comutatividade 
(�˅�)˅� ≡ �˅(�˅�) (�˄�)˄� ≡ �˄(�˄�) 
Leis da associatividade 
�˅(�˄�) ≡ (�˅�)˄(�˅�) �˄(�˅�) ≡ (�˄�)˅(�˄�) 
Leis da distributividade 
¬(�˄�) ≡ ¬�˅¬� ¬(�˅�) ≡ ¬�˄¬� 
Leis de Morgan 
�˅(�˄�) ≡ � �˄(�˅�) ≡ � 
Leis da absorção 
�˅¬� ≡ � �˄¬� ≡ � 
Leis da negação 
 
 
 
 
 
 
Tabela 6. Equivalências logicas 
relacionadas com implicações 
� → � ≡ ¬�˅� 
� → � ≡ ¬� → ¬� 
�˅� ≡ ¬� → � 
�˄� ≡ ¬(� → ¬�) 
¬(� → �) ≡ �˄¬� 
(� → �)˄(� → �) ≡ � → (�˄�) 
(� → �)˄(� → �) ≡ (�˅�) → � 
(� → �)˅(� → �) ≡ � → (�˅�) 
(� → �)˅(� → �) ≡ (�˄�) → � 
 
 
Tabela 7. Equivalências logicas 
relacionadas com implicações 
� ↔ � ≡ (� → �)˄(� → �) 
� ↔ � ≡ ¬� → ¬� 
� ↔ � ≡ (�˄�)˅(¬�˄¬�) 
¬(� ↔ �) ≡ � ↔ ¬� 
 
Exemplo 5: Mostre que as proposições ¬(�˅(¬�˄�)) e ¬�˄¬� são 
logicamente equivalentes. 
 
Podemos utilizar uma tabela de verdade para mostrar que as proposições são 
equivalentes. Em lugar disso, estabeleceremos a equivalência utilizando 
equivalências logicas da Tabela 5. 
 
¬(�˅(¬�˄�)) ≡ ¬�˄¬(¬�˄�) Segunda lei de Morgan 
 ≡ ¬�˄(¬(¬�)˅¬�) Primeira lei de Morgan 
 ≡ ¬�˄(�˅¬�) Lei da dupla negação 
 ≡ (¬�˄�)˅(¬�˄¬�) Segunda lei da distributividade 
 ≡ �˅(¬�˄¬�) ¬�˄� ≡ � 
 ≡ (¬�˄¬�)˅� Lei da comutatividade da disjunção 
 ≡ (¬�˄¬�) Lei da identidade para � 
 
Portanto, ¬(�˅(¬�˄�)) e ¬�˄¬� são logicamente equivalentes. 
 
 
 
Exemplo 6: Mostre que (�˄�) → (�˅�) é uma tautologia. 
 
Vamos mostrar que a proposição é logicamente equivalente a �. 
 
(�˄�) → (�˅�) ≡ ¬(�˄�)˅(�˅�) Exemplo 3 
 ≡ (¬�˅¬�)˅(�˅�) Primeira lei de Morgan 
 ≡ (¬�˅�)˅(¬�˅�) Leis da associatividade e 
comutatividade da disjunção 
 ≡ �˅� Exemplo 1 e a lei da comutatividade 
para a disjunção 
 ≡ � Lei da dominação 
 
Portanto, (�˄�) → (�˅�) é uma tautologia. 
 
1.3. Predicados e Quantificadores 
 
Considere a seguinte sentença “ � > 3 ”. Ele não é verdadeiro nem falso se não 
se especifica o valor da variável. A sentença “ � é maior que 3 ” tem duas 
partes. A primeira parte é a variável � chamada de sujeito. A segunda parte “ é 
maior que 3 ” é chamada de predicado e faz referência a uma propriedade que 
pode ter o sujeito. Vamos denotar a sentença “ � é maior que 3 ” por �(�), onde 
� denota o predicado e � é a variável. Uma vez que se assigne um valor para a 
variável �, a sentença �(�) se torna numa proposição e tem um valor de 
verdade. 
 
Exemplo 1: Seja �(�) que denota a sentença “ � > 3 ”. Quais são os valores de 
verdade de �(4) e �(2) ? 
 
Quantificadores 
 
A quantificação cria uma proposição a partir de uma função proposicional. 
Abordaremos dois tipos de quantificação, a saber, quantificação universal e 
quantificação existencial. 
 
Quantificador Universal 
 
Muitas sentenças matemáticas impõem que uma propriedade seja verdadeira 
para todos os valores de uma variável num domínio particular. Tais sentenças 
são expressas utilizando um quantificador universal. A quantificação universal 
de uma função proposicional é a proposição que afirma que �(�) é verdadeira 
para todos os valores de � no domínio. O domínio especifica os possíveis 
valores da variável �. 
 
 
Definição 1: A quantificação universal de �(�) é a proposição “�(�) é 
verdadeira para todos os valores � do domínio”. 
 
A notação ∀� ∈ �: �(�) denota a quantificação universal de �(�). 
Chamaremos o símbolo ∀ o quantificador universal. A proposição ∀� ∈
�: �(�) se lê como “para todo � ∈ �: �(�)”. 
 
Um número natural é um número inteiro não-negativo. O conjunto dos números 
naturais é denotado pelo símbolo ℕ. 
ℕ = {0, 1, 2, 3, … } 
ℤ denota o conjunto dos números inteiros. 
ℤ� denota o conjunto dos números inteiros positivos. 
ℚ denota o conjunto dos números racionais. 
ℝ denota o conjunto dos números reais. 
 
Exemplo 5: Qual é o valor de verdade da quantificação ∀� ∈ ℝ: � + 1 > � ? 
Exemplo 6: Qual é o valor de verdade da quantificação ∀� ∈ ℝ: � < 2 ? 
Exemplo 7: Qual é o valor de verdade da quantificação ∀� ∈ ℕ˄� ≤ 4: �� <
10 ? 
 
Quantificador Existencial 
 
Muitas sentenças matemáticas afirmam que existe um elemento com algumapropriedade. Tais sentenças se expressam através de quantificadores 
existenciais. Com um quantificador existencial formamos uma proposição que é 
verdadeira se e somente se �(�) é verdadeira para ao menos um valor � no 
domínio. 
 
Definição 2: A quantificação existencial de �(�) é a proposição “Existe um 
elemento � no domínio tal que �(�) é verdadeira”. 
 
Utilizamos a notação ∃� ∈ �: �(�) para a quantificação existencial de �(�). O 
símbolo ∃ se denomina quantificador existencial. A quantificação existencial 
∃� ∈ �: �(�) se lê como “Existe um � que pertence a � tal que �(�)”. 
 
Exemplo 11: Qual é o valor de verdade da quantificação ∃� ∈ ℝ: � > 3 ? 
Exemplo 12: Qual é o valor de verdade da quantificação ∃� ∈ ℝ: � = � + 1 ? 
Exemplo 11: Qual é o valor de verdade da quantificação ∃� ∈ ℕ˄� ≤ 4: �� >
10? 
 
Na Tabela 1 se resume o significado dos quantificadores universais e 
existenciais. 
 
 
 
 
Tabela 1. Quantificadores. 
Sentença Quando é verdadeira? Quando é falsa? 
∀� ∈ �: �(�) �(�) é verdadeira para 
todo � ∈ � 
Existe um � ∈ � tal que �(�) é falsa 
∃� ∈ �: �(�) Existe um � ∈ � tal que 
�(�) é verdadeira 
�(�) é falsa para todo � ∈ � 
 
 
Negações de Quantificadores 
 
Frequentemente se faz necessário considerar a negação de uma expressão 
quantificada. Por exemplo, considere a negação do enunciado “Todos os 
estudantes de GCC103 já fizeram uma disciplina de cálculo”. 
 
Esta sentença é uma quantificação universal da forma 
∀� ∈ �: �(�), onde �(�) é a sentença “� já fez uma disciplina de cálculo”. A 
negação de esta sentença é “Não se cumpre que todos os estudantes de GCC103 
já fizeram uma disciplina de cálculo”. Isto é equivalente a “Existe pelo menos 
um estudante de GCC103 que não fez uma disciplina de cálculo”. Isto é a 
quantificação existencial da negação da função proposicional original, ou seja, 
∃� ∈ �: ¬�(�). 
 
Este exemplo ilustra a seguinte equivalência: 
 
¬∀� ∈ �: �(�) ≡ ∃� ∈ �: ¬�(�). 
 
De forma similar, podemos estabelecer a seguinte equivalência: 
 
¬∃� ∈ �: �(�) ≡ ∀� ∈ �: ¬�(�). 
 
Exemplo 15: Quais são as negações dos seguintes enunciados: 
a. Há um político honesto 
b. Todos os americanos comem hambúrguer 
 
a. Todo político é desonesto 
b. Alguns americanos não comem hambúrguer 
 
Exemplo 16: Quais são as negações das seguintes sentenças: 
a. ∀� ∈ ℝ: �� > � 
b. ∃� ∈ ℝ: �� = 2 
 
Exemplo 17: Expresse a frase “Todo estudante desta aula já fez cálculo” 
utilizando predicados e quantificadores. 
 
 Para todo estudante desta aula, esse estudante já fez cálculo. 
 Para todo estudante � desta aula, � já fez cálculo. 
 ∀� ∈ �: �(�) onde � consiste nos estudantes desta aula e �(�) é o 
predicado “� já fez cálculo”. 
 
Exemplo 18: Formalize as seguintes frases: 
a. Algum estudante desta aula já visitou México 
b. Todo estudante desta aula já visitou México ou Argentina 
 
 Há um estudante nesta aula tal que esse estudante já visitou México 
 Há um estudante � nesta aula tal que � já visitou México 
 ∃� ∈ �: �(�) onde � consiste nos estudantes desta aula e �(�) é o 
predicado “� já visitou México”. 
 
 Para todo estudante � desta aula, � já visitou México ou � já visitou 
Argentina. 
 ∀� ∈ �: �(�)˅�(�) onde � consiste nos estudantes desta aula, �(�) é 
o predicado “� já visitou México” e �(�) é o predicado “� já visitou 
Argentina”. 
 
Exemplo 19: Considere as seguintes frases. As duas primeiras se denominam 
premissas e a terceira se denomina conclusão. O conjunto das três se denomina 
argumento. 
a. Todos os leões são ferozes 
b. Alguns leões não tomam café 
c. Algumas criaturas ferozes não tomam café 
Sejam �(�), �(�) e �(�) os enunciados “� é um leão”, “� é feroz” e “� toma 
café”, respectivamente. Supondo que o domínio � é o conjunto de todas as 
criaturas, expresse as sentenças do argumento utilizando quantificadores. 
 
a. ∀� ∈ �: �(�) → �(�) 
b. ∃� ∈ �: �(�)˄¬�(�) 
c. ∃� ∈ �: �(�)˄¬�(�) 
 
 
1.4. Quantificadores Compostos 
 
São quantificadores que se localizam dentro do alcance da aplicação de outros 
quantificadores, como a sentença ∀� ∈ ℝ ∃� ∈ ℝ: � + � = 0. 
 
Exemplo 1: A sentença ∀� ∈ ℝ ∀� ∈ ℝ: � + � = � + � afirma que � + � =
� + � para todo par de números reais � e �. 
Exemplo 2: Traduz a sentença para a linguagem natural ∀� ∈ ℝ ∀� ∈ ℝ: � >
0 ˄ � < 0 → �� < 0. 
 
 Para todo par de números reais � e �, se � > 0 e � < 0, então �� < 0. 
 Para os pares de números reais � e �, se � é positivo e � é negativo, 
então �� é negativo. 
 O produto de um número real positivo e um número real negativo é um 
número real negativo. 
 
Exemplo 4: Traduz a sentença ∃� ∈ � ∀� ∈ � ∀� ∈ �: �(�, �)˄�(�, �)˄(� ≠
�) → ¬�(�, �) a linguagem natural, onde �(�, �) significa que � e � são 
amigos e � consiste em todos os estudantes da faculdade. 
 
 Os estudantes � e � são amigos, os estudantes � e � são amigos, � e � 
não são a mesma pessoa, então � e � não são amigos. 
 Há um estudante � tal que para todos os estudantes � e todos os 
estudantes � que são diferentes de �, se � e � são amigos e � e � 
também são amigos, então � e � não são amigos. 
 Há um estudante tal que seus amigos não são amigos entre si. 
 
 
1.5. Métodos de Demonstração 
 
Duas questões importantes que aparecem no estudo das matemáticas são: 
1. Quando um argumento matemático está correto? 
2. Que métodos se podem utilizar para construir argumentos matemáticos? 
 
Um teorema é uma sentença que se pode verificar que é verdadeira. 
Demostramos que um teorema é verdadeiro através de uma sequência de 
sentenças que constituem um argumento chamado demonstração. Para 
construir demonstrações precisamos de métodos para derivar sentenças novas a 
partir das conhecidas. As sentenças que se utilizam numa demonstração podem 
incluir axiomas ou postulados, hipóteses do teorema ou teoremas demonstrados 
previamente. As regras de inferência, que são os meios usados para deduzir 
conclusões a partir de outras afirmações, ligam os passos de uma demonstração. 
 
Um lema é um teorema simples utilizado na demonstração de outros teoremas. 
Um corolário é uma proposição que se pode estabelecer diretamente a partir de 
um teorema que já foi demonstrado. Uma conjectura é uma sentença cujo valor 
de verdade é desconhecido. Quando se encontra uma demonstração para uma 
conjectura, ela se converte num teorema. 
 
Regras de Inferência 
 
Estas regras justificam os passos dados para demonstrar que a partir de uma 
serie de hipóteses se obtém de forma logica uma conclusão. A tautologia 
(�˄(� → �)) → � é a base da regra de inferência chamada modus ponens. Esta 
tautologia se escreve da seguinte forma: 
 
� 
� → � 
∴ � 
 
O símbolo ∴ denota “Portanto”. O modus ponens declara que se uma 
implicação e sua hipótese são verdadeiras, então a conclusão desta implicação é 
verdadeira. 
 
Exemplo 1: Suponha que a implicação “se hoje nevar, iremos a esquiar” e a 
hipótese “hoje esta nevando” são verdadeiras. Então, pelo modus ponens, segue 
que a conclusão “iremos a esquiar” é verdadeira. 
 
Exemplo 2: Suponha que a implicação “se � é maior que 3, então �� é maior 
que 9” é verdadeira. Portanto, se � é maior que 3, pelo modus ponens, segue 
que �� é maior que 9. 
 
A Tabela 1 mostra uma lista de regras de inferência mais importantes. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Tabela 1. Regras de inferência. 
Regra de 
inferência 
Tautologia Nome 
� 
∴ �˅� 
� → (�˅�) Adição 
�˄� 
∴ � 
(�˄�) → � Simplificação� 
� → � 
∴ � 
(�˄(� → �)) → � Modus ponens 
¬� 
� → � 
∴ ¬� 
(¬�˄(� → �)) → ¬� Modus tollens 
� → � 
� → � 
∴ � → � 
((� → �)˄(� → �)) → (� → �) Silogismo hipotético 
�˅� 
¬� 
∴ � 
((�˅�)˄¬�) → � Silogismo disjuntivo 
 
 
 
Exemplo 3: Qual é a regra de inferência na qual se baseia o seguinte 
argumento: “Agora estamos debaixo de zero graus. Portanto, estamos debaixo 
de zero graus ou chove agora”. 
 
Seja � a proposição “Agora estamos debaixo de zero graus” e � “chove agora”. 
Então, este argumento é da seguinte forma: 
� 
∴ �˅� 
 
Este argumento utiliza a regra da adição. 
 
Exemplo 4: Qual é a regra de inferência na qual se baseia o seguinte 
argumento: “Estamos debaixo de zero graus e chove. Portanto, estamos debaixo 
de zero graus”. 
 
Seja � a proposição “Estamos debaixo de zero graus” e � “chove”. Então, este 
argumento é da seguinte forma: 
�˄� 
∴ � 
Este argumento utiliza a regra da simplificação. 
 
 
Exemplo 5: Qual é a regra de inferência na qual se baseia o seguinte 
argumento: “Se hoje chove, então hoje não faremos churrasco. Se hoje não 
faremos um churrasco, faremos um churrasco amanha. Portanto, se hoje chove 
então faremos um churrasco amanha”. 
 
Seja � a proposição “hoje chove”, � “hoje não faremos um churrasco” e � 
“faremos um churrasco amanha”. Então, este argumento é da seguinte forma: 
� → � 
� → � 
∴ � → � 
 
Este argumento utiliza a regra do silogismo hipotético. 
 
Argumentos válidos 
 
Um argumento dedutivo é correto se sempre que todas as hipóteses são 
verdadeiras, então a conclusão também é verdadeira. Consequentemente, 
mostrar que � se deduz logicamente das hipóteses ��, ��, … , �� é o mesmo que 
mostrar que a implicação (��˄��˄ … ˄��) → � é verdadeira. Quando todas as 
proposições utilizadas num argumento correto são verdadeiras, se obtém uma 
conclusão correta. Porem, um argumento correto pode levar a uma conclusão 
incorreta se utilizamos uma ou mais proposições falsas no argumento. Por 
exemplo 
 
Se √2 >
�
�
 então (√2)� > (
�
�
)�. Sabemos que √2 >
�
�
; portanto (√2)� = 2 >
(
�
�
)� =
�
�
 
 
é um argumento correto baseado no modus ponens. Porem, a conclusão deste 
argumento é falsa. Utilizou-se no argumento a proposição falsa √2 >
�
�
. 
 
Exemplo 6: Mostre as seguintes hipóteses “Esta tarde não faz sol e faz mais 
frio que ontem”, “Iremos a nadar somente se faz sol”, “Se não vamos a nadar, 
daremos um passeio em canoa” e “Se damos um passeio em canoa, estaremos 
em casa de noite” levam a conclusão “Estaremos em casa de noite”. 
 
Seja � a proposição “Esta tarde faz sol”, � a proposição “faz mais frio que 
ontem”, � a proposição “Iremos a nadar”, � a proposição “daremos um passeio 
em canoa” e � a proposição “Estaremos em casa de noite”. Então, as hipóteses 
se podem expressar como ¬�˄�, � → �, ¬� → � e � → �. A conclusão é �. 
 
 
 
Vamos construir um argumento para mostrar que nossas hipóteses levam a 
conclusão desejada como segue: 
 
1. ¬�˄� Hipoteses 
2. ¬� Simplificação usando o passo 1 
3. � → � Hipoteses 
4. ¬� Modus tollens usando os passos 2 e 3 
5. ¬� → � Hipoteses 
6. � Modus ponens usando os passos 4 e 5 
7. � → � Hipoteses 
8. � Modus ponens usando os passos 6 e 7 
 
Regras de inferência para sentenças quantificadas 
Estas regras de inferência se usam com frequência nos argumentos matemáticos, 
as vezes sem menciona-las explicitamente. 
Particularização universal é a regra de inferência que se utiliza para concluir 
que �(�) é verdadeira, onde � é um elemento particular do domínio �, dada a 
premissa ∀� ∈ �: �(�). Utiliza-se a particularização universal quando se conclui 
da sentença “Todas as mulheres são sabias” que “Maria é sabia”, onde Maria é 
um elemento do domínio � de todas as mulheres. 
Generalização universal é a regra de inferência que declara que ∀� ∈ �: �(�) é 
verdadeira, dada a premissa de que �(�) é verdadeiro para todos os elementos � 
no domínio �. Utilizamos a generalização universal quando mostramos que 
∀� ∈ �: �(�) é verdadeira tomando um elemento arbitrário � do domínio e 
mostrando que �(�) é verdadeira. 
Particularização existencial é a regra que nos permite concluir que existe um 
elemento � no domínio � tal que �(�) é verdadeiro se sabemos que ∃� ∈
�: �(�) é verdadeiro. Geralmente, não temos conhecimento das propriedade de 
�, somente que este existe. 
Generalização existencial é a regra de inferência que se utiliza para concluir 
que ∃� ∈ �: �(�) é verdadeiro quando se conhece um elemento particular � com 
�(�) verdadeiro. 
Resumimos estas regras de inferência na Tabela 2. 
 
 
 
Regra de inferência Nome 
∀� ∈ �: �(�) 
∴ �(�) 
Particularização 
universal 
�(�) para um � arbitrário 
∴ ∀� ∈ �: �(�) 
Generalização 
universal 
∃� ∈ �: �(�) 
∴ �(�) para algum elemento � 
Particularização 
existencial 
�(�) para algum elemento � 
∴ ∃� ∈ �: �(�) 
Generalização 
existencial 
 
Exemplo 12: Mostre que as premissas “Todo aluno da disciplina matemática 
discreta está matriculado em AED2” e “Maria é uma aluna de matemática 
discreta” implica a conclusão “Maria esta matriculada em AED2”. 
 
Se �(�) denota “� é aluno da disciplina matemática discreta”, �(�) denota “� 
está matriculado em AED2” e � denota o conjunto de alunos. Então, as 
premissas são ∀� ∈ �: �(�) → �(�) e �(Maria). A conclusão é �(Maria). 
 
Podemos utilizar os seguintes passos para estabelecer a conclusão a partir das 
premissas: 
 
1. ∀� ∈ �: �(�) → �(�) Premisa 
2. �(Maria) → �(Maria) Particularização universal de 1 
3. �(Maria) Premisa 
4. �(Maria) Modus ponens usando 2 e 3 
 
Exemplo 13: Mostre que as premissas “Um estudante desta aula não há lido o 
livro” e “Todo aluno nesta aula aprovou a primeira prova” implica a conclusão 
“Alguém que aprovou a primeira prova não há lido o livro”. 
 
Se �(�) denota “� é desta aula”, �(�) denota “� há lido o livro”, �(�) denota 
“� aprovou a primeira prova” e � denota o conjunto de alunos. As premissas são 
∃� ∈ �: �(�)˄¬�(�) e ∀� ∈ �: �(�) → �(�). A conclusão é ∃� ∈
�: �(�)˄¬�(�) . Os seguintes passos estabelecem a conclusão a partir das 
premissas: 
 
1. ∃� ∈ �: �(�)˄¬�(�) Premisa 
2. �(�)˄¬�(�) Particularização existencial de 1 
3. �(�) Simplificação de 2 
4. ∀� ∈ �: �(�) → �(�) Premisa 
5. �(�) → �(�) Particularização universal de 4 
6. �(�) Modus ponens usando 3 e 5 
7. ¬�(�) Simplificação de 2 
8. �(�)˄¬�(�) Conjunção de 6 e 7 
9. ∃� ∈ �: �(�)˄¬�(�) Generalização existencial de 8 
 
 
Métodos para demonstrar Teoremas 
 
Dado que muitos teoremas são implicações, as técnicas para demonstrar 
implicações são importantes. Lembre-se que quando se demonstra a sentença 
� → � somente falta demonstrar que � é verdadeiro se � é verdadeiro. 
 
Demonstração Direta 
 
A implicação � → � se pode demonstrar supondo que se � é verdadeiro então � 
deve ser também verdadeiro. Para realizar este tipo de demonstração, se supõe 
que � é verdadeiro e se utilizam regras de inferência e teoremas já 
demonstrados para demonstrar que � deve ser também verdadeiro. 
 
Definição 1: O inteiro � é par se existe um inteiro � tal que � = 2� e é ímpar 
se existe um inteiro � tal que � = 2� + 1. 
 
Exemplo 14: Mostre uma demonstração direta do teorema “Se � é um inteiro 
ímpar, então �� é um inteiro ímpar”. 
 
Supomos que a hipótese é verdadeira, ou seja, � é ímpar. 
Então, � = 2� + 1 para algum inteiro �.Podemos escrever �� = 2(2�� + 2�) + 1, onde � = 2�� + 2� é um inteiro. 
Por tanto, �� é um número ímpar. 
 
Demonstração Indireta 
 
Como a implicação � → � é equivalente a ¬� → ¬�, podemos demonstrar a 
implicação � → � demonstrando a implicação ¬� → ¬�. 
 
Exemplo 15: Mostre uma demonstração indireta do teorema “Se 3� + 2 é 
ímpar, então � é ímpar”. 
 
O teorema anterior é equivalente a “Se � é par, então 3� + 2 é par”. 
Supomos que a hipótese é verdadeira, ou seja, � é par. 
Então, � = 2� para algum inteiro �. 
Podemos escrever 3� + 2 = 2(3� + 1), onde � = 3� + 1 é um inteiro. 
Logo, 3� + 2 é um número par. 
Por tanto, demonstramos o teorema original. 
 
Definição 2: O número racional � é racional se existem dois inteiros � e �, 
� ≠ 0, tal que � = �/�. Um número real que não é racional se denomina 
irracional. 
 
Exemplo 18: Demonstre que a soma de dois números racionais é um número 
racional. 
 
Vamos tentar uma demonstração direta. 
Supomos que � e � são números racionais. 
Da def. 2, existem dois inteiros � e �, � ≠ 0, tal que � = �/�, e existem outros 
dois inteiros � e �, � ≠ 0, tal que � = �/�. 
Podemos escrever � + � =
�
�
+
�
�
=
�����
��
, onde �� + �� é um inteiro e �� ≠ 0. 
Por tanto, � + � é um número racional. 
 
Exemplo 19: Demonstre que se � é um inteiro e �� é ímpar, então � é ímpar. 
 
A demonstração direta não é fácil. 
Vamos tentar uma demonstração indireta. 
A sentença anterior é equivalente a “Se � é um inteiro e � é par, então �� é 
par”. 
Supomos que a hipótese é verdadeira, ou seja, � é par. 
Então, � = 2� para algum inteiro �. 
Podemos escrever �� = 4�� = 2(2��), onde � = 2�� é um inteiro. 
Logo, �� é um número par. 
Por tanto, demonstramos a sentença original. 
 
Demonstração por Redução ao Absurdo 
 
A implicação � → � é equivalente a (�˄¬�) → �˄¬�. Assim, para provar que 
� → �, basta provar que (�˄¬�) → �˄¬�. Ou seja, em uma demonstração por 
redução ao absurdo, supomos que a hipótese e a negação da conclusão são 
ambas verdadeiras e tentamos deduzir uma contradição. 
 
Exemplo 21: Prove que √2 é irracional mostrando uma demonstração por 
redução ao absurdo. 
 
Seja � a proposição “√2 é irracional”. 
Supomos que ¬� é verdadeiro. 
Então √2 é racional. 
Da def. 2, existem dois inteiros � e �, � ≠ 0, tal que √2 = �/�, onde � e � não 
tem fatores comuns. 
Como √2 = �/� então 2 = ��/��. 
Logo, 2b� = a�. 
Como �� é par, então � é par. 
Ou seja, existe um inteiro � tal que � = 2�. 
Assim, 2�� = 4��. Simplificando, obtemos �� = 2��. 
Como �� é par, então � é par. 
Desta forma, os inteiros � e � tem um fator comum igual a 2. 
Se � é a sentença “� e � são inteiros sem fatores comuns”, então ¬� → �˄¬�. 
Por tanto, � é verdadeiro, ou seja, √2 é irracional. 
 
 
Demonstração por Casos (Exaustão) 
 
Para demonstrar uma implicação da forma (��˅��˅ … ˅��) → �, podemos 
utilizar a proposição equivalente (�� → �)˄(�� → �)˄ … ˄(�� → �) 
 
Exemplo 23: Utilize uma demonstração por casos para provar que |��|=
|�||�|, onde � e � são números reais. 
 
Seja � denota “� e � são números reais” e � denota “|��|= |�||�|”. Observe 
que � é equivalente a ��˅��˅��˅��, onde �� denota “� ≥ 0 ˄ � ≥ 0 ”, �� 
denota “� ≥ 0 ˄ � < 0 ”, �� denota “� < 0 ˄ � ≥ 0 ” e �� denota “� < 0 ˄ � <
0”. Para demonstrar � → �, devemos provar que �� → �, �� → �, �� → � e 
�� → �. 
Se � ≥ 0 ˄ � ≥ 0 , então |��|= �� = |�||�|. Logo, �� → �. 
Se � ≥ 0 ˄ � < 0 , então |��|= −�� = � (−� ) = |�||�|. Logo, �� → �. 
Se � < 0 ˄ � ≥ 0 , então |��|= −�� = (−� )� = |�||�|. Logo, �� → �. 
Se � < 0 ˄ � < 0, então |��|= �� = (−� )(−� ) = |�||�|. Logo, �� → �. 
 
Por tanto, provamos que � → �. 
 
3. Raciocínio Matemático, Indução e Recursividade 
 
3.3. Indução Matemática 
 
Qual é a soma dos � primeiros inteiros positivos ímpares? 
 
1 = 1 
1 + 3 = 4 
1 + 3 + 5 = 9 
1 + 3 + 5 + 7 = 16 
1 + 3 + 5 + 7 + 9 = 25 
 
Pelos resultados anteriores, é razoável supor que a soma dos � primeiros 
inteiros positivos ímpares é ��. Se esta suposição é correta para qualquer inteiro 
�, então necessitamos de um método para demonstra-la. 
 
Indução matemática é uma técnica extremamente importante que podemos 
utilizar para demonstrar sentenças desse tipo. Deve ficar claro que a indução 
matemática somente pode ser utilizada na demonstração de resultados que 
foram obtidos de alguma outra forma. 
 
Muitos teoremas afirmam que �(�) é verdadeira para todo � inteiro positivo, 
onde �(�) é uma função proposicional ou predicado como, por exemplo, a 
sentença 1 + 2 + 3 + ⋯ + � = �(� + 1)/2 ou � ≤ 2�. A indução matemática 
se utiliza para demonstrar proposições da forma ∀� ∈ �: �(�), onde o domínio 
� geralmente é o conjunto dos inteiros positivos. 
 
Uma demonstração por indução de que �(�) é verdadeira para todo � inteiro 
positivo consiste em dois passos: 
 
PASSO BASE: Mostramos que a proposição �(1) é verdadeira. 
PASSO DA INDUÇÃO: Mostramos que a implicação �(�) → �(� + 1) é 
verdadeira para todo � inteiro positivo. 
 
A sentença �(�) se denomina hipótese de indução. Quando provamos os dois 
passos de uma demonstração por indução matemática, provamos que �(�) é 
verdadeira para todo � inteiro positivo, ou seja, ∀� ∈ ℤ�: �(�) é verdadeira. 
Este método é chamado de primeiro princípio de indução matemática. 
 
Exemplo 1: Utilize indução matemática para demonstrar que a soma dos � 
primeiros inteiros positivos ímpares é ��. 
 
Seja �(�) a proposição que afirma a soma dos � primeiros inteiros positivos 
ímpares é ��. Ou seja, �(�): 1 + 3 + 5 + ⋯ + (2� − 1) = � �. 
 
PASSO BASE: �(1) afirma que 1 = 1�. 
PASSO DA INDUÇÃO: Supomos que �(�) é verdadeira para algum inteiro 
positivo �, isto é: 
1 + 3 + 5 + ⋯ + (2� − 1) = � �. 
Devemos provar que �(� + 1) é verdadeira, ou seja: 
1 + 3 + 5 + ⋯ + (2� − 1 ) + (2� + 1) = (� + 1)�. 
Se �(�) é verdadeira, então: 
1 + 3 + 5 + ⋯ + (2� − 1 ) + (2� + 1) = �� + (2� + 1) = (� + 1)�. 
Assim, �(� + 1) é verdadeira. 
 
Como �(1) é verdadeira e �(�) → �(� + 1) também é verdadeira para todo � 
inteiro positivo, pelo princípio da indução matemática concluímos que �(�) é 
verdadeira para todo � inteiro positivo. 
 
Exemplo 2: Utilize o método da indução matemática para demonstrar que 
� < 2� para todo inteiro positivo �. 
 
Seja �(�): � < 2�. 
 
PASSO BASE: �(1) afirma que 1 < 2�. 
PASSO DA INDUÇÃO: Supomos que �(�) é verdadeira para algum inteiro 
positivo �, isto é: � < 2� . 
 
Devemos provar que �(� + 1) é verdadeira, ou seja: 
� + 1 < 2���. 
 
Se �(�) é verdadeira, então: 
� + 1 < 2� + 1. 
Como 1 ≤ 2� para todo inteiro positivo �, então: 
� + 1 < 2� + 1 ≤ 2� + 2� = 2. 2� = 2���. 
 
Assim, �(� + 1) é verdadeira. 
 
Por tanto, pelo princípio da indução matemática concluímos que �(�) é 
verdadeira para todo � inteiro positivo. 
 
Exemplo 3: Utilize o método da indução matemática para demonstrar que 
�� − � é divisível por 3 sempre que � seja um inteiro positivo. 
 
Seja �(�) a proposição “�� − � é divisível por 3”. 
 
Exemplo 4: Utilize o método da indução para demonstrar que 1 + 2� + 2� +
⋯ + 2 � = 2��� − 1 para todos os inteiros não negativos �. 
 
Seja �(�): 1 + 2� + 2� + ⋯ + 2 � = 2��� − 1 . 
 
PASSO BASE: �(0) afirma que 2� = 1 = 2� − 1 . 
PASSO DA INDUÇÃO: Supomos que �(�) é verdadeira para algum inteiro 
positivo �, isto é: 1 + 2� + 2� + ⋯ + 2 � = 2��� − 1 . 
 
Devemos provar que �(� + 1) é verdadeira, ou seja: 
1 + 2� + 2� + ⋯ + 2 � + 2��� = 2(���)�� − 1 = 2 ��� − 1 . 
 
Se �(�) é verdadeira, então: 
1+ 2� + 2� + ⋯ + 2 � + 2��� = (2��� − 1 ) + 2��� = 2. 2��� − 1 . 
1 + 2� + 2� + ⋯ + 2 � + 2��� = 2��� − 1 . 
 
Assim, �(� + 1) é verdadeira. 
 
Por tanto, pelo princípio da indução matemática concluímos que �(�) é 
verdadeira para todo � inteiro não negativo. 
 
 
Indução Forte 
 
Há outra forma de indução matemática que frequentemente se utiliza nas 
demonstrações. Nesta forma usamos o mesmo passo base, porem muda o passo 
da indução. Supomos que �(�) é verdadeira para � = 1, ⋯ , � e baseando-nos 
nesta suposição, demonstramos que �(� + 1) deve ser também verdadeira. Este 
método é conhecido como indução forte ou também chamado como o segundo 
princípio da indução matemática. 
 
Os passos utilizados para demonstrar que �(�) é verdadeira para todo inteiro 
positivo � são: 
 
PASSO BASE: Mostramos que a proposição �(1) é verdadeira. 
PASSO DA INDUÇÃO: Mostramos que a implicação 
[�(1)˄�(2)˄ ⋯ ˄� (�)] → �(� + 1) é verdadeira para todo � inteiro positivo. 
 
As duas formas de indução matemática são equivalentes. 
 
Exemplo 14: Mostre que se � é um inteiro maior que 1, então � se pode 
escrever como o produto de números primos. 
 
Seja �(�) a proposição “� se pode escrever como o produto de números 
primos”. 
PASSO BASE: �(2) afirma que 2 pode-se escrever como o produto de 
números primos. Isto é verdade pois 2 = 1 × 2 . 
 
PASSO DA INDUÇÃO: Supomos que �(2)˄ ⋯ ˄� (�) é verdadeira para 
algum inteiro positivo � ≥ 2 . 
 
Devemos provar que �(� + 1) é verdadeira. 
 
Se �(2)˄ ⋯ ˄� (�) é verdadeira para � ≥ 2 , então: 
 
Caso 1: Se � + 1 é primo 
 Então, �(� + 1) é verdadeiro. 
 
Caso 2: Se � + 1 não é primo 
Então, podemos escrever � + 1 como o produto de dois inteiros, ou seja: 
� + 1 = �� tal que 2 ≤ � ≤ � < � + 1. 
Pela hipótese de indução, � e � se podem escrever como o produto de 
números primos. Assim, � + 1 se pode escrever como o produto de 
números primos (isto é, os primos da fatoração de � e �). 
 
Assim, �(� + 1) é verdadeira. 
 
Por tanto, pelo segundo princípio da indução matemática concluímos que �(�) 
é verdadeira para todo inteiro positivo � > 1. 
 
Exemplo 15: Prove que qualquer franquia postal maior ou igual a 12 centavos 
pode ser obtida usando-se selos de 4 e 5 centavos. 
 
Seja �(�) a proposição “uma franquia postal de � centavos pode ser obtida 
usando-se selos de 4 e 5 centavos”. 
 
Demonstração utilizando o primeiro princípio da indução matemática. 
 
PASSO BASE: �(12) afirma que uma franquia postal de 12 centavos pode ser 
obtida usando-se selos de 4 e 5 centavos Isto é verdade considerando três selos 
de 4 centavos. 
 
PASSO DA INDUÇÃO: Supomos que �(�) é verdadeira para algum inteiro 
positivo � ≥ 12 , isto é, uma franquia postal de � centavos pode ser obtida 
usando-se selos de 4 e 5 centavos. 
 
Devemos provar que �(� + 1) é verdadeira, ou seja, uma franquia postal de 
� + 1 centavos pode ser obtida usando-se selos de 4 e 5 centavos. . 
 
Se �(�) é verdadeira, então: 
 
Caso 1: Se foi utilizado ao menos um selo de 4 centavos 
Então, podemos trocar este selo por um selo de 5 para formar uma 
franquia de � + 1 centavos. 
 
Caso 2: Se não foi utilizado nenhum selo de 4 centavos 
Então, a franquia de � centavos se formou usando somente selos de 5 
centavos. Como � ≥ 12 , então foi utilizado ao menos três selos de 5 
centavos. Assim, se trocamos três selos de 5 por quatro de 4, então 
formamos uma franquia de � + 1 centavos. 
 
Assim, �(� + 1) é verdadeira. 
 
Por tanto, pelo primeiro princípio da indução matemática concluímos que �(�) 
é verdadeira para todo inteiro positivo � ≥ 12 . 
 
Demonstração utilizando o segundo princípio da indução matemática. 
 
PASSO BASE: As seguintes proposições são verdadeiras: 
�(12): três selos de 4. 
�(13): dois de 4 e um de 5. 
�(14): um de 4 e dois de 5. 
�(15): três de 5. 
 
PASSO DA INDUÇÃO: Supomos que �(12)˄�(13)˄ ⋯ ˄� (�) é verdadeira 
para algum inteiro positivo � ≥ 15 . 
 
Devemos provar que �(� + 1) é verdadeira, ou seja, uma franquia postal de 
� + 1 centavos pode ser obtida usando-se selos de 4 e 5 centavos. . 
 
Para formar uma franquia de � + 1 centavos, podemos usar a franquia de � − 3 
e um selo de 4 centavos. 
 
Assim, �(� + 1) é verdadeira. 
 
Por tanto, pelo segundo princípio da indução matemática concluímos que �(�) 
é verdadeira para todo inteiro positivo � ≥ 12 . 
 
 
3.4. Definições Recorrentes 
 
Às vezes é difícil definir objetos de forma explícita, porem pode ser simples se 
o definimos em termos deles mesmos. Este processo se denomina recursão. 
 
Podemos utilizar a recursão para definir sequências, funções, conjuntos e 
operações. Por exemplo, a sequência das potências de 2 é dada por �(�) = 2�, 
para � = 0, 1, 2, ⋯ Porem, esta sequência se pode definir também definindo o 
primeiro termo da sequência, �(0) = 1, e uma regra para obter um termo da 
sequência a partir da anterior, �(� + 1) = 2�(�), para � = 0, 1, 2, ⋯ 
 
 
Funções definidas recursivamente 
 
Utilizamos dois passos para definir uma função cujo domínio é o conjunto dos 
números naturais ℕ. 
 
PASSO BASE: Especificamos o valor da função em zero. 
 
PASSO RECURSIVO: Proporcionamos uma regra para obter seu valor num 
inteiro a partir dos seus valores em inteiros menores. 
 
Exemplo 1: Suponha que � se define recursivamente como: 
 
�(0) = 3 
�(� + 1) = 2�(�) + 3 
 
Calcule �(1), �(2), �(3) e �(4). 
 
Exemplo 2: Determine uma definição recursiva da função fatorial �(�) = �! 
 
�(0) = 1 
�(� + 1) = (� + 1)�(�) 
 
Exemplo 2: Determine uma definição recursiva de ��, onde � é um número 
real não nulo e � é um número natural. 
 
Como �� = 1 e ���� = ���, então: 
 
�(0) = 1 
�(� + 1) = ��(�) 
 
é uma definição recursiva de ��. 
 
Definição 1: Os números de Fibonacci, �(0), �(1), �(2),⋯ , se definem 
recursivamente da seguinte forma: 
 
�(0) = 0 
�(1) = 1 
�(�) = �(� − 1 ) + �(� − 2) para � = 2, 3, 4, ⋯ 
 
 
Exemplo 5: Calcule os números de Fibonacci �(2), �(3), �(4), �(5) e �(6). 
 
 
Conjuntos definidos recursivamente 
 
De forma similar a definição recursiva de funções, as definições recursivas de 
conjuntos têm duas partes, um passo base e um passo recursivo. No passo 
base se especifica uma coleção inicial de elementos. No passo recursivo se 
proporcionam regras para a formação de novos elementos do conjunto a partir 
dos que já se conhecem. 
 
Exemplo 7: Considere o subconjunto � dos números inteiros definidos por: 
 
PASSO BASE: 3 ∈ �. 
PASSO RECURSIVO: Se � ∈ � e � ∈ �, então � + � ∈ �. 
 
Exemplo 10: Podemos definir o conjunto de formulas bem definidas formadas 
com variáveis proposicionais, operadores lógicos do conjunto {¬, ˄, ˅, →, ↔} e 
os valores � e �. 
 
PASSO BASE: �, � e �, onde � é uma variável proposicional, são formulas 
bem definidas. 
PASSO RECURSIVO: Se � e � são formulas bem definidas, então (¬�), 
(�˄�), (�˅�), (� → �) e (� ↔ �) são formulas bem definidas. 
 
Exemplo 11: Podemos definir de forma recursiva o conjunto das formulas bem 
definidas formadas por variáveis, números e operadores do conjunto {+, −,∗
,/, ^}. 
 
PASSO BASE: � é uma formula bem definida se � é um número ou uma 
variável. 
PASSO RECURSIVO: Se � e � são formulas bem definidas, então (� + �), 
(� − �) , (� ∗ �), (�/�) e (�^�) são formulas bem definidas. 
 
Exemplo 12: Demonstre que o conjunto � definido no Exemplo 7 é o conjunto 
dos inteiros positivos múltiplos de 3. 
 
Seja � = {3� | � ≥ 1} o conjunto dos inteirospositivos múltiplos de 3. Para 
demonstrar que � = � devemos provar que � é um subconjunto de � e que � é 
um subconjunto de �. 
 
Prova de � ⊆ � 
Seja a sentença �(�): 3� ∈ �. Devemos provar que �(�) é verdadeira para todo 
� ≥ 1 . 
 
PASSO BASE: �(1) afirma que 3 × 1 = 3 ∈ � . 
PASSO DA INDUÇÃO: Supomos que �(�) é verdadeira para algum inteiro 
positivo �, isto é, 3� pertence a �. 
 
Devemos provar que �(� + 1) é verdadeira, ou seja, provar que 3(� + 1) ∈ �. 
 
Como 3� ∈ � e 3 ∈ �, da segunda parte da definição recursiva segue que 
3� + 3 = 3(� + 1) ∈ �. Assim, �(� + 1) é verdadeira. 
 
Por tanto, pelo princípio da indução matemática concluímos que �(�) é 
verdadeira para todo � ≥ 1 . 
 
Prova de � ⊆ � 
 
Para esta prova, vamos utilizar a definição recursiva de �. 
 
O passo base da definição especifica que 3 ∈ �. Como 3 = 3 × 1 então 3 ∈ �. 
Para completar a prova, devemos provar que todos os inteiros de � gerados 
usando o passo recursivo pertencem ao conjunto �. Ou seja, considerando as 
premissas: 
Se � ∈ � então � ∈ � 
Se � ∈ � então � ∈ � 
Devemos provar que se � + � ∈ � então � + � ∈ �. 
Pelo passo recursivo, se � ∈ � e � ∈ � então � + � ∈ �. Como � e � são 
múltiplos de 3 então � + � também é múltiplo de 3. Assim, � + � ∈ �. 
 
 
6. Recorrência 
6.1 Relações de Recorrência 
 
A regra que define um elemento em função dos que lhe precedem se denomina 
relação de recorrência. 
 
Definição 1: Uma relação de recorrência para a sequência {�(�) | � ≥ � �} é 
uma equação que determina o elemento �(�) em função dos elementos 
anteriores, isto é, �(0), �(1), ⋯ �(� − 1) , para todo inteiro � ≥ � �, onde �� é 
um inteiro positivo. Uma sequência é uma solução de uma relação de 
recorrência se seus elementos satisfazem a relação para todo inteiro positivo �. 
 
 
Exemplo 2: Determine se a sequência �(�) é solução da relação de recorrência 
�(�) = 2�(� − 1 ) − �(� − 2) para � ≥ 2 , onde �(�) = 3� para � ≥ 1 . 
Responda a mesma pergunta para as sequências �(�) = 2� e �(�) = 5. 
 
Se �(�) = 3�, então para � ≥ 2 
2�(� − 1 ) − � (� − 2 ) = 2�3(� − 1 )�− 3 (� − 2 ) = 3� = �(�). 
Por tanto, a sequência �(�) é solução da relação de recorrência. 
 
Se �(�) = 2�, então �(0) = 1, �(1) = 2 e �(2) = 4. Para � = 2, 
2�(1) − � (0) = 2 × 2 − 1 = 3 ≠ �(2) . 
Por tanto, a sequência �(�) não é solução da relação de recorrência. 
 
Se �(�) = 5, então para � ≥ 2 
2�(� − 1 ) − � (� − 2 ) = 2 × 5 − 5 = 5 = �(�) . 
Por tanto, a sequência �(�) é solução da relação de recorrência. 
 
Exemplo 4: Um casal de coelhos recém-nascidos (um de cada sexo) é solto 
numa ilha. Os coelhos não podem ter descendência até a idade de dois meses. 
Com dois meses de idade, cada casal de coelhos tem como descendência outro 
casal de coelhos a cada mês. Determine uma relação de recorrência para o 
número de casais de coelhos que existirá na ilha depois de � meses, supondo que 
nenhum coelho morre. 
 
Mês Casais 
reprodutores 
Casais 
jovens 
Total de 
casais 
1 0 1 1 
2 0 1 1 
3 1 1 2 
4 1 2 3 
5 2 3 5 
6 3 5 8 
 
 
Seja �(�) o número de casais de coelhos que vivem na ilha depois de � meses. 
 
A população de coelhos pode ser modelada utilizando uma relação de 
recorrência. No final do primeiro mês, o número de casais de coelhos na ilha é 
�(1) = 1. Como o casal não se reproduz durante o segundo mês, então �(2) =
1. Para calcular o número de casais depois de � meses, devemos somar o 
número de casais de coelhos que tinha no mês anterior, �(� − 1) , e o número de 
casais que nascem durante esse mês, que é �(� − 2) , já que somente os coelhos 
com dois meses ou mais podem reproduzir-se. 
 
 
 
Por tanto, a sequência �(�) verifica a relação de recorrência: 
�(�) = �(� − 1 ) + �(� − 2) para � ≥ 3 
junto com as condições iniciais �(1) = 1 e �(2) = 1. 
 
A sequência �(�) é a sequência de Fibonacci. 
 
 
Exemplo 5: [Torre de Hanoi] Considere três barras montadas sobre uma base 
junto com discos de diferentes tamanhos. No inicio do jogo, os discos se 
colocam na primeira barra ordenados de maior a menor. As regras do jogo 
permitem mover os discos de um em um para troca-los de barra, com a restrição 
de que um disco nunca pode ser colocado encima de outro menor. O objetivo do 
jogo é colocar os discos na segunda barra, ordenados com o maior na base. 
 
Seja �(�) o número de movimentos necessários para resolver o problema da 
Torre de Hanoi com � discos. Determine uma relação de recorrência para a 
sequência �(�) . 
 
 
 
 
 
 
 
 
Iniciamos com n discos na primeira barra. Os n − 1 discos superiores se podem 
levar para a terceira barra, seguindo as regras do jogo, realizando H(n − 1) 
movimentos. Durante o processo anterior, o disco maior permaneceu no mesmo 
lugar. A seguir, realizamos um movimento para coloca-lo na posição mais baixa 
da segunda barra. Uma vez feito isto, com outros H(n − 1) movimentos 
podemos levar os n − 1 da terceira barra para a segunda, colocando-os encima 
do maior e terminando assim o jogo. 
 
H(n) = 2H(n − 1 ) + 1 
 
A condição inicial é H(1) = 1, já que um único disco se pode levar da primeira 
barra para a segunda com um único movimento. 
 
Um procedimento iterativo nos mostra uma formula explícita para H(n) . 
 
H(n) = 2H(n − 1 ) + 1 
H(n) = 2(2H (n − 2 ) + 1) + 1 = 2�H(n − 2 ) + 2 + 1 
H(n) = 2�(2H(n − 3 ) + 1) + 2 + 1 = 2�H(n − 3 ) + 2� + 2 + 1 
⋮ 
H(n) = 2���H(1) + 2��� + 2��� + ⋯ + 2 + 1 
H(n) = 2��� + 2��� + 2��� + ⋯ + 2 + 1 
H(n) = 2� − 1 
 
O método iterativo nos proporciona a solução da relação de recorrência H(n) =
2H(n − 1 ) + 1 com a condição inicial H(1) = 1. A demonstração de que esta 
solução é correta pode ser feita utilizando o principio da indução matemática. 
 
 
6.2 Resolução de relações de recorrência 
 
Uma grande variedade de relações de recorrência pode ser resolvida utilizando 
argumentos iterativos. Porem há um tipo especial de relações de recorrência que 
podem ser resolvidas explicitamente. São as relações de recorrência que 
expressam os termos da sequência como uma combinação linear dos termos 
anteriores. 
 
Definição 1: Uma relação de recorrência linear, homogênea de ordem � e com 
coeficientes constantes é da forma: 
�(�) = ���(� − 1 ) + ���(� − 2 ) + ⋯ + � ��(� − �) 
onde ��, ��, …, �� são números reais e �� ≠ 0. 
 
 
 
Exemplo 1: 
a. �(�) = 1.11�(� − 1) é uma relação de recorrência linear e homogênea 
de ordem 1. 
b. �(�) = �(� − 1 ) + �(� − 2) é uma relação de recorrência linear e 
homogênea de ordem 2. 
c. �(�) = �(� − 5) é uma relação de recorrência linear e homogênea de 
ordem 5. 
 
Exemplo 2: 
a. �(�) = �(� − 1 ) + ��(� − 2) não é linear. 
b. � (�) = 2� (� − 1 ) + 1 não é homogênea. 
c. �(�) = ��(� − 1) não tem coeficiente constante. 
 
 
Se �(�) = ��, então �� − � ��
��� − � ��
��� − ⋯ − � ���� − � � = 0, onde � é 
uma constante. Esta equação se denomina equação característica. As soluções 
desta equação são as raízes características. 
 
Teorema 1: Seja �� e �� números reais. Suponha que �
� − � �� − � � = 0 tem 
duas raízes reais distintas �� e ��. Então �(�) = ���(� − 1 ) + ���(� − 2 ) se e 
somente se �(�) = ����
� + ����
� para � ≥ 0 , onde �� e �� são constantes. 
 
Exemplo 3: Qual é a solução da relação de recorrência 
�(0) = 2 
�(1) = 7 
�(�) = �(� − 1 ) + 2�(� − 2 ) � ≥ 2 
 
A equação característica da relação de recorrência é �� − � − 2 = 0 . 
Suas raízes são �� = 2 e �� = −1 . 
Então �(�) = ��2
� + ��(−1)
� 
Utilizando as condições iniciaisobtemos �� = 3 e �� = −1 . 
Por tanto, �(�) = 3 ∙ 2� − (−1 )� � ≥ 0 
 
Exemplo 4: Calcule a solução para a sequência de Fibonacci. 
 
�(0) = 0 
�(1) = 1 
�(�) = �(� − 1 ) + �(� − 2 ) � ≥ 2 
 
A equação característica da relação de recorrência é �� − � − 1 = 0 . 
Suas raízes são �� = (1 + √5)/2 e �� = (1 − √5)/2. 
Então �(�) = �� �
��√�
�
�
�
+ �� �
��√�
�
�
�
 
Utilizando as condições iniciais obtemos �� = 1/√5 e �� = −1/ √5. 
Por tanto, �(�) =
�
√�
�
��√�
�
�
�
−
�
√�
�
��√�
�
�
�
 � ≥ 0 
 
Teorema 2: Seja �� e �� números reais tal que �� ≠ 0. Suponha que �
� − � �� −
�� = 0 tem uma única raiz ��. Então �(�) = ���(� − 1 ) + ���(� − 2 ) se e 
somente se �(�) = ����
� + �����
� para � ≥ 0 , onde �� e �� são constantes. 
 
Exemplo 5: Qual é a solução da relação de recorrência 
�(0) = 1 
�(1) = 6 
�(�) = 6�(� − 1 ) − 9� (� − 2 ) � ≥ 2 
 
A equação característica da relação de recorrência é �� − 6� + 9 = 0 . 
Sua única raiz é �� = 3. 
Então �(�) = ��3
� + ���3
� 
Utilizando as condições iniciais obtemos �� = 1 e �� = 1. 
Por tanto, �(�) = 3� + �3� � ≥ 0 
 
Teorema 3: Seja ��, ��, …, �� números reais. Suponha que �
� − � ��
��� − ⋯ −
�� = 0 tem � raízes reais distintas ��, ��, …, �� . Então �(�) = ���(� − 1 ) +
���(� − 2 ) + ⋯ + � ��(� − �) se e somente se �(�) = ����
� + ����
� + ⋯ +
����
� para � ≥ 0 , onde ��, ��, …, �� são constantes. 
 
 
Exemplo 6: Determine a solução da relação de recorrência 
�(0) = 2 
�(1) = 5 
�(2) = 15 
�(�) = 6�(� − 1 ) − 11� (� − 2 ) + 6�(� − 3) � ≥ 3 
 
A equação característica da relação de recorrência é �� − 6� � + 11� − 6 = 0 . 
Suas raízes são �� = 1, �� = 2 e �� = 3. 
Então �(�) = ��1
� + ��2
� + ��3
� 
Utilizando as condições iniciais obtemos �� = 1, �� = −1 e �� = 2. 
Por tanto, �(�) = 1 − 2 � + 2 ∙ 3� � ≥ 0 
 
 
Relações de Recorrência Linear e Não-Homogênea com Coeficientes 
Constantes 
 
Uma relação de recorrência linear e não-homogênea com coeficientes constantes 
é da forma: 
�(�) = ���(� − 1 ) + ���(� − 2 ) + ⋯ + � ��(� − � ) + �(�) 
onde ��, ��, …, �� são números reais e �(�) é uma função não nula. 
 
 
Teorema 5: Seja ��, ��, …, �� números reais. Se ��(�) é uma solução particular 
da relação de recorrência linear não-homogênea com coeficientes constantes 
�(�) = ���(� − 1 ) + ���(� − 2 ) + ⋯ + � ��(� − � ) + �(�) então toda 
solução é da forma �(�) = ��(�) + ��(�), onde ��(�) é uma solução de 
�(�) = ���(� − 1 ) + ���(� − 2 ) + ⋯ + � ��(� − � ) para � ≥ 0 . 
 
 
Exemplo 10: Qual é a solução da relação de recorrência 
�(1) = 6 
�(�) = 3�(� − 1 ) + 2� � ≥ 2 
 
Solução homogênea: 
A relação de recorrência linear homogênea é �(�) = 3�(� − 1 ). Suas soluções são 
��(�) = �3
�, onde � é uma constante. 
 
Solução particular: 
Como �(�) = 2�, então vamos supor que ��(�) = �� + �, onde � e � são 
constantes. Substituindo na relação de recorrência linear não-homogênea 
obtemos: 
�� + � = 3(�(� − 1 ) + �) + 2� 
Simplificando obtemos (2 + 2�)� + (2� − 3� ) = 0. Assim, � = −1 e � =
−3/2 . Logo, ��(�) = −� − 3/2 . 
 
Todas as soluções são da forma: �(�) = −� −
�
�
+ �3�. 
Utilizando a condição inicial obtemos � = 11/6. 
Por tanto, �(�) = −� −
�
�
+
��
�
3� para � ≥ 1 . 
 
Exemplo 11: Determine todas as soluções da relação de recorrência 
�(�) = 5�(� − 1 ) − 6�(� − 2) + 7 � � ≥ 2 
 
Solução homogênea: 
A relação de recorrência linear homogênea é �(�) = 5�(� − 1 ) − 6�(� − 2) . Suas 
soluções são ��(�) = ��3
� + ��2
�, onde �� e �� são constantes. 
 
Solução particular: 
Como �(�) = 7�, então vamos supor que ��(�) = � ∙ 7
�, onde � é uma 
constante. Substituindo na relação de recorrência linear não-homogênea 
obtemos: 
� ∙ 7� = 5� ∙ 7��� − 6� ∙ 7��� + 7� 
Simplificando obtemos 49� = 35� − 6� + 49 . Assim, � = 49/20. Logo, 
��(�) = (49/20)7
�. 
 
Por tanto, todas as soluções são da forma: �(�) = ��3
� + ��2
� + (49/20)7�.