AD1 FAC

Curso de Tecnologia em Sistemas de Computa¸ao c˜ Disciplina: Fundamentos de Algoritmos para Computa¸ao c˜ Professoras: Susana Makler e Sulamita Klein
Gabarito AD1 - Primeiro Semestre de 2013
Nome Assinatura -

Quest˜es: o 1. (1.5) Verifique se cada uma das afirma¸oes abaixo ´ falsa ou verdadeira. c˜ e
Se for verdadeira, prove, se for falsa justifique.
(i) {{∅}} ∈ D, onde D = {{∅}, ∅, X}
Resposta: Falsa, pois {{∅}} n˜o ´ elemento do conjunto D. Seria a e correto afirmar que {∅} ∈ D ou {{∅}} ⊆ D.
(ii) {{∅}} ⊆ P (D), onde D est´ definido no item (i). a Resposta: Verdadeira, pois {∅} ´ elemento de P (D). e P (D) = {∅; {{∅}}; {∅}; {X}; {{∅}, ∅}; {{∅}, X}; {∅, X}, {{∅}, ∅, X}}.
(iii) (A − B) − C ⊆ A − (B − C), sendo A, B e C conjuntos arbitr´rios. a Resposta: Verdadeira.
Se (A−B)−C = ∅, a continˆncia ´ trivialmente v´lida. Considere e e a agora o caso (A−B)−C = ∅, isto ´, existe x ∈ (A−B)−C. Neste e caso, sabemos que x ∈ A mas x ∈ B e x ∈ C. Logo, x ∈ (B − C)
/
/
/
(pois, se x ∈ (B − C), deve ser x ∈ B que ´ falso) . E, portanto, e x ∈ A − (B − C). Como x ´ arbitr´rio, mostramos que todo e a elemento de (A − B) − C ´ tamb´m elemento de A − (B − C), o e e que conclui a prova.
Observe o seguinte diagrama de Venn que ilustra a prova:
2. (1.5) Usando o Princ´ ıpio de Inclus˜o e Exclus˜o, determine o n´mero a a u o de permuta¸˜es de (1, 2, 3, 4, 5, 6, 7) nas quais nem o 3 ocupa o 3 lugar co nem o 5 ocupa o 5◦ lugar.
1

A

B
(A-B)

A

B

(A-B)-C

A

C
A

B

C
B

A

(B-C)

B

A-(B-C)

C

C

C

Figura 1: Diagrama de Venn que ilustra a prova de (A−B)−C ⊆ A−(B−C), sendo A, B e C conjuntos arbitr´rios. Note que o conjunto cinza claro est´ a a contido no conjunto cinza escuro, como gostar´ ıamos. Resposta:
Considere os conjuntos:
U = conjunto das permuta¸˜es de (1, 2, 3, 4, 5, 6, 7); co A = conjunto das permuta¸˜es de (1, 2, 3, 4, 5, 6, 7) onde o n´mero 3 co u o ocupa o 3 lugar, e