[SOLUTIONS] Introducao aos Fundamentos da Computacao - Newton

Prévia do material em texto

Soluc¸o˜es dos Exerc´ıcios Propostos no Livro
Introduc¸a˜o aos Fundamentos da Computac¸a˜o:
Linguagens e Ma´quinas
(Ed. Thomson, 2006)
Newton Jose´ Vieira
Departamento de Cieˆncia da Computac¸a˜o
Instituto de Cieˆncias Exatas
Universidade Federal de Minas Gerais
Belo Horizonte, 30/06/2007
Pec¸o a quem encontrar erros nas soluc¸o˜es a seguir entrar em contato com o autor no
enderec¸o nvieira@dcc.ufmg.br. Antecipadamente, agradec¸o
2
Cap´ıtulo 1
Conceitos Preliminares
1.1 Representac¸a˜o
Nesta sec¸a˜o na˜o ha´ exerc´ıcios.
1.2 Prova de Teoremas
1. a) A afirmativa (α ∧ β) → α so´ e´ falsa se α ∧ β e´ verdadeira e α e´ falsa. Mas a α ∧ β
na˜o pode ser verdadeira se α e´ falsa. Assim, (α ∧ β)→ α na˜o pode ser falsa; logo, e´
va´lida.
b) A afirmativa α→ (α ∨ β) so´ e´ falsa se α e´ verdadeira e α ∨ β e´ falsa. Mas, sendo α
verdadeira, α ∨ β na˜o pode ser falsa. Assim, α→ (α ∨ β) na˜o pode ser falsa; logo, e´
va´lida.
c) A afirmativa (α ∧ ¬α) → β so´ pode ser falsa se α ∧ ¬α e´ verdadeira e β e´ falsa.
Mas a afirmativa α ∧ ¬α na˜o pode ser verdadeira, pois e´ uma contradic¸a˜o. Assim,
(α ∧ ¬α)→ β na˜o pode ser falsa; logo, e´ va´lida.
d) A afirmativa α→ (β ∨¬β) so´ e´ falsa se α e´ verdadeira e β ∨¬β e´ falsa. Mas, β ∨¬β
na˜o pode ser falsa, pois β e ¬β na˜o podem ser ambas falsas. Assim, α → (β ∨ ¬β)
na˜o pode ser falsa; logo, e´ va´lida.
e) A afirmativa (α → β) ∨ α so´ pode ser falsa se ambas, α → β e α sa˜o falsas. Mas,
sendo α falsa, α → β e´ verdadeira. Assim, (α → β) ∨ α na˜o pode ser falsa; logo, e´
va´lida.
f) A afirmativa (α→ β)∨ (β → α) so´ pode ser falsa se α→ β e β → α sa˜o falsas. Para
α→ β ser falsa, α deve ser verdadeira (e β falsa), e para β → α ser falsa, α deve ser
falsa (e β verdadeira); contradic¸a˜o! Assim, a afirmativa original na˜o pode ser falsa;
logo, e´ va´lida.
2. a) Suponha que α → β e´ verdadeira. Segue-se que α e´ falsa ou β e´ verdadeira. No
primeiro caso, ¬α e´ verdadeira e, portanto, ¬β → ¬α e´ verdadeira. No segundo caso,
¬β e´ falsa e, portanto, ¬β → ¬α e´ tambe´m verdadeira. Logo, (α → β) ⇒ (¬β →
¬α). Suponha, por outro lado, que α → β e´ falsa. Segue-se que α e´ verdadeira e β
e´ falsa. Com isto, ¬α e´ falsa e ¬β e´ verdadeira e, portanto, ¬β → ¬α e´ falsa. Logo,
(¬α→ ¬β)⇒ (α→ β).
b) Primeiro, mostra-se que (α∨β)→ γ ⇒ [(α→ γ)∧(β → γ)]: Suponha que (α∨β)→ γ
e´ verdadeira. Segue-se que α ∨ β e´ falsa ou γ e´ verdadeira. No primeiro caso, α e
β sa˜o falsas e, portanto, α → γ e β → γ sa˜o verdadeiras. No segundo caso, sendo
3
γ verdadeira, α → γ e β → γ sa˜o tambe´m verdadeiras. Assim, se (α ∨ β) → γ e´
verdadeira, (α→ γ)∧(β → γ) e´ verdadeira. Logo, (α∨β)→ γ ⇒ [(α→ γ)∧(β → γ)].
Resta mostrar que [(α → γ) ∧ (β → γ)] ⇒ (α ∨ β) → γ. Para isto, suponha que
(α→ γ)∧(β → γ) e´ verdadeira; segue-se que α→ γ e β → γ sa˜o verdadeiras. Destas
duas segue-se que γ e´ verdadeira ou α e β sa˜o falsas, e, neste u´ltimo caso, α ∨ β e´
falsa. Mas, sendo γ verdadeira ou α ∨ β falsa, (α ∨ β) → γ e´ verdadeira. Portanto,
[(α→ γ) ∧ (β → γ)]⇒ (α ∨ β)→ γ.
c) Suponha que α→ (β ∧ γ) e´ verdadeira. Segue-se que α e´ falsa ou β ∧ γ e´ verdadeira.
No primeiro caso, sendo α falsa, α → β e α → γ sa˜o verdadeiras. No segundo caso,
sendo β verdadeira, α → β e´ verdadeira, e sendo γ verdadeira, α → γ e´ verdadeira.
Logo, (α → (β ∧ γ)) ⇒ ((α → β) ∧ (α → γ)). Suponha, agora, que α → (β ∧ γ) e´
falsa. Segue-se que α e´ verdadeira e (β ∧ γ) e´ falsa, ou seja, β e´ falsa ou γ e´ falsa.
Com isto, α → β e´ falsa ou α → γ e´ falsa e, portanto, (α → β) ∧ (α → γ) e´ falsa.
Logo, α→ (β ∧ γ)⇒ (α→ β) ∧ (α→ γ).
3. a) Na˜o existe atribuic¸a˜o de valor-verdade para α tal que ambas, α e ¬α sejam verdeiras.
Assim, por vacuidade, sempre α e ¬α sa˜o verdadeiras, γ tambe´m e´.
b) Se α→ γ e´ verdadeira, enta˜o α e´ falsa ou γ e´ verdadeira. No primeiro caso, α ∧ β e´
falsa e, portanto, (α ∧ β)→ γ e´ verdadeira. No segundo caso, sendo γ e´ verdadeira,
(α ∧ β)→ γ e´ tambe´m verdadeira. Conclui-se, enta˜o que {α→ γ} ⇒ (α ∧ β)→ γ.
c) Suponha que ¬α→ β e ¬β sejam verdadeiras. Neste caso, β e´ falsa e, portanto, ¬α
e´ falsa. Sendo ¬α falsa, α e´ verdadeira. Logo, se ¬α→ β e ¬β sa˜o verdadeiras, α e´
verdadeira, ou seja, {¬α→ β,¬β} ⇒ α.
4. Sejam x e y nu´meros reais tais que x > 0 e x < y. Destas duas u´ltimas segue-se que
x2 < xy. Das mesmas, segue-se tambe´m que y > 0. Desta e do fato de que x < y,
deduz-se que xy < y2. De x2 < xy e xy < y2, conclui-se que x2 < y2.
5. Sejam x e y nu´meros reais arbitra´rios. Suponha que x2+ y = 13 e y 6= 4. Deve-se mostrar
que, neste caso, x 6= 3. Suponha o contra´rio: x = 3. Enta˜o, substituindo-se x por 3 em
x2 + y = 13, obte´m-se: 32 + y = 13 e, assim, y = 13 − 9 = 4. Contradic¸a˜o. Logo, se
x2 + y = 13 e y 6= 4, enta˜o x 6= 3.
6. Seja x um nu´mero real tal que x > 2. Seja k = (x +
√
x2 − 4)/2; observe que k e´ um
nu´mero real, pois x > 2. Ale´m disso,
k +
1
k
=
x+
√
x2 − 4
2
+
1
(x+
√
x2 − 4)/2 =
x+
√
x2 − 4
2
+
2
x+
√
x2 − 4.
Fazendo-se as operac¸o˜es e simplificando-se obte´m-se:
k +
1
k
==
x2 + 2x
√
x2 − 4 + x2 − 4 + 4
2x+ 2
√
x2 − 4 = x.
Conclui-se, enta˜o, que para todo nu´mero real x, se x > 2, existe um nu´mero y tal que
y + (1/y) = x.
7. Seja x um nu´mero natural. A prova sera´ feita pela contrapositiva. Suponha, assim, que√
x e´ um nu´mero racional. Neste caso,
√
x = p/q, onde p e q sa˜o nu´meros naturais primos
entre si. Segue-se que x = p2/q2. Como p e q sa˜o primos entre si, p2 e q2 sa˜o primos entre
si, e como x e´ um nu´mero natural q2 so´ pode ser 1 e x = p2. Portanto, para todo nu´mero
natural x, se x na˜o e´ e´ um quadrado perfeito,
√
x na˜o e´ um nu´mero racional.
4
8. Seja n um nu´mero inteiro na˜o divis´ıvel por 3. Enta˜o n = 3q + r, onde q e´ um inteiro e
r ∈ {1, 2}. Caso 1: r = 1. Tem-se que n2 = (3q + 1)2 = 9q2 + 6q + 1 = 3(3q2 + 2q) + 1.
Fazendo-se k = 3q2 + 2q tem-se que k e´ um inteiro tal que n2 = 3k + 1, como requerido.
Caso 2: r = 2. Tem-se que n2 = (3q+2)2 = 9q2+12q+4 = 3(3q2+4q+1)+1. Fazendo-se
k = 3q2 + 4q + 1 tem-se que k e´ um inteiro tal que n2 = 3k + 1.
1.3 Conjuntos
1. a) A ∩B = {0, 1, 2, 3, 4, 5}.
b) C = {−4,−2, 0, 2, 4, 6, 8}.
c) D = {−5,−4,−3,−2,−1, 6, 7, 8}.
d) {(0, 7), (2, 7), (4, 7)}.
2. Resposta para a primeira pergunta: A−B = B −A se, e somente se, A = B. Prova:
(←) Suponha que A = B. Enta˜o A−B = B −A = ∅.
(→) Suponha que A−B = B −A. Para provar, primeiramente, que A ⊆ B, seja x ∈ A.
Suponha que x 6∈ B. Neste caso, x ∈ A − B, e, como A − B = B − A, x ∈ B − A.
Mas, neste caso, x ∈ B e x 6∈ A. Contradic¸a˜o. Assim, se x ∈ A, enta˜o x ∈ B, ou
seja, A ⊆ B. Prova-se que B ⊆ A de forma ana´loga.
Resposta para a segunda pergunta: A ∪B = A ∩B se, e somente se, A = B. Prova:
(←) Suponha que A = B. Enta˜o A ∪B = A ∩B = A = B.
(→) Suponha que A ∪ B = A ∩ B. Para provar, primeiramente, que A ⊆ B, seja x ∈ A.
Com isto, x ∈ A ∪ B. Neste caso, como A ∪ B = A ∩ B, x ∈ A ∩ B. Assim x ∈ B.
Portanto, se x ∈ A, enta˜o x ∈ B, ou seja, A ⊆ B. Prova-se que B ⊆ A de forma
ana´loga.
3. Sera´ mostrado que A ∪B = A ∪ C se, e somente se, (B −C) ∪ (C −B) ⊆ A. (Ou seja, a
condic¸a˜o procurada e´: a diferenc¸a sime´trica entre B e C deve estar contida em A, mesmo
que B 6= C.)
(→) Suponha que A ∪B = A ∪C. Seja x um elemento arbitra´rio de (B −C) ∪ (C −B).
Caso 1: x ∈ B − C, ou seja x ∈ B e x 6∈ C. Como x ∈ B e A ∪B = A ∪C, segue-se
que x ∈ A ∪ C. Desta e de x 6∈ C, conclui-se que x ∈ A. Caso 2: ana´logo. Portanto,
se x ∈ (B − C) ∪ (C −B), enta˜o x ∈ A. Logo, (B − C) ∪ (C −B) ⊆ A.
(→) Suponha que (B−C)∪(C−B) ⊆ A. Para provar, primeiramente, que A∪B ⊆ A∪C,
seja x ∈ A ∪ B. Caso 1: x ∈ A. Enta˜o x ∈ A ∪ C. Caso 2: x ∈ B. Neste caso, se
x ∈ C, x ∈ A ∪ C, e se x 6∈ C, x ∈ B − C; e como B − C ⊆ A, x ∈ A e, portanto,
x ∈ A∪C. Assim, se x ∈ A∪B, enta˜o x ∈ A∪C, ou seja A∪B ⊆ A∪C. De forma
ana´loga, A ∪ C ⊆ A ∪B. Portanto, A ∪ C = A ∪B.
4. a) Basta provar que ∀x[x ∈ A ∪B ↔ x ∈ A∩B]. Seja, enta˜o, um elemento x arbitra´rio.
Tem-se:
x ∈ A ∪B ↔ x 6∈ A ∪B pela definic¸a˜o de complemento
↔ ¬(x ∈ A ou x ∈ B) pela definic¸a˜ode unia˜o
↔ x 6∈ A e x 6∈ B por DeMorgan
↔ x ∈ A e x ∈ B pela definic¸a˜o de complemento
↔ x ∈ A ∩B pela definic¸a˜o de intersec¸a˜o.
5
b) Suponha que A∩B = A∪B. Inicialmente, prova-se que A ⊆ B. Seja x um elemento
arbitra´rio de A. Neste caso, x ∈ A ∪ B; e como A ∩ B = A ∪ B, x ∈ A ∩ B. Logo,
x ∈ B e, portanto, A ⊆ B. Prova-se que B ⊆ A de forma similar. Portanto, A = B.
Conclui-se que se A ∩B = A ∪B enta˜o A = B.
c) Basta provar que ∀x[x ∈ (A−B) ∪ (B −A)↔ x ∈ (A ∪B)− (A ∩B)]. Assim, seja
um elemento x arbitra´rio. Tem-se:
(→) Suponha que x ∈ (A−B)∪ (B−A). Caso 1: x ∈ A−B. Enta˜o x ∈ A e x 6∈ B.
Como x ∈ A, x ∈ A∪B, e como x 6∈ B, x 6∈ A∩B. Portanto, x ∈ (A∪B)− (A∩B).
O caso 2, x ∈ B −A, e´ similar.
(→) Suponha que x ∈ (A ∪B)− (A ∩B). Enta˜o x ∈ A ∪B e x 6∈ A ∩ B. Segue-se,
enta˜o, que x ∈ A ou x ∈ B e tambe´m que x 6∈ A ou x 6∈ B. Assim, so´ se pode ter
dois casos: o caso em que x ∈ A e x 6∈ B e caso em que x ∈ B e x 6∈ A. Em outras
palavras, x ∈ A−B ou x ∈ B −A. Portanto, x ∈ (A−B) ∪ (B −A).
d) Basta provar que ∀x[x ∈ A − (A − B) ↔ x ∈ A ∩ B]. Seja, enta˜o, um elemento x
arbitra´rio. Tem-se:
x ∈ A− (A−B) ↔ x ∈ A e x 6∈ A−B pela def. de diferenc¸a
↔ x ∈ A e (x 6∈ A ou x ∈ B) pela def. de diferenc¸a
↔ (x ∈ A e x 6∈ A) ou (x ∈ A e x ∈ B) pela distrib. e/ou
↔ x ∈ A e x ∈ B
↔ x ∈ A ∩B pela def. de intersec¸a˜o.
e) Basta provar que ∀x[x ∈ (A−B)−C ↔ x ∈ A− (B ∪C]. Assim, seja um elemento
x arbitra´rio. Tem-se:
x ∈ (A−B)− C↔ x ∈ A−B e x 6∈ C pela def. de diferenc¸a
↔ x ∈ A e x 6∈ B e x 6∈ C pela def. de diferenc¸a
↔ x ∈ A e ¬(x ∈ B ou x ∈ C) pela lei de De Morgan
↔ x ∈ A e x 6∈ B ∪C pela def. de unia˜o
↔ x ∈ A− (B ∪ C) pela def. de diferenc¸a.
f) Basta provar que ∀x[x ∈ (A − B) − C ↔ x ∈ (A − C) − (B − C]. Assim, seja um
elemento x arbitra´rio. Tem-se:
x ∈ (A−B)− (B − C)↔ (x ∈ A e x 6∈ C) e x 6∈ B − C
pela def. de diferenc¸a
↔ (x ∈ A e x 6∈ C) e (x 6∈ B ou x ∈ C)
pela def. de diferenc¸a
↔ (x ∈ A e x 6∈ C e x 6∈ B) ou (x ∈ A e x 6∈ C e x ∈ C)
pela distr. e/ou
↔ x ∈ A e x 6∈ C e x 6∈ B
↔ x ∈ A−B e x 6∈ C pela def. de diferenc¸a
↔ x ∈ (A−B)− C pela def. de diferenc¸a
g) Seja um par (x, y) arbitra´rio. Tem-se:
(x, y) ∈ A× (B ∩C)↔ x ∈ A ∧ y ∈ B ∩ C pela def. de produto
↔ x ∈ A ∧ y ∈ B ∧ y ∈ C pela def. de intersec¸a˜o
↔ (x ∈ A ∧ y ∈ B) ∧ (x ∈ A ∧ y ∈ C)
↔ x ∈ A×B ∧ x ∈ A× C pela def. de produto
↔ x ∈ (A×B) ∩ (A× C) pela def. de intersec¸a˜o
6
h) Seja um par (x, y) arbitra´rio. Tem-se:
(x, y) ∈ (A ∩B)× (C ∩D)↔ x ∈ (A ∩B) ∧ y ∈ (C ∩D)
pela def. de produto
↔ x ∈ A ∧ x ∈ B ∧ y ∈ C ∧ y ∈ D
pela def. de intersec¸a˜o
↔ (x ∈ A ∧ y ∈ C) ∧ (x ∈ B ∧ y ∈ D)
por associatividade
↔ x ∈ A× C ∧ x ∈ B ×D
pela def. de produto
↔ x ∈ (A× C) ∩ (B ×D)
pela def. de intersec¸a˜o
5. As partic¸o˜es de {1, 2} sa˜o: {{1}, {2}} e {{1, 2}}. As partic¸o˜es de {1, 2, 3} sa˜o: {{1}, {2}, {3}},
{{1}, {2, 3}}, {{2}, {1, 3}}, {3}, {1, 2}} e {{1, 2, 3}}. E as partic¸o˜es de {1, 2, 3, 4} sa˜o:
{{1}, {2}, {3}, {4}}, {{1}, {2}, {3, 4}}, {{1}, {3}, {2, 4}}, {{1}, {4}, {2, 3}}, {{2}, {3}, {1, 4},
{{2}, {4}, {1, 3}}, {{3}, {4}, {1, 2}}, {{1}, {2, 3, 4}}, {{2}, {1, 3, 4}}, {{3}, {1, 2, 4}}, {{4}, {1, 2, 3}},
{{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2, 3}} e {{1, 2, 3, 4}}.
Segue a func¸a˜o part(A), que retorna o conjunto das partic¸o˜es do conjunto (finito) A:
Entrada: um conjunto finito A.
Sa´ıda: o conjunto das partic¸o˜es de A.
se A = ∅ enta˜o retorne ∅ fimse;
R← ∅;
selecione um elemento a ∈ A;
para cada B ⊂ A tal que a ∈ B fac¸a
para cada X ∈ part(A−B) fac¸a
R← R ∪ {{B} ∪X};
fimpara
fimpara;
retorne R ∪ {{A}}.
1.4 Relac¸o˜es
1. a) A relac¸a˜o ⊂ e´ transitiva, na˜o e´ reflexiva nem sime´trica.
b) A relac¸a˜o na˜o e´ reflexiva, nem sime´trica nem transitiva.
c) A relac¸a˜o e´ reflexiva e transitiva, e na˜o e´ sime´trica.
d) A relac¸a˜o e´ reflexiva e transitiva, e na˜o e´ sime´trica.
e) A relac¸a˜o e´ reflexiva, sime´trica e transitiva.
2. Sejam R1 ⊆ A2 e R2 ⊆ B2
a) Se R1 e R2 sa˜o reflexivas, R1∪R2 e´ reflexiva sobre A∪B: Seja x ∈ A∪B. Se x ∈ A,
(x, x) ∈ R1, pois R1 e´ reflexiva, e se x ∈ B, (x, x) ∈ R2, pois R2 e´ reflexiva. Assim,
(x, x) ∈ R1 ∪R2.
7
Se R1 e R2 sa˜o reflexivas, R1 ∩ R2 e´ reflexiva sobre A ∩ B: Seja x ∈ A ∩ B. Como
x ∈ A e x ∈ B, (x, x) ∈ R1 e (x, x) ∈ R2 pois R1 e R2 sa˜o reflexivas. Assim,
(x, x) ∈ R1 ∩R2.
b) Se R1 e R2 sa˜o sime´tricas, R1 ∪R2 e´ sime´trica sobre A∪B: Sejam x, y ∈ A ∪B. Se
x, y ∈ A e (x, y) ∈ R1, enta˜o (y, x) ∈ R1 e, analogamente, se x, y ∈ B e (x, y) ∈ R2,
enta˜o (y, x) ∈ R2, pois R1 e R2 sa˜o sime´tricas. Por outro lado, se x ∈ A − B e
y ∈ B − A, ou vice-versa, ou seja, x e y na˜o pertencem ao mesmo conjunto, na˜o se
pode ter (x, y) ∈ R1 nem (x, y) ∈ R2. Assim, em qualquer caso, se x, y ∈ A ∪ B e
(x, y) ∈ R1 ∪R2, (y, x) ∈ R1 ∪R2.
Se R1 e R2 sa˜o sime´tricas, R1 ∩ R2 e´ sime´trica sobre A ∩ B: Sejam x, y ∈ A ∩ B.
Como x, y ∈ A e x, y ∈ B (y, x) ∈ R1 e (y, x) ∈ R2, pois R1 e R2 sa˜o sime´tricas.
Portanto, se x, y ∈ A ∩B e (x, y) ∈ R1 ∩R2, (y, x) ∈ R1 ∩R2.
c) SeR1 eR2 sa˜o transitivas, R1∪R2 pode na˜o ser transitiva. Por exemplo, R1 = {(a, b)}
sobre {a, b} e R2 = {(b, c)} sobre {b, c}; tem-se que R1 ∪ R2 = {(a, b), (b, c)} sobre
{a, b, c}, que na˜o e´ transitiva, pois (a, c) 6∈ R1 ∪R2.
A relac¸a˜o R1∩R2 e´ transitiva sobreA∩B: Dado que (x, y) ∈ R1∩R2 e (y, z) ∈ R1∩R2,
segue-se que (x, y) ∈ R1 e (y, z) ∈ R1, e tambe´m que (x, y) ∈ R2 e (y, z) ∈ R2. Como
R1 e R2 sa˜o transitivas, deduz-se que (x, z) ∈ R1 e (x, z) ∈ R2. Logo, (x, z) ∈ R1∩R2.
3. (→) Suponha que R e´ sime´trica. Sejam x e y elementos arbitra´rios tais que (x, y) ∈ R.
Como R e´ sime´trica, segue-se que (y, x) ∈ R. Desta u´ltima, segue-se que (x, y) ∈ R−1.
Logo, se (x, y) ∈ R, enta˜o (x, y) ∈ R−1, ou seja, R ⊆ R−1. De forma similar, mostra-se
que R−1 ⊆ R. Portanto, R = R−1.
(←) Suponha que R = R−1 e seja (x, y) ∈ R. Segue-se que (x, y) ∈ R−1 e, portanto,
(y, x) ∈ R. Logo, se (x, y) ∈ R enta˜o (y, x) ∈ R. Como (x, y) e´ um elemento arbitra´rio de
R, conclui-se que R e´ sime´trica.
4. (→) Suponha que R e´ reflexiva sobre um conjunto A. Seja x um elemento arbitra´rio de
A. Como R e´ reflexiva, segue-se que (x, x) ∈ R. Segue-se, pela definic¸a˜o de inversa, que
(x, x) ∈ R−1. Logo, R−1 e´ reflexiva sobre A.
(←) Suponha que R−1 e´ reflexiva sobre um conjunto A. Seja x um elemento arbitra´rio de
A. Como R−1 e´ reflexiva, segue-se que (x, x) ∈ R−1. Segue-se, pela definic¸a˜o de inversa,
que (x, x) ∈ R. Logo, R e´ reflexiva sobre A.
5. (→) Suponha que R e´ anti-sime´trica. Sejam x e y elementos arbitra´rios de A tais que
(x, y) ∈ R∩R−1, ou seja, (x, y) ∈ R e (x, y) ∈ R−1. Desta u´ltima, segue-se que (y, x) ∈ R.
Como R e´ anti-sime´trica, (x, y) ∈ R e (y, x) ∈ R, segue-se que x = y e, portanto,
(x, y) ∈ ιA. Assim, R ∩R−1 ⊆ ιA.
(←) Suponha que R ∩ R−1 ⊆ ιA. Sejam x e y tais que (x, y) ∈ R e (y, x) ∈ R. Como
(y, x) ∈ R, (x, y) ∈ R−1, e, portanto, (x, y) ∈ R∩R−1. Como R∩R−1 ⊆ ιA, segue-se que
(x, y) ∈ ιA e, portanto, x = y. Conclui-se que se (x, y) ∈ R e (y, x) ∈ R, enta˜o x = y.
Portanto, R e´ anti-sime´trica.
6. Nesta questa˜o, considere que se o denominador nas operac¸o˜es de divisa˜o for 0, o resultado
e´ sempre o mesmo (“indefinido”) e diferente de qualquer outro resultado.
Como x1/x2 = x1/x2 para quaisquer x1, x2 ∈ N, R e´ reflexiva. Suponha que x1/x2 =
y1/y2, para x1, x2, y1, y2 ∈N. Segue-se que y1/y2 = x1/x2. Logo, R e´ sime´trica. Supondo-
se que x1/x2 = y1/y2 e y1/y2 = z1/z2, conclui-se que x1/x2 = z1/z2. Portanto, R e´
transitiva. Como R e´ reflexiva, sime´trica e transitiva, R e´ uma relac¸a˜o de equivaleˆncia.
8
Para cada par (x1, x2) ∈ N2 ha´ a classe de equivaleˆncia {(y1, y2) ∈ N2 | y1/y2 = x1/x2},
ou seja a cada nu´mero racional, r, corresponde a classe de equivaleˆncia constitu´ıda dos
pares de naturais (x1, x2) tais que r = x1/x2.
7. a) Fecho reflexivo: {(a, a), (c, c), (d, d), (e, e)} ∪R.
b) Fecho sime´trico: {(a, d), (b, a)} ∪R.
c) Fecho transitivo: {(c, a), (c, b), (c, c), (d, b), (d, d)} ∪R.
d) Fecho reflexivo e sime´trico: {(a, a), (c, c), (d, d), (e, e), (a, d), (b, a)} ∪R.
e) Fechoreflexivo e transitivo: {(a, a), (c, c), (d, d), (e, e), (c, a), (c, b), (d, b)} ∪R.
f) Fecho sime´trico e transitivo: {(a, d), (b, a), (c, a), (c, b), (c, c), (d, b), (d, d)} ∪R.
g) Fecho reflexivo, sime´trico e transitivo:
{(a, a), (c, c), (d, d), (e, e), (a, d), (b, a), (c, a), (c, b), (d, b)} ∪R.
1.5 Func¸o˜es
1. O nu´mero ma´ximo para R ⊆ A × B ser uma func¸a˜o e´ |R| = |A|, ja´ que na˜o se pode ter
(x, y) ∈ f e (x, z) ∈ f se y 6= z.
2. Sejam f : A→ B, g : C → D e h = f ∪ g. Enta˜o:
h : A ∪C → B ∪D se, e somente se, ∀x ∈ A ∩ Cf(x) = g(x).
Prova:
(→) Suponha que h : A ∪ C → B ∪D. Seja um elemento arbitra´rio x de A ∩ C. Como
h = f ∪ g e h : A ∪ C → B ∪D, segue-se que h(x) = f(x) = g(x).
(←) Suponha que ∀x ∈ A∩Cf(x) = g(x). Seja y um elemento arbitra´rio de A∪C. Para
mostrar existe um u´nico z ∈ B ∪D tal que (y, z) ∈ h, sera˜o considerados 3 casos:
Caso 1 : y ∈ A − C. Como f : A → B, h = f ∪ g e y ∈ A, um z tal que (y, z) ∈ h e´
z = f(y). E como g : C → D, h = f ∪ g e y 6∈ C, tal z e´ u´nico.
Caso 2 : y ∈ C − A. Como g : C → D, h = f ∪ g e y ∈ C, um z tal que (y, z) ∈ h e´
z = g(y). E como f : A→ B, h = f ∪ g e y 6∈ A, tal z e´ u´nico.
Caso 3 : y ∈ A ∩ C. Como f : A→ B, g : C → D, h = f ∪ g e ∀x ∈ A ∩ Cf(x) = g(x), o
u´nico z tal que (y, z) ∈ h e´ z = f(y) = g(y).
3. a) f na˜o e´ injetora, pois f(0) = f(1) = 0. E´ sobrejetora, pois f(2n) = n para todo
n ∈ N.
b) g e´ injetora, pois se g(n) = g(k), enta˜o k = n. Ela na˜o e´ sobrejetora, pois na˜o existe
n ∈ N tal que g(n) = 2: g(1) = 1 e g(2) = 3 e g e´ crescente.
c) h e´ injetora: Suponha que h(n) = h(k). Se n e k forem ambos pares ou ambos
ı´mpares, para que n− 1 = k − 1 ou n+ 1 = k + 1, deve-se ter que n = k. Por outro
lado se um e´ par e o outro e´ ı´mpar, para que n+1 = k−1, deve-se ter que n+2 = k;
mas, para que isto seja verdade, n e k na˜o podem ser um par e o outro ı´mpar!
h e´ sobrejetora, pois h(n+1) = n para todo nu´mero n par a partir de 0, e h(n−1) = n
para todo nu´mero n ı´mpar a partir de 1.
Portanto, h e´ bijetora. Da u´ltima sentenc¸a acima, veˆ-se que a h−1 = h.
4. Sejam |A| = n e |B| = k.
9
a) Para cada a ∈ A, f(a) pode ser qualquer elemento de B. Assim, existem kn func¸o˜es
totais poss´ıveis.
b) Para cada a ∈ A, f(a) pode ser indefinido ou qualquer elemento de B. Assim,
existem (k + 1)n func¸o˜es parciais poss´ıveis.
c) Se n > k, na˜o ha´ func¸a˜o injetora. Suponha que n ≤ k. Escolhido um elemento de
B para ser f(a), ele na˜o pode mais ser f(b) para b 6= a. Assim, existem P (k, n) =
k.(k − 1) . . . (k − n+ 1) = k!/(k − n)! func¸o˜es injetoras poss´ıveis, se n ≤ k.
d) Se n < k, na˜o ha´ func¸a˜o sobretora. Suponha que n ≥ k. Deve ser escolhido um
elemento de eA tal que f(a) seja um elemento de B, para cada elemento de B. Para
isto existem P (n, k) = n.(n−1) . . . (n−k+1) = n!/(n−k)! possibilidades. Para cada
uma delas, os n − k elementos restantes de A podem, cada um deles, ser mapeado
para qualquer um dos elementos de B: sa˜o kn−k possibilidades. Assim, existem
(n!.kn−k)/(n − k)! func¸o˜es sobrejetoras poss´ıveis, se n ≥ k.
e) Quando n = k, existe uma u´nica func¸a˜o bijetora. Se n 6= k, na˜o existe func¸a˜o
bijetora.
5. a) Sejam x e y elementos arbitra´rios de A tais que x 6= y. Como f e´ injetora, f(x) 6=
f(y). E como g e´ injetora, g(f(x)) 6= g(f(y)). Portanto, se x 6= y, enta˜o g(f(x)) 6=
g(f(y)). Conclui-se que g ◦ f e´ injetora.
b) Seja y ∈ C arbitra´rio. Como g e´ sobrejetora, existe z ∈ B tal que g(z) = y. E como
f e´ sobrejetora, existe x ∈ A tal que f(x) = z, ou ainda, g(f(x)) = y. Logo, para
todo y ∈ C existe x ∈ A tal que g(f(x)) = y. Portanto, g ◦ f e´ sobrejetora.
c) Dos dois resultados acima segue-se que g ◦ f e´ bijetora.
6. Seja f : A→ B. Seja C = {b ∈ B | f(a) = b para algum a ∈ A}. Seja a func¸a˜o sobrejetora
g : A→ C tal que g(a) = f(a) para todo a ∈ A. Seja a func¸a˜o injetora h : C → B tal que
h(c) = c para todo c ∈ C. Enta˜o f = h ◦ g.
7. Como g◦f = f ◦g, g(f(n)) = f(g(n)) para todo n ∈ R. Logo, c(an+b)+d = a(cn+d)+b,
ou seja, acn + bc + d = acn + ad + b, ou ainda, bc + d = ad + b. Tem-se, enta˜o, que
b(c− 1) = d(a− 1).
1.6 Conjuntos Enumera´veis
1. a) O conjunto X = {n ∈ N |nmod 10 = 0} e´ enumera´vel, pois e´ um subconjunto de N.
Uma func¸a˜o bijetora seria g : N→ X, tal que g(n) = 10n.
b) O conjunto N3 = {(n1, n2, n3) |n1, n2, n3 ∈ N} e´ enumera´vel. Uma func¸a˜o bijetora
seria h : N3 → N, tal que h(n1, n2, n3) = f(f(n1, n2), n3), onde f : N2 → N e´ tal
que f(i, j) = (i+ j)(i + j + 1)/2 + i.
c) O conjunto W = {n ∈ R | 0 < n < 1} na˜o e´ enumera´vel, como sera´ mostrado
por contradic¸a˜o. Suponha que W e´ enumera´vel. Seja, enta˜o, r0, r1, r2, . . . uma
enumerac¸a˜o dos elementos de W . Sera´ denotado por di(r) o i-e´simo d´ıgito apo´s
a v´ırgula da expansa˜o decimal do nu´mero r de W . Por exemplo, d1(0, 53) = 5,
d7(0, 53) = 0. Seja o nu´mero k entre 0 e 1 tal que di(k) = di(ri) + 5mod 10 para
i ∈ N. Tal nu´mero difere de qualquer ri no i-e´simo d´ıgito apo´s a v´ırgula. Logo k 6= ri
para i ∈ N. Contradic¸a˜o; W na˜o e´ enumera´vel.
10
2. Suponha que tal conjunto seja enumera´vel. Enta˜o existe uma enumerac¸a˜o f0, f1, f2, . . . de
todas as func¸o˜es de N para {0, 1}. Seja a func¸a˜o g : N→ {0, 1} tal que g(n) = 1− fn(n).
Ora, g(n) 6= fn(n) para todo n ∈ N, e, portanto, g 6= fn para todo n ∈ N. Logo, a
suposic¸a˜o da enumerabilidade das func¸o˜es na˜o se sustenta.
3. Suponha que tal conjunto seja enumera´vel. Enta˜o existe uma enumerac¸a˜o f0, f1, f2, . . . de
todas as func¸o˜es de N para N monotoˆnicas crescentes. Seja a func¸a˜o h : N → N tal que
h(n) = 1 +
∑n
k=0 fk(k). Veja que, como as func¸o˜es fk sa˜o monotoˆnicas crescentes, enta˜o
fk(k) > 0 para k > 0. Assim, h, ale´m de diferente de fn para todo n ∈ N. e´ monotoˆnica
crescente. Logo, a suposic¸a˜o da enumerabilidade das func¸o˜es monotoˆnicas crescentes e´
incorreta.
4. Seja um conjunto enumera´vel arbitra´rio A e suponha que B ⊆ A. Se B e´ finito, e´ conta´vel,
por definic¸a˜o. Suponha que B e´ infinito. Sera´ mostrado que B e´ enumera´vel construindo-
se uma func¸a˜o bijetora g : N → B. Como A e´ enumera´vel, existe uma func¸a˜o bijetora
f : N → A; assim sendo, pode-se dizer que A = {f(k) | k ∈ N}. A func¸a˜o g pode ser
constru´ıda da seguinte forma:
• g(0) = f(m), onde m e´ o menor nu´mero natural tal que f(k) ∈ B;
• para i > 0, g(i) = f(k), onde k e´ o menor nu´mero natural tal que f(k) ∈ B e k > j,
sendo j tal que g(i− 1) = f(j).
5. Como todo subconjunto de conjunto enumera´vel e´ conta´vel (questa˜o 4), sabe-se que A−B
e´ conta´vel. Como (A−B)∪B = A∪B, basta mostrar que (A−B)∪B e´ conta´vel, sendo
que (A − B) ∩ B = ∅. No caso em ambos A − B e B sa˜o finitos, (A − B) ∪ B e´ finito e,
portanto, conta´vel. No caso em que um deles e´ finito e o outro na˜o, seja {a0, a1, . . . , am} o
conjunto finito e suponha que existe uma func¸a˜o bijetora f de N para o conjunto infinito.
Enta˜o, pode-se construir uma func¸a˜o bijetora h : N → A ∪ B, onde h(k) = ak para
0 ≤ k ≤ m e h(k) = f(k − m − 1) para k ≥ m + 1. Agora, se ambos A − B e B sa˜o
infinitos, sejam f : N → A − B e g : N → B bijetoras. Enta˜o pode-se construir uma
func¸a˜o bijetora h : N→ A ∪B, onde h(2k) = f(k) e h(2k − 1) = g(k) para k ∈ N.
A intersec¸a˜o e´ subconjunto dos dois conjuntos. Logo e´ conta´vel (questa˜o 4).
O produto de conjuntos finitos e´ finito. Se um dos conjuntos e´ finito e o outro na˜o, seja
{a0, a1, . . . , am} o conjunto finito e suponha que existe uma func¸a˜o bijetora f de N para
o conjunto infinito. Sem perda de generalidade, seja A o conjunto finito. Enta˜o, pode-se
construir uma func¸a˜o bijetora h : A×B → N, onde h(i, j) = j(m+1)+ i para 0 ≤ i ≤ m
e j ∈ N. Se os dois conjuntos forem infinitos, sejam f : A → N e g : B → N bijetoras.
A func¸a˜o h : A ×B → N, onde h(f(a), g(b)) = (f(a) + g(b))(f(a) + g(b) + 1)/2 + f(a) e´
bijetora.
6. Seja |F | = n. A cardinalidade do conjunto das func¸o˜es totais f : F → E e´ igual a`
do conjunto En: existe uma func¸a˜o bijetora que, a cada func¸a˜o f faz corresponder a n-
upla (f(a1),f(a2), . . . , f(an)), onde a1, a2, . . . , an sa˜o os elementos de F . Como E
n e´
enumera´vel, segue-se que o conjunto em questa˜o e´ enumera´vel.
1.7 Definic¸o˜es Recursivas
1. Definic¸a˜o recursiva de f : N→ N, tal que f(n) =∑nk=1 k:
a) f(1) = 1;
11
b) f(n) = f(n− 1) + n para n > 1.
2. Seja um universo U . O nu´mero de elementos do conjunto poteˆncia de um conjunto finito
de elementos de U , pode ser definido recursivamente assim:
a) |P(∅)| = 1;
b) |P(X ∪ {a})| = 2|P(X)| para todo a ∈ U .
3. Definic¸a˜o recursiva da representac¸a˜o de nu´meros bina´rios sem zeros a` esquerda, r : N→ B,
onde B e´ o conjunto das sequ¨eˆncias de d´ıgitos bina´rios:
a) r(0) = 0, r(1) = 1;
b) r(n) = r(bn/2c)(n mod 2) para n > 1.
Assim, por exemplo, r(5) = r(2)1 = r(1)01 = 101.
4. Definic¸a˜o recursiva da sequ¨eˆncia de Fibonacci:
a) a0 = 0 e a1 = 1;
b) an = an−2 + an−1 para n ≥ 2.
5. Definic¸a˜o recursiva de multiplicac¸a˜o sobre N:
a) m× 0 = 0 para todo m ∈N;
b) m× s(n) = m+ (m× n) para m,n ∈ N.
6. Definic¸a˜o recursiva de LP′, semelhante a LP, pore´m com omissa˜o e/ou excesso de pareˆnteses:
a) cada varia´vel proposicional pertence a LP′;
b) se α, β ∈ LP′, enta˜o pertencem a LP′: ¬α, α ∧ β, α ∨ β, α→ β, α↔ β e (α).
1.8 Induc¸a˜o Matema´tica
1. So´ existe um conjunto de 0 elementos: ∅; e 20 = 1 = |{∅}| = |P(∅)|. Seja n ≥ 0.
Suponha, como hipo´tese de induc¸a˜o, que |P(A)| = 2n para conjuntos A de n elementos.
Seja um conjunto B de n + 1 elementos e a um de seus elementos. Tem-se: P(B) =
P(B − {a}) ∪ {X ∪ {a} |X ∈ P(B − {a})}. Pela hipo´tese de induc¸a˜o, |P(B − {a})| = 2n,
e como P(B − {a}) e {X ∪ {a} |X ∈ P(B − {a})} teˆm o mesmo nu´mero de elementos,
|P(B)| = 2n + 2n = 2n+1.
2. a)
∑0
k=0 k
2 = 02 = 0 = 0(0 + 1)(2 × 0 + 1)/6. Seja n um nu´mero natural arbitra´rio.
Suponha, como hipo´tese de induc¸a˜o, que
∑n
k=0 k
2 = n(n+1)(2n+1)/6. Basta provar,
enta˜o, que
∑n+1
k=0 k
2 = (n + 1)(n + 2)(2n + 3)/6. De fato:∑n+1
k=0 k
2= [
∑n
k=0 k
2] + (n+ 1)2
= [n(n+ 1)(2n + 1)/6] + (n+ 1)2 pela hipo´tese de induc¸a˜o
= [n(n+ 1)(2n + 1) + 6(n+ 1)2]/6
= (n+ 1)[n(2n + 1) + 6(n+ 1)]/6
= (n+ 1)(2n2 + 7n+ 6)/6
= (n+ 1)(n + 2)(2n + 3)/6.
b)
∑0
k=0 k
3 = 03 = 0 = 02 = [0(0 + 1)/2]2. Seja n ≥ 0 arbitra´rio. Suponha,
como hipo´tese de induc¸a˜o, que
∑n
k=0 k
3 = [n(n + 1)/2]2. Basta provar, enta˜o, que∑n+1
k=0 k
3 = [(n+ 1)(n + 2)/2]2. De fato:
12
∑n+1
k=0 k
3= [
∑n
k=0 k
3] + (n+ 1)3
= [n(n+ 1)/2]2 + (n+ 1)3 pela hipo´tese de induc¸a˜o
= [n2(n+ 1)2 + 4(n + 1)3]/4
= [(n+ 1)2(n2 + 4n+ 4)]/4
= [(n+ 1)2(n+ 2)2]/4
= [(n+ 1)(n + 2)/2]2.
c) Inicialmente, obsereve que: 22×0− 1 = 20− 1 = 1− 1 = 0, que e´ divis´ıvel por 3. Seja
n ≥ 0. Suponha, como hipo´tese de induc¸a˜o, que 22n − 1 e´ divis´ıvel por 3. Enta˜o:
22(n+1) − 1 = 22n+2 − 1 = 22n × 22 − 1 = 4 × 22n − 1 = 3 × 22n + 22n − 1. Como
3× 22n e´ divis´ıvel por 3 e, pela hipo´tese de induc¸a˜o, 22n − 1 tambe´m e´ divis´ıvel por
3, segue-se que 22(n+1) − 1 e´ divis´ıvel por 3.
d) 03 − 0 = 0, que e´ divis´ıvel por 6. Seja n ≥ 0. Hipo´tese de induc¸a˜o: n3 − n e´
divis´ıvel por 6. Deve-se provar que (n + 1)3 − (n + 1) e´ divis´ıvel por 6. Tem-se:
(n+1)3−(n+1) = n3+3n2+3n+1−n−1 = (n3−n)+(3n2+3n) = (n3−n)+3n(n+1).
Como n(n + 1) e´ sempre um nu´mero par, 3n(n + 1) e´ divis´ıvel por 6. E como, pela
hipo´tese de induc¸a˜o, n3−n tambe´m e´ divis´ıvel por 6, segue-se que (n+1)3− (n+1)
e´ divis´ıvel por 6.
e) 70 − 1 = 1 − 1 = 0, que e´ divis´ıvel por 6. Seja n ≥ 0. Suponha, como hipo´tese de
induc¸a˜o, que 7n − 1 e´ divis´ıvel por 6. Tem-se: 7n+1 − 1 = 7n − 1 + 6 × 7n. Como
6×7n e´ divis´ıvel por 6 e, pela hipo´tese de induc¸a˜o, 7n−1 e´ divis´ıvel por 6, conclui-se
que 7n+1 − 1 e´ divis´ıvel por 6.
3. a) Tem-se:
∑1
k=1[k(k + 1)] = 1(1 + 1) = 2 = 1(2)(3)/3 = 1(1 + 1)(1 + 2)/3. Seja n ≥ 1.
Suponha, como hipo´tese de induc¸a˜o, que
∑n
k=1[k(k+1)] = n(n+1)(n+2)/3. Basta,
enta˜o, provar que
∑n+1
k=1 [k(k + 1)] = (n+ 1)(n + 2)(n + 3)/3. De fato:∑n+1
k=1 [k(k + 1)]= [
∑n
k=1 k(k + 1)] + (n+ 1)(n + 2)
= [n(n+ 1)(n + 2)/3] + (n+ 1)(n + 2) pela hipo´tese de induc¸a˜o
= [n(n+ 1)(n + 2) + 3(n+ 1)(n + 2)]/3
= (n+ 1)(n + 2)(n + 3)/3.
b)
∑1
k=1 2
k = 21 = 2 = 2×1 = 2(2−1) = 2(21−1). Seja n ≥ 1. Suponha, como hipo´tese
de induc¸a˜o, que
∑n
k=1 2
k = 2(2n− 1). Tem-se: ∑n+1k=1 2k = [∑nk=1 2k]+ 2n+1 = 2(2n−
1)+2n+1, pela hipo´tese de induc¸a˜o. Logo,
∑n+1
k=1 2
k = 2n+1−2+2n+1 = 2(2n+1−1),
como requerido.
c) Inicialmente, veja que
∑1
k=1[1/k(k+1)] = 1/(1+1). Seja n ≥ 1 arbitra´rio, e suponha,
como hipo´tese de induc¸a˜o, que
∑n
k=1[1/k(k + 1)] = n/(n + 1). Enta˜o:∑n+1
k=1 [1/k(k + 1)]= [
∑n
k=1[1/k(k + 1)]] + 1/(n + 1)(n + 2)
= [n/(n+ 1)] + 1/(n + 1)(n + 2) pela hipo´tese de induc¸a˜o
= [n(n+ 2) + 1]/[(n + 1)(n + 2)]
= [n2 + 2n + 1]/[(n + 1)(n + 2)]
= (n+ 1)2/[(n + 1)(n + 2)]
= (n+ 1)/(n + 2).
Logo, pelo princ´ıpio de induc¸a˜o,
∑n
k=1[1/k(k + 1)] = n/(n+ 1) para todo n ≥ 1.
d) 13+(1+1)3+(1+2)3 = 1+8+27 = 36, que e´ divis´ıvel por 9. Seja um nu´mero natural n
arbitra´rio maior ou igual a 1. Suponha, como hipo´tese de induc¸a˜o, que n3+(n+1)3+
(n+2)3 e´ divis´ıvel por 9. Deve-se mostrar que (n+1)3+(n+2)3+(n+3)3 e´ divis´ıvel
por 9. Tem-se que (n+1)3+(n+2)3+(n+3)3 = (n+1)3+(n+2)3+n3+9n2+27n+27,
13
ou seja, (n + 1)3 + (n + 2)3 + (n + 3)3 = n3 + (n+ 1)3 + (n + 2)3 + 9(n2 + 3n + 3).
Deduz-se, enta˜o, aplicando-se a hipo´tese de induc¸a˜o, que (n+1)3+(n+2)3+(n+3)3
e´ divis´ıvel por 9.
4. Seja n um nu´mero natural arbitra´rio. Suponha, como hipo´tese, que
F (k) =
1√
5

(1 +√5
2
)k
−
(
1−√5
2
)k
para k < n. Sera˜o considerados 3 casos:
Caso 1: n = 0. Neste caso, F (0) = 0 por definic¸a˜o, e (1/
√
5)[((1 +
√
5)/2)0 − ((1 −√
5)/2)0] = 1− 1 = 0.
Caso 2: n = 1. Neste caso, F (1) = 1 por definic¸a˜o, e (1/
√
5)[((1 +
√
5)/2)1 − ((1 −√
5)/2)1] = (1 +
√
5− 1 +√5)/(2√5) = 1.
Caso 3: n ≥ 2. Neste caso, F (n) = F (n − 1) + F (n − 2) por definic¸a˜o. Aplicando-se a
hipo´tese de induc¸a˜o, obte´m-se:
F (n) =
1√
5


(
1 +
√
5
2
)n−1
−
(
1−√5
2
)n−1+ 1√
5


(
1 +
√
5
2
)n−2
−
(
1−√5
2
)n−2 .
Assim,
F (n) =
1√
5


(
1 +
√
5
2
)n−2(
1 +
√
5
2
+ 1
)
−
(
1−√5
2
)n−2 (
1−√5
2
+ 1
)
 .
Verifica-se facilmente que:
1 +
√
5
2
+ 1 =
(
1 +
√
5
2
)2
e
1−√5
2
+ 1 =
(
1−√5
2
)2
.
Portanto,
F (n) =
1√
5
[(
1 +
√
5
2
)n
−
(
1−√5
2
)n]
.
5. Sera´ usada induc¸a˜o forte sobre o nu´mero de conectivos. Assim, seja n ≥ 0, e suponha que
o resultado valha para sentenc¸as com menos de n conectivos. Deve-se provar, enta˜o, que
o resultado vale para sentenc¸as com n conectivos. Considera-se dois casos:
(a) n = 0. Uma sentenc¸a sem conectivos e´ uma varia´vel proposicional, e esta tem apenas
dois prefixos: λ e ela mesma. Em ambos o nu´mero de abre e fecha pareˆnteses e´ zero.
(b) n > 0. Uma sentenc¸a com conectivos e´ da forma ¬α ou (α⊕ β), onde ⊕ ∈ {∧,∨,→
,↔}:
i) ¬α. Como α tem n − 1 conectivos, o resultado vale para α, pela hipo´tese de
induc¸a˜o. Segue-se que vale tambe´m para ¬α, que na˜o tem outros pareˆnteses que os
de α.
ii) (α ⊕ β). Como α e β teˆm menos de n conectivos, o resultado vale para ambos,
pela hipo´tese de induc¸a˜o. Segue-se que o resultado vale tambe´m para α ⊕ β. E o
resultado continua valendo ao se colocar os pareˆnteses externos.
14
1.9 Grafos
1. Isto segue do fato de que a soma dos graus dos ve´rtices e´ par: em um grafo sem arestas
tal soma e´ zero, e cada aresta acrescenta 2 unidades a` soma.
2. Sera´ feita uma prova por induc¸a˜o sobre o nu´mero de ve´rtices. A menor a´rvore, que e´ da
forma ({v}, ∅, v), tem um ve´rtice e nenhuma aresta. Seja um nu´mero n ≥ 1 e suponha,
como hipo´tese de induc¸a˜o, que a proposic¸a˜o e´ verdadeira para a´rvores com n ve´rtices.
Uma a´rvore com n+ 1 ve´rtices e´ da forma (V ∪ {v}, A ∪ {{v, v′}}, r), onde v ∈ V , v′ 6∈ V
e (V,A, r) e´ uma a´rvore de n ve´rtices. Pela hipo´tese de induc¸a˜o, |A| = n − 1, ou ainda,
|A|+ 1 = (n+ 1)− 1, o que mostra que a proposic¸a˜o vale para a´rvores de n+ 1 ve´rtices,
ja´ que estas teˆm |A|+ 1 arestas.
3. Isto segue dofato de que a cada aresta introduzida no grafo, a soma dos graus dos ve´rtices
aumenta de 2 unidades.
4. O nu´mero de arestas de Kn e´ C(n, 2) = n(n+ 1)/2.
5. a) Uma a´rvore bina´ria de altura 0 tem apenas 1 ve´rtice e ele e´ folha; e 20 = 1. Seja
n ≥ 0. Suponha, como hipo´tese de induc¸a˜o, que a´rvores bina´rias de altura n possuem,
no ma´ximo, 2n folhas. Uma a´rvore bina´ria B de altura n + 1 possue um ma´ximo
de folhas quando as duas suba´rvores da raiz possuem um ma´ximo de folhas. Isto
acontece quando ambas teˆm altura n. Assim, pela hipo´tese de induc¸a˜o, elas possuem
2n folhas. Logo a a´rvore B tem 2n + 2n = 2n+1 folhas.
b) Uma a´rvore bina´ria de altura 0 tem apenas 1 ve´rtice; e 20+1 − 1 = 1. Seja n ≥ 0.
Suponha, como hipo´tese de induc¸a˜o, que a´rvores bina´rias de altura n possuem, no
ma´ximo, 2n+1−1 ve´rtices. Uma a´rvore bina´ria B de altura n+1 possue um ma´ximo
de ve´rtices quando as duas suba´rvores da raiz possuem um ma´ximo de ve´rtices. Isto
acontece quando ambas teˆm altura n. Assim, pela hipo´tese de induc¸a˜o, elas possuem
2n+1− 1 ve´rtices. Logo a a´rvore B tem os 2n+1− 1 ve´rtices de cada uma mais a raiz:
2n+1 − 1 + 2n+1 − 1 + 1 = 2× 2n+1 + 1 = 2n+2 + 1.
6. Sera´ usada a definic¸a˜o de a´rvore do livro.
(a)→(b) Por induc¸a˜o sobre o nu´mero de ve´rtices. Se a a´rvore tem 1 ve´rtice na˜o tem
arestas. Logo, satisfaz (b). Seja n ≥ 1, e suponha que (b) vale para a´rvores de n ve´rtices.
Seja uma a´rvore A de n+ 1 ve´rtices. Pela definic¸a˜o, tal a´rvore e´ formada de uma a´rvore
de n ve´rtices pela inclusa˜o de um ve´rtice novo e uma nova aresta. Como, pela hipo´tese
de induc¸a˜o, (b) vale para a´rvore de n ve´rtices, enta˜o continua valendo para A.
(b)→(c) Sendo o grafo ac´ıclico, se existir um caminho simples de um ve´rtice a outro,
ele e´ u´nico. Assim, basta mostrar a existeˆncia de caminho simples. Isto sera´ feito por
induc¸a˜o sobre o nu´mero de ve´rtices. Se o grafo tem 1 ve´rtice, existe caminho simples dele
ate´ ele mesmo. Seja n ≥ 1, e suponha que (c) vale para grafos (que satisfazem (b)) de
n ve´rtices ou menos. Seja Seja um grafo G de n + 1 ve´rtices que satisfac¸a (b). Seja v
um ve´rtice arbitra´rio de G. Suponha que existam k ve´rtices adjacentes a v, v1, v2,. . . ,vk.
Retirando-se as arestas {v, v1}, . . . , {v, vk}, como o grafo e´ ac´ıclico, obte´m-se k+1 grafos
(componentes) sem ve´rtices em comum, k grafos em que esta˜o os ve´rtices v1, v2,. . . ,vk,
e um contendo apenas v. Pela hipo´tese de induc¸a˜o, (c) vale para cada um deles. Com a
reinclusa˜o de v e arestas incidentes, havera´ tambe´m um caminho simples de cada ve´rtice
de cada um dos k + 1 componentes a qualquer outro de outro componente, passando por
v.
15
(c)→(a) A prova sera´ feita por induc¸a˜o sobre o nu´mero de ve´rtices. Se o grafo tem 1
ve´rtice, ele na˜o tem aresta, pois existe um u´nico caminho simples do ve´rtice a ele mesmo.
Seja n ≥ 1, e suponha que (a) vale para grafos (que satisfazem (c)) de n ve´rtices ou
menos. Seja Seja um grafo G de n + 1 ve´rtices que satisfac¸a (c). Seja v um ve´rtice
arbitra´rio de G de grau 1; v existe, pois o conjunto de ve´rtices e´ finito e , assim, partindo-
se de qualquer ve´rtice, um caminhamento qualquer deve terminar antes repetir um ve´rtice;
caso contra´rio, existiria mais de um caminho simples, contrariando (c). Removendo-se v
e a aresta incidente, obte´m-se um grafo que, pela hipo´tese de induc¸a˜o, e´ uma a´rvore.
Adicionando-se v e a aresta incidente, obte´m-se enta˜o uma a´rvore.
1.10 Linguagens Formais
1. O nu´mero de prefixos e o de sufixos e´ n + 1. O nu´mero ma´ximo de subpalavras e´ 1 +
C(n − 1 + 2, 2) = 1 + C(n + 1, 2) = 1 + (n + 1)n/2; assim, o nu´mero de subpalavras vai
de n+ 1 a 1 + (n+ 1)n/2.
2. a) {1}∗{0}{0, 1}∗.
b) {0, 1}({0, 1}2)∗.
c) {0}∗{0}{1}∗.
d) {λ} ∪ {0}{10}∗ ∪ {1}{01}∗.
e) {xx |x ∈ {0, 1}∗}.
3. a) {0, 1}10.
b) {0, 1}{λ, 0, 1}199.
c) {01, 1}{0, 1}∗{00}.
d) {1, 011}∗.
e) {1}∗({0}{1}∗{0}{1}∗)∗ ∪ {0}∗{1}{0}∗({1}{0}∗{1}{0}∗)∗.
f) {0}∗{1}{0}∗{λ, 1}{0}∗ ∩ ({0, 1}3)∗
4. a) A(B ∪C) ⊆ (AB) ∪ (AC)
Seja w ∈ Σ∗ tal que w ∈ A(B ∪ C). Enta˜o existem x e y tais que w = xy, x ∈ A e
y ∈ B ∪ C. No caso em que y ∈ B, segue-se que xy ∈ AB e no caso em que y ∈ C,
segue-se que xy ∈ AC. Logo, xy = w ∈ (AB) ∪ (AC).
(AB) ∪ (AC) ⊆ A(B ∪C)
Seja w ∈ Σ∗ tal que w ∈ (AB) ∪ (AC). Enta˜o w ∈ AB ou w ∈ AC. No primeiro
caso, existem x e y tais que w = xy, x ∈ A e y ∈ B. Como y ∈ B ∪D para qualquer
linguagem D, segue-se que xy = w ∈ A(B ∪C). No caso em que w ∈ AC, existem x
e y tais que w = xy, x ∈ A e y ∈ C. Como y ∈ D ∪ C para qualquer linguagem D,
segue-se que xy = w ∈ A(B ∪ C). Conclui-se, portanto, que w ∈ A(B ∪C).
b) Contra-exemplo: A = {λ, a}, B = {b}, C = {ab}.
5. Suponha que λ ∈ L. Neste caso, λ ∈ L+ e, portanto, L+∪{λ} = L+. Como L∗ = L+∪{λ},
segue-se que L∗ = L+. Agora suponha que λ 6∈ L. Enta˜o λ 6∈ L+. Como L∗ = L+ ∪ {λ},
segue-se que L+ = L∗ − {λ}.
6. L∗ e´ finita se, e somente se, L = ∅ ou L = {λ}.
16
7. Uma condic¸a˜o necessa´ria e suficiente para L = LR e´: w ∈ L se, e somente se, wR ∈ L,
para toda palavra w.
Prova:
(→) Suponha que L = LR. Seja w uma palavra arbitra´ria. Se w ∈ L, enta˜o, pela definic¸a˜o
de reverso, wR ∈ LR; e como LR = L, wR ∈ L. Por outro lado, se wR ∈ L, enta˜o, pela
definic¸a˜o de reverso, (wR)R = w ∈ LR; e como LR = L, w ∈ L. Assim, para toda palavra
w, w ∈ L se, e somente se, wR ∈ L.
(←) Suponha que w ∈ L se, e somente se, wR ∈ L, para toda palavra w. L ⊆ LR, pois: se
x ∈ L, enta˜o, pela suposic¸a˜o acima, xR ∈ L; e pela definic¸a˜o de reverso, (xR)R = x ∈ LR.
Por outro lado, LR ⊆ L, pois: se x ∈ LR, da definic¸a˜o de reverso, tem-se que xR ∈ L (pois
x = (xR)R); e pela suposic¸a˜o acima, x ∈ L. Conclui-se enta˜o que L = LR.
8. A prova sera´ por induc¸a˜o sobre n. Para n = 0, tem-se: (wR)0 = λ = λR = (w0)R.
Seja n ≥ 0 e suponha que (wR)n = (wn)R. Segue-se que: (wR)n+1 = (wR)nwR =
(wn)RwR, pela hipo´tese de induc¸a˜o. E como (wn)RwR = (wwn)R = (wn+1)R, segue-se
que (wR)n+1 = (wn+1)R.
9. L∗ ⊆ ⋃
n∈N L
n.
Por induc¸a˜o forte sobre |w|. Suponha, como hipo´tese de induc¸a˜o, que se w ∈ L∗ enta˜o
w ∈ ⋃
n∈N L
n para palavras de tamanho menor que um certo k arbitra´rio. Para mostrar
que isto vale tambe´m para palavras de tamanho k, considera-se dois casos:
k = 0. A u´nica palavra de tamanho 0 e´ λ, e λ ∈ ⋃
n∈N L
n, pois L0 = {λ}.
k > 0. Seja w de tamanho k tal que w ∈ L∗. Pela definic¸a˜o de fecho de Kleene, pode-se
dizer que w = xy, onde x ∈ L∗, y ∈ L e y 6= λ. Pela hipo´tese de induc¸a˜o, x ∈ ⋃
n∈N L
n.
Segue-se que x ∈ Li para algum i ∈ N. Como y ∈ L, tem-se que xy ∈ Li+1. Portanto,
w ∈ ⋃
n∈N L
n.⋃
n∈N L
n ⊆ L∗.
Este resultado segue do fato de que para todo n ≥ 0, Ln ⊆ L∗, fato este que sera´ provado
por induc¸a˜o sobre n. Inicialmente, note que L0 = {λ}, e λ ∈ L∗ por definic¸a˜o. Seja
n arbitra´rio e suponha que Ln ⊆ L∗. Como Ln+1 = LnL, e, pela hipo´tese de induc¸a˜o,
Ln ⊆ L∗, segue-se, pela definic¸a˜o de fecho de Kleene, que Ln+1 ⊆ L∗.
10. a) Seja w uma palavra arbitra´ria. Se w ∈ L∗, como λ ∈ L∗, segue-se que wλ =
w ∈ L∗L∗. Para completar, sera´ provado, por induc¸a˜o no tamanho de y que para
quaisquer palavras x, y ∈ L∗, se xy ∈ L∗L∗ enta˜o xy ∈ L∗. Inicialmente, veja que
se x ∈ L∗, xλ = x ∈ L∗. Seja n ≥ 0 e suponha, como hipo´tese de induc¸a˜o, que
se xy ∈ L∗L∗ enta˜o xy ∈ L∗ para palavras y de n ou menos s´ımbolos. Seja y uma
palavra arbitra´ria de L∗ de n+ 1 s´ımbolos e x ∈ L∗. Enta˜o, y = y1y2, onde y1 ∈ L∗
e y2 ∈ L, y2 6= λ. Assim, dado que xy1 ∈ L∗L∗ , pela hipo´tes de induc¸a˜o xy1 ∈ L∗.
Como y2 ∈ L, segue-se que (xy1)y2 = xy ∈ L∗.
b) Seja w uma palavra arbitra´ria. Se w ∈ L∗, como λ ∈ (L∗)∗, segue-se da definic¸a˜o de
fecho de Kleene que λw ∈ (L∗)∗L∗, ou seja, w ∈ (L∗)∗. Sera´ provado, por induc¸a˜o
no tamanho de w que para quaisquer palavras w ∈ (L∗)∗, w ∈ L∗. Inicialmente, veja
que λ ∈ L∗. Seja n ≥ 0 e suponha, como hipo´tese de induc¸a˜o, que se x ∈ (L∗)∗
enta˜o x ∈ L∗ para palavras x de n ou menos s´ımbolos. Seja w uma palavra de n+1
s´ımbolos. Suponha que w ∈ (L∗)∗.Enta˜o w = xy, onde x ∈ (L∗)∗ e y ∈ L∗, y 6= λ.
Como |x| ≤ n, segue-se pela hipo´tese de induc¸a˜o que x ∈ L∗. Assim, xy ∈ L∗L∗ e,
do resultado do item (a), segue-se que xy ∈ L∗.
17
c) Seja w uma palavra arbitra´ria. Se w ∈ (L1 ∪ L2)∗, como λ ∈ L∗1, segue-se que
wλ = w ∈ (L1 ∪ L2)∗L∗1. Sera´ mostrado por induc¸a˜o no tamanho de y que para
quaisquer palavras x ∈ (L1 ∪ L2)∗ e y ∈ L∗1, se xy ∈ (L1 ∪ L2)∗L∗1 enta˜o xy ∈
(L1 ∪ L2)∗. Inicialmente, observe que λ ∈ (L1 ∪ L2)∗. Seja n ≥ 0 e suponha, como
hipo´tese de induc¸a˜o, que se xy ∈ (L1 ∪ L2)∗L∗1 enta˜o xy ∈ (L1 ∪ L2)∗ para palavras
y ∈ L∗1 de n ou menos s´ımbolos. Seja y ∈ L∗1 uma palavra de n+ 1 s´ımbolos; assim,
y = y1y2, onde y1 ∈ L∗1 e y2 ∈ L1, y2 6= λ, e suponha que xy ∈ (L1 ∪ L2)∗L∗1.
Enta˜o xy1 ∈ (L1 ∪ L2)∗L∗1. Como |y1| ≤ n, segue-se pela hipo´tese de induc¸a˜o que
xy1 ∈ (L1 ∪ L2)∗. Como y2 ∈ L1, y2 ∈ L1 ∪ L2. Assim, (xy1)y2 = w ∈ (L1 ∪ L2)∗.
d) (L1 ∪ L2)∗ ⊆ (L∗1L∗2)∗.
Sera´ provado, por induc¸a˜o no tamanho de w que para quaisquer palavras w ∈ (L1 ∪
L2)
∗, w ∈ (L∗1L∗2)∗. Tem-se: λ ∈ (L∗1L∗2)∗. Seja n ≥ 0 e suponha, como hipo´tese
de induc¸a˜o, que z ∈ (L∗1L∗2)∗ para palavras z ∈ (L1 ∪ L2)∗ de n ou menos s´ımbolos.
Seja w ∈ (L1 ∪ L2)∗ de n + 1 s´ımbolos. Enta˜o, w = xy, y 6= λ, x ∈ (L1 ∪ L2)∗ e
y ∈ (L1 ∪ L2). Pela hipo´tese de induc¸a˜o, x ∈ (L∗1L∗2)∗. Se y ∈ L1, enta˜o y ∈ L∗1 e,
como λ ∈ L∗2, yλ = y ∈ L∗1L∗2; logo, xy = w ∈ (L∗1L∗2)∗. Por outro lado, se y ∈ L2,
racioc´ınio ana´logo mostra que xy = w ∈ (L∗1L∗2)∗.
(L∗1L
∗
2)
∗ ⊆ (L1 ∪ L2)∗.
Sera´ provado, por induc¸a˜o no tamanho de w que para quaisquer palavras w ∈
(L∗1L
∗
2)
∗, w ∈ (L1 ∪ L2)∗. Tem-se: λ ∈ (L1 ∪ L2)∗. Seja n ≥ 0 e suponha, como
hipo´tese de induc¸a˜o, que z ∈ (L1 ∪ L2)∗ para palavras z ∈ (L∗1L∗2)∗ de n ou menos
s´ımbolos. Seja w ∈ (L∗1L∗2)∗ de n + 1 s´ımbolos. Enta˜o, w = xy, y 6= λ, x ∈ (L∗1L∗2)∗
e y ∈ L∗1L∗2. Pela hipo´tese de induc¸a˜o, x ∈ (L1 ∪ L2)∗. Sejam y1 ∈ L∗1 e y2 ∈ L∗2 tais
que y = y1y2. Enta˜o w = xy1y2 ∈ (L1 ∪L2)∗L∗1L∗2. Aplicando-se o resultado do item
(c) duas vezes, conclui-se que w ∈ (L1 ∪ L2)∗.
11. L1 = {λ, a}, L2 = {a, aa}.
12. a) Definic¸a˜o recursiva de X = {0}∗{1}∗:
• λ ∈ X;
• se x ∈ X enta˜o 0x ∈ X e x1 ∈ X.
b) Definic¸a˜o recursiva de Y = {0n1n |n ∈ N}:
• λ ∈ Y ;
• se x ∈ Y enta˜o 0x1 ∈ Y .
c) Definic¸a˜o recursiva de Z = {w ∈ {0, 1}∗ |w conte´m 00}:
• 00 ∈ Z;
• se x ∈ Z enta˜o 0x, 1x, x0, x1 ∈ Z.
d) Definic¸a˜o recursiva de W = {001011021 . . . 0n1 |n ∈N}:
• 1, 101 ∈W ;
• se x10n1 ∈W enta˜o x10n10n+11 ∈W .
1.11 Grama´ticas
1. Nas derivac¸o˜es abaixo esta˜o grifadas as varia´veis expandidas.
a) A ⇒ BB ⇒ B ⇒ λ.
A ⇒ BB ⇒ B ⇒ λ.
18
b) A ⇒ BB ⇒ 0B1B ⇒ 01B ⇒ 01.
A ⇒ BB ⇒ 0B1B ⇒ 0B1 ⇒ 01.
A ⇒ BB ⇒ B0B1 ⇒ 0B1 ⇒ 01.
A ⇒ BB ⇒ B0B1 ⇒ B01 ⇒ 01.
c) A ⇒ BB ⇒ 0B1B ⇒ 01B ⇒ 010B1 ⇒ 0101.
A ⇒ BB ⇒ 0B1B ⇒ 0B10B1 ⇒ 010B1 ⇒ 0101.
A ⇒ BB ⇒ 0B1B ⇒ 0B10B1 ⇒ 0B101 ⇒ 0101.
A ⇒ BB ⇒ B0B1 ⇒ 0B10B1 ⇒ 010B1 ⇒ 0101.
A ⇒ BB ⇒ B0B1 ⇒ 0B10B1 ⇒ 0B101 ⇒ 0101.
A ⇒ BB ⇒ B0B1 ⇒ B01 ⇒ 0B101 ⇒ 0101.
d) A ⇒ BB ⇒ B ⇒ 0B1 ⇒ 00B11 ⇒ 0011.
A ⇒ BB ⇒ 0B1B ⇒ 00B11B ⇒ 0011B ⇒ 0011.
A ⇒ BB ⇒ 0B1B ⇒ 00B11B ⇒ 00B11 ⇒ 0011.
A ⇒ BB ⇒ 0B1B ⇒ 0B1 ⇒ 00B11 ⇒ 0011.
A ⇒ BB ⇒ B ⇒ 0B1 ⇒ 00B11 ⇒ 0011.
A ⇒ BB ⇒ B0B1 ⇒ 0B1 ⇒ 00B11 ⇒ 0011.
A ⇒ BB ⇒ B0B1 ⇒ B00B11 ⇒ 00B11 ⇒ 0011.
A ⇒ BB ⇒ B0B1 ⇒ B00B11 ⇒ B0011 ⇒ 0011.
A linguagem gerada e´ {0n1n |n ∈ N}2.
2. L(G′) = L(G). Cada palavra gerada por G, a grama´tica do Exemplo 49, pode ser gerada
por uma derivac¸a˜o da forma:
P⇒ aAbc (regra 1)
k⇒ aakA(bC)kbc (regra 2, k vezes; k ≥ 0)
⇒ aak(bC)kbc (regra 3)
⇒ ak+1(bC)k−1b2Cc (regra 4, 1 vez)
2⇒ ak+1(bC)k−2b3C2c (regra 4, 2 vezes)
...
k⇒ ak+1bk+1Ckc (regra 4, k vezes)
k⇒ ak+1bk+1ck+1 (regra 5, k vezes)
Cada uma destas palavras pode ser gerada, por meio de G′, como mostrado abaixo. O
que esta´ diferente esta´ grifado.
P⇒ aAbD (regra 1)
k⇒ aakA(bC)kbD (regra 2, k vezes; k ≥ 0)
⇒ aak(bC)kbD (regra 3)
⇒ ak+1(bC)k−1b2CD (regra 4, 1 vez)
2⇒ ak+1(bC)k−2b3C2D (regra 4, 2 vezes)
...
k⇒ ak+1bk+1CkD (regra 4, k vezes)
k⇒ ak+1bk+1Dck (regra 5, k vezes)
k⇒ ak+1bk+1ck+1 (regra 6, 1 vez)
19
Note-se que uma derivac¸a˜o de uma palavra da linguagem gasta um passo a mais na
grama´tica G′: o u´ltimo, que e´ usado para produzir o u´ltimo c. Uma derivac¸a˜o em G′ que,
usando a regra 6, substitua D por c antes da subsitituic¸a˜o de todos os Cs por cs, na˜o leva
a nenhuma palavra da linguagem.
3. a) P → aI | bP |λ
I → aP | bI
b) X → aXb |λ
c) X → aXa | bXb |λ | a | b
d) P → A |B |λ
A → aBa | a
B → bAb | b
e) P → aBPCd |λ
BC → bc
Ba → aB
Bb → bb
dC → Cd
cC → cc
4. Para a grama´tica do item (b), observando-se o esquema:
X
k⇒ akXbk ⇒ akbk.
veˆ-se que sa˜o gastos k + 1 = (n/2) + 1 passos.
Para a grama´tica do item (c), se n = 0, e´ gasto 1 passo:
X ⇒ λ
e se n > 0 sa˜o gastos k = dn/2e + 1 passos, pois
• Uma derivac¸a˜o comec¸a assim: X k⇒ xXxR (regras 1 e 2, k vezes, k ≥ 0, |x| = |xR| =
k).
• Em seguida, e´ aplicada uma das 3 u´ltimas regras. Se for a regra λ, o nu´mero de
passos e´ k = (n/2) + 1, onde n = 2k. Se for uma das outras duas regras, o nu´mero
de passos e´ k = [(n− 1)/2] + 1, onde n = 2k + 1.
5. L(G) = {a}∗{b}∗.
Prova:
{a}∗{b}∗ ⊆ L(G). O seguinte esquema de derivac¸a˜o mostra que toda palavra da forma
aibj, para i, j ≥ 0, e´ gerada por G:
A
i⇒ aiA (regra A→ aA, i vezes, i ≥ 0)
⇒ aiB (regra A→ B)
j⇒ aibjB (regra B → bB, j vezes, j ≥ 0)
⇒ aibj (regra B → λ)
Como qualquer palavra gerada por G segue necessariamente este mesmo esquema de
derivac¸a˜o, segue-se que L(G) ⊆ {a}∗{b}∗.
20
1.12 Problemas de Decisa˜o
1. a) Nada se pode dizer. X pode ser decid´ıvel ou na˜o.
b) X e´ decid´ıvel: para qualquer entrada x (para X), o algoritmo R produz uma sa´ıda
y, a partir da qual um algoritmo para D obte´m a resposta para x.
c) X e´ indecid´ıvel: pelo item anteriror, se X fosse decid´ıvel, I seria decid´ıvel.
d) Nada se pode dizer. X pode ser decid´ıvel ou na˜o.
1.13 Exerc´ıcios
1. Segue uma definic¸a˜o recursiva de vˆ : LP→ {V, F}:
a) vˆ(α) = v(α) para α ∈ VP;
b) vˆ(¬α) = V se, e somente se, vˆ(α) = F ;
vˆ((α ∧ β)) = V se, e somente se, vˆ(α) = V e vˆ(β) = V ;
vˆ((α ∨ β)) = F se, e somente se, vˆ(α) = F e vˆ(β) = F ;
vˆ((α→ β)) = F se, e somente se, vˆ(α) = V e vˆ(β) = F ;
vˆ((α↔ β)) = V se, e somente se, vˆ(α) = vˆ(β).
2. Basta substituir, indutivamente:
• α ∧ β por ¬(¬α ∨ ¬β);
• α→ β por ¬α ∨ β;
• α↔ β por (¬α ∨ β) ∧ (α ∨ ¬β);
• ∃xα por ¬∀x¬α.
3. Por induc¸a˜o sobre n. Inicialmente, veja que (0 + 1)2 − 02 = 1 > 0. Seja n um nu´mero
natural arbitra´rio. Suponha, como hipo´tese de induc¸a˜o, que existe k ∈ N tal que (k+1)2−
k2 > n. Seja k0 tal nu´mero. Como (k0+1)
2−k20 = k20+2k0+1−k20 = 2k0+1, pela hipo´tese
de induc¸a˜o, tem-se que 2k0+1 > n. Logo, 2k0+2 > n+1. E como (k0+2)
2− (k0+1)2 =
k20 +4k0+4− k20 − 2k0− 1 = 3k0+3, segue-se que (k0+2)2− (k0+1)2 > n+1. Portanto,
existe um nu´mero natural k tal que (k + 1)2 − k2 > n+ 1: k0 + 1 seria um tal nu´mero.
4. Deve-se provar que existem k, n0 ∈ N tais que para todo n ≥ n0, 10n2+100n+1000 ≤ kn2.
Sejam k = 1110 e n0 = 1. Sera´ provado, por induc¸a˜o, que para todo n ≥ n0, 10n2+100n+
1000 ≤ kn2 = 1110n2. Inicialmente, veja que 10×12+100×1+1000 = 1110 = 1110×12.
Seja n um nu´mero natural arbitra´rio maior ou igual a 1, e suponha, como hipo´tese de
induc¸a˜o, que 10n2+100n+1000 ≤ 1110n2. Segue-se que 10(n+1)2+100(n+1)+1000 =
10n2 + 20n+ 10 + 100n+ 100 + 1000 = (10n2 + 100n+ 1000) + 20n+ 110. Pela hipo´tese
de induc¸a˜o, (10n2 +100n+1000) + 20n+110 ≤ 1110n2 +20n+110. Como esta u´ltima e´
menor do que (1110n2 +20n+110) + 2200n+1000 e esta, por sua vez e´ igual a 1110n2 +
2220n+1110 = 1110(n+1)2, conclui-se que 10(n+1)2+100(n+1)+1000 < 1110(n+1)2.
Portanto, pelo princ´ıpio de induc¸a˜o, para todo n ≥ 1, 10n2 + 100n + 1000 ≤ 1110n2. Ja´
que existem k, n0 ∈ N tais que para todo n ≥ n0, 10n2 + 100n + 1000 ≤ kn2, conclui-se
que 10n2 + 100n + 1000 e´ O(n2).
Te´cnicas de provas utilizadas: construtiva para a existencial 2 vezes (quando se exibiu
k = 1110 e n0 = 1) e induc¸a˜o (para provar que para todo n ≥ n0 . . .).
21
5. |A∪B| = |A|+ |B| − |A∩B|.Prova: Cada elemento de A−B e cada elemento de A∩B
e´ contado uma vez em |A|, e cada elemento de B−A e cada elemento de A∩B e´ contado
uma vez em |B|. Assim, os elementos de A ∩ B sa˜o contados duas vezes em |A| + |B|,
raza˜o da subtrac¸a˜o de |A ∩B|.
Generalizando: | ∪ni=1 Ai| = S1 + S2 + · · · + Sn, onde:
Sk = (−1)k+1 ×
∑
j1 6=j2 6=···6=jk
|Aj1 ∩Aj2 ∩ . . . ∩Ajk |, para 1 ≤ k ≤ n.
Para provar este resultado por induc¸a˜o, note inicialmente que | ∪1i=1Ai| = |A1| = S1. Seja
n ≥ 1 arbitra´rio. Hipo´tese de induc¸a˜o: | ∪ni=1 Ai| = S1 + S2 + · · · + Sn, sendo Sk definido
como acima. Basta, agora, provar que | ∪n+1i=1 Ai| = S′1 + S′2 + · · · + S′n+1, onde cada S′k
e´ como Sk, so´ que cada jk pode ser tambe´m k + 1. Como ∪n+1i=1 Ai = (∪ni=1Ai) ∪ An+1,
tem-se, pelo resultado acima, que:
| ∪n+1i=1 Ai| = | ∪ni=1 Ai|+ |An+1| − |(∪ni=1Ai) ∩An+1|.
Pela hipo´tese de induc¸a˜o, segue-se que:
| ∪n+1i=1 Ai| = S1 + S2 + · · · + Sn + |An+1| − |(∪ni=1Ai) ∩An+1|.
Como S′1 = S1 + |An+1| e a intersec¸a˜o distribui sobre unia˜o:
| ∪n+1i=1 Ai| = S′1 + S2 + · · ·+ Sn − | ∪ni=1 (Ai ∩An+1)|.
Pela hipo´tese de induc¸a˜o, tem-se que:
| ∪n+1i=1 (Ai ∩An+1)| = S′′1 + S′′2 + · · ·+ S′′n, onde:
S′′k = (−1)k+1 ×
∑
j1 6=j2 6=···6=jk
|(Aj1 ∩An+1) ∩ (Aj2 ∩An+1) ∩ . . . ∩ (Ajk ∩An+1)|
para 1 ≤ k ≤ n. Ou ainda:
S′′k = (−1)k+1 ×
∑
j1 6=j2 6=···6=jk
|Aj1 ∩Aj2 ∩ . . . ∩Ajk ∩An+1|.
Assim, como
| ∪n+1i=1 Ai| = S′1 + S2 + · · ·+ Sn − (S′′1 + S′′2 + · · · + S′′n).
e como S2 − S′′1 = S′2, S3 − S′′2 = S′3, . . . , Sn − S′′n−1 = S′n, e −S′′n = S′n+1, conclui-se que
| ∪n+1i=1 Ai| = S′1 + S′2 + · · ·+ S′n + S′n+1.
6. a) Seja X um elemento arbitra´rio de P(A) ∪ P(B). Enta˜o X ∈ P(A) ou X ∈ P(B).
No primeiro caso, X ⊆ A, e no segundo, X ⊆ B. Em qualquer caso, X ⊆ A ∪ B.
Portanto, X ∈ P(A ∪B). Conclui-se que P(A) ∪ P(B) ⊆ P(A ∪B).
b) P(A) ∩ P(B) ⊆ P(A ∩B).
Seja X um elemento arbitra´rio de P(A)∩P(B). Enta˜o X ∈ P(A) e X ∈ P(B); logo,
X ⊆ A e X ⊆ B. Segue-se que X ⊆ A ∩ B. Portanto, X ∈ P(A ∩ B). Conclui-se
que P(A) ∩ P(B) ⊆ P(A ∩B).
P(A ∩B) ⊆ P(A) ∩ P(B).
Seja X um elemento arbitra´rio de P(A ∩ B). Enta˜o X ⊆ A ∩ B; logo, X ⊆ A
e X ⊆ B. Segue-se que X ∈ P(A) e X ∈ P(B). Portanto, X ∈ P(A) ∩ P(B).
Conclui-se que P(A ∩B) ⊆ P(A) ∩ P(B).
22
7. a) A4B ⊆ (A ∪B)− (A ∩B).
Seja x ∈ A 4 B. Enta˜o, por definic¸a˜o, x ∈ A − B ou x ∈ B − A. No primeiro
caso, x ∈ A e x 6∈ B; como x ∈ A, x ∈ A ∪ B, e como x 6∈ B, x 6∈ A ∩ B. Assim,
x ∈ (A ∪B)− (A∩B). No segundo caso, procede-se de forma ana´loga para mostrar
que tambe´m x ∈ (A ∪B)− (A ∩B).
(A ∪B)− (A ∩B) ⊆ A4B.
Seja x ∈ (A ∪ B) − (A ∩ B). Segue-se que x ∈ A ∪ B e x 6∈ A ∩ B. Caso 1:
x ∈ A. Como x 6∈ A ∩ B, x 6∈ B. Assim, x ∈ A − B. Caso 2: x ∈ B. Como
x 6∈ A ∩B, x 6∈ A. Assim, x ∈ B −A. Portanto, x ∈ A−B ou x ∈ B −A, ou ainda,
x ∈ (A−B) ∪ (B −A) = A4B.
b) A4 (B 4 C) ⊆ (A4B)4 C.
Seja x ∈ A4 (B4C). Enta˜o, pela definic¸a˜o, x ∈ A− (B4C) ou x ∈ (B4C)−A.
Caso 1: x ∈ A− (B 4 C).
Enta˜o x ∈ A e x 6∈ B 4 C. Desta u´ltima, segue-se que x 6∈ B − C e x 6∈ C − B, ou
seja, (I) x 6∈ B ou x ∈ C e (II) x 6∈ C ou x ∈ B. Por um lado, se x ∈ C, de (II)
segue-se que x ∈ B; com isto, x 6∈ A − B e x 6∈ B − A; logo, x 6∈ A4 B e, assim,
x ∈ C − A4 B. Por outro lado, se x 6∈ C, de (I) segue-se x 6∈ B; com isto, e como
x ∈ A, x ∈ A − B e, portanto, x ∈ A4 B; segue-se que x ∈ (A4 B) − C. Como
x ∈ C−A4B se x ∈ C, e x ∈ (A4B)−C se x 6∈ C, conclui-se que x ∈ (A4B)4C.
Caso 2: x ∈ (B 4 C)−A
Enta˜o x ∈ B 4 C e x 6∈ A. Da primeira, Segue-se que x ∈ B e x 6∈ C ou x ∈ C e
x 6∈ B. No caso em que x ∈ B e x 6∈ C, x ∈ B −A e, portanto, x ∈ A4B; segue-se
que x ∈ (A4 B) − C e que x ∈ (A4 B)4 C. E no caso em que x ∈ C e x 6∈ B,
x 6∈ A−B e x 6∈ B −A; portanto, x 6∈ A4B; e assim, x ∈ C − (A4B), ou ainda,
x ∈ (A4B)4 C.
(A4B)4 C ⊆ A4 (B 4 C).
Procede-se forma similar a` acima.
c) (A−B)4 (B −A) ⊆ A4B.
Seja x ∈ (A−B)4 (B−A). Enta˜o x ∈ (A−B)− (B−A) ou x ∈ (B−A)− (A−B).
No caso em que x ∈ (A − B) − (B − A), x ∈ A − B e, portanto, x ∈ A4 B. E no
caso em que x ∈ (B −A)− (A−B), x ∈ A−B e, portanto, x ∈ A4B.
A4B ⊆ (A−B)4 (B −A).
Seja x ∈ A4 B. Enta˜o x ∈ A − B ou x ∈ B − A. No primeiro caso, segue-se que
x ∈ (A − B)− (B − A), e no segundo segue-se que x ∈ (B − A) − (A − B). Assim,
em qualquer caso, x ∈ (A−B)4 (B −A).
d) (→)
Suponha que A4B = A e suponha que B 6= ∅. Seja, enta˜o b ∈ B. Se b ∈ A, enta˜o,
como A4 B = A, b ∈ A4 B; mas isto e´ imposs´ıvel, pois se b ∈ A, b 6∈ B − A e se
b ∈ B, b 6∈ A − B. Assim, b 6∈ A. Neste caso, b ∈ B − A e, logo, b ∈ A4 B. Mas
isto tambe´m no˜ pode ser, ja´ que A4 B = A. Conclui-se, portanto, que b na˜o pode
existir, e, assim, B = ∅.
(←)
Suponha que B = ∅. Prova-se, primeiro, que A4 B ⊆ A. Seja x ∈ A4 B. Com
isto, x ∈ A − B ou x ∈ B − A. Como B = ∅, este u´ltimo caso e´ imposs´ıvel. Assim,
x ∈ A − B. E como B = ∅, x ∈ A. Portanto, A 4 B ⊆ A. Agora, prova-se que
A ⊆ A4 B. Seja x ∈ A. Como B = ∅, x ∈ A − B e, portanto, x ∈ A4 B. Logo,
A ⊆ A4B.
23
e) A−B = A4B se, e somente se, B ⊆ A, como provado abaixo.
(→)
Suponha que A − B = A 4 B. Seja b ∈ B. Com isto, b 6∈ A − B. Supondo que
b 6∈ A, segue-se que b ∈ B − A e, portanto, b ∈ A4 B. Isto na˜o pode ser, visto que
A−B = A4B. Assim, se b ∈ B, enta˜o b ∈ A. Portanto, B ⊆ A.
(←)
Suponha que B ⊆ A. Se x ∈ A−B, enta˜o x ∈ A4B; logo A−B ⊆ A4B. Assim,
basta mostrar que A4B ⊆ A−B. Seja x ∈ A4B. Como B ⊆ A, tem-se x 6∈ B−A;
portanto, x ∈ A−B. Logo, A4B ⊆ A−B.
8. Seja uma relac¸a˜o R reflexiva e transitiva arbitra´ria. Sera´ mostrado por induc¸a˜o que
Rn = R para todo n ≥ 1. R1 = R, por definic¸a˜o. Seja n ≥ 1. Suponha, como hipo´tese
de induc¸a˜o, que Rn = R. Por definic¸a˜o, Rn+1 = Rn ◦R, pois n+ 1 ≥ 2. Pela hipo´tese de
induc¸a˜o, Rn = R. Assim, basta mostrar que R◦R = R. Mostra-se primeiro que R ⊆ R◦R.
Para isto, seja (x, y) ∈ R. Como R e´ reflexiva, (x, x) ∈ R. Logo, (x, y) ∈ R ◦R. Portanto,
R ⊆ R ◦ R. Agora, mostra-se que R ◦R ⊆ R. Seja (x, y) ∈ R ◦ R; enta˜o existe z tal que
(x, z) ∈ R e (z, y) ∈ R. Como R e´ transitiva, (x, y) ∈ R. Portanto, R ◦R ⊆ R.
9. Seja F : A→ A tal que f(a) = aC para todo a ∈ A, onde aC e´ um certo elemento da classe
de equivaleˆncia a que pertence a. Tal elemento existe, visto que todo a ∈ A pertence a
alguma classe de equivaleˆncia e classes de equivaleˆncia na˜o sa˜o vazias. Qualquer elemento
da classe de equivaleˆncia de a serve para ser aC , mas escolhido um, ele deve ser a u´nica
imagem para todos os componentes da classe. Uma func¸a˜o assim satisfaz os requisitos,
como mostrado abaixo.
(→)
Suponha que xRy. Enta˜o x e y pertencem a` mesma classe de equivaleˆncia C e, portanto,
f(x) = xC = yC = f(y).
(←)
Suponha que f(x) = f(y). Enta˜o f(x) e f(y) pertencem a` mesma classe de equivaleˆncia.
Portanto, xRy.
10. [a] 6= ∅, visto que R e´ reflexiva e, portanto, aRa.
Agora, mostra-se que as classes de equivaleˆncia sa˜o disjuntas, ou seja, dados a, b ∈ A,
[a] = [b] ou [a] ∩ [b] = ∅. Suponha que [a] ∩ [b] 6= ∅, e seja x ∈ A tal que x ∈ [a] e x ∈ [b].
Seja y ∈ [a]. Enta˜o, aRy e, por simetria, yRa. Como aRx, por transitividade, yRx. Como
xRb, por transitividade, yRb. Por simetria, bRy. Logo, y ∈ [b]. Como y e´ um elemento
arbitra´rio de [a], [a] ⊆ [b]. De form ana´loga, mostra-se [b] ⊆ [a].
Falta mostrar que ∪a∈A[a] = A. As classes de equivaleˆncia [a] so´ teˆm elementos de A.
Assim, ∪a∈A[a] ⊆ A. Por outro lado, se x ∈ A, enta˜o existe uma classe de equivaleˆncia [x]
por definic¸a˜o, o que mostra que A ⊆ ∪a∈A[a].
11. a) f(A ∪B) ⊆ f(A) ∪ f(B).
Seja x ∈ f(A ∪ B). Enta˜o, x = f(y) onde y ∈ A ∪ B. Se y ∈ A, segue-se que
f(y) ∈ f(A) e se y ∈ B, f(y) ∈ f(B). Assim, x = f(y) ∈ f(A) ∪ f(B).
f(A) ∪ f(B) ⊆ f(A ∪B).
Seja x ∈ f(A) ∪ f(B). Enta˜o x ∈ f(A) ou x ∈ f(B). Se x ∈ f(A), enta˜o x = f(y),
onde y ∈ A; se y ∈ A, y ∈ A∪B, e portanto x = f(y) ∈ f(A∪B). Da mesma forma,
mostra-se que se x ∈ f(B), x ∈ f(A ∪B).
24
b) f(A ∩B) ⊆ f(A) ∩ f(B).
Seja x ∈ f(A∩B). Enta˜o, x = f(y) onde y ∈ A∩B. Assim, y ∈ A e y ∈ B, de onde
se segue que f(y) ∈ f(A) e f(y) ∈ f(B). Logo, x = f(y) ∈ f(A) ∩ f(B).
12. a) Tem-se:
fA(x) = 1↔ x ∈ A por definic¸a˜o
↔ x 6∈A
↔ f
A
(x) 6= 1 por definic¸a˜o
↔ f
A
(x) = 0
↔ 1− f
A
(x) = 1.
Portanto, fA(x) = 1− fA(x).
b) Tem-se:
fA∪B(x) = 1↔ x ∈ A ∪B por definic¸a˜o
↔ x ∈ A ou x ∈ B
↔ fA(x) = 1 ou fB(x) = 1 por definic¸a˜o
↔ fA(x) + fB(x)− fA(x)fB(x) = 1.
Portanto, fA∪B(x) = fA(x) + fB(x)− fA(x)fB(x).
c) Tem-se:
fA∩B(x) = 1↔ x ∈ A ∩B por definic¸a˜o
↔ x ∈ A e x ∈ B
↔ fA(x) = 1 e fB(x) = 1 por definic¸a˜o
↔ fA(x)fB(x) = 1.
Portanto, fA∩B(x) = fA(x)fB(x).
d) Tem-se:
fA−B(x) = 1↔ x ∈ A−B por definic¸a˜o
↔ x ∈ A e x 6∈ B
↔ fA(x) = 1 e fB(x) 6= 1 por definic¸a˜o
↔ fA(x) = 1 e fB(x) = 0
↔ fA(x) = 1 e 1− fB(x) = 1
↔ fA(x)(1 − fB(x)) = 1.
Portanto, fA∩B(x) = fA(x)fB(x).
13. (→)
Seja uma func¸a˜o injetora f : A → B. Seja C a imagem de A. Enta˜o g : C → A tal que
g(c) e´ o elemento a tal que f(a) = c e´ uma func¸a˜o sobretora. O elemento a existe e e´
u´nico visto que f e´ uma func¸a˜o injetora.
(←)
Seja uma func¸a˜o sobrejetora f : B → A. Enta˜o g : A→ B tal que g(a) e´ algum elemento
de {b | f(b) = a} e´ uma func¸a˜o injetora. Como f e´ uma func¸a˜o sobrejetora, para todo a
tal conjunto na˜o e´ vazio; e os conjuntos sa˜o disjuntos, pois f e´ func¸a˜o.
14. Seja Σ = {a1, a2, . . . , an}. Enta˜o:
Σ∗ e´ enumera´vel. Uma enumerac¸a˜o para Σ e´ dada pela func¸a˜o η : Σ∗ → N tal que
η(λ) = 0 e η(apmapm−1 . . . ap0) =
∑m
k=0(pk × nk).
25
P(Σ∗) na˜o e´ enumera´vel. Suponha que P(Σ∗) e´ enumera´vel. Enta˜o existe uma func¸a˜o
bijetora de P(Σ∗) para N, de forma que os elementos de P(Σ∗) podem ser enumer-
ados: A0, A1, A2, . . .. Seja o conjunto B = {w ∈ Σ∗ |w 6∈ Aη(w)}, onde η e´ a func¸a˜o
de enumerac¸a˜o vista acima (ou qualquer outra). Mas, como {η(w) |w ∈ Σ∗} = N,
segue-se que B 6= Ai para todo i ∈N. Logo, a suposic¸a˜o de que existe a enumerac¸a˜o
A0, A1, A2, . . . na˜o e´ correta, ou seja, P(Σ∗) na˜o e´ enumera´vel.
15. Seja uma func¸a˜o bijetora f : A → P(A). Agora, considere o conjunto D ⊆ A assim
definido:
para cada a ∈ A, a ∈ D se, e somente se, a 6∈ f(a).
Como f e´ uma func¸a˜o bijetora, para cada X ⊆ A deve existir x ∈ A tal que f(x) = X.
Em particular, para D deve enta˜o existir d ∈ A tal que f(d) = D. Mas, pela definic¸a˜o de
D, segue-se que d ∈ D = f(d) se, e somente se, d 6∈ f(d). Tal contradic¸a˜o leva a` conclusa˜o
que na˜o existe uma func¸a˜o bijetora de um conjunto A para um conjunto P(A).
Este resultado implica que para qualquer conjunto existe conjunto com cardinalidade
maior. Em particular, considerando-se conjuntos infinitos, existe uma infinidade de “or-
dens de infinidade”: N, P(N), P(P(N)), etc.
16. A representac¸a˜o de um nu´mero n na base b gasta blogb nc+ 1 s´ımbolos, se b > 1. Como
logb n = logb c × logc n, onde b > 1 e c > 1, veˆ-se que a transic¸a˜o de uma base para
outra, ambas maiores ou iguais a 2, e´ influenciada apenas por um fator constante, logb c.
E dado o exposto no Exemplo 47, as representac¸o˜es em bases maiores ou iguais a 2 sa˜o
exponencialmente mais concisas do que na base 1.
17. Definic¸a˜o recursiva de v : {0, 1}∗ → N, de forma que v(w) e´ o nu´mero representado por
w na base 2:
a) v(0) = 0 e v(1) = 1;
b) v(x0) = 2v(x) e v(x1) = 2v(x) + 1.
18. Subtrac¸a˜o:
a) m− 0 = m, para todo m ∈ N;
b) s(m)− s(n) = m− n, para todo m,n ∈N.
Divisa˜o:
a) m/s(0) = m, para todo m ∈ N;
b) para todo m ∈ N e todo n > s(0), m/n = 0, se m < n, e m/n = s((m − n)/n), se
m ≥ n.
onde a relac¸a˜o < e´ assim definida:
a) n < s(n), para todo n ∈ N;
b) se m < n, enta˜o m < s(n), para todo m,n ∈ N.
Resto da divisa˜o:
a) nmod n = 0, para todo n ∈ N;
b) mmod n = m, se m < n;
c) mmod n = (m− n)mod n, se n < m.
26
Ma´ximo divisor comum:
a) mdc(n, n) = n, para todo n ∈ N;
b) mdc(m,n) = mdc(m− n, n), se n < m;
c) mdc(m,n) = mdc(m,n−m), se m < n.
19. Conjunto Anc(v) de ancestrais de um ve´rtice v de uma a´rvore (V,A, r):
a) v ∈ Anc(v);
b) se v ∈ Anc(v) e (v′, v) ∈ A, enta˜o v′ ∈ Anc(v).
20. ψ(n) = blog2 nc. Sera´ feita uma demonstrac¸a˜o por induc¸a˜o forte. Assim, suponha, como
hipo´tese de induc¸a˜o, que ψ(k) = blog2 kc para todo k < n.
Caso n = 1. ψ(1) = 0 = log2 1.
Caso n > 1. Por definic¸a˜o, ψ(n) = ψ(bn/2c)+1. Como, bn/2c < n, segue-se, pela hipo´tese
de induc¸a˜o, que ψ(n) = blog2bn/2cc + 1. Se n mod 2 = 0, enta˜o ψ(n) = blog2 n/2c+ 1 =
b(log2 n)− 1c + 1 = b(log2 n)c − 1 + 1 = blog2 nc. Por outro lado, se n mod 2 = 1, enta˜o
ψ(n) = blog2(n− 1)/2c+1 = blog2(n− 1)− 1c+1 = blog2(n− 1)c− 1+1 = blog2(n− 1)c.
Mas, se n mod 2 = 1 e n > 0, blog2(n − 1)c = blog2 nc. Assim, ψ(n) = blog2 nc em
qualquer caso.
21. a)
∑0
k=1[k(k+1)(k+2)] = 0× 1× 2 = 0 = (0× 1× 2× 3)/4. Seja n ≥ 1. Suponha, cmo
hipo´tese de induc¸a˜o, que
∑n
k=1[k(k +1)(k+2)] = n(n+ 1)(n+2)(n+3)/4. Tem-se:∑n+1
k=1 [k(k+1)(k+2)] = [
∑n
k=1[k(k+1)(k+2)]]+(n+1)(n+2)(n+3). Aplicando-se
a hipo´tese de induc¸a˜o, obte´m-se que esta u´ltima e´ igual a [n(n+1)(n+2)(n+3)/4]+
(n + 1)(n + 2)(n + 3). Simplificando-se esta, chega-se a
∑n+1
k=1 [k(k + 1)(k + 2)] =
(n+ 1)(n + 2)(n + 3)(n + 4)/4, o que completa a prova.
b) Inicialmente, veja que 30 − 70 − 2 = 0, que e´ divis´ıvel por 8. Seja n um nu´mero
natural arbitra´rio. Suponha como hipo´tese de induc¸a˜o que 3n+7n−2 e´ divis´ıvel por
8. Tem-se: 3n+1+7n+1−2 = 3×3n+7×7n−2 = 3(3n+7n−2)+(4×7n+4). Pela
hipo´tese de induc¸a˜o, o primeiro termo desta u´ltima e´ divis´ıvel por 8. Assim, basta
mostrar que o segundo, 4× 7n+4 tambe´m e´ divis´ıvel por 8, o que sera´ feito tambe´m
por induc¸a˜o. Para n = 0: 4×70+4 = 8, que e´ divis´ıvel por 8. Seja n ≥ 0, e suponha
que 4× 7n + 4 e´ divis´ıvel por 8. Segue-se que 4 × 7n+1 + 4 = 7(4 × 7n + 4) − 24. O
primeiro termo desta u´ltima e´ divis´ıvel por 8, pela hipo´tese de induc¸a˜o, e o segundo,
24, tambe´m e´, o que leva a` conclusa˜o que 4× 7n+1 + 4 e´ divis´ıvel por 8.
c) Tem-se:
∏0
k=2(1 − 1/k) = 1 − 1/2 = 1/2. Seja n ≥ 2, e suponha, como hipo´tese
de induc¸a˜o, que
∏n
k=2(1 − 1/k) = 1/n. Segue-se que:
∏n+1
k=2(1 − 1/k) = [
∏n
k=2(1 −
1/k)] × [1 − 1/(n + 1)] = (1/n) × [1 − 1/(n + 1)], pela hipo´tese de induc¸a˜o. Esta
u´ltima e´ igual a (1/n)× (n+ 1− 1)/(n + 1)] = 1/(n + 1), o que completa a prova.
d)
∑2
k=1(1/
√
k) = 1 + 1/
√
2 = (
√
2 + 1)/
√
2 =
√
2(
√
2 + 1)/2 >
√
2, pois
√
2 + 1 > 2.
Seja n ≥ 2. Hipo´tese de induc¸a˜o: ∑nk=1(1/√k) > √n. Segue-se que: ∑n+1k=1(1/√k) =
[
∑n
k=1(1/
√
k)] + 1/
√
n+ 1. Segue-se, pela hipo´tese de induc¸a˜o, que
∑n+1
k=1(1/
√
k) >√
n+1/
√
n+ 1. Mas esta u´ltima e´ igual a [
√
n
√
n+ 1+1]/
√
n+ 1, que, por sua vez
e´ igual a
√
n+ 1[
√
n
√
n+ 1 + 1]/(n + 1). Mas esta e´ maior do que
√
n+ 1, como
requerido para completar a prova, pois
√
n
√
n+ 1+1 > n+1, ja´ que
√
n
√
n+ 1 > n.
22. Representando cada pessoa por um ve´rtice e cada relacionamento de amizade por uma
aresta, de tal forma que v, v′ e´ uma aresta se, e somente se, as pessoas representadas por
v e v′ sa˜o amigas, deve-se mostrar que o grafo tem 2 ve´rtices com o mesmo grau. Para
27
isto, pode-se usar o princ´ıpio do pombal, segundo o qual para se acomodar n pombos em
menos de n casinhas, alguma casinha devera´ receber mais de 1 pombo. Seja um grafo de
n ve´rtices, representando um grupo de n pessoas. Observando-se que um ve´rtice pode ter
de 0 a n − 1 ve´rtices adjacentes (o grafo na˜o pode conter loops nem arestas mu´ltiplas),
considera-se 2 casos. Supondo que um certo ve´rtice tem grau 0, enta˜o cada ve´rtice so´
pode ter graus de 0 a n− 2 (um ve´rtice na˜o pode ser adjacente a si mesmo nem a`quele de
grau 0). Por outro lado, se nenhum ve´rtice tem grau 0, cada ve´rtice so´ pode ter graus de
1 a n − 1. Nos dois casos, pelo princ´ıpio do pombal, existem dois ve´rtices com o mesmo
grau.
23. Se cada ve´rtice pode ter qualquer nu´mero de filhos, a altura e´ 0, se a a´rvore conte´m
apenas 1 ve´rtice, e e´ 2, se ela conte´m mais de 1 ve´rtice; neste u´ltimo caso, todos os
ve´rtices, com excessa˜o da raiz, sa˜o filhos da raiz. Se cada ve´rtice pode ter no ma´ximo
r filhos, a altura mı´nima e´ a de uma a´rvore que em cada n´ıvel k tem rk ve´rtices, com
excessa˜o, possivelmente, do u´ltimo. Assim, a altura mı´nima, neste caso, e´blogr nc, onde
n e´ o nu´mero de ve´rtices.
24. a) Uma a´rvore estritamente n-a´ria com i ve´rtices internos tem n× i+1 ve´rtices, ja´ que
cada um dos i ve´rtice internos tem n filhos; e o termo 1 refere-se a` raiz.
b) Dado o resultado anterior, tem-se que uma a´rvore estritamente n-a´ria de k ve´rtices
tem (k − 1)/n ve´rtices internos. Ja´ o nu´mero de folhas e´ k − i = k − (k − 1)/n.
c) Uma a´rvore estritamente n-a´ria com k ve´rtices tem altura mı´nima igual a blogn kc,
e altura ma´xima igual a d(k − 1)/ne.
25. L = X, onde X = {0m1n |m,n ≥ 0}.
L ⊆ X.
Sera´ provado por induc¸a˜o sobre o tamanho das palavras w que se w ∈ L emta˜o w ∈ X.
λ = λλ = 0010 ∈ X. Seja n ≥ 0, e suponha, como hipo´tese de induc¸a˜o, que x ∈ X se
x ∈ L, para x tal que |x| = n. Para w ∈ L tal que |w| = n+1 tem-se, pela definic¸a˜o de L,
que w = 0y ou w = x1, onde x e y sa˜o palavras de L. Pela hipo´tese de induc¸a˜o, segue-se
que x ∈ X e y ∈ X, ou seja, ambos, x e y sa˜o da forma 0m1n. Enta˜o w = 00m1n ∈ X ou
w = 0m1n1 ∈ X.
X ⊆ L.
Sera´ provado por induc¸a˜o sobre o tamanho das palavras w que se w ∈ X emta˜o w ∈ L.
0010 = λλ = λ ∈ L. Seja n ≥ 0, e suponha, como hipo´tese de induc¸a˜o, que x ∈ L
se x ∈ X, para x tal que |x| = n. Para w ∈ X tal que |w| = n + 1 tem-se, que w e´
da forma 00m1n ou da forma 11n, onde m,n ≥ 0. No primeiro caso, pela hipo´tese de
induc¸a˜o, segue-se que 0m1n ∈ L; enta˜o, pela definic¸a˜o de L, w ∈ L. No segundo caso,
como 11n = 1n1, e, pela hipo´tese de induc¸a˜o, 1n ∈ L, tem-se tambe´m que, pela definic¸a˜o
de L, w ∈ L.
26. a) Definic¸a˜o recursiva de L1 = {w ∈ {0, 1} | |w| e´ par}:
• λ ∈ L1;
• se y ∈ L1, enta˜o 00y, 01y, 10y, 11y ∈ L1.
b) Definic¸a˜o recursiva de L2 = {w ∈ {0, 1} |w e´ pal´ındromo}:
• λ, 0, 1 ∈ L2;
• se w ∈ L2, enta˜o 0w0, 1w1 ∈ L2.
c) Definic¸a˜o recursiva de L3 = {w ∈ {0, 1} |w conte´m 00}:
28
• 00 ∈ L3;
• se w ∈ L3, enta˜o 0w, 1w,w0, w1 ∈ L3.
d) Definic¸a˜o recursiva de L4 = {w ∈ {0, 1} |w na˜o conte´m 00}:
• λ, 0 ∈ L4;
• se y ∈ L4, enta˜o y1, y10 ∈ L4.
e) Definic¸a˜o recursiva de L5 = {0n2 |n ∈ N}:
• λ ∈ L5;
• se y ∈ L5, enta˜o y02
√
|y|+1 ∈ L5.
f) Definic¸a˜o recursiva de L6 = {w |w e´ uma permutac¸a˜o dos d´ıgitos 1, 2 e 3}:
• 123 ∈ L6;
• se abc ∈ L6, enta˜o acb ∈ L6 e bca ∈ L6, onde a, b, c ∈ {1, 2, 3}.
g) Definic¸a˜o recursiva de L7 = {w |w e´ uma permutac¸a˜o dos 10 d´ıgitos decimais}:
• 0123456789 ∈ L7;
• se xab ∈ L7 ou axb ∈ L7, enta˜o xba ∈ L7, onde a, b ∈ {1, 2} e x ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}∗ .
27. Definic¸a˜o recursiva de concatenac¸a˜o:
• xλ = x para x ∈ Σ∗;
• se x(ya) = (xy)a para x, y ∈ Σ∗ e a ∈ Σ.
Sera´ provado que (xy)z = x(yz) por induc¸a˜o sobre |z|. Para z = λ, tem-se: (xy)λ = xy =
x(yλ). Seja n ≥ 0. Suponha que (xy)z = x(yz) para toda palavra z tal que |z| = n.
Seja w uma palavra de n+ 1 s´ımbolos. Enta˜o w = za para uma palavra z de n s´ımbolos
e a ∈ Σ. Segue-se que (xy)w = (xy)(za) = ((xy)z)a, pela definic¸a˜o de concatenac¸a˜o.
Prosseguindo: ((xy)z)a = (x(yz))a, pela hipo´tese de induc¸a˜o. E, aplicando-se duas vezes
a definic¸a˜o de concatenac¸a˜o, determina-se que (x(yz))a = x((yz)a) = x(y(za)), o que
conclui a argumentac¸a˜o, visto que x(y(za)) = x(yw).
Definic¸a˜o recursiva de reverso:
• λR = λ;
• se xR = y e a ∈ Σ enta˜o (xa)R = axR.
Sera´ provado que (xy)R = yRxR por induc¸a˜o sobre |y|. Para y = λ, tem-se: (xy)R =
(xλ)R = xR = λxR = λRxR = yRxR. Seja n ≥ 0, e suponha que (xy)R = yRxR para
palavras y tal que |y| = n. Seja w uma palavra de n+1 s´ımbolos, ou seja w = za para uma
palavra z de n s´ımbolos e a ∈ Σ. Enta˜o (xw)R = (x(za))R = ((xz)a)R, pela definic¸a˜o de
concatenac¸a˜o. E ((xz)a)R = a(xz)R, pelas definic¸a˜o de reverso. Pela hipo´tese de induc¸a˜o,
segue-se que a(xz)R = a(zRxR). Pelo resultado acima (associatividade da concatenac¸a˜o),
a(zRxR) = (azR)xR, e pela definic¸a˜o de reverso, (azR)xR = (za)RxR = wRxR.
A seguir, mostra que se w e´ pal´ındromo, w = vvR ou w = vavR para algum v ∈ Σ∗
e a ∈ Σ. Seja w um pal´ındromo. Se |w| e´ par, enta˜o w = xy, onde |x| = |y| ≥ 0.
Como w e´ pal´ındromo, w = xy = (xy)R = yRxR. De xy = yRxR e do fato de que
|x| = |y| = |yR|, segue-se que yR = x (e xR = y). Assim, w = xy = xxR. Agora, suponha
que |w| e´ ı´mpar. Enta˜o w = xay, onde |x| = |y| ≥ 0, a ∈ Σ. Como w e´ pal´ındromo,
w = xay = (xay)R = yR(xa)R = yRaxR. Como w = xay = yRaxR e |x| = |y| = |yR|,
segue-se que yR = x (e xR = y) e, portanto, w = xay = xaxR.
29
28. De x = xR, y = yR e xy = (xy)R = yRxR, deduz-se que xy = yx. Sera´ mostrado por
induc¸a˜o forte sobre |xy| que, neste caso, existem k, n ∈ N e z tais que x = zk e y = zn.
Seja m ≥ 0 e suponha, como hipo´tese de induc¸a˜o, que o resultado valha para todo x e
y tais que |xy| < m. Sejam, enta˜o duas palavras quaisquer x e y tais que |xy| = m. Se
m = 0, x = y = λ, e basta fazer k = n = 0. Seja, enta˜o, x e y tais que |xy| ≥ 1. Sa˜o 3
casos a considerar: |x| = |y|, |x| < |y| e |x| > |y|. No primeiro caso, tem-se que x = y
e, portanto, basta fazer z = x e k = n = 1. No segundo caso, deve existir uma palavra
s tal que y = xs. Como xy = yx, segue-se que xxs = xsx, que implica que xs = sx.
Desta u´ltima, pela hipo´tese de induc¸a˜o, existem u, i e j tais que x = ui e s = uj. Assim,
y = xs = ui+j . Isto mostra que o resultado vale tomando-se z = u, k = i e n = i + j. O
terceiro caso e´ similar a este u´ltimo.
29. Seja X ⊆ L∗. Por induc¸a˜o sobre o tamanho de uma palavra w, sera´ mostrado que w ∈ L∗
se, e somente se, w ∈ (L∗∪X)∗. Tem-se: λ ∈ (L∗∪X)∗ e λ ∈ L∗, por definic¸a˜o. Seja uma
palavra w tal que |w| > 0. Se w ∈ L∗, enta˜o, por definic¸a˜o, w = xy, onde x ∈ L∗ e y ∈ L.
Como x ∈ L∗, x ∈ L∗ ∪ X e tambe´m x ∈ (L∗ ∪ X)∗. Como y ∈ L, y ∈ L∗ e tambe´m
y ∈ L∗ ∪X. Logo xy = w ∈ (L∗ ∪X)∗. Por outro lado, se w ∈ (L∗ ∪X)∗, w = xy, onde
x ∈ (L∗ ∪X)∗ e y ∈ L∗ ∪X. Como X ⊆ L∗, y ∈ L∗. Pela hipo´tese de induc¸a˜o, x ∈ L∗.
Assim, segue-se que xy = w ∈ L∗.
30. Como Σ1 e Σ2 sa˜o alfabetos, Σ
∗
1 e Σ
∗
2 sa˜o enumera´veis. Assim, sejam f1 : Σ
∗
1 → N
e f2 : Σ
∗
2 → N func¸o˜es bijetoras. A func¸a˜o g : Σ∗1Σ∗2 → N, onde g(xy) = (f1(x) +
f2(y))(f1(x) + f2(y) + 1)/2 + f1(x) para x ∈ Σ∗1 e y ∈ Σ∗2, e´ bijetora. Logo, Σ∗1Σ∗2 e´
enumera´vel.
31. Por induc¸a˜o sobre n. O domı´nio deH0 : Σ
0×Σ0 → N e´ {(λ, λ)}, e tem-se queH0(λ, λ) = 0,
e portanto H0(λ, λ) = H0(λ, λ) + H0(λ, λ). Seja n ≥ 0 e suponha, como hipo´tese de
induc¸a˜o, que Hn(x, y) ≤ Hn(x, z) + Hn(z, y) para qualquer palavra z de Σn. Sejam
a, b, c ∈ Σ. Sera´ mostrado que Hn+1(xa, yb) ≤ Hn(xa, zc) + Hn(zc, yb). Considera-se 5
casos:
a = b = c.
Enta˜o Hn+1(xa, yb) = Hn(x, y), Hn+1(xa, zc) = Hn(x, z) e Hn+1(zc, yb) = Hn(z, y).
Como, pela hipo´tese de induc¸a˜o, Hn(x, y) ≤ Hn(x, z)+Hn(z, y), Hn+1(xa, yb) ≤ Hn(xa, zc)+
Hn(zc, yb).
a = b 6= c.
Enta˜oHn+1(xa, yb) = Hn(x, y), Hn+1(xa, zc) = Hn(x, z)+1 eHn+1(zc, yb) = Hn(z, y)+1.
Como, pela hipo´tese de induc¸a˜o, Hn(x, y) ≤ Hn(x, z) +Hn(z, y), segue-se que Hn(x, y) <
Hn(x, z) + 1 +Hn(z, y) + 1 e, portanto, Hn+1(xa, yb) < Hn(xa, zc) +Hn(zc, yb).
a = c 6= b.
Enta˜oHn+1(xa, yb) = Hn(x, y)+1, Hn+1(xa, zc) = Hn(x, z) eHn+1(zc, yb) = Hn(z, y)+1.
Como, pela hipo´tese de induc¸a˜o, Hn(x, y) ≤ Hn(x, z) +Hn(z, y), segue-se que Hn(x, y) +
1 ≤ Hn(x, z) +Hn(z, y) + 1 e, portanto, Hn+1(xa, yb) ≤ Hn(xa, zc) +Hn(zc, yb).
b = c 6= a.
Enta˜oHn+1(xa, yb) = Hn(x, y)+1, Hn+1(xa, zc) = Hn(x, z)+1 eHn+1(zc, yb) = Hn(z, y).
Como, pela hipo´tese de induc¸a˜o, Hn(x, y) ≤ Hn(x, z) +Hn(z, y), segue-se que Hn(x, y) +
1 ≤ Hn(x, z) + 1 +Hn(z, y) e, portanto, Hn+1(xa, yb) ≤ Hn(xa, zc) +Hn(zc, yb).
a 6= b 6= c.
Enta˜o Hn+1(xa, yb) = Hn(x, y) + 1, Hn+1(xa, zc) = Hn(x, z) + 1 e Hn+1(zc, yb) =
30
Hn(z, y) + 1. Como, pela hipo´tese de induc¸a˜o, Hn(x, y) ≤ Hn(x, z) + Hn(z, y), segue-
se que Hn(x, y)+1 < Hn(x, z)+1+Hn(z, y)+1 e, portanto, Hn+1(xa, yb) < Hn(xa, zc)+
Hn(zc, yb).
Assim, veˆ-se que, em qualquer caso, Hn+1(xa, yb) ≤ Hn(xa, zc) +Hn(zc, yb).
32. a) Grama´tica para {w ∈ {0, 1}∗ |w na˜o conte´m 00}:
P → 0A | 1P |λ
A → 1P |λ
b) Grama´tica para {0n12n+10n |n ∈ N}:
P → 0UP0 | 1
U1 → 111
U0 → 0U
c)Grama´tica para {w0w |w ∈ {1, 2}∗}:
P → 1PU | 2PD | 0
0U → 01
0D → 02
1U → U1
2U → U2
1D → D1
2D → D2
d) Grama´tica para {anbnck | 0 ≤ n < k}:
P → AS
A → aAbC |λ
Cb → bC
Cc → cc
S → cS | c
31
32
Cap´ıtulo 2
Ma´quinas de Estado-Finito
2.1 Alguns Exemplos
1. Cada estado sera´ uma palavra mcl, onde m ∈ {0, 1, 2, 3} e´ o nu´mero de missiona´rios do
lado esquerdo, c ∈ {0, 1, 2, 3} e´ o nu´mero de canibais do lado esquerdo, e l ∈ {e, d} e´ o
lado em que esta´ a canoa (e: esquerdo; d: direito). Cada transic¸a˜o tera´ um um ro´tulo
da forma ij, onde 1 ≤ i + j ≤ 2, sendo que i e´ o nu´mero de missiona´rios e j e´ o nu´mero
de canibais viajando na canoa. O diagrama de estados esta´ mostrado na figura a seguir.
Nele, cada aresta (v1, r, v2) representa duas transic¸o˜es: de v1 para v2 e de v2 para v1,
ambas com ro´tulo r.
33e
22d
31d
32e
32d
30d 31e 11d
22e
02d03e01d
11e
02e
00d01e
01
11
02
10
01
02 01 20
11
20
0102
10
01
11
02
01
2. M = ({0, 1, 2, 3}, {0, 1, 2}, δ, 0, {0}), onde δ e´ dada por:
δ 0 1 2
0 0 1 2
1 3 0 1
2 2 3 0
3 1 2 3
3. Observando-se o cruzamento em T, nota-se que sa˜o necessa´rios sema´foros para controlar
o tra´fego nos sentidos:
• de A para B (nome: A1);
33
• de A para C (nome: A2);
• de B para C (nome: B);
• de C para B (nome: C).
Procurando maximizar o nu´mero de sema´foros abertos (isto e´ com o farol verde aceso),
chega-se a um conjunto de treˆs situac¸o˜es poss´ıveis:
• A1 e A2 abertos, B e C fechados;
• A2 e C abertos, A1 e B fechados;
• B e C abertos, A1 e A2 fechados.
A ma´quina tera´ treˆs estados, um para cada uma destas treˆs situac¸o˜es. Para dar nome a
um estado sera˜o usados os nomes dos sema´foros abertos na situac¸a˜o correspondente. Os
estados sera˜o: {A1, A2}, {A2, C} e {B,C}.
A transic¸a˜o de um estado para outro dependera´ das leituras dos sensores. Para cada
sema´foro ha´ um sensor que verifica se ha´ ve´ıculo no sentido controlado por ele. Para os
sema´foros A1, A2, B e C, sejam a1, a2, b e c as situac¸o˜es em que o sensores respectivos
esta˜o detectando a presenc¸a de ve´ıculo nos sentidos respectivos. Assim, um subconjunto
de S = {a1, a2, b, c} pode ser usado para indicar os sentidos em que os carros esta˜o se
movimentando. Por exemplo, ∅ indica que nenhum ve´ıculo esta´ sendo detectado; {a1, c}
indica que so´ esta˜o sendo detectados ve´ıculos nos sentidos de A para B e de C para B.
Existira´ uma transic¸a˜o de cada estado sob cada subconjunto de S.
Para cada transic¸a˜o, sera´ especificada como sa´ıda uma sequ¨eˆncia de ac¸o˜es do tipo liga/desliga
sema´foros. A ac¸a˜o “ligar sema´foro x”, x ∈ {A1, A2, B,C}, sera´ representada por l(x), e a
ac¸a˜o “desligar sema´foro x” por d(x). A ac¸a˜o “deixa como esta´” sera´ representada por −.
A figura a seguir mostra um diagrama de estados para o problema. Para simplificar o
diagrama, cada aresta representa um conjunto de transic¸o˜es; no diagrama, a sa´ıda e´ a
mesma para cada uma de tais transic¸o˜es. Para este fim, os ro´tulos sa˜o da forma X/y,
onde X e´ um conjunto de subconjuntos de S, e y, a sa´ıda comum, e´ uma sequ¨eˆncia de
ac¸o˜es liga/desliga.
Alguns valores para X esta˜o indicados atrave´s da notac¸a˜o:
• [s]+ = {X ⊂ S | s ∈ X}; e
• [s1\s2] = [s1]+ − [s2]+.
Aqueles da forma [s]+ rotulam transic¸o˜es com maior “prioridade”. Por exemplo, no estado
{A2, C}, dois conjuntos, um com a1 e outro com b indicam que ha´ ve´ıculos nos sentidos
dos sema´foros A1 e B. Com isto, deve-se escolher entre a transic¸a˜o para o estado {A1, A2}
e a transic¸a˜o para o estado {B,C}. La´ esta´ indicado que a transic¸a˜o escolhida e´ aquela
para {B,C}, pois [b]+ = {X ⊂ S | b ∈ X} e [a1\b] = [a1]+ − [b]+ (veja a figura).
34
{A1, A2} {A2, C}
{B,C}
[c]+/d(A1)l(C)
[a1\b]/d(C)l(A1)
[b\c]/d(A1)d(A2)l(B)l(C)
[a1]
+/d(B)d(C)l(A1)l(A2)
[b]+/d(A2)l(B)
[a2\a1]/d(B)l(A2)
P({A1, A2})/− P({A2, C})/−
P({B,C})/−
Pode-se mostrar que, nesta soluc¸a˜o, na˜o ha´ possibilidade de um ve´ıculo ser impedido de
se dirigir de algum ponto a outro indefinidamente. Por outro lado, a soluc¸a˜o apresentada
na˜o e´ u´nica.
2.2 Autoˆmatos Finitos Determin´ısticos
1. a)
1 2 3 4
0,1 0,1 0,1
b)
1 2 3
0,1 0,1
c)
1 2 3 4 5
0,1 0,1 0,1 0,1
0,1
d)
1 2 3
0,1 0,1
0,1
e)
1 2 3 4 5
1 1 1 1
0,1
0000
f) Um AFD seria aquele com estados E = ({0, 1, 2}×{0, 1, 2})∪{e}, sendo e um estado
de erro, e cada estado restante, da forma (i, j), atingido quando a palavra de entrada
w for tal que |w| mod 3 = i e w tiver j ocorreˆncias de 1. O estado inicial e´ (0, 0), os
estados finais sa˜o (0, 1) e (0, 2), e a func¸a˜o de transic¸a˜o e´ dada por:
35
• δ((i, j), 0) = ((i+ 1) mod 3, j) para i, j ∈ {0, 1, 2};
• δ((i, j), 1) = ((i+ 1) mod 3, j + 1) para i ∈ {0, 1, 2} e j ∈ {0, 1};
• δ((i, 2), 1) = e para i ∈ {0, 1, 2}; e
• δ(e, a) = e para a ∈ {0, 1}.
2. a)
1 2 3
0 0
b)
1 2 3
0 1
1
1
c)
− 0 00 001
1 01 11
0 0 1
11 1
0 1
0
1
0,1
d)
0
1
0
1
1
0
1
0
e)
1 0
00000
0
0
0
1
1
1
1
f) Sejam Σ = {0, 1, 2} e E = {xyz |x, y, z ∈ {p, i}}. Suponha que p = i e i = p. Enta˜o
o AFD e´ (E,Σ, δ, ppp, {ppp}), onde δ e´ dada por:
δ(xyz, a) =


xyz se a = 0
xyz se a = 1
xyz se a = 2
3. a)
36
1 2
3
3′
4′ 4
0,1
1
0
0,1
10,1
0
b)
1
0
1
0
c)
0
1
0
1
1
1
0
1
0
0
d) Apo´s consumido um prefixo x, deve-se saber, para prosseguir-se com o reconheci-
mento:
• se |x| e´ par ou ı´mpar (para se saber se a pro´xima posic¸a˜o e´ par ou ı´mpar);
• se x tem nu´mero par ou ı´mpar de 0s nas posic¸o˜es pares; e
• se x tem nu´mero par ou ı´mpar de 0s nas posic¸o˜es ı´mpares.
Logo, sa˜o necessa´rios 8 estados. Representado-se cada estado como uma tripla
[k1, k2, k3], de forma que cada ki pode ser p (par) ou i (´ımpar), e
• k1 = p↔ |x| e´ par,
• k2 = p↔ x tem nu´mero par de 0s nas posic¸o˜es pares, e
• k3 = p↔ x tem nu´mero par de 0s nas posic¸o˜es ı´mpares,
um AFD para a linguagem em questa˜o seria
({p, i}3, {0, 1}, δ, [p, p, p], {[p, p, i], [i, p, i]}})
sendo δ dada por δ([k1, k2, k3], 0) = [k
′
1, k
′
2, k
′
3] e δ([k1, k2, k3], 1) = [k
′
1, k2, k3], onde:
• k′1 = p↔ k1 = i
• k′2 = p↔ (k1 = p e k2 = p) ou (k1 = i e k2 = i)
• k′3 = p↔ (k1 = i e k3 = p) ou (k1 = p e k3 = i)
e)
p u q0
1
0,1
1
4. Um AFD equivalente: M ′ = (E∪{g, f},Σ, δ′, i, F ∪{f}), onde g, f 6∈ E e δ′ e´ como segue:
37
• δ′(e, a) = δ(e, a) para todo a ∈ Σ tal que δ(e, a) e´ definido;
• δ′(e, a) = g para todo a ∈ Σ tal que δ(e, a) e´ indefinido e e 6∈ F ;
• δ′(e, a) = f para todo a ∈ Σ tal que δ(e, a) e´ indefinido e e ∈ F ;
• δ′(g, a) = g para todo a ∈ Σ; e
• δ′(f, a) = f para todo a ∈ Σ.
5. Por induc¸a˜o sobre |x|. Para x = λ, δˆ(e, λy) = δˆ(δˆ(e, λ), y), pela definic¸a˜o de δˆ. Suponha,
como hipo´tese de induc¸a˜o, que δˆ(e, xy) = δˆ(δˆ(e, x), y) para palavras x de tamanho n,
n ≥ 0. Para palavras de tamanho n + 1, az, onde a e´ um s´ımbolo do alfabeto e z uma
palavra de tamanho n, tem-se:
δˆ(e, azy)= δˆ(δ(e, a), zy) pela definic¸a˜o de δˆ
= δˆ(δˆ(δ(e, a), z), y) pela hipo´tese de induc¸a˜o
= δˆ(δˆ(az), y) pela definic¸a˜o de δˆ.
6. Em Prolog, um AFD poderia ser representado por meio de 3 predicados:
inicial(E): E e´ um estado inicial;
final(E): E e´ um estado final;
delta(E1,A,E2): δ(E1, A) = E2.
Representando uma palavra por meio de lista, λ sendo representanda pela lista vazia, um
programa que retorna yes se uma palavra W e´ aceita, e retorna no em caso contra´rio, seria:
aceita(W) :-
inicial(I),
deltachapeu(I,W,E),
final(E).
onde deltachapeu e´ assim definida:
deltachapeu(E,[],E).
deltachapeu(E,[X|R],ER) :-
delta(E,X,EX),
deltachapeu(EX,R,ER).
7. Basta substituir o comando
e← D[e, s]
por um comando da forma:
caso e seja
pp: se s = 0 enta˜o e← ip sena˜o e← pi fimse
ip: se s = 0 enta˜o e← pp sena˜o e← ii fimse
pi : se s = 0 enta˜o e← ii sena˜o e← pp fimse
ii : se s = 0 enta˜o e← pi sena˜o e← ip fimse
fimcaso
38
8. A definic¸a˜o 6 diz que e ≈ e′ se, e somente se:
δˆ(e, y) ∈ F se, e somente se, δˆ(e′, y) ∈ F .
para toda palavra y. Enta˜o, que ≈ e´ uma relac¸a˜o de equivaleˆncia,