lista0.1 TecnicasProva Enumerabilidade[solucao]

Prévia do material em texto

Fundamentos de Teoria da Computac¸a˜o DCC/ICEx/UFMG
Prof. Ma´rio S. Alvim 2017/02
SOLUC¸A˜O DE LISTA DE EXERCI´CIOS
Lista 0 - Parte 1/2
(Conceitos Fundamentais: Terminologia, Te´cnicas de Prova, Enumerabilidade)
Leitura necessa´ria:
• Introduc¸a˜o a` Teoria da Computac¸a˜o, 2a Edic¸a˜o (Michael Sipser):
– Cap´ıtulo 0.1: Autoˆmatos, Computabilidade e Complexidade
– Cap´ıtulo 0.2: Noc¸o˜es e Terminologia Matema´ticas
– Cap´ıtulo 0.3: Definic¸o˜es, Teoremas e Provas
– Cap´ıtulo 0.4: Tipos de Prova
• Material suplementar:
– Conjunto de slides: Aula 0.1 - Terminologia, Te´cnicas de Prova, Enumerabilidade.
Revisa˜o.
1. Responda formalmente a`s seguintes perguntas:
(a) O que e´ um conjunto enumera´vel?
Soluc¸a˜o do professor: Um conjunto enumera´vel e´ aquele para o qual se pode encontrar uma
bijec¸a˜o entre seus elementos e o conjunto dos nu´meros naturais.
(b) Deˆ dois exemplos de conjuntos infinitos que sejam enumera´veis, e dois exemplos de conjuntos
infinitos que na˜o sejam enumera´veis.
Soluc¸a˜o do professor: O conjunto dos inteiros e´ infinito e enumera´vel. O conjunto dos ra-
cionais e´ infinito e enumera´vel. O conjunto (0, 1), os reais no intervalo aberto de 0 a 1, e´ na˜o-
enumera´vel. O conjunto dos nu´meros complexos e´ na˜o-enumera´vel.
Exerc´ıcios.
2. (Sipser 0.7) Para cada item, deˆ uma relac¸a˜o que satisfac¸a a condic¸a˜o.
a) Reflexiva e sime´trica, mas na˜o transitiva.
Soluc¸a˜o do professor: Considere uma relac¸a˜o R sobre o conjunto de todas as pessoas que ja´
comeram pizza tal que xRy se, e somente se, x e y ja´ dividiram uma pizza. A relac¸a˜o e´ reflexiva
(todo mundo que comeu pizza ja´ dividiu uma pizza consigo mesmo), sime´trica (se x dividiu uma
pizza com y, enta˜o y dividiu uma pizza com x), mas na˜o e´ transitiva (eu ja´ dividi uma pizza com
minha ma˜e, e minha ma˜e ja´ dividiu uma pizza com meu avoˆ, mas eu nunca dividi uma pizza com
meu avoˆ).
b) Reflexiva e transitiva, mas na˜o sime´trica.
1
Soluc¸a˜o do professor: A relac¸a˜o de menor ou igual ≤ sobre os nu´meros reais e´ reflexiva (todo
real e´ menor ou igual a si mesmo), transitiva (se x ≤ y e y ≤ z, enta˜o x ≤ z, para todo x, y, z ∈ R),
mas na˜o e´ sime´trica (tome 3 ≤ 5, mas 5 6≤ 3).
c) Sime´trica e transitiva, mas na˜o reflexiva.
Soluc¸a˜o do professor: Considere uma relac¸a˜o R sobre os reais tais que xRy se, e somente se,
xy > 0. A relac¸a˜o e´ sime´trica (se xy > 0 enta˜o yx > 0), transitiva (se xy > 0 e yz > 0, enta˜o
xz > 0, pois x, y e z nesse caso devem ter todos o mesmo sinal), mas na˜o e´ reflexiva (o nu´mero 0
na˜o se relaciona a si mesmo).
3. Use uma prova direta para mostrar que o produto de dois nu´meros ı´mpares e´ ı´mpar.
Soluc¸a˜o do professor: Sejam m e n dois inteiros ı´mpares. Enta˜o existem inteiros k e k′ tais
que m = 2k + 1 e n = 2k′ + 1. Assim, podemos calcular o produto mn = (2k + 1)(2k′ + 1) =
4kk′+ 2k+ 2k′+ 1 = 2(2kk′+ k+ k′) + 1. Como 2kk′+ k+ k′ e´ tambe´m um nu´mero inteiro, podemos
concluir que mn e´ ı´mpar, pois trata-se do dobro de um inteiro mais um.
4. Use uma prova por contradic¸a˜o para mostrar que a soma de um nu´mero irracional e um nu´mero
racional e´ irracional.
Soluc¸a˜o do professor: Seja i um nu´mero irracional e r um nu´mero racional. Como r e´ racional,
existem inteiros p e q tais que r = p/q.
Por contradic¸a˜o, assuma que a soma i + r e´ racional. Neste caso, existiriam inteiros x e y tais que
i + r = x/y, ou seja, i = x/y − r. Mas como r = p/q, ter´ıamos i = x/y − p/q = (qx−py)/(qy). Note que
como tanto qx − py quanto qy sa˜o inteiros, isso significaria que i = (qx−py)/qy seria racional. Mas
isto contradiz a nossa hipo´tese de que i e´ irracional. Como chegamos a uma contradic¸a˜o, devemos
concluir que a hipo´tese de que a soma i + r e´ racional esta´ errada, e, portanto, a soma deve sempre
ser irracional.
5. Demonstre que 1 · 1! + 2 · 2! + · · ·+ n · n! = (n + 1)!− 1, para n ≥ 1. Use induc¸a˜o matema´tica.
Soluc¸a˜o do professor: Por induc¸a˜o.
Passo base.
1 · 1! = (1 + 1)!− 1
Passo indutivo.
1 · 1! + · · ·+ n · n! + (n + 1) · (n + 1)! = (n + 1)!− 1 + (n + 1) · (n + 1)! (pela hipo´tese de induc¸a˜o)
= (1 + (n + 1))(n + 1)!− 1
= ((n + 1) + 1)!− 1
6. Demonstre que 5 divide n5 − n sempre que n e´ um inteiro na˜o-negativo. Use induc¸a˜o matema´tica.
2
Soluc¸a˜o do professor: Por induc¸a˜o.
Passo base. 0 divide 05 − 0 = 0.
Passo indutivo. Assumimos como hipo´tese de induc¸a˜o que para um n arbitra´rio, n5− n = 5k para
algum k inteiro. Logo, para n + 1 teremos:
(n + 1)5 − (n + 1) = (n5 + 5n4 + 10n3 + 10n2 + 5n + 1)− (n + 1) (produto nota´vel)
= (n5 − n) + (5n4 + 10n3 + 10n2 + 5n) (reagrupando parecelas)
= 5k + 5(n4 + 2n3 + 2n2 + n) (pela hip. de induc¸a˜o)
= 5(k + n4 + 2n3 + 2n2 + n) ,
de onde conclu´ımos que (n + 1)5 − (n + 1) tambe´m e´ divis´ıvel por 5.
7. Determine se cada um dos conjuntos abaixo e´ enumera´vel ou na˜o. Para aqueles enumera´veis, exiba
uma enumerac¸a˜o mostrando os 10 primeiros elementos.
(a) os inteiros maiores do que 10;
Soluc¸a˜o do professor: Enumera´vel: 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, . . .
(b) os inteiros ı´mpares negativos;
Soluc¸a˜o do professor: Enumera´vel: −1,−3,−5,−7,−9,−11,−13,−15,−17,−19, . . .
(c) os nu´meros reais entre 0 e 2;
Soluc¸a˜o do professor: Na˜o-enumera´vel: o intervalo na˜o-enumera´vel (0, 1) esta´ contido neste
conjunto.
(d) os inteiros mu´ltiplos de 10.
Soluc¸a˜o do professor: Enumera´vel: 0, 10,−10, 20,−20, 30,−30, 40,−40, 50, . . .
8. Deˆ um exemplo de dois conjuntos na˜o-enumera´veis A e B tais que A ∩B seja:
(a) Finito.
(b) Infinito enumera´vel.
(c) Na˜o-enumera´vel.
Soluc¸a˜o do professor: Nesta questa˜o, a notac¸a˜o (a, b) indica o intervalo real aberto comec¸ando em
a ∈ R e terminando em b ∈ R.
(a) A = (1, 2), B = (3, 4), A ∩B = ∅ e´ finito.
(b) A = (1, 2) ∪ Z, B = (3, 4) ∪ Z, A ∩B = Z e´ infinito enumera´vel.
(c) A = (1, 3), B = (2, 4), A ∩B = (2, 3) e´ na˜o-enumera´vel.
9. Mostre que o conjunto Z× Z e´ enumera´vel.
3
Soluc¸a˜o do professor: Podemos enumerar os elementos de Z×Z conforme o quadro abaixo. Cada
linha do quadro corresponde a um elemento de Z, e cada coluna tambe´m corresponde a um elemento
de Z, de forma que cada ce´lula do quadro corresponde ao par ordenado formado pela linha e coluna
correspondentes. Os c´ırculos representam uma enumerac¸a˜o poss´ıvel dos elementos de Z× Z.
Z× Z 0 1 −1 2 −2 3 −3 . . .
0 (0, 0) 1 (0, 1) 2 (0,−1) 4 (0, 2) 7 (0,−2) 11 (0, 3) 16 (0,−3) 22 . . .
1 (1, 0) 3 (1, 1) 5 (1,−1) 8 (1, 2) 12 (1,−2) 17 (1, 3) 23 (1,−3) . . . . . .
−1 (−1, 0) 6 (−1, 1) 9 (−1,−1) 13 (−1, 2) 18 (−1,−2) 24 (−1, 3) . . . (−1,−3) . . . . . .
2 (2, 0) 10 (2, 1) 14 (2,−1) 19 (2, 2) 25 (2,−2) . . . (2, 3) . . . (2,−3) . . . . . .
−2 (−2, 0) 15 (−2, 1) 20 (−2,−1) 26 (−2, 2) . . . (−2,−2) . . . (−2, 3) . . . (−2,−3) . . . . . .
3 (3, 0) 21 (3, 1) 27 (3,−1) . . . (3, 2) . . . (3,−2) . . . (3, 3) . . . (3,−3) . . . . . .
−3 (−3, 0) 28 (−3, 1) . . . (−3,−1) . . . (−3, 2) . . . (−3,−2) . . . (−3, 3) . . . (−3,−3) . . . . . .
Uma soluc¸a˜o alternativa e´ produzir a seguinte enumerac¸a˜o, em que as tuplas sa˜o ordenadas de acordo
com a soma dos mo´dulos de suas coordenadas:
(0, 0),
(0, 1), (0,−1), (1, 0), (−1, 0),
(0, 2), (0,−2), (1, 1), (1,−1), (−1, 1), (−1,−1), (2, 0), (−2, 0),
(0, 3), (0,−3), (1, 2), (1,−2), (−1, 2), (−1,−2), (2, 1), (2,−1), (−2, 1), (−2,−1), (3, 0), (−3, 0),
(0, 4), (0,−4), (1, 3), (1,−3), (−1, 3), (−1,−3), (2, 2), (2,−2), (−2, 2), (−2,−2), (3, 1), (3,−1), . . .
4