O principal axioma da Teoria dos Conjuntos, que relaciona os termos primitivos elemento e conjunto diz que a afirmação "Um elemento pertence a um conjunto" é uma proposição. A simplicidade aparente deste axioma esconde dois importante fatos: ao considerar como proposição a afirmação dada, decorre que
- a pertinência estabelece a relação entre elementos e conjuntos: dado um elemento qualquer e um conjunto qualquer, este elemento pertence (ou não) ao conjunto;
- a Teoria dos Conjuntos fica edificada sobre a Lógica, uma vez que o que vale para proposições valerá para este axioma também.
Em geral, elementos são representados por letras minúsculas e conjuntos por letras maiúsculas. Dizer que "um elemento está contido no conjunto A" ou que "o conjunto A pertence ao conjunto B" não só é impreciso como é logicamente falso: a relação de pertinência se dá entre conjuntos e elementos (a relação de subconjunto, associada ao termo "contido", se dá entre conjuntos; elementos se relacionam entre si por relação de igualdade).
Este axioma permite também definir precisamente um conjunto especial, denominado conjunto vazio: ∅ é um conjunto vazio se, para qualquer elemento a, a não pertence a ∅. Veja que esta definição não é baseada na ideia de cardinalidade (número de elementos de um conjunto), a qual nem mesmo foi definida ainda, e ainda permite provar fatos importantes, como o que o conjunto vazio é único e que todo conjunto contém o conjunto vazio.
Uma vez definida a relação entre conjuntos e elementos, torna-se fundamental definir como um conjunto pode ser descrito. A Teoria do Conjunto nos fornece duas formas:
- a enumeração de todos os seus elementos;
- descrição das propriedades comuns a todos os elementos do conjunto. Mais formalmente, se P(x) é uma sentença aberta em x (isto é, uma sentença tal que, uma vez atribuí um valor específico para a variável x, tal sentença se torna uma proposição), então {x ∈ X | P(x) é verdadeira} é um conjunto, onde X é o conjunto de todos os possíveis valores de x.
Usando as duas formas acima, podemos descrever o conjunto A dos números pares positivos menores ou iguais a 10 como
- A = {2, 4, 6, 8, 10}, ou
- A = {x ∈ N | 2 ≤ x ≤ 10}
Dados dois conjuntos A e B, é possível definir três novos conjuntos:
- conjunto união A ∪ B = {x | x ∈ A ou x ∈ B}
- conjunto interseção A ∩ B = {x | x ∈ A e x ∈ B}
- conjunto diferença A \ B = {x ∈ A | x ∉ B}
Observe que os três operadores acima são definidos em termos dos conectivos lógicos fundamentais:
- disjunção, na união;
- conjunção, na interseção; e
- negação na diferença.
Esta relação permite a verificação das propriedades destes operadores e a relação entre eles (como o equivalente das Leis de Morgan para união e interseção).
Há três maneiras de se representar conjuntos em C++: as classes set e bitset, e o tipo primitivo
int, sendo que a última também é válida em C.
A biblioteca padrão do C++ traz a implementação da classe set (#include <set>), que abstrai
a ideia de conjuntos, e provê operações elementares (como inserção e remoção de elementos,
através dos métodos insert() e erase(), ou relações de pertinência, com o método
count()). Nesta classe os elementos são únicos, e armazenados ordenadamente (uma travessia
padrão é feita do menor para o maior elemento). Contudo, as operações de união, interseção e
diferença de conjuntos são feitas em qualquer contêiner ordenado, através das funções
set_union(), set_intersection() e set_difference(), disponíveis na biblioteca de
algoritmos (#include <algorithm>) e exemplificadas abaixo.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> A { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; // Conjunto A
vector<int> B { 2, 3, 5, 7, 11, 13 }; // Conjunto A
vector<int> C;
set_union(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C));
cout << "union = ";
for (auto x : C)
cout << x << " ";
cout << endl; // C = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13 }
C.clear();
set_intersection(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C));
cout << "intersection = ";
for (auto x : C)
cout << x << " ";
cout << endl; // C = { 2, 3, 5, 7 }
C.clear();
set_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C));
cout << "difference = ";
for (auto x : C)
cout << x << " ";
cout << endl; // C = { 1, 4, 6, 8, 9, 10 }
return 0;
}O tipo de dados primitivo int (ou sua variante long long, com maior capacidade de
armazenamento) também pode ser usado para uma interpretação mais compacta e eficiente de
conjuntos. Em geral o tipo int tem 32 bits de tamanho, e podemos cada elemento do conjunto
universo (que contém todos os elementos possíveis, numa quantidade menor ou igual a 32)
com cada bit, de modo que, se o bit está
ligado, o elemento pertence ao conjunto; e se desligado, não pertence.
Fora a restrição em relação ao número de elementos do conjunto universo, esta representação tem várias vantagens:
- ocupa pouco espaço em memória (4 bytes a cada 32 elementos);
- permite responder relações de pertinência em complexidade O(1);
- permite operações de união, interseção e diferença também em O(1).
A última característica se dá por conta da definição de tais operações em termos dos conectivos lógicos, e pelo fato das linguagens C e C++ disponibilizarem tais operações bit a bit. Veja o exemplo anterior reescrito em termos desta nova representação. Considere que o conjunto universo U = {1, 2, 3, ..., 32}.
#include <iostream>
using namespace std;
int main()
{
int A = 2046; // A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, bits correspondentes ligados
int B = 10412; // B = { 2, 3, 5, 7, 11, 13 }, mesmo motivo
int C = A | B; // C = 12286
cout << "union = ";
for (int x = 1; x <= 16; ++x)
if (C & (1 << x))
cout << x << " ";
cout << endl; // C = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13 }
C = A & B; // C = 172
cout << "intersection = ";
for (int x = 1; x <= 16; ++x)
if (C & (1 << x))
cout << x << " ";
cout << endl; // C = { 2, 3, 5, 7 }
C = A & ~B; // C = 1874
cout << "difference = ";
for (int x = 1; x <= 16; ++x)
if (C & (1 << x))
cout << x << " ";
cout << endl; // C = { 1, 4, 6, 8, 9, 10 }
return 0;
}Para conjuntos universos com mais de 32 elementos (ou 64, no caso de variáveis long long), ou
se usa um vetor de inteiros, ou a classe bitset (#include <bitset>), que pode armazenar
uma quantidade arbitrária de bits (que deve ser conhecida em tempo de compilação) e que
traz em sua interface as operações básicas dos conjuntos e suporte para os operadores lógicos
bit a bit.
A linguagem C++ também oferece, em sua biblioteca padrão, a classe multiset
(#include <multiset>), que permite o armazenamento de elementos repetidos (embora seja uma
extrapolação da ideia básica de um conjunto, tal representação pode ser útil em alguns
contextos).
- Codeforces
- UVA
HALE, Margie. Essentials of Mathematics: Introduction to Theory, Proof, and the Professional Culture. Mathematical Association of America, 2003.