Teoria da Computacao

Leandro B. Marinho - leandrobezerramarinho@gmail.com

April 21, 2015

1.1.1 Determine se cada um dos seguintes itens e verdadeiro ou falso.

(a) ; ✓ ; (V)

(b) ; 2 ; (F)

(c) ; 2 {;} (V)

(d) ; ✓ {;} (V)

(e) {a, b} 2 {a, b, c, {a, b}} (V)

(f) {a, b} ✓ {a, b, c, {a, b}} (V)

(g) {a, b} ✓ 2{a,b,{a,b}} (V)

(h) {{a, b}} 2 2{a,b,{a,b}} (V)

(i) {a, b, {a, b}}� {a, b} = {a, b} (F)

2{a,b,{a,b}} = {{a}, {b}, {{a, b}}, {a, b}, {a, {a, b}}, {b, {a, b}}, {a, b, {a, b}}, ;}

1.1.2 O que sao conjuntos abaixo? Denote-os utilizando somente chaves, vırgulas e nu-merais.

(a) ({1, 3, 5} [ {3, 1}) \ {3, 5, 7} = {3, 5}

(b) [{{3}, {3, 5},\{{5, 7}, {7, 9}}} = {3, 5, 7}

(c) ({1, 2, 5}� {5, 7, 9}) \ ({5, 7, 9}� {1, 2, 5}) = {}

(d) 2{7,8,9} � 2{7,9} = {{7, 8}, {8, 9}, {7, 8, 9}}

(e) 2; = {;}

1.1.3 Prove cada uma das seguintes igualdades:

1

(a) A [ (B \ C) = (A [ B) \ (A [ C)Solucao:i) Seja x um elemento arbritario de A [ (B \ C)x 2 A [ (B \ C) ! x 2 A _ x 2 (B \ C) Def. [! x 2 A _ (x 2 B ^ x 2 C) Def. \! (x 2 A _ x 2 B) ^ (x 2 A _ x 2 C) Prop. Distributiva Log.! (x 2 A [ B) ^ (x 2 A [ C) Def. [! [x 2 (A [ B) \ (A [ C)] Def. \Logo A [ (B \ C) ✓ (A [ B) \ (A [ C)ii) Seja x um elemento arbritario de (A [ B) \ (A [ C)x 2 (A [ B) \ (A [ C) ! [x 2 (A [B) ^ x 2 (A [ C)] Def. \! [(x 2 A _ x 2 B) ^ (x 2 A _ x 2 C)] Def. [! [(x 2 A) ^ (x 2 B _ x 2 C)] Prop. Distributiva Log.! [x 2 A ^ (x 2 B [ C)] Def. [! [x 2 A \ (B \ C)]Logo (A [B) \ (A [ C) ✓ A [ (B \ C)Assim, A [ (B \ C) = (A [ B) \ (A [ C)

(b) A \ (B [ C) = (A \B) [ (A \ C)Solucao:i) Seja x um elemento arbritario de A \ (B [ C)x 2 A \ (B [ C) ! x 2 A ^ x 2 (B [ C) Def. \! x 2 A ^ (x 2 B _ x 2 C) Def. [! (x 2 A ^ x 2 B) _ (x 2 A ^ x 2 C) Prop. Distributiva Log.! (x 2 A \B) _ (x 2 A \ C) Def. \! [x 2 (A \ B) [ (A \ C)] Def. [Logo A \ (B [ C) ✓ (A \B) [ (A \ C)ii) Seja x um elemento arbritario de (A \ B) [ (A \ C)x 2 (A \ B) [ (A \ C) ! [x 2 (A \B) _ x 2 (A \ C)] Def. [! [(x 2 A ^ x 2 B) _ (x 2 A ^ x 2 C)] Def. \! [(x 2 A) _ (x 2 B ^ x 2 C)] Prop. Distributiva Log.! [x 2 A _ (x 2 B \ C)] Def. \! [x 2 A [ (B [ C)]Logo (A \ B) [ (A \ C) ✓ A \ (B [ C)Assim, A \ (B [ C) = (A \ B) [ (A \ C)

(c) A \ (A [B) = A

Solucao:Deve-se mostrar que: i) A \ (A [B) ✓ A e ii) A ✓ A \ (A [ B).i) A demonstracao segue direto de (A \ B) ✓ A, tomando B = (A [B).ii) Seja x 2 A. Como A ✓ A [ B, segue que x 2 A [ B. Assim x 2 A e x 2 A [ B.Logo, x 2 A \ (A [ B). Portanto, A ✓ A \ (A [B).Conclui-se entao que A \ (A [B) = A.

(d) A [ (A \ B) = A

Solucao:

2

Deve-se mostrar que: i) A [ (A \B) ✓ A e ii) A ✓ A [ (A \ B).i) Se x 2 A[ (A\B), entao x 2 A ou x 2 A\B. Mas A\B ✓ A, assim se x 2 A\B

entao x 2 A. Desse modo, x 2 A ou x 2 A. Logo, x 2 A. Portanto, A [ (A \B) ✓ A.ii) Esta demonstracao segue direto de A ✓ (A [B) com B = (A \B).Conclui-se entao que A [ (A \B) = A.

(e) A� (B \ C) = (A� B) [ (A� C)Solucao:Deve-se mostrar que i) A� (B \ C) ✓ (A� B) [ (A� C) e ii) (A� B) [ (A� C) ✓A� (B \ C).i) Se x for qualquer elemento de A � (B \ C), entao x 2 A, mas x /2 B ou x /2 C.Logo,x e um elemento de de A� B ou e um elemento de A� C, sendo, portanto, umelemento de R. Entao, A� (B \ C) ✓ (A� B) [ (A� C).ii) Seja x 2 (A�B)[ (A�C); entao x e um elemento de de A�B ou e um elementoA � C, sendo portanto, um elemento de A, mas nao de B, ou de A, mas nao de C.Logo x 2 A, mas x /2 B \ C, logo x 2 A� (B \ C).Portanto, (A � B) [ (A � C) ✓ A � (B \ C), constando assim que A � (B \ C) =(A� B) [ (A� C).

1.1.4 Seja S = {a, b, c, d}.

(a) Qual das particoes de S tem o menor numero de membros? Qual delas tem o maiornumero de membros?Solucao:Menor numero de membros: {{a, b, c, d}}Maior numero de membros: {{a}, {b}, {c}, {d}}

(b) Liste todas as particoes de S que tem exatamente dois membros.Solucao:{{a, b}, {c, d}}, {{b, c}, {a, d}}, {{b, d}, {a, c}}

1.2.1 Escreva explicitamente cada uma das seguintes expressoes.

(a) {1}⇥ {1, 2}⇥ {1, 2, 3}Solucao: {(1, 1, 1), (1, 2, 2), (1, 1, 3), (1, 2, 1), (1, 1, 2), (1, 2, 3)}

(b) ; ⇥ {1, 2}Solucao: {}

(c) 2{1,2} ⇥ {1, 2}Solucao: {{1}, {2}, {1, 2}, ;}⇥ {1, 2} ={({1}, 1), ({1}, 2), ({2}, 1), ({2}, 2), ({1, 2}, 1), ({1, 2}, 2), (;, 1), (;, 2)}

1.2.2 Seja R = {(a, b), (a, c)(c, d), (a, a), (b, a)}. O que siginifica R � R, a composicao deR consigo mesma? Qual a funcao R

�1, a inversa de R? Quais das relacoes R, R �R ou R

�1

3

sao funcoes?Solucao:R �R = {(a, a), (a, d), (a, b), (a, c), (b, a), (b, c), (b, b)}R

�1 = {(b, a), (c, a)(d, c), (a, a), (a, b)}Nenhuma das relacoes e funcao.

1.2.3 Seja f : A 7! B e g : B 7! C. Seja h : A 7! C sua composicao. Em cada um dosseguintes casos, declare as condicoes necessarias e suficientes a que f e g deve atender, demodo que h esteja de acordo com o que foi especificado.

(a) SobrejetoraSolucao:g precisa ser sobrejetora e f precisa ser uma funcao de tal forma que os elementos dasua imagem se relacionem com todos elementos do contra-domınio de g

(b) InjetoraSolucao:g e f precisam ser injetoras

(c) BijetoraSolucao:f precisa ser sobrejetora e g injetora

1.2.4 Se A e B sao conjuntos quaisquer, escrevemos BA para denotar o conjunto de todasas funcoes de A para B. Descreva um isomorfismo natural entre {0, 1}A e 2A.Solucao:

1.3.1 Suponha que R = {(a, c), (c, e), (e, e), (e, b), (d, b), (d, d)}. Desenhe grafos orientadosrepresentando cada uma das seguintes relacoes:

(a) R

(b) R

�1

4

(c) R [R

�1

(d) R \R

�1

1.3.2 Sejam R e S relacoes binarias sobre A = {1, . . . , 7} com as representacoes graficasmostradas a seguir.

Figure 1: 1.3.2

5

(a) Indique se R e S sao (i) simetricas, (ii) reflexivas e (iii) transitivasSolucao: R nao e i, ii nem iii. S e simetrica

(b) Repita (a) para a relacao R [ S.Solucao: R [ S e reflexiva

Figure 2: 1.3.2 b

1.3.3 Desenhe grafos orientados representando relacoes dos seguintes tipos:

(a) Reflexiva, transitiva e anti-simetrica.

(b) Reflexiva, transitiva e nem simetrica nem anti-simetrica.

1.3.4 Seja A um conjunto nao-vazio, e que R ✓ A ⇥ A seja o conjunto vazio. Quais saoas propriedades de R?

(a) Reflexividade.

(b) Simetria.

(c) Anti-simetria.

(d) Transitividade.

6

Figure 3: 1.3.3 a

Figure 4: 1.3.3 b

Solucao: Por definicao (8x)(x /2 R) $ R = ;

Reflexividade: R nao e reflexiva.Prova (por contradicao):1) (8x)((x, x) 2 R), por hipotese de R ser reflexiva2) (8x)((x, x) /2 R), def. de ;3) (x, x) 2 R, Particularizacao Universal (PU) de 14) (x, x) /2 R, PU de 25) (x, x) 2 R ^ (x, x) /2 R, conjuncao de 3 e 46) contradicao

Simetria: R e simetricaProva (por contradicao):

7

1) ⇠ (8x, y)((x, y) 2 R ! (y, x) 2 R), hipotese de contradicao, R nao e simetica.2) (9x, y)((x, y) /2 R ^ (x, y) 2 R), neg 13) (y, x) /2 R, def de ;4) (x, y) /2 R ^ (y, x) 2 R, Particularizacao Existencial (PE) de 25) (x, y) /2 R ^ (y, x) /2 R, conjuncao 3 e 46) contradicao

Transitividade: R e transitivaProva (por contradicao):1) ⇠ (8x, y, z)(xRy ^ yRz ! xRz), hipotese de contradicao, R nao e transitiva.2) ⇠ (8x, y, z)(⇠ (xRy ^ yRz) _ yRz)) Eq. de implicacao 1.3) (9x, y, z)(⇠ (⇠ (xRy ^ yRz) _ xRz))4) ⇠ (⇠ (xRy ^ yRz) _ xRz) PE 35) xRy ^ yRz^ ⇠ xRz De Morgan 46) xRy Simplificao de 57) ⇠ xRy, def de ;8) xRy^ ⇠ xRy, conj 6 e 79) contradicao

Anti-simetria: R e anti-simetricaProva (por contradicao):1) ⇠ (8x, y)(xRy ^ yRz ! x = z) hipotese de contradicao2) ⇠ (8x, y)(⇠ (xRy ^ yRz) _ (x = z)) Equivalencia de implicacao 13) (9x, y, z)(⇠ (⇠ (xRy ^ yRz) _ (x = z))) Negacao 24) ⇠ (⇠ (xRy ^ yRz) _ (x = z)) PE 35) xRy ^ yRz ^ x 6= z De Morgan 46) xRy Simplificacao de 57) ⇠ xRy, def de ;8) xRy ^ xRy, conj. de 6 e 79) contradicao

1.3.5 Seja f : A 7! B. Demonstre que a seguinte relacao R e de equivalencia emA : (a, b) 2 R, se, e somente se f(a) = f(b).Solucao:Reflexiva f(a) = f(a)Simetrica f(a) = f(b) ! f(b) = f(a)Transitiva f(a) = f(b) ^ f(b) = f(c)! f(a) = f(c)! aRb e bRc

! aRc

1.3.6 Seja R ✓ A⇥A uma relacao binaria, conforme definida abaixo. Em que casos R euma relacao de ordem parcial? Em que casos R e uma relacao de ordem total?

8

(a) A = os inteiros positivos; (a, b) 2 R se, e somente se, b e divisıvel por a.Solucao:Nao e ordem total por nao apresentar a relacao de totalidade sobre os inteiros: nem(2, 3), nem (3, 2) pertencem a R. (a, a) pertence a R, portanto e reflexiva. Se a edivisıvel por b, entao a > b ou a = b, se temos aRb e bRa, significa que (a > b oua = b) e (b > a ou b = a), ou seja a = b, portanto R e anti-simetrico. A transitividadeneste caso e trivial. Portanto R e uma ordem parcial.

(b) A = N⇥ N; ((a, b)(c, d)) 2 R se e somente se a c ou b � d. Solucao: ordem parcial

(c) A = N; (a, b) 2 R se e somente se b = a ou b = a+ 1. Solucao: ordem parcial

(d) A e conjunto de todas as palavras de um idioma; (a, b) 2 R se, e somente se, o com-primento de a nao for maior que o comprimento de b. Solucao: ordem parcial

(e) A e o conjunto de todas as palavras de nosso idioma; (a, b) 2 R se, e somente se, a fora mesma que b, ou entao se ocorrer um maior numero de vezes que b no presente livro.Solucao: ordem parcial

1.3.7 Sejam R1 e R2 duas relacoes de ordem parcial quaisquer sobre o mesmo conjuntoA. Demostre que R1 \R2 e uma relacao de ordem parcial.Solucao:Suponhamos R1 e R2 ordens parciais. R1 \R2 = {(x, y)|(x, y) 2 R1 ^ (x, y) 2 R2}- Reflexividade:(x, y) 2 R1 e (x, x) 2 R2 portanto (x, x) 2 R1 \R2

- Anti-Simetria:Seja dois pares (x, y) e (y, x) pertencentes a R1\R2. Como eles pertencem a intersecao de doisconjuntos eles pertencem aos conjuntos individualmente, ou seja, (x, y) 2 R1, (x, y) 2 R2,(y, x) 2 R1, (y, x) 2 R2. Como tanto R1 quanto R2 sao antissimetricos, concluimos quex = y, o que prova que R1 \R2 e antissimetricos- Transitividade:1. (x, y) 2 R1 \R2, hipotese2. (y, z) 2 R1 \R2, hipotese3. (x, y) 2 R1, simp 14. (x, y) 2 R2, simp 15. (y, z) 2 R1, simp 26. (y, z) 2 R2, simp 27. (x, z) 2 R1, transitividade de R1, 3,58. (x, z) 2 R2, transitividade de R2, 4,69. (x, z) 2 R1 \R2, conj, 7,8

1.3.8

9

(a) Prove que, se S for uma colecao qualquer de conjuntos, entao RS = {(A,B) : A,B 2S, eA ✓ B} e uma relacao de ordem parcial.Solucao:i) ReflexividadeARSA porque A ✓ A

ii) Anti-SimetricaA ✓ B e B ✓ A(A,B 2 S)x 2 A ! x 2 B ou x 2 B ! x 2 A

A = BRS e anti-simetricaiii) TransitividadeA ✓ B e B ✓ C

x 2 A ! x 2 B

x 2 B ! x 2 C

x 2 A ! x 2 C

A ✓ C

RS e transitivaRS e uma relacao de ordem parcial.

(b) Seja S = 2{1,2,3}. Desenhe um grafo orientado que represente a relacao de ordem parcialRS definida em (a). Quais sao os elementos mınimos de RS?Solucao: O ; e o mınimo.

Figure 5: 1.3.8 b

1.3.9 Em que circunstancias um grafo orientado representa uma funcao?Solucao:Uma funcao pode ser definida como uma relacao R com a seguinte propriedade.(8x, y, z)(xRy _ xRz ! x = z)Ou seja, x so pode se relacionar (ou ser mapeado) a um e somente um elemento. Em termosdo dıgrafo que representa esta relacao quer dizer que o grau de saıda de todos os nos do

10

dıgrafo e no maximo um.

1.3.10 Demostre que qualquer funcao de um conjunto finito para ele proprio contem umciclo.Solucao:Prova por inducao no tamanho do conjunto. Seja A o conjunto e B = {f |f : A ! A} oconjunto das funcoes de A em A.i) A = {a}, card(A) = 1 ! Tem cicloB = {{(a, a)}}ii) A = {a, b}, card(A) = 2 ! Tem cicloB = {{(a, a), (b, b)}, {(b, a), (a, b)}}iii) Suponha que card(A) = n e que B tenha n! funcoes de A em A, todas contendo ciclos.A = {a1, a2, . . . , an}B = {f1, f2, . . . , fn!}Seja A

0 = A [ {an+1}, card(A0) = n+ 1E as funcoes de A

0em A

0, pertencentes ao conjunto B

0, sao feitas estendendo as funcoes do

domınio A para A [ {an+1}.Seja f 2 B, temos n+1 maneiras de estender f : A ! A essa funcao para g : A[ {an+1} !A [ {an+1}1- Podemos fazer g : A0 ! A

0

2- Ou podemos trocar um elemento de f : tome ak 2 A com f(ak) = aj, faremos a seguinteextensao.g : A0 ! A

0

g(a) = f(a), se a 2 A e a /2 ak

g(a) = an+1, se a 2 A e a = ak

g(a) = aj, se a /2 A e a /2 an+1,Repare que so tenho estas duas opcoes para gerar as funcoes de A

0 = A [ {an+1}, casocontrario terıamos elementos de A

0 que nao seriam cobertos por estas funcoes.

Afirmacao 1: Na construcao (i) temos ciclosProva f : A ! A tem ciclos, e a construcao (i) nao alterou f , so adicionou g(an+1) = an+1.

Afirmacao 2: Na construcao (ii) temos ciclos. Neste caso ha dois casos a considerar.a) Ak nao pertence a um ciclo: o mesmo caso da afirmacao 1.b) Ak pertence a um ciclo: neste caso aparentemente quebramos o ciclo, mas a transformacaoque fizemos mantem o ciclo adicionando um caminho indireto entre ak e aj.Isto completa a prova por inducao.

1.4.1 Demonstre que os seguintes conjuntos sao contaveis:

(a) A uniao de tres conjuntos contaveis quaisquer, nao necessariamente infinitos ou dis-juntos. Solucao:A uniao de conjuntos e associativa. A [B [ C = (A [B) [ C = A [ (B [ C)Ou seja, so e preciso mostrar que a uniao de dois conjuntos contaveis quaisquer e

11

contavel.Um conjunto e contavel se ele e finito (i.e. (9f)(f : {1, 2, . . . , n} ! A ^ f e bijetora),ou existe uma bijecao entre o conjunto A e N.

Fato: Se A e B sao contaveis A [B tambem e.Devemos dividir esta demonstracao em tres partes.i) A e B finitos.card(A) = n e card(B) = m, card(A \B) = n

0

Seja In = {1, 2, . . . , n}, In ! A e g : Im ! B, funcoes bijetivas respectivamente A eB. Sem perda de generalidade supomos m > n e m� n

0> 0.

Vamos criar a funcao g

0 definida da seguinte formag

0 : Im�n0 ! (B � A \ B)g

0, e uma bijecao que mapeia os elementos da parte de B que nao tem elementos emcomum com A. E construıda como a restricao da funcao g, ou seja, continua sendouma bijecao (o que prova que B � A \ B tambem e finito).Iremos construir uma funcao que mapeia todos os elementos de A [ B, esta funcaomapeia inicialmente todos os elementos de A, e depois inclui os elementos de B quenao pertencem a A, usando a funcao g

0.Seja

h In+m�n0 ! A [B

h(x) =

⇢f(x) se x n

g

0(x� n) se x > n

h e uma bijecao, pela propria construcao, pois ela mapeia conjuntos disjuntos (A, Bmenos os elementos de A) usando funcoes bijetoras. O fato de h ser uma bijecao com-pleta a prova de A [ B ser finito e portanto contavel para o caso que consideramos.

ii) A finitos e B infinitamente contavel.- para A (bijecao) : f : In ! A

- para B (bijecao) : g : N ! B

Seja g

0 : N ! (B � A \ B), g

0 construıdo da mesma forma que no caso anterior,como uma restricao ao domınio de g, mas lembrando que este domınio e infinito, entaouma restricao de um numero (os elementos de A) nao altera o domınio (ele continuasendo infinito) e a funcao g

0 continua sendo uma bijecao, pois nao acrescentou novoselementos, so retirou alguns.Iremos construir a funcao h como um mapeamento entre os naturais e A [ B.

h : N ! A [B

h(x) =

⇢f(x) se x n

g

0(x� n) se x > n

h e uma bijecao, pela propria construcao, como no item i). O fato de h ser uma bijecaocompleta a prova de A [ B ser infinitamente contavel.

12

iii) A e B infinitamente contaveis.Sejam as bijecoes f : N ! A e g : N ! B

Vamos construir mais uma vez g0 como uma restricao na imagem de g, tal que ela naocontenha nenhum elemento que pertenca a B e a B simultaneamente, funcao esta quee bijetora pelas mesmas razoes dos itens anteriores.

Prossigamos para a construcao de h. Seja:

h : N ! A [B

h(2n) = f(n)

h(2n� 1) = g

0(n)

Ou seja, dividimos o domınio de N em numeros pares e ımpares, e fizemos cada umdestes subconjuntos serem mapeados para A ou B \ A.h e bijetora, pois cada par e mapeado em um de A, e cada ımpar em um elemento deB que nao pertence a A. Ou seja, com h, N cobre todo o conjunto A [ B. Portanto,A [ B e infinitamente contavel.Assim, provamos que para tres conjuntos contaveis quaisquer, a uniao dos tres econtavel, porque a uniao de dois deles e contavel e o resultado desta uniao com oterceiro e contavel tambem, ou seja, pela propriedade associativa a uniao dos tres econtavel sse a uniao de dois deles e.

(b) O conjunto de todos os subconjuntos finitos de N. Solucao:Seja X o conjunto de todos os subconjuntos finitos de N.

X = {A|9f : In ! AeA ⇢ N} (1)

Podemos visualizar X na seguinte tabela

n Xn

0 ;1 {{1}, {2}, . . . , {n}, . . .}2 {{1, 2}, {1, 3}, . . . , {1, n}, . . . , {2, 3}, . . . , {n,m}}

X =[

Xi

Podemos facilmente verificar o seguinte fato: se x 2 Xi entao x[ {n} 2 Xi+1, para umn qualquer que nao pertenca a x.

13

Fato 1: Xn e contavel (para cada n pertencente aos naturais)Prova: por inducao- X0 e contavel: trivial- Suponha Xn contavel e seja f : N ! Xn

Vamos construir uma funcao f

0 : Xn+1 ! N⇥ N usando a funcao f.se x 2 Xi entao x [ {n} 2 Xn+1

Podemos gerar os elementos de Xn+1 usando os elementos de Xn

f

0(xk [ {n} = (f�1(xk), n)

Reparem que f

0 gera uma tabela N ⇥ N, onde nenhum dos elementos sao iguais (sema diagonal principal), e portanto e bijetora, pois existe uma bijecao entre N e N ⇥ N.O que prova que Xn+1 tambem e contavel, terminando assim a prova por inducao.Como X =

SXi e como acabamos de mostra que para cada i, Xi e contavel, entao a

uniao de varios conjuntos contavel tambem e contavel, ainda mais que estes sao dis-juntos.

1.4.2 Apresente explicitamente bijecoes entre cada um dos seguintes pares de conjuntos:

(a) N e os numeros naturais ımparesSolucao:

f : N ! Imparesf(n) = 2n� 1

f(n) = 2n� 1

(b) N e o conjunto de todos os inteirosSolucao:

f : N ! Z

f(n) =

8<

:�n

2se n e par ou zero

n� 1

2se n e ımpar

(c) N e N⇥ N⇥ NSolucao:Vamos construir uma funcao h : N⇥ N ! N bijetora.

h(n, k) =

8<

:

0 se n = k = 1h(n� 1, k) + n se k = 1 e n > 1h(n, k � 1) + k � 1 caso contrario

14

Vamos usar a funcao anterior para gerar a bijecao de N e N⇥ N⇥ N .

h

0(n, k, l) = h(n, h(k, l))

n|k 1 2 3 4 51 0 1 3 6 102 2 4 7 11 163 5 8 12 174 10 13 185 14 19

15