Módulo 1: Métodos de Prova de Teoremas

•UNIVERSIDADE FEDERAL DE CAMPINA GRANDE

•CENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA

•DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO

•Professor Ulrich Schiel

•UNIVERSIDADE FEDERAL DE CAMPINA GRANDE

•CENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA

•DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO

•Professor Ulrich Schiel

•UNIVERSIDADE FEDERAL DE CAMPINA GRANDE

•CENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA

•DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO

•Professor Ulrich Schiel

Prova

• Filosofia (silogismo)

• Direito (elemento de convicção ao julgamento)

• Lógica (Linguagem, Axiomas, Regras de Dedução)

• Matemática (comprovar uma conjectura a partir de axiomas e regras)

É um procedimento sistemático de determinar a veracidade de um novo fato a partir de fatos conhecidos

Métodos de Prova de Teoremas

Teoremas matemáticos são expressos, geralmente, na forma:

“Se P então Q”

onde P e Q representam sentenças simples ou compostas.

Exemplos:

• Se A B, então A B = A• Se um número inteiro é divisível por 6, então ele é

divisível também por 3• Se x é primo e maior que 2 então x é ímpar.

Teorema = Conjectura + Prova

Provar/demonstrar a conjectura (“se P então Q”) é

deduzir/inferir Q (conclusão/tese) a partir de P

(hipótese/premissa) usando axiomas e regras da lógica

e conhecimento específico sobre o assunto ou domínio.

Uma conjectura passa a se chamar um teorema depois

de provada.

• Conjectura: (se P então Q)• Tese: Q• Hipótese: P

Teoria

a partir de axiomas e teoremas aplica-se regras de dedução para obter novos teoremas.

• Linguagem: (fórmulas bem formadas)• Axiomas: [(x=y e P(x)) então P(y) - substituição]• Regras de dedução: (modus ponens)

Prova: Abordagens

Negar (refutar) ou Demonstrar (provar)

Negar (refutar):

Procurar um exemplo (contra-exemplo) no qual P é verdadeiro e Q é falso

Exemplos:

• Todo inteiro menor que 10 é maior que 5

– Reescrevendo:

– Se um inteiro é menor que 10, então ele é maior que 5.• contra-exemplo: 3

• A soma de quaisquer três inteiros consecutivos é par.

• contra-exemplo: 2+3+4 é ímpar.

Refutação

• Assumir a conjectura e chegar a um absurdo

• Encontrar um contra-exemplo.

Refutação

• Um único contra-exemplo é suficiente para se refutar a conjectura

• procurar um contra-exemplo e não achá-lo não constitui prova de que a conjectura é verdadeira

• ainda que um simples contra-exemplo seja suficiente para refutar a conjectura, muitos exemplos não provam a suposição. Eles simplesmente fortalecem sua inclinação a procurar uma demonstração.

• (única exceção quando se está fazendo uma asserção sobre uma coleção finita) – Exemplo: “entre 20 e 30 só existem dois números primos”

Demonstrar/Provar

Demonstração direta: “Se P, então Q”

• Assume-se a hipótese P como verdadeira e procura-

se deduzir a tese Q

Exemplo:

Se um inteiro é divisível por 6 então ele também é divisível por 3

Se um inteiro é divisível por 6 então ele é também divisível por 3

HípóteseHípótese: x é divisível por 6

1. x = 6.k , para algum inteiro k (definição de divisibilidade)

2. 6 = 2.3 (fato numérico)

3. x =(2.3). k (substituição (2) em (1))

4. x = (3.2). k (comutatividade do produto)

5. x = 3.(2.k) (associatividade do produto)

6. 2.k é inteiro (propriedade dos inteiros)

7. x = 3.m , para o inteiro m = 2.k

ConclusãoConclusão: x é divisível por 3 (definição de divisibilidade)

Se um inteiro é divisível por 6 então duas vezes o inteiro é divisível por 4

HípóteseHípótese: x é divisível por 6

• x = k.6 , para algum inteiro k (definição de divisibilidade)

• 2.x = 2.k.6 (se x=y então kx=ky)

• 2x = k.2.6 (comutatividade)

• 2x = k.12 (fato numérico)

• 2x = k.3.4 (fato numérico)

• 2x = m.4 , para inteiro m igual a k.3

ConclusãoConclusão: 2x é divisível por 4 (definição de divisibilidade)

O produto de dois pares é par

Se x e y são pares, então x.y é par.

• Hípótese: x e y são pares• x = 2m , para algum inteiro m (definição de par)• y = 2n , para algum inteiro n ( “ “ )• x.y = 2m.2n• x.y = 2.(m.2n) (associatividade)• x.y = 2.k , onde k é inteiro igual a 2mn• Conclusão: x.y é par.

Se AB então AB = A

Hipótese: AB• PARTE 1: A AB

– Para todo x A, temos x B (hipótese)– Mas, x A & x B x A B (definição de )– Logo A AB (definição de )

• PARTE 2: AB A– Para todo x AB– Então x A (definição de )– Então AB A (definição de )

• Tese: AB = A.

• definição: X = Y def X Y e Y X

Dupla implicação

Teoremas são, às vezes, enunciados na forma:

“P se, e somente, Q”

significando:

“Se P, então Q” e “Se Q, então P”

Para se provar um teorema dessa forma deve-se provar tanto uma quanto outra implicação.

Exemplo: x < y se, e somente se, x2 < y2.

x < y se, e somente se, x2 < y2

Se x < y então x2 < y2

• Hipótese: x < y• y = x + k , para algum inteiro positivo k (hipótese)• y2 = (x + k)2 (fato numérico)• y2 = x2 + 2xk + k2 (fato numérico)• y2 > x2

• Conclusão: x2 < y2

Se x2 < y2 então x < y • Hipótese: x2 < y2 • y2 = x2 + k• y = (x2 + k)½ > (x2)½ = x• Conclusão: x < y

O que acontece com x = -2 e y = 1 ???

Demonstrar/Provar

Demonstração por contraposição: “Se P então Q”

Provar “se não Q então não P” é provar “Se P então Q”

Exemplo:

Se um inteiro é divisível por 6 então ele também é divisível por 3

Contrapositiva:

Se um inteiro não é divisível por 3 então ele também não é divisível por 6.

Se um inteiro não é divisível por 3 então ele também não é divisível por 6

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

• x k.3 , p/ todo inteiro k (negação de divisibilidade)

• x (2.d).3 , para todo inteiro d (já que 2.d é inteiro)

• x d.(2.3) , para todo inteiro d (associatividade da multipl.)

• x d.6, para todo inteiro d (fato numérico)

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

• Exercício: Se o quadrado de um número é ímpar, então o número também é ímpar.

xy é ímpar se e somente se x e y são ímpares

Se x e y são ímpares então xy é ímpar• Hipótese: x e y são ímpares• x = 2n + 1 e y = 2m + 1, p/ m e n inteiros • xy = 2.(2nm+m+n) + 1• Conclusão: xy é ímpar.

Se xy é ímpar então x e y são ímpares

• Vamos provar essa parte por contraposição

Se xy é ímpar então x e y são ímpares

• Se x ou y não é ímpar então xy não é ímpar• Hípóteses:

- x é par e y é par ou - x é par e y é ímpar ou- x é ímpar e y é par

• x é par e y é par• Conclusão: x.y é par (já provado)• x é par e y é ímpar• x = 2m e y = 2n + 1, p/ m e n inteiros• xy = 2.(2mn + m)• Conclusão: xy é par.

Demonstrar/Provar

Ex.: Se um número somado a ele próprio resulta no próprio número, então ele é igual a zero.

• Hipótese:x + x = x Tese: x=0• Negação da tese: x 0• 2.x = x (hipótese e x + x = 2.x)• 2.x/x = x/x (pois x 0)• 2 = 1 Absurdo• Conclusão: x = 0.

Demonstração por contradição ou por absurdo: “Se P, então Q”Assumir “P Q” é provar “Se P então Q”

“Existem infinitos números primos”

Refutar: o número de primos é finito

• Sejam p1, p2, ..., pn todos os primos

• Seja agora k = p1 x p2 x ..., x pn + 1

• k não é divisível por nenhum pi, pois sempre resta 1

• Como todo primo é um inteiro maior que 0, k > pn

• Logo k é primo e maior que todos os outros• CONTRADIÇÃO

2½ não é um número racional

Def.: um número racional é um número que pode ser escrito na forma p/q onde p e q são inteiros, tal que p e q não têm fatores comuns além da unidade.

Por contraposição:

• Negação da tese: 2½ é racional • 2½ = p/q com p e q primos entre si (definição)• 2 = p2/q2

• 2q2 = p2

• 2 divide p2

• p2 é par• p é par (p é par – teorema anterior)• 2 divide p

2½ não é um número racional

• 4 é um fator de p2 (2 divide p)• 2q2 = p2 (já estabelecido)• 2q2 = 4k (4 é um fator de p2)• q2 = 2k• 2 divide q2 • 2 divide q

• Conclusão: 2 divide tanto de p quanto de q, contrariando a suposição inicial que p e q não tem fatores comuns além da unidade (2½ = p/q é racional)

Exercício

1) Dado uma conjectura

1. P Q, a negação de P é denotada por ~P, chamamos

2. ~Q ~P de contrapositiva

3. Q P de recíproca

4. ~P ~Q de condicional inverso

a) Quais são equivalentes?

b) Dado “Todo número par entre 4 e 12 é uma soma de dois primos”, Identifique P e Q e dê suas contrapositivas, recíprocas e condicional inverso e mostre quais são teoremas.

2) Prove que “se x é positivo então x+1 é positivo”

a) por contraposição

b) por contradição (absurdo)

Demonstrar/Provar - Princípio da Indução Finita

Demonstração por indução:

“Todo inteiro positivo x tem a propriedade P”

nP(n)

Se pudermos mostrar que:

1. P(1) é verdadeiro, ou seja, 1 tem a propriedade;

2. P(k)P(k+1), ou seja se um inteiro qualquer tem a propriedade P então o inteiro seguinte também a tem;

Então a conjectura nP(n) é verdadeira (é um teorema).

Prova por Indução

Passos:

• provar a veracidade de P(1); (base da indução)

• Admitir P(k) como verdadeiro (hipótese de indução)

• demonstrar que, P(k+1) é verdadeiro;

exemplo de prova por indução

Provar que a equação 1 + 3 + 5 +...+ (2n - 1) = n2 é verdadeira para qualquer inteiro positivo n.• Base de indução: P(1) é verdadeira, ou seja, 1 = 12.• Hipótese de indução:

P(k) : 1 + 3 + 5 + ... + (2k - 1) = k2 • Temos que mostrar então:

P(k+1): 1 + 3 + 5 + ... + (2k - 1) + [2(k+1) - 1] = (k+1)2

•

1 + 3 + 5 +...+ (2k - 1) = k2

1 + 3 + 5 + ... + (2k - 1) + [2(k + 1) - 1] = k2 + [2(k + 1) - 1] (hipótese de indução) = k2 + [2k + 2 - 1] = k2 + 2k + 1 = (k + 1)2

ou seja, 1 + 3 + 5 + ... + [2(k+1) - 1] = (k+1)2

então, como P(1) e P(k)P(k+1), para k arbitrário, podemos afirmar que xP(x), ou seja: 1 + 3 + 5 +...+ (2n - 1) = n2 é verdadeira para qualquer inteiro positivo n.

exemplo de prova por indução

Provar que a equação 1+2+3+...+n = n(n+1)/2 é verdadeira para qualquer inteiro positivo n.• P(1) é verdadeira, ou seja, 1 = 1(1+1)/2.• Hipótese de indução: P(k)

1 + 2 + 3 + ... + k = k(k+1)/2• Temos que mostrar então: P(k+1)

1 + 2 + 3 + ... + k + (k+1) = (k+1)[(k+1)+1]/2• O lado esquerdo dessa expressão pode ser reescrito como:

k(k+1)/2 + (k+1) (pela hipótese de indução)

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

• = k(k+1)/2 + (k+1)• = (k+1) (k/2 + 1)• = (k+1) (k/2 + 2/2)• = (k+1)(k+2)/2• = (k+1)[(k+1)+1]/2

ou seja, 1 + 2 + 3 + ... + k + (k+1) = (k+1)[(k+1)+1]/2.

então, como P(1) e P(k)P(k+1), para k arbitrário, podemos afirmar que xP(x), ou seja:

1 + 2 + 3 +...+ n = n(n+1)/2 para todo inteiro n.

Indução completa

Passos:

• estabelecer a veracidade de P(1); (base da indução)

• assumir a veracidade de P(r) para todos os inteiros r entre 1 e um inteiro arbitrário k; (hipótese de indução);

• provar a veracidade de P(k+1);

• Então, podemos afirmar que todo inteiro positivo tem a propriedade P, ou xP(x).

Exercício

• Mostre, por indução completa que, para a seqüência de Fibonacci, vale a relação

F(n) < 2n

• N.B. A seqüência de Fibonacci é dada por

F(1)=1;

F(2)=2 e • F(n)=F(n-1) + F(n-2)), para n>2

Exercícios

Provar uma das duas fórmulas abaixo: • a fórmula para a soma dos n primeiros termos de uma progressão geométrica (n 1) é:

a + ar + ar2 +...+ arn-1 = (a-arn)/(1-r).• a fórmula para a soma dos n primeiros termos de uma progressão aritmética (n1) é:

a + (a+r) + (a+2r) +...+ (a+(n-1)r) = an + r(n-1)n/2.

• Dado uma conjectura

P Q, a negação de P é denotada por P’, chamamos• Q’ P’ de contrapositiva• Q P de recíproca• P’ Q’ de condicional inverso

1. Quais são equivalentes?

2. Dado “Se n é um número par com 4 ≤ n ≤ 12, então n é uma soma de dois primos”, dê suas contrapositivas, recíprocas e condicional inverso e mostre quais são teoremas.