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

Fundamentos em Teoria da ComputaЗ╞o


DisciplinaFundamentos de Teoria da Computação141 materiais535 seguidores
Pré-visualização50 páginas
Do
ponto de vista tecnolo´gico, pelo menos ate´ agora, a base mais conveniente tem sido a base
2. Do ponto de vista matema´tico, no entanto, qualquer base serve. Por exemplo, para
representar um nu´mero natural n na base 1, pode-se usar uma sequ¨e\u2c6ncia de n+1 s´\u131mbolos.
Pode-se determinar que, para representar um nu´mero natural n na base b, para n \u2265 2,
usa-se uma sequ¨e\u2c6ncia de blogb nc + 1 s´\u131mbolos. Assim, ve\u2c6-se que a representac¸a\u2dco de um
nu´mero em uma base maior que 1 e´ exponencialmente mais concisa que a representac¸a\u2dco
em una´rio.
Ja´ os nu´meros reais na\u2dco podem ser todos representados em qualquer base, ja´ que os
nu´meros irracionais na\u2dco podem ser representados. Isto segue do fato de que o conjunto
dos nu´meros reais na\u2dco e´ enumera´vel: se cada nu´mero real pudesse ser representado por
uma sequ¨e\u2c6ncia de s´\u131mbolos finita, enta\u2dco, dado que os naturais tambe´m podem, seria
poss´\u131vel ter uma func¸a\u2dco bijetora dos naturais para os reais. Uma implicac¸a\u2dco disto, e´ que
nenhum computador, mesmo com memo´ria ilimitada, pode manipular todos os nu´meros
reais. Como os computadores te\u2c6m memo´ria limitada, eles sequer conseguem manipular
todos os nu´meros racionais; na realidade eles so´ conseguem manipular um subconjunto
dos racionais, normalmente denominados de nu´meros de ponto flutuante.
Generalizando, se um conjunto na\u2dco e´ conta´vel, enta\u2dco seus elementos na\u2dco podem ser
(todos) representados por seque\u2c6ncias finitas de s´\u131mbolos tomados de um conjunto finito
de s´\u131mbolos. Por outro lado, se um conjunto e´ conta´vel, seus elementos podem ser
(todos) representados por seque\u2c6ncias finitas de s´\u131mbolos tomados de um conjunto finito
de s´\u131mbolos.
Exerc´\u131cios
1. Para cada um dos conjuntos abaixo, prove que ele e´, ou que na\u2dco e´, enumera´vel:
(a) {n \u2208 N | nmod 10 = 0}.
(b) {(n1, n2, n3) | n1, n2, n3 \u2208 N}.
(c) {n \u2208 R | 0 < n < 1}.
25
2. O conjunto das func¸o\u2dces de N para {0, 1} pode ser visto como o conjunto de todos
os problemas de decisa\u2dco (problemas cuja resposta e´ sim ou na\u2dco)22. Prove que tal
conjunto na\u2dco e´ enumera´vel.
3. Uma func¸a\u2dco total f : N \u2192 N e´ dita monoto\u2c6nica crescente se f(n + 1) > f(n)
para todo n \u2208 N. Prove que o conjunto das func¸o\u2dces monoto\u2c6nicas crescentes na\u2dco e´
conta´vel.
4. Mostre que todo subconjunto de um conjunto enumera´vel e´ conta´vel.
5. Mostre que a unia\u2dco, a intersec¸a\u2dco e o produto cartesiano de dois conjuntos conta´veis
sa\u2dco conjuntos conta´veis.
6. Sejam F um conjunto finito e E um conjunto enumera´vel. O conjunto das func¸o\u2dces
totais f : F \u2192 E e´ enumera´vel?
1.7 Definic¸o\u2dces Recursivas
Uma propriedade importante dos conjuntos enumera´veis e´ que eles podem ser definidos
atrave´s de uma definic¸a\u2dco recursiva (ou indutiva). Uma definic¸a\u2dco recursiva especifica como
um conjunto conta´vel pode ser gerado a partir de um subconjunto do mesmo aplicando-
se determinadas operac¸o\u2dces um nu´mero finito de vezes. Uma definic¸a\u2dco recursiva de um
conjunto A consta de tre\u2c6s partes:
(a) base: especificac¸a\u2dco de um conjunto base B \u2282 A;
(b) passo recursivo: especificac¸a\u2dco de um elenco de operac¸o\u2dces que, se aplicadas a ele-
mentos de A, geram elementos de A;
(c) fechamento: afirmac¸a\u2dco que os u´nicos elementos de A sa\u2dco aqueles que podem ser
obtidos a partir dos elementos de B aplicando-se um nu´mero finito de vezes as
operac¸o\u2dces especificadas em (b).
O conjunto B deve ser um conjunto conta´vel. Ele pode, inclusive, ter sido definido
recursivamente.
Exemplo 30 O conjuntoN pode ser definido assim, a partir de {0}, usando-se a operac¸a\u2dco
s (sucessor):
(a) 0 \u2208 N;
(b) se n \u2208 N, enta\u2dco s(n) \u2208 N;
(c) so´ pertence a N o nu´mero que pode ser obtido de acordo com (a) e (b).
De forma equivalente, pode-se omitir o item (c) de uma definic¸a\u2dco recursiva e dizer que
o conjunto definido e´ o menor conjunto que pode ser obtido por meio de (a) e (b). Neste
texto, o item (c) na\u2dco sera´ explicitado, mas suposto implicitamente quando se disser que
o conjunto e´ definido recursivamente por (a) e (b).
Func¸o\u2dces tambe´m podem ser definidas recursivamente; afinal, func¸o\u2dces sa\u2dco conjuntos!
22Uma introduc¸a\u2dco a problemas de decisa\u2dco sera´ feita na Sec¸a\u2dco 1.12.
26
Exemplo 31 A func¸a\u2dco fatorial, fat : N\u2192 N e´ definida recursivamente por:
(a) fat(0) = 1;
(b) fat(n) = n× fat(n\u2212 1), para n \u2265 1.
Evidentemente, a definic¸a\u2dco do exemplo anterior poderia ser colocada no formato apre-
sentado no in´\u131cio desta sec¸a\u2dco:
(a) (0, 1) \u2208 fat ;
(b) se n \u2265 1 e (n\u2212 1, k) \u2208 fat , enta\u2dco (n, nk) \u2208 fat ;
(c) so´ pertence a fat o par que pode ser obtido conforme (a) e (b).
No estilo do Exemplo 31, que sera´ adotado aqui, o passo (b) da definic¸a\u2dco mostra como
obter o valor f(n1, n2, . . . , nk) a partir de valores \u201cmais simples\u201d, isto e´, de valores
f(n\u20321, n
\u2032
2, . . . , n
\u2032
k) tais que pelo menos um n
\u2032
j e´ menor que nj e nenhum n
\u2032
j e´ maior que nj.
Segue mais um exemplo.
Exemplo 32 Utilizando a representac¸a\u2dco de nu´mero natural dada pela definic¸a\u2dco recursiva
do Exemplo 30, onde a representac¸a\u2dco de um nu´mero n > 0 e´ dada por s(s(· · · s(0) · · ·)),
onde aparecem n s\u2019s, e´ apresentada a seguir uma definic¸a\u2dco recursiva da operac¸a\u2dco de soma
sobre N:
(a) n+ 0 = n, para todo n \u2208 N;
(b) m+ s(n) = s(m+ n), para todo n \u2208 N.
Observe que a soma m+ s(n) e´ obtida a partir da soma \u201cmais simples\u201d m+ n. A partir
do seguinte trecho da´ para perceber como uma soma e´ \u201cconstru´\u131da\u201d (colchetes sa\u2dco usados
ao inve´s de alguns pare\u2c6nteses apenas para efeitos de maior legibilidade):
s(0) + s(s(s(0)))= s[s(0) + s(s(0))] por (b)
= s[s[s(0) + s(0)]] por (b)
= s[s[s[s(0) + 0]]] por (b)
= s[s[s[s(0)]]] por (a)
Antecipando um pouco do assunto a ser tratado na Sec¸a\u2dco 1.10, segue um exemplo de
definic¸a\u2dco recursiva da sintaxe de uma linguagem.
Exemplo 33 A seguir sera´ definida uma (sintaxe de uma) linguagem para a Lo´gica Pro-
posicional, LP, ou seja, a parte da Lo´gica Matema´tica vista informalmente na Sec¸a\u2dco 1.2,
exclu´\u131dos os conectivos \u2200 e \u2203. Para isto, sera´ suposto um conjunto de varia´veis proposi-
cionais para expressar afirmativas primitivas (indivis´\u131veis ou na\u2dco compostas) constitu´\u131do
dos s´\u131mbolos: p, q e r, com ou sem \u131´ndices. Para os conectivos sera\u2dco utilizados os s´\u131mbolos
apresentados na Sec¸a\u2dco 1.2. E sera\u2dco tambe´m utilizados os s´\u131mbolos auxiliares \u201c(\u201d e \u201c)\u201d.
A linguagem LP e´, enta\u2dco, definida recursivamente assim:
27
(a) cada varia´vel proposicional pertence a LP;
(b) se \u3b1 e \u3b2 pertencem a LP, enta\u2dco tambe´m pertencem a LP:
\u2022 ¬\u3b1;
\u2022 (\u3b1 \u2227 \u3b2);
\u2022 (\u3b1 \u2228 \u3b2);
\u2022 (\u3b1\u2192 \u3b2);
\u2022 (\u3b1\u2194 \u3b2).
Exemplos de afirmativas pertencentes a LP: p, q, ¬p, (p \u2192 q), ((p \u2192 q) \u2227 ¬p). As duas
primeiras foram obtidas da base da definic¸a\u2dco, a terceira e a quarta aplicando-se o passo
recursivo da definic¸a\u2dco uma u´nica vez, e a u´ltima aplicando-se o passo recursivo a partir
da terceira e da quarta. Observe que, por esta definic¸a\u2dco, na\u2dco sa\u2dco exemplos de afirmativas
pertencentes a LP: pq, p \u2227 q, (p), ¬(p). Na\u2dco ha´ como gerar tais sequ¨e\u2c6ncias a partir das
varia´veis proposicionais aplicando-se as regras de composic¸a\u2dco de (b).
Diversos outros exemplos de definic¸o\u2dces recursivas sera\u2dco vistos nas pro´ximas sec¸o\u2dces e
cap´\u131tulos.
Exerc´\u131cios
1. De\u2c6 uma definic¸a\u2dco recursiva de f : N\u2192 N, onde f(n) = \u2211nk=1 k.
2. Fac¸a uma definic¸a\u2dco recursiva do nu´mero de elementos do conjunto pote\u2c6ncia de
conjuntos finitos.
3. Fac¸a uma definic¸a\u2dco recursiva das representac¸o\u2dces dos nu´meros naturais na base 2,
sem zeros a` esquerda, de forma que cada nu´mero tenha uma u´nica representac¸a\u2dco.
4. Fac¸a uma definic¸a\u2dco recursiva dos nu´meros da se´rie de Fibonacci: 0, 1, 1, 2, 3, 5, 8,
13, . . .
5. Continuando no estilo do Exemplo 32, pa´gina 27, fac¸a uma definic¸a\u2dco recursiva da
operac¸a\u2dco de multiplicac¸a\u2dco sobre N.
6. No Exemplo 33, foi apresentada uma sintaxe muito simples e conveniente do ponto
de vista formal, mas que na\u2dco e´ adequada na pra´tica, pois o uso exaustivo de
pare\u2c6nteses leva a afirmativas longas e ileg´\u131veis. O procedimento usual para resolver
esse problema e´ assumir prioridades para