Fundamentos em Teoria da ComputaЗ╞o
303 pág.

Fundamentos em Teoria da ComputaЗ╞o


DisciplinaFundamentos de Teoria da Computação140 materiais530 seguidores
Pré-visualização50 páginas
os conectivos e utilizar as leis associativas
da conjunc¸a\u2dco e da disjunc¸a\u2dco para omitir pare\u2c6nteses. Por outro lado, a colocac¸a\u2dco de
pare\u2c6nteses em excesso a`s vezes e´ tolerado. Fac¸a uma definic¸a\u2dco recursiva para uma
linguagem LP\u2032 em que pare\u2c6nteses podem ser omitidos, mas que tambe´m podem
ser colocados em excesso. (Observe que a interpretac¸a\u2dco de uma afirmativa existe
a` parte da mesma; a definic¸a\u2dco recursiva devera´ gerar apenas as afirmativas sintati-
camente aceita´veis, sem preocupac¸a\u2dco com as regras de prioridades dos conectivos,
que existira\u2dco a` parte.)
28
1.8 Induc¸a\u2dco Matema´tica
A maioria dos resultados a serem apresentados nos cap´\u131tulos vindouros sera\u2dco provados
mediante evocac¸a\u2dco do denominado princ´\u131pio de induc¸a\u2dco matema´tica. Tal princ´\u131pio espe-
lha a definic¸a\u2dco recursiva dos nu´meros naturais, como se pode observar a seguir.
Princ´\u131pio de induc¸a\u2dco matema´tica: Seja uma propriedade P sobre os naturais.
Enta\u2dco, caso
\u2022 P se verifique para o nu´mero 0, e
\u2022 para um natural n arbitra´rio, se P se verifica para n, enta\u2dco P se verifica
para n+ 1,
pode-se concluir que P se verifica para todo nu´mero natural.23
Utilizando-se tal princ´\u131pio pode-se provar, por induc¸a\u2dco sobre n, que uma propriedade
P se verifica para todo nu´mero n \u2208 N, em tre\u2c6s passos:
(1) base da induc¸a\u2dco: provar que P se verifica para o nu´mero zero;
(2) hipo´tese de induc¸a\u2dco: supor que P se verifica para n, onde n e´ um nu´mero natural
arbitra´rio; e
(3) passo indutivo: provar que P se verifica para n+ 1.
Exemplo 34 Um resultado frequentemente utilizado por quem trabalha em computac¸a\u2dco
e´ o fato de que, para todo n \u2208 N, \u2211nk=0 k = n(n+1)/2, resultado este que ja´ foi utilizado
no Exemplo 27, pa´gina 23. Segue uma prova do mesmo por induc¸a\u2dco sobre n.
Inicialmente, veja que
\u22110
k=0 k = 0 = 0(0 + 1)/2. Suponha, como hipo´tese de induc¸a\u2dco,
que
\u2211n
k=0 k = n(n+1)/2 para um nu´mero natural n arbitra´rio. Basta provar, enta\u2dco, que\u2211n+1
k=0 k = (n+1)(n+2)/2. Ora,
\u2211n+1
k=0 k =
\u2211n
k=0 k+ (n+1) = n(n+1)/2+ (n+1), pela
hipo´tese de induc¸a\u2dco. Desenvolvendo: n(n + 1)/2 + (n + 1) = [n(n + 1) + 2(n + 1)]/2 =
(n+ 1)(n+ 2)/2. Logo, pelo princ´\u131pio da induc¸a\u2dco,
\u2211n
k=0 k = n(n+ 1)/2.
Vale ressaltar que o princ´\u131pio da induc¸a\u2dco e´ a base para se provar uma afirmativa
aplica´vel a todos os elementos de um conjunto enumera´vel, ja´ que, como existe uma
func¸a\u2dco bijetora dos naturais para tal conjunto, pode-se \u201ctransformar\u201d uma afirmativa
sobre os elementos do conjunto enumera´vel infinito em uma afirmativa sobre os naturais
(ou vice-versa). So´ que, normalmente, ao inve´s de fazer a transformac¸a\u2dco, raciocina-se
com a afirmativa original, adaptando-se o princ´\u131pio de induc¸a\u2dco. Assim, por exemplo,
para provar que P se verifica para todo natural n \u2265 k, basta:
(1) base da induc¸a\u2dco: provar que P se verifica para o nu´mero k;
(2) hipo´tese de induc¸a\u2dco: supor que P se verifica para n, sendo n \u2265 k arbitra´rio; e
(3) passo indutivo: provar que P se verifica para n+ 1.
23Mais formalmente: [P (0) \u2227 \u2200n(P (n)\u2192 P (n+ 1))]\u2192 \u2200nP (n).
29
(Neste caso, a transformac¸a\u2dco seria trivial: uma afirmativa sobre n, onde n \u2265 k, e´ o mesmo
que uma afirmativa sobre n+ k, onde n \u2265 0). Segue um exemplo.
Exemplo 35 Segue uma demonstrac¸a\u2dco, por induc¸a\u2dco sobre n, que n! > 2n para todo
n \u2265 4.
Inicialmente, para n = 4 tem-se: n! = 24 > 16 = 2n. Seja um n \u2265 4 arbitra´rio, e
suponha, como hipo´tese de induc¸a\u2dco, que n! > 2n. Deduz-se:
(n+ 1)!= (n+ 1)× n! pela definic¸a\u2dco de fatorial
> (n+ 1)× 2n pela hipo´tese de induc¸a\u2dco, pois n+ 1 > 0
> 2× 2n pois n \u2265 4
= 2n+1.
Logo, (n+ 1)! > 2n+1. Conclui-se que n! > 2n para todo n \u2265 4.
Existe uma versa\u2dco do princ´\u131pio de induc¸a\u2dco, e consequente formato de prova por
induc¸a\u2dco que pode ser mais fa´cil e/ou conveniente de ser usada em algumas circunsta\u2c6ncias.
Tal versa\u2dco, chamada de princ´\u131pio de induc¸a\u2dco forte, diz que, caso
\u2022 para um natural arbita´rio n, se P se verifica para todo k < n, enta\u2dco P se verifica
para n,
pode-se concluir que P se verifica para todo nu´mero natural.24 Uma prova por induc¸a\u2dco
baseada neste princ´\u131pio teria os passos:
(1) hipo´tese de induc¸a\u2dco: supor que P se verifica para todo k < n, onde n e´ um nu´mero
natural arbitra´rio; e
(2) passo indutivo: provar que P se verifica para n.
Exemplo 36 Seja o problema de provar que todo nu´mero natural n \u2265 2 e´ primo ou
produto de nu´meros primos.
A prova sera´ feita por induc¸a\u2dco forte sobre n. Para este efeito, seja n \u2265 2 arbitra´rio
e suponha, como hipo´tese de induc¸a\u2dco, que todo nu´mero natural 2 \u2264 k < n e´ primo ou
produto de nu´meros primos. Basta, enta\u2dco, provar que n e´ primo ou produto de primos.
Se n e´ um nu´mero primo, a afirmativa e´ trivialmente verdadeira. Caso contra´rio, por
definic¸a\u2dco de nu´mero primo, n = i × j, sendo 2 \u2264 i, j < n. Neste caso, pela hipo´tese
de induc¸a\u2dco, ambos, i e j, sa\u2dco primos ou produtos de nu´meros primos. Conclui-se que n
e´ primo ou produto de nu´meros primos. Logo, pelo princ´\u131pio de induc¸a\u2dco, todo nu´mero
natural n \u2265 2 e´ primo ou produto de nu´meros primos.
O exemplo a seguir ilustra a aplicac¸a\u2dco do princ´\u131pio de induc¸a\u2dco a entidades que na\u2dco
envolvem diretamente os nu´meros naturais.
Exemplo 37 Seja o conjunto das afirmativas da linguagem LP definido recursivamente
no Exemplo 33, pa´gina 27. Seja na(\u3b1) o nu´mero de abre pare\u2c6nteses e nf(\u3b1) o nu´mero
de fecha pare\u2c6nteses da afirmativa \u3b1. Sera´ provado, por induc¸a\u2dco que na(\u3b1) = nf(\u3b1) para
todo \u3b1 \u2208 LP .
Seja o grau de uma afirmativa o nu´mero de conectivos lo´gicos da mesma, o qual pode
ser definido recursivamente assim:
24Mais formalmente: \u2200n[(\u2200k < nP (k))\u2192 P (n)]\u2192 \u2200nP (n).
30
\u2022 o grau de uma varia´vel proposicional e´ zero;
\u2022 o grau de (\u3b1\u2295\u3b2) e´ um a mais que a soma dos graus de \u3b1 e \u3b2, onde\u2295 \u2208 {\u2227,\u2228,\u2192,\u2194}.
\u2022 o grau de ¬\u3b1 e´ um a mais que o grau de \u3b1.
Sera´ feita induc¸a\u2dco (forte) sobre o grau das afirmativas. Seja n um natural arbitra´rio
e suponha, como hipo´tese de induc¸a\u2dco, que na(\u3b1) = nf(\u3b1) para todo \u3b1 de grau menor que
n. Basta, enta\u2dco, mostrar que na(\u3b1) = nf(\u3b1) para todo \u3b1 de grau n. Considera-se dois
casos:
Caso 1: n = 0. Neste caso, \u3b1 e´ uma varia´vel proposicional e, portanto, na(\u3b1) = 0 = nf(\u3b1).
Caso 2: n > 0. Este caso pode ser subdividido em dois:
2.1 \u3b1 = ¬\u3b3. O grau de \u3b3 e´ n \u2212 1 e, portanto, pela hipo´tese de induc¸a\u2dco, na(\u3b3) =
nf(\u3b3). Segue-se que na(\u3b1) = nf(\u3b1), pois na(\u3b1) = na(\u3b3) e nf(\u3b1) = nf(\u3b3).
2.2 \u3b1 = (\u3b31 \u2295 \u3b32). Os graus de \u3b31 e de \u3b32 sa\u2dco menores que n e, portanto, pela
hipo´tese de induc¸a\u2dco, na(\u3b31) = nf(\u3b31) e na(\u3b32) = nf(\u3b32). Segue-se que na(\u3b1) =
nf(\u3b1), pois na(\u3b1) = na(\u3b31) + na(\u3b32) + 1 e nf(\u3b1) = nf(\u3b31) + nf(\u3b32) + 1.
Segue-se que na(\u3b1) = nf(\u3b1) para todo \u3b1 \u2208 LP .
Exerc´\u131cios
1. Prove por induc¸a\u2dco que |P(A)| = 2|A| para todo conjunto finito A.
2. Prove por induc¸a\u2dco que, para todo nu´mero natural n \u2265 0:
(a)
\u2211n
k=0 k
2 = n(n+ 1)(2n+ 1)/6.
(b)
\u2211n
k=0 k
3 = [n(n+ 1)/2]2.
(c) 22n \u2212 1 e´ divis´\u131vel por 3.
(d) n3 \u2212 n e´ divis´\u131vel por 6.
(e) 7n \u2212 1 e´ divis´\u131vel por 6.
3. Prove por induc¸a\u2dco que, para todo nu´mero natural n \u2265 1:
(a)
\u2211n
k=1[k(k + 1)] = n(n+ 1)(n+ 2)/3.
(b)
\u2211n
k=1 2
k = 2(2n \u2212 1).
(c)
\u2211n
k=1[1/k(k + 1)] = n/(n+ 1).
(d) n3 + (n+ 1)3 + (n+ 2)3 e´ divis´\u131vel por 9.
4. Seja F a func¸a\u2dco de Fibonacci definida recursivamente assim:
(a) F (0) = 0; F (1) = 1;
(b) F (n) = F (n\u2212 1) + F (n\u2212 2) para n \u2265 2.
31
\ufffd
\ufffd	A
\ufffd
\ufffd	B
\ufffd\ufffd
?
?
-
\ufffd
\ufffd	D
?\ufffd
\ufffd	C \ufffd
\ufffd
\ufffd
\ufffd
\ufffd
\ufffd\ufffd
\ufffd
\ufffd	E\ufb00 \ufffd
\ufffd\ufffd\ufffd
\ufffd
\ufffd	F
@
@@R@
@@I
(a) Um grafo dirigido.
\ufffd\ufffd \ufffd\ufffdChile\ufffd\ufffd
\ufffd
@
@@
\ufffd\ufffd \ufffd\ufffdBol´\u131via
@
@@
\ufffd\ufffd \ufffd\ufffdBrasil
\ufffd\ufffd \ufffd\ufffdParaguai\ufffd\ufffd
\ufffd
\ufffd\ufffd \ufffd\ufffdArgentina\ufffd\ufffd
\ufffd
\ufffd\ufffd
\ufffd\ufffd
\ufffd\ufffd
\ufffd
\ufffd
\ufffd
\ufffd
\ufffd\ufffd \ufffd\ufffdUruguai
(b) Um grafo na\u2dco dirigido.
Figura 1.8: Exemplos de grafos dirigido e na\u2dco dirigido.
Prove por induc¸a\u2dco que
F (n) =
1\u221a
5
[(
1 +
\u221a
5
2
)n
\u2212
(
1\u2212\u221a5
2
)n]
.
5. Prove que o nu´mero de abre pare\u2c6nteses de qualquer prefixo de qualquer afirmativa
da linguagem LP do Exemplo 33, pa´gina 27, e´ maior ou igual ao nu´mero de fecha
pare\u2c6nteses.
1.9 Grafos
Um grafo e´ uma estrutura matema´tica que conte´m dois tipos de entidades: ve´rtices