In [1]:
%matplotlib inline
Álgebra é constituída de operações definidas sobre uma soleção de objetos. Neste contexto, álgebra de conjuntos corresponderia às operações definidas sobre todos os conjuntos.
As operações da álgebra de conjuntos podem ser não reversíveis e reversíveis:
É possível estabelecer uma relação entre a lógica e as operações da álgebra de conjuntos:
| Conectivo ou relação lógicos | Operação ou relação sobre conjuntos |
|---|---|
| Negação | Complemento |
| Disjunção | União |
| Conjunção | Intersecção |
| Implicação | Continência |
| Equivalência | Igualdade |
As propriedades dos conectivos e operadores lógicos são válidas na teoria dos conjuntos, como mostrado a seguir:
| Conectivo lógico | Operação sobre conjuntos |
|---|---|
| Idempotência: $\wedge$ e $\lor$ | idmpotência: intersecção e união |
| Comutativa: $\wedge$ e $\lor$ | comutativa: intersecção e união |
| Associativa: $\wedge$ e $\lor$ | associativa: intersecção e união |
| Distributiva: $\wedge$ sobre $\lor$ $\lor$ sobre $\wedge$ |
distributiva: intersecção sobre união união sobre intersecção |
| Dupla negação | duplo complemento |
| DeMorgan | DeMorgan |
| absorção | absorção |
Sejam $A$ e $B$ dois conjuntos. A união entre eles, $A \cup B$, é definida como:
$A \cup B = \{x \mid x \in A \lor x \in B\}$
Considerando a lógica, o conjunto $A$ pode ser definido como $x \in A$. O conjunto $B$ pode ser definido como $x \in B$. Ou seja, a propriedade de pertiência é utilizada para indicar uma proposição lógica.
A união corresponde à operação lógica disjunção (símbolo $\lor$).
Exemplo: Considere os conjuntos:
Então:
Exemplo: Suponha os conjuntos:
Então:
É importante observar que o resultado da união é um conjunto sem repetições de elementos.
Vejamos as propriedades da união:
Prova da propriedade elemento neutro Elemento neutro: $A \cup \emptyset = \emptyset \cup A = A$.
Assim, há duas igualdades, que podem ser analisadas considerando a validade da transitividade [da igualdade]. Assim, temos que observar alguns casos.
(A) Para provar $A \cup \emptyset = \emptyset \cup A$:
O primeiro caso (1): Seja $x \in A \cup \emptyset$. Então devemos provar que $A \cup \emptyset \subseteq \emptyset \cup A$:
Portanto, $A \cup \emptyset \subseteq \emptyset \cup A$.
O segundo caso (2): Seja $x \in \emptyset \cup A$. Então devemos provar que $\emptyset \cup A \subseteq A \cup \emptyset$:
Portanto, $\emptyset \cup A = A \cup \emptyset$.
Terceiro caso (3): De (1) e (2) concluímos que $A \cup \emptyset = \emptyset \cup A$.
(B) Para provar $A \cup \emptyset = A$:
Quarto caso (4): Seja $x \in A \cup \emptyset$. Então devemos provar que $A \cup \emptyset \subseteq A$:
Portanto, $A \cup \emptyset \subseteq A$.
Quinto caso (5): Seja $x \in A$. Então devemos provar que $A \subseteq A \cup \emptyset$:
Portanto, $A \subseteq A \cup \emptyset$.
Sexto caso (6): De (4) e (5) concluímos que $A \cup \emptyset = A$.
Sétimo caso (7): Por fim, de (3) e (6) e pela transitividade da igualdade, concluímos que $A \cup \emptyset = \emptyset \cup A = A$ e provamos a propriedade do elemento neutro da união.
Exercício 2.1: Prove as propriedades idempotência, comutativa e associativa da união.
In [17]:
import pylab as plt
from matplotlib_venn import venn2, venn2_circles
set1 = set([1,2,3])
set2 = set([3,4,5])
venn2([set1, set2], ('A', 'B'))
plt.show()
Sejam dois conjuntos $A$ e $B$. A intersercção entre eles, $A \cap B$ é definida como:
$A \cap B = \{x | x \in A \wedge x \in B\}$
A união corresponde à operação lógica conjunção (símbolo $\wedge$).
Sejam $A$ e $B$ dois conjuntos não vazios. Se $A \cap B = \emptyset$, então $A$ e $B$ são chamados conjuntos disjuntos, conjuntos independentes, ou conjuntos mutuamente exclusivos.
Exemplo: Considere os conjuntos:
Então:
Vejamos as propriedades da intersecção:
As propriedades a seguir envolvem as operações de união e intersecção:
Exercício 2.2: Algumas linguagens de programação possuem estruturas de dados para conjuntos, as quais disponibilizam, também, operações sobre estes. Faça uma pesquisa sobre linguagens de programação e, selecionando uma linguagem de programação que suporte definição de conjuntos e operações sobre eles, apresente exemplos, contemplando as operações e propriedades vistas até o momento (e.g. pertiência, contingência, união e intersecção).
Exercício 2.3: Considerando uma linguagem de programação que forneça suporte a conjuntos e operações sobre eles, crie um programa que leia conjuntos em arquivos texto (um elemento do conjunto em cada linha) e gere a saída também em um arquivo texto (também um elemento em cada linha). O programa deve considerar e demonstrar a utilização das operações e propriedades vistas até o momento (e.g. pertiência, contingência, união e intersecção).
Exercício 2.4: Suponha o conjunto universo $S = \{p, q, r, s, t, u, v, w\}$ bem como os seguintes conjuntos:
Determine:
a) $B \cap C$
b) $A \cup C$
c) $\sim{C}$
d) $A \cap B \cap C$
e) $\sim(A \cup B)$
f) $(A \cup B) \cap \sim{C}$
Entende-se por operação reversível uma operação a partir de cujo resultado pode-se recuperar os operandos originais.
Considerando o conjunto universo $U$. O complemento de um conjunto $A \subseteq U$, denotado por $\sim{A}$ é definido como:
\begin{align*} \sim{A} = \{x \in U | x \notin A \} \end{align*}Exemplos
Considere o conjunto universo definido por $\mbox{Digitos} = \{0, 1, 2, ..., 9\}$. Seja $A = \{0, 1, 2\}$. Então, $\sim{A} = \{3, 4, 5, 6, 7, 8, 9\}$.
Suponha conjunto universo $\mathbb{N}$. Seja $A = \{0, 1, 2\}$. Então, $\sim{A} = \{x \in \mathbb{N} | x \gt 2\}$.
Para qualquer conjunto universo $U$, valem:
Suponha que $U$ é o conjunto universo. Então, para qualquer conjunto $A \subseteq U$, valem:
Neste último exemplo, observe que:
Também vale a noção e duplo complemento (ou dupla negação), ou seja:
\begin{align*} \sim\sim{A} = A \end{align*}A propriedade denominada DeMorgan vale-se do complemento, envolvendo as operações de unição e interseção, como mostra a tabela a seguir.
| DeMorgan na Álgebra de conjuntos | Propriedade DeMorgan na Lógica |
|---|---|
| $\sim(A \cup B) = \sim{A} \cap \sim{B}$ | $\lnot(p \lor q) \Leftrightarrow \lnot{p} \wedge \lnot{q}$ |
| $\sim(A \cap B) = \sim{A} \cup \sim{B}$ | $\lnot(p \wedge q) \Leftrightarrow \lnot{p} \lor \lnot{q}$ |
Sejam os conjuntos $A$ e $B$. A diferença dos conjuntos $A$ e $B$, denotada por $A - B$ é definida como:
\begin{align*} A - B = A \cap \sim{B} \end{align*}ou
\begin{align*} A - B = \{x | x \in A \wedge x \notin B \} \end{align*}Exemplos
Para qualquer conjunto $A$ sabe-se que:
A operação unária chamada conjunto das partes, ao ser aplicada ao conjunto $A$ resulta no conjunto de todos os subconjuntos de $A$. Suponha um conjunto $A$. O conjunto das partes de $A$ (ou conjunto potência), denotado por $\mbox{P}(A)$ ou $2^A$ é definido por:
\begin{align*} \mbox{P}(A) = \{X | X \subseteq A \} \end{align*}Exemplos
A operação produto cartesiano é uma operação binária que, quando aplicada a dois conjuntos $A$ e $B$ resulta em um conjunto constituído de sequências de duas componentes (tuplas), sendo que a primeira componente de cada sequência é um elemento de $A$, e a segunda componente, um elemento de $B$.
Uma sequência de $n$ componentes, denominada $n$-upla ordenada, consiste de $n$ objetos (não necessariamente distintos) em uma ordem fixa. Por exemplo, uma 2-upla ordenada é denominada par ordenado. Um par ordenado no qual a primeira componente é $x$ e a segunda é $y$ é definido como $\langle x, y \rangle$.
Uma $n$-upla ordenada é definida como:
\begin{align*} \langle x_1, x_2, x_3, ..., x_n \rangle \end{align*}Uma $n$-upla ordenada não deve ser confundida com um conjunto, pois a ordem das componentes é importante. Assim:
\begin{align*} \langle x, y \rangle \neq \langle y, x \rangle \end{align*}O produto cartesiano dos conjuntos $A$ e $B$, denotado por $A \times B$ é definido por:
\begin{align*} A \times B = \{ \langle a, b \rangle | a \in A \wedge b \in B \} \end{align*}O produto cartesiano de um conjunto com ele mesmo é definido por $A \times A = A^2$
Exemplos Sejam os conjuntos $A = \{a\}$, $B = \{a, b\}$ e $C = \{0, 1, 2\}$. Então:
Exercício 2.5: Considere os conjuntos $A = \{a\}$, $B = \{a, b\}$ e $C = \{0, 1, 2\}$. Calcule os seguintes produtos cartesianos:
Diferentemente da união, que desconsidera repetições de elementos no conjunto resultante, a união disjunta permite que os elementos do conjunto resultante sejam duplicados, uma vez que seja identificada a sua fonte. A união disjunta dos conjuntos $A$ e $B$, denotada por $A + B$ ou $A \dot\cup\ B$ é definida como:
\begin{align*} A + B = \{ \langle a, A \rangle | a \in A\} \cup \{ \langle b, B \rangle | b \in B\} \end{align*}ou
\begin{align*} A + B = \{ a_A | a \in A\} \cup \{ b_B | b \in B\} \end{align*}Exemplo
Exercício 2.6: Considere os conjuntos $D = \{0, 1, 2, ..., 9\}$, $V = \{a, e, i, o, u\}$, e $P = \{0, 2, 4, 6, ...\}$. Então, encontre:
Exercício 2.7: Utilizando um banco de dados relacional, crie duas tabelas: Palavras1 e Palavras2, respectivamente. Utilizando linguagem SQL, crie e apresente o resultado de uma consulta que realiza o produto cartesiano entre as duas tabelas.
Exercício 2.8: Crie um programa que lê $n$ arquivos de entrada. Cada arquivo contém uma palavra em cada linha. O programa deve ler os arquivos e gerar um arquivo de saída chamado pc.txt contendo o produto cartesiano entre as palavras dos arquivos de entrada. Cada linha do arquivo de saída deve representar um elemento do produto cartesiano (uma $n$-upla) cujos componentes devem estar separados por um espaço [em branco].
Exemplo: Para os arquivos de entrada:
| palavras1.txt |
|---|
| jose |
| maria |
| palavras2.txt |
|---|
| silva |
| santos |
| palavras3.txt |
|---|
| moreira |
| aires |
O arquivo resultante
| pc.txt |
|---|
| jose silva moreira |
| jose silva aires |
| jose santos moreira |
| jose santos aires |
| maria silva moreira |
| maria silva aires |
| maria santos moreira |
| maria santos aires |