Logica e Matematica Discreta
Teoria Elementar dos Conjuntos
Prof Clezio
04 de Junho de 2010
Curso de Ciencia da Computacao
Nocoes basicas
Um conjunto designa-se geralmente por uma letra latina maiuscula:
A,B,C , . . .X ,Y ,Z
Os objetos que constituiem um conjunto denomina-se elementos do con-
junto, sao representados por letras latinas minusculas:
a, b, c, . . . x , y , z
O conjunto A cujos elementos sao a, b, c, . . . serao denotados por:
A = {a, b, c, . . .}
Exemplos:
1. Conjunto das vogais do alfabeto portugues {a, e, i , o, u};2. Conjunto dos dias da semana {segunda feira, terca feira, quarta
feira, quinta feira, sexta feira, sabado, domingo}
1
Nocoes basicas
Conjuntos sao particularmente uteis em programao para definir variaveis,
constantes, strings, listagens, etc.
Relacao de pertinencia:Para indicar que um elemento x pertence ao conjunto A, escreve-se:
x ∈ A.
ara indicar que um elemento x nao pertence ao conjunto A, escreve-se:
x /∈ A.
Conjunto Universo:
Definicao:Chama-se conjunto universo ou apenas universo de uma teoria o
conjuntos de todos os entes que sao sempre considerados como
elementos dessa teoria.
E usual usual tambem chamar o conjunto universo de conjunto
fundamental da teoria e representa-se pela letra U.
2
Nocoes basicas
Exemplos:
1. Em aritmetica o conjunto universo e o conjunto Z, de todos os
numeros inteiros;
2. Em Calculo Diferencial e integral o conjunto universo e o conjunto Rde todos os numeros reais;
3. Em geometria espacial o conjunto universo e formado pelos pontos
do espaco tridimensional.
Diagramas de Ven
Em um diagrama de Venn o Universo e representado por um retangulo e
os demais conjuntos por cırculos dentro do retangulo.3
Determinacao de um Conjunto
De um modo geral, diz-se que um conjunto A e dado ou definido em um
universo U quando se conhece uma criterio, uma propriedade, que permite
saber se um elemento de U pertence a A.
Ha duas formadas de definir um conjunto em um universo U.
I) Enumerando individualmente todos os elementos que pertencem ao con-
junto; A = {=,+,%,&, 1}
II) Atraves de uma propriedade p(x) definida sobre elementos do universo
U, podemos formar o conjunto A dos elementos de U que satisfazem a
propriedade p(x).
Simbolicamente: A = {x ∈ U ∧ p(x)}
4
Nocoes basicas
Definicao:Dois conjuntos A e B dizem-se iguais se e somente se todos elemento
que pertence a um deles tambem pertence ao outro.
Exprime-se a igualdade dos conjuntos A e B pela notacao usual A = B.
Simbolicamente, escrevemos
A = B ⇐⇒ (∀x)(x ∈ A ⇐⇒ x ∈ B)
Exprime-se que o conjunto A nao e igual ao conjunto B pela notacao usual
A 6= B.
Simbolicamente, escrevemos
A 6= B ⇐⇒ (∃x)(x ∈ A ∧ x /∈ B) ∨ (∃y)(y ∈ B ∧ y /∈ A)
5
Igualdade de conjuntos
Exemplos:
1) {5, 6, 7} = {7, 5, 6} = {5, 5, 6, 6, 7}2) {x |x2 − 3x + 2 = 0} = {1, 2} = {1, 2, 2, 1}3) {x ∈ N|5 < x < 9, x 6= 7} = {x ∈ N|5 < x < 9, x e par}
6
Relacao de Inclusao
Dois conjuntos quaisquer podem ser comparados pela relacao de inclusao.
Definicao:Diz-se que um conjunto A esta contido em um conjunto B se e somente
se todo elemento de A tambem e um elemento de B.
Notacao: A ⊆ B
Simbolicamente,
A ⊆ B ⇐⇒ (∀x)(x ∈ A =⇒ x ∈ B)
A
B
Quando A esta contido em B tambem se diz que B contem A, o que se
indica pela notacao B ⊇ A, que se Le “B contem A.
7
Relacao de Inclusao
A Negacao de A ⊆ B indica-se pela notacao A * B, que se le: A nao esta
contido em B.
E claro que A * B se e somente se existe pelo menos um elemento de A
que nao e elemento de B, ou seja,
A * B ⇐⇒ (∃x)(x ∈ A ∧ X /∈ B)
Assim como fizemos antes, escrevemos B + A, que se le“B nao contem A
8
Relacao de Inclusao
Exemplos:
1) {1, 2} ⊆ {1, 2, 5}2) O conjunto P dos numeros naturais pares esta contido no conjunto
N dos numeros naturais: P ⊆ N
3) O conjunto A dos numeros naturais terminados em 5 esta contido
no conjunto B dos numeros naturais divisıveis por 5: A ⊆ B
4) Sejam A o conjunto dos quadrados, B o conjunto dos retangulos e
C o conjuntos dos paralelogramos: Temos A ⊆ B,A ⊆ C e B ⊆ C .
9
Propriedades da Inclusao
A relacao de inclusao possui as seguintes propriedades:
1) Reflexiva: A ⊆ A;
2) Transitiva: A ⊆ B ∧ B ⊆ C =⇒ A ⊆ C
3) Anti-simetrica: A ⊆ B ∧ B ⊆ A =⇒ A = B
4) O conjunto vazio esta contido em qualquer conjunto A, isto e,
(∀A)(∅ ⊆ A).
5) Qualquer que seja o conjunto A em um universo U, A esta contido
em U, ou seja, (∀A)(A ⊆ U).
A propriedade anti-simetrica nos fornece um metodo para demonstrar a
igualdade entre dois conjuntos A e B.
10
Conjunto Comparaveis
Definicao:Dois conjuntos A e B dizem-se comparaveis se A ⊆ B ou B ⊆ A.
A e B nao sao comparaveis se A * B e B * A. Nesse caso existe um
elemento de A que nao esta em B e existe um elemento de B que nao esta
em A.
Exemplos:
1) O conjunto A = {a, b} e {a, b, c} sao comparaveis, pois A esta
contido em B.
2) Os conjuntos C = {1, 2} e D = (2, 3, 4) nao sao comparaveis, pois
1 ∈ C e 1 /∈ D e 3 ∈ De 3 /∈ C .
11
Subconjuntos
Definicao:Todo conjunto A que esta contido em um conjunto B (A ⊆ B) diz se
subconjunto ou parte de B.
Como B sempre esta contido em si mesmo (B ⊆ B), B e uma parte de B
que e chamada de parte cheia de B.
O conjunto vazio tambem esta em B (∅ ⊆ B), ou seja ∅ e parte de B que
e chamada de parte vazia de B.
Se A ⊆ B nao e nem vazio e nem e a parte cheia de B, dizemos que A e
um subconjunto proprio ou uma parte propria de B.
12
Conjunto das Partes de um Conjunto
Definicao:Chama-se conjunto das partes de um conjunto E o conjunto cujos
elementos sao todas as partes de E, inclusive a parte cheia e a parte
vazia.
O Conjunto das partes de E e representado por P(E ) e seus elementos
sao os subconjuntos X tais que X ⊆ E . Simbolicamente:
P(E ) = {X |X ⊆ E}
Se E for um conjunto finito entao P(E ) tem 2n elementos.
Teorema:Quaisquer que seja os conjuntos E e F , tem-se:
E ⊆ F ⇐⇒ P(E ) ⊆ P(F )
13
Complementar de um subconjunto
Seja A uma parte de um conjunto E (A ⊆ E ).
Definicao:Chama se complementar de A em relacao a E ou complemento de A em
relacao E , o conjunto de todos os elementos de E que nao pertencem a
A.
Notacao:E − A = {x |x ∈ E ∧ x /∈ A}. Se E e o conjunto universo U
denotaremo U − A por Ac ou A′.
������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������
������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������
E
E−A
A
O conjunto E em relacao ao qual se determina o complementar, chama se
conjunto de referencia ou referencial.
14
Propriedades do Complementar
Sejam A e B partes de um conjunto E .
1) E − ∅ = E
2) E − E = ∅3) E − (E − A) = A
4) A ⊆ B =⇒ E − B ⊆ E − A
Observacao: Para conjuntos quaisquer A e B em um universo U tem-se:
∅C = U, Uc = ∅, (Ac)c = A,A ⊂ B ⇐⇒ Bc ⊆ Ac .
15
Operacoes com conjunto
Definicao:Chama-se intersecao de dois conjuntos A e B ao conjunto de todos os
elementos que pertencem simultaneamente a A e a B.
Notacao: A ∩ B e se le A inter B.
Simbolicamente: A ∩ B = {x |x ∈ A ∧ x ∈ B}
Logo x ∈ A ∩ B ⇐⇒ x ∈ A ∧ x ∈ B.
Exemplos
1) {1, 2, 3, 4} ∩ {3, 4, 5, 6} = {3, 4}2) N ∩ Z = N3) Q ∩ R = Q4) Sejam os conjuntos A = {x ∈ N|x e multiplo de 2} e B = {x ∈ N|x
e multiplo de 3} entao A ∩ B = {x ∈ N|x e multiplo de 6}.5) {x ∈ R|x > 2 ∩ {x ∈ R|x ≤ 5} = {x ∈ R|2 < x ≤ 5}
16
Operacoes com conjunto
Definicao:Dois conjuntos A e B dizem-se disjuntos se e somente se nao tem
elementos comuns.
Portanto A e B sao disjuntos se e somente se a intersecao de A e B e o
conjunto vazio: A ∩ B = ∅
Simbolicamente A e B sao disjuntos ⇐⇒ A ∩ B = ∅
17
Operacoes com conjunto
Propriedades da Inclusao e da Intersecao
1) A ∩ B ⊆ A e A ∩ B ⊆ B
2) A ⊆ B ⇐⇒ A ∩ B = A
3) C ⊆ A ∧ C ⊆ B ⇐⇒ C ⊆ A ∩ B
4) A ⊆ B =⇒ A ∩ C ⊆ B ⊂ C
18
Operacoes com conjunto
Propriedades da Intersecao
1) A ∩ ∅ = ∅2) A ∩ U = A
3) A ∩ AC = ∅4) A ∩ A = A
5) Comutativa: A ∩ B = B ∩ A
6) Associativa: (A ∩ B) ∩ C = A ∩ (B ∩ C ) Em vista da propriedade
associativa escrevemos simplesmente A ∩ B ∩ C sem utilizar os
parenteses.
19
Operacoes com conjunto
Definicao:Chama se intersecao do n conjuntos A1,A2,A3, . . . ,An ao conjunto dos
elementos que pertence simultaneamente a todos esses n conjuntos.
Notacao: A1 ∩ A2 ∩ A3 ∩ . . . ∩ An oun⋂
i=1
Ai
Simbolicamente:n⋂
i=1
Ai = {x |x ∈ A1 ∧ x ∈ A2 ∧ x ∈ A3 ∧ . . . ∧ x ∈ An}
ou aindan⋂
i=1
Ai = {x |∀(i = 1, 2, 3, . . . , n)(x ∈ Ai )}
20
Operacoes com conjunto
Consideremos um conjunto E e seja F uma colecao de partes de E .
Definicao:Chama-se intersecao da colecao F ou apenas intersecao de F ao
conjunto de todos os elementos x de E que pertence a todos os
subconjuntos X ∈ F .
Notacao:⋂X∈F
X ou⋂{X |X ∈ F}
Simbolicamente:⋂X∈F
{a ∈ E |(∀X )(X ∈ F) =⇒ a ∈ X}
21
Operacoes com conjunto
Seja E = {a, b, c, d , e} e F = {K , L,M}, onde K = {a, b, c, d}, L =
{a, c, d}, M = {d , e} Tem-se⋂X∈F
X = {d}
22
Operacoes com conjunto
Definicao:Chama-se uniao (ou reuniao) de dois conjuntos A e B ao conjunto de
todos os elementos que pertencem a A ou a B.
Notacao: A ∪ B e se le A uniao B.
Simbolicamente: A ∪ B = {x |x ∈ A ∨ x ∈ B}
Logo x ∈ A ∪ B ⇐⇒ x ∈ A ∨ x ∈ B.
Exemplos
1) {1, 2, 3, 4} ∪ {3, 4, 5, 6} = {1, 2, 3, 4, 5, 6}2) N ∪ Z = Z
3) Q ∪ R = R
4) {x ∈ R|2 < x} ∪ {x ∈ R|x ≥ 5} = {x ∈ R|2 < x}
23
Operacoes com conjunto
Propriedades da Uniao
1) A ∪ ∅ = A
2) A ∪ U = U
3) A ∪ AC = U
4) A ∪ A = A
5) Comutativa: A ∪ B = B ∪ A
6) Associativa: (A ∪ B) ∪ C = A ∪ (B ∪ C )
Em vista da propriedade associativa escrevemos simplesmente A ∪ B ∪ C
sem utilizar os parenteses.
24
Operacoes com conjunto
Propriedades da Uniao
1) A ∪ ∅ = A
2) A ∪ U = U
3) A ∪ AC = U
4) A ∪ A = A
5) Comutativa: A ∪ B = B ∪ A
6) Associativa: (A ∪ B) ∪ C = A ∪ (B ∪ C )
25
Operacoes com conjunto
Propriedades da intersecao e da Uniao
Sejam A, B, e C conjuntos quaisquer em um universo U.
1) Lei de Absorcao: A ∩ (A ∪ B) = A e B ∪ (A ∩ B) = B;
2) Distributividade da intersecao em relacao a uniao:
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C );
3) Distributividade da uniao em relacao a intersecao:
A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C );
4) Leis de De Morgam: (A ∩ B)c = Ac ∪ Bc , (A ∪ B)c = Ac ∩ Bc .
26
Operacoes com conjunto
As leis de De Morgam (1806-1871) ensina, que
i) O complementar de intersecao e igual a uniao dos complementares
de cada um dos conjuntos;
ii) O complementar da uniao e igual a intersecao dos complementares
de cada um dos conjuntos.
Em outras palavras a ”tomada”de complementar transforma
intersecao em uniao e vice versa.
27
Operacoes com conjunto
Definicao:Chama se uniao de n conjuntos A1,A2,A3, . . . ,An ao conjunto dos
elementos que pertence a pelo menos um desses n conjuntos.
Notacao: A1 ∪ A2 ∪ A3 ∪ . . . ∪ An oun⋂
i=1
Ai .
Simbolicamente:n⋃
i=1
Ai = {x |x ∈ A1 ∨ x ∈ A2 ∨ x ∈ A3 ∨ . . . ∨ x ∈ An}
ou aindan⋃
i=1
Ai = {x |∃i(i = 1, 2, 3, . . . , n)(x ∈ Ai )}
28
Operacoes com conjunto
Consideremos um conjunto E e seja F uma colecao de partes de E .
Definicao:Chama-se Uniao da colecao F ou apenas uniao de F ao conjunto de
todos os elementos x de E que pertence a, pelo menos, um dos
subconjuntos X ∈ F .
Notacao:⋃X∈F
X ou⋃{X |X ∈ F}
Simbolicamente:⋃X∈F
{a ∈ E |(∃X )(X ∈ F) =⇒ a ∈ X}
29
Operacoes com conjunto
Princıpio de Dualidade.
As propriedade de reuniao, intersecao e complementacao e suas consequen-
cias constituem a chamada Algebra de Conjuntos.
Toda propriedade relativa a subconjuntos de um mesmo conjunto universo
U em que intervenha, no todo ou em partes, as operacoes de uniao, in-
tersecao, complementacao e as relacoes =, ⊆ ou ⊇, resulta em outra
propriedade, conservando-se o sinal = e trocando entre si os sımbolos ∩ e
∪, ⊆ e ⊇, ∅ e U.
Duas propriedades que se podem obter uma da outra por este princıpio de
dualidade dizem duais.
30
Operacoes com conjunto
Simplificacao de Expressoes.
As propriedade das operacoes sobre conjunto permitem simplificar expres-
soes de conjuntos .
1) A ∩ B ∩ Ac = (A ∩ Ac) ∩ B = ∅ ∩ B = ∅2) A ∪ (Ac ∪ ∅) = A ∪ (Ac = U
3) (A ∪ B) ∩ Bc = (A ∩ Bc) ∪ (B ∩ Bc) = (A ∩ BC ) ∪ ∅ = A ∩ Bc
4) (A ∩ B) ∪ (Ac ∩ B) = (A ∪ Ac) ∩ B = U ∩ B = B
5) (A ∪ B)c ∪ (Ac ∩ B) = (Ac ∩ Bc) ∪ (Ac ∩ B) = Ac ∩ (Bc ∪ B) =
Ac ∪ U = Ac .
31
Operacoes com conjunto
Exemplo:
A segunda fase de um concurso publico foi constituıda de dois proble-
mas: 340 candidatos acertaram somente um problema. 300 acertaram
o segundo. 120 acertaram os dois problemas e 250 erraram o primeiro.
Quantos candidatos fizeram a prova? e quantos acertaram pelo menos um
dos problemas?
Solucao: Vamos fazer a distincao dos conjuntos
• A: conjunto dos candidatos que acertaram o primeiro problema;
• B: conjunto dos candidatos que acertaram o segundo problema;
• U: conjunto dos candidatos que fizeram a prova.
Analisando as informacoes dadas, temos que:
1◦) 120 acertaram os dois problemas n(A ∩ B) = 120;
2◦) 300 candidatos acertaram o segundo problema (Observe que nao foi
dito que acertaram somente o segundo problema).32
Operacoes com conjunto
Para determinarmos quantos candidatos acertaram somente o segundo pro-
blema, faremos: 300− 120 = 180.
3◦) 340 candidatos acertaram somente um problema como 180 acertaram
somente o segundo problema, fazendo 340 − 180 = 160 e o numero de
candidatos que acertaram somente o primeiro problema.
4◦) n(S − A) = 250 candidatos erraram o primeiro problema nesse grupo
estao incluıdos os candidatos que acertaram somente o segundo problema
e os que erraram os dois problemas. Dessa forma, 250 − 180 = 70 e o
numero de candidatos que erraram os dois problemas.
33
Operacoes com conjunto
Agora podemos responder a pergunta do problema.
Total = numero de candidatos que acertaram somente o primeiro problema
+ numero de candidatos que acertaram somente o segundo problema +
numero de candidatos que acertaram os dois problemas + numero de can-
didatos que erraram os dois problemas.
Ou seja, Total = 160 + 180 + 120 + 70 = 530 Assim, concluımos que 530
candidatos fizeram a prova.
34