Matemática para Computação

Conjuntos

Conceitos básicos de matemática para computação

  • ciência da computação
  • conceitos básicos
  • conjuntos
  • matemática
Última atualização: 2023-08-01

Resumo

Os conceitos de conjuntos e suas operaçõe são muito utilizados em ciência da computação. Neste artigo são tratados os conceitos básicos de conjuntos e suas operações, com foco no uso destes conceitos nas disciplinas de linguagens formais e bancos de dados.

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.

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:

a A

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$ é:

a A

Definição de Conjuntos

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) \}\]

Continência

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 subconjunto $B$ pode ser visto como:

A B

Subconjunto próprio

Dados os conjuntos $A$ e $B$ e as relações:

\[\begin{eqnarray} A \in 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\]

Igualdade de conjuntos

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:

B 1 2 2 3 3 3 A 1 2 3

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.

Conjunto vazio

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$.

Operações sobre conjuntos

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.

União

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 \}\] A B

Intersecção

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.

A B

Complemento

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 B

Diferenç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}\] A B

Conjunto das Partes

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 \}\]

Produto Cartesiano

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}$.

Propriedades das operações sobre conjuntos

As propriedades analisadas, a seguir, presupõe a existência do universo $U$ e dos conjuntos $A$, $B$ e $C$.

Idempotência

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}\]

Comutativa

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}\]

Associativa

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\]

Distributiva

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}\]

Duplo Complemento

O complemento do complemento de um conjunto $A$, em relação ao universo $U$, é o próprio conjunto.

\[\thicksim\! ( \thicksim\! A ) = A\]

Lei de DeMorgan

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\]

Conjunto universo e conjunto vazio.

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}\]