Apostila de Matemtica DiscretaFeito de acordo com as aulas de Flaviana 461249

Copiada por Marcus Cardoso

Unidade II - Tcnicas de demonstraoUma proporo matemtica considerada verdadeira (e depois disso chamada muitas vezes de teorema) se for provada de forma indiscutvel e com uma linguagem lgica usual sua veracidade. Nosso objetivo aqui discutir as formas de provar afirmaes matemticas com o uso de raciocnio lgico. Existem algumas tcnicas mais comuns. O que sempre preciso ter em mente que exemplos nunca provam que uma afirmativa possa ser garantida por um nmero infinitos de casos (os exemplos); mas bons exemplos (contra exemplos) garantem que uma afirmao falsa. Ex: Qual o valor logico das afirmaes? Justifique a) Todo inteiro maior do que zero menor do que dez. Falsa: 11 > 0; mas 11 no menor do que 10. b) Todo inteiro entre 1 e 40 que divisvel por 9 tambm divisvel por 3. Verdadeiro: No intervalo indicado, os inteiros divisveis por 9 so: 9,18,27 e 36. E cada um deles tambm divisvel por 3 9 = 3.3; 18 = 3.6; 27 = 3.9; 36 = 3.13 c) Todo inteiro que divisvel por 9 tambm divisvel por 3 Verdadeiro. Seja n um inteiro divisvel por 9 n = 9q para algum n = (3.3)q = 3(3q) n divisvel por 3. Observe que a prova de que c) verdadeira tambm pode ser usada para garantir que b) seja verdadeira, mas ao contrrio no. O exemplo c) poderia ser reescrito como Se n divisvel por 9, ento n divisvel por 3 Se denotarmos: A: n divisvel por 9 B: n divisvel por 3 A afirmao tem a forma AB em que o antecedente A consequente B como tese da proposio. As tcnicas 1) Demonstrao direta aquela no qual provamos uma implicao do tipo AB de forma direta partindo da hiptese A e chegando; com uso de raciocnio lgico e argumentaes verdadeiras na tese B. (Como a que fizemos no exemplo) conhecido como hiptese e o

Exerccios : Prove as seguintes proposies

a) A soma de dois inteiros pares um inteiro par. Se m e n so inteiros pares, ento m + n um inteiro par Hiptese: m e n so pares. Tese : m + n par Demonstrao Sejam m e n pares

- m + n par b)O quadrado de um inteiro mpar mpar. Se n um inteiro mpar, ento n um inteiro mpar Hiptese : n mpar Tese: n mpar Prova Seja n um inteiro mpar

n mpar c) Se n par ento n par A: Hiptese : n par B: Tese : n par No possvel mostrar direta AB, mas sabemos, por tautologia Que AB = A'B Assim AB pode ser reescrito como: BA Se n impar ento n mpar que exatamente a afirmao do exerccio. Assim temos: 2) Demonstrao na forma contrapositiva. a prova direta de A'B' a forma contrapositiva de AB Exerccio: Se m + n par, ento m e n tem a mesma paridade m + n = 2k Contrapositiva Se m . n tem paridade distinta ento m + n mpar A: Hiptese: m + n mpar B: m e n tem uma paridade.

m e n inteiros de paridade distinta.

m + n = 2(k) + (2l +1) m + n = 2(k +l) +1 m + n = mpar Exerccio 2: Prove a) m + n par b) a par A Hiptese: A Tese: B Hiptese B Tese : A A B = (AB) ^ (BA) Hip: A Tese: B Hip: B Tese: A m e n tem a mesma paridade

a par

Tcnicas de demonstraesDireta Ex: Se x e y so mpares, ento xy mpar Hiptese : x e y so mpares Tese xy mpar Demonstrao Sejam xy inteiros mpares

x = 2K + 1 e y = 2q +1 - xy = (2k + 1)(2q + 1) - xy = 2k2q + 2k + 2q + 1 - xy = 2(k2q + k + q) + 1 - xy = 2l + 1 onde l = (2kq + k + q) - xy = mpar

Contrapositiva (AB) = B A Prova direta de B A Ex: Se xy mpar, ento x e y so mpares Lembre-se AB tem recproca BA. Observe que a proposio do exemplo 2 a recproca da proposio do exemplo 1. Prova do exemplo 2. Hiptese: xy mpar A Tese: x e y so mpar B xy = 2k + 1 (2q + 1)(2l +1) = Contrapositiva: B' A' Hiptese B : x ou y par Tese A xy par Demonstrao (na forma contrapositiva) Se x ou y par Suponha sem perda de generalidade De que x par x = 2k xy = 2(ky)y xy = 2(ky)

xy par Observao : A proposio xy mpar se e somente se x e y so mpares uma equivalncia, ou seja da forma AB A demonstrao de proposio dessa forma deve ser feita em duas etapas a) A B (ida) b) B A (volta) No caso da proposio acima, a demonstrao ser formada pelas demonstraes do exemplo e volta e exemplo 2(ida) 3) Demonstrao por absurdo. baseada na tautologia

(AB) (A ^ B' 0) Onde O qualquer contradio

Tabela VerdadeA V V F F B V F V F AB V F V V A ^ B' F V F F O F F F F A ^ B' O V F V V

Numa demonstrao por absurdo (tambm conhecida como demonstrao por contradio) provamos AB atravs da prova de A ^ B' O . Para isso assumimos a hiptese e a negao da tese de AB. E chegamos a uma contradio. Exerccio: Prove as proposies a) Se um nmero somado a ele mesmo resulta no prprio nmero ento esse nmero 0. x + x = x, x = 0 Demonstrao: Suponha por absurdo que x+x=x x0 a) 2x = x e x 0 b) 2x x = 0 e x 0 c) x = 0 e x 0

CONTRADIO

b) xy mpar x e y so mpares Prova: Suponha por absurdo que (xy mpar) ^ ( x ou y par) (xy mpar) ^ ( x par um perda generalidade) (xy mpar) ^ ( x = 2k) (xy mpar) ^ ( xy = 2ky par) Absurdo Logo x e y so mpares. c) x - 5x + 6 = 0 x4 Prova: Suponha por absurdo que x -5x + 6 = 0 4 -5.4 + 6 =0 2=0 Absurdo Logo x 4

ou seja m.d.c (a,b) =1

2b 4k b = 2k b par b par Absurdo, pois a e b so pares, mas m.d.c (a,b) = 1

Induo matemtica1 Princpio de induo matemtica (1P.I.M.) Seja P(n) uma propriedade sobre os inteiros positivos que i) P(1) verdadeira ii) Se P(n) verdadeira ento P(n + 1) tambm verdadeira Ento P(n) verdadeira Uma demonstrao por induo baseada no P.I.M. Pra que o 1 P.I.M. seja usado, precisamos garantir as condies i) e ii) A condio inicial ou caso base. A condio ii) uma condicional e seu antecedente chamado de hiptese de induo. Observao: Dados inteiros a e b, dizemos que a divide b se b for mltiplo de a ou seja se existisse um inteiro x tal que b = ax Notao a|b a divide b

O exemplo quer dizer

1 P.I.M. Seja P(n) uma propriedade sobre os inteiros positivos Se valem i) P(1) V ii) P (n) verdadeira P(n+1) verdadeiras ento P(n) verdadeira todo A >1 Exerccios: 1) Mostre que a soma dos n primeiros mpares positivos n. 1 + 3 ... (2n 1) = n = 1 + 3+ 5 + 7 (2n 1) De uma forma geral

Prova do Exerccio

Por induo i) A frmula vale se n = 1

OK ii) Hiptese de induo

Vamos mostrar que

Vejamos

1 + 3 (2n 1) + (2n + 1) n + (2n + 1) pela h.i. (hiptese de induo)

Por i) e ii) pelo 1 P.I.M vale

ou seja a soma dos n mpares n 2) Prove que: 1 + 2 + 3 + n = n(n + 1) / 2

Por induo em n: i) A frmula vale se n =1

ii)

Vamos mostrar que

Vejamos

Logo por i) e ii) pelo PIM 1 + 2 + 3 + n = n(n + 1)/2 3) Voc tem uma balana de dois pratos e um conjunto de apenas uma falsa e mais leve do que as outras. Prove que a moeda falsa com apenas n passagens moedas das quais possvel descobrir qual

n=1 n=2

2 moedas 2 = 4 moedas

1 pesagem 1 pesagem

Hiptese de induo: possvel descobrir qual a moeda falsa dentre as 2 moedas com n pesagens.

Vamos garantir que para moedas precisamos de n + 1 pesagens. De fato : Se dividimos as moedas em dois grupos de 2 moedas cada (isso possvel pois ) Com a 1 boas e nos restam descobrir qual a pesagem descobrimos qual grupo tem moeda falsa . Descartamos as moedas moedas 1 falsa .Usando a hiptese de induo fazemos n pesagens para moeda falsa totalizando n + 1 pesagens. moedas ) com n pesagens.

Logo por induo possvel saber qual a moeda falsa ( dentre

Relaes de recorrnciaUma definio por recorrncia aquela feita por condio bsica onde apresentamos os primeiros casos. Passo de recorrncia, onde os casos seguintes so apresentados em dependncia dos anteriores. Exemplos: a) O fatorial de n = n! 0! = 1, n! = n(n-1)!

5! = 5.4.3! = 5.4.3.2.1! = 5.4.3.2.1.0! = 5.4.3.2.1.1

b) Sequncia de Fibonacci F1 = 1 F2 = 1

n > =3 1,1,2 uma sequncia de n definido por conforme acima. c) Potncias d) Mais sequencias

T(1) = a T (n) = a T(n 1) n=>2 T(n), n = > 1so os termos da sequencia T(1); T(2); T(3); T(4)

Dada uma definio recorrente, qualquer o grande problema encontrar uma frmula fechada que a resolva. Melhor dizendo, como encontrar uma frmula que fornea o termo de ordem n, que dependa apenas de n no dos casos anteriores.

Exerccio: Considere a definio recorrente.t(1) = 3 t(n) = 6 + t(n 1) a) Escreva os primeiros termos da sequencia T(n) T(1) = 3 T(2) = 6 + 5(2 -1) {3,9,15,21,27} b) Tente escrever uma frmula fechada para T(n); 5n = 6 + 5(n 1) = 6 + (6 + 5(n -2)) T(n) = 6 + T(n 1) = 6 + 6( + 5(n 2)) = 2.6 + 5( n 2) = 2.6 + (6 + 5(n 3) = 36 + 5(n 3) Sn = 36 + 5(n - 4) = 4.6 + 5(n - 4) = k6 + 5(n - k) Se n k = 1 k=n1 5(n) = (n 1).6 + 5(1) 5(n) = (n 1).6 + 3 5(n) = 6n 3 c) Prove a frmula fechada de b) Devemos provar que a frmula fechada da definio

S(1) = 3 S(n) = 6 + 5(n 1) n=>2 S(n) = 6n 3 i) n = 1 A frmula S(n) = 6n 3 resolve a definio S(1) = 3 S(n) = 6 + 5(n 1) Se n = 1a conjectiva diz que S(1) = 6.1 3 = 3 valor de S(1) por definio ii) Hiptese de induo A frmula S(n) = 6n 3 resolve a definio no caso n Vamos mostrar que a hiptese de induo implica que: A frmula resolve a definio no caso n + 1 Por definio S(n) = 6 + 5(n) = 6 + 6n 3 = 6 + (n + 1) 3 = S (n + 1) pela frmula fechada Logo por i) e ii) a frmula S(n) = 6n + 3 resolve a definio, todo n maior ou igual a 1 d) Determine S(1000) S(1000) = 6.1000 3 = 5997 Exerccios 2. i) Encontre uma frmula fechada para a soma

ii) Prove a frmula Soluo

a frmula fechada para a S(1) =

Prova por induo Caso base: n = 1 Por definio S(1) = Pela frmula = S(1) = 1/ (1 +1) Logo a frmula resolve a definio se n = 1 Passo de induo Hip de induo (n) A frmula fechada

Resolve a definio no caso n Para n + 1, temos Por definio

=

(n + 1) / (n + 2)