Slide - Aula 8 O Princípio da Definição Recursiva - Matemática Discreta 2021-2

Matematica Discreta — Aula 08 — = O principio da definicdo recursiva Jamil Abreu UFLA/ICET/DMM Lavras/MG Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 1/30 Comecemos esta aula retomando o seguinte resultado da aula passada. Se B ⊂ N ´e infinito ent˜ao B ´e enumer´avel. Vamos definir uma bije¸c˜ao f : N → B. Procedemos por indu¸c˜ao. Definimos primeiramente f (1) = menor elemento de B. Supondo que f (1), f (2), . . . , f (n) tenham sido definidos, definimos f (n + 1) = menor elemento de B − {f (1), . . . , f (n)}. (Observa¸c˜ao: {f (1), . . . , f (n)} = f ({1, . . . , n}).) Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 2 / 30 O conjunto B − f ({1, . . . , n}) ´e n˜ao vazio pois, se fosse vazio ent˜ao f : {1, . . . , n} → B seria sobrejetora, o que implicaria que B ´e finito e isto ´e uma contradi¸c˜ao. Logo, f (n) est´a bem definido, pelo princ´ıpio da boa ordem. Por indu¸c˜ao, f (n) fica definido para todo n. Vejamos que f ´e uma bije¸c˜ao. Primeiro, f ´e injetiva: se m < n ent˜ao f (m) ∈ {f (1), . . . , f (n − 1)} e f (n) /∈ {f (1), . . . , f (n − 1)}. Em particular, f (m) ̸= f (n). Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 3 / 30 Vejamos que f ´e sobrejetora. Seja p ∈ B. Como f ´e injetiva, f (N) ´e infinito, em particular f (N) n˜ao pode estar contido no conjunto {1, . . . , p}. Logo, f (n) > p para algum n. Seja m ∈ N o menor natural tal que f (m) ⩾ p (†) Assim, f (i) < p para i < m. Logo, p /∈ f ({1, . . . , m − 1}). Pela defini¸c˜ao de f , p ⩾ f (m). (…) Por (†) e (‡), f (m) = p. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 4 / 30 H´a um ponto na demonstra¸c˜ao anterior em que o princ´ıpio da indu¸c˜ao foi, podemos dizer, desvirtuado. Isto ocorreu no momento em que dissemos “Por indu¸c˜ao, f (n) fica definido para todo n.” O que diz o princ´ıpio da indu¸c˜ao? Ele diz que se A ⊂ N ´e indutivo ent˜ao A = N. Quando usamos este princ´ıpio para provar um teorema por indu¸c˜ao, o que essencialmente fazemos ´e definir A como sendo o conjunto dos n para os quais o teorema ´e verdadeiro e ent˜ao procedemos para tentar mostrar que A ´e indutivo. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 5 / 30 Na demonstracao anterior, ndo estavamos realmente provando algo por inducado mas “definindo algo por indu¢ado”, o que rigorosamente falando, ainda carece de significacdo dentro do que ja desenvolvemos até aqui. Uma suposta definicao por indu¢ao nao poderia materializar-se de outra forma que nao fosse definir o conjunto A como sendo o conjunto dos n para os quais f(n) esta definido e entado mover-se no sentido de mostrar que A é indutivo. Nesta situacdo, mostrar que A é indutivo significaria mostrar que f(n + 1) esta definido sempre que f(n) 0 esta (ou os valores f(m), para m < n). Entretanto, note a estranheza disso tudo: = por um lado, f é uma fun¢ado que, enquanto tal, ja esta definida em seu dominio desde 0 inicio (ao se escrever que A é “o conjunto dos n para os quais f(n) esta definido” ); r= por outro lado, f(n + 1) é construido ao longo da demonstra¢ao, a partir de f(n), ou seja, f é um objeto em construcao. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 6/30 Esta evidente contradi¢ao deixa claro que algo novo é necessario para tornar vidvel uma tal definicado indutiva. Este algo novo é justamente o principio da defini¢ao recursiva. Na demonstracao, a bijecdo f : N > B foi “construfda” a partir das condicoes: («) f(1) = menor elemento de B, * f(n +1) = menor elemento de B — f({1,...,n}). Esta é uma formula recursiva; ela define a funcdo f em termos de si mesma. Dizemos que uma definicdo através de uma férmula recursiva é uma definicao recursiva. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 7/30 Antes de abordarmos a forma geral do princ´ıpio da defini¸c˜ao recursiva, vamos demonstr´a-lo no caso espec´ıfico anterior. Isto tornar´a clara a ideia no caso geral. O primeiro passo consiste em mostrar que existem fun¸c˜oes definidas em segmentos {1, . . . , n} e que satisfazem (∗). Lema Para todo n ∈ N, existe uma fun¸c˜ao f : {1, . . . , n} → B que satisfaz (∗) em seu dom´ınio. O lema fala da validade de uma afirma¸c˜ao que depende de n, logo claramente sua demonstra¸c˜ao ´e suscet´ıvel `a indu¸c˜ao. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 8 / 30 Demonstracao do lema O lema é valido para n = 1, pois a func¢do f(1) = menor elemento de B estd claramente bem definida, pelo principio da boa-ordem, e satisfaz (*). Suponha o lema valido para n, isto é, existe uma funcdo fF: {1,...,n} 3B satisfazendo (*) em seu dominio: (1) = menor elemento de B, (**) tH = menor elemento de B — f({1,...,n —1}). Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 9/30 Continua¸c˜ao Defina f : {1, . . . , n, n + 1} → B por f (i) = ˇf (i) se i ∈ {1, . . . , n}, f (n + 1) = menor elemento de B − ˇf ({1, . . . , n}). Como B ´e infinito, ˇf n˜ao ´e sobrejetora, logo B − ˇf ({1, . . . , n}) ̸= ∅ e f (n + 1) est´a bem definido. Note que esta defini¸c˜ao de f ´e aceit´avel pois n˜ao define f em termos de si mesma mas em termos de ˇf . Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 10 / 30 Resta mostrar que f satisfaz (x) em seu dominio. Primeiro, f satisfaz (+) para i=1,...,n, pois f(i) = F(i) para tais valores de /, ou seja, f(1) = menor elemento de B, f(n) = menor elemento de B — f({1,...,n—1}). Como f({1,...,n}) = f({1,...,n}), temos também que f(n +1) = menor elemento de B — f({1,...,n}) = menor elemento de B — f({1,..., n}). Portanto, f satisfaz (*) para =1,...,n+1. QED Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 11/30 Lema Sejam f : {1, . . . , n} → B e f : {1, . . . , m} → B fun¸c˜oes satisfazendo (∗) em seus respectivos dom´ınios. Ent˜ao, f (i) = g(i) para todo i em ambos os dom´ınios. Se o lema fosse falso, seja k ∈ N o menor natural tal que f (k) ̸= g(k). Como f (1) = g(1) = menor elemento de B temos que k > 1. Logo, se 1 ⩽ m < k ent˜ao f (m) = g(m). Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 12 / 30 Como f e g satisfazem (∗), f (k) = menor elemento de B − f ({1, . . . , k − 1}) = menor elemento de B − g({1, . . . , k − 1}) = g(k), o que contradiz a escolha de k. QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 13 / 30 Teorema Existe uma Unica funcao f : N — B satisfazendo (*) para todo n EN. Pelos dois lemas anteriores, para cada n € N existe uma Unica fun¢ao f,: {1,...,n} > B satisfazendo (*) em seu dominio. A funcdo f do enunciado sera obtida (vista como conjunto de pares ordenados) como f= Vf. neN Primeiro, para ver que f é de fato uma funcao, devemos mostrar que cada i € N aparece como primeira coordenada de um tinico elemento de f. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 14/30 Para isto, note que i ∈ dom fn ⇐⇒ i ⩽ n. (♯) Pelo lema anterior, fn(i) = fm(i) (n, m ⩾ i). Logo, os elementos (♯) s˜ao todos iguais para diferentes valores de n, ou seja, h´a apenas um elemento de f que tem i por primeira coordenada. Agora, vejamos que f (como fun¸c˜ao) satisfaz (∗). Isto segue da igualdade f (i) = fn(i) (i ⩽ n) e do fato de que cada fn satisfaz (∗) em seu dom´ınio. QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 15 / 30 O princ´ıpio geral da defini¸c˜ao recursiva ´e o seguinte. Teorema Seja A um conjunto, seja a ∈ A. Seja F o conjunto de todas as fun¸c˜oes g : {1, . . . , n} → A para algum n ∈ N. Dada uma fun¸c˜ao ρ : F → A, existe uma fun¸c˜ao f : N → A tal que f (1) = a, f (n + 1) = ρ(f |{1,...,n}). A demonstra¸c˜ao baseia-se em ideias j´a colocadas anteriormente e fica a cargo do leitor. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 16 / 30 Exemplo Este ´ultimo teorema generaliza o primeiro. Para ver isto, seja B ⊂ N um conjunto infinito e seja b ∈ B o menor elemento de B. Para cada fun¸c˜ao g : {1, . . . , n} → B, defina ρ(g) = menor elemento de B − Im g. Pelo teorema anterior existe uma fun¸c˜ao f : N → B tal que f (1) = b e f (n + 1) = ρ(f |{1,...,n}) = menor elemento de B − Im f |{1,...,n} = menor elemento de B − f ({1, . . . , n}). QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 17 / 30 Exemplo Dado um numero real a, costuma-se definir as poténcias a” recursivamente: () at =a, x att — a”. a, Esta “definicdo” torna-se rigorosa quando vista como aplicac¢ao do teorema anterior a funcao P(g) = g(m)-a, definida para funcdes g : {1,...,m}-— R. O teorema garante que existe uma Unica funcao f : N > R tal que f(1) =ae Fin +1) = p(Fl er, ny) = F(n) - a. Ao denotarmos f(n) = a”, obtemos justamente (x). QED Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 18 /30 Exemplo Seja (an)ncn uma sequéncia de nimeros reais. A soma )>;_1 ax € definida recursivamente por 1 S ak = 41, k=1 n+1 n y ak = y ak + ans. k=1 k=1 Esta “definicdo” torna-se rigorosa quando vista como aplicac¢ao do teorema anterior a funcao P(g) = g(m) + ams, onde g: {1,...,m} OR. QED Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 19/30 O simbolo 5) é denominado “simbolo do somatério”. Na verdade, a soma ay +++ + ap que jd escrevemos tantas vezes em aulas anteriores é apenas uma notacdo para n ) Ak. k=1 O simbolo de somatério aparece em inumeras formulas matematicas. Na verdade, virtualmente toda férmula na matematica superior envolvendo somas acaba exibindo este simbolo. Outra definicdo relacionada envolve o simbolo de “produtério” n Ia k=1 (Vide Lista 8.) Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 20 / 30 Exemplo (férmula binomial) Se ae b sao ntimeros reais entado “fn n_ k ,pn—k (a+b) => ({)a*6 . C9) k=0 Acima, para inteiros positivos 0 < k <n, n\ _ nl! k} (n—k)!k! é o coeficiente binomial. O simbolo n! (lé-se: “n fatorial”) é definido indutivamente por 0! =1le nt =n(n—1)!sen>1. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 21/30 Continuacao Uma propriedade relevante dos coeficientes binomiais é que n n n+1 = k>1). (i) G-Ce) wen Ndo é preciso usar indu¢do para demonstrar a identidade acima. Vamos demonstrar a a formula (44) por indu¢do em n. A férmula é valida para n = 1, pois 1 L\ kik 1 1 > (;)*6 = oot 1 a=a+b. k=0 Agora, suponha que a férmula (¥4) seja valida para algum n > 1. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 22/30 Continuacao Entao, (a+ b)"*! = (a+ b)(a+ 6)” n n _— b k pn—k (a+ >> ({)3 b k=0 “ (n “ (n _ k+1 pn—k k ,pn+1—k => (2) 2 b +o (fate k=0 k=0 n+1 n n n _— k ,pn—(k—1) k pn+l1—k (74) +o (fate k=1 k=0 onde na primeira soma da Ultima linha trocamos k por k — 1. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 23 /30 Continuacao Agora, separando o termo correspondente a k = n+ 1 na primeira soma e k = 0 na segunda soma vemos que toda a expressdo acima 6 direita é ° n n n “./(n _ k pn—(k—1) n+l n+1 k pnt1—k = (,"4)a*6 + (73 (9) +d (fate k=1 k=1 ° n n _ k pn+1—k n+1 n+1 =H [(.2 1) + De +a" +b k=1 n+1 “.(n+1 n+1 _ ptt k pnt+1—k n+1 ( 0 ) + S° , j? + 0 a k=1 n+1 _ S- (" + ') ak pnti-k = k . k=0 Portanto, a formula é valida também para n+ 1. QED Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 24 /30 A torre de Han´oi A torre de Han´oi ´e um quebra-cabe¸cas que consiste de uma base contendo trˆes pinos, num dos quais s˜ao dispostos alguns discos uns sobre os outros, em ordem crescente de diˆametro, de cima para baixo. O jogo foi inventado pelo matem´atico francˆes Edouard Lucas, em 1883, e seu objetivo consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, sob a restri¸c˜ao de que um disco maior nunca fique em cima de outro menor. Figura: A torre de Han´oi. O nome do jogo remete `a cidade de Han´oi, capital do Vietn˜a. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 25 / 30 N˜ao ´e imediatamente ´obvio que o quebra-cabe¸ca tenha uma solu¸c˜ao. Contudo, um pouco de pr´atica numa situa¸c˜ao, digamos, de 2 ou 3 discos nos convence de que sim, h´a solu¸c˜ao. Agora, a pergunta natural ´e: Qual ´e a melhor solu¸c˜ao? Ou seja, quantos movimentos, no m´ınimo, s˜ao necess´arios para se realizar a tarefa? Seja T(n) o menor n´umero de movimentos necess´arios para se transferir n discos de um pino a outro, sob as condi¸c˜oes de Lucas. ´E f´acil ver que, por exemplo, T(0) = 0 (se n˜ao h´a discos, nenhum movimento ´e necess´ario!), T(1) = 1 e T(2) = 3. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 26 / 30 Agora, no caso geral, raciocinamos recursivamente: PASSO 1 ▶ transferimos os n − 1 discos de cima (pino 1) para um outro pino (pino 2), o que requer T(n − 1) movimentos. PASSO 2 ▶ transferimos o maior (que est´a no pino 1) para o outro pino (pino 3), o que requer 1 movimento. PASSO 3 ▶ transferimos os n − 1 discos do pino 2 para o pino 3, o que novamente requer T(n − 1) movimentos. Assim, no total temos 2T(n − 1) + 1 movimentos e podemos seguramente afirmar que T(n) ⩽ 2T(n − 1) + 1. Entretanto, em algum momento devemos mover o disco grande e, quando o fizermos, os outros n − 1 devem estar no “pino 2” e ter˜ao sido necess´arios no m´ınimo T(n − 1) movimentos para lev´a-los para l´a e tamb´em no m´ınimo mais T(n − 1) movimentos para lev´a-los em seguida ao “pino 3”. Logo, T(n) ⩾ 2T(n − 1) + 1. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 27 / 30 Consequentemente, T(n) satisfaz a formula recursiva T(n) = 2T(n—1)+1. Pelo teorema da recursdo, existe uma unica funcdo T que satisfaz a formula recursiva acima. Note que T(3) =2-34+1=7, T(4)=2-741=15, T(5) =2-154+1=31, T(6) = 2-31+4+1=63, etc. Isto sugere que T(n)=2"-—1 (n=0,1,2,...) (b) Isto pode ser verificado por induc¢ao. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 28 / 30 F´ormulas de recorrˆencia como a da Torre de Han´oi ´e t´ıpica de muitas que surgem em aplica¸c˜oes de todos os tipos. Para encontrar uma express˜ao fechada para alguma quantidade de interesse como T(n) passamos por trˆes etapas: 1 analisar os casos pequenos; isso nos d´a uma vis˜ao do problema e nos ajudar´a nas etapas 2 e 3 seguintes. 2 encontrar e provar uma express˜ao matem´atica para a quantidade de interesse; para a Torre de Han´oi, esta ´e a recorrˆencia (♮); 3 encontrar e provar uma forma fechada para a quantidade de interesse; para o Torre de Han´oi, esta ´e a solu¸c˜ao (♭). Dentro da Matem´atica Discreta, o terceiro est´agio costuma receber mais aten¸c˜ao. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 08 29 / 30 Leitura complementar Primeiro capitulo de: m “Ronald L. Graham, Donald E. Knuth & Oren Patashnik, Matemdtica Concreta: Fundamentos Para a Ciéncia da Computacao, LTC, 1995”. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 08 30/30