import matplotlib.pyplot as plt
plt.style.use('../styles/gcpeixoto-book.mplstyle')

Conjuntos¶

Objetivos de aprendizagem¶

Descrever, em linguagem natural e em Python, os conceitos fundamentais da teoria ingênua de conjuntos;
Implementar operações entre conjuntos em Python utilizando o tipo fundamental "set";
Identificar e interpretar relações entre conjuntos de dados em contextos aplicados;
Projetar soluções computacionais básicas que utilizem estruturas de conjuntos para representar e cruzar informações

Teoria “ingênua” de conjuntos¶

A teoria ingênua de conjuntos é o ponto de partida da Matemática moderna. Ela se baseia na ideia intuitiva de que um conjunto é simplesmente uma coleção de objetos bem definidos, chamados elementos. O adjetivo ingênua é usado porque essa abordagem trata os conjuntos de forma direta, sem recorrer a formalismos lógicos rigorosos — assume-se que qualquer coleção de objetos pode formar um conjunto.

Essa visão é suficiente para aplicações práticas em ciência da computação, onde conjuntos são usados para representar grupos de dados, categorias, coleções de registros ou relações entre objetos. Ela se contrapõe à teoria axiomática, que fornece estruturas necessária para se provar propriedades fundamentais de forma rigorosa e evitar contradições. Neste capítulo, veremos como expressar a teoria ingênua a partir de exemplos usando a linguagem Python.

Curiosidade: teoria ingênua x teoria axiomática

A teoria “ingênua” dos conjuntos trata os conjuntos de forma intuitiva — qualquer coleção de objetos bem definidos pode ser considerada um conjunto. Essa visão é simples e suficiente para a maior parte da matemática discreta e da computação, onde trabalhamos com conjuntos finitos e bem delimitados.

Já a teoria axiomática dos conjuntos, como a de Zermelo-Fraenkel (ZF), ou ZF com Axioma da Escolha (ZFC), surgiu para resolver paradoxos lógicos descobertos na formulação ingênua, como o Paradoxo de Russell.

Assim, enquanto a teoria ingênua é conceitualmente acessível e prática para aplicações computacionais, a teoria axiomática fornece a base lógica rigorosa sobre a qual toda a matemática moderna é construída.

Princípios de intuição¶

A intuição natural sobre o que é um conjunto apoia-se em ideias pouco rigorosas. São três os princípios básicos da teoria ingênua:

Princípio da compreensão irrestrita:

“Para toda propriedade $P(x)$ , existe um conjunto formado por todos os elementos que a satisfazem.”

Princípio da extensionalidade:

“Dois conjuntos são iguais se e somente se têm os mesmos elementos.”

Este princípio, também usado pela teoria axiomática, diz que um conjunto é definido pela “extensão” de seus elementos.

Princípio da liberdade de construção:

“Qualquer coleção de objetos bem definidos pode ser reunida em um conjunto.”

Este princípio, na verdade, apenas reforça a “ingenuidade” de se definir conjuntos de forma livre.

Elementos¶

Em Python, os elementos (ou membros) de um conjunto (finito) serão caracterizados por um objeto que possui um tipo. Aqui, usaremos os seguintes: int, float, bool, str, list, tuple e set.

Vejamos alguns exemplos:

type(2)

int

type(3.5)

float

type(True)

bool

type(False)

bool

type('palavra')

str

type([1,'a',3.5,True])

list

type((1,2))

tuple

type({1,2,3})

set

Definição de conjuntos¶

De maneira simples, podemos definir uma coleção ou conjunto de elementos por atribuição e listas.

$V = \{ v : v \text{ é uma vogal} \}$

vogais = ['a','e','i','o','u'] # conjunto das vogais
vogais

['a', 'e', 'i', 'o', 'u']

$P = \{ x : x \text{ é ímpar e } 1 \leq x \leq 7 \}$

P = [1,3,5,7] 
P

[1, 3, 5, 7]

Entretanto, para usarmos operações de conjuntos, a estrutura mais adequada para definir conjuntos é set.

Coleções vs. conjuntos em Python

Em matemática, uma coleção de elementos pode ser representada de várias formas. Na prática, usamos enumeração (listagem dos elementos) ou especificação (propriedade). Em Python, a ideia de “coleção” se traduz em estruturas que armazenam vários valores, como listas (list), tuplas (tuple) e conjuntos (set). A diferença é que:

uma lista (list) mantém a ordem dos elementos e permite repetições, funcionando como uma sequência ordenada, o que é algo mais próximo de uma enumeração (p.ex. [1,2,2,3]).
um conjunto (set) elimina duplicatas e não mantém ordem, refletindo a definição matemática de conjunto: uma coleção sem repetição e sem ordem (p.ex. {1,2,3}).

Assim, embora possamos usar listas para descrever coleções, a estrutura set é a que realmente implementa o conceito matemático de conjunto em Python.

V = set(vogais)
V

{'a', 'e', 'i', 'o', 'u'}

P = set(P)
P

{1, 3, 5, 7}

Definição por extensão¶

Podemos definir um conjunto em Python de duas formas:

usando set();
usando um par de chaves com especificação de elementos: {expr, expr2, ...}.

Conjunto vazio¶

# Única forma (e correta) de criar um conjunto vazio em Python
A = set()
A

set()

Conjunto unitário¶

B = {1}
B

{1}

Conjunto arbitrário¶

C = {'a','b',1,2}
C

{1, 2, 'a', 'b'}

Pertinência¶

Curiosidade: Por que

x \in

O símbolo $\in$ foi introduzido pelo matemático Giuseppe Peano em 1889. A fim de buscar uma notação lógica e universal para expressar relações entre objetos e coleções, ele escolheu a letra grega épsilon ( $\epsilon$ ), inicial da palavra latina “est”, que significa “é”. Assim, a expressão $x \in A$ literalmente queria dizer “x est in A”, ou “x está em A”, que passou a ser lida como “x pertence a A”.

Considere o conjunto $C$ acima.

$x \in C$

1 in C

True

$x \notin C$

'a' not in C

False

Continência¶

Considere o conjunto $D = \{ 1,2 \}$

D = {1,2}

$D \subseteq C$

D <= C

True

$D \subset C$

D < C

True

$C \supseteq D$

C >= D

True

$C \supset D$

C > D

True

Igualdade¶

Consideremos $A = \{ 1,4,3,1 \}$ , $B = \{ 1,4,3,3,1 \}$ , $C = \{ 4,3,1 \}$ , $D = \{ 2,1 \}$ e $E = \{ 1,2,1 \}$

A = {1,4,3,1} 
B = {1,4,3,3,1} 
C = {4,3,1}
D = {2,1}
E = {1,2,1}

Então, todas as expressões abaixo são válidas

A=B

(1)

A=C

(2)

D=E

(3)

C \neq D

(4)

B \neq E

(5)

A == B

True

A == C

True

D == E

True

C != D

True

B != E

True

Atribuição vs. comparação

Lembre-se que a diferença entre A = B e A == B em Python está no seguinte: a primeira sentença é uma atribuição; a segunda, um teste lógico.

A == B == C

True

Cardinalidade¶

A cardinalidade de um conjunto é o número de elementos que ele contém.

Número de elementos em um conjunto

Em Matemática, a cardinalidade é comumente representada por uma das seguintes formas:

com barras verticais (interpretado como “módulo de”): $|A|$
com o símbolo cerquilha (informalmente chamado de tralha, ou hash): $\#A$

Ambas as formas significam “quantos elementos há no conjunto $A$ ”.

Para sabermos o número de elementos de um set, use a função len

len(C)

3

Definição por propriedade¶

Em Python, podemos construir conjuntos usando compreensão de conjuntos (set comprehension), que é a forma mais próxima da notação matemática $A = { x \in U : (x) }$.

A sintaxe geral é:

{ expressão for variável in sequência if condição },

em que sequência é um objeto iterável e condição é uma condição opcional.

Objetos iteráveis

Um objeto iterável em Python é qualquer estrutura de dados que pode fornecer seus elementos um por um, de forma sequencial, permitindo que seja percorrida por um laço for ou transformada em outras coleções. Exemplos são list, tuple, str, range, set, dict, frozenset (versão imutável de set), file e generator.

$F = \{ x \in \mathbb{Z} : 0 \le x < 10 \}$

F = {x for x in range(10)}
F

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

d = range(4)
e = range(6)
D = {-x for x in d[1:3]}
E = {x for x in e}
D

{-2, -1}

{-x for x in d[1:3]}

{-2, -1}

{0, 1, 2, 3, 4, 5}

$B = \{ x \in \mathbb{N} : x < 10 \text{ e } x \text{ é par} \}$

B = {x for x in range(10) if x % 2 == 0}
B

{0, 2, 4, 6, 8}

$C = \{ x \in \mathbb{Z} : 0 \le x < 20 \land x^2 < 100 \}$

C = {x for x in range(20) if x**2 < 100}
C

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Elementos e conjuntos como “objetos”¶

Para representarmos elementos de um conjunto qualquer por meio do computador, é natural usarmos o conceito abstrato de “objeto”. Um objeto, na ciência da computação, é uma entidade dotada de várias propriedades que são discutadas em uma disciplina específica denominada Programação Orientada a Objetos. Por ora, vamos elencar apenas duas dessas propriedades, por serem relevantes para nosso contexto:

Identidade: propriedade que o distingue de qualquer outro objeto. Em Python usamos id(x) para localizar o “endereço lógico” ou “etiqueta” de um objeto x.
Estado: propriedade de conter dados armazenados pelo objeto: atributos, valores e estruturas. O estado pode ser mutável ou imutável.
Comportamento: propriedade que permite operações e interações com outros objetos, como os métodos.

Mutabilidade de conjuntos¶

Em Python, um objeto definido como set() é mutável. Isto significa que sua estrutura interna pode ser modificada após sua criação sem troca de identidade. Vejamos um exemplo:

# Cria um conjunto S
S = {0,1,2} 

# Identidade atual de S
id_atual = id(S) 

# Inclui o elemento 3 em S
S.add(3)

# Identidade de S após modificação
id_nova = id(S)

# Testa se a identidade de S mudou após a modificação
print(id_atual == id_nova)

True

Métodos que modificam conjuntos¶

O quadro abaixo elenca os principais métodos modificadores de um set.

Método	Descrição
`add(x)`	Adiciona o elemento `x` ao conjunto.
`remove(x)`	Remove `x`; lança erro se `x` não existir.
`discard(x)`	Remove `x`; não lança erro se `x` não existir.
`pop()`	Remove e retorna um elemento arbitrário.
`clear()`	Remove todos os elementos do conjunto.

pares = {0,2,4,6,8} # conjunto dos números pares menores que 10

pares.add(10) # adiciona o elemento 10
print(pares)

pares.remove(4) # remove o elemento 4
print(pares)

pares.discard(12)  # não gera erro
# pares.remove(12)  # gera erro

print(pares.pop()) # remove e retorna um elemento arbitrário

print(pares.clear()) # esvazia o conjunto

{0, 2, 4, 6, 8, 10}
{0, 2, 6, 8, 10}
0
None

Uma consequência importante da mutabilidade¶

Por serem mutáveis, um set não pode ser colocado dentro de outro set. Neste sentido, não conseguimos representar de imediato, algo como $\{ 1, \{ 2, 3 \} \}$ , perfeitamente aceitável na Matemática. A solução que trata essa divergência entre Matemática e Computação é frozenset, um tipo de dado que cria um conjunto imutável.

A = {frozenset({1}), frozenset({2,3})}
A

{frozenset({1}), frozenset({2, 3})}

A = frozenset({0,2,4,6,8}) # conjunto dos números pares menores que 10
A.add(10) # gera erro

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[41], line 2
      1 A = frozenset({0,2,4,6,8}) # conjunto dos números pares menores que 10
----> 2 A.add(10) # gera erro

AttributeError: 'frozenset' object has no attribute 'add'

Unicidade de conjuntos¶

Um set preserva a unicidade dos elementos. Isto significa que, internamente, ele realiza um “mapeamento” para no máximo uma ocorrência daquele elemento. Logo, set é a estrutura adequada a se usar quando não queremos repetição.

X = set() # conjunto vazio
X.add(0) # adiciona o elemento 0
X.add(0) # tenta adicionar o elemento 0 novamente
print(X) # unicidade preservada

{0}

Y = {0,0,0,1,1,2,2} # exemplo de unicidade preservada
Y

{0, 1, 2}

Não-ordenabilidade de conjuntos¶

Um set não preserva a ordem de inserção e não permite acessar elementos por posição (indexação). Ao percorrermos um set com um laço, por exemplo, os elementos do conjunto são acessados em uma ordem que:

não depende da ordem original;
pode mudar entre execuções;
pode mudar quando o set cresce.

# Execute este código 3 vezes, sempre limpando antes para observar a não-ordenabilidade
Y = {7, 2, 6, 3}
print(", ".join(str(y) for y in Y))        

Y.add(-1)
print(", ".join(str(y) for y in Y))        

Y.add(-10)
print(", ".join(str(y) for y in Y))        

Y.add(-2)
print(", ".join(str(y) for y in Y))

2, 3, 6, 7
2, 3, 6, 7, -1
2, 3, 6, 7, -10, -1
2, 3, 6, 7, -10, -2, -1

Casos de utilidade para `set`¶

Remoção de duplicatas de forma rápida:

_ = [1, 2, 2, 3, 4, 4, 4]
unicos = set(_)
unicos

{1, 2, 3, 4}

Testar pertinência (mais rápido que lista)

forbidden = {"H2SO4", "H2S", "H2SO3"}
if "H2S" in forbidden:
    print("Item proibido!")

Item proibido!

Filtragem lógica (ver Exemplo Aplicado II)

esportes = {("futebol", 22), ("tênis", 6.7), ("basquete", 24), ("pingue-pongue", 4)}

limite = 10
selecionados = {nome for (nome, d) in esportes if d < limite}
selecionados

{'pingue-pongue', 'tênis'}

Quadro-resumo de operações elementares¶

O quadro abaixo lista as operações elementares com conjuntos que aprendemos e como executá-las em Python.

Operação	Símbolo matemático	Operador / Método em Python
Pertinência	$x \in A$	`x in A`
Não-pertinência	$x \notin A$	`x not in A`
Subconjunto	$A \subseteq B$	`A <= B`
Subconjunto próprio	$A \subset B$	`A < B`
Superconjunto	$A \supseteq B$	`A >= B`
Superconjunto próprio	$A \supset B$	`A > B`
Igualdade	$A = B$	`A == B`
Conjunto vazio	$\varnothing$	`set()`

Exercícios aplicados resolvidos¶

I. Identificar o vocabulário único de um arquivo de texto e contar palavras.

# Conteúdo de '1-texto.txt'.

A inteligência artificial está transformando a educação e a pesquisa em ciência de dados.
A pesquisa impulsiona novas descobertas.

Resolução¶

palavras = set()

with open("../examples/1-texto.txt", "r", encoding="utf-8") as f:
    for linha in f:
        for palavra in linha.lower().split():
            palavras.add(palavra.strip(".,;!?"))

print("Vocabulário distinto:", palavras)
print("Total de palavras únicas:", len(palavras))

Vocabulário distinto: {'dados', 'de', 'descobertas', 'está', 'transformando', 'impulsiona', 'artificial', 'em', 'ciência', 'novas', 'pesquisa', 'e', 'educação', 'inteligência', 'a'}
Total de palavras únicas: 15

Uma descrição matemática possível para o exemplo I é:

“Seja $T$ o conjunto de todas as palavras da Língua Portuguesa que aparecem no fragmento de texto dado e $U$ as palavras que aparecem apenas uma única vez. Determine o número de tais palavras.”

Este problema, teve como resultado o número inteiro $q = |U|$ , para $U = \{ u_i \in T : i \in \{ 1,2,\ldots, n\} \land q \leq n \}$ , com $n = |T|$ .

II. Capturar somente os esportes cujos diâmetros das bolsas ou discos são menores que um valor limite.

Resolução¶

# Dataframe com esportes e seus diâmetros padrão (em milímetros)
dados = {
    "esporte": ["Basquete", "Futebol", "Tênis", "Pingue-pongue", "Golfe", "Beisebol", "Hóquei"],
    "diametro_mm": [240, 220, 67, 40, 43, 74, 76]
    }

# Criação do dataframe
from pandas import DataFrame
df = DataFrame(dados)
df

# Valor do limitante (em milímetros)
L = 80 

# Filtragem dos esportes com diâmetro menor que L
E_L = set(df[df["diametro_mm"] < L]["esporte"])

E_L

{'Beisebol', 'Golfe', 'Hóquei', 'Pingue-pongue', 'Tênis'}

Uma descrição matemática possível para o exemplo II é:

“Seja $E$ o conjunto de todos os esportes registrados no banco de dados e $d$ o diâmetro da bola ou disco do esporte correspondente. Determine o subconjunto dos esportes para os quais $d$ é inferior a um valor determinado.”

Este problema, que se resume a uma filtragem, teve como resultado o conjunto $E_L= \{ e \in E : d(e) < L\}$ para $L= 80$ mm.

plt.rcdefaults()

Conjuntos

Conjuntos¶

Objetivos de aprendizagem¶

Teoria “ingênua” de conjuntos¶

Princípios de intuição¶

Elementos¶

Definição de conjuntos¶

Definição por extensão¶

Conjunto vazio¶

Conjunto unitário¶

Conjunto arbitrário¶

Pertinência¶

Continência¶

Igualdade¶

Cardinalidade¶

Definição por propriedade¶

Elementos e conjuntos como “objetos”¶

Mutabilidade de conjuntos¶

Métodos que modificam conjuntos¶

Uma consequência importante da mutabilidade¶

Unicidade de conjuntos¶

Não-ordenabilidade de conjuntos¶

Casos de utilidade para set¶

Quadro-resumo de operações elementares¶

Exercícios aplicados resolvidos¶

Resolução¶

Resolução¶

Casos de utilidade para `set`¶