L1_conjuntos

Prévia do material em texto

Lista 1 Conjuntos Discreta - 2022.2 - FJG
1. Considere o conjunto A = {1, 2, 3} e determine a veracidade das seguintes proposições:
i) 3 ∈ A ii) {1, 2} ∈ A iii) 1 ⊂ A
iv) {3} ⊂ A v) (3 ∈ A) ∨ (4 ∈ A) vi) {3} ∪ {2} = {1}
vii) ∅ ∈ A viii) ∅ ⊂ A ix) 2 ∈ A ∨ {3} ∈ A
2. Prove a seguinte igualdade,
(A4B)4 C = {(A ∪B ∪ C)− [(A ∩B) ∪ (A ∩ C) ∪ (B ∩ C)]} ∪ (A ∩B ∩ C).
Deduça que a ordem na qual se escrevem A,B,C, assim como a ubicação dos paréntesis no termo
à esquerda resultam irrelevantes.
3. Principio de "Inclusão-exclusão".
A1 ∪A2 ∪A3 = (A1 ∩ (A2 ∪A3) ) t (A2 ∩ (A3 ∪A1) ) t (A3 ∩ (A2 ∪A1) )t
(A1 ∩A2 ∩A3) t (A2 ∩A3 ∩A1) t (A3 ∩A1 ∩A2)t
(A1 ∩A2 ∩A3).
(a) Prove.
(b) Interprete, ou seja, enuncie com palavras.
(c) Generalize para n conjuntos.
4. Determine a veracidade das seguintes proposições para A,B,C subconjuntos de un conjunto de
referência U . Se verdadeiro, prove, se falso dê um contra-exemplo.
a) A4B ⊂ (A4 C) ∪ (B 4 C) e) A− (B − C) = (A−B) ∪ C
b) A4B = ∅ ⇐⇒ A = B f) A = ∅
c) A ⊂ B ⇐⇒ A ⊃ B g) (A4B)4B = A
d) A ⊂ B → A4B = B ∩A h) (A ∩B)× C = (A× C) ∩ (B × C)
5. Sejam A,B,C conjuntos, f : B → C e g : A → B funções. Determine a veracidade das seguintes
proposições, se verdadeiro prove, se falso dê um contra-exemplo.
(a) se f e g são injetivas então f ◦ g é injetiva
(b) se f ◦ g é sobrejetiva então f é sobrejetiva.
(c) se f ◦ g é sobrejetiva então g é sobrejetiva.
(d) se f ◦ g é injetiva então g é injetiva.
(e) se f ◦ g é injetiva então f é injetiva.
(f) se f e g são injetivas então f ◦ g é injetiva
(g) se f e g são sobrejetivas então f ◦ g é sobrejetiva
(h) se f e g são bijetivas então f ◦ g é bijetiva.
6. Defina funções f, g : N → N tais que a composta f ◦ g seja a identidade, IdN, mas g ◦ f 6= IdN.
7. Sejam A, B, conjuntos finitos. Prove que se f : A → B e g : B → A são funções injetivas então
f e g são de fato bijetivas.
1
Lista 1 Conjuntos Discreta - 2022.2 - FJG
8. Considere S7 o conjunto de sequências de 7 bits, bi = 0 ou 1,
b1b2b3b4b5b6b7 ∈ S7.,
Definimos as seguintes funções de B em B.
• O shift right, R, é a função que deleta o ultimo bit b7, e adiciona um 0 a esquerda,i.e.,
R(b1b2b3b4b5b6b7) = 0b1b2b3b4b5b6.
• Analogamente, o shift left, L, é a função que deleta o primeiro bit b1, e adiciona um 0 a
direita.
• Dado p = p1p2p3p4p5p6p7 um elemento fixo definimos a função AND-p, de modo que Ap(x)
escreve o mínimo dígito a digito entre p e x.
Ap(x) = b1b2b3b4b5b6b7, com bi = min{pi, xi}.
• A função OR-p, Op, que escreve o máximo valor entre os dígitos de p e x.
• A função XOR-p, Xp, onde Xp(x) = b1b2b3b4b5b6b7, e bi = pi + xi com a convenção de que
2 = 0. Por exemplo:
X0011001(1111111) = 1100110 ; X0101010(1101011) = 1000001.
(a) Compute as compostas: R ◦ L, L ◦R, Ap ◦Ap, Ap ◦Op, Op ◦Ap, Xp ◦Xp.
(b) Prove que apenas uma destas é bijetiva e dê a inversa.
(c) Desafio: faça o exercício em geral para sequências de "n-bits, com n fixo porém arbitrário.
Dica: opere com logica proposicional e as propriedades análogas às de conjuntos.
2