CEDERJ Computação -

Curso de Tecnologia em Sistemas de Computação

Disciplina: Fundamentos de Algoritmos para Computação

Professoras: Susana Makler e Sulamita Klein Gabarito AD1 - Segundo Semestre de 2012

Questões:

1. (1.5) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira. Se for verdadeira, prove, se for falsa justifique.

1. A − (B − C) = (A − B) − C;

Resposta: Falsa. Sejam A,B e C conjuntos não vazios tais que

1. ∩ C 6= ∅, A ∩ B = ∅ e B ∩ C = ∅. A − (B − C) = A − B = A

enquanto que

(A − B) − C = A − C 6= A, pois A ∩ C =6 ∅.

Logo, a afirmação é falsa.

1. (A ∩ B) − C = (A ∩ B)∆(A ∩ C).

Lembre que: X∆Y = (X − Y ) ∪ (Y − X).

Resposta: Falsa. Inicialmente vamos reescrever a afirmação sabendo que X∆Y = (X − Y ) ∪ (Y − X).

1. ∩ B) − C = (A ∩ B)∆(A ∩ C)

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

Sejam A,B e C conjuntos distintos não vazios tais que A∩B∩C 6=

∅, A ∩ B 6= ∅, A ∩ C 6= ∅ e B ∩ C =6 ∅.

Observem os diagramas de Venn da Figura 1 ilustram a situação e provam que (A∩B)−C 6= ((A∩B)−(A∩C))∪((A∩C)−(A∩B)).

1. (1.5) Dentre os números de 1 a 1000, inclusive, quantos são divisíveis por 2 ou 5 ou 12? Justifique.

Sugestão: Use o Princípio da Inclusão e Exclusão.

Resposta: Considere os conjuntos:

[pic 2][pic 1]

[pic 4][pic 3]

Figura 1: O diangrama de Venn da esquerda ilustra a expressão (A∩B)−C, enquanto o diagrama da direita ilustra a expressão ((A ∩ B) − (A ∩ C)) ∪ ((A ∩ C) − (A ∩ B)).

U = {x ∈N| 1 ≤ x ≤ 1000};

1. = {x ∈ U| x é divisível por 2} = {x ∈ U| x = 2n,n ∈N};
2. = {x ∈ U| x é divisível por 5} = {x ∈ U| x = 5m,m ∈N} C = {x ∈ U| x é divisível por 12} = x ∈ U| x = 12p,p ∈N}.

Pelo Princípio da Inclusão e Exclusão temos:

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

C) + n(A ∩ B ∩ C)

1. = {2 × 1,2 × 2,2 × 3,···,2 × 500} = {2,4,6,···,1000} n(A) = 500
2. = {5 × 1,5 × 2,5 × 3,···,5 × 200} = {5,10,15,···,1000} n(B) = 200
3. = {12 × 1,12 × 2,12 × 3,···,12 × 83} = {12,24,36,···,996} n(C) = 83

(A ∩ B) = {x ∈ U| x é divisível por 10} = {x ∈ U| x = 10k,k ∈N} =

{10 × 1,10 × 2,10 × 3,···,10 × 100} = {10,20,30,···,1000}

n(A ∩ B) = 100

1. ∩ C) = {x ∈ U| x é divisível por 12} = C n(A ∩ C) = 83
2. ∩ C) = {x ∈ U| x é divisível por 60} = {x ∈ U| x = 60j,j ∈N} =

{60 × 1,60 × 2,60 × 3,···,60 × 16} = {60,120,180,···,960} n(B ∩ C) = 16

(A ∩ B ∩ C) = {x ∈ U| x é divisível por 60} = (B ∩ C) n(A ∩ B ∩ C) = 16

Daí, temos:

n(A ∪ B ∪ C) = 500 + 200 + 83 − 100 − 83 − 16 + 16 = 600

Logo, temos 600 números inteiros entre 1 e 1000 que são divisíveis por 2,5 ou 12.

...