Departamento de Informática – E D L M
Indução Matemática
Recursão
Estruturas Discretas e Lógica Matemática
Dep. de Informática – UFMA
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
• O princípio da indução matemática é
uma ferramenta muito útil para provar
certas propriedades dos números
naturais.
• Não pode ser usada para descobrir
teoremas, mas somente para proválos.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
• Seja P(n) uma função proposicioinal,
e queremos provar que P(n) é
verdadeiro para qualquer n natural :
– Mostre que P(0) é true.
(passo básico)
– Mostre que se P(n) então P(n + 1) para
qualquer nN.
(passo indutivo)
– Então P(n) deve ser true para qualquer
nN.
(conclusão)
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
•
•
Exemplo:
Mostre que n < 2n para todo inteiro
positivo n.
– Seja P(n) a proposição “n < 2n.”
1. Mostre que P(1) é true. (passo básico)
•
P(1) é true, porque 1 < 21 = 2.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
1. Mostre que se P(n) é true, então P(n
+ 1) é true. ( passo indutivo)
– Assuma que n < 2n é true.
– Precisamos mostrar que P(n + 1) é true,
n + 1 < 2n+1
– Começamos com n < 2n:
n + 1 < 2n + 1  2n + 2n = 2n+1
– Assim, se n < 2n então n + 1 < 2n+1
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
• Então P(n) deve ser true para
qualquer inteiro possitivo.
(conclusão)
– n < 2n é true para todo inteiro positivo.
• C.Q.D
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
• Outro exemplo (“Gauss”):
1 + 2 + … + n = n (n + 1)/2
• Mostre que P(0) é true.(passo base)
• Para n = 0 temos 0 = 0. True.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
• Mostre que se P(n) então P(n + 1)
para qualquer nN. (passo indutivo)
1 + 2 + … + n = n (n + 1)/2
1 + 2 + … + n + (n + 1) = n (n + 1)/2 + (n + 1)
= (2n + 2 + n (n + 1))/2
= (2n + 2 + n2 + n)/2
= (2 + 3n + n2 )/2
= (n + 1) (n + 2)/2
= (n + 1) ((n + 1) + 1)/2
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
• Então P(n) deve ser true para todo
nN. (conclusão)
• 1 + 2 + … + n = n (n + 1)/2 é true para
todo nN.
• C.Q.D.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
• Existe outra técnica de prova similar
ao princípio da indução matemática.
• É chamado de segundo princípio da
indução matemática.
• Pode ser usado para provar que uma
função proposicional P(n) é true para
todo número natural.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
• O segundo princípio da indução
matemática:
• Mostre que P(0)é true.
(passo básico)
• Mostre que se P(0) e P(1) e … e P(n),
então P(n + 1) para todo nN.
(passo indutivo)
• Então P(n) deve ser true para todo
nN.
(conclusão)
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
• Exemplo: Mostre que todo inteiro
maior que 1 pode ser escrito como um
produto de número primos.
• Mostre que P(2) é true.
(passo básico)
• 2 é o produto de um primo: ele
mesmo.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
indução
• mostre que se P(2) e P(3) e … e P(n),
então P(n + 1) para qualquer nN. (passo
indutivo)
– Dois casos possíveis:
• Se (n + 1) é primo, então P(n + 1) é true.
• Se (n + 1) não é primo, ele pode se escrito como
produto de dois inteiros a e b tal que
2  a  b < n + 1.
• Pwla hipótese de indução, a e b podems er escritos
como produtos de primos.
– Então, n + 1 = ab pode ser escrito como um
produto de primor.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Indução
• Assim, P(n) deve ser true para
qualquer nN.
(conclusão)
• C.Q.D.
• Provamos que todo inteiro maior que
1 pode ser escrito como um produto
de números primos.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Definições Recursivas
• recursão é um princípio relacionado à
indução matemática.
• Numa definição recursiva um objeto é
descrito em função de sim mesmo.
• Podemos definir recursivamente
sequências, funções e conjuntos.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Sequências Recursivamente
Definidas
• Exemplo:
• A sequência {an} de pontências de 2 é
dada por
an = 2n para n = 0, 1, 2, … .
• A mesma sequência pode ser definida
recursivamente:
a0 = 1
an+1 = 2an para n = 0, 1, 2, …
• Obviamente indução e recursão são
similares.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções Definidas Recursivamente
• Podemos usar o seguinte método
para definir uma função com domínio
nos números naturais:
– Especifique o valor da função para zero.
– Dê uma regra para encontraro valor da
função para um inteiro qualquer, a partir
dos inteiros menores que ele.
• Um definição assim é denominada
recursiva.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções Definidas Recursivamente
• Exemplo:
• f(0) = 3
• f(n + 1) = 2f(n) + 3
•
•
•
•
•
f(0) = 3
f(1) = 2f(0) + 3 = 23 + 3 = 9
f(2) = 2f(1) + 3 = 29 + 3 = 21
f(3) = 2f(2) + 3 = 221 + 3 = 45
f(4) = 2f(3) + 3 = 245 + 3 = 93
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções Definidas Recursivamente
• Como definir a função fatorial (f(n) = n!)
recursivamente ?
• f(0) = 1
• f(n + 1) = (n + 1)f(n)
•
•
•
•
•
f(0) = 1
f(1) = 1f(0) = 11 = 1
f(2) = 2f(1) = 21 = 2
f(3) = 3f(2) = 32 = 6
f(4) = 4f(3) = 46 = 24
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Funções Definidas Recursivamente
• Exemplo: Números de Fibonacci
• f(0) = 0, f(1) = 1
• f(n) = f(n – 1) + f(n - 2)
•
•
•
•
•
•
•
f(0) = 0
f(1) = 1
f(2) = f(1) + f(0) = 1 + 0 = 1
f(3) = f(2) + f(1) = 1 + 1 = 2
f(4) = f(3) + f(2) = 2 + 1 = 3
f(5) = f(4) + f(3) = 3 + 2 = 5
f(6) = f(5) + f(4) = 5 + 3 = 8
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Conjuntos Definidos Recursivamente
• Se queremos definir um conjunt
recursivamente:
– Um conjunto inicial de elementos,
– Regras para construção des demais elementos
a apartir do conjunto incial.
• Exemplo: Seja S definido recursivamente
por:
– 3S
– (x + y)  S if (x  S) e (y  S)
• S é o conjunto dos inteiros positivos
divisíveis por 3.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Conjuntos Definidos Recursivamente
• Prova:
• Seja A o conjunto de todos os inteiros
positivos divisíveis por 3.
• Para mostrar que A = S,(A  S e S 
A).
• Parte I: Prove que A  S
– Mostrar que todo inteiro positivo divisível
por 3 está em S.
• Indução matemática.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Conjuntos Definidos Recursivamente
• Seja P(n) a afirmativa “3n pertence a S”.
• Passo básico: P(1) é true, porque 3 está
em S.
• Passo Indutivo:
• Se P(n) é true, então P(n + 1) é true.
– Assuma que 3n está em S.
– Como 3n está em S e 3 está em S
– Da definição recursiva de S temos que
• 3n + 3 = 3(n + 1) também está em S.
• Conclusãon da Parte I: A  S.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Conjuntos Definidos Recursivamente
• Part II: Mostrar que : S  A.
• Passo básico:
– Todos os elementos iniciais de S estão em A
– 3 está em A. True.
• Passo Indutivo:
– (x + y) está em A se x e y estão em S.
– Se x e y estão em A,
• Então 3 | x e 3 | y.
• Do Teorema Isegue que 3 | (x + y).
• Conclusão da Parte II: S  A.
• Logo: A = S.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Conjuntos Definidos Recursivamente
• Exemplo:
• Fórmulas bem formadas de variáveis,
numeria s e operadores de {+, -, *, /,
^} são definidas por:
– x é uma fórmula bem formada se x é um
numeral ou uma variável.
– (f + g), (f – g), (f * g), (f / g), (f ^ g) são
fórmulas bem formadas.
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Conjuntos Definidos Recursivamente
• Com esta definição, podemos
construir fórmulas como::
– (x – y)
– ((z / 3) – y)
– ((z / 3) – (6 + 5))
– ((z / (2 * 4)) – (6 + 5))
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Algoritmos Recursivos
• Um algoritmo é denominado recursivo
se resolve um problema reduzindo-o a
uma instância do mesmo problema
com tamanho menor.
• Exemplo I: Algoritmo Recursivo de
Fibonacci
procedure fibo(n: nonnegative integer)
if n = 0 then fibo(0) := 0
else if n = 1 then fibo(1) := 1
else fibo(n) := fibo(n – 1) + fibo(n – 2)
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Algoritmos Recursivos
• Avaliação Recursiva de Fibonacci:
f(4)
f(3)
f(2)
f(2)
f(1)
f(1)
f(1)
f(0)
f(0)
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Algoritmos Recursivos
procedure iterative_fibo(n: nonnegative integer)
if n = 0 then
y := 0
else
x := 0
y := 1
for i := 1 to n-1
z := x + y
x:=y
y := z
end
end {y is the n-th Fibonacci number}
Prof. Anselmo Paiva
Departamento de Informática – E D L M
Algoritmos Recursivos
• Para cada algoritmo recursivo, existe
um equivalente iterativo.
• Algoritmos recursivos são menores,
mais elegantes e fáceis de entender
• Algoritmos iterativos são em geral
mais eficientes em tempo e memória.
Prof. Anselmo Paiva