Fondamenti di informatica - Laurea triennale Informatica/Elementi di insiemistica
Il concetto di insieme
[modifica | modifica sorgente]Un insieme è una collezione di oggetti chiamati elementi (o membri).
Un insieme è determinato solo dai suoi elementi e non dall’ordine con cui vengono elencati.
Gli elementi si considerano distinti: eventuali ripetizioni in un elenco non cambiano l’insieme.
Come si descrive un insieme
[modifica | modifica sorgente]Se l’insieme è finito e piccolo, si può descrivere per elenco, scrivendo tutti gli elementi tra parentesi graffe.
Se l’insieme è grande o infinito, si descrive indicando una proprietà di appartenenza.
Notazione per comprensione (set-builder notation)
Si usa la forma con la barra verticale “|”, letta “tale che”, per esprimere la proprietà necessaria: la proprietà viene scritta dopo la barra. (esempio: A{x|x è intero e positivo})
Tipi di elementi e insiemi di insiemi
[modifica | modifica sorgente]Un insieme può contenere elementi di qualunque tipo (numeri, persone, oggetti, ecc.), anche di natura diversa tra loro.
Un insieme può contenere come elementi altri insiemi, costruendo strutture più articolate.
Insiemi numerici principali
[modifica | modifica sorgente]Gli insiemi più comuni sono ℤ (interi), ℚ (razionali) e ℝ (reali).
I razionali sono quozienti di interi, mentre i reali si rappresentano come punti sulla retta reale che si estende indefinitamente.
Notazioni per segno e intervalli
Per indicare sottoinsiemi come numeri negativi, positivi o non negativi si usano notazioni dedicate (ad esempio con apici “−”, “+”, ecc.).
Cardinalità
[modifica | modifica sorgente]Per un insieme finito A, la cardinalità è il numero di elementi e si indica con ∣A∣.
Per insiemi infiniti esiste una nozione analoga (ad esempio la cardinalità di ℤ è ℵ0),
Appartenenza ed insieme vuoto
[modifica | modifica sorgente]Per indicare appartenenza si usa x∈A, mentre per non appartenenza x∈/A.
L’insieme senza elementi si chiama insieme vuoto e si indica con ∅.
Uguaglianza tra insiemi
[modifica | modifica sorgente]Due insiemi sono uguali (A=B) se hanno esattamente gli stessi elementi.
Formalmente bisogna mostrare doppia inclusione: ogni elemento di A è in B e ogni elemento di B è in A.
Non uguaglianza
Per dimostrare A!=B basta un controesempio: un elemento che sta in uno ma non nell’altro.
Sottoinsiemi: inclusione e proprietà
Si dice A⊆B se ogni elemento di A appartiene anche a B.
Ogni insieme è sottoinsieme di sé stesso e ∅ è sottoinsieme di ogni insieme.
Differenza tra “elemento” e “sottoinsieme”
È cruciale distinguere 1 da {1}: un numero può essere elemento, mentre un insieme può essere sottoinsieme.
Sottoinsieme proprio
Si scrive A⊂B quando A⊆B ma A!=B.
Esempi classici: ℤ ⊂ ℚ e ℚ ⊂ ℝ, perché ogni intero è razionale e ogni razionale è reale, ma non vale il contrario.
Insieme delle parti (power set)
L’insieme di tutti i sottoinsiemi di A si indica con P(A).
Se A ha n elementi, allora ∣P(A)∣=2n.
Operazioni fondamentali tra insiemi
[modifica | modifica sorgente]L’unione A∪B contiene gli elementi che stanno in A o in B (o in entrambi).
L’intersezione A∩B contiene gli elementi comuni a A e B.
La differenza A∖B contiene gli elementi che stanno in A ma non in B.
Esempio: numeri irrazionali
Gli irrazionali si possono definire come R∖Q: reali che non sono razionali.
Famiglie di insiemi e disgiunzione
Una collezione di insiemi è una famiglia di insiemi.
Due insiemi sono disgiunti se A∩B=∅.
Una famiglia è a due a due disgiunta se ogni coppia di insiemi distinti è disgiunta.
Insieme universo e complemento
Quando si lavora dentro un insieme più grande U, questo si chiama universo.
Il complemento di A è Ac=U∖A.
Dipendenza dall’universo
Il complemento cambia se cambia l’universo U: è un punto concettuale essenziale.
Diagrammi di Venn
[modifica | modifica sorgente]I diagrammi di Venn visualizzano insiemi e operazioni: l’universo è un rettangolo e i sottoinsiemi sono cerchi.
Le regioni rappresentano: elementi in nessuno, solo in uno, o in entrambi (e analogamente per tre insiemi).
Applicazioni al conteggio
Con tre insiemi si risolvono problemi tipici (ad esempio studenti iscritti a più corsi) distribuendo i numeri nelle regioni corrette.
Proprietà e leggi degli insiemi
[modifica | modifica sorgente]Si raccolgono leggi importanti: associative, commutative, distributive, leggi di identità, complemento, assorbimento, e le leggi di De Morgan.
Molte possono essere comprese e controllate anche con diagrammi di Venn, mentre le dimostrazioni formali vengono rimandate.
Unione e intersezione di collezioni
L’unione di una famiglia contiene gli elementi che stanno in almeno uno degli insiemi della famiglia.
L’intersezione di una famiglia contiene gli elementi che stanno in tutti gli insiemi della famiglia.
Partizioni
Una partizione di A è una collezione di sottoinsiemi non vuoti, a due a due disgiunti, la cui unione è A.
Ogni elemento di A deve appartenere a uno e un solo blocco della partizione.
Ordine: coppie ordinate e prodotto cartesiano
Gli insiemi non considerano l’ordine, ma una coppia ordinata (a,b) in generale è diversa da (b,a).
Il prodotto cartesiano A×B è l’insieme di tutte le coppie (a,b) con a∈A e b∈B.
Cardinalità del prodotto
Se A e B sono finiti, allora ∣A×B∣=∣A∣⋅∣B∣.
L’idea si estende alle n-uple e ai prodotti di più insiemi, utili per elencare combinazioni (come menu: antipasto–secondo–dolce).
Suggerimenti di problem solving
[modifica | modifica sorgente]Per dimostrare uguaglianza tra insiemi si usa la doppia inclusione.
Per dimostrare non uguaglianza basta un controesempio.
Per verificare un’inclusione si parte dalla definizione; per negarla basta trovare un elemento in A che non è in B.
I diagrammi di Venn aiutano a intuire relazioni e a controllare rapidamente se un’affermazione è plausibile prima della dimostrazione formale.