Fundamentos de Algoritmo para Computação

Gabarito da AP1 - Fundamentos de Algoritmos para
Computa¸c˜ao
1. (2.0) Verifique se cada uma das afirma¸c˜oes abaixo ´e verdadeira. Se for falsa, justifique e fa¸ca a devida modifica¸c˜ao de modo a torn´a-la verdadeira. Caso seja verdadeira, justifique. (a) {∅} ⊆ {∅, 2,−3, 5}
Resposta:
A afirmativa ´e verdadeira porque ∅ ´e o ´unico elemento do conjunto {∅} e ´e um elemento do conjunto A = {∅, 2,−3, 5}, usamos o s´ımbolo est´a contido (⊆) para estudarmos a rela¸c˜ao entre conjuntos.
(b) (A ∪ B) ∩ C = (A ∩ B) ∪ C
Resposta: A afirmativa ´e falsa, pois por exemplo, se considerarmos os conjuntos
A = {1, 2, 3, 4}, B = {3, 4, 5, 6} e C = {1, 3, 5, 7, 9}, temos A ∪ B =
{1, 2, 3, 4, 5, 6}, (A ∪ B) ∩ C = {1, 3, 5}, A ∩ B = {3, 4} e (A ∩ B) ∪ C =
{1, 3, 4, 5, 7, 9}, conclu´ımos que (A ∪ B) ∩ C 6= (A ∩ B) ∪ C.
As afirma¸c˜oes corretas s˜ao:
(A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
OU
(A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C)
(c) Se n(A ∪ B) = 15, n(A) = 9, n(A ∩ B) = 2 ent˜ao n(B) = 6.
Resposta: A afirma¸c˜ao ´e falsa, pois pelo princ´ıpio de inclus˜ao e exclus˜ao, n(A∪B) = n(A)+n(B)−n(A∩B), implicando em n(B) = 8, para n(A∪B) =
15, n(A) = 9, n(A ∩ B) = 2.
Portanto, a afirma¸c˜ao correta ´e:
Se n(A ∪ B) = 15, n(A) = 9, n(A ∩ B) = 2 ent˜ao n(B) = 8.
2. (2.0) Mostre usando Indu¸c˜ao Matem´atica:
Pn
i=1
1
2i = 1 − 1
2n para todo n inteiro natural.
1
Prova:
Seja P(n) : Pn i=1 1
2i = 1 − 1
2n
Base da indu¸c˜ao:
Para n = 1, 1
21 = 1
2 = 1 − 1
2 = 1 − 1
21 , logo P(1) ´e verdadeiro.
Hip´otese de Indu¸c˜ao:
Suponha verdadeiro para n = k, isto ´e, P(k) ´e verdadeiro:
P(k) : Pk i=1 1
2i = 1 − 1
2k
Vamos mostrar que se P(k) ´e verdadeiro ent˜ao P(k + 1) ´e verdadeiro, isto ´e:
Temos que provar que: P(k + 1) : Pk+1 i=1 1
2i = 1 − 1
2k+1 ´e verdadeiro.
Desenvolvendo para n = k + 1 e usando a hip´otese de indu¸c˜ao, temos que:
Pk+1
i=1
1
2i =
= (
1
21 +
1
22 + . . . +
1
2k )
| {z } (Por hip´otese indutiva)
+ 1
2k+1 =
= 1 − 1
2k + 1