Teoria da Compuação Revisão FPA

Algoritmos e Fundamentos da Teoria de Computac¸ao˜

Lista de Exerc´ıcios 00

• Sejam os conjuntos X = f1; 2; 3; 4g e Y = f0; 2; 4; 6g. Defina explicitamente os conjuntos pedidos nos itens abaixo.

1. X [ Y

1. X \ Y

1. X  Y

1. Y  X

1. P(X)

[pic 1]

1. X [ Y = f0; 1; 2; 3; 4; 6g

1. X \ Y = f2; 4g

1. X  Y = f1; 3g

1. Y  X = f0; 6g

e.

P(X) =f ;; f1g; f2g; f3g; f4g; f1; 2g; f1; 3g; f1; 4g; f2; 3g; f2; 4g; f3; 4g; f1; 2; 3g; f1; 2; 4g; f1; 3; 4g; f2; 3; 4g; f1; 2; 3; 4g g

• Sejam os conjuntos X = fa; b; cg e Y = f1; 2g.

1. Liste todos os subconjuntos de X.

1. Liste todos os elementos de X  Y.

1. Liste todas as func¸oes˜ totais de Y para X.

[pic 2]

1. P(X) = f;; fag; fbg; fcg; fa; bg; fa; cg; fb; cg; fa; b; cgg.

1. X  Y = f[a; 1]; [a; 2]; [b; 1]; [b; 2]; [c; 1]; [c; 2]g.

1. Um argumento simples de contagem e´ suficiente para sabermos que existem 32 = 9 func¸oes˜ totais de Y para X. (De forma geral, ha´ nm func¸oes˜ totais, aonde m e´ o numero´ de elementos do dom´ınio e n e´ o numero´ de

1

[pic 3]

elementos do co-dom´ınio.) As nove func¸oes˜ sao˜ descritas a seguir.

f0 = f[1; a]; [2; a]g

f1 = f[1; a]; [2; b]g

f2 = f[1; a]; [2; c]g

f3 = f[1; b]; [2; a]g

f4 = f[1; b]; [2; b]g

f5 = f[1; b]; [2; c]g

f6 = f[1; c]; [2; a]g

f7 = f[1; c]; [2; b]g

f8 = f[1; c]; [2; c]g

• Mostre que o conjunto dos numeros´ naturais pares e´ enumeravel´.

[pic 4]

Um conjunto e´ enumeravel´ se ele tem a mesma cardinalidade que N, o conjunto dos numeros´ naturais. Dois conjuntos temˆ a mesma cardinalidade se existe uma bijec¸ao˜ entre os seus elementos. Assim, para mostrar que o conjunto P dos naturais pares e´ enumeravel,´ basta apresentar uma func¸ao˜ f : N ! P que seja bijetora. A func¸ao˜ f(n) = 2n satisfaz essa condic¸ao˜.

• Mostre que o conjunto dos numeros´ inteiros pares e´ enumeravel´. (Obs.: um numero´ inteiro i e´ par se o valor absoluto jij e´ divis´ıvel por 2.)

[pic 5]

Seja IP o conjunto dos inteiros pares. Para mostrar que IP e´ enumeravel,´ basta apresentar uma func¸ao˜ f : N! IP que seja bijetora. A func¸ao˜ abaixo satisfaz essa condic¸ao˜.

f(n) =	n	n par
	n + 1	n ´ımpar

5 Mostre que o conjunto dos numeros´ racionais positivos e´ enumeravel´.  (Obs.: Considere que ambos o

numerador e o denominador sao˜ naturais positivos.)

[pic 6]

Basta perceber que o conjunto dos numeros´ racionais positivos Q+ pode ser representado por elementos de

N+		+,	+	2	N+		´
	N+	aonde para todo [i; j]			N+, i e´ o numerador e j e´ o denominador. Assim, uma demonstrac¸ao˜

de que N N e´ enumeravel,´ similar ao Exemplo 1.4.2 do livro do Sudkamp, e´ suficiente. E poss´ıvel modificar a func¸ao˜ dada no exemplo para obtermos uma nova bijec¸ao˜ sobre os conjuntos de interesse dessa questao˜. Uma func¸ao˜ como abaixo resolve esse problema.

f([i; j]) = 12 ((i + j        2) (i + j        1)) + i        1

[pic 7]

Desenvolva um programa (em Python, por exemplo) que trac¸a a construc¸ao˜ dos pontos no semi-plano Q+ segundo o mapeamento da func¸ao˜ f, para se certificar que a construc¸ao˜ e´ uma bijec¸ao˜.

• (Desafio) Prove que o conjunto dos numeros´ reais no intervalo [0; 1] e´ incontavel´. Dica: Use o argumento de diagonalizac¸ao˜ sobre a casas decimais (d´ıgitos a` direita da v´ırgula) destes numeros´ reais.

2

[pic 8]

Para mostrar que o conjunto dos numeros´ reais no intervalo [0; 1] e´ incontavel,´ primeiramente observamos que qualquer numero´ real no intervalo [0; 1] pode ser expressado por um decimal infinito da forma :x0x1x2 : : : xn : : :.

Assuma que o conjunto dos numeros´ reais no intervalo [0; 1] e´ contavel´. Isso implica que existe uma sequenciaˆ

r0; r1; r2; : : : ; rn; : : :

que contem´ todos os numeros´ reais no intervalo [0; 1]. Fac¸a a expansao˜ decimal de rn ser denotada por :xn0xn1xn2 : : :. A sequenciaˆ dos numeros´ reais e´ utilizada para construir uma matriz bidimensional infinita, aonde a i-esima´ linha corresponde a` expansao˜ decimal de ri.

...