mat_discreta_ap

Prévia do material em texto

Universidade Estadual de Mato Grosso
Campus de Ca´ceres
Departamento de Matema´tica
Bacharelado em Computac¸a˜o
Matemática Discreta
Computac¸a˜o
Apostila
Docente: Michael K. V. Gondim
Cáceres
2015
1
Conteúdo
1 Indução 3
1.1 Elemento mínimo e PBO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Indução matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Outras formas de indução matemática . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Conjuntos 7
2.1 Conjunto universo e vazio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Conjunto unitário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Relação de Inclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Conjunto das Partes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.5 Diagrama de Venn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.6 Operação entre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.6.1 Reunião . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.6.2 Interseção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.6.3 Diferença e complementar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.7 Simplificação de expressões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.7.1 Produto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.8 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2
1 Indução
1.1 Elemento mínimo e PBO
O princípio da indução matemática é uma técnica para lidar com tipos de dados que têm uma
relação de boa-ordem. Para isso, definiremos o elemento mínimo de um conjunto e logo em seguida,
introduziremos o método de recorrência ou indução matemática.
Definição 1.1. Seja A um conjunto de inteiros. Chama-se elemento mínimo de A um elemento a ∈ A tal
que a ≤ x para todo x ∈ A.
Simbolicamente, temos:
min A = a ⇔ a ∈ A e ∀x ∈ A, a ≤ x
Princípio da Boa Ordem: Todo subconjunto não-vazio de inteiros positivos contém um
elemento mínimo.
1.2 Indução matemática
Teorema 1.1. Seja P(n) uma proposição associada a cada inteiro positivo n e que satisfaz às duas seguintes
condições:
1. P(1) é verdadeira;
2. para todo inteiro positivo k, se P(k) é verdadeira, então P(k + 1) é verdadeira.
Nestas condições, a proposição P(n) é verdadeira para todo inteiro positivo n.
1.2.1 Exemplos
Exemplo 1.1. Demonstrar a proposição:
P(n) : 1 + 3 + 5 + . . . + (2n − 1) = n2, ∀n ∈N
Demonstração. Temos que
(1) P(1) é verdadeira, visto que 1 = 12.
(2) A hipótese de indução é que a proposição:
P(k) : 1 + 3 + 5 + . . . + (2k − 1) = k2, k ∈N
é verdadeira. Queremos mostrar que
1 + 3 + 5 + . . . + (2k − 1) + (2k + 1) = (k + 1)2.
Vamos então, adicionar 2k + 1 em ambos os membros da nossa hipótese de indução, assim
1 + 3 + 5 + . . . + (2k − 1) + (2k + 1) = k2 + 2k + 1
= (k + 1)2
e isto significa que a proposição P(k+1) é verdadeira. Logo, pelo Teorema da indução matemática
1.1, a proposição P(n) é verdadeira para todo inteiro positivo n. �
3
Exemplo 1.2. Demonstrar a proposição:
P(n) :
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + . . . +
1
n(n + 1)
=
n
n + 1
, ∀n ∈N
Demonstração. Temos que
(1) P(1) é verdadeira, visto que
1
1 · 2 =
1
1 + 1
.
(2) A hipótese de indução é que a proposição:
P(k) :
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + . . . +
1
k(k + 1)
=
k
k + 1
, k ∈N
é verdadeira. Queremos mostrar que
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + . . . +
1
k(k + 1)
+
1
(k + 1)(k + 2)
=
k + 1
k + 2
.
Vamos então, adicionar
1
(k + 1)(k + 2)
em ambos os membros da nossa hipótese de indução,
assim
1
1 · 2 +
1
2 · 3 +
1
3 · 4 + . . . +
1
k(k + 1)
+
1
(k + 1)(k + 2)
=
k
k + 1
+
1
(k + 1)(k + 2)
=
k(k + 2) + 1
(k + 1)(k + 2)
=
k2 + 2k + 1
(k + 1)(k + 2)
e isto significa que a proposição P(k+1) é verdadeira. Logo, pelo Teorema da indução matemática
1.1, a proposição P(n) é verdadeira para todo inteiro positivo n. �
Exemplo 1.3. Demonstrar a proposição:
P(n) : 3 | (22n − 1), ∀n ∈N
Demonstração. Temos que
(1) P(1) é verdadeira, visto que 3 | (22 − 1).
(2) A hipótese de indução é que a proposição:
P(k) : 3 | (22k − 1), k ∈N
é verdadeira. Portanto, das propriedades de divisibilidade, temos:
22k − 1 = 3q, com q ∈ Z
Queremos mostrar que
3 | (22(k+1) − 1).
4
Então, temos que
22(k+1) − 1 = 22 · 22k − 1
= 4 · 22k − 1
= 4 · 22k − 4 + 4 − 1
= (4 · 22k − 4) + (4 − 1)
= 4(22k − 1) + 3
= 4 · 3q + 3
= 3(4q + 1)
e isto significa que a proposição P(k+1) é verdadeira. Logo, pelo Teorema da indução matemática
1.1, a proposição P(n) é verdadeira para todo inteiro positivo n. �
Exemplo 1.4. Demonstrar a proposição:
P(n) : 2n > n, ∀n ∈N
Demonstração. Temos que
(1) P(1) é verdadeira, visto que 21 = 2 > 1.
(2) A hipótese de indução é que a proposição:
P(k) : 2k > k, k ∈N
é verdadeira. Queremos mostrar que
2(k + 1) > k + 1.
Vamos então, multiplicar por 2 em ambos os membros da nossa hipótese de indução, assim
2 · 2k > 2k
2k+1 > k + k (OBS: k + k ≥ k + 1)
2k+1 > k + 1
e isto significa que a proposição P(k+1) é verdadeira. Logo, pelo Teorema da indução matemática
1.1, a proposição P(n) é verdadeira para todo inteiro positivo n. �
1.3 Outras formas de indução matemática
Teorema 1.2. Seja r um inteiro positivo fixo e seja P(n) uma proposição associada a cada inteiro n ≥ r e
que satisfaz às duas seguintes condições:
1. P(r) é verdadeira;
2. para todo inteiro positivo k ≥ r, se P(k) é verdadeira, então P(k + 1) é verdadeira.
Nestas condições, a proposição P(n) é verdadeira para todo inteiro n ≥ r.
1.3.1 Exemplos
Exemplo 1.5. Demonstrar a proposição:
P(n) : 2n < n!, ∀n ≥ 4
Exemplo 1.6. Demonstrar a proposição:
P(n) : n2 > 2n1, ∀n ≥ 3
5
1.4 Exercícios
1. Demonstrar por “indução matemática”:
(a) 12 + 22 + 32 + . . . + n2 =
n
6
(n + 1)(2n + 1), ∀n ∈N
(b) 13 + 23 + 33 + . . . + n3 =
n2
4
(n + 1)2, ∀n ∈N
(c) 12 + 32 + 52 + . . . + (2n − 1)2 = n
3
(4n2 − 1), ∀n ∈N
(d) 13 + 33 + 53 + . . . + (2n − 1)3 = n
3
(n + 1)(n + 2), ∀n ∈N
(e) 1 +
1
4
+
1
9
+ . . . +
1
n2
≤ 2 − 1
n
, ∀n ∈N
(f) a + aq + aq2 + . . . + aqn =
a(qn−1 − 1
q − 1 , (q , 1) ∀n ∈N
2. Demonstrar por “indução matemática”:
(a) 2n < 2n+1, ∀n ∈N
(b) 2n > n2, ∀n ≥ 5
(c) 2n > n3, ∀n ≥ 10
(d) 4n > n4, ∀n ≥ 5
(e) n! > n2, ∀n ≥ 4
(f) n! > n3, ∀n ≥ 6
3. Demonstrar por “indução matemática”:
(a) 2 | (3n − 1) ∀n ∈N
(b) 6 | (n3 − 3n), ∀n ≥ 5
(c) 5 | (8n − 1), ∀n ≥ 10
(d) 24 | (52n − 1), ∀n ≥ 5
(e) 7 | (23n − 1), ∀n ≥ 4
(f) 8 | (32n + 7), ∀n ≥ 6
4. Demonstrar que 10n+1 − 9n − 10 é um múltiplo de 81 para todo inteiro positivo n.
5. Demonstrar que
n3
3
+
n5
5
+
7n
15
é um inteiro positivo para todo n ∈N.
6
2 Conjuntos
A noção matemática de conjunto é praticamente a mesma que se usa na linguagem comum;
é o mesmo que agrupamento, classe, coleção, sistema.
De acordo com (Lima, 2013): Um conjunto (ou coleção) é formado de objetos, chamados os
seus elementos. A relação básica entre um objeto e um conjunto é a relação de pertinência:
x ∈ A (x pertence a A)
x < A (x não pertence a A)
Os principais conjuntos numéricos são:
1. O conjunto dos números naturais: N = {1, 2, 3, . . .}2. O conjunto dos números inteiros: Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}
3. O conjunto dos números racionais: Q = {pq ; p, q ∈ Z e q , 0}
4. O conjunto dos números reais: R
5. O conjunto dos números complexos: C = {a + bi; a, b ∈ R e i2 = −1}
Os conjuntos serão representados por letras maiúsculas; A, B, C, X, etc. Os elementos de um
conjunto serão representados por letras minúsculas: a, b, x, y, etc.
Existem essencialmente duas maneiras de especificar um conjunto particular. Listando seus
elementos ou enunciando propriedades que caracterizam seus elementos.
Exemplo 2.1. Vejamos o conjunto das vogais V que pode ser definido com todos os seus elementos
V = {a, e, i, o,u}
ou usando uma propriedade
V = {x; x é uma vogal}
2.1 Conjunto universo e vazio
Dois conjuntos especiais são o conjunto universo, isto é, o conjunto de todos os objetos em
questão, e o conjunto vazio, isto é, o conjunto que não contém nenhum elemento. Os conjuntos
universo e vazio são denotados, respectivamente, por U e ∅.
2.2 Conjunto unitário
Em álgebra de conjuntos, os objetos de interesse são os conjuntos e não os elementos que
pertencem a eles. Assim, as operações devem ser definidas sobre ou entre conjuntos, mas nunca
sobre elementos isolados. Para tratar elementos, devemos considerar conjuntos unitários. Por
exemplo, se a é um elemento de U então {a} denota o conjunto unitário que contém apenas um
único elemento, o elemento a.
2.3 Relação de Inclusão
Um conjunto A é igual a um conjunto B, denotado A = B, se eles contêm exatamente os
mesmos elementos. Caso contrário, eles são diferentes e denotamos por A , B.
Um conjunto A está contido num conjunto B se todos os elementos de A pertencem também
ao conjunto B. Escrevemos A ⊂ B e dizemos que A é um subconjunto de B. Se, além disso, B
possui pelo menos um elemento que não pertence a A, então dizemos que A está propriamente
contido em B, ou que A é um subconjunto próprio de B, e denotamos A ( B.
A relação de inclusão de conjuntos ⊂ obedece às seguintes propriedades. Para quaisquer X,
Y e Z,
7
I1. (reflexiva) X ⊂ X
I2. (transitiva) X ⊂ Y e Y ⊂ Z ⇒ X ⊂ Z
I3. (anti-simétrica) X ⊂ Y e Y ⊂ X ⇒ X = Y
I4. ∅ ⊂ X e X ⊂ U
A propriedade anti-simétrica será muito usada nas demonstrações!
Observação 2.1. Escrevemos A ( B para representar que A é subconjunto de B, mas não é igual a B.
Quando fazemos A ⊂ B, temos que A é subconjunto de B, mas nada impede que eles sejam igual.
2.4 Conjunto das Partes
Dado um conjunto X, indica-se com 𝒫(X) o conjunto cujos elementos são as partes de X.
Exemplo 2.2. Seja A = {a, b, c}. Liste todos os elementos de 𝒫(A).
Exemplo 2.3. Mostre que se A contém n elementos então 𝒫(A) contém 2n elementos.
2.5 Diagrama de Venn
Os diagramas de Venn são úteis para reforçar a noção intuitiva sobre conjuntos, principalmente
para analisar relações entre os conjuntos e também seus membros. Para demonstrar propriedades
dos conjuntos, uma prova estritamente algébrica seria necessária. No entanto, para entender
uma propriedade e, mais do que isso, para nos convencermos de sua validade, os diagramas de
Venn são bastante uteis.
No diagrama de Venn o conjunto universo é representado por um retângulo, mais precisa-
mente, pelos pontos interiores ao retângulo. Qualquer conjunto é desenhado como sendo uma
curva fechada, inteiramente contida no retângulo. Pontos interiores à curva correspondem aos
elementos do conjunto. No exemplo das figuras, a união e interseção de dois conjuntos genéricos
estão representadas pelas regiões hachuradas da figura 1 e 2, respectivamente. O complemento
de um conjunto é representado no diagrama da figura 3.
Figura 1: União
Figura 2: Interseção Figura 3: Complementar
As propriedades que veremos podem ser entendidas com o auxílio de diagramas de Venn.
2.6 Operação entre conjuntos
2.6.1 Reunião
A reunião dos conjuntos A e B é o conjunto A ∪ B, formado pelos elementos de A mais os
elementos de B. Então, se x ∈ A ∪ B significa que x ∈ A ou x ∈ B.
A ∪ B = {x; x ∈ A ou x ∈ B}
Sejam quais forem os conjuntos A e B, tem-se
A ⊂ A ∪ B e B ⊂ A ∪ B
8
2.6.2 Interseção
A interseção dos conjuntos A e B é o conjunto A ∩ B, formado pelos elementos comuns a A e
B. Assim, se x ∈ A ∩ B significa que x ∈ A e x ∈ B.
A ∩ B = {x; x ∈ A e x ∈ B}
Quando A ∩ B = ∅, tem-se que A e B são conjuntos disjuntos.
Sejam quais forem os conjuntos A e B, tem-se
A ⊂ A ∪ B e B ⊂ A ∪ B
Propriedades da reunião e interseção
∪1. A ∪ ∅ = A
∪2. A ∪ A = A
∪3. A ∪ B = B ∪ A
∪4. (A ∪ B) ∪ C = A ∪ (B ∪ C)
∪5. A ∪ B = A ⇔ B ⊂ A
∪6. A ⊂ B,A′ ⊂ B′ ⇒ A ∪ A′ ⊂ B ∪ B′
∪7. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
∩1. A ∩ ∅ = ∅
∩2. A ∩ A = A
∩3. A ∩ B = B ∩ A
∩4. (A ∩ B) ∩ C = A ∩ (B ∩ C)
∩5. A ∩ B = A ⇔ A ⊂ B
∩6. A ⊂ B,A′ ⊂ B′ ⇒ A ∩ A′ ⊂ B ∩ B′
∩7. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Para provar as igualdades iremos usar a propriedade anti-simétrica da inclusão. Vamos
mostrar as cinco primeiras propriedades acima.
∪1. Demonstração. Vamos mostrar que A ∪ ∅ ⊂ A e depois mostraremos que A ⊂ A ∪ ∅. Bom,
dado x ∈ A ∪ ∅, temos que x ∈ A ou x ∈ ∅, mas como ∅ não possui elementos, deve que
x ∈ A. Logo, temos que A ∪ ∅ ⊂ A. Agora, dado x ∈ A, pela definição de reunião, temos
que x ∈ A ∪ ∅. Assim, A ⊂ A ∪ ∅. Pela relação de inclusão, segue que A ∪ ∅ = A. �
∪2. Demonstração. Usando a propriedade anti-simétrica da inclusão iremos mostrar que
A ∪A ⊂ A e A ⊂ A ∪A. No primeiro caso, consideremos x ∈ A ∪A, então temos que x ∈ A
ou x ∈ A, logo x ∈ A e, assim, A∪A ⊂ A. No segundo caso, tomemos x ∈ A, logo x ∈ A∪A
e assim, A ⊂ A ∪ A. Do que foi mostrado em ambos os casos, segue A ∪ A = A. �
∪3. Demonstração. Novamente fazendo o uso da anti-simetria da inclusão, iremos mostrar que
A ∪ B ⊂ B ∪ A e B ∪ A ⊂ A ∪ B. Então, dado x ∈ A ∪ B, temos que x ∈ A ou x ∈ B. Se x ∈ A,
então x ∈ B∪A, ou se x ∈ B, temos que x ∈ B∪A. Em ambos os casos, temos que x ∈ B∪A,
e assim segue que A∪ B ⊂ B∪A. Por outro lado, dado x ∈ B∪A, segue que x ∈ B ou x ∈ A.
Assim, x ∈ B, temos x ∈ A ∪ B ou se x ∈ A, temos que x ∈ A ∪ B e, em ambos os casos,
temos que x ∈ B ∪ A, logo B ∪ A ⊂ A ∪ B. Portanto, A ∪ B = B ∪ A. �
∪4. Demonstração. Vamos mostrar que (A ∪ B) ∪ C ⊂ A ∪ (B ∪ C) e A ∪ (B ∪ C) ⊂ (A ∪ B) ∪ C.
Então, dado x ∈ (A ∪ B) ∪ C, segue que x ∈ A ∪ B ou x ∈ C. Assim, se x ∈ A ∪ B, então
x ∈ A ou X ∈ B, o que resulta em x ∈ A ∪ (B ∪ C). Agora, se x ∈ C, então x ∈ B ∪ C, o
que implica em x ∈ A ∪ (B ∪ C). De ambos os casos, segue x ∈ A ∪ (B ∪ C). Como, dado
x ∈ (A ∪ B) ∪ C implica em x ∈ A ∪ (B ∪ C), segue que (A ∪ B) ∪ C ⊂ A ∪ (B ∪ C). Por outro
lado, dado x ∈ A ∪ (B ∪ C), temos que x ∈ A ou x ∈ B ∪ C. Se x ∈ A, temos que x ∈ A ∪ B,
e mais, x ∈ (A ∪ B) ∪ C. Agora, se x ∈ B ∪ C, então x ∈ B ou x ∈ C, assim se x ∈ B, temos
que x ∈ A ∪ B, o que implica x ∈ (A ∪ B) ∪ C, mas se x ∈ C, temos que x ∈ (A ∪ B) ∪ C. Em
qualquer caso, segue que x ∈ (A ∪ B) ∪ C. Mostramos então, que x ∈ A ∪ (B ∪ C) implica
x ∈ (A∪ B)∪C. Logo, A∪ (B∪C) ⊂ (A∪ B)∪C. Portanto, pela propriedade anti-simétrica
da inclusão, segue que (A ∪ B) ∪ C = A ∪ (B ∪ C). �
9
∪5. Demonstração. Temos que A ∪ B = A, ou seja, para todo x ∈ A ∪ B, implica que x ∈ A, em
particular, para todo x ∈ B, temos que x ∈ A ∪ B e, por hipótese, x ∈ A. Logo, para todo
x ∈ B implica que x ∈ A, portanto B ⊂ A. Por outro lado, se B ⊂ A, então dado x ∈ B, temos
que x ∈ A e assim x ∈ A ∪ B. Logo, A = A ∪ B. �
2.6.3 Diferença e complementar
A diferença entre os conjuntos A e B é o conjunto
A − B = {x; x ∈ A e x < B}.
Se A e B forem disjuntos então
A − B = A
e de um modo geral
A − B = A − (A ∩ B).
Quando se tem B ⊂ A, a diferença A − B chama-se o complementar de B em relação a A e
escreve-se
A − B = 𝒞AB
ou quando não houver dúvida sobre o conjunto “maior”, podemos simplesmente escrever
Bc
Observação 2.2. x ∈ Xc ⇔ x < X.
Teorema 2.1. A − B = A ∩ Bc.
Demonstração. Com efeito
x ∈ A − B⇔ x ∈ A e x < B
⇔ x ∈ A e x ∈ Bc
⇔ x ∈ A ∩ Bc.
�
Propriedades:
𝒞1 (Ac)c = A,
𝒞2 A ⊂ B ⇔ Bc ⊂ Ac,
𝒞3 A = ∅⇔ Ac = U,
𝒞4 (A ∪ B)c = Ac ∩ Bc,
𝒞5 (A ∩ B)c = Ac ∪ Bc.
Vamos demonstrar as duas primeiras propriedades.
𝒞1 Demonstração. Temos que x ∈ (Ac)c ⇔ x < Ac ⇔ x ∈ A. Logo, (Ac)c = A. �
𝒞2 Demonstração. Suponhamos A ⊂ B. Então um elemento x ∈ Bc não pode pertencer a B
e, com maior razão, não pode pertencerá a A. Logo x ∈ Bc ⇒ x ∈ Ac, ou seja, Bc ⊂ Ac.
Reciprocamente, se temos Bc ⊂ Ac então, pelo que acabamos de ver, deve ser (Ac)c ⊂ (Bc)c.
Usando a propriedade 𝒞1, obtemos A ⊂ B. �
10
2.7 Simplificação de expressões
As operações ∪, ∩ e 𝒞 podem ser utilizadas para combinar conjuntos de várias formas. A
combinação pode ser representada por uma expressão que descreve como os conjuntos foram
combinados. Assim como a combinação de conjuntos resulta em um conjunto, uma expressão
que descreve uma combinação de conjuntos representa um conjunto (aquele que resulta após as
combinações serem executadas).
Como vimos no caso de algumas propriedades, existem diferentes formas para se expressar
um mesmo conjunto. Por exemplo, vimos que X = X ∪ X. Ou ainda, (X ∪ Y)c = Xc ∩ Yc.
Assim sendo, surge a possibilidade de estudarmos diferentes formas de expressão de conjuntos.
Expressões podem ser expandidas, fatoradas ou simplificadas aplicando-se as leis fundamentais.
Exemplo 2.4. Mostramos a simplificação da expressão [(A ∩ B) ∪ (A ∩ Bc)] ∩ (Ac ∪ B).
Demonstração. Usando as propriedades temos:
[(A ∩ B) ∪ (A ∩ Bc)] ∩ (Ac ∪ B) = [A ∩ (B ∪ Bc)] ∩ (Ac ∪ B)
= (A ∩U) ∩ (Ac ∪ B)
= A ∩ (Ac ∪ B)
= (A ∪ Ac) ∪ (A ∩ B)
= ∅ ∪ (A ∩ B)
= A ∩ B
�
2.7.1 Produto cartesiano
O produto cartesiano dos conjuntos A e B é o conjunto de todos os pares ordenados (a, b) tais
que a primeira coordenada pertença ao conjunto A e a segunda, seja um elemento de B.
A × B = {(a, b); a ∈ A e b ∈ B}
onde, (a, b) = (x, y) ⇔ a = x e b = y. E ainda, quando A = B, temos A × A = A2.
11
2.8 Exercícios
1. Prove as propriedades da Reunião e Interseção que não foram mostradas acima (use o
diagrama de Venn como auxílio).
2. Mostre a validade das propriedades do complementar que não foram mostradas acima
(use o diagrama de Venn como auxílio).
3. Desenhe a relação X ⊂ Y num diagrama de Venn. Quais igualdades envolvendo os
conjuntos X e Y são verdadeiras quando X ⊂ Y? Liste pelo menos três.
4. Simplifique as seguintes expressões:
(a) (A ∩ Bc)c ∪ (B ∩ C)
(b) [(A ∪ B) ∩ (A ∪ Bc)] ∩ (A ∪ B)
(c) (A ∩ B ∩ C) ∪ (A ∩ B ∩ Cc) ∪ (Ac ∩ B ∩ Cc) ∪ (Ac ∩ Bc ∩ Cc)
(d) (A ∪ B) ∩ (A ∪ Bc) ∩ (Ac ∪ B)
5. Verifique se as igualdades são válidas. Justifique (pode ser via diagrama de Venn) ou
mostre um contra exemplo.
(a) (A ∩ B) ∪ B = B
(b) (A ∩ C) ∩ (B ∪ C) = A ∩ C
(c) Se A ∪ B = A ∪ C então B = C
(d) A ∩ (B ∪ C) = (A ∩ B) ∪ C
(e) A ∪ B = (Ac ∩ Bc)c
(f) (A ∪ Bc) ∩ (Ac ∪ B) ∩ (Ac ∪ Bc) = Ac ∪ Bc
(g) A ∩ (B − C) = (A ∩ B) − (A ∩ C)
(h) A ∩ B = A − (A − B)
(i) X − X = ∅
(j) X − ∅ = X
(k) ∅ − X = ∅
Referências
Lima, E. L. (2013). Curso de análise vol. 1, volume 1. Lima, Rio de Janeiro, 14th edition. ISBN
978-85-244-0118-3. 7
12
	Indução
	Elemento mínimo e PBO
	Indução matemática
	Exemplos
	Outras formas de indução matemática
	Exemplos
	Exercícios
	Conjuntos
	Conjunto universo e vazio
	Conjunto unitário
	Relação de Inclusão
	Conjunto das Partes
	Diagrama de Venn
	Operação entre conjuntos
	Reunião
	Interseção
	Diferença e complementar
	Simplificação de expressões
	Produto cartesiano
	Exercícios