Em diversas áreas da ciência da computação é importante entender conceitos de conjuntos, como nas linguagens formais ou nos bancos de dados. Aqui são apresentados alguns desses conceitos, além das principais operações de conjuntos.
Um conjunto é um grupo de objetos representado como uma unidade. É uma estrutura que armazena elementos de qualquer tipo, sem repetição e sem qualquer ordenação. Um conjunto pode ter zero ou mais elementos distintos. Se um elemento $a$ é um elemento do conjunto $A$, dizemos que $a$ pertence ao conjunto $A$, e denotamos a pertinência por:
\[a \in A\]Uma forma de representação que facilita a visualização de conjuntos é o diagrama de Venn. Graficamente a pertinência de um elemento $a$ ao conjunto $A$ pode ser vista como:
Caso queria se afirmar que $a$ não pertence ao conjunto $A$, utilizamos:
\[a \notin A\]O diagrama de Venn para esta relação entre o elemento $a$ e o conjunto $A$ é:
Uma forma de definir um conjunto é listar todos os elementos do conjunto, por exemplo
\[{Vogais} = \{ a, e, i, o, u \}\]Ao listar todos os elementos de um conjunto, quando o padrão do conjunto é óbvio e de fácil interpretação, podemos utilizar “$\dots$”:
\[\begin{align} & Alfabeto = \{ a, b, c, d, \dots, x, y, z \} \\ & Impares = \{ 1, 3, 5, \dots \} \end{align}\]Outra forma de definir um conjunto é a partir de uma propriedade. Por exemplo, assumindo que $\mathbb{N}$ seja o conjunto dos números naturais, e $\bmod{}$ como a operação que retorna o resto da divisão inteira, podemos definir o conjunto dos números pares como:
\[{Pares} = \{ x \in \mathbb{N} \:|\: x \bmod{2} = 0 \}\]Esta definição de conjunto pode ser interpretada como o conjunto de todos os elementos pertencentes aos números naturais, $\mathbb N$, tal que o resto da divisão inteira seja igual a 0.
A forma geral para a definição de um conjunto em relação a uma propriedade $p$ é:
\[\{ x \:|\: x \in A \land P(x) \} \hspace{2em} \text{ou} \hspace{2em} \{ x \in A \:|\: P(x) \}\]Se todos os elementos de um conjunto $A$ são elementos de um conjunto $B$, afirma-se que $A$ está contido em $B$, e denota-se por:
\[A \subseteq B\]Alternativamente, podemos dizer que $B$ contém $A$, denotando a relação por:
\[B \supseteq A\]Nesse caso, quando $A \subseteq B$ ou $B \supseteq A$, dizemos que $A$ é um subconjunto de $B$.
Para que um conjunto $A$ seja subconjunto do conjunto $B$ é necessário que a seguinte regra seja satisfeita:
\[x \in A \Longrightarrow x \in B\]Graficamente um subconjunto $A$ de um conjunto $B$ pode ser visto como:
Dados os conjuntos $A$ e $B$ e as relações:
\[\begin{eqnarray} A \subseteq B & \\ b \notin A & \\ b \in B \end{eqnarray}\]podemos afirmar que $A$ é subconjunto próprio de $B$, e denota-se essa relação como:
\[A \subset B\]Alternativamente, dizemos que $B$ contém propriamente $A$, utilizando:
\[B \supset A\]Dois conjuntos são iguais se e somente se todos os elementos de um conjunto também pertence ao outro conjunto:
\[A = B \iff A \subseteq B \land B \subseteq A\]A partir da definição da igualdade de conjuntos, podemos demonstrar que elementos repetidos não influenciam na definição do conjunto, uma vez que, mesmo que existam elementos repetidos, a condição $A \subseteq B \land B \subseteq A$ continua válida, como mostra a imagem:
Como não existe elemento $x$ em $A$ tal que $x \notin B$ ou em $B$ tal que $x \notin A$, os conjuntos são iguais, logo, a repetição de elementos não altera o conjunto.
Um conjunto importante é o conjunto que não contém nenhum elemento, o conjunto vazio, $\{\ \}$, usualmente representado pelo símbolo $\varnothing$.
Um conjunto vazio não representa nada, ele representa um conjunto sem nenhum elemento dentro.
O conjunto vazio está contido que qualquer conjunto $A$. Podemos demonstrar isso a partira da definição de subconjunto e da regra da implicação. É necessário que a condição $x \in \varnothing \Longrightarrow x \in A$ seja verdadeira, e como o antecedente $x \in \varnothing$ é falso para qualquer $x$, a condição será verdadeira, logo $\varnothing \subseteq A$.
As principais operações sobre conjuntos são a união, a diferença, o complemento, o conjunto das partes e o produto cartesiano. O resultado de uma operação sobre conjuntos será outro conjunto.
Sejam $A$ e $B$ conjuntos, a união ($\cup$) dos conjuntos resultará em um conjunto com todos os elementos de $A$ e de $B$.
\[A \cup B = \{ x \:|\: x \in A \lor x \in B \}\]Sejam $A$ e $B$ conjuntos, a intersecção ($\cap$) dos conjuntos resultará em um conjunto contendo apenas os elementos presente tanto em $A$ quanto em $B$.
\[A \cup B = \{ x \:|\: x \in A \land x \in B \}\]Quando temos que $A \cap B = \varnothing$ dizemos que $A$ e $B$ são conjuntos disjuntos, independentes ou mutuamente exclusivos.
Dado um conjunto fixo $U$, denominado conjunto universo, o complemento de um conjunto $A$ é formado por todos os elementos de $U$ que não existem em $A$.
\[\thicksim\! A = \{ x \:|\: x \in U \land x \notin A \}\]A diferença entre os conjuntos $A$ e $B$ é um cojunto com os elementos existentes em $A$ que não existem em $B$.
\[\begin{align} & A - B = A \cap \thicksim\! B & A - B = \{ x \:|\: x \in A \land x \notin B \} \end{align}\]O conjunto das partes (ou conjunto potência) de um conjunto $A$ é o conjunto de todos os subconjuntos de $A$.
Seja $A = { a, b, c }$, a lista completa de subconjuntos $S$ de $A$ é $\varnothing$, $\{a\}$, $\{b\}$, $\{c\}$, $\{a, b\}$, $\{a, c\}$, $\{b, c\}$, $\{a, b, c\}$, portanto, o conjunto das partes de $A$ tem 8 elementos:
\[2^A = \mathcal{P}(A) = \{ \varnothing, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\} \}\]Podemos definir o conjunto das partes como:
\[2^A = \mathcal{P}(A) = \{ S \:|\: S \subseteq A \}\]O produto cartesiano de dois conjuntos é o conjunto de pares ordenados $(a, b)$, sendo que $a \in A$ e $b \in B$.
\[A \times B = \{ (a, b) \:|\: a \in A \land b \in B \}\]Esta não é uma operação comutativa. Note que a ordem dos elementos é importante, e $A \times B \neq B \times A$.
A operação pode ser multidimensional, ou seja, executada sobre múltipos conjuntos, como em
\[A \times B \times C = \{(a,b,c) \:|\: a \in A \land b \in B \land c \in C\}\]Esta operação também não é associativa. Seja o conjunto $A = \{1\}$, então $(A \times A) \times A$ resulta em $\{(1, 1), 1\}$, enquanto $A \times (A \times A)$ resulta em $\{1, (1, 1)\}$. L É usual usar expoentes quando do produto cartesiano de um conjunto com ele mesmo, como em $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$, ou $\mathbb{R}^3 = \mathbb{R} \times \mathbb{R} \times \mathbb{R}$.
As propriedades analisadas, a seguir, presupõe a existência do universo $U$ e dos conjuntos $A$, $B$ e $C$.
O resultado da união ou intersecção de um conjunto com ele mesmo é o próprio conjunto.
\[\begin{align} & A \cup A = A \\ & A \cap A = A \end{align}\]As operações de intersecção e união são comutativas.
\[\begin{align} & A \cup B = B \cup A \\ & A \cap B = B \cap A \end{align}\]A ordem das operações de união e intersecção pode ser qualquer:
\[\begin{align} & (A \cup B) \cup C = A \cup (B \cup C) \\ & (A \cap B) \cap C = A \cap (B \cap C) \end{align}\]Com isso temos que o uso de parenteses é desnecessário, uma vez que
\[(A \cup B) \cup C = A \cup (B \cup C) = A \cup B \cup C\]A união de conjuntos é distributiva sobre a intersecção, e a intersecção de conjuntos é distributiva sobre a união.
\[\begin{align} & A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \\ & A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \end{align}\]O complemento do complemento de um conjunto $A$, em relação ao universo $U$, é o próprio conjunto.
\[\thicksim\! ( \thicksim\! A ) = A\]O complemento da união de dois conjuntos é a intersecção dos complementos desses conjuntos.
\[\thicksim\! (A \cup B) = \; \thicksim\! A \; \cap \thicksim\! B\]O complemento da intersecção de dois conjuntos é a união dos complementos desses conjuntos.
\[\thicksim\! (A \cap B) = \; \thicksim\! A \; \cup \thicksim\! B\]Podemos obter o conjunto universo $U$ e o conjunto vazio $\varnothing$ a partir da união ou intersecção de um conjunto com o seu complemento:
\[\begin{align} & A \cup \thicksim A = U \\ & A \cap \thicksim A = \varnothing \end{align}\]