IFMG Campus Formiga Matemática Discreta

Notas de Aula 2: Métodos de Prova

Prof. Diego Mello 2o. Semestre 2012

Sumário

1 Introdução 2

2 Conceitos 2

3 Teoremas 4

4 Métodos de Prova 64.1 Prova Direta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64.2 Prova por Contraposição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94.3 Prova por Contradição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.4 Prova por Equivalência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.5 Prova por Contra-Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.6 Prova por Divisão em Casos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.7 Prova por Exaustão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.8 Provas Existenciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.9 Prova de Unicidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.10 Outros Métodos de Prova . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5 Resumo: Técnicas de Prova 27

6 Exercícios de Fixação 29

1

1 Introdução

Este documento contém as notas de aula sobre o tema ‘Métodos de Prova’ da disciplina de Mate-mática Discreta do curso de Ciência da Computação do Insituto Federal de Minas Gerais - CampusFormiga. Ela é baseada no conteúdo dos livros referenciados neste documento.

Este documento serve apenas como referência para acompanhamento das aulas, e não substitui anecessidade de leitura e estudo da bibliografia oficial do curso. Muitos dos exemplos, tabelas ediagramas contidos no documento foram extraídos e/ou adaptados dos livros contidos na seção dereferências bibliográficas.

2 Conceitos

Uma prova é um argumento válido que estabelece a verdade de uma declaração matemática.

Uma prova pode utilizar (i) as hipóteses de um teorema, (ii) axiomas ou (iii) teoremas previamenteprovados como ingredientes que, em conjunto com regras de inferência, estabelecem a verdade dadeclaração que está sendo demonstrada.

Um teorema é uma sentença que pode ser demonstrada como verdadeira. Um teorema pode ser aquantificação universal de uma declaração condicional com uma ou mais hipóteses, e uma conclu-são. Uma definição alternativa diz que um teorema é uma afirmação específica que pode ser provada.

Alguns teoremas são mais importantes ou menos importantes que os outros; daí existem designaçõesalternativas que os matemáticos usam no lugar de teorema. Por exemplo, o teorema de Pitágorasmerece ser chamado de teorema em função de sua importância na geometria. A afirmação ‘o qua-drado de um inteiro par é também um inteiro par ’ também é um teorema, mas talvez não mereçauma designação deste nível. Outra afirmação, ‘3 + 9 = 12’ é também um teorema, mas não temtanto prestígio para usar essa designação.

Por isso, teoremas podem adotar outras nomenclaturas. Teoremas também podem ser chamados defatos, resultados, lemas, proposições, corolários e alegações. Descreveremos brevemente no decorrerdesta seção algumas situações em que as designações alternativas são empregadas.

Um resultado é uma declaração modesta, genérica para um teorema. Um fato é um teorema deimportância bastante limitada, tal como ‘6+3 = 9’. Uma proposição é um teorema de importânciasecundária, mais importante que um fato porém com menos prestígio que um teorema.

Um teorema é demonstrado ser verdadeiro por meio de uma prova. Uma prova pode conter comodeclarações os axiomas, as premissas do teorema (se houverem), e outros teoremas já demonstradosanteriormente.

Um axioma ou postulado é uma sentença ou proposição que não é provada ou demonstrada, masé considerada óbvia e aceita como verdade na construção de deduções e inferências. Como exemplo,

2

a Tabela 1 apresenta uma série de axiomas úteis sobre os números reais; alguns também se aplicamao conjunto dos números inteiros.

Tabela 1: Tabela de Axiomas sobre os Números Reais

Axioma DeclaraçãoFecho Aditivo Para todo número real x e y, x+ y é um número realFecho multiplicativo Para todo número real x e y, x · y é um número realAssociatividade Aditiva Para todo número real x, y e z, (x+ y) + z = x+ (y + z)

Associatividade Multiplicativa Para todo número real x, y e z, (x · y) · z = x · (y · z)Comutatividade Aditiva Para todo número real x e y, x+ y = y + x

Comutatividade Multiplicativa Para todo número real x e y, x · y = y · xIdentidade Aditiva Para todo número real x, x+ 0 = 0 + x = x

Identidade Multiplicativa Para todo número real x, x · 1 = 1 · x = x

Elemento IdentidadeA identidade aditiva 0 e a identidade multiplicativa 1 sãodistintas, i.e., 0 6= 1

Lei Inversa para AdiçãoPara todo número real x, existe um número real −x (inversoaditivo de x) tal que x+ (−x) = (−x) + x = 0

Lei Inversa para MultiplicaçãoPara todo número real x, existe um número real x−1 = 1

x

(inverso multiplicativo de x) tal que x · ( 1x) = ( 1

x) · x = 1

Lei DistributivaPara todos os números reais x, y e z, x · (y+z) = x ·y+x ·z,e (x+ y) · z = x · z + y · z.

Lei da TricotomiaPara todos os números reais x e y, exatamente uma dascondições x = y, x < y ou x > y é verdadeira

Lei da TransitividadePara todos os números reais x, y e z, se x > y e y > z, entãox > z

Lei da Compatibilidade Aditiva Para todos os números reais x, y e z, se x > y, x+ z > y+ z

Lei da Compatibilidade Multipli-cativa

Para todos os números reais x, y e z, se x > y e z > 0,x · z > y · z

Uma definição é uma sequência de palavras que expressa o significado de uma expressão. Definiçõessão elementos essenciais na dedução sobre a verdade de um teorema. Para exemplificar, segue aDefinição 1, sobre o significado de um número ser primo no conjunto dos números inteiros.

Definição 1 (Primalidade). Um número primo é um número inteiro n > 1 tal que n não édivisível por nenhum inteiro além de 1 e n.

Teoremas menos importantes que são úteis na prova de outros resultados são denominados de le-mas. Provas mais complicadas tornam-se fáceis de compreender quando são provadas usando umasérie de lemas, onde cada lema é provado separadamente, decompondo o teorema em partes meno-res. Os lemas são as partes (instrumentos) usados para provar teoremas complexos.

Uma alegação é análoga ao lema. Alegações são afirmações que aparecem dentro da prova de umteorema. A função de uma alegação é organizar os passos-chave da prova. A formulação de uma

3

alegação pode envolver termos que só fazem sentido no contexto da prova.

Um corolário é um teorema que pode ser estabelecido diretamente a partir de um teorema que foiprovado. O corolário é uma decorrência imediata de um teorema. É um resultado com uma provarápida.

Exemplo:O Teorema de Pitágoras afirma que a2 = b2 + c2, onde a é a diagonal do triângulo retângulo, e be c são os catetos opostos e adjacentes do triângulo retângulo. A diagonal de um quadrado cujoslados medem l unidades é l

√2; tal declaração é um corolário do Teorema de Pitágoras. ◭

Uma conjectura é uma declaração em que propõem-se ser verdadeira, geralmente com base emalguma evidência parcial, argumento heurístico ou intuição de um especialista. Quando a provade uma conjectura é encontrada, a declaração correspondente torna-se um teorema; obviamente, seuma conjectura é provada ser falsa, ela não é um teorema. Enfim, uma conjectura é uma proposiçãoque ainda não foi provada nem refutada.

Exemplo:Conjectura de Goldbach: ∀n, se n é par, ∃a, b tal que a e b são primos e a+ b = n.

A conjectura de Goldbach é uma das mais antigas conjecturas de teoria dos números. Segundo[Loureiro, A. A. F.], até novembro de 2010 ela foi verificada para números até 2× 1018 por meio deprogramas de computador. O último resultado publicado1 em Setembro de 2012 atingiu númerosverificados até 3× 1017.

Embora tenha sido verificada para números até 3×1017, não significa que a conjectura é verdadeirapara números entre 3× 1017 e ∞. ◭

3 Teoremas

Resultados matemáticos são geralmente expressos como teoremas da forma ‘se p, então q’, ou p → q.onde p e q podem representar sentenças compostas. Em teoremas expressos desta forma, tentamosdeduzir q de p a partir de axiomas, regras de inferência, definições e resultados já provados.

Se for possível usar na dedução apenas axiomas (i.e., sentença assumida verdadeira), então o teo-rema é verdadeiro. No entanto, muitas vezes desejamos demonstrar teoremas sobre um tema emparticular (ex: algoritmos de grafos, algebra booleana, teoria de compiladores, programação linearou outros temas). Neste casos, usamos como premissas fatos sobre o assunto em questão (comodefinições e resultados previamente provados) em conjunto com axiomas e regras de inferência para

1Ver novidades em http://www.ieeta.pt/~tos/goldbach.html

4

deduzir q de p a partir de uma sequência lógica de passos que começam em p e terminam em q.

Exemplo:Provar o teorema: ‘se um inteiro é divisível por 6, então ele também é divisível por 3’.

Para efetuar a prova, devemos usar uma série de axiomas, fatos e definições para mostrar que ahipótese ‘x é divisível por 6’ (p) leva à conclusão ‘x é divisível por 3’ (q).

Podemos partir da definição de divisibilidade: um inteiro a é divisível por um inteiro b se a forigual ao produto de um inteiro k por b, ou seja, a = k · b. Apresentaremos os passos envolvidos nademonstração do teorema.

Hipótese: x é divisível por 6

x = k · 6 para algum inteiro k (Definição de divisibilidade)6 = 2 · 3 (Fato numérico)x = k(2 · 3) (Substituição)x = (k · 2)3 (Axioma da associabilidade multiplicativa)x = (k · 2)

︸ ︷︷ ︸

inteiro

3 (Fato: × é fechada sobre os inteiros)

Conclusão: x é divisível por 3

Demonstramos através de uma sequência de axiomas, definições e fatos matemáticos que a hipótese‘x é divisível por 6’ leva à conclusão ‘x é divisível por 3’, logo o teorema apresentado foi provadoser verdadeiro. Este tipo de prova é denominada de prova direta, e será abordada mais adiante. ◭

A maioria das afirmações em matemática são universais; assim, um teorema pode conter um resul-tado sobre todos os objetos do domínio de interpretação. Neste caso, a expressão formal do teoremacomeçará com pelo menos um quantificador universal, na forma ∀x ∈ D(P (x) → Q(x) que pode serescrito informalmente como P (x) → Q(x).

Quando D é um conjunto finito, ou existe um número finito de valores x que satisfazem a propri-edade P (x), uma possível forma de provar a afirmação consiste no uso do método de exaustão,onde a afirmação é provada verdadeira desde que mostre ser verdadeira para cada um dos elementosda coleção finita. Veja o exemplo a seguir:

Exemplo:[Adaptado de [Loureiro, A. A. F.]] ∀n ∈ Z, se n é par e 4 ≤ n ≤ 30, então n pode ser escrito comoa soma de dois números primos.

Podemos mostrar a verdade desta declaração enumerando todos os números pares entre 4 e 30,decompondo-os em uma soma de dois números primos. Listando-os, teremos

5

4 = 2 + 2 6 = 3 + 3 8 = 3 + 5 10 = 5 + 512 = 5 + 7 14 = 3 + 11 16 = 5 + 11 18 = 7 + 1120 = 7 + 13 22 = 5 + 17 24 = 5 + 19 26 = 7 + 1928 = 11 + 17 30 = 11 + 19

Através da enumeração de todos os elementos do domínio x ∈ Z|4 ≤ x ≤ 30 mostramos que aafirmação é verdadeira. ◭

Entretanto, o método da exaustão é pouco prático quando o domínio D é muito grande ou nãofinito. Podemos nestes casos utilizar o método da generalização para mostrar a verdade de umaafirmação.

A única forma para a sentença P (x) → Q(x) ser falsa é P (x) ser verdadeira e Q(x) ser falsa. Paramostrar que (Px) → Q(x) é verdadeira suponha que P (x) é verdadeira e mostre que Q(x) tambémdeve ser verdadeira. Para mostrar que ∀x ∈ D(P (x) → Q(x)) é verdadeiro, suponha que c é umelemento específico mas escolhido arbitrariamente do domínio D, e mostre que c satisfaz a propri-edade P (c) → Q(c). Se provarmos P (c) → Q(c) para um elemento arbritrário c, então teremosprovado ∀x ∈ D(P (x) → Q(x)).

Esta generalização funciona devido ao uso da regra de generalização da lógica de predicados, apre-sentada nas notas de aula sobre lógica.

4 Métodos de Prova

A construção de provas é uma tarefa complexa e difícil. No entanto, existem alguns métodos de semostrar que a declaração condicional P (x) → Q(x) é verdadeira a partir da lógica. Dentre eles estãoa prova direta, a prova por contraposição, a prova por contradição, a prova por contra-exemplo ea prova por divisão de casos. Entender a mecânica destes métodos é a chave para aprender a ler econstruir provas matemáticas.

Uma vez escolhido o método de prova, empregamos axiomas, definições de termos, resultados previ-amente provados e regras de inferência para completar a prova. As próximas seções irão apresentara idéia central de cada método, exemplificando sua aplicação.

4.1 Prova Direta

A prova direta de uma declaração condicional p → q consiste em provar que a declaração p → qé verdadeira mostrando que, se p é verdadeiro, então q também deve ser verdadeiro tal que a com-binação de p verdadeiro e q falso nunca ocorrerá.

A prova direta de uma declaração condicional p → q é construída quando:

• o primeiro passo consiste na consideração de que p é verdadeiro;

6

• os passos subsequentes são construídos através de axiomas, definições, resultados provados eregras de inferência;

• o último passo mostra que q também deve ser verdadeiro.

Em uma prova direta, assumimos que p é verdadeiro e usamos axiomas, definições e resultados pro-vados, juntamente com regras de inferência para provar que q também é verdadeiro. Provas diretaslevam das premissas do teorema até a conclusão. Elas começam com as premissas, continuam coma sequência de deduções e finalizam com a conclusão.

Em [Loureiro, A. A. F.] é apresentado um método para construir provas diretas, cuja adaptação éapresentada a seguir, no Algoritmo 1.

Algoritmo 1 Construção de uma prova direta1: Expresse a declaração a ser provada na forma ∀x ∈ D, se P (x), então Q(x)2: Comece a prova supondo que x é um elemento específico de D escolhido abritrariamente para

o qual P (x) é V.3: Mostre que Q(x) é V usando axiomas, definições, resultados anteriores e regras de inferência

Alguns exemplos de prova direta serão apresentados a seguir. Definições serão apresentadas ondehouver necessidade.

Definição 2 (Paridade). Um inteiro n é par se existir algum inteiro k tal que n = 2k, e n é ímpar

se existir algum inteiro k tal que n = 2k+1. Dois inteiros tem a mesma paridade quando ambossão pares ou quando ambos são ímpares; eles tem a paridade oposta quando um é par e o outro éímpar.

Teorema 1. Se n é um inteiro ímpar, então n2 é ímpar.

Prova Direta. O teorema declara que ∀n(P (n) → Q(n)), onde P (n) é ‘n é um inteiro ímpar’ e Q(n)é ‘n2 é ímpar’. Para mostrar a prova direta deste teorema, vamos assumir que a hipótese destadeclaração condicional é verdadeira, ou seja, assumimos que n é ímpar. Pela Definição 2, temos quen = 2k + 1, para um inteiro k. Queremos mostrar que n2 também é ímpar. Elevando ambos ostermos da equação n = 2k + 1 ao quadrado, obtém-se a equação

n2 = (2k + 1)2

que expressa o valor de n2. Desenvolvendo o termo à direita, temos

n2 = 4k2 + 4k + 1

n2 = 2 (2k2 + 2k)︸ ︷︷ ︸

t

+1

Pela Definição 2 temos que quando n é ímpar, n2 também é ímpar

7

Teorema 2 ([Loureiro, A. A. F.]). Se a e b são inteiros, então 6a2b é par.

Prova Direta. Pela Definição 2, um inteiro n é par quando n = 2k. Considere n = 6a2b e k = 3a2b.Como as operações de +, − e × entre inteiros resultam em inteiros, temos que 3a2b é um inteiro, e6a2b é o dobro de 3a2b. Assim, 6a2b

︸︷︷︸

n

= 2(3a2b︸︷︷︸

k

). Concluímos que 6a2b é par.

Definição 3 (Quadrado Perfeito). Um inteiro a é um quadrado perfeito se houver um inteiro btal que a = b2.

Teorema 3. Se m e n são quadrados perfeitos, então n ·m é também um quadrado perfeito.

Prova Direta. Para produzir a prova direta deste teorema, vamos assumir que a hipótese é verda-deira (no caso, que ambos números n e m são ambos quadrados perfeitos). Pela Definição 3 temosque existem dois números, r e s tais que n = r2 e m = s2. O objetivo da prova é mostrar quen ·m é também um quadrado perfeito; faremos isso substituindo os valores r2 e s2 no produto n ·m.Assim,

n ·m = r2 · s2

n ·m = rr · ssn ·m = (rr)(ss)

n ·m = (rs)(rs)

n ·m = (rs)2

Logo, n ·m é o quadrado de rs, um número inteiro. Pela Definição 3, temos que o produto n ·m étambém um quadrado perfeito.

Teorema 4 ([Loureiro, A. A. F.]). Se a soma de dois números inteiros é par, então a sua diferençatambém é par (linguagem natural). ∀ inteiros n e m, se n+m é par, então n−m é par (linguagemformal).

Prova Direta. Suponha m e n inteiros tal que m+ n seja par. Pela Definição 2, m+ n = 2k, paraalgum inteiro k. Subtraindo-se uma quantidade n de ambos os lados da igualdade m + 2 = 2k,teremos

m+ n− n = 2k − n

m = 2k − n

Usando este resultado, podemos expressar a diferença entre m e n como

m− n = (2k − n)︸ ︷︷ ︸

m

−n

m− n = 2k − 2n

m− n = 2 (k − n)︸ ︷︷ ︸

t

onde t = (k− n) é um inteiro que, multiplicado por 2, resulta em um inteiro par. Logo, a diferençaentre dois inteiros m e n cuja soma é par é um inteiro par.

8

4.2 Prova por Contraposição

Provas de teoremas da forma ∀x(P (x) → Q(x)) que não começam com as premissas e terminamcom a conclusão são também possíveis; dá-se a este tipo de prova a denominação de prova indireta.Se você falha em provar uma conjectura através de prova direta, mas tem o sentimento de que ela éverdadeira, poderá empregar algum dos métodos de prova indireta para realizar tal demonstração.

Um tipo de prova indireta é aquela conhecida como prova por contraposição, que faz uso defatos onde a declaração condicional (p → q) é verdadeira quando a sua contrapositiva (¬q → ¬p)também é verdadeira. Este resultado advém da tautologia [(¬q → ¬p) → (p → q)]. Para deixaristo claro, verifique a tabela verdade apresentada na Tabela 2, que mostra os valores verdades dadeclaração condicional, sua contrapositiva e da tautologia correspondente.

Tabela 2: Tabela verdade para as proposições (p → q), (¬q → ¬p) e [(¬q → ¬p) → (p → q)]p q ¬p ¬q (p → q) (¬q → ¬p) (¬q → ¬p) → (p → q)

0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 0 0 1 1 1

Na prova contrapositiva, provamos uma declaração condicional do tipo (p → q) aplicando a provadireta sobre sua contrapositiva (¬q → ¬p), mostrando que ela é verdadeira quando (¬q) e (¬p)forem verdadeiras. A prova por contraposição de uma declaração condicional p → q é construídaquando:

• o primeiro passo consiste em considerar a premissa (¬q) da contrapositiva verdadeira;

• os passos subsequentes são construídos através de axiomas, definições, resultados provados eregras de inferência;

• o último passo consiste em mostrar que a conclusão (¬p) da contrapositiva segue dos passosanteriores.

O Algoritmo 2 (adaptado de [Loureiro, A. A. F.]) apresenta alguns passos que podem ser seguidosna construção de uma prova por contraposição.

Algoritmo 2 Construção de uma prova por contraposição1: Escreva a declaração a ser provada na forma ∀x ∈ D, se P (x), então Q(x)2: Reescreva a declaração na forma contrapositiva: ∀x ∈ D, se ¬Q(x), então ¬P (x)3: Prove o contrapositivo (¬q → ¬p) por prova direta4: (a) Suponha x um elemento específico, escolhido de forma arbitrária de D tal que ¬Q(x) é V5: (b) Mostre que ¬P (x) é V

A seguir serão apresentados alguns exemplos de prova de teoremas por meio do método de provapela contrapositiva.

9

Teorema 5. Se n é um inteiro e 3n+ 2 é ímpar, então n é ímpar.

Prova Direta. Assuma que 3n+2 é um inteiro ímpar. Da Definição 2, 3n+ 2 = 2k +1 para algumvalor de k inteiro. Da expressão resultante 3n + 1 = 2k parece não haver uma forma direta de seconcluir que n é ímpar. Aqui, a tentativa de prova direta falha.

Prova por Contraposição. A primeira coisa que necessitamos fazer é identificar a hipótese e conclu-são da declaração condicional nas formas direta e contrapositiva. Isto posto, temos:

p : ‘3n+ 2 é ímpar’q : ‘n é ímpar’

¬p : ‘3n+ 2 é par’¬q : ‘n é par’

O próximo passo deste método consiste em assumir que a conclusão q é falsa, ou seja, ¬q é verda-deira. Neste caso, assumimos que ¬q : ‘n é par’ é verdade. Este é o ponto de partida da prova.Por meio de prova direta, devemos partir de ¬q e usar axiomas, definições e resultados previamenteprovados para mostrar que se ¬q é verdadeiro, então ¬p também deve ser verdadeiro.

Pela definição de paridade (Definição 2), n = 2k para algum inteiro k. Substituindo 2k por n, temos

3n+ 2 = 3(2k) + 2

3n+ 2 = 6k + 2

3n + 2 = 2 (3k + 1)︸ ︷︷ ︸

t

onde t = 3k + 1 é um inteiro que, multiplicado por 2, resulta em um inteiro par. Pela Definição 2temos que 3n+ 2 é par. Observe que ‘3n+ 2 é par’ consiste justamente na negação da hipótese doteorema original, ou seja, a partir de ¬q chegamos à ¬p.

Se ¬q leva à ¬p, então a sentença (¬q → ¬p) é verdadeira. Por equivalência, a sentença (p → q)também é verdadeira. Logo, demonstramos que ‘se 3n+ 2 é ímpar, então n é ímpar’.

Teorema 6. Para todo número real positivo x e y, se o produto xy excede 25, então x > 5 ou y > 5.

Prova por Contraposição. Identificando a premissa e conclusão da sentença original e sua contra-positiva. Temos

p : ‘xy excede 25’q : ‘x > 5 ou y > 5’ (r ∨ s)

¬p : ‘xy não excede 25’¬q : ‘0 < x ≤ 5 e 0 < y ≤ 5’ DeMorgan: ¬(r ∨ s) ≡ (¬r ∧ ¬s)

Consideramos a negação da conclusão do teorema, ou seja, consideramos verdade que 0 < x ≤ 5 e0 < y ≤ 5. Sob tais circunstâncias, encontramos que o produto xy é limitado por 0 < xy < 5 · 5,ou seja, 0 < xy ≤ 25. Em outras palavras, o produto xy não excede 25, que corresponde à sentença¬p. Assim, ¬q leva à ¬p, (¬q → ¬p) é verdadeira e, consequentemente, a o teorema (p → q) éverdadeiro.

10

Teorema 7. Se n = ab, com a e b inteiros positivos, então a ≤ √n ou b ≤ √

n.

Prova por Contraposição. Identificando as premissas e conclusões da forma direta e contrapositivado teorema:

p : ‘n = ab’q : ‘(a ≤ √

n) ou (b ≤ √n)’ (r ∨ s)

¬p : ‘n 6= ab’¬q : ‘(a >

√n) e (b >

√n)’ DeMorgan: ¬(r ∨ s) ≡ (¬r ∧ ¬s)

Para provar o teorema original pela sua forma contrapositiva, devemos assumir que ¬q é verdadeiro.

Seja r : (a ≤ √n) e s : (b ≤ √

n). Logo, q pode ser substituído por (r ∨ s), e (¬q) pode sersubstituído por ¬(r∨ s). Uma das equivalências lógicas mais importantes consiste em uma das Leisde DeMorgan, que declara que ¬(r ∨ s) ≡ (¬r ∧ ¬s). Logo, a sentença (¬q) pode ser substituídapela equivalência lógica (¬r ∧ ¬s).

Nesta demonstração, a declaração (¬r ∧ ¬s) pode ser traduzida como (a >√n) e (b >

√n).

Estamos interessados em mostrar que n 6= ab. Podemos fazer isso multiplicando ambas as quanti-dades a e b, obtendo a · b > √

n · √n, ou seja, ab > n. Logo, ab 6= n, ou seja, chegamos em ¬p.

Demonstramos que ¬q leva à ¬p, então (¬q → ¬p) é verdadeira, de forma que o teorema (p → q)também é verdadeiro.

Teorema 8. Se um inteiro x é divisível por 6, então x também é divisível por 3

Prova por Contraposição. Seja p : ‘um inteiro x é divisível por 6’ e q : ‘um inteiro x é divisível por 3’.Na prova contrapositiva, o teorema (p → q) é demonstrado pela prova direta da sua contrapositiva,isto é, (¬q → ¬p). O enunciado deste teorema na forma contrapositiva passa a ser ‘se um inteiro xnão é divisível por 3, então x não é divisível por 6’. A demonstração da prova é dada a seguir.

Hipótese: x não é divisível por 3

x 6= k · 3 para algum inteiro k (Negação da divisibilidade por 3)x 6= (2k1) · 3 k é igual a um inteiro 2k1x 6= k1(2 · 3) (Axioma da associabilidade multiplicativa)x 6= k1 · 6 para algum inteiro k1 (Fato)

Conclusão: x não é divisível por 6

Teorema 9 ([Loureiro, A. A. F.]). Dado qualquer inteiro n, se n2 é par, então n é par.

11

Prova por Contraposição. Vamos identificar as premissas e conclusões do teorema e da sua formacontrapositiva:

p : ‘n2 é par’q : ‘n é par’

¬p : ‘n2 não é par’¬q : ‘n não é par’

Partimos da declaração ¬q, ou seja, assumimos que n não é par. Oras, se n não é par, então n éímpar (ver Definição 2). Se n é ímpar, então n = 2k + 1 para algum inteiro k.

O produto de n por n é, dessa forma, expresso por (2k + 1)(2k + 1) = (2k + 1)2. Desenvolvendo aexpressão, temos

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

n2 = (2k + 1)2

n2 = 4k2 + 4k + 1

n2 = 2 (2k2 + 2k)︸ ︷︷ ︸

t

+1

Pela definição de paridade (Definição 2) temos que, assumindo n ímpar, n2 é ímpar, ou seja, partindode ¬q chegamos a ¬p. Logo, a declaração condicional (¬q → ¬p) é verdadeira, e o teorema (p → q)também é verdadeiro.

4.3 Prova por Contradição

Outra forma de provar uma declaração condicional do tipo (p → q) consiste na prova por contra-dição. Na prova por contradição, o teorema (p → q) é demonstrado de maneira indireta.

Neste tipo de prova, assumimos que a declaração ∀x ∈ D(P (x) → Q(x)) é falsa, isto é, p → q é falsapara pelo menos uma substituição de x do domínio D. Existe algum elemento x do domínio D parao qual P (x) é verdadeiro e Q(x) é falso. Em linguagem lógica, partimos de (p ∧ ¬q) e deduzimosque (p ∧ ¬q) leva à uma contradição.

Usamos a verdade de (p∧¬q) para derivar uma contradição, isto é, uma sentença que sempre resultaem falso. Uma vez que uma contradição seja obtida, provamos a verdade do teorema (p → q), pois[(p ∧ ¬q) → 0] → (p → q) é uma tautologia, onde (p → q) equivale à [(p ∧ ¬q) → 0] (ver Tabela 3).

Tabela 3: Tabela verdade para as proposições (p → q), [(p ∧ ¬q) → 0] e [(p ∧ ¬q) → 0] → (p → q)p q ¬q (p ∧ ¬q) (p ∧ ¬q) → 0 (p → q) [(p ∧ ¬q) → 0] → (p → q)

0 0 1 0 1 1 10 1 0 0 1 1 11 0 1 1 0 0 11 1 0 0 1 1 1

12

Como vimos, a forma (p∧¬q) é útil para provar declarações condicionais na forma (p → q). Existeainda uma outra forma de provar uma declaração na forma p por contradição, usando a sentença¬p → (r ∧ ¬r).

Nesta forma, a demonstração começa considerando que p é falso, ou seja, ¬p é verdadeiro, e usamosaxiomas, definições e resultados já provados para deduzir que ¬p leva à alguma contradição do tipo(r ∧ ¬r) para alguma proposição r. Oras, se afirmar que a declaração p é falsa leva à uma con-tradição, então a declaração p é verdadeira pois [(¬p → (r∧¬r)] → p é uma tautologia (ver Tabela 4).

Tabela 4: Tabela verdade para as proposições [¬p → (r ∧ ¬r)] e [¬p → (r ∧ ¬r)] → pp r ¬p ¬r (r ∧ ¬r) [¬p → (r ∧ ¬r)] [¬p → (r ∧ ¬r)] → p

0 0 1 1 0 0 10 1 1 0 0 0 11 0 0 1 0 1 11 1 0 0 0 1 1

O Algoritmo 3 apresentado a seguir foi adaptado de [Loureiro, A. A. F.], e apresenta alguns princí-pios para construir provas por contradição.

Algoritmo 3 Construção de uma prova por contradição1: Suponha que a declaração a ser provada é falsa2: Mostre que esta declaração leva logicamente à uma contradição3: Conclua que a afirmação a ser provada é verdadeira

Para finalizar, vimos nesta sub-seção que um teorema ou sentença pode ser demonstrado através daprova por contradição. Duas formas foram apresentadas, uma para declarações na forma p e outrapara declarações na forma (p → q). Nos exemplos de demonstração por contradição apresentadosneste documento procuraremos destacar a forma escolhida para se mostrar a contradição e, destaforma, demonstrar a verdade sobre a sentença ou teorema enunciado.

Definição 4 (Números Racionais e Irracionais). Um número real r é racional se existem inteirosp e q com q 6= 0 tal que r = p/q. Um número real que não é racional é denominado irracional.

Teorema 10. O número√2 é um número irracional.

Prova por Contradição. Seja p a proposição ‘√2 é um número irracional’. Para demonstrar a ver-

dade desta sentença, usaremos a prova por contradição na forma ¬p → (r ∧ ¬r). Suponha que ¬pé verdadeiro, ou seja, ‘

√2 não é um número irracional’. Se

√2 não é irracional, logo

√2 é racional.

13

Se√2 é racional, segundo a Definição 4 existem inteiros a e b tal que

√2 = a/b, onde b 6= 0 e a e

b não possuem fatores em comum, i.e., a/b é o menor termo desta relação. Aplicando o quadrado àambos os lados da expressão

√2 = a/b, obtemos:

(√2)2

=(a

b

)2

2 =a2

b2

2b2 = a2

Esta última expressão mostra que, pela definição de paridade (Definição 2), o número a2 é umnúmero par. Segundo o Teorema 9, se a2 é par, então a também é par. Logo a pode ser escrito daforma a = 2k, para algum inteiro k. Substituindo o termo a na expressão já desenvolvida, temos:

2b2 = a2

2b2 = (2k)2

2b2 = 4k2

Dividindo ambos os termos da igualdade por 2, temos:

b2 = 2k2

Acabamos de concluir que b2 é par (Definição 2). Oras, se b2 é par, b também é par (Teorema 9).

A hipótese usada nesta demonstração assumiu que√2 é um número racional, ou seja,

√2 = a/b,

onde a e b não possuem fatores em comum. Porém, deduzimos da Definição 2 e Teorema 9 que osnúmeros a e b são pares, logo o número 2 divide a e b.

Seja r : ‘2 divide os inteiros a e b’, e ¬r : ‘os inteiros a e b não possuem fatores em comum’. Adedução partindo da hipótese ¬p levou à contradição (r ∧ ¬r).

Isto é suficiente para concluir que a sentença p : ‘√2 é um número irracional’ é verdadeira.

Teorema 11 ([Loureiro, A. A. F.]). Não existe um inteiro que seja o maior de todos.

Prova por Contradição. Para demonstrar a verdade desta sentença, usaremos a prova por contra-dição na forma ¬p → (r ∧ ¬r). Suponha que ¬p seja verdadeira, ou seja, ‘existe um inteiro N queé o maior de todos os inteiros’.

Partindo de ¬p temos que N ≥ n, para cada inteiro n. Seja M = N + 1 a soma de dois inteiros. Aoperação + é fechada sobre o conjunto dos números inteiros: a soma de dois inteiros resulta em umnovo inteiro – logo existe um inteiro M que equivale à N + 1. Concluímos que M > N .

Seja r : ‘existe um inteiro N que é maior do que todos os inteiros’ e ¬r : ‘existe um inteiro M > N ’.A dedução da sentença ¬p levou à contradição (r ∧ ¬r), que é suficiente para demonstrar porcontradição que a sentença original, p, é verdadeira.

14

Até o presente momento utilizamos a forma ¬p → (r ∧ ¬r) para provar os Teoremas 10 e 11. En-tretanto, podemos usar outras formas na prova por contradição com objetivo de provar declaraçõescondicionais na forma (p → q). Trata-se da forma (p ∧ ¬q) → 0.

Neste tipo de prova, nós assumimos que a hipótese do teorema é verdadeira e a sua conclusão éfalsa, e usamos axiomas, definições e resultados já provados para deduzir uma contradição. Emnotação formal, (p ∧ ¬q) → 0.

Mostrar uma contradição partindo de p∧¬q é suficiente para demonstrar a verdade do teorema, jáque existe uma equivalência lógica entre as proposições (p → q) e (p ∧ ¬q → 0), já apresentada naTabela 3.

Teorema 12. Se 3n + 2 é ímpar, então n é ímpar

Prova por Contradição. Seja p : ‘3n+2 é ímpar’ e q : ‘n é ímpar’. O teorema tem a forma (p → q),logo podemos demonstrar a verdade de (p → q) por uma prova por contradição.

Para construir a prova por contradição, assuma a verdade de (p ∧ ¬q), isto é, ‘3n+ 2 é ímpar’ e ‘nnão é ímpar’. Pela definição de paridade (ver Definição 2), se n não é ímpar, então n é par e existeum inteiro k tal que n = 2k.

Substituindo n por 2k na expressão 3n + 2, obtemos

3n+ 2 = 3(2k) + 2

3n+ 2 = 6k + 2

3n + 2 = 2 (3k + 1)︸ ︷︷ ︸

t

O número t = 3k+1 é um inteiro que, multiplicado por 2, resulta em um número par – logo 3n+2é um número par. Segundo a dedução, ¬p é verdadeiro.

Na prova, assumimos a verdade de p : ‘3n+ 2 é ímpar’, e por meio de dedução sobre a definição deparidade encontramos ¬p : ‘3n+ 2 é par’. Logo, (p ∧ ¬q) → (p ∧ ¬p), ou seja, (p ∧ ¬q) → 0.

Como [(p ∧ ¬q) → 0] ≡ (p → q), então o teorema (p → q) é verdadeiro.

Teorema 13. Se a e b são números inteiros, então a2 − 4b 6= 2.

Prova por Contradição. Seja p : ‘a e b ∈ Z’ e q : ‘a2 − 4b 6= 2’. Para provar por contradição que oteorema (p → q) é verdadeiro, podemos usar a forma (p ∧ ¬q) → 0.

Devemos considerar a verdade das proposições (p∧¬q), ou seja, ‘a e b ∈ Z’, e ‘a2 − 4b = 2’. Vamostrabalhar sobre a sentença a2 − 4b = 2:

a2 − 4b = 2

15

a2 = 4b+ 2

a2 = 2(2b+ 1)

De acordo com a Definição 2, a2 é par. Se a2 é par, pelo Teorema 9 temos que a também é par epode ser escrita na forma a = 2k, para algum inteiro k.

Substituindo a por 2k na expressão a2 − 4b = 2, temos

a2 − 4b = 2

(2k)2 − 4b = 2

4k2 − 4b = 2

Dividindo ambos os lados da expressão acima por 2 resultará em

2k2 − 2b = 1

2 (k2 − b)︸ ︷︷ ︸

t

= 1

Da expressão acima, temos que t = k2− b é um inteiro. Se 1 = 2t, pela definição de paridade temosque 1 é par.

Seja a proposição r : ‘1 é par’, e seja a proposição ¬r : ‘1 é ímpar’. Pela dedução, encontramosque r é verdadeiro, porém, pela definição de paridade sabemos que 1 é ímpar porque não existenenhum inteiro que multiplicado por 2 resulte em 1. Se tanto r quanto ¬r são verdadeiros, temosa contradição (r ∧ ¬r).

Partimos de (p∧¬q) e deduzimos a contradição (r ∧¬r), ou seja, [(p ∧¬q) → 0]. Por equivalência,se [(p ∧ ¬q) → 0] é verdadeiro, então o teorema (p → q) também é verdadeiro.

Teorema 14. Para todo número real x ∈ [0, π/2], temos sinx+ cos x ≥ 1.

Prova por Contradição. Seja p : ‘x ∈ [0, π/2]’, e p : ‘sinx+cos x ≥ 1’. Para provar o teorema (p → q)por contradição, devemos assumir a verdade de (p ∧ ¬q), ou seja, ‘x ∈ [0, π/2]’ e ‘sinx+ cos x < 1’.

De p temos que o ângulo varia entre 0 ≤ x ≤ π/2, ou seja, nem sinx nem cos x são negativos, logo0 ≤ sinx+ cosx < 1.

Elevando a expressão 0 ≤ sinx+ cosx < 1 ao quadrado, temos

02 ≤ (sinx+ cos x)2 < 12

0 ≤ sin2 x+ 2 sin x cos x+ cos2 x < 1

0 ≤ sin2 x+ cos2 x︸ ︷︷ ︸

1

+2 sinx cos x < 1

16

Substituindo sin2 x+ cos2 x por 1, temos

0 ≤ 1 + 2 sinx cos x < 1

Se de p temos que nem sinx, nem cos x são negativos, então 1 + 2 sin x cos x será sempre maior doque zero. Assim,

1 + 2 sin x cos x < 1

2 sinx cos x < 0

Seja r : ‘2 sin x cos x < 0’. Partindo de (p∧¬q), deduzimos que r é verdadeiro; no entando p afirmaque se 0 ≤ x ≤ π/2, nem o sinx nem o cos x são negativos, logo 2 sinx cos x também não é negativo.Em outras palavras, ¬r também é verdadeiro.

Chegamos à contradição (r ∧ ¬r), ou seja, (p ∧ ¬q) → 0. Por equivalência, se (p ∧ ¬q) → 0 éverdadeiro, o teorema (p → q) também é verdadeiro.

4.4 Prova por Equivalência

A prova por equivalência é útil para provar teoremas bicondicionais, na forma (p ↔ q). Parademonstrar um teorema nesta forma, necessitamos mostrar que (p → q) e (q → p) são ambos ver-dadeiros.

Este tipo de demonstração é suficiente para provar (p ↔ q) graças à relação entre as proposições(p ↔ q) e [(p → q) ∧ (q → p)], que resultam na tautologia (p ↔ q) ↔ [(p → q) ∧ (q → p)] cujosvalores verdade são apresentados na Tabela 5.

Tabela 5: Tabela verdade para a tautologia (p ↔ q) ↔ [(p → q) ∧ (q → p)]p q p → q q → p (p → q) ∧ (q → p) p ↔ q (p ↔ q) ↔ [(p → q) ∧ (q → p)]

0 0 1 1 1 1 10 1 1 0 0 0 11 0 0 1 0 0 11 1 1 1 1 1 1

Teorema 15. Se n é um inteiro, então n é impar se e somente se n2 é ímpar.

Prova por Equivalência. Seja p : ‘n é ímpar’ e q : ‘n2 é ímpar’. O teorema tem a forma (p ↔ q),logo para provar o teorema necessitamos mostrar que as proposições (p → q) e (q → p) são ambasverdadeiras.

O Teorema 1 consiste justamente na proposição (p → q), que já demonstramos ser verdadeira pormeio de prova direta (ver demonstração do Teorema 1). Agora resta provar que a proposição (q → p)é igualmente verdadeira.

17

Para provar que a proposição (q → p) é verdadeira, vamos usar a prova por contraposição. Emum teorema na forma (q → p), a proposição q é a hipótese ou premissa do teorema, e a proposiçãop é a conclusão. Para demonstrar que o teorema é verdadeiro por contraposição, devemos partirda verdade sobre a negação da conclusão (neste caso, ¬p) para deduzir que a negação da hipótese(neste caso, ¬q) é também verdadeira. Em linguagem formal, (¬p → ¬q).

Seja ¬p : ‘n é par’ verdadeira. Da definição de paridade (Definição 2), temos que o número n podeser determinado por n = 2k, para algum inteiro k. Elevando a expressão n = 2k ao quadrado,temos:

(n)2 = (2k)2

n2 = 4k2

n2 = 2(2k2

)

︸ ︷︷ ︸

t

Ou seja, n2 é par uma vez que pode ser expresso por n2 = 2t, para um inteiro t = 2k2. Acabamosde deduzir ¬q.

Nesta demonstração, partimos de ¬p e deduzimos ¬q usando definições e fatos matemáticos. Comoexiste equivalência entre (¬p → ¬q) e (q → p), mostrar a verdade sobre (¬p → ¬q) é suficiente paraprovar que (q → p) é verdadeira.

Como nesta demonstração mostramos que as proposições (p → q) e (q → p) são ambas verdadeiras,pela equivalência entre as proposições (p ↔ q) e [(p → q) ∧ (q → p)] temos que o teorema (p ↔ q)é verdadeiro.

Em alguns casos, um teorema declara que diversas proposições, ditas p1, p2, . . . , pn são equivalentes.Tal fato é formalizado da seguinte maneira: p1 ↔ p2 ↔ p3 ↔ · · · ↔ pn, que declara que todas as nproposições possuem a mesma tabela verdade.

Consequentemente, para todo i e j com 1 ≤ i ≤ n e 1 ≤ j ≤ n, pi e pj são equivalentes. Uma formade provar essa equivalência mútua é usar o resultado da tautologia (p1 ↔ p2 · · · ↔ pn) ↔ [(p1 →p2) ∧ (p2 → p3) ∧ · · · ∧ (pn → p1)].

Se as n proposições condicionais (p1 → p2), (p2 → p3), . . . , (pn → p1) forem demonstradas seremverdadeiras, então as proposições p1, p2, . . . , pn são todas equivalentes.

Essa forma de demonstrar equivalência entre as n proposições é bastante eficiente, pois envolve ndemonstrações. A alternativa consiste em provar a verdade de (pi → pj), para todo i 6= j, com1 ≤ i ≤ n e 1 ≤ j ≤ n, que envolve demonstrar n2 − n proposições condicionais deste tipo.

Teorema 16. Para um inteiro n, as declarações n é par, n− 1 é ímpar e n2 é par são equivalentes.

18

Prova por Equivalência. Sejam p1 : ‘n é par’, p2 : ‘n − 1 é ímpar’ e p3 : ‘n2 é par’. Para provar aequivalência entre p1, p2 e p3 iremos usar a demonstração por equivalência.

Na demonstração por equivalência, devemos provar a verdade de (p1 → p2), (p2 → p3) e (p3 → p1)usando os métodos de prova direta e indireta. Vamos demonstrar a verdade de cada uma das pro-posições condicionais a seguir, em separado.

Demonstrando (p1 → p2) por prova direta: Assumindo que n é par, então temos que n = 2k paraalgum inteiro k. Por consequência,

n− 1 = (2k)− 1

n− 1 = 2k − 1

n− 1 = 2 (k − 1)︸ ︷︷ ︸

t

+1

Logo, n−1 é igual ao produto de um inteiro t = k−1 por 2, somado à 1. Pela definição de paridade(Definição 2) temos que n − 1 é ímpar. Partimos da verdade sobre p1 e chegamos à verdade sobrep2 usando demonstração direta, logo a proposição condicional (p1 → p2) é verdadeira.

Demonstrando (p2 → p3) por prova direta: Assumimos que n − 1 é ímpar, ou seja, n − 1 pode serescrito na forma n− 1 = 2k + 1, para algum inteiro k. Disso, temos

n− 1 = 2k + 1

n = 2k + 2

(n)2 = (2k + 2)2

n2 = 4k2 + 8k + 4

n2 = 2 (2k2 + 4k + 2)︸ ︷︷ ︸

t

Ou seja, n2 pode ser escrito pelo produto de um inteiro t = 2k2 + 4k + 2 por 2. Pela definição deparidade, n2 é par. Partindo de p2, por demonstração direta mostramos a verdade de p3; logo aproposição condicional (p2 → p3) é verdadeira.

Demonstraremos (p3 → p1) por contraposição, ou seja, assumindo que ¬p1 é verdadeiro, chegaremosa ¬p3 verdadeiro. Assumiremos que n− 1 é par, ou seja, n− 1 = 2k para algum inteiro k. Assim,

n− 1 = 2k

n = 2k + 1

(n)2 = (2k + 1)2

n2 = 4k2 + 4k + 1

n2 = 2 (2k2 + 2k)︸ ︷︷ ︸

t

+1

19

Ou seja, n2 é dado pelo produto de um inteiro t = 2k2 +2k por 2, somado à 1, ou seja, n2 = 2t+1.Pela definição de paridade, n2 é ímpar, ou seja, ¬p3 é verdadeiro. Provamos que se (¬p1 → ¬p3) éverdadeiro, então a proposição condicional (p3 → p1) é também verdadeira.

Demonstramos que as 3 proposições condicionais (p1 → p2), (p2 → p3) e (p3 → p1) são verdadeiras,que nos leva à concluir que p1, p2 e p3 são equivalentes.

4.5 Prova por Contra-Exemplo

Para mostrar que uma declaração na forma ∀x ∈ D(P (x)) ou na forma ∀x ∈ D(P (x) → Q(x)) éfalsa, basta encontrar um contra-exemplo.

Um contra-exemplo consiste em um valor x do domínio D para o qual P (x) é falso em declaraçõesdo tipo ∀x ∈ D(P (x)), ou para o qual P (x) é verdadeiro e Q(x) é falso em declarações da forma∀x ∈ D(P (x) → Q(x)).

Este tipo de prova é usada quando uma declaração da forma ∀x ∈ D(P (x)) ou ∀x ∈ D(P (x) →Q(x)) nos parece ser falsa, mas que não conseguimos demonstrar pelas técnicas já discutidas. Nestecasos, buscamos um contra-exemplo que mostre a falsidade da declaração.

Teorema 17 (Adaptado de [Loureiro, A. A. F.]). Para todo a,b ∈ R, [(a2 = b2) → (a = b)].

Prova por Contra-Exemplo. Seja P (a, b) : (a2 = b2), e seja Q(a, b) : (a = b). Para mostrar que aafirmação ∀a∀b(P (a, b) → Q(a, b)) é falsa, basta encontrar um contra-exemplo para o qual a igual-dade dos quadrados de a e b não implique que a e b sejam iguais.

Observamos que a atribuição de valores a = 4 e b = −4 torna a sentença P (a, b) verdadeiro e Q(a, b)falso, logo a declaração condicional P (a, b) → Q(a, b) é falsa.

Logo, os valores a = 4 e b = −4 são um contra-exemplo para a afirmação [(a2 = b2) → (a = b)].

Teorema 18. Cada inteiro positivo é a soma dos quadrados de dois inteiros.

Prova por Contra-Exemplo. Seja P (x) : n = a2 + b2. Para mostrar que P (x) é falso, basta apresen-tar um contra-exemplo, ou seja, um inteiro que não é formado pela soma dos quadrados de outrosdois inteiros.

Buscaremos por um contra-exemplo, enumerando alguns casos. Assim,

0 = 02 + 02 (Verdadeiro)1 = 12 + 02 (Verdadeiro)2 = 12 + 12 (Verdadeiro)3 = ? + ? (Falso)

O número 3 é um inteiro que não pode ser escrito pela soma do quadrado de dois outros inteiros.Logo, o número 3 é um contra-exemplo para P (x), pois torna P (x) falso.

20

4.6 Prova por Divisão em Casos

Existe ainda um outro tipo de prova, conhecida como prova por divisão de casos, que é útilquando temos que examinar múltiplos casos antes de demonstrar que uma declaração é verdadeiraem todos os cenários.

Uma prova por divisão em casos deve cobrir todos os casos que surgem no teorema em questão.Geralmente uma prova por casos é aplicada quando não existe uma forma óbvia de começar a de-monstração, porém existem informações extras sobre cada caso que ajudam a desenvolver a prova.

Teorema 19 (Adaptado de [Loureiro, A. A. F.]). Dois números inteiros consecutivos quaisquer temparidade oposta.

Prova por Divisão em Casos. Suponha m e m+1 dois inteiros consecutivos. Para provar o teoremaacima, devemos mostrar que um dos números, m ou m+ 1, é par, e o outro é ímpar.

Pela definição de paridade (Definição 2) sabemos que ou m é par, ou m é ímpar. Vamos verificarambos os casos em separado.

Caso 1 (m é par): Se considerarmos que m é par, então m = 2k para algum inteiro k. Substituindom por 2k na expressão m+ 1, obtemos:

m+ 1 = (2k) + 1

m+ 1 = 2k + 1

Logo, m + 1 é ímpar. Temos que um dos números é par, enquanto que o outro é ímpar – logo osinteiros m e m+ 1 tem paridade oposta.

Caso 2 (m é ímpar): Se considerarmos que m é ímpar, então m = 2k + 1 para algum inteiro k.Substituindo o valor de m na expressão m+ 1, temos:

m+ 1 = (2k + 1) + 1

m+ 1 = 2k + 2

m+ 1 = 2 (k + 1)︸ ︷︷ ︸

t

Ou seja, m+ 1 pode ser escrito na forma m+ 1 = 2t, onde t = k + 1 é um inteiro. Logo, m+ 1 épar. Se considerar m ímpar nos levou à encontrar que m+1 é par, temos que os inteiros m e m+1tem paridade oposta.

Conclui-se que, independente de qual dos dois casos ocorre, os números m e m + 1 sempre temparidade oposta. Isto posto, o teorema é verdadeiro.

21

Teorema 20. Se n ∈ N, então 1 + (−1)2 · (2n− 1) é um múltiplo de 4.

Prova por Divisão em Casos. Suponha n ∈ N verdadeiro. Logo, n é par ou n é ímpar. Como ofator (−1)n na expressão pode assumir um valor diferente dependente da paridade de n, devemosentão considerar os dois casos em separado.

Caso 1 (n é par): Se n é par, então n = 2k para algum inteiro k, e (−1)n = 1. A expressão1 + (−1)2 · (2n − 1) torna-se 1 + (2n − 1). Substituindo n por 2k, temos 1 + [2(2k) − 1] = 4k. Oresultado 4k é múltiplo de 4.

Caso 2 (n é ímpar): Se n é ímpar, então n = 2k + 1 para algum inteiro k, e (−1)n = −1.Assim, a expressão 1 + (−1)2 · (2n − 1) resulta em 1− (2n − 1). Substituindo n por 2k + 1, temos1− (2n− 1) = 1− [2(2k+1)− 1] = 1− [4k+2− 1] = 1− [4k+1] = −4k. O resultado −4k tambémé múltiplo de 4.

Ambos os casos mostram que 1 + (−1)2 · (2n − 1) é sempre múltiplo de 4.

Teorema 21. Mostre que |xy| = |x| · |y| para x e y números reais.

Prova por Divisão em Casos. A notação |c| é usada para indicar o valor absoluto de um númeroreal c. Por definição, |c| = c quando c ≤ 0, ou |c| = −c quando c < 0.

Para provar o teorema, temos que mostrar todos os casos possíveis envolvendo o valor absoluto de xe y. Tomando a definição usada acima, verificamos que existem quatro casos a serem demonstrados:x positivo, y positivo; x positivo, y negativo; x negativo, y positivo e x negativo, y negativo.

Caso 1 (x ≥ 0, y ≥ 0): se x ≥ 0 e y ≥ 0, então o produto xy ≥ 0. Pela definição de valor absoluto,se c ≥ 0 então |c| = c. Neste caso, tanto x quanto y são positivos, ou seja, |x| = x e |y| = y. Logo,|xy| = xy = |x| · |y|.

Caso 2 (x ≥ 0, y < 0): se x ≥ 0 e y < 0, então o produto xy < 0. Logo, |xy| = −xy. Peladefinição de valor absoluto, |c| = c se c ≥ 0, ou |c| = −c se c < 0. Neste caso, consideramos quex é positivo e y é negativo, logo |x| = x e |y| = −y. Em função dos sinais de x e y, a expressãoresultante |xy| = −xy pode ser reescrita como |xy| = x(−y). Usando a definição de valor absolutotemos então que |xy| = |x| · |y|.

Caso 3 (x < 0, y ≥ 0). Se x < 0 e y ≥ 0, então o produto xy < 0. Logo, |xy| = −xy. Peladefinição de valor absoluto, |c| = c se c ≥ 0, ou |c| = −c se c < 0. Neste caso, consideramos quex é negativo e y é positivo, logo |x| = −x e |y| = y. Em função dos sinais de x e y, a expressãoresultante |xy| = −xy pode ser reescrita como |xy| = (−x)y. Usando a definição de valor absolutotemos então que |xy| = |x| · |y|.

Caso 4 (x < 0, y < 0). Se x < 0 e y < 0, então o produto xy ≥ 0. Logo, |xy| = xy. Pela definiçãode valor absoluto, |c| = c se c ≥ 0, ou |c| = −c se c < 0. Neste caso, consideramos que x e y sãonegativos, logo |x| = −x e |y| = −y. Em função dos sinais de x e y, a expressão resultante |xy| = xy

22

pode ser reescrita como |xy| = (−x)(−y). Usando a definição de valor absoluto temos então que|xy| = |x| · |y|.

A igualdade |xy| = |x| · |y| se manteve em todos os casos demostrados, esgotando as possibilidades.Logo, concluímos que a afirmação |xy| = |x| · |y| é verdadeira.

4.7 Prova por Exaustão

Alguns teoremas podem ser provados pelo exame de um número relativamente pequeno de exemplos.Provas deste tipo são denominadas de provas exaustivas ou prova por exaustão, pois a provaocorre esgotando-se todas as possibilidades.

Provas exaustivas são um tipo especial de prova por casos onde cada caso consiste em verificar umúnico exemplo.

Teorema 22. Prove que (n + 1)3 ≥ 3n se n é um inteiro positivo com n ≤ 4.

Prova por Exaustão. Podemos provar a declaração acima por meio de exaustão, visto que temosuma quantidade pequena de casos (mais especificamente, n = 1, n = 2, n = 3 e n = 4. A provaconsiste na inspeção de que a desigualdade (n+ 1)3 ≥ 3n é verdadeira para todos os casos:

n = 1 (1 + 1)3 ≥ 31 8 ≥ 3 (Verdadeiro)n = 2 (2 + 1)3 ≥ 32 27 ≥ 9 (Verdadeiro)n = 3 (3 + 1)3 ≥ 33 64 ≥ 27 (Verdadeiro)n = 4 (4 + 1)3 ≥ 34 125 ≥ 81 (Verdadeiro)

Logo, em todos os casos do domínio a desigualdade se manteve verdadeira. Provamos por exaustãoque (n+ 1)3 ≥ 3n é verdadeiro para n inteiro positivo com n ≤ 4.

4.8 Provas Existenciais

Alguns teoremas são afirmações de que objetos de um determinado tipo existem. Teoremas destetipo tem a forma ∃xP (x), para um dado predicado P . Provas para proposições na forma ∃xP (x)são denominadas provas existenciais. Existem diversas formas de provas teoremas deste tipo.

Uma das formas consiste em encontrar um elemento a, chamado de testemunha, tal que P (a) sejaverdadeiro. Este tipo de prova de existência é denominada de prova construtiva.

Teorema 23. Existe um inteiro positivo que pode ser escrito como a soma dos cubos de inteirospositivos em duas maneiras diferentes.

Prova Existencial Construtiva. O menor número que pode ser escrito desta forma é o número 1729.De fato,

1729 = 103 + 93︸ ︷︷ ︸

Forma 1

= 123 + 13︸ ︷︷ ︸

Forma 2

23

Se P (x): ‘x é positivo e pode ser escrito como a soma dos cubos de inteiros positivos de duasmaneiras diferentes’, temos que P (1729) é verdadeiro; logo 1729 é uma testemunha para esta provaconstrutiva de ∃xP (x).

Teorema 24. Existe um inteiro que é par e primo.

Prova Existencial Construtiva. Seja P (x): ‘x é par e x é primo’. A afirmação acima pode ser for-malizada como ∃xP (x).

Considere o número inteiro 2. O número 2 ∈ Z e o número 2 é um número primo, pois os únicosinteiros que dividem o número 2 é o número 1 e ele próprio.

O número 2 é uma testemunha de que P (x) é verdadeiro, logo ∃xP (x) é verdadeiro.

Também é possível dar uma prova de existência não construtiva para declarações do tipo ∃xP (x),isto é, não encontramos um elemento a tal que P (a) seja verdadeiro mas provamos que ∃xP (x) éverdadeiro de outra maneira.

Teorema 25. Mostre que existem números irracionais x e y tal que xy é racional.

Prova Existencial Não-Construtiva. Seja√2 um número irracional. Se tomarmos x =

√2 e y =

√2,

então xy =(√

2)√

2.

Se(√

2)√

2é um número racional, então temos dois irracionais x =

√2 e y =

√2 tal que xy resulta

em um racional.

Por outro lado, se(√

2)√

2for um irracional, então podemos assumir x =

(√2)√

2e y =

√2

irracionais tal que xy =

(√2√

2

)√

2

=(√

2)√

2·√

2=

(√2)2

= 2, que é racional. Neste caso, xy

resulta em um número racional.

Na prova não-construtiva apresentada acima, nós não encontramos irracionais x e y tal que xy é

irracional, mas mostramos que ou o par x =√2, y =

√2, ou o par x =

(√2)√

2, y =

√2 possui a

propriedade desejada, mesmo sem indicar qual dos dois pares é a prova existencial do Teorema 25.

Outra maneira ainda de apresentar provas existenciais não-construtivas para um teorema consisteem mostrar ∃xP (x) indiretamente. Por exemplo, podemos mostrar que ¬∃xP (x) leva à uma con-tradição, de forma que a declaração ∃xP (x) é verdadeira.

24

4.9 Prova de Unicidade

Quando um teorema afirma a existência de um único objeto que satisfaz uma determinada propri-edade, devemos fazer a demonstração de tal teorema utilizando a prova por unicidade. Uma provapor unicidade envolve demonstrar que existe um elemento com tal propriedade (como uma provaexistencial), e que nenhum outro elemento além deste possui tal propriedade.

Uma prova de unicidade envolve duas partes:

• existência: mostrar que existe um elemento x com a propriedade enunciada.

• unicidade: mostrar que se x 6= y, então y não tem tal propriedade2; ou podemos mostrar quese x e y têm a propriedade desejada, então x = y.

A seguir apresentamos dois exemplos de prova por unicidade.

Teorema 26. Se a e b são números reais e a 6= 0, então há um único número real r tal que ar+b = 0

Prova de Unicidade. Dividiremos a demonstração em duas partes, para mostrar a existência de talnúmero r, seguida da demonstração de unicidade de r no sentido de que apenas r satisfaz a equaçãoar + b = 0.

Para demonstrar que tal número r existe, podemos isolar o r na equação acima, de onde obteremoso seu valor como r = − b/a. O número r é, portanto, a raíz da equação ar + b = 0, tornando aigualdade verdadeira.

Uma vez identificado que existe r tal que ar+ b = 0, devemos provar que ele é o único número realque também satisfaz essa equação. Seja s um número real tal que as + b = 0. Isolando o valor des, obtemos que s = − b/a. O número s também satisfaz a equação as+ b = 0; no entanto s = − b/ae r = − b/a; logo s = r.

Teorema 27. Todo inteiro tem um único inverso aditivo.

Prova de Unicidade. Seja p um inteiro. Iremos mostrar que existe um inteiro q tal que p + q = 0.Se isolarmos o valor de q na equação acima, teremos que q = −p. Logo, existe um inteiro q = −ptal que p+ q = 0.

Agora provaremos que q é único. Seja um inteiro r 6= q tal que p + r = 0. Como p + q = 0 ep + r = 0, então p + q = p + r. Subtraindo-se p de ambos os lados, a igualdade resulta em q = r.Oras, a declaração q 6= r levou a deduzir que q = r, ou seja, chegamos a uma contradição. Istoposto, p = r e, portanto, existe apenas um número q = −p que é inverso aditivo de p.

2i.e., ∃x(P (x)∧ ∀y(y 6= x → ¬P (y)))

25

4.10 Outros Métodos de Prova

As técnicas clássicas de prova foram apresentadas nas seções 4.1 à 4.9; entretanto existem aindaoutros tipos de prova, que serão brevemente comentadas na presente seção.

A primeira delas consiste na prova por vacuidade. Na prova por vacuidade, um teorema na formap → q é provado ser verdadeiro quando sabemos que p é falso. Isso ocorre porque sempre que p éfalso, p → q é verdadeiro em uma declaração condicional, independente do valor de q (ver Tabela 6).

Tabela 6: Tabela verdade para (p → q), com destaque para os elementos da prova por vacuidadep q p → q

0 0 10 1 11 0 01 1 1

Como consequência, se p é falso então temos uma prova por vacuidade do teorema na forma p → q.Este tipo de prova é útil para estabelecer casos onde o teorema declara que uma declaração condi-cional é para todos os inteiros positivos, isto é, ∀xP (x).

Teorema 28. Mostre que P (0) é verdadeiro, onde P (n) expressa a declaração ‘se n > 1, entãon2 > n’ no domínio dos números inteiros.

Prova por Vacuidade. P (0) significa que ‘se 0 > 1, então 02 > 0’. A hipótese 0 > 1 é falsa, o queimplica que P (0) é, automaticamente, verdadeira.

De forma equivalente, podemos provar que um teorema na forma p → q é verdadeiro se a conclusãoq for verdadeira. A Tabela 7 mostra os valores verdade para uma proposição condicional, comdestaque para o resultado de p → q quando q é verdadeiro. Este tipo de técnica é denominada deprova trivial.

Tabela 7: Tabela verdade para (p → q), com destaque para os elementos da prova trivialp q p → q

0 0 10 1 11 0 01 1 1

Teorema 29. Seja P (n) a afirmação ‘se a e b são inteiros positivos com a ≥ b, então an ≥ bn’ nodomínio do conjunto Z

+. Mostre que P (0) é verdadeira.

26

Prova Trivial. A proposição P (0) significa ‘se a ≥ b, então a0 ≥ b0’. Como a0 = b0 = 1, então aconclusão a0 ≥ b0 é verdadeira; logo a declaração condicional P (0) é verdadeira, independente dosvalores de a e b.

Por fim, existe ainda a prova por indução finita, que envolve um passo base que correspondeà uma demonstração dedutiva da proposição para um número natural; e um passo indutivo queconsiste na demonstração dedutiva da proposição geral: a validade da proposição para n implicana validade da proposição para n + 1. Por tratar-se de uma técnica de demonstração importantee poderosa para Ciência da Computação, a prova por indução será abordada em detalhes maisadiante, no estudo de recorrência.

5 Resumo: Técnicas de Prova

A Tabela 8 resume as técnicas de prova discutidas neste documento.

Tabela 8: Resumo das Técnicas de Prova

Prova Dedução Como provar

Direta p → qAssuma a premissa p verdadeira, e deduzaa conclusão q

Contraposição (¬q → ¬p) ≡ (p → q)Assuma a negação da conclusão ¬q verda-deira, e deduza a negação da hipótese ¬p

Contradição [(p ∧ ¬q) → 0] ≡ (p → q)

Assuma a hipótese p verdadeira, e a con-clusão q falsa. Deduza uma contradição apartir de (p ∧ ¬q). Se [(p ∧ ¬q) → 0], en-tão o teorema (p → q) é verdadeiro, pois[(p∧¬q) → 0] → (p → q) é uma tautologia

Contradição [¬p → 0] ≡ p

Assuma a negação da declaração p verda-deira, e deduza uma contradição (r∧¬r) apartir de ¬p. Se uma contradição é encon-trada, então a declaração p é verdadeirapois [(¬p → 0) → p] é uma tautologia.

Equivalência [(p → q) ∧ (q → p)] ≡ (p ↔ q)

Mostrar que as declarações (p → q) e(q → p) são ambas verdadeiras, empre-gando qualquer um dos métodos de provaconhecidos

Contra-Exemplo ∃a ∈ D(¬P (a))

Encontrar um elemento a ∈ D para o qualP (a) é falso. Se isso ocorrer, então a de-claração ∀x ∈ D(P (x)) é falsa.

Contra-Exemplo ∃a ∈ D(P (a) ∧ ¬Q(a))

Encontrar um elemento a ∈ D para o qualP (a) é verdadeiro e Q(a) é falso. Se existirtal elemento, então a sentença [P (a) →Q(a)] será falsa, assim como a declaraçãoquantificada ∀x ∈ D([(P (x) → Q(x)]).

27

Divisão de CasosListar os casos e inspecionar avalidade do teorema para cadacaso

Se o teorema em questão é válido para to-dos os casos em separado, então ele é ver-dadeiro.

ExaustãoInspecionar a validade do teo-rema para cada x ∈ D

O teorema é provado verificando-se a suavalidade para cada elemento x do domínio.Basta um contra-exemplo para provar queo teorema é falso.

ExistenciaisConstrutivas

Apresentar uma testemunha atal que P (a) seja verdadeiro

Se existe algum elemento a do domínio talque a sentença P (a) é verdadeira, então asentença quantificada ∃xP (x) será igual-mente verdadeira.

Existenciais Não-Construtivas

Mostrar que ∃x(P (x)) semapresentar uma testemunha apara o qual a sentença P (a)seja verdadeira.

Mostrar ∃x(P (x)) indiretamente.

Unicidade

(i) mostrar que existe algumelemento a tal que P (a) é ver-dadeiro;(ii) mostrar que se existe umelemento b tal que P (b) é ver-dadeiro, então a = b.

Se existe um elemento a tal que P (a) éverdadeiro, e nenhum outro elemento domesmo domínio possui essa propriedade,então mostramos que ∃!xP (x).

Vacuidade Inspeção sobre o valor de pSe p é falso, (p → q) é verdadeiro indepen-dente do valor de q

Trivial Inspeção sobre o valor de qSe q é verdadeiro, então (p → q) tambémé verdadeiro, independente do valor de p

28

6 Exercícios de Fixação

Resolva a seguinte lista de exercícios. Você poderá usar os axiomas, definições e teoremas provadosapresentados neste documento como parte do raciocínio dedutivo. Caso precise de mais axiomas,definições, teoremas e fatos para completar a prova, você deverá pesquisar por contra própria edestacar os resultados.

Use prova direta para demonstrar as afirmações dos Exercícios 1 à 3.

Exercício 1. Para todos os inteiros a e b, se a e b são pares, então a soma a+ b é par.

Exercício 2. Para todos os inteiros a e b, se a e b são pares, então o produto a · b é par.

Exercício 3. Todo inteiro ímpar é a diferença de dois quadrados.

Demonstre que as seguintes afirmações são verdadeiras usando as provas direta, por contraposiçãoe por contradição.

Exercício 4. Se n é um inteiro par, então n+ 7 é ímpar.

Exercício 5. Se n é um inteiro ímpar, então n+ 11 é par.

Forneça uma prova por contraposição para as seguintes afirmações:

Exercício 6. Para todos os inteiros a e b, se a · b é ímpar, então a e b são ambos ímpares.

Exercício 7. Para todos os inteiros a e b, se a + b é par, então a e b são ambos pares ou ambosímpares.

Exercício 8. Para todo número real x e y, se x+ y ≥ 100, então x ≥ 50 ou y ≥ 50.

Prove as afirmações dos Exercícios 9 à 12 por contradição:

Exercício 9. Para cada inteiro n, se n é ímpar, então n2 é ímpar.

Exercício 10. Não existem inteiros a e b para o qual 18a+ 6b = 1.

Exercício 11. Para cada x ∈ [π/2, π], sinx− cos x ≥ 1.

Exercício 12.√6 é um número irracional.

Prove as afirmações dos Exercícios 13 à 18 usando qualquer uma das técnicas apresentadas nestedocumento.

Exercício 13. Se n é um inteiro positivo, então n é par se e somente se 7n+ 4 é par.

Exercício 14. Se n é um inteiro positivo, então n é ímpar se e somente se 5n+ 6 é ímpar.

Exercício 15. Se x2 + 2x− 3 = 0, então x 6= 2.

29

Exercício 16. Se um número somado à ele mesmo resulta no próprio número, então este númeroé zero.

Exercício 17. Se x é um inteiro par e primo, então x = 2.

Exercício 18. Se n é um inteiro ímpar, então 8 divide (n2 − 1).

Apresente um contra-exemplo para as seguintes afirmações:

Exercício 19. Toda figura geométrica com quatro ângulos retos é um quadrado.

Exercício 20. Todo quadrilátero com quatro lados iguais têm ângulos retos.

Prove, usando o método da exaustão, a declaração

Exercício 21. Seja o conjunto D formado pelos inteiros pares de 2 à 26, ou seja, D = {2, 4, 6, 8,10, 12, 14, 16, 18, 20, 22, 24, 26}. Para todo número x ∈ D, x pode ser escrito como a soma deno máximo 3 quadrados perfeitos.

Prove, usando prova por divisão em casos, as declarações:

Exercício 22. Se dois inteiros tem a mesma paridade, então sua soma é par.

Exercício 23. Se n ∈ N, então n2 + 3n + 4 é par.

Exercício 24. Prove que dado um número real x existem números únicos n e ǫ tais que x = n− ǫ,com n inteiro e 0 ≤ ǫ < 1.

Exercício 25. Mostre que se a, b e c são números reais e a 6= 0, então existe uma única soluçãopara a equação ax+ b = c.

Referências

[Rosen, K. H.] Matemática Discreta e suas Aplicações, Tradução da 6a. Edição em Inglês. EditoraMc-Graw Hill Brasil, ISBN 978-85-7726-036-2, 2009.

[Gersting, J. L.] Fundamentos Matemáticos para Ciência da Computação, 3a. edição. Editora LTC,ISBN 978-85-2161-422-7, 1995.

[Grimaldi, R. P.] Discrete and Combinatorial Mathematics: An Applied Introduction, 3rd. edition.Adison Wesley, ISBN: 0-201-54983-2, 1994.

[Loureiro, A. A. F.] Slides sobre matemática discreta. Disponível emhttp://homepages.dcc.ufmg.br/~loureiro/md/md_3MetodosDeProva.pdf. Acessadoem Set/2012.

[Hammack, R.] Book of Proof. Mathematics Textbook Series. Disponível emhttp://www.people.vcu.edu/~rhammack/BookOfProof/BookOfProof.pdf. Acessado emOut/2012.

30