Teoria dos Conjuntos - Fundamentos Matemáticos da Informática

Prévia do material em texto

Sumário Conjuntos Operações Propriedades
Fundamentos Matemáticos da Informática
Teoria dos Conjuntos
UFPA
27 de julho de 2021
Sumário Conjuntos Operações Propriedades
Conjuntos
Definições
Subconjuntos
Operações
Diagramas de Venn
Propriedades
Definições
Uso de Identidades
Sumário Conjuntos Operações Propriedades
Conjuntos
Definição
Um conjunto é uma coleção de entidades (chamadas de membros
ou elementos do conjunto) que pode ser identificada
ou:
Coleção não-ordenada de objetos
• normalmente, todos os objetos em um conjunto gozam de
uma mesma propriedade em comum
Exemplo
Conjunto dos inteiros menores do que 4: A = {1, 2, 3}
Sumário Conjuntos Operações Propriedades
Exemplos de Conjuntos
• Conjunto dos livros da livraria da UFPA (conj. finito)
• Conjunto dos números naturais (infinito)
• Conjunto dos dinossauros vivos (conj. Vazio, { }, ∅)
• Conjunto S de 2 elementos onde um dos quais é o conjunto
das letras minúsculas do alfabeto e o outro é conjunto dos
d́ıgitos decimais:
• X = {a, b, c , d , . . . , y , z}
• Y = {0, 1, 2, . . . , 9}
• S = {X ,Y } = {{a, b, c , . . . , y , z}, {0, 1, 2, . . . , 9}}
Sumário Conjuntos Operações Propriedades
Denotação e Pertinência
• Usualmente, utilizam-se letras maiúsculas para denotar
conjuntos e minúsculas para denotar elementos do conjunto
• (Pertinência) O śımbolo ∈ denota que um elemento pertence
ao conjunto. Ex.: a ∈ A
Exemplo
Seja A = {violeta,mostarda, vermelho}, então
• mostarda ∈ A
• púrpura /∈ A
Sumário Conjuntos Operações Propriedades
Denotação e Pertinência
• Usualmente, utilizam-se letras maiúsculas para denotar
conjuntos e minúsculas para denotar elementos do conjunto
• (Pertinência) O śımbolo ∈ denota que um elemento pertence
ao conjunto. Ex.: a ∈ A
Exemplo
Seja A = {violeta,mostarda, vermelho}, então
• mostarda ∈ A
• púrpura /∈ A
Sumário Conjuntos Operações Propriedades
Caracteŕısticas dos Conjuntos
Ordem dos Elementos
A ordem em que os elementos são listados em um conjunto é
irrelevante
Exemplo:
{3, 2, 1} e {1, 3, 2} representam o mesmo conjunto
Repetição dos Elementos
A repetição dos elementos em um conjunto é irrelevante
Exemplo:
{1, 1, 1, 3, 2} é uma outra representação de {1, 2, 3}
Sumário Conjuntos Operações Propriedades
Caracteŕısticas dos Conjuntos
Ordem dos Elementos
A ordem em que os elementos são listados em um conjunto é
irrelevante
Exemplo:
{3, 2, 1} e {1, 3, 2} representam o mesmo conjunto
Repetição dos Elementos
A repetição dos elementos em um conjunto é irrelevante
Exemplo:
{1, 1, 1, 3, 2} é uma outra representação de {1, 2, 3}
Sumário Conjuntos Operações Propriedades
Representação de Conjuntos
Conjuntos Infinitos
Conjuntos infinitos podem ser definidos indicando-se um padrão
Exemplo
Seja S o conjunto de todos os inteiros pares positivos
Forma Corriqueira
{2, 4, 6, . . .}
Forma Recursiva
S também pode ser definido por
”recursão”:
1. 2 ∈ S
2. Se n ∈ S , então (n + 2) ∈ S
Forma mais clara (e mais segura)
Forma mais clara (e mais segura) de descrever o conjunto S :
S = {x |x é inteiro positivo par}
”S é o conjunto de todos os x tal que x é um inteiro positivo e par”
Sumário Conjuntos Operações Propriedades
Representação de Conjuntos
Conjuntos Infinitos
Conjuntos infinitos podem ser definidos indicando-se um padrão
Exemplo
Seja S o conjunto de todos os inteiros pares positivos
Forma Corriqueira
{2, 4, 6, . . .}
Forma Recursiva
S também pode ser definido por
”recursão”:
1. 2 ∈ S
2. Se n ∈ S , então (n + 2) ∈ S
Forma mais clara (e mais segura)
Forma mais clara (e mais segura) de descrever o conjunto S :
S = {x |x é inteiro positivo par}
”S é o conjunto de todos os x tal que x é um inteiro positivo e par”
Sumário Conjuntos Operações Propriedades
Representação de Conjuntos
Conjuntos Infinitos
Conjuntos infinitos podem ser definidos indicando-se um padrão
Exemplo
Seja S o conjunto de todos os inteiros pares positivos
Forma Corriqueira
{2, 4, 6, . . .}
Forma Recursiva
S também pode ser definido por
”recursão”:
1. 2 ∈ S
2. Se n ∈ S , então (n + 2) ∈ S
Forma mais clara (e mais segura)
Forma mais clara (e mais segura) de descrever o conjunto S :
S = {x |x é inteiro positivo par}
”S é o conjunto de todos os x tal que x é um inteiro positivo e par”
Sumário Conjuntos Operações Propriedades
Conjuntos Definidos por Propriedades
• A melhor maneira de definir um conjunto é especificando uma
propriedade que os elementos do conjunto têm em comum
• Usa-se um predicado P(x) para denotar uma propriedade P
referente a uma variável objeto x
• Notação para um conjunto S cujos elementos têm a
propriedade P
S = {x |P(x)}
• O que significa também
(∀x)[(x ∈ S → P(x)) ∧ (P(x)→ x ∈ S)]
Todos os Elementos de S têm a propriedade P e tudo que
tem a propriedade P pertence a S
Sumário Conjuntos Operações Propriedades
Conjuntos Definidos por Propriedades
• A melhor maneira de definir um conjunto é especificando uma
propriedade que os elementos do conjunto têm em comum
• Usa-se um predicado P(x) para denotar uma propriedade P
referente a uma variável objeto x
• Notação para um conjunto S cujos elementos têm a
propriedade P
S = {x |P(x)}
• O que significa também
(∀x)[(x ∈ S → P(x)) ∧ (P(x)→ x ∈ S)]
Todos os Elementos de S têm a propriedade P e tudo que
tem a propriedade P pertence a S
Sumário Conjuntos Operações Propriedades
Conjuntos Definidos por Propriedades
• A melhor maneira de definir um conjunto é especificando uma
propriedade que os elementos do conjunto têm em comum
• Usa-se um predicado P(x) para denotar uma propriedade P
referente a uma variável objeto x
• Notação para um conjunto S cujos elementos têm a
propriedade P
S = {x |P(x)}
• O que significa também
(∀x)[(x ∈ S → P(x)) ∧ (P(x)→ x ∈ S)]
Todos os Elementos de S têm a propriedade P e tudo que
tem a propriedade P pertence a S
Sumário Conjuntos Operações Propriedades
Conjuntos Definidos por Propriedades
• A melhor maneira de definir um conjunto é especificando uma
propriedade que os elementos do conjunto têm em comum
• Usa-se um predicado P(x) para denotar uma propriedade P
referente a uma variável objeto x
• Notação para um conjunto S cujos elementos têm a
propriedade P
S = {x |P(x)}
• O que significa também
(∀x)[(x ∈ S → P(x)) ∧ (P(x)→ x ∈ S)]
Todos os Elementos de S têm a propriedade P e tudo que
tem a propriedade P pertence a S
Sumário Conjuntos Operações Propriedades
Conjuntos Definidos por Propriedades
Exemplos
1. {x |x é um inteiro e 3 < x ≤ 7}
2. {x |x é um mês com exatamente 30 dias}
3. {x |x é a capital da França}
Exerćıcios
Descreva os seguintes conjuntos
1. {1, 4, 9, 16}
2. {cabelereiro, barbeiro, atendente}
3. {2, 3, 5, 7, 11, 13, 17, . . .}
Sumário Conjuntos Operações Propriedades
Conjuntos Definidos por Propriedades
Exemplos
1. {x |x é um inteiro e 3 < x ≤ 7}
2. {x |x é um mês com exatamente 30 dias}
3. {x |x é a capital da França}
Exerćıcios
Descreva os seguintes conjuntos
1. {1, 4, 9, 16}
2. {cabelereiro, barbeiro, atendente}
3. {2, 3, 5, 7, 11, 13, 17, . . .}
Sumário Conjuntos Operações Propriedades
Conjuntos Especiais
• N: Conjunto dos números naturais: {0, 1, 2, 3, . . .}
• Z: Conjunto dos números inteiros:
{. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}
• Q: Conjunto dos números racionais: {x |x = n/m,
n,m ∈ Z ∧m 6= 0}
• R: Conjunto dos números reais: {x |x é um número real }
• P: Conjunto dos números primos: {2, 3, 5, 7, 11, 13, 17, . . .}
• C: Conjunto dos números complexos: {a + bı|a, b ∈ R}
Sumário Conjuntos Operações Propriedades
Igualdade de conjuntos
Definição
Dois conjuntos A e B são ditos iguais se e somente se eles
possuem os mesmos elementos. Neste caso, escreve-se: A = B
A = B significa:
(∀x)[(x ∈ A→ x ∈ B) ∧ (x ∈ B → x ∈ A)]
Sumário Conjuntos Operações Propriedades
Subconjuntos
Definição
O conjunto A é dito um subconjuntode B se e somente se todo
elemento de A é também um elemento de B
• Isto é ∀x(x ∈ A→ x ∈ B)
• Diz-se que ”A está contido em B”e escreve-se A ⊆ B
• Se A não é um subconjunto de B, escreve-se A * B
• Se A é um subconjunto de B, mas queremos enfatizar que
A 6= B, escrevemos A ⊂ B e dizemos que A é um subconjunto
próprio de B
Como podemos definir A ⊂ B através de notação lógica ?
(∀x)(x ∈ A→ x ∈ B) ∧ (∃y)(y ∈ B ∧ ¬(y ∈ A))
Sumário Conjuntos Operações Propriedades
Subconjuntos
Definição
O conjunto A é dito um subconjunto de B se e somente se todo
elemento de A é também um elemento de B
• Isto é ∀x(x ∈ A→ x ∈ B)
• Diz-se que ”A está contido em B”e escreve-se A ⊆ B
• Se A não é um subconjunto de B, escreve-se A * B
• Se A é um subconjunto de B, mas queremos enfatizar que
A 6= B, escrevemos A ⊂ B e dizemos que A é um subconjunto
próprio de B
Como podemos definir A ⊂ B através de notação lógica ?
(∀x)(x ∈ A→ x ∈ B) ∧ (∃y)(y ∈ B ∧ ¬(y ∈ A))
Sumário Conjuntos Operações Propriedades
Exemplos de Subconjuntos
Sejam os conjuntos:
A = {1, 7, 9, 15}
B = {7, 9}
C = {7, 9, 15, 20}
Então as seguintes sentenças são verdadeiras:
B ⊆ C 15 ∈ C
B ⊆ A {7, 9} ⊆ B
B ⊂ A {7} ⊂ A
A * C ∅ ⊆ C
Sobre o Conjunto Vazio
O conjunto Vazio é um subconjunto de todo conjunto
Se x = ∅ então x ⊆ S
Sumário Conjuntos Operações Propriedades
Exemplos de Subconjuntos
Sejam os conjuntos:
A = {1, 7, 9, 15}
B = {7, 9}
C = {7, 9, 15, 20}
Então as seguintes sentenças são verdadeiras:
B ⊆ C 15 ∈ C
B ⊆ A {7, 9} ⊆ B
B ⊂ A {7} ⊂ A
A * C ∅ ⊆ C
Sobre o Conjunto Vazio
O conjunto Vazio é um subconjunto de todo conjunto
Se x = ∅ então x ⊆ S
Sumário Conjuntos Operações Propriedades
Exerćıcio
Sejam:
A = {x |x ∈ N e x ≥ 5}
B = {10, 12, 16, 20}
C = {x |(∃y)(y ∈ N e x = 2y)}
Quais das proposições a seguir são verdadeiras?
1. B ⊆ C
2. B ⊂ A
3. A ⊆ C
4. 26 ∈ C
5. {11, 12, 13} ⊆ A
6. {12} ∈ B
1. {12} ⊆ B
2. {11, 12, 13} ⊂ C
3. 12 ⊆ A
4. {∅} ⊆ B
Sumário Conjuntos Operações Propriedades
Conjuntos Membros de Outros Conjuntos
Conjuntos podem ter outros conjuntos como membros
Exemplo
A = {∅, {a}, {b}, {a, b}}
B = {x |x é um subconjunto do conjunto {a, b}}
Note que estes dois conjuntos são iguais
Sumário Conjuntos Operações Propriedades
Exerćıcio
Sejam os conjuntos: A = {1, 2, 3} e B = {{1}, 3, 5, 9}, verifique se
os seguintes exerćıcios são verdadeiros:
1. 1 ∈ B
2. {1} ⊆ B
3. 1 ⊆ A
4. {1} ⊆ A
5. ∅ ∈ A
Sumário Conjuntos Operações Propriedades
Exemplo de Subconjunto
• Suponha que B = {x |P(x)} e que A ⊆ B
• Para provar que A ⊆ B, tomamos um x ∈ A arbitrário e
mostramos que P(x) é verdadeira (os elementos de A
”herdam”a propriedade de B)
Exemplo
Seja B = {x |x é múltiplo de 4} e A = {x |x é múltiplo de 8}
Para mostrar que A ⊆ B tomamos um x ∈ A
x = m.8 para algum inteiro m então
x = m.2.4 ou x = k .4, onde k = 2m também é um inteiro
Isso mostra que x é múltiplo de 4 e, portanto, x ∈ B
Sumário Conjuntos Operações Propriedades
Exemplo de Subconjunto
• Suponha que B = {x |P(x)} e que A ⊆ B
• Para provar que A ⊆ B, tomamos um x ∈ A arbitrário e
mostramos que P(x) é verdadeira (os elementos de A
”herdam”a propriedade de B)
Exemplo
Seja B = {x |x é múltiplo de 4} e A = {x |x é múltiplo de 8}
Para mostrar que A ⊆ B tomamos um x ∈ A
x = m.8 para algum inteiro m então
x = m.2.4 ou x = k .4, onde k = 2m também é um inteiro
Isso mostra que x é múltiplo de 4 e, portanto, x ∈ B
Sumário Conjuntos Operações Propriedades
Igualdade de Conjuntos
A e B são iguais se e somente se contêm os mesmos elementos
Exemplo
Provar que {x |x ∈ N e (x2 < 15)} = {x |x ∈ N e (2x < 7)}
Podemos provar que A = B provando que:
A ⊆ B e B ⊆ A
Elementos de A: {0, 1, 2, 3} - todos com dobro < 7
Elementos de B: {0, 1, 2, 3} - todos com quadrado < 15
Sumário Conjuntos Operações Propriedades
Igualdade de Conjuntos
A e B são iguais se e somente se contêm os mesmos elementos
Exemplo
Provar que {x |x ∈ N e (x2 < 15)} = {x |x ∈ N e (2x < 7)}
Podemos provar que A = B provando que:
A ⊆ B e B ⊆ A
Elementos de A: {0, 1, 2, 3} - todos com dobro < 7
Elementos de B: {0, 1, 2, 3} - todos com quadrado < 15
Sumário Conjuntos Operações Propriedades
Conjunto potência (ou conjunto de partes)
Muitos problemas envolvem testar todas as combinações dos
elementos de um conjunto para ver se elas satisfazem alguma
propriedade
Exemplo
Seja A = {1, 2, 3}
Então P(A) consiste dos seguintes subconjuntos de A
P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
Conjunto Potência (de todas as partes de A)
Dado um conjunto A, o conjunto potência de A é o
conjunto formado por todos os subconjuntos de A
É denotado por P(A) ou 2A
NOTA: se A tem n elementos, P(A) tem 2n elementos
Sumário Conjuntos Operações Propriedades
Produto Cartesiano
Definição
Sejam A e B conjuntos. O produto cartesiano de A e B, denotado
por A× B, é o conjunto de todos os pares ordenados (a, b), onde
a ∈ A e b ∈ B.
A× B = {(a, b)|a ∈ A ∧ b ∈ B}
A ordem é importante em um par ordenado !
Exemplo
Qual é o produto de A = {1, 2} e B = {a, b, c}?
A× B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
Note que: B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c , 1), (c , 2)}
Sumário Conjuntos Operações Propriedades
Produto Cartesiano
Definição
Sejam A e B conjuntos. O produto cartesiano de A e B, denotado
por A× B, é o conjunto de todos os pares ordenados (a, b), onde
a ∈ A e b ∈ B.
A× B = {(a, b)|a ∈ A ∧ b ∈ B}
A ordem é importante em um par ordenado !
Exemplo
Qual é o produto de A = {1, 2} e B = {a, b, c}?
A× B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
Note que: B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c , 1), (c , 2)}
Sumário Conjuntos Operações Propriedades
Produto Cartesiano
Definição
Sejam A e B conjuntos. O produto cartesiano de A e B, denotado
por A× B, é o conjunto de todos os pares ordenados (a, b), onde
a ∈ A e b ∈ B.
A× B = {(a, b)|a ∈ A ∧ b ∈ B}
A ordem é importante em um par ordenado !
Exemplo
Qual é o produto de A = {1, 2} e B = {a, b, c}?
A× B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
Note que: B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c , 1), (c , 2)}
Sumário Conjuntos Operações Propriedades
Produto Cartesiano
Definição
Sejam A e B conjuntos. O produto cartesiano de A e B, denotado
por A× B, é o conjunto de todos os pares ordenados (a, b), onde
a ∈ A e b ∈ B.
A× B = {(a, b)|a ∈ A ∧ b ∈ B}
A ordem é importante em um par ordenado !
Exemplo
Qual é o produto de A = {1, 2} e B = {a, b, c}?
A× B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
Note que: B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c , 1), (c , 2)}
Sumário Conjuntos Operações Propriedades
Produto Cartesiano
Sejam os conjuntos A = {a, b} e B = {c , d}, encontre os seguintes
produtos cartesianos:
1. A× B
2. B × A
3. A2
4. B3
Sumário Conjuntos Operações Propriedades
Diagramas de Venn
A ⊆ B A * B
Conjunto Universo
Conjunto contendo todos os objetos em consideração
Sumário Conjuntos Operações Propriedades
Diagramas de Venn
A ⊆ B A * B
Conjunto Universo
Conjunto contendo todos os objetos em consideração
Sumário Conjuntos Operações Propriedades
União de Conjuntos
Definição
Se A e B são conjuntos, a união de A e B, denotada por A ∪ B, é
o conjunto que contém os elementos que estão em
A ou em B, ou em ambos.
A ∪ B = {x |(x ∈ A) ∨ (x ∈ B)}
A ∪ B =
Exemplo
A união dos conjuntos {1, 3, 5} e {1, 2, 3} é o conjunto {1, 2, 3, 5}
Sumário Conjuntos Operações Propriedades
União de Conjuntos
Definição
Se A e B são conjuntos, a união de A e B, denotada por A ∪ B, é
o conjunto que contém os elementos que estão em
A ou em B, ou em ambos.
A ∪ B = {x |(x ∈ A) ∨ (x ∈ B)}
A ∪ B =
Exemplo
A união dos conjuntos {1, 3, 5} e {1, 2, 3} é o conjunto {1, 2, 3, 5}
Sumário Conjuntos Operações Propriedades
Interseção de Conjuntos
DefiniçãoSe A e B são conjuntos, a interseção de A e B, denotada por
A ∩ B, é o conjunto que contém os elementos que estão tanto em
A como em B
A ∩ B = {x |(x ∈ A) ∧ (x ∈ B)}
A ∩ B =
Exemplo
A interseção dos conjuntos {1, 3, 5} e {1, 2, 3} é o conjunto {1, 3}
Sumário Conjuntos Operações Propriedades
Interseção de Conjuntos
Definição
Se A e B são conjuntos, a interseção de A e B, denotada por
A ∩ B, é o conjunto que contém os elementos que estão tanto em
A como em B
A ∩ B = {x |(x ∈ A) ∧ (x ∈ B)}
A ∩ B =
Exemplo
A interseção dos conjuntos {1, 3, 5} e {1, 2, 3} é o conjunto {1, 3}
Sumário Conjuntos Operações Propriedades
Diferença entre Dois Conjuntos
Definição
Se A e B são conjuntos, a diferença de A e B é o conjunto de
todos os elementos que estão em A mas não em B
A− B = {x |(x ∈ A) ∧ (x /∈ B)}
A− B =
Exemplo
A diferença dos conjuntos {1, 3, 5} e {1, 2, 3} é o conjunto {5}.
Sumário Conjuntos Operações Propriedades
Diferença entre Dois Conjuntos
Definição
Se A e B são conjuntos, a diferença de A e B é o conjunto de
todos os elementos que estão em A mas não em B
A− B = {x |(x ∈ A) ∧ (x /∈ B)}
A− B =
Exemplo
A diferença dos conjuntos {1, 3, 5} e {1, 2, 3} é o conjunto {5}.
Sumário Conjuntos Operações Propriedades
Diferença Simétrica
A⊕ B = (A− B) ∪ (B − A)
Ou
A4 B = (A− B) ∪ (B − A)
Exerćıcio
Desenhe o Diagrama de Venn para esta operação.
Sumário Conjuntos Operações Propriedades
Complemento de um Conjunto
Definição
Se U é o Conjunto Universo, U − A é chamado de o
Complemento de A e é denotado por A.
A = {x |x /∈ A} A =
Exemplo
Seja U o conjunto universo consistindo de todos os inteiros
positivos e seja A o conjunto dos inteiros positivos maiores do que
10, então
A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Sumário Conjuntos Operações Propriedades
Complemento de um Conjunto
Definição
Se U é o Conjunto Universo, U − A é chamado de o
Complemento de A e é denotado por A.
A = {x |x /∈ A} A =
Exemplo
Seja U o conjunto universo consistindo de todos os inteiros
positivos e seja A o conjunto dos inteiros positivos maiores do que
10, então
A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Sumário Conjuntos Operações Propriedades
Exerćıcio
Descreva cada um dos conjuntos a seguir listando seus elementos:
1. {x |x ∈ N e x2 < 25}
2. {x |x ∈ N e x é par e 2 < x < 11}
3. {x |x ∈ R e x2 = −1}
4. {x |x ∈ Z e |x | < 4}
Sumário Conjuntos Operações Propriedades
Exerćıcio
Sejam: A = {1, 2, 3, 5, 10}, B = {2, 4, 7, 8, 9}, C = {5, 8, 10}
subconjuntos de S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, encontre:
1. A ∪ B
2. A− C
3. B ∩ (A ∪ C )
Sumário Conjuntos Operações Propriedades
Propriedades dos Conjuntos
Comutatividade
• A ∪ B = B ∪ A
• A ∩ B = B ∩ A
Associatividade
• A ∪ (B ∪ C ) = (A ∪ B) ∪ C
• A ∩ (B ∩ C ) = (A ∩ B) ∩ C
Distributividade
• A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )
• A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
Sumário Conjuntos Operações Propriedades
Propriedades dos Conjuntos
Comutatividade
• A ∪ B = B ∪ A
• A ∩ B = B ∩ A
Associatividade
• A ∪ (B ∪ C ) = (A ∪ B) ∪ C
• A ∩ (B ∩ C ) = (A ∩ B) ∩ C
Distributividade
• A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )
• A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
Sumário Conjuntos Operações Propriedades
Propriedades dos Conjuntos
Comutatividade
• A ∪ B = B ∪ A
• A ∩ B = B ∩ A
Associatividade
• A ∪ (B ∪ C ) = (A ∪ B) ∪ C
• A ∩ (B ∩ C ) = (A ∩ B) ∩ C
Distributividade
• A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )
• A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
Sumário Conjuntos Operações Propriedades
Propriedades de Conjuntos
Idempotência
• A ∩ A = A
• A ∪ A = A
Complemento
• A = A
• A ∪ A = U
• A ∩ A = ∅
• ∅ = U e também U = ∅
• A ∪ B = A ∩ B (1a. Lei de De Morgan)
• A ∩ B = A ∪ B (2a. Lei de De Morgan)
Sumário Conjuntos Operações Propriedades
Propriedades de Conjuntos
Idempotência
• A ∩ A = A
• A ∪ A = A
Complemento
• A = A
• A ∪ A = U
• A ∩ A = ∅
• ∅ = U e também U = ∅
• A ∪ B = A ∩ B (1a. Lei de De Morgan)
• A ∩ B = A ∪ B (2a. Lei de De Morgan)
Sumário Conjuntos Operações Propriedades
Propriedades do Conjunto Universo (U) e Vazio (∅)
Propriedades do Conjunto Universo
A ∪ U = U
A ∩ U = A
Propriedades do Conjunto Vazio
A ∪ ∅ = A
A ∩ ∅ = ∅
Sumário Conjuntos Operações Propriedades
Uso das Identidades
Exemplo
Sejam A, B e C conjuntos. Mostre que A ∪ (B ∩ C ) = (C ∪B)∩A
Sumário Conjuntos Operações Propriedades
Exerćıcio
Sejam: A = {a, c , f , g}, B = {a, e}, C = {b, h}
subconjuntos de S = {a, b, c, d , e, f , g , h}, encontre:
1. A
2. B
3. A ∪ B
4. A ∩ B
5. S
6. A− B
7. A⊕ B
8. A ∪ A
Sumário Conjuntos Operações Propriedades
Exerćıcio
Sejam: A = {2, 4, 5, 6, 8}, B = {1, 4, 5, 9},
C = {x |x ∈ Z e 2 ≤ x < 5}
subconjuntos de S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, encontre:
1. A ∪ B
2. A ∩ B
3. A ∩ C
4. (A ∩ B)
5. (C ∩ B) ∪ A
6. (C ∪ B)
7. (B − A) ∩ (A− B)
8. B × C
Sumário Conjuntos Operações Propriedades
Cardinalidade de Conjuntos
Definição
Um conjunto A é dito finito se ele tem n elementos distintos, onde
n ∈ N
• n é chamado a Cardinalidade de A
• a Cardinalidade de A é denotada por |A|
Exemplos
1. Seja A o conjunto dos inteiros positivos ı́mpares menores do
que 10. Então |A| = 5
2. Seja A o conjunto das letras do alfabeto. Então |A| = 26
Sumário Conjuntos Operações Propriedades
Cardinalidade de Conjuntos
Definição
Um conjunto A é dito finito se ele tem n elementos distintos, onde
n ∈ N
• n é chamado a Cardinalidade de A
• a Cardinalidade de A é denotada por |A|
Exemplos
1. Seja A o conjunto dos inteiros positivos ı́mpares menores do
que 10. Então |A| = 5
2. Seja A o conjunto das letras do alfabeto. Então |A| = 26
Sumário Conjuntos Operações Propriedades
Prinćıpio da Adição
Definição
Se uma primeira tarefa pode ser feita de n1 modos e uma segunda
tarefa de n2 modos, e se ambos os eventos não podem ocorrer ao
mesmo tempo, então há n1 + n2 modos de fazer uma ou outra
tarefa
Se A e B são conjuntos disjuntos então |A ∪ B| = |A|+ |B|
Esta regra pode ser estendida para
|A1 ∪ A2 ∪ . . . ∪ Am| = |A1|+ |A2|+ . . . + |Am|
Sumário Conjuntos Operações Propriedades
Prinćıpio da Adição
Exerćıcio
Um consumidor deseja comprar um véıculo de uma concessionária.
A concessionária tem 23 automóveis e 14 caminhões em estoque.
Quantas escolhas posśıveis o consumidor tem ?
Sumário Conjuntos Operações Propriedades
Prinćıpio da Multiplicação
Definição
Suponha que um procedimento possa ser subdividido em duas
tarefas. Se há n1 modos de fazer a 1
a. tarefa e n2 modos de fazer
a segunda depois que a 1a. esteja pronta, então há n1.n2 modos de
executar o procedimento
Se A e B são conjuntos finitos então |A× B| = |A|.|B|
Esta regra pode ser estendida para
|A1 × A2 × . . .× Am| = |A1|.|A2|. . . . .|Am|
Sumário Conjuntos Operações Propriedades
Prinćıpio da Multiplicação
Definição
Suponha que um procedimento possa ser subdividido em duas
tarefas. Se há n1 modos de fazer a 1
a. tarefa e n2 modos de fazer
a segunda depois que a 1a. esteja pronta, então há n1.n2 modos de
executar o procedimento
Se A e B são conjuntos finitos então |A× B| = |A|.|B|
Esta regra pode ser estendida para
|A1 × A2 × . . .× Am| = |A1|.|A2|. . . . .|Am|
Sumário Conjuntos Operações Propriedades
Prinćıpio da Multiplicação
Exemplo 1
Uma criança pode escolher uma entre duas balas, uma rosa e uma
preta, e um entre três chicletes, um amarelo, um verde e um
branco. Quantos conjuntos diferentes a criança pode ter ?
Sumário Conjuntos Operações Propriedades
Prinćıpio da Multiplicação
Exemplo 2
A última parte de um número de telefone tem 4 d́ıgitos. Quantos
números de 4 d́ıgitos existem?
Exemplo 3
Quantos números de 4 d́ıgitos sem repetições de d́ıgitos existem?
Sumário Conjuntos Operações Propriedades
Prinćıpio da Multiplicação
Exemplo 2
A última parte de um número de telefone tem 4 d́ıgitos. Quantos
númerosde 4 d́ıgitos existem?
Exemplo 3
Quantos números de 4 d́ıgitos sem repetições de d́ıgitos existem?
Sumário Conjuntos Operações Propriedades
Prinćıpio da Inclusão e Exclusão
Exemplo
Sabe-se que em uma aula de uma certa disciplina da Computação
há 20 mulheres e 35 formandos. Quantos estudantes desta aula
são mulheres ou formandos?
Resposta:
• Provavelmente, a resposta correta não é ”adicionar a
quantidade de mulheres e formandos”
• Mulheres formandas seriam contadas duas vezes
• Logo, o número de mulheres ou formandos é a soma do
número de mulheres com o número de formandos menos o
número de mulheres formandas
Sumário Conjuntos Operações Propriedades
Prinćıpio da Inclusão e Exclusão
Exemplo
Sabe-se que em uma aula de uma certa disciplina da Computação
há 20 mulheres e 35 formandos. Quantos estudantes desta aula
são mulheres ou formandos?
Resposta:
• Provavelmente, a resposta correta não é ”adicionar a
quantidade de mulheres e formandos”
• Mulheres formandas seriam contadas duas vezes
• Logo, o número de mulheres ou formandos é a soma do
número de mulheres com o número de formandos menos o
número de mulheres formandas
Sumário Conjuntos Operações Propriedades
Prinćıpio da Inclusão e Exclusão
Exemplo
Sabe-se que em uma aula de uma certa disciplina da Computação
há 20 mulheres e 35 formandos. Quantos estudantes desta aula
são mulheres ou formandos?
Resposta:
• Provavelmente, a resposta correta não é ”adicionar a
quantidade de mulheres e formandos”
• Mulheres formandas seriam contadas duas vezes
• Logo, o número de mulheres ou formandos é a soma do
número de mulheres com o número de formandos menos o
número de mulheres formandas
Sumário Conjuntos Operações Propriedades
Prinćıpio da Inclusão e Exclusão
Definição
Se A e B são conjuntos finitos, então |A∪B| = |A|+ |B| − |A∩B|
Exemplo
Seja A = {a, b, c , d , e} e B = {c , e, f , h, k ,m}. Verifique a
igualdade acima.
Resposta:
A ∪ B = {a, b, c , d , e, f , h, k ,m} e A ∩ B = {c , e}
|A ∪ B| = 9, |A| = 5, |B| = 6, |A ∩ B| = 2
9 = 5 + 6− 2
Sumário Conjuntos Operações Propriedades
Prinćıpio da Inclusão e Exclusão
Definição
Se A e B são conjuntos finitos, então |A∪B| = |A|+ |B| − |A∩B|
Exemplo
Seja A = {a, b, c , d , e} e B = {c , e, f , h, k ,m}. Verifique a
igualdade acima.
Resposta:
A ∪ B = {a, b, c , d , e, f , h, k ,m} e A ∩ B = {c , e}
|A ∪ B| = 9, |A| = 5, |B| = 6, |A ∩ B| = 2
9 = 5 + 6− 2
Sumário Conjuntos Operações Propriedades
Prinćıpio da Inclusão e Exclusão
Exemplo
Uma companhia de computação deve contratar 25 programadores
para lidar com tarefas de programação de sistemas e 40
programadores para programação de aplicativos. Dos contratados,
10 terão que realizar tarefas de ambos os tipos. Quantos
programadores devem ser contratados?
Sumário Conjuntos Operações Propriedades
Prinćıpio da Inclusão e Exclusão
Exemplo
Suponha que haja 1.807 calouros de exatas na universidade.
Destes, 453 estão cursando Computação, 567 estão cursando
Engenharia Mecânica e 299 estão em ambos os cursos. Quantos
não estão cursando Computação nem Engenharia Mecânica?
Sumário Conjuntos Operações Propriedades
Prinćıpio da Inclusão e Exclusão
Definição
Se A, B e C são conjuntos finitos então
|A∪B∪C | = |A|+|B|+|C |−|A∩B|−|A∩C |−|B∩C |+|A∩B∩C |
Sumário Conjuntos Operações Propriedades
Prinćıpio da Inclusão e Exclusão
Exemplo
Uma quitanda vende apenas brócolis, cenoura e batata. Em
determinado dia, a quitanda atendeu 208 pessoas. Se 114
compraram brócolis, 152 compraram cenouras, 17 batatas, 64
brócolis e cenouras, 12 cenouras e batatas e 8 brócolis e batatas,
determine se alguém comprou os 3 produtos simultaneamente.
Sumário Conjuntos Operações Propriedades
Partições
A partição de um conjunto não vazio A é uma coleção P de
subconjuntos não vazios de A tal que:
1. Cada elemento de A pertence a um dos conjuntos em P
2. Se A1 e A2 são elementos distintos de P, então A1 ∩ A2 = ∅
Exemplo
Seja A = {a, b, c , d , e, f , g , h} e os seguintes subconjuntos de A.
Quais destes conjuntos formariam partições de A ?
A1 = {a, b, c , d} A2 = {a, c , e, f , g , h}
A3 = {a, c , e, g} A4 = {b, d}
A5 = {f , h}
P = {A3,A4,A5}
Sumário Conjuntos Operações Propriedades
Partições
A partição de um conjunto não vazio A é uma coleção P de
subconjuntos não vazios de A tal que:
1. Cada elemento de A pertence a um dos conjuntos em P
2. Se A1 e A2 são elementos distintos de P, então A1 ∩ A2 = ∅
Exemplo
Seja A = {a, b, c , d , e, f , g , h} e os seguintes subconjuntos de A.
Quais destes conjuntos formariam partições de A ?
A1 = {a, b, c , d} A2 = {a, c , e, f , g , h}
A3 = {a, c , e, g} A4 = {b, d}
A5 = {f , h}
P = {A3,A4,A5}
Sumário Conjuntos Operações Propriedades
Prinćıpio das Casas de Pombo
(Pigeonhole principle)
Prinćıpio das Casas de Pombo
Se mais de x itens são colocados em x caixas, então pelo menos
uma caixa contém mais de um item.
Exemplo 1:
Quantas pessoas têm que estar presentes em uma sala para
garantir que duas delas têm o último nome começando com a
mesma letra ?
Exemplo 2:
Quantas vezes é preciso jogar um dado para garantir que um
mesmo valor apareça duas vezes ?
Sumário Conjuntos Operações Propriedades
Prinćıpio das Casas de Pombo
(Pigeonhole principle)
Prinćıpio das Casas de Pombo
Se mais de x itens são colocados em x caixas, então pelo menos
uma caixa contém mais de um item.
Exemplo 1:
Quantas pessoas têm que estar presentes em uma sala para
garantir que duas delas têm o último nome começando com a
mesma letra ?
Exemplo 2:
Quantas vezes é preciso jogar um dado para garantir que um
mesmo valor apareça duas vezes ?
Sumário Conjuntos Operações Propriedades
Prinćıpio das Casas de Pombo
(Pigeonhole principle)
Prinćıpio das Casas de Pombo
Se mais de x itens são colocados em x caixas, então pelo menos
uma caixa contém mais de um item.
Exemplo 1:
Quantas pessoas têm que estar presentes em uma sala para
garantir que duas delas têm o último nome começando com a
mesma letra ?
Exemplo 2:
Quantas vezes é preciso jogar um dado para garantir que um
mesmo valor apareça duas vezes ?
	Sumário
	Conjuntos
	Definições
	Subconjuntos
	Operações
	Diagramas de Venn
	Propriedades
	Definições
	Uso de Identidades