Capı́tulo 3
Teoria dos Conjuntos
Edmilson Marmo Moreira
Universidade Federal de Itajubá - UNIFEI
Programa de Pós-graduação em Ciência e Tecnologia da Computação - POSCOMP
“Trabalho no tempo dissolve o peso de quaisquer preocupações, mas tempo sem
trabalho cria fardos de tédio, sempre difı́ceis de carregar”.
André Luiz
1
Considerações Iniciais
A teoria dos conjuntos é a teoria matemática que trata das propriedades dos conjuntos. Ela tem sua origem nos trabalhos do matemático russo Georg Cantor, e se baseia
na ideia de definir conjunto como uma noção primitiva. Também chamada de teoria
ingênua ou intuitiva devido à descoberta de várias antinomias (ou paradoxos) relacionadas à definição de conjunto. Estas antinomias conduziram a matemática a axiomatizar
as teorias matemáticas, com influências profundas sobre a lógica e os fundamentos da
matemática.
O conjunto é um conceito fundamental em todos os ramos da matemática e também da
computação, pois praticamente todos os conceitos desenvolvidos nestas áreas, bem como
os resultados correspondentes, são baseados em conjuntos ou construções sobre conjuntos
(LIPSCHUTZ, 1972).
Definição 1.1 (Conjunto) Um conjunto é uma lista, coleção ou classe de objetos bem
definidos e não ordenados.
Os objetos em um conjunto podem ser qualquer coisa: números, pessoas, letras, rios
etc. Esses objetos são chamados de elementos ou membros de um conjunto.
Exemplos:
1. Os números 1, 3, 7 e 10.
1
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 2
2. As soluções da equação x2 − 3x + 2 = 0.
3. As pessoas que habitam a Terra.
4. As vogais a, e, i, o e u.
1.1
Notação
Os conjuntos são em geral designados por letras maiúsculas: A, B, C, X, Y etc. Por
sua vez, os elementos dos conjuntos são geralmente representados por letras minúsculas:
a, b, c, x, y etc.
Se um conjunto for definido relacionando seus membros, como, por exemplo, ao se
considerar A, que é constituı́do dos números 1, 3, 7 e 10, pode-se escrever:
A = {1, 3, 7, 10}
isto é, os elementos são separados por vı́rgulas e compreendidos entre chaves { }. Isto é
chamado de forma tabular de um conjunto.
Um conjunto pode também ser definido através das propriedades que seus elementos
precisam satisfazer como, por exemplo, ao se considerar B como o conjunto de todos
os números pares, usa-se então uma letra, geralmente x, para representar um elemento
arbitrário e escreve-se:
B = {x | x é par}
que se lê “B é o conjunto de números x tal que x é par”. Isto é chamado de forma de
construção de um conjunto.
Se um objeto x é um membro de um conjunto A, isto é, A contém x como um de seus
elementos, pode-se então escrever:
x∈A
que também pode ser lido “x pertence a A” ou “x está em A”.
Se, por outro lado, um objeto x não é membro do conjunto A, isto é, A não contém
x como um dos seus elementos, pode-se escrever:
x 6∈ A
Exemplos:
1. Seja A = {a, e, i, o, u}. Desse modo, a ∈ A, x 6∈ A
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 3
2. Seja A = {x | x é par}. Desse modo, 4 ∈ A, 5 6∈ A.
1.2
Conjuntos Finitos e Infinitos
Os conjuntos podem ser finitos ou infinitos. Intuitivamente, um conjunto é finito se
consiste de um número especı́fico de elementos diferentes, isto é, se, durante a contagem
dos diferentes membros do conjunto, o processo de contagem chega a um final. De outro
modo, o conjunto é infinito.
Exemplos:
1. Seja M o conjunto de dias da semana. Assim M é finito.
2. Seja N = {x | x é par}. Assim N é infinito.
Se A for um conjunto finito, designar-se-á por cardinalidade de A o número de seus
elementos, o qual se representa por card(A). Um conjunto com cardinalidade igual a 1
diz-se singular.
1.3
Igualdade de Conjuntos
Se cada elemento do conjunto A é também um membro do conjunto B, então A é um
subconjunto de B. Mais especificamente, A é um subconjunto de B se x ∈ A implica em
x ∈ B. Essa relação é indicada como segue:
A⊂B
que é lida como “A está contido em B”.
Se os conjuntos A e B forem iguais então ter-se-á A ⊂ B e, simultaneamente, B ⊂ A;
ou seja, se A ⊂ B e B ⊂ A se verificarem simultaneamente então tem-se A = B.
Definição 1.2 (Igualdade de Conjuntos) A e B são iguais, isto é A = B se, e somente se, A ⊂ B e B ⊂ A.
Se A é um subconjunto de B, pode-se também escrever:
B⊃A
e será lido como “B é um superconjunto de A” ou “B contém A”.
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 4
Além disso, escreve-se: A 6⊂ B se A não for subconjunto de B. Assim, se A não é
subconjunto de B, isto é, se A 6⊂ B, deve haver pelo menos um elemento de A que não
seja membro de B.
Exemplos:
1. O conjunto A = {1, 3, 5} é um subconjunto de B = {1, 5, 2, 3, 4} pois os números 1,
3 e 5 pertencentes a A, também pertencem a B.
2. Seja N = {x | x é par}, isto é, N = {2, 4, 6, . . .} e seja M = {x | x é uma potência
positiva de 2}, isto é, M = {2, 4, 8, 16, . . .}. Assim M ⊂ N , isto é, M está contido
em N .
1.4
Conjunto Nulo
É conveniente introduzir o conceito de conjunto vazio, isto é, um conjunto que não
contém elementos. Este conjunto é muitas vezes chamado de conjunto nulo. É dito que
tal conjunto é sem elementos ou vazio, sendo representado pelo sı́mbolo ∅ ou por { }.
Exemplos:
1. Seja A o conjunto de habitantes da Terra com mais de 200 anos. De acordo com
estatı́sticas conhecidas, A é um conjunto nulo.
2. Seja N = {x | x2 = 4 ∧ x é ı́mpar}. Assim N é um conjunto vazio.
O conjunto nulo ∅ é considerado como um subconjunto de qualquer conjunto. Considera-se a prova de, por exemplo, ∅ ⊂ A qualquer que seja o conjunto A. A única forma de
mostrar que esta inclusão é falsa é verificar que ∅ possui um elemento que não pertence
a A. Ora, como ∅ não possui elementos então aquela relação verifica-se sempre.
1.5
Conjunto Universo
Intuitivamente, poderia parecer razoável que se considerasse como conjunto qualquer
coleção de objetos. Isto, porém, conduz a situações paradoxais, como se deu conta o
filósofo inglês Bertrand Russel, por volta de 1901.
Bertrand Russel começou por observar que se se adotar a concepção intuitiva de
conjunto, então pode se dizere que alguns conjuntos são membros de si próprios enquanto
outros não o são. Um conjunto de elefantes, por exemplo, não é um elefante e, portanto,
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 5
não é um elemento de si próprio; no entanto, o conjunto de todas as ideias abstratas
é, ele próprio, uma ideia abstrata, pelo que pertence a si próprio. As propriedades “ser
membro de si próprio” e “não ser membro de si próprio” parecem assim ser propriedades
perfeitamente adequadas para definir conjuntos. Mas, estas propriedades conduzem à
criação de um paradoxo (PINTO, 2005).
Suponha, se possı́vel, que o conjunto A seja definido como sendo o conjunto de todos
os conjuntos que não são membros de si próprios, isto é,
A = X : X 6∈ X.
Coloca-se então a questão a saber se A é ou não elemento de si próprio. Se A não for
membro de si próprio A 6∈ A, satisfazendo a propriedade definidora de A e, portanto,
A ∈ A; se A pertence a si próprio, A ∈ A e não satisfaz a propriedade definidora de A e,
como consequência, A 6∈ A. De cada uma das possı́veis hipóteses pode-se deduzir a sua
negação, o que constitui um paradoxo. Uma versão mais leiga do paradoxo foi proposta
pelo próprio Russell, no que ficou conhecido como Paradoxo do Barbeiro. O paradoxo é
construı́do supondo que o barbeiro é o homem da cidade que barbeia os homens que não
se barbeiam a si próprios. O paradoxo é facilmente obtido ao se perguntar se o barbeiro
se barbeia a si próprio.
Para eliminar possibilidades deste tipo supor-se-á, de ora em diante, que os conjuntos
considerados são todos constituı́dos por elementos de um conjunto U suficientemente
grande, chamado conjunto universal ou universo do discurso.
A ideia de um conjunto universal estará sempre presente mesmo quando não seja
explicitamente mencionado. Na matemática há conjuntos que constituem muito frequentemente os universos do discurso sendo, por isso, conveniente dispor de nomes para eles.
Exemplos:
1. N = {0, 1, 2, 3, · · ·}.
2. Z = {x | x é um número inteiro}.
3. Q = {x | x é um número racional}.
4. R = {x | x é um número real}.
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 6
1.6
Comparabilidade
Diz-se que dois conjuntos A e B são comparáveis se
A ⊂ B ou B ⊂ A
isto é, se um dos conjuntos é um subconjunto do outro conjunto. Além disso, é dito que
dois conjuntos não são comparáveis se:
A 6⊂ B e B 6⊂ A
Observe que, se A não é comparável a B, existe então um elemento em A que não existe
em B, assim como há um elemento em B que não aparece em A.
Exemplos:
1. Seja A = {a, b} e B = {a, b, c}. Desse modo, A é comparável a B, pois A é um
subconjunto de B.
2. Seja R = {a, b, d} e S = {a, b, c}. Assim, R e S não são comparáveis pois c ∈
S e c 6∈ R e d ∈ R e d 6∈ S.
1.7
Aplicações em Prolog
Os conjuntos podem ser representados em Prolog através de listas. As aplicações
desta nota serão apresentadas nesta linguagem, utilizando o compilador Turbo Prolog
conforme discussão do Laboratório 01. Entretanto, é preciso considerar que as listas são
estruturas ordenadas que permitem a repetição dados. Desta forma, é necessário tomar as
devidas precauções para que ao manipular as listas, como conjuntos, os resultados sejam
pertinentes.
A listagem do exemplo a seguir ilustra alguns predicados básicos para manipular
conjuntos.
Domains
ConjuntoInt = integer*
Predicates
Pertence(integer,ConjuntoInt).
Cardinalidade(ConjuntoInt,integer).
SubConjunto(ConjuntoInt,ConjuntoInt).
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 7
SubConjuntoAux(ConjuntoInt,ConjuntoInt).
Comparaveis(ConjuntoInt,ConjuntoInt).
Iguais(ConjuntoInt,ConjuntoInt).
Ordena(ConjuntoInt,ConjuntoInt).
Trocar(ConjuntoInt,ConjuntoInt).
Clauses
Pertence(Elem,[Elem|_]).
Pertence(Elem,[_|Cauda]) :Pertence(Elem,Cauda).
Cardinalidade([],0).
Cardinalidade([_|Cauda],N) :Cardinalidade(Cauda,NAux),
N = NAux + 1.
SubConjunto(Conj1,Conj2) :Ordena(Conj1,C1),
Ordena(Conj2,C2),
SubConjuntoAux(C1,C2).
SubConjuntoAux([],[]).
SubConjuntoAux([Elem|Cauda1],[Elem|Cauda2]) :SubConjuntoAux(Cauda1,Cauda2).
SubConjuntoAux(Conj1,[_|Cauda1]) :SubConjuntoAux(Conj1,Cauda1).
Comparaveis(A,B) :SubConjunto(A,B);
SubConjunto(B,A).
Iguais(Conj1, Conj2) :SubConjunto(Conj1, Conj2),
SubConjunto(Conj2, Conj1).
Ordena(Lista,ListaOrdenada) :Trocar(Lista,ListaAux),!,
Ordena(ListaAux,ListaOrdenada).
Ordena(ListaOrdenada,ListaOrdenada).
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 8
Trocar([X,Y|Cauda],[Y,X|Cauda]) :- X > Y.
Trocar([Elem|Cauda1],[Elem|Cauda2]) :Trocar (Cauda1,Cauda2).
O primeiro predicado analisa se um determinado elemento pertence ao conjunto. O
segundo predicado retorna a quantidade de elementos do conjunto. Os demais predicados
estão relacionados a comparação entre conjuntos. É importante observar que o predicado
que avalia se um conjunto é subconjunto de outro não é o mesmo que um predicado para
comparar duas listas diretamente. Isto ocorre, porque entre conjuntos não importa a
ordem em que os elementos aparecem ou são inseridos na estrutura. Desta forma, para
se comparar conjuntos, basta saber se todos os elementos de um conjunto fazem parte do
outro conjunto e vice-versa.
2
Operações com Conjuntos
Em aritmética, aprende-se a somar, subtrair e multiplicar, isto é, atribui-se a cada par
de números x e y, um número x + y chamado a soma de x e y, um número x − y chamado
de diferença de x e y e um número xy chamado de produto de x e y. Esses atributos são
chamados as operações de adição, subtração e multiplicação de números. Nos conjuntos
há também operações semelhantes, ou seja, é possı́vel atribuir novos conjuntos a pares
de conjuntos A e B nas operações conhecidas como união, interseção e diferença. Os
conjuntos podem ser combinados de diversas maneiras.
2.1
União
Definição 2.1 (União de Conjuntos) Sejam os conjuntos A e B. A união dos conjuntos A e B, denotado por A ∪ B, é o conjunto que contém os elementos que pertencem
a A ou a B ou a ambos.
Um elemento x pertence a união dos conjuntos A e B se, e somente se, x pertencer a
A ou pertencer a B. Assim, a união de A e B pode ser concisamente definida por:
A ∪ B = {x | x ∈ A ∨ x ∈ B}.
Deduz-se diretamente da definição da união de dois conjuntos que A ∪ B e B ∪ A são o
mesmo conjunto, isto é,
A ∪ B = B ∪ A.
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 9
Além disso, A e B são sempre subconjuntos de A ∪ B, isto é,
A ⊂ (A ∪ B) e B ⊂ (A ∪ B).
Exemplos:
1. Sejam S = {a, b, c, d} e D = {f, b, d, g}. Assim, S ∪ T = {a, b, c, d, f, g}.
2. Seja P o conjunto dos números reais positivos e seja Q o conjunto dos números reais
negativos. Desse modo, P ∪ Q, a união de P e Q, consiste de todos os números reais
exceto o zero.
Pode-se utilizar diagramas de Venn (assim chamados em honra ao matemático
britânico do século XIX John Venn) para visualizar as operações n-árias entre conjuntos.
A área sombreada na Figura 1 ilustra o conjunto resultante da operação de união nos dois
conjuntos A e B.
Figura 1: Diagrama de Venn representando a união de A e B
O código Prolog a seguir apresenta um predicado para realizar a união entre dois
conjuntos. Para atingir este objetivo, o predicado concatena as listas que representam
os conjuntos. Entretanto, após esta ação, é necessário retirar os elementos repetidos,
ou seja, aqueles elementos que fazem parte dos dois conjuntos originais. O predicado
RetiraRepetidos realiza esta tarefa.
Domains
ConjuntoInt = integer*
Predicates
UneLista(ConjuntoInt,ConjuntoInt,ConjuntoInt).
RetiraTodos(integer,ConjuntoInt,ConjuntoInt).
RetiraRepetidos(ConjuntoInt,ConjuntoInt).
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 10
Uniao(ConjuntoInt,ConjuntoInt,ConjuntoInt).
Clauses
UneLista([],L,L).
UneLista([Elem|L1],L2,[Elem|L3]) :UneLista(L1,L2,L3).
RetiraTodos(_,[],[]).
RetiraTodos(Elem,[Elem|Cauda1],Cauda2) :RetiraTodos(Elem,Cauda1,Cauda2).
RetiraTodos(Elem,[Elem1|Cauda1],[Elem1|Cauda2]) :Elem <> Elem1,
RetiraTodos(Elem,Cauda1,Cauda2).
RetiraRepetidos([],[]).
RetiraRepetidos([Elem|Cauda1],[Elem|Cauda2]) :RetiraTodos(Elem,Cauda1,Lista),
RetiraRepetidos(Lista,Cauda2).
Uniao(Conj1,Conj2,ConjUniao) :UneLista(Conj1,Conj2,ConjAux),
RetiraRepetidos(ConjAux,ConjUniao).
2.2
Interseção
Definição 2.2 (Interseção de Conjuntos) Sejam os conjuntos A e B. A interseção
dos conjuntos A e B, denotada por A ∩ B, é o conjunto que contém os elementos que
pertencem a ambos os conjuntos A e B.
Um elemento x pertence a interseção dos conjuntos A e B se, e somente se, x pertencer
a A e também pertencer a B. Assim, a interseção de A e B pode ser concisamente definida
por:
A ∩ B = {x | x ∈ A ∧ x ∈ B}.
Segue-se diretamente da definição de interseção de dois conjuntos que:
A ∩ B = B ∩ A.
Além disso, cada um dos conjuntos A e B contém A ∩ B, isto é,
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 11
(A ∩ B) ⊂ A e (A ∩ B) ⊂ B.
Outra observação é que se os conjuntos A e B não têm elementos em comum, isto é,
se A e B são disjuntos, a interseção de A e B é o conjunto nulo, isto é, A ∩ B = ∅.
Exemplos:
1. Sejam S = {a, b, c, d} e D = {f, b, d, g}. Assim, S ∩ T = {b, d}.
2. Seja V o conjunto dos múltiplos de 2, isto é, V = {2, 4, 6, . . .}; e seja W o conjunto
dos múltiplos de 3, isto é, W = {3, 6, 9, . . .}. Assim, V ∩ W = {6, 12, 18, . . .}.
Definição 2.3 (Conjuntos Disjuntos) Dois conjuntos são chamados disjuntos se a interseção destes conjuntos resultar no conjunto vazio.
O diagrama de Venn apresentado na Figura 2 representa a interseção dos conjuntos
A e B.
Figura 2: Diagrama de Venn representando a interseção de A e B
O próximo código Prolog apresenta o predicado para realizar a interseção de dois
conjuntos. O predicado Pertence já foi apresentado anteriormente, por isso seu código
não está presente nesta listagem.
Predicates
Intersecao(ConjuntoInt, ConjuntoInt, ConjuntoInt).
Clauses
Intersecao([],_,[]).
Intersecao([Elem|Cauda1],Conj2,[Elem|Cauda2]) :Pertence(Elem,Conj2), !,
Intersecao(Cauda1,Conj2,Cauda2).
Intersecao([_|Cauda],Conj2,ConjInter) :Intersecao(Cauda,Conj2,ConjInter).
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 12
2.3
Diferença
Definição 2.4 (Diferença entre Conjuntos) Sejam os conjuntos A e B. A diferença
de A e B, denotada por A − B, é o conjunto contendo os elementos que estão em A mas
não em B. A diferença de A e B é também chamada de complemento de B com relação
a A.
Um elemento x pertence a diferença de A e B se, e somente se, x pertencer a A e não
pertencer a B. Assim, a diferença de A e B pode ser concisamente definida por:
A − B = {x | x ∈ A ∧ x 6∈ B}.
O conjunto A contém A − B como um subconjunto, isto é,
(A − B) ⊂ A.
Outra observação é que os conjuntos (A − B), (A ∩ B) e (B − A) são mutuamente
disjuntos, isto é, a interseção de quaisquer dois destes conjuntos resulta no conjunto vazio.
Exemplos:
1. Sejam S = {a, b, c, d} e D = {f, b, d, g}. Assim, S − T = {a, c}.
2. Sejam R o conjunto dos números reais e Q o conjunto dos números racionais. Assim,
R − Q consiste no conjunto dos números irracionais.
O diagrama de Venn apresentado na Figura 3 representa a diferença dos conjuntos A
e B.
Figura 3: Diagrama de Venn representando a diferença de A e B
A seguir é apresentado o predicado Prolog para a operação de diferença. Este predicado utiliza o predicado RetiraTodos, já comentado anteriormente.
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 13
Predicates
Diferenca(ConjuntoInt, ConjuntoInt, ConjuntoInt).
Clauses
Diferenca(ConjDif,[],ConjDif).
Diferenca(Conj1,[Elem|Cauda],ConjDif) :RetiraTodos(Elem,Conj1,ConjAux),
Diferenca(ConjAux,Cauda,ConjDif).
2.4
Complemento
Definição 2.5 (Complemento de um Conjunto) Seja U o conjunto universo. O
complemento do conjunto A, denotado por A0 , é o complemento de A com relação a U.
Em outras palavras, o complemento do conjunto A é U − A.
Um elemento x pertence A0 se, e somente se, x 6∈ A. O complemento de A pode ser
também definido resumidamente por:
A0 = {x | x ∈ U ∧ x 6∈ A}
ou simplesmente:
A0 = {x | x 6∈ A}.
Exemplos:
1. Considerando que o conjunto universal U seja o alfabeto e seja T = {a, b, c}. Assim
T 0 = {d, e, f, . . . , y, z}.
2. Seja E = {0, 2, 4, 6, . . .}, isto é, os números pares. Então, E 0 = {1, 3, 5, . . .}, os
números ı́mpares, considerando que o conjunto universal seja constituı́do pelos números naturais {0, 1, 2, 3, . . .}.
O diagrama de Venn apresentado na Figura 4 representa o complemento de A, isto é,
a área por fora de A. O conjunto universal U consiste na área do retângulo.
Algumas observações são diretamente identificadas a partir do complemento de um
conjunto:
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 14
Figura 4: Diagrama de Venn representando o complemento de A
1. A união de qualquer conjunto A e seu complemento A0 é o conjunto universal, isto
é,
A ∪ A0 = U.
2. O conjunto A e seu complemento A0 são disjuntos, isto é,
A ∩ A0 = ∅.
3. O complemento do conjunto universal U é o conjunto nulo ∅ e vice-versa, isto é,
U 0 = ∅ e ∅0 = U.
4. O complemento do complemento de um conjunto A é o próprio conjunto A. Abreviadamente:
(A0 )0 = A.
5. A diferença de A e B é igual à interseção de A com o complemento de B, isto é,
A − B = A ∩ B0.
A prova desta observação ocorre diretamente das definições:
A − B = {x | x ∈ A ∧ x 6∈ B} = {x | x ∈ A ∧ x ∈ B 0 } = A ∩ B 0 .
2.5
Conjunto de Potência
A famı́lia de todos os subconjuntos de qualquer conjunto A é chamado o conjunto
de potência ou conjunto das partes de A. Designa-se o conjunto de potência de A
por:
2A .
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 15
Exemplos:
1. Seja M = {a, b}. Assim 2M = {{a, b}, {a}, {b}, ∅}.
2. Seja E = {1, 2, 3}. Assim 2E = {E, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3}, ∅}.
Se um conjunto S é finito, ou seja, S possui n elementos, pode-se provar que o conjunto de potência de S tem 2n elementos. Esta é uma das razões pela qual a classe dos
subconjuntos de S é chamada de conjunto de potência de S e é designada por 2S .
Para se representar o conjunto de Potência de um conjunto em Prolog, será necessário declarar uma lista de lista, ou seja, um conjunto de conjunto. A próxima listagem
apresenta este código.
Domains
ConjuntoInt = integer*
ConjPotencia = ConjuntoInt*
Predicates
GeraSubconjuntos(ConjuntoInt,ConjPotencia).
Clauses
GeraSubConjuntos(Conj,ConjPot) :findall(X,SubConjuntoAux(Conj,X),ConjPot).
Destaca-se, ainda, a utilização do predicado predefinido findall. Este predicado é
usado para colher valores especı́ficos de uma lista ou string convertida em lista, fazendo
backtracking, tanto em tokens, ou retirando os caracteres e colocando-os em uma lista. A
fórmula geral deste predicado é:
findall(VarNome,AlgumPredicado(...), ListaParametros)
O primeiro parâmetro informa ao Prolog que variável designa o valor a ser extraı́do da
lista; o segundo é um predicado que o usuário constrói e oferece muitos valores durante o
processo de backtracking; o último é uma variável que conterá a lista de valores encontrados
no backtracking. Deve haver um domı́nio definido ao qual pertençam todos os valores de
ListaParametros (ROBERTS, 1988).
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 16
2.6
Operações em Conjuntos Comparáveis
As operações de união, interseção, diferença e complemento têm propriedades simples
quando os conjuntos sob consideração são comparáveis. Os seguintes teoremas podem ser
provados:
• Seja A um subconjunto de B. Assim a interseção A e B é precisamente A, isto é,
A ⊂ B implica em A ∩ B = A.
• Seja A um subconjunto de B. A união de A e B é precisamente B, isto é,
A ⊂ B implica em A ∪ B = B.
• Seja A um subconjunto de B. Assim B 0 é um subconjunto de A0 , isto é,
A ⊂ B implica em B 0 ⊂ A0 .
• Seja A um subconjunto de B. A união de A e (B − A) é precisamente B, isto é,
A ⊂ B implica em A ∪ (B − A) = B.
3
Identidade dos Conjuntos
Existem muitas igualdades entre conjuntos envolvendo as operações de união, interseção, diferença e complementação que são verdadeiras para todos os subconjuntos de um
dado conjunto S. Como elas são independentes dos subconjuntos particulares utilizados,
essas igualdades são chamadas de identidades.
A tabela a seguir apresenta algumas dessas identidades:
Identidades
Leis
A∪A=A
A∩A=A
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)
Associativas
A∪B =B∪A
A∩B =B∩A
Comutativas
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Distributivas
A∪∅=A
A∪U =U
A∩U =A
A∩∅=∅
Identidade
A ∪ A0 = U
(A0 )0 = A
A ∩ A0 = ∅
U = ∅, ∅0 = U
Complemento
(A ∪ B)0 = A0 ∩ B 0
(A ∩ B)0 = A0 ∪ B 0
de Morgan
Idempotentes
0
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 17
4
Exercı́cios
1. Seja que A = {1, 2, 3, 4, 5} e B = {0, 3, 6}. Encontrar:
(a) A ∪ B.
(b) A ∩ B.
(c) A − B.
(d) B − A.
2. Seja S = {B, A, S, I, C}, B = {P, A, S, C, A, L}, C = {F, O, R, T, R, A, N }. Encontrar:
(a) A ∪ B.
(b) A − (B ∩ C).
(c) A − B.
(d) B − A.
3. Encontrar 2A , onde A = {1, 2, 3}.
4. Se A e B são conjuntos, define-se a diferença simétrica de A e B por
A M B = (A − B) ∪ (B − A)
Seja A = {1, 2, 3, 4, 5, 6}, B = {4, 5, 6, 7, 8} e C = {0, 1, 2, 8}. Encontrar:
(a) A M B
(b) B M C
(c) A M A
(d) A M ∅
(e) (A M B) M C
(f) (A M A) M A
5. Desenvolver um predicado Prolog para encontrar a diferença simétrica entre dois
conjuntos.
6. Numa escola de 360 alunos, onde as únicas matérias dadas são matemática e português, 240 alunos estudam matemática e 180 alunos estudam ambas. Qual o número
de alunos que estudam português?
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 18
7. Numa indústria, 120 operários trabalham de manhã, 130 trabalham à tarde, 80
trabalham à noite; 60 trabalham de manhã e à tarde, 50 trabalham de manhã e a
noite, 40 trabalham à tarde e à noite e 20 trabalham nos três perı́odos. Sobre esta
estrutura é possı́vel afirmar:
(a) 150 operários trabalham em 2 perı́odos.
(b) Há 500 operários na indústria.
(c) 300 operários não trabalham à tarde.
(d) Há 30 operários que trabalham só de manhã.
8. Um colégio ofereceu cursos de inglês e espanhol, devendo os alunos se matricularem
em pelo menos um deles. Dos 45 alunos de uma classe, 13 resolveram estudar tanto
inglês quanto espanhol; em espanhol, matricularam-se 22 alunos. Quantos alunos se
matricularam em inglês?
9. Num colégio foi realizada uma pesquisa para saber quais os esportes praticados
pelos alunos. Sabe-se que A={alunos que jogam basquete}, B={alunos que jogam
futebol} e C={alunos que jogam volei}. O resultado está resumido na tabela a
seguir:
card(A)
card(B)
card(C)
card(A ∩ B)
card(A ∩ C)
card(C ∩ B)
card(A ∩ B ∩ B)
card(U ) − card(A ∪ B ∪ C)
150
180
100
30
40
25
20
245
10. Num almoço, foram servidos, entre outros pratos, frangos e leitões. Sabendo-se que,
das 94 pessoas presentes, 56 comeram frango, 41 comeram leitão e 21 comeram dos
dois, qual o número de pessoas que não comeram nem frango nem leitão?
11. Verifique a validade das proposições a seguir:
(a) {1, 4, 3} = {3, 4, 1};
(b) {1, 3, 1, 2, 3, 2} ⊂ {1, 2, 3};
(c) {4} ∈ {{4}};
(d) {4} ⊂ {{4}};
(e) ∅ ⊂ {{4}};
12. Sejam A = {1, 2, . . . , 8, 9}, B = {2, 4, 6, 8}, C = {1, 3, 5, 7, 9}, D = {3, 4, 5} e E =
{3, 5}. Que conjuntos podem ser iguais a X se são dadas as seguintes informações:
(a) X e B são disjuntos;
(b) X ⊂ D e X 6⊂ B
(c) X ⊂ A e X 6⊂ C
Matemática Discreta - Notas de Aula - Capı́tulo 03 - 19
(d) X ⊂ C e X 6⊂ A
13. Escreva um predicado prolog que ordena uma lista de elementos utilizando o método
QuickSort.
14. Prove que: (A − B) ∩ B = ∅.
15. Prove que: B − A é um subconjunto de A0 .
16. Prove: B − A0 = B ∩ A.
17. Prove que A ∪ B = ∅ implica em A = ∅ e B = ∅.
18. Prove que se A ⊂ B e B ⊂ C, então A ⊂ C.
19. Prove que se (A − B) ∪ (B − A) = A ∪ B, então A ∩ B = ∅.
Referências
GERSTING, J. L. Fundamentos Matemáticos para a Ciência da Computação: Um
tratamento moderno de Matemática Discreta. 5a. ed. Rio de Janeiro: Livros Técnicos e
Cientı́ficos Editora S.A. 597 p.
LIPSCHUTZ, S. Teoria dos Conjuntos. São Paulo: McGraw-Hill, 1972. 337 p.
PINTO, J. S. Tópicos de Matemática Discreta. Aveiro, 2005.
ROBERTS, R. Turbo Prolog. Rio de Janeiro: LTC - Livros Técnicas e Cientı́ficos Editora
Ltda, 1988. 180 p.