Curso de Tecnologia em Sistemas de Computação
Disciplina Fundamentos de Algoritmos para Computação
Gabarito da AP1 - Primeiro Semestre de 2010
Questões:
1. (2.0) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira.
Se for verdadeira, prove, se for falsa justifique.
(a) ∅ = {∅}
Resposta: FALSO. Dois conjuntos são iguais se todo elemento de um conjunto é elemento do outro conjunto e vice-versa.
O conjunto ∅ não tem elementos enquanto {∅} tem um elemento,
∅ ∈ {∅}. Logo, ∅ = {∅}.
(b) (A ∩ B ) ∪ C = (A ∪ C ) ∩ B
Resposta: FALSO. Contra-exemplo: Sejam os conjuntos A =
{1, 2, 3}, B = {3, 4, 5} e C = {1, 3, 5}.
Temos que (A ∩ B ) = {3}, (A ∩ B ) ∪ C = {1, 3, 5}, (A ∪ C ) =
{1, 2, 3, 5} e (A ∪ C ) ∩ B = {3, 5}.
Podemos concluir que (A ∩ B ) ∪ C = (A ∪ C ) ∩ B .
(c) n((A ∪ B ) ∩ C ) ≤ n(A ∩ C ) + n(B ∩ C )
Resposta: VERDADEIRO. Pela propriedade distributiva, temos que (A ∪ B ) ∩ C = (A ∩ C ) ∪ (B ∩ C ), e isto implica em dizer que n((A ∪ B ) ∩ C ) = n((A ∩ C ) ∪ (B ∩ C )).
Portanto,

n((A ∪ B ) ∩ C )
= n((A ∩ C ) ∪ (B ∩ C ))
= n(A ∩ C ) + n(B ∩ C )−n((A ∩ C ) ∩ (B ∩ C ))
= n(A ∩ C ) + n(B ∩ C ) −n(A ∩ B ∩ C )

=
=
=
=

´
E negativo

≤ n(A ∩ C ) + n(B ∩ C )
2. (2.0) Mostre por indução matemática que:
23n − 1 é divisível por 7 para todo natural n ≥ 1.
Resposta: Seja P (n) : 23n − 1 divisível por 7 , para todo n ∈ N.
Base da indução:
Para n = 1, temos que 23.1 − 1 = 7, que é divisível por 7, portanto P(1) é verdadeira.
Hipótese de