Le proprietà delle operazioni tra gli insiemi

Le operazioni tra insiemi presentano alcune proprietà fondamentali.

Alcune proprietà trovano analogie nelle operazioni aritmetiche, come la proprietà commutativa, associativa e distributiva dell'unione e dell'intersezione.

Altre proprietà, invece, sono specifiche dell'algebra degli insiemi. Ad esempio, la proprietà di idempotenza, le leggi di assorbimento e le leggi di De Morgan.

La tabella delle proprietà

In questa tabella sono elencate le principali proprietà delle operazioni insiemistiche.

Proprietà	Espressione
Proprietà di idempotenza	\( A \cap A = A \) \( A \cup A = A \)
Proprietà commutativa dell'intersezione	\( A \cap B = B \cap A \)
Proprietà commutativa dell'unione	\( A \cup B = B \cup A \)
Proprietà associativa dell'intersezione	\( A \cap (B \cap C) = (A \cap B) \cap C \)
Proprietà associativa dell'unione	\( A \cup (B \cup C) = (A \cup B) \cup C \)
Leggi di assorbimento	\( A \cap (A \cup B) = A \) \( A \cup (A \cap B) = A \)
Proprietà distributiva dell'intersezione rispetto all'unione	\( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \)
Proprietà distributiva dell'unione rispetto all'intersezione	\( A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \)
Leggi di De Morgan	\( \overline{A \cap B} = \overline{A} \cup \overline{B} \) \( \overline{A \cup B} = \overline{A} \cap \overline{B} \)

Queste proprietà sono molto utili perché costituiscono la base per risolvere problemi usando l'algebra degli insiemi.

Ad esempio, sono utilizzate nei linguaggi di programmazione, nell'analisi combinatoria e nei modelli probabilistici. Un'altra importante applicazione delle proprietà insiemistiche si trova nell'analisi dei linguaggi formali e degli automi, dove operazioni come l'unione e l'intersezione sono essenziali per definire e trasformare linguaggi regolari e contesti grammaticali più complessi.

Proprietà di idempotenza

Questa proprietà afferma che se prendo un insieme \( A \) e lo "unisco" con se stesso (\( A \cup A \)), ottengo ancora \( A \).  $$ A \cup A = A $$ Allo stesso modo, se faccio l'intersezione di \( A \) con se stesso (\( A \cap A \)), il risultato è sempre \( A \). $$ A \cap A = A $$

L'operazione non cambia nulla, non aggiunge né toglie elementi, perché stai solo ripetendo la stessa cosa.

Ora, detta così sembra una banalità assoluta: se unisco l'insieme con se stesso, cosa vuoi che succeda? E' proprio questo il punto! Non succede nulla.

$$ A \cup A = A $$

Lo stesso accade se lo interseco con se stesso.

$$ A \cap A = A $$

La proprietà di idempotenza sembra ovvia ma, se ignorata, fa fare errori da principiante.

Nota. Ad esempio, questa proprietà è utile nella logica booleana quando devo semplificare le espressioni insiemistiche senza perdermi in calcoli inutili. Insomma, mi salva dal fare operazioni ridondanti e dal perdere tempo.

Esempio

Considero l'elenco di persone iscritte a un corso universitario, diciamo:

\[ A = \{ \text{Alice, Bob, Charlie} \} \]

Ora, per qualche strano motivo, cerco di unire l'elenco con sé stesso:

\[ A \cup A = \{ \text{Alice, Bob, Charlie} \} \cup \{ \text{Alice, Bob, Charlie} \} \]

Il risultato? Esattamente lo stesso elenco. Aggiungere di nuovo le stesse persone non cambia nulla. Al corso universitario sono iscritte sempre tre persone.

\[ A \cup A = \{ \text{Alice, Bob, Charlie} \} \]

Stesso discorso per l'intersezione:

\[ A \cap A = \{ \text{Alice, Bob, Charlie} \} \cap \{ \text{Alice, Bob, Charlie} \} \]

Ovviamente il risultato è ancora \( A \), perché sto cercando gli elementi in comune tra due insiemi che sono identici.

\[ A \cap A = \{ \text{Alice, Bob, Charlie} \} \]

In parole povere, unire o intersecare un insieme con sé stesso è come cercare di raddoppiare il numero di scarpe nell'armadio dicendo due volte la lista di quelle che possiedo.

Leggi di assorbimento

La legge di assorbimento afferma che l’intersezione di un insieme con un’espressione che lo contiene è l’insieme stesso. \[ A \cap (A \cup B) = A \] Inoltre, l’unione di un insieme con un’espressione che ne è parte è ancora l’insieme stesso. \[ A \cup (A \cap B) = A \]

In altre parole, aggiungere elementi già inclusi o rimuovere elementi che non cambiano nulla è inutile: l’insieme rimane invariato.

Si chiamano "leggi di assorbimento" perché, in entrambe le operazioni, l’insieme \( A \) assorbe l’effetto dell’unione o dell’intersezione con l’altro insieme \( B \), rendendolo irrilevante nel risultato finale.

Ad esempio, neell’intersezione: \( A \cap (A \cup B) = A \) l'insieme \( A \) "assorbe" \( B \) perché l’intersezione con \( A \cup B \) non aggiunge nulla di nuovo rispetto ad \( A \). Nell’unione \( A \cup (A \cap B) = A \), invece, l'insieme \( A \) "assorbe" \( A \cap B \), perché aggiungere una parte di \( A \) è ridondante.

Esempio

L'insieme \( A \) rappresenta il gruppo di studenti che hanno superato un esame, e l'insieme \( B \) il gruppo di studenti che hanno provato l’esame indipendentemente dal risultato (promossi o bocciati).

1] Prima legge di assorbimento

La prima legge di assorbimento afferma \( A \cap (A \cup B) = A \)

Dove \( A \cup B \) è l’insieme di tutti gli studenti che hanno provato l'esame, sia promossi che bocciati.

Quindi, l'operazione \( A \cap (A \cup B) \) prende solo gli studenti che sono sia in \( A \) che in \( A \cup B \).

Il risultato è ancora solo \( A \), perché chi ha superato l’esame è già presente in \( A \cup B \), l’esistenza del gruppo \( B \) non influisce.

2] Seconda legge di assorbimento

La seconda legge di assorbimento afferma che \( A \cup (A \cap B) = A \)

Dove \( A \cap B \) sono gli studenti che hanno superato l'esame (\( A \)) e che, ovviamente, fanno parte del gruppo di chi ha provato l'esame (\( B \)).

Quindi il risultato è sempre l'insieme \( A \).

$$ (A \cap B) = A $$

Se poi unisco il risultato con l'insieme \( A \), ottengo sempre \( A \)! Ho ribadito l’ovvio.

$$  A \cup (A \cap B) = A \cup A = A $$

La legge di assorbimento è uno strumento utile per semplificare le espressioni inutilmente ridondanti e non complicarsi la vita nei calcoli.

La proprietà distributiva dell'intersezione rispetto all'unione

La proprietà distributiva dell’intersezione rispetto all’unione afferma che intersecare un insieme con l’unione di due insiemi equivale a unire le intersezioni dello stesso insieme con ciascuno dei due insiemi separatamente, ovvero:  \[
A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \]

E' una di quelle proprietà che sembrano complicate ma che, in realtà, dicono solo che l’intersezione si può distribuire sull’unione, un po’ come la moltiplicazione si distribuisce sulla somma in aritmetica.

L’idea è che, invece di fare prima l’unione e poi l’intersezione con \( A \), posso prima fare l’intersezione separata di \( A \) con \( B \) e \( A \) con \( C \), e poi unirne i risultati.

Esempio

Considero tre insiemi \( A \) , \( B \) e \( C \)

• \( A \) è l’insieme degli studenti che hanno preso almeno 18 all’esame di algebra lineare.
• \( B \) è l’insieme degli studenti iscritti alla facoltà di matematica
• \( C \) è l’insieme degli studenti iscritti alla facoltà di informatica

Ora voglio trovare tutti gli studenti che hanno passato l’esame di algebra lineare e sono iscritti a matematica o informatica.

Uso entrambi i lati della formula per vedere cosa succede:

1] Svolgo il lato sinistro: \( A \cap (B \cup C) \)

Prima svolgo l'unione \( B \cup C \), cioè prendo tutti gli studenti di matematica e informatica.

Poi interseco il risultato con \( A \), dove ci sono gli studenti che hanno preso almeno 18 all’esame di algebra lineare.

Il risultato è l'insieme degli studenti che hanno superato l’esame e sono iscritti a uno dei due corsi.

2] Svolgo il lato destro: \( (A \cap B) \cup (A \cap C) \)

Prima trovo \( A \cap B \), cioè gli studenti che hanno superato l’esame di algebra lineare e sono iscritti a matematica.

Poi trovo l'intersezione \( A \cap C \), cioè quelli che hanno superato lo stesso esame e sono iscritti a Informatica.

Infine, unisco i risultati e ottengo l'insieme degli studenti che hanno superato l’esame e appartengono almeno a uno dei due corsi.

In entrambi i casi il risultato finale è lo stesso.

La proprietà distributiva dell’unione rispetto all’intersezione

La proprietà distributiva dell’unione rispetto all’intersezione afferma che l’unione di un insieme con l’intersezione di due insiemi equivale all’intersezione delle unioni dello stesso insieme con ciascuno dei due insiemi separatamente. \[ A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\]

L’idea è che prima unire e poi intersecare è equivalente a prima intersecare e poi unire.

In pratica, invece di prendere \( A \) e unirlo a \( B \cap C \) tutto insieme, posso distribuire l’unione su entrambi i termini di \( B \cap C \), fare le operazioni separatamente e poi intersecare i risultati.

Esempio

Considero tre insiemi \( A \) , \( B \) e \( C \)

• \( A \) è l’insieme degli studenti che hanno una borsa di studio.
• \( B \) è l’insieme degli studenti iscritti alla facoltà di matematica.
• \( C \) è l’insieme degli studenti iscritti alla facoltà di informatica.

Ora voglio trovare tutti gli studenti che hanno una borsa di studio oppure sono iscritti a entrambi i corsi (matematica e informatica).

Usiamo entrambi i lati della formula:

1] Svolgo il lato sinistro: \( A \cup (B \cap C) \)

Prima interseco gli insiemi \( B \cap C \), cioè prendo gli studenti iscritti a entrambi i corsi.

Poi unisco il risultato con \( A \), quindi aggiungo anche tutti gli studenti con la borsa di studio.

Il risultato è un insieme con gli studenti che hanno una borsa di studio oppure sono iscritti a entrambi i corsi.

2] Svolgo il lato destro: \( (A \cup B) \cap (A \cup C) \)

Prima trovo l'unione \( A \cup B \), cioè gli studenti con la borsa di studio o iscritti a matematica.

Poi trovo l'unione \( A \cup C \), cioè gli studenti con la borsa di studio o iscritti a informatica.

Infine, interseco i due insiemi e ottengo gli studenti che hanno la borsa di studio oppure sono iscritti a entrambi i corsi.

In entrambi i casi il risultato è identico.

Le leggi di De Morgan

Le leggi di De Morgan servono a dire che la negazione di un’operazione logica può essere espressa con un’operazione opposta tra le negazioni dei singoli elementi. Le formule sono:  \[ \overline{A \cap B} = \overline{A} \cup \overline{B} \] \[ \overline{A \cup B} = \overline{A} \cap \overline{B} \]

Ma cosa significano in pratica? Probabilmente sono le proprietà meno intuitive degli insiemi.

In parole povere, le leggi di De Morgan dicono che negare un’intersezione equivale a unire le negazioni, mentre negare un’unione equivale a intersecare le negazioni.

È come dire che negare di amare sia il caffè che il tè significa che odi almeno uno dei due; mentre negare di amare il caffè o il tè significa che li odi entrambi.

Per capire meglio faccio un esempio concreto.

Esempio pratico

Considero un ristorante che serve solo due tipi di piatti principali:

- \( A \): Pizza
- \( B \): Pasta

Ora supponiamo di voler descrivere in due modi diversi il gruppo di persone che non vogliono né pizza né pasta.

Secondo la prima legge di De Morgan vale la seguente formula:

$$ \overline{A \cap B} = \overline{A} \cup \overline{B} $$

La parte sinistra dell'equazione, \( \overline{A \cap B} \), significa "tutti quelli che non vogliono né la pizza, né la pasta".

Nota. L'intersezione $ A \cap B $ include tutte le persone che amano sia la pizza che la pasta. Pertanto, la sua negazione è l'insieme di persone che non vogliono entrambe le cose $ \overline{A \cap B} $. E' sufficiente non desiderare uno dei due piatti per essere in questo insieme.

L'insieme di quelli che non vogliono pizza ( \( \overline{A} \) ) oppure non vogliono pasta ( \( \overline{B} \) ) posso anche riscriverlo come:

\[ \overline{A} \cup \overline{B} \]

Le due espressioni danno lo stesso risultato.

Secondo la seconda legge di De Morgan vale questa formula

$$ \overline{A \cup B} = \overline{A} \cap \overline{B} $$

In questo caso, la parte sinistra dell’equazione, \( \overline{A \cup B} \), significa "tutti quelli che non vogliono né pizza né pasta".

Poiché sono quelli che non vogliono la pizza e contemporaneamente non vogliono la pasta, posso identificarli scrivendo questa espressione:

$$ \overline{A} \cap \overline{B} $$

Dove \( \overline{A} \) sono le persone che "non vogliono la pizza" mentre  \( \overline{B} \) sono quelle che "non vogliono la pasta".

L'intersezione $ \overline{A} \cap \overline{B} $ restituisce gli elementi in comune, ossia le persone che non vogliono né la pizza, né la pasta..

E così via.