Tecnicas de Demonstracoes

Gentil Lopes da Silva

27 de novembro de 2008

Resumo:

Aqui reuniremos algumas tecnicas de demonstracoes matematicas. Acre-ditamos que todo aluno de matematica deva conhece-las.

Nota: Este e um excerto retirado de um de nossos livros.

1 Tecnicas (Engenharia) de Demonstracao

Os problemas em matematica dividem-se em duas classes:

Determinacao: calcule, encontre, ache, determine,. . .

Demonstracao: mostre, prove, demonstre,. . .

Costumo mesmo dizer que a matematica comeca com os problemas do se-gundo tipo. De fato, a resolucao da maioria dos problemas do primeiro tipo saoalgoritmicas (mecanicas); enquanto os problemas do segundo tipo exigem muitode criatividade (engenhosidade).

Um outro criterio que utilizo para distinguir nao-matematica (algoritmo)de matematica, e que a nao-matematica e susceptıvel de programacao - a exem-plo dos poderosos softwares algebricos - enquanto que a matematica em si (de-monstracoes) nao. Para se lidar com matematica torna-se indispensavel o co-nhecimento de algumas tecnicas de demonstracao.

1

Gentil 2

1.1 Operacoes Logicas sobre Proposicoes

Faremos um resumo das operacoes do calculo proposicional tambem cha-madas operacoes logicas. Os principais operadores (conectivos) logicos sao osseguintes:

∨ Disjuncao (“ou”)∧ Conjuncao (“e”)¯ Negacao−→ Condicional (“se...entao”)←→ Bicondicional (“se e somente se”)

cujas tabelas-verdade sao dadas a seguir∗

p q p∨q

V V V

V F V

F V V

F F F

p q p∧q

V V V

V F F

F V F

F F F

p p

V F

F V

p q p−→ q

V V V

V F F

F V V

F F V

p q p←→ q

V V V

V F F

F V F

F F V

p p q p∨q

V F V V

V F F F

F V V V

F V F V

Acrescentamos a tabela-verdade da proposicao p∨q a qual nos sera de grandeutilidade.

1.1.1 Equivalencias Notaveis

A seguir listamos algumas equivalencias entre proposicoes, as quais podemser demonstradas com o auxılio das respectivas tabelas-verdade.

1) ¯p⇐⇒ p (Dupla Negacao)

2) Leis Idempotentes

a) p ∨ p⇐⇒ p

b) p ∧ p⇐⇒ p

3) Leis Comutativas

a) p ∨ q ⇐⇒ q ∨ p

b) p ∧ p⇐⇒ q ∧ p

4) Leis Associativas

a) p ∨ (q ∨ r)⇐⇒ (p ∨ q) ∨ r

b) p ∧ (q ∧ r)⇐⇒ (p ∧ q) ∧ r

∗Estas tabelas definem os respectivos operadores.

Gentil 3

5) Leis de De Morgan∗

a) ( p ∨ q ) ⇐⇒ p ∧ q

b) ( p ∧ q ) ⇐⇒ p ∨ q

6) Leis Distributivas

a) p ∧ ( q ∨ r ) ⇐⇒ (p ∧ q) ∨ (p ∧ r)

b) p ∨ ( q ∧ r ) ⇐⇒ (p ∨ q) ∧ (p ∨ r)

1. Proposicoes Aparentadas

p −→ q : Direta

q −→ p : Recıproca

p −→ q : Contraria

q −→ p : Contrapositiva (contra-recıproca)

2. Equivalencia Entre Proposicoes Aparentadas

2.1 A proposicao direta equivale a contra-recıproca.

p −→ q ⇐⇒ q −→ p

Para provar isto faremos uso da seguinte identidade:

p −→ q = p ∨ q

Esta identidade pode ser obtida das respectivas tabelas-verdade.Prova:

(i) p −→ q = p ∨ q

(ii) q −→ p = ¯q ∨ p

= p ∨ q

�

Isto significa que as proposicoes p −→ q e q −→ p assumemsempre os mesmos valores logicos; isto e, ou sao ambas verdadeiras(V ) ou sao ambas falsas (F ). Consultando a tabela do bicondicionalconcluimos que a proposicao

(

p −→ q)

←→(

q −→ p)

e tautologica. Logo, estas proposicoes sao equivalentes, isto e

p −→ q ⇐⇒ q −→ p

Sendo assim acabamos de estabelecer nossa primeira tecnica dedemonstracao indireta:

∗Augustus De Morgan (1806 − 1873) lecionou no University College, Londres. Foi ma-tematico e logico, e contribuiu para preparar o caminho da Logica matematica moderna.

Gentil 4

(T-1) O teorema direto equivale ao contra-recıproco†

H =⇒ T ⇐⇒ T =⇒ H

Enunciemos nossa segunda tecnica de demonstracao indireta:

(T-2) Anexacao a hipotese da negacao da tese

H =⇒ T ⇐⇒(

H ∧ T)

=⇒ T

Prova: Provemos a seguinte equivalencia:

p −→ q ⇐⇒(

p ∧ q)

−→ q

De fato,

(i) p −→ q = p ∨ q.

(ii) p ∧ q −→ q = (p ∧ q) ∨ q

= ( p ∨ ¯q ) ∨ q

= p ∨ q ∨ q

= p ∨ q.

�

(T-3) Reducao ao absurdo

H =⇒ T ⇐⇒(

H ∧ T)

=⇒ f

Onde: f e uma proposicao de valor logico falso (e qualquer con-tradicao).

Prova: Provemos a seguinte equivalencia:

p −→ q ⇐⇒(

p ∧ q)

−→ f

De fato,

(i) p −→ q = p ∨ q.

(ii) p ∧ q −→ f = (p ∧ q) ∨ f

= (p ∧ q)

= p ∨ ¯p

= p ∨ p.

�

Nota: Na tabela-verdade da proposicao p ∨ q vemos que quando ovalor logico de q e F , prevalece o valor logico de p. Estamos dizendoque p ∨ f = p.

†H: Hipotese, T : Tese, H: Negacao da hipotese, T : Negacao da tese.

Gentil 5

1.1.2 Uma Equivalencia Notavel

Uma das equivalencias mais utilizadas em demonstracoes ma-tematicas e a que segue

(T-4) Teorema com hipotese composta (∧)Se a hipotese de um teorema e formada pela conjuncao de duas

outras, e valida a seguinte equivalencia

(

H1∧H

2

)

=⇒ T ⇐⇒(

H1∧ T

)

=⇒ H2

Isto e, junta-se a uma das hipoteses a negacao da tese e demonstra-se a negacao da outra hipotese.

Prova: Provemos a seguinte equivalencia

p ∧ q −→ r ⇐⇒ p ∧ r −→ q

De fato,

p ∧ q −→ r = (p ∧ q) ∨ r

= (p ∨ q) ∨ r

= p ∨ q ∨ r.

Por outro lado,

p ∧ r −→ q = (p ∧ r) ∨ q

= (p ∨ ¯r) ∨ q

= p ∨ r ∨ q.

�

Vejamos alguns exemplos de aplicacao desta equivalencia:

1o) Em teoria dos numeros: Se a divide b e a nao divide c entao b nao divide c.

H1

: a|b⇒ T: b 6 | c.

H2

: a 6 | c

H1∧ T =⇒ H

2

Prova: Para algum n1

e algum n2

inteiros, resulta

H1

:b

a= n

1

=⇒c

b=

c

a · n1

= n2

T :c

b= n

2

Observe quec

a= n

1· n

2≡ H

2

�

Gentil 6

2o) Em Analise:

Se a ≤ b e b ≤ a entao a = b.

H1

: a ≤ b

⇒ T: a = b.H

2: b ≤ a

H1∧ T =⇒ H

2

Prova: Suponha a ≤ b e a 6= b, entao a < b. �

3o) Em Analise:

Se n ∈ N, x ∈ R, e n < x < n + 1, entao x 6∈ N.

H1

: x > n

⇒ T: x 6∈ N.H

2: x < n + 1

H1∧ T =⇒ H

2

Prova: Se x > n e x ∈ N entao x ≥ n + 1. �

4o) Em Teologia (Unicidade de Deus)Suponhamos que existam dois Deuses D e D′:

H1

: D e Deus⇒ T: D = D′

H2

: D′ e Deus

Prova: H1∧ T : Suponhamos que D e Deus e que D 6= D′. Entao existe

algum atributo em D nao partilhado por D′, por conseguinte D′ nao eDeus, o que contraria H

2. �

Corolario 1. Jesus Cristo nao e Deus.

Sugestao: Quando voce estudante encontrar-se frente a um teorematipo

H1∧H

2=⇒ T

e, apos bater o desespero (ou antes mesmo), tente demonstrar o equivalente

H1∧ T =⇒ H

2

(T-5) O seguinte teorema nao e raro em matematica:

H1⇐⇒

(

H2

=⇒ T)

Gentil 7

E um teorema, tipo “se e somente se”, isto e

H1

=⇒(

H2

=⇒ T)

H1⇐=

(

H2

=⇒ T)

Entao

(i) H1

=⇒(

H2

=⇒ T)

Observemos que a tese do teorema acima e um outro teorema. Istosignifica que assumindo H

1devemos demonstrar H

2=⇒ T . Isto e, deve-

mos mostrar que H2

acarreta T . Ainda,

H1∧H

2=⇒ T

Esta conclusao pode ser provada assim:

H1−→

(

H2−→ T

)

= H1∨

(

H2−→ T

)

= H1∨

(

H2∨ T

)

= (H1∧H

2) ∨ T

= H1∧H

2−→ T.

Portanto subsiste a seguinte equivalencia

H1

=⇒(

H2

=⇒ T)

⇐⇒(

H1∧H

2=⇒ T

)

(ii)(

H2

=⇒ T)

=⇒ H1

Consideremos a contrapositiva: H1

=⇒(

H2

=⇒ T)

. Entao,

H1−→

(

H2−→ T

)

= H1−→

(

H2∨ T

)

= H1−→ H

2∧ T

Portanto subsiste a seguinte equivalencia(

(H2

=⇒ T ) =⇒ H1

)

⇐⇒(

H1

=⇒ H2∧ T

)

(T-6) Teorema com hipotese composta (∨)Se a hipotese de um teorema e formada pela disjuncao de duas outras,

e valida a seguinte equivalencia

(

H1∨H

2

)

=⇒ T ⇐⇒(

H1

=⇒ T)

∧(

H2

=⇒ T)

Prova: Provemos a seguinte equivalencia

p ∨ q −→ r ⇐⇒(

p −→ r)

∧(

q −→ r)

De fato,

p ∨ q −→ r = (p ∨ q) ∨ r

= (p ∧ q) ∨ r

=(

p ∨ r)

∧(

q ∨ r)

=(

p −→ r)

∧(

q −→ r)

�