Bacharelado em Ciência da Computação Matemática Discreta · 2 Dedução e Provas 3 Métodos de Prova Exaustão Vacuidade Trivial Direta Contraposição Contradição Prova por

Bacharelado em Ciência da ComputaçãoMatemática Discreta

Prof. Diego Mello da Silva

Instituto Federal de Minas Gerais - Campus Formiga

16 de janeiro de 2013

[email protected] (IFMG) Matemática Discreta 16 de janeiro de 2013 1 / 55

Sumário

1 Conceitos de Provas e Teoremas

2 Dedução e Provas

3 Métodos de ProvaExaustãoVacuidadeTrivialDiretaContraposiçãoContradiçãoProva por EquivalênciaProva por Contra-ExemploProva por Divisão em CasosProva ExistencialProva de Unicidade


Conceitos de Provas e Teoremas


Prova

Definição (Prova)

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

Uma prova utiliza:

hipóteses de um teorema;

axiomas;

definições;

resultados de teoremas previamente provados;

como ingredientes que, juntamente com regras de inferência , estabelecema verdade sobre a declaração que está sendo demonstrada.


Teoremas

Um teorema é uma sentença que pode ser demonstrada comoverdadeira.

Um teorema é uma afirmação específica que pode ser provada .

Resultados matemáticos são, geralmente, expressos como teoremas naforma ‘se p, então q’.

p e q podem representar sentenças compostas.

p é a hipótese do teorema

q é a conclusão do teorema

A dedução de q a partir de p é feita com uso de axiomas, definições,regras de inferência e resultados já provados.


TerminologiaA terminologia é empregada segundo a importância do teorema:

Teorema : atualmente, teorema tem sido usado em afirmaçõesprovadas que tem uma ‘grande importância matemática’. Ex:

Teorema de Pitágoras1,

Teorema do Limite Central2,

Teorema Fundamental da Aritmética3.

Fato : teorema de importância limitada. Ex: ‘3 + 6 = 9’.

Proposição : teorema de importância secundária, mais importante queum fato e menos importante que um teorema. Faz parte de um teoremamaior.

1a2 = b2 + c2

2quando o tamanho de uma amostra aumenta, a distribuição de x̄ ∼ N3se x ∈ Z e x > 1, x pode ser decomposto em um produto de primos > 0


TerminologiaAxioma ou Postulado : sentença ou proposição que não é provada,mas é considerada óbvia e aceita como verdade na construção dededuções.

∀x ∈ R, x + y ∈ R4

Pode-se traçar uma reta ligando-se dois pontos quaisquer5.

Lemas : teoremas menos importantes usados na demonstração deteoremas mais complexos.

Corolário : Teoremas estabelecidos sobre outros teoremas provados; éa decorrência imediata de um teorema.

O Teorema de Pitágoras afirma que a2 = b2 + c2.

A diagonal de um quadrado cujos lados medem l unidades é l√

2(corolário).

4Fecho Aditivo em R5Elementos, de Euclides


TerminologiaConjectura : afirmação que propõe-se ser verdadeira com base em:

evidência parcial

argumento heurístico

intuição de um especialista

Goldbach 6: ∀n par, ∃a, b ∈ Z tal que a e b são primos e a + b = n.

Jan/2005: verificado até 02 × 1017

Fev/2007: verificado até 04 × 1017


Mai/2011: verificado até 22 × 1017


Seria verdadeiro de 35 × 1017 até ∞?6http://www.ieeta.pt/~tos/goldbach.html


http://www.ieeta.pt/~tos/goldbach.html

Outros IngredientesDefinições : sequências de palavras que expressam o significado deexpressões em matemática. Algumas definições importantes:

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

Divisibilidade : um inteiro a é divisível por um inteiro b se a for igual aoproduto de um inteiro k por b, ou seja, a = k · b.

Paridade : um inteiro n é par se existir algum inteiro k tal que n = 2k , en é ímpar se existir algum inteiro k tal que n = 2k + 1

Quadrado Perfeito : um inteiro a é um quadrado perfeito se houver uminteiro b tal que a = b2

Números Racionais : um número real r é racional se existem inteiros pe q com q 6= 0 tal que r = p/q


Dedução e Provas


Dedução e ProvasResultados matemáticos são expressos por teoremas na forma ‘se p,então q’.

Em teoremas desta forma, tentamos deduzir q de p usando

Axiomas

Definições

Regras de Inferência

Resultados demonstrados

A dedução segue uma ordem lógica de passos que começam em p eterminam em q

Prove : ‘se um inteiro é divisível por 6, então ele é divisível por 3’.


Dedução e Provas


Hipótese : x é divisível por 6

Dedução

x = k · 6 para algum inteiro k (Definição de divisibilidade)


Dedução e Provas



Dedução

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


Dedução e Provas



Dedução

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


Dedução e Provas



Dedução

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


Dedução e Provas



Dedução

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

︸︷︷︸

t

3 (Fecho Multiplicativo)


Dedução e Provas



Dedução


︸︷︷︸

t


x = t · 3 para t = 2k , t ∈ Z (Definição de divisibilidade)


Dedução e Provas



Dedução


︸︷︷︸

t


x = t · 3 para t = 2k , t ∈ Z (Definição de divisibilidade)

Conclusão : x é divisível por 3


Dedução e ProvasMaioria das declarações em matemática são universais

Logo, teorema pode conter uma declaração sobre todos os objetos deum domínio D

∀x ∈ D(P(x) → Q(x))

Informalmente, P(x) → Q(x)

Quando D é finito, podemos provar P(x) → Q(x) mostrando que isso éverdade para cada elemento x ∈ D (método da exaustão )

Prove : ‘∀n ∈ Z, se n é par e 4 ≤ n ≤ 30, então n pode ser escrito comoa soma de dois números primos’.




∀x ∈ D(P(x) → Q(x))




04 = 02 + 02 06 = 03 + 03 08 = 03 + 05 10 = 05 + 05




∀x ∈ D(P(x) → Q(x))




04 = 02 + 02 06 = 03 + 03 08 = 03 + 05 10 = 05 + 0512 = 05 + 07 14 = 03 + 11 16 = 05 + 11 18 = 07 + 11




∀x ∈ D(P(x) → Q(x))




04 = 02 + 02 06 = 03 + 03 08 = 03 + 05 10 = 05 + 0512 = 05 + 07 14 = 03 + 11 16 = 05 + 11 18 = 07 + 1120 = 07 + 13 22 = 05 + 17 24 = 05 + 19 26 = 07 + 19




∀x ∈ D(P(x) → Q(x))




04 = 02 + 02 06 = 03 + 03 08 = 03 + 05 10 = 05 + 0512 = 05 + 07 14 = 03 + 11 16 = 05 + 11 18 = 07 + 1120 = 07 + 13 22 = 05 + 17 24 = 05 + 19 26 = 07 + 1928 = 11 + 17 30 = 11 + 19


Dedução e Provas

Porém, quando o domínio D é não-finito ou grande , o método daexaustão não é prático

Neste caso, usamos o método da generalização para mostrar averdade da afirmação

P(x) → Q(x) é falso quando P(x) é verdadeiro e Q(x) é falso

Suponha P(x) é verdadeiro

Mostre que Q(x) também é verdadeiro

Como mostrar que ∀x ∈ D(P(x) → Q(x)) é verdadeiro?

Suponha c específico e escolhido arbitrariamente de D.

Mostre que c satisfaz P(c) → Q(c)

Se mostrarmos P(c) → Q(c), provamos ∀x ∈ D(P(x) → Q(x))


Métodos de Prova


Métodos de Prova

A construção de provas torna-se mais fácil quando se utiliza algum dosmétodos de prova

São ferramentas para mostrar P(x) → Q(x) a partir da lógica.

Prova por Exaustão

Prova por Vacuidade

Prova Trivial

Prova Direta

Prova por Contraposição

Prova por Contradição

Prova por Contra-Exemplo

Prova por Equivalência

Prova por Divisão em Casos

Prova Existencial e de Unicidade


Prova por ExaustãoAplicam-se quando teoremas podem ser provados pelo exame de umnúmero pequeno de exemplos

Prova ocorre esgotando-se todas as possibilidades

É um tipo especial de prova em casos (ver adiante)

Teorema‘Se n é um inteiro positivo com n ≤ 4, então (n + 1)3 ≥ 3n.’

Prova por Exaustão.

Prova: inspeção de que (n + 1)3 ≥ 3n ocorre em todos os casos

p/ n = 1: (1 + 1)3 ≥ 31 =⇒ 8 ≥ 3 (Verdadeiro)








p/ n = 1: (1 + 1)3 ≥ 31 =⇒ 8 ≥ 3 (Verdadeiro)p/ n = 2: (2 + 1)3 ≥ 32 =⇒ 27 ≥ 9 (Verdadeiro)








p/ n = 1: (1 + 1)3 ≥ 31 =⇒ 8 ≥ 3 (Verdadeiro)p/ n = 2: (2 + 1)3 ≥ 32 =⇒ 27 ≥ 9 (Verdadeiro)p/ n = 3: (3 + 1)3 ≥ 33 =⇒ 64 ≥ 27 (Verdadeiro)








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


Prova por VacuidadeTeorema na forma p → q é provado verdadeiro quando p é falso.

p q p → q

0 0 10 1 11 0 01 1 1

TeoremaSeja P(n): ‘se n > 1, então n2 > n’ para n ∈ Z. Mostre que P(0) é verdadeiro

Prova por Vacuidade.

P(0): ‘se 0 > 1︸︷︷︸

p

, então 02 > 0︸︷︷︸

q

’.

A hipótese p é falsa,

Logo, a implicação p → q é verdadeira, ou seja, P(0) é verdadeiro.


Prova por VacuidadeTeoremaSe o país x é africano e venceu uma copa do mundo no século XX, então xfica na Europa.


Não existe país africano que venceu uma copa do mundo no século XX.

Logo, p → q é verdadeiro.

TeoremaSe x2 + 1 < 0, então x5 ≥ 4, com D = R.


x2 + 1 é sempre positivo, logo p é falso ∀x ∈ D

Logo, a implicação p → q é [email protected] (IFMG) Matemática Discreta 16 de janeiro de 2013 19 / 55

Prova TrivialTeorema na forma p → q é provado verdadeiro quando q é verdadeiro.

p q p → q

0 0 10 1 11 0 01 1 1

TeoremaSeja P(n): ‘se a e b são inteiros positivos com a ≥ b, então an ≥ bn ’ paran ∈ Z

+. Mostre que P(0) é verdadeiro.

Prova Trivial.

P(0): ‘se a ≥ b︸︷︷︸

p

, então a0 ≥ b0︸︷︷︸

q

’.

A hipótese q é verdadeira, pois a0 = b0 = 1 independente de a e b.

Logo, a implicação p → q é verdadeira, ou seja, P(0) é [email protected] (IFMG) Matemática Discreta 16 de janeiro de 2013 20 / 55

Prova TrivialTeoremaSeja x ∈ R. Se x > 0, então x2 + 5 > 0.

Prova Trivial.

x2 ≥ 0, ∀x ∈ R

x2 + 5 > x2, ∀x ∈ R

x2 + 5 ≥ 0, ∀x ∈ R

x2 + 5 > 0, x > 0.

A conclusão q é sempre verdadeira.

Logo, a implicação p → q é verdadeira.


Prova DiretaA prova direta consiste em mostrar que p → q é verdadeiro quando:

assume-se p verdadeiro

mostra-se que quando p é verdadeiro, q também é verdadeiro

A dedução de que a verdade de p leva à verdade de q é feita usando:

axiomas e fatos matemáticos

definições

regras de inferência

resultados já provados

Algoritmo 1 Construção de uma prova direta

1: Expresse a declaração a ser provada na forma ∀x ∈ D P(x) → 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


Prova Direta

Definição (Paridade)

Um inteiro n é par se existir algum inteiro k tal que n = 2k, e n é ímpar seexistir algum inteiro k tal que n = 2k + 1.

Teorema

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

Prova Direta.� Assumimos que n é ímpar.


Prova Direta



Teorema



� Pela definição, n = 2k + 1, para um inteiro k .


Prova Direta



Teorema




� Elevando ambos lados de n = 2k + 1 ao quadrado: n2 = (2k + 1)2


Prova Direta



Teorema





� n2 = 4k2 + 4k + 1 ⇒ n2 = 2 (2k2 + 2k)︸︷︷︸

t

+1


Prova Direta



Teorema





� n2 = 4k2 + 4k + 1 ⇒ n2 = 2 (2k2 + 2k)︸︷︷︸

t

+1

� Logo, n2 = 2t + 1. Pela definição, se n é ímpar, n2 também é ímpar.


Prova Direta



TeoremaSe a e b são inteiros, então 6a2b é par.

Prova Direta.� Pela definição, um inteiro n é par quando n = 2k .


Prova Direta





� Considere n = 6a2b e k = 3a2b.


Prova Direta






� Operações +, − e × são fechadas nos inteiros: 3a2b ∈ Z


Prova Direta







� n = 2(3a2b︸︷︷︸

k

).


Prova Direta







� n = 2(3a2b︸︷︷︸

k

).

� Logo, n = 2k . Pela definição, 6a2b é par.


Prova Direta

Definição (Quadrado Perfeito)

Um inteiro a é um quadrado perfeito se houver um inteiro b tal que a = b2.

TeoremaSe m e n são quadrados perfeitos, então n · m é um quadrado perfeito.

Prova Direta.� Assumir que m e n são quadrados perfeitos.


Prova Direta





� Pela definição, existem r , s ∈ Z tais que n = r2 e m = s2.


Prova Direta






� n · m = r2 · s2 = rr · ss = (rr)(ss) = (rs)(rs)


Prova Direta







� n · m = (rs)2


Prova Direta







� n · m = (rs)2

� O produto n · m é o quadrado de rs.


Prova Direta







� n · m = (rs)2


� Operação × é fechada nos inteiros: rs ∈ Z


Prova Direta







� n · m = (rs)2


� Operação × é fechada nos inteiros: rs ∈ Z

� Logo, o produto n · m é um quadrado perfeito.


Prova DiretaDefinição (Paridade)


Teorema∀ n e m ∈ Z, se n + m é par, então n − m é par

Prova Direta.� Suponha m, n ∈ Z tal que m + n seja par.






� Pela definição, m + n = 2k para k ∈ Z.







� m = 2k − n







� m = 2k − n

� Diferença de m e n: m − n = (2k − n)− n







� m = 2k − n


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

t







� m = 2k − n


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

t

� Logo, m − n = 2t , t ∈ Z. Pela definição, m − n é par


Prova Direta

Use prova direta para demonstrar as seguintes afirmações:

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

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

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

.


Prova Indireta

Teoremas na forma p → q também podem ser demonstrados por meio deprovas que não começam com a premissa e terminam com a conclusão.

A este tipo de demonstração denominados de prova indireta

Ela é usada quando

A demonstração falha por prova direta...

... mas existe um sentimento de que a afirmação é verdadeira.

São métodos de prova indireta:

Prova por contraposição

Prova por contradição (Reductio ad Absurdum)


Prova Indireta

Para exemplificar, seja o seguinte teorema.

TeoremaSe n é um inteiro e 3n + 2 é ímpar, então n é ímpar.

Tentativa de Prova Direta.� Assuma que 3n + 2 é um inteiro ímpar.


Prova Indireta




� Da definição de paridade, 3n + 2 = 2k + 1 para k ∈ Z


Prova Indireta





� 3n + 1 = 2k


Prova Indireta





� 3n + 1 = 2k

� E agora???

A tentativa de prova falha, pois não há forma direta de concluir que n é ímpar.

Devemos recorrer a um dos métodos de prova indireta.


Prova por ContraposiçãoA prova por contraposição consiste em mostrar que p → q é verdadeirousando o fato de que (¬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

Algoritmo 2 Construção de uma prova por contraposição

1: Escreva a declaração a ser provada na forma ∀x ∈ D, P(x) → Q(x)2: Reescreva a declaração na forma contrapositiva: ∀x ∈ D, ¬Q(x) → ¬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) é verdadeiro


Prova por ContraposiçãoVoltemos ao teorema:


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

Prova por Contraposição.� ¬q: n é par, logo n = 2k , k ∈ Z (paridade)






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






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

� 3n + 2 = 6k + 2






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

� 3n + 2 = 6k + 2

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

t

, com t = 3k + 1 ∈ Z






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

� 3n + 2 = 6k + 2

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

t

, com t = 3k + 1 ∈ Z

� 3n + 2 = 2t






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

� 3n + 2 = 6k + 2

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

t

, com t = 3k + 1 ∈ Z

� 3n + 2 = 2t

� Logo, pela definição de paridade, 3n + 2 é par (¬p)



TeoremaPara todo número real positivo x e y, se o produto x · y excede 25, entãox > 5 ou y > 5.

Premissa p : ‘x · y > 25’ ¬p : ‘x · y ≤ 25’Premissa q : ‘x > 5 ou y > 5’ ¬q : ‘(0 < x ≤ 5) e (0 < y ≤ 5)’

Prova por Contraposição.� ¬q: (0 < x ≤ 5) e (0 < y ≤ 5)






� 0 · 0 < x · y < 5 · 5






� 0 · 0 < x · y < 5 · 5

� 0 < x · y ≤ 25






� 0 · 0 < x · y < 5 · 5

� 0 < x · y ≤ 25

� Logo, o produto x · y não excede 25 (¬p)


Prova por ContraposiçãoTeoremaSe n = a · b, com a e b inteiros positivos, então a ≤

√n ou b ≤

√n.

Premissa p : ‘n = a · b’ ¬p : ‘n 6= ab’Premissa q : ‘(a ≤

√n) ou (b ≤

√n)’ ¬q : ‘(a >

√n) e (b >

√n)’

Prova por Contraposição.

� ¬q: (a >√

n) e (b >√

n)



√n ou b ≤

√n.


√n) ou (b ≤

√n)’ ¬q : ‘(a >

√n) e (b >

√n)’


� ¬q: (a >√

n) e (b >√

n)

� a · b >√

n ·√

n



√n ou b ≤

√n.


√n) ou (b ≤

√n)’ ¬q : ‘(a >

√n) e (b >

√n)’


� ¬q: (a >√

n) e (b >√

n)

� a · b >√

n ·√

n

� a · b > (√

n)2



√n ou b ≤

√n.


√n) ou (b ≤

√n)’ ¬q : ‘(a >

√n) e (b >

√n)’


� ¬q: (a >√

n) e (b >√

n)

� a · b >√

n ·√

n

� a · b > (√

n)2

� a · b > n



√n ou b ≤

√n.


√n) ou (b ≤

√n)’ ¬q : ‘(a >

√n) e (b >

√n)’


� ¬q: (a >√

n) e (b >√

n)

� a · b >√

n ·√

n

� a · b > (√

n)2

� a · b > n

� Logo, a · b 6= n (¬p)


Prova por ContraposiçãoTeoremaSe um inteiro x é divisível por 6, então x também é divisível por 3

Premissa p : ‘x é divisível por 6’ ¬p : ‘x não é divisível por 6’Premissa q : ‘x é divisível por 3’ ¬q : ‘x não é divisível por 3’

Prova por Contraposição.� (¬q) x 6= k · 3, para k ∈ Z





� k = 2t





� k = 2t

� x 6= (2t) · 3





� k = 2t

� x 6= (2t) · 3

� x 6= t(2 · 3)





� k = 2t

� x 6= (2t) · 3

� x 6= t(2 · 3)

� x 6= t · 6, para t ∈ Z





� k = 2t

� x 6= (2t) · 3

� x 6= t(2 · 3)

� x 6= t · 6, para t ∈ Z

� Logo, pela definição de divisibilidade, x não é divisível por 6 (¬p)[email protected] (IFMG) Matemática Discreta 16 de janeiro de 2013 34 / 55

Prova por ContraposiçãoTeoremaDado qualquer inteiro n, se n2 é par, então n é par.

Premissa p : ‘n2 é par’ ¬p : ‘n2 é ímpar’Premissa q : ‘n é par’ ¬q : ‘n é ímpar’

Prova por Contraposição.� (¬q) n = 2k + 1, k ∈ Z





� n2 = n · n ⇒ n2 = (2k + 1) · (2k + 1)





� n2 = n · n ⇒ n2 = (2k + 1) · (2k + 1)

� n2 = (2k + 1)2 ⇒ n2 = 4k2 + 4k + 1





� n2 = n · n ⇒ n2 = (2k + 1) · (2k + 1)

� n2 = (2k + 1)2 ⇒ n2 = 4k2 + 4k + 1

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

t

+1





� n2 = n · n ⇒ n2 = (2k + 1) · (2k + 1)

� n2 = (2k + 1)2 ⇒ n2 = 4k2 + 4k + 1

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

t

+1

� n2 = 2t + 1. Logo, pela definição de paridade, n2 é ímpar.



Use prova por contraposição para demonstrar as seguintes afirmações:

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

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

.


Prova por ContradiçãoUma prova por contradição mostra (p → q) indiretamente em dois casos:

� Teoremas na forma p → q: assumir que ∀x ∈ D(P(x) → Q(x)) é falso

Em lógica, (p ∧ ¬q)

Partindo de (p ∧ ¬q), deduzir uma contradição 0.

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

� Teoremas na forma p: assumir que ∀x ∈ D(P(x)) é falso

Em lógica, ¬p

Partindo de ¬p, deduzir a contradição (r ∧ ¬r).

p r ¬p ¬r (r ∧ ¬r) [¬p → (r ∧ ¬r)] [¬p → (r ∧ ¬r)] ↔ p0 0 1 1 0 0 10 1 1 0 0 0 11 0 0 1 0 1 11 1 0 0 0 1 1


Prova por ContradiçãoDe maneira mais geral,

Algoritmo 3 Construção de uma prova por contradição

1: 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

Resumo

[(p ∧ ¬q) → 0] ≡ (p → q)

� Assuma a hipótese p verdadeira, e a conclusãoq falsa.� Deduza uma contradição a partir de (p ∧ ¬q).� Se [(p ∧ ¬q) → 0], então a declaração (p → q)é verdadeira, pois [(p ∧ ¬q) → 0] ≡ (p → q)

[¬p → 0] ≡ p

� Assuma a negação da declaração p verdadeira.� Deduza uma contradição (r ∧¬r) a partir de ¬p.� Se (¬p → 0), então a declaração p é verda-deira, pois [(¬p → 0) ≡ p].



Teorema (Forma p)Não existe um inteiro que seja o maior de todos.

Prova por Contradição.� (¬p): ∃ N ∈ Z tal que N é o maior de todos.





� N ≥ n, ∀n ∈ Z





� N ≥ n, ∀n ∈ Z

� M = N + 1. Pelo fecho aditivo, M ∈ Z





� N ≥ n, ∀n ∈ Z


� M > N.





� N ≥ n, ∀n ∈ Z


� M > N.

� Contradição: ‘N é o maior de todos os inteiros’, e ‘M é maior do que N ’.





� N ≥ n, ∀n ∈ Z


� M > N.

� Contradição: ‘N é o maior de todos os inteiros’, e ‘M é maior do que N ’.

� Portanto, (p → q) pois [(p ∧ ¬q) → 0] ≡ (p → q).


Prova por ContradiçãoDefinição (Números Racionais)

Um número real r é racional se existem inteiros p e q | r = p/q, com q 6= 0.

Teorema (Forma p)

O número√

2 é um número irracional.

Prova por Contradição.

� (¬p):√

2 é um número racional.




Teorema (Forma p)

O número√



� (¬p):√


� ∃ a, b ∈ Z tal que√

2 = a/b. Logo a e b não possuem fatores em comum.




Teorema (Forma p)

O número√



� (¬p):√




�

(√2)2

= (a/b)2 ⇒ 2 = a2/b2 ⇒ a2 = 2b2 . Se a2 é par, a é par⋆.




Teorema (Forma p)

O número√



� (¬p):√




�

(√2)2


� a2 = 2b2 ⇒ (2k)2 = 2b2 ⇒ 2b2 = 4k2 ⇒ b2 = 2k2 . Portanto, b é par.




Teorema (Forma p)

O número√



� (¬p):√




�

(√2)2



� Contradição: ‘a e b não possuem fatores em comum’, e ‘a e b sãodivididos por 2’.




Teorema (Forma p)

O número√



� (¬p):√




�

(√2)2



� Contradição: ‘a e b não possuem fatores em comum’, e ‘a e b sãodivididos por 2’.

� Portanto, (p → q) pois [(p ∧ ¬q) → 0] ≡ (p → q)[email protected] (IFMG) Matemática Discreta 16 de janeiro de 2013 40 / 55

Prova por ContradiçãoTeorema (Forma p → q)Se 3n + 2 é ímpar, então n é ímpar

Prova por Contradição.� (p ∧ ¬q): ‘3n + 2 é ímpar’ e ‘n é par’.




� Se n é par, então n = 2k , k ∈ Z





� 3n + 2 = 3(2k) + 2 ⇒ 3n + 2 = 6k + 2 ⇒ 3n + 2 = 2 (3k + 1)︸︷︷︸

t





� 3n + 2 = 3(2k) + 2 ⇒ 3n + 2 = 6k + 2 ⇒ 3n + 2 = 2 (3k + 1)︸︷︷︸

t

� 3n + 2 = 2t , para t ∈ Z





� 3n + 2 = 3(2k) + 2 ⇒ 3n + 2 = 6k + 2 ⇒ 3n + 2 = 2 (3k + 1)︸︷︷︸

t

� 3n + 2 = 2t , para t ∈ Z

� Pela definição de paridade, 3n + 2 é par.





� 3n + 2 = 3(2k) + 2 ⇒ 3n + 2 = 6k + 2 ⇒ 3n + 2 = 2 (3k + 1)︸︷︷︸

t

� 3n + 2 = 2t , para t ∈ Z


� Contradição: ‘3n + 2 é ímpar ’ e ‘3n + 2 é par ’.





� 3n + 2 = 3(2k) + 2 ⇒ 3n + 2 = 6k + 2 ⇒ 3n + 2 = 2 (3k + 1)︸︷︷︸

t

� 3n + 2 = 2t , para t ∈ Z


� Contradição: ‘3n + 2 é ímpar ’ e ‘3n + 2 é par ’.

� Portanto, (p → q) pois [(p ∧ ¬q) → 0] ≡ (p → q)[email protected] (IFMG) Matemática Discreta 16 de janeiro de 2013 41 / 55

Prova por ContradiçãoTeorema (Forma p → q)

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


� (p ∧ ¬q): ‘a, b ∈ Z’ e ‘a2 − 4b = 2’.





� (p ∧ ¬q): ‘a, b ∈ Z’ e ‘a2 − 4b = 2’.

� a2 − 4b = 2 ⇒ a2 = 4b + 2 ⇒ a2 = 2(2b + 1) . Se a2 é par, a é par⋆.





� (p ∧ ¬q): ‘a, b ∈ Z’ e ‘a2 − 4b = 2’.


� a2 − 4b = 2 ⇒ (2k)2 − 4b = 2 ⇒ 4k2 − 4b = 2 ⇒ 2k2 − 2b = 1





� (p ∧ ¬q): ‘a, b ∈ Z’ e ‘a2 − 4b = 2’.


� a2 − 4b = 2 ⇒ (2k)2 − 4b = 2 ⇒ 4k2 − 4b = 2 ⇒ 2k2 − 2b = 1

� 2 (k2 − b)︸︷︷︸

t

= 1 ⇒ 1 = 2t





� (p ∧ ¬q): ‘a, b ∈ Z’ e ‘a2 − 4b = 2’.


� a2 − 4b = 2 ⇒ (2k)2 − 4b = 2 ⇒ 4k2 − 4b = 2 ⇒ 2k2 − 2b = 1

� 2 (k2 − b)︸︷︷︸

t

= 1 ⇒ 1 = 2t

� Contradição: ‘1 é ímpar’ e ‘1 é par’





� (p ∧ ¬q): ‘a, b ∈ Z’ e ‘a2 − 4b = 2’.


� a2 − 4b = 2 ⇒ (2k)2 − 4b = 2 ⇒ 4k2 − 4b = 2 ⇒ 2k2 − 2b = 1

� 2 (k2 − b)︸︷︷︸

t

= 1 ⇒ 1 = 2t

� Contradição: ‘1 é ímpar’ e ‘1 é par’

� Portanto (p → q), pois [(p → q) → 0] ≡ (p → q).



Use prova por contradição para demonstrar as seguintes afirmações:

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

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

.


Prova por EquivalênciaA prova por equivalência é usada para provar teoremas na forma (p ↔ q).

Para mostrar (p ↔ q), devemos mostrar que (p → q) e (q → p) são ambosverdadeiros.

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

Útil em teoremas que declaram que p1 ↔ p2 ↔ · · · ↔ pn

Número de demonstrações a fazer:

∀i ∀j, i 6= j, (pi → pj): n2 − n , ou

[p1 ↔ p2 · · · ↔ pn] ≡ [(p1 → p2) ∧ (p2 → p3) · · · ∧ (pn → p1)]: n

Em cada demonstração, podemos usar

Prova Direta

Prova Indireta



TeoremaPara n ∈ Z, n é par, n − 1 é ímpar e n2 é par são equivalentes.

Prova por Equivalência.Prova Direta de (p1 → p2):� (p1) n = 2k





� n − 1 = (2k)− 1 ⇒ n − 1 = 2k − 1 (p2)





� n − 1 = (2k)− 1 ⇒ n − 1 = 2k − 1 (p2)

Prova Direta de (p2 → p3):� (p2) n − 1 = 2k + 1 ⇒ n = 2k + 2





� n − 1 = (2k)− 1 ⇒ n − 1 = 2k − 1 (p2)


� (n)2 = (2k + 2)2 ⇒ n2 = 4k2 + 8k + 4 (p3) ⇒ n2 = 2t





� n − 1 = (2k)− 1 ⇒ n − 1 = 2k − 1 (p2)


� (n)2 = (2k + 2)2 ⇒ n2 = 4k2 + 8k + 4 (p3) ⇒ n2 = 2t

Prova Contrapositiva de (p3 → p1):� (¬p1) n = 2k + 1





� n − 1 = (2k)− 1 ⇒ n − 1 = 2k − 1 (p2)


� (n)2 = (2k + 2)2 ⇒ n2 = 4k2 + 8k + 4 (p3) ⇒ n2 = 2t

Prova Contrapositiva de (p3 → p1):� (¬p1) n = 2k + 1

� (n)2 = (2k + 1)2 ⇒ n2 = 4k2 + 4k + 1 ⇒ n2 = 2t + 1 (¬p3)


Prova por Contra-ExemploA prova por contra-exemplo é usada quando

Uma declaração ∀x ∈ D(P(x)) ou ∀x ∈ D(P(x) → Q(x)) parece falsa

Não conseguimos demonstrar isso pelas técnicas conhecidas

Mas podemos tentar encontrar um contra-exemplo.

Contra-exemplo : valor de a ∈ D para o qual

P(a) é falso, em declarações ∀x ∈ D(P(x))

P(a) é verdadeiro e Q(a) é falso, em declarações ∀x ∈ D(P(x) → Q(x))

Declaração Dedução Explicação

∀x ∈ D(P(x)) ∃ a ∈ D (¬P(a))Encontrar um elemento a ∈ D para oqual P(a) é falso. Se isso ocorrer, entãoa declaração ∀x ∈ D(P(x)) é falsa.

∀x ∈ D(P(x) → Q(x)) ∃a ∈ D(P(a) ∧ ¬Q(a))

Encontrar um elemento a ∈ D para oqual P(a) é verdadeiro e Q(a) é falso.Se existir tal elemento, então a sentença∀x ∈ D(P(x) → Q(x)) é falsa



TeoremaPara todo a,b ∈ R, [(a2 = b2) → (a = b)]. Prove que a declaração é falsa.

Prova por Contra-Exemplo.

� Sejam P(a, b): ‘(a2 = b2)’, e seja Q(a, b): ‘(a = b)’.






� a = 4 e b = −4






� a = 4 e b = −4

� P(4,−4) é verdadeiro






� a = 4 e b = −4


� Q(4,−4) é falso






� a = 4 e b = −4


� Q(4,−4) é falso

� ∴ 4 e −4 são um contra-exemplo para ∀ a, b ∈ R (P(a, b) → Q(a, b)).



TeoremaCada inteiro positivo é a soma dos quadrados de dois inteiros. Prove que aafirmação é falsa.


� Seja P(x): ‘n = a2 + b2’.





� Seja P(x): ‘n = a2 + b2’.

� P(0) : 0 = 02 + 02 (Verdadeiro)





� Seja P(x): ‘n = a2 + b2’.

� P(0) : 0 = 02 + 02 (Verdadeiro)

� P(1) : 1 = 12 + 02 (Verdadeiro)





� Seja P(x): ‘n = a2 + b2’.

� P(0) : 0 = 02 + 02 (Verdadeiro)

� P(1) : 1 = 12 + 02 (Verdadeiro)

� P(2) : 2 = 12 + 12 (Verdadeiro)





� Seja P(x): ‘n = a2 + b2’.

� P(0) : 0 = 02 + 02 (Verdadeiro)

� P(1) : 1 = 12 + 02 (Verdadeiro)

� P(2) : 2 = 12 + 12 (Verdadeiro)

� P(3) : 3 =??+?? (Falso)





� Seja P(x): ‘n = a2 + b2’.

� P(0) : 0 = 02 + 02 (Verdadeiro)

� P(1) : 1 = 12 + 02 (Verdadeiro)

� P(2) : 2 = 12 + 12 (Verdadeiro)

� P(3) : 3 =??+?? (Falso)

� Portanto, 3 é um contra-exemplo de ∀x ∈ Z(P(x)).


Prova por Divisão em CasosUma prova por divisão em casos ocorre quando

Existem múltiplos casos a examinar antes de determinar a verdade dadeclaração

Todos os casos devem ser cobertos

Existem informações extras sobre cada caso que ajudam a desenvolvera prova

.



TeoremaDois números inteiros consecutivos quaisquer tem paridade oposta.

Prova por Divisão em Casos.Caso 1 (m é par):





� m = 2k , k ∈ Z (par)





� m = 2k , k ∈ Z (par)

� m + 1 = (2k) + 1 ⇒ m + 1 = 2k + 1 (ímpar)





� m = 2k , k ∈ Z (par)

� m + 1 = (2k) + 1 ⇒ m + 1 = 2k + 1 (ímpar)

Caso 2 (m é ímpar):





� m = 2k , k ∈ Z (par)

� m + 1 = (2k) + 1 ⇒ m + 1 = 2k + 1 (ímpar)


� m = 2k + 1 , k ∈ Z (ímpar)





� m = 2k , k ∈ Z (par)

� m + 1 = (2k) + 1 ⇒ m + 1 = 2k + 1 (ímpar)


� m = 2k + 1 , k ∈ Z (ímpar)

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





� m = 2k , k ∈ Z (par)

� m + 1 = (2k) + 1 ⇒ m + 1 = 2k + 1 (ímpar)


� m = 2k + 1 , k ∈ Z (ímpar)

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

� m + 1 = 2t (par)





� m = 2k , k ∈ Z (par)

� m + 1 = (2k) + 1 ⇒ m + 1 = 2k + 1 (ímpar)


� m = 2k + 1 , k ∈ Z (ímpar)

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

� m + 1 = 2t (par)

� Portanto, dois inteiros quaisquer consecutivos tem paridade oposta.



Definição (Módulo)O módulo de um número c é |c| = c se c ≥ 0, ou |c| = −c se c < 0.

TeoremaMostre que |xy | = |x | · |y | para x e y números reais.

Prova por Divisão em Casos.Caso 1: x ≥ 0 e y ≥ 0:� x ≥ 0 e y ≥ 0: xy ≥ 0






� xy ≥ 0 ⇒ |xy | = xy






� xy ≥ 0 ⇒ |xy | = xy

� xy ≥ 0 ⇒ xy = (x)(y) = |x | · |y |






� xy ≥ 0 ⇒ |xy | = xy

� xy ≥ 0 ⇒ xy = (x)(y) = |x | · |y |

Caso 2: x ≥ 0 e y < 0:� x ≥ 0 e y < 0: xy < 0






� xy ≥ 0 ⇒ |xy | = xy

� xy ≥ 0 ⇒ xy = (x)(y) = |x | · |y |

Caso 2: x ≥ 0 e y < 0:� x ≥ 0 e y < 0: xy < 0

� xy < 0 ⇒ |xy | = −xy






� xy ≥ 0 ⇒ |xy | = xy

� xy ≥ 0 ⇒ xy = (x)(y) = |x | · |y |

Caso 2: x ≥ 0 e y < 0:� x ≥ 0 e y < 0: xy < 0

� xy < 0 ⇒ |xy | = −xy

� xy < 0 ⇒ −xy = (x)(−y) = |x | · |y |






� xy ≥ 0 ⇒ |xy | = xy

� xy ≥ 0 ⇒ xy = (x)(y) = |x | · |y |

Caso 2: x ≥ 0 e y < 0:� x ≥ 0 e y < 0: xy < 0

� xy < 0 ⇒ |xy | = −xy

� xy < 0 ⇒ −xy = (x)(−y) = |x | · |y |

Caso 3: x < 0 e y ≥ 0:� x < 0 e y ≥ 0: xy < 0






� xy ≥ 0 ⇒ |xy | = xy

� xy ≥ 0 ⇒ xy = (x)(y) = |x | · |y |

Caso 2: x ≥ 0 e y < 0:� x ≥ 0 e y < 0: xy < 0

� xy < 0 ⇒ |xy | = −xy

� xy < 0 ⇒ −xy = (x)(−y) = |x | · |y |

Caso 3: x < 0 e y ≥ 0:� x < 0 e y ≥ 0: xy < 0

� xy < 0 ⇒ |xy | = −xy = (−x)(y)






� xy ≥ 0 ⇒ |xy | = xy

� xy ≥ 0 ⇒ xy = (x)(y) = |x | · |y |

Caso 2: x ≥ 0 e y < 0:� x ≥ 0 e y < 0: xy < 0

� xy < 0 ⇒ |xy | = −xy

� xy < 0 ⇒ −xy = (x)(−y) = |x | · |y |

Caso 3: x < 0 e y ≥ 0:� x < 0 e y ≥ 0: xy < 0

� xy < 0 ⇒ |xy | = −xy = (−x)(y)

� xy < 0 ⇒ (−x)(y) = |x | · |y |






� xy ≥ 0 ⇒ |xy | = xy

� xy ≥ 0 ⇒ xy = (x)(y) = |x | · |y |

Caso 2: x ≥ 0 e y < 0:� x ≥ 0 e y < 0: xy < 0

� xy < 0 ⇒ |xy | = −xy

� xy < 0 ⇒ −xy = (x)(−y) = |x | · |y |

Caso 3: x < 0 e y ≥ 0:� x < 0 e y ≥ 0: xy < 0

� xy < 0 ⇒ |xy | = −xy = (−x)(y)

� xy < 0 ⇒ (−x)(y) = |x | · |y |

Caso 4: x < 0 e y < 0:� x < 0 e y < 0: xy ≥ 0






� xy ≥ 0 ⇒ |xy | = xy

� xy ≥ 0 ⇒ xy = (x)(y) = |x | · |y |

Caso 2: x ≥ 0 e y < 0:� x ≥ 0 e y < 0: xy < 0

� xy < 0 ⇒ |xy | = −xy

� xy < 0 ⇒ −xy = (x)(−y) = |x | · |y |

Caso 3: x < 0 e y ≥ 0:� x < 0 e y ≥ 0: xy < 0

� xy < 0 ⇒ |xy | = −xy = (−x)(y)

� xy < 0 ⇒ (−x)(y) = |x | · |y |

Caso 4: x < 0 e y < 0:� x < 0 e y < 0: xy ≥ 0

� xy ≥ 0 ⇒ |xy | = xy = (−x)(−y)






� xy ≥ 0 ⇒ |xy | = xy

� xy ≥ 0 ⇒ xy = (x)(y) = |x | · |y |

Caso 2: x ≥ 0 e y < 0:� x ≥ 0 e y < 0: xy < 0

� xy < 0 ⇒ |xy | = −xy

� xy < 0 ⇒ −xy = (x)(−y) = |x | · |y |

Caso 3: x < 0 e y ≥ 0:� x < 0 e y ≥ 0: xy < 0

� xy < 0 ⇒ |xy | = −xy = (−x)(y)

� xy < 0 ⇒ (−x)(y) = |x | · |y |

Caso 4: x < 0 e y < 0:� x < 0 e y < 0: xy ≥ 0

� xy ≥ 0 ⇒ |xy | = xy = (−x)(−y)

� xy ≥ 0 ⇒ (−x)(−y) = |x | · |y |






� xy ≥ 0 ⇒ |xy | = xy

� xy ≥ 0 ⇒ xy = (x)(y) = |x | · |y |

Caso 2: x ≥ 0 e y < 0:� x ≥ 0 e y < 0: xy < 0

� xy < 0 ⇒ |xy | = −xy

� xy < 0 ⇒ −xy = (x)(−y) = |x | · |y |

Caso 3: x < 0 e y ≥ 0:� x < 0 e y ≥ 0: xy < 0

� xy < 0 ⇒ |xy | = −xy = (−x)(y)

� xy < 0 ⇒ (−x)(y) = |x | · |y |

Caso 4: x < 0 e y < 0:� x < 0 e y < 0: xy ≥ 0

� xy ≥ 0 ⇒ |xy | = xy = (−x)(−y)

� xy ≥ 0 ⇒ (−x)(−y) = |x | · |y |


Prova ExistencialUma prova existencial é usada em teoremas que afirmam que objetos deum determinado tipo existem.

Teoremas desta forma são denotados por ∃x ∈ D(P(x))

Prova existencial construtiva

consiste em encontrar uma testemunha a tal que P(a) seja verdadeiro

TeoremaExiste um inteiro que é par e primo.

Prova Existencial Construtiva.� Seja P(x): ‘x é par e x é primo’ e seja o teorema ∃xP(x)








� Testemunha: 2








� Testemunha: 2

� Testemunha: 2 ∈ Z e 2 = 2k , para k = 1 ∴ 2 é par








� Testemunha: 2


� Testemunha: 2 é primo, pois apenas 1 e ele mesmo dividem 2








� Testemunha: 2


� Testemunha: 2 é primo, pois apenas 1 e ele mesmo dividem 2

� Logo, ∃xP(x) é verdadeiro.


Prova de Unicidade

Uma prova de unicidade é usada em teoremas que afirmam que existeapenas um objeto que satisfaz uma determinada propriedade.

Uma prova por unicidade envolve duas partes:

Provar existência: mostrar que existe um elemento x com a propriedade

Provar unicidade: mostrar que

se x 6= y , então y não tem essa propriedade, ou

se x e y tem a propriedade, então x = y

.


Prova de Unicidade

TeoremaSe a e b são números reais e a 6= 0, então há um único número real r tal quear + b = 0

Prova de Unicidade.Provar existência :� ar + b = 0 ⇒ ar = −b ⇒ r = − b/a


Prova de Unicidade



� com r = − b/a, a igualdade ar + b = 0 torna-se verdadeira


Prova de Unicidade




� Logo, ∃r ∈ R(ar + b = 0).


Prova de Unicidade




� Logo, ∃r ∈ R(ar + b = 0).

Provar unicidade :� Seja s ∈ R tal que as + b = 0


Prova de Unicidade




� Logo, ∃r ∈ R(ar + b = 0).


� se s satisfaz a igualdade as + b = 0, então s = − b/a


Prova de Unicidade




� Logo, ∃r ∈ R(ar + b = 0).


� se s satisfaz a igualdade as + b = 0, então s = − b/a

� Logo, r = s.


Provas

Apresente um contra-exemplo para a afirmação

Toda figura geométrica com quatro ângulos retos é um quadrado.

Use prova por divisão em casos para demonstrar as seguintes afirmações:

Se n é um inteiro, então 3n2 + n + 14 é par.

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

.


Documents

Bacharelado em Ciência da Computação Matemática Discreta · 2 Dedução e Provas 3 Métodos de Prova Exaustão Vacuidade Trivial Direta Contraposição Contradição Prova por