Matematica discreta - Insiemi
Matematico tedesco G. Cantorha introdotto il concetto di set. Aveva definito un insieme come una raccolta di oggetti definiti e distinguibili selezionati per mezzo di determinate regole o descrizioni.
Setla teoria costituisce la base di molti altri campi di studio come la teoria dei conteggi, le relazioni, la teoria dei grafi e le macchine a stati finiti. In questo capitolo tratteremo i diversi aspetti diSet Theory.
Set - Definizione
Un set è una raccolta non ordinata di elementi diversi. Un set può essere scritto esplicitamente elencando i suoi elementi usando la parentesi di set. Se l'ordine degli elementi viene modificato o viene ripetuto qualsiasi elemento di un set, non vengono apportate modifiche al set.
Alcuni esempi di set
- Un insieme di tutti i numeri interi positivi
- Un insieme di tutti i pianeti del sistema solare
- Un insieme di tutti gli stati dell'India
- Un insieme di tutte le lettere minuscole dell'alfabeto
Rappresentazione di un set
Gli insiemi possono essere rappresentati in due modi:
- Elenco o forma tabulare
- Imposta la notazione del costruttore
Elenco o forma tabulare
L'insieme è rappresentato elencando tutti gli elementi che lo compongono. Gli elementi sono racchiusi tra parentesi graffe e separati da virgole.
Example 1 - Set di vocali in alfabeto inglese, $ A = \ lbrace a, e, i, o, u \ rbrace $
Example 2 - Insieme di numeri dispari inferiori a 10, $ B = \ lbrace 1,3,5,7,9 \ rbrace $
Imposta la notazione del costruttore
L'insieme è definito specificando una proprietà che gli elementi dell'insieme hanno in comune. L'insieme è descritto come $ A = \ lbrace x: p (x) \ rbrace $
Example 1 - L'insieme $ \ lbrace a, e, i, o, u \ rbrace $ è scritto come -
$ A = \ lbrace x: \ text {x è una vocale in alfabeto inglese} \ rbrace $
Example 2 - L'insieme $ \ lbrace 1,3,5,7,9 \ rbrace $ è scritto come -
$ B = \ lbraccia x: 1 \ le x \ lt 10 \ e \ (x \% 2) \ ne 0 \ rbrace $
Se un elemento x è un membro di qualsiasi insieme S, è denotato da $ x \ in S $ e se un elemento y non è un membro dell'insieme S, è denotato da $ y \ non in S $.
Example- Se $ S = \ lbrace1, 1.2, 1.7, 2 \ rbrace, 1 \ in S $ ma $ 1.5 \ non in S $
Alcuni set importanti
N - l'insieme di tutti i numeri naturali = $ \ lbrace1, 2, 3, 4, ..... \ rbrace $
Z - l'insieme di tutti i numeri interi = $ \ lbrace ....., -3, -2, -1, 0, 1, 2, 3, ..... \ rbrace $
Z+ - l'insieme di tutti i numeri interi positivi
Q - l'insieme di tutti i numeri razionali
R - l'insieme di tutti i numeri reali
W - l'insieme di tutti i numeri interi
Cardinalità di un set
La cardinalità di un insieme S, indicata con $ | S | $, è il numero di elementi dell'insieme. Il numero è indicato anche come numero cardinale. Se un insieme ha un numero infinito di elementi, la sua cardinalità è $ \ infty $.
Example- $ | \ lbraccia 1, 4, 3, 5 \ rbrace | = 4, | \ lbrace 1, 2, 3, 4, 5, \ dots \ rbrace | = \ infty $
Se ci sono due insiemi X e Y,
$ | X | = | Y | $ denota due insiemi X e Y aventi la stessa cardinalità. Si verifica quando il numero di elementi in X è esattamente uguale al numero di elementi in Y. In questo caso, esiste una funzione biiettiva "f" da X a Y.
$ | X | \ le | Y | $ denota che la cardinalità dell'insieme X è minore o uguale alla cardinalità dell'insieme Y. Si verifica quando il numero di elementi in X è minore o uguale a quello di Y. Qui esiste una funzione iniettiva 'f' da X a Y.
$ | X | \ lt | Y | $ denota che la cardinalità dell'insieme X è minore della cardinalità dell'insieme Y. Si verifica quando il numero di elementi in X è inferiore a quello di Y. Qui, la funzione 'f' da X a Y è una funzione iniettiva ma non biiettiva.
$ Se \ | X | \ le | Y | $ e $ | X | \ ge | Y | $ poi $ | X | = | Y | $. Gli insiemi X e Y sono comunemente indicati come insiemi equivalenti.
Tipi di set
I set possono essere classificati in molti tipi. Alcuni dei quali sono finiti, infiniti, sottoinsiemi, universali, propri, singoli, ecc.
Insieme finito
Un insieme che contiene un numero definito di elementi è chiamato insieme finito.
Example- $ S = \ lbrace x \: | \: x \ in N $ e $ 70 \ gt x \ gt 50 \ rbrace $
Set infinito
Un insieme che contiene un numero infinito di elementi è chiamato un insieme infinito.
Example- $ S = \ lbrace x \: | \: x \ in N $ e $ x \ gt 10 \ rbrace $
Sottoinsieme
Un insieme X è un sottoinsieme dell'insieme Y (scritto come $ X \ subseteq Y $) se ogni elemento di X è un elemento dell'insieme Y.
Example 1- Siano $ X = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ e $ Y = \ lbrace 1, 2 \ rbrace $. Qui l'insieme Y è un sottoinsieme dell'insieme X poiché tutti gli elementi dell'insieme Y sono nell'insieme X. Quindi, possiamo scrivere $ Y \ subseteq X $.
Example 2- Siano $ X = \ lbrace 1, 2, 3 \ rbrace $ e $ Y = \ lbrace 1, 2, 3 \ rbrace $. Qui l'insieme Y è un sottoinsieme (non un sottoinsieme appropriato) dell'insieme X poiché tutti gli elementi dell'insieme Y sono nell'insieme X. Quindi, possiamo scrivere $ Y \ subseteq X $.
Sottoinsieme proprio
Il termine "sottoinsieme proprio" può essere definito come "sottoinsieme di ma non uguale a". Un insieme X è un sottoinsieme appropriato dell'insieme Y (scritto come $ X \ sottoinsieme Y $) se ogni elemento di X è un elemento dell'insieme Y e $ | X | \ lt | Y | $.
Example- Siano $ X = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ e $ Y = \ lbrace 1, 2 \ rbrace $. Qui imposta $ Y \ sottoinsieme X $ poiché tutti gli elementi in $ Y $ sono contenuti anche in $ X $ e $ X $ ha almeno un elemento è più di $ Y $ impostato.
Set universale
È una raccolta di tutti gli elementi in un particolare contesto o applicazione. Tutti gli insiemi in quel contesto o applicazione sono essenzialmente sottoinsiemi di questo insieme universale. Gli insiemi universali sono rappresentati come $ U $.
Example- Possiamo definire $ U $ come l'insieme di tutti gli animali sulla terra. In questo caso, l'insieme di tutti i mammiferi è un sottoinsieme di $ U $, l'insieme di tutti i pesci è un sottoinsieme di $ U $, l'insieme di tutti gli insetti è un sottoinsieme di $ U $ e così via.
Insieme vuoto o insieme nullo
Un set vuoto non contiene elementi. È indicato da $ \ emptyset $. Poiché il numero di elementi in un insieme vuoto è finito, l'insieme vuoto è un insieme finito. La cardinalità dell'insieme vuoto o dell'insieme nullo è zero.
Example- $ S = \ lbrace x \: | \: x \ in N $ e $ 7 \ lt x \ lt 8 \ rbrace = \ emptyset $
Set Singleton o Set di unità
L'insieme singleton o l'insieme di unità contiene solo un elemento. Un insieme singleton è indicato da $ \ lbrace s \ rbrace $.
Example- $ S = \ lbrace x \: | \: x \ in N, \ 7 \ lt x \ lt 9 \ rbrace $ = $ \ lbrace 8 \ rbrace $
Set uguale
Se due insiemi contengono gli stessi elementi si dice che sono uguali.
Example - Se $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 6, 1, 2 \ rbrace $, sono uguali in quanto ogni elemento dell'insieme A è un elemento dell'insieme B e ogni elemento dell'insieme B è un elemento dell'insieme A.
Set equivalente
Se le cardinalità di due insiemi sono le stesse, vengono chiamate insiemi equivalenti.
Example- Se $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 16, 17, 22 \ rbrace $, sono equivalenti in quanto la cardinalità di A è uguale alla cardinalità di B. cioè $ | A | = | B | = 3 $
Set sovrapposti
Due insiemi che hanno almeno un elemento comune sono chiamati insiemi sovrapposti.
In caso di serie sovrapposte -
$ n (A \ cup B) = n (A) + n (B) - n (A \ cap B) $
$ n (A \ cup B) = n (A - B) + n (B - A) + n (A \ cap B) $
$ n (A) = n (A - B) + n (A \ cap B) $
$ n (B) = n (B - A) + n (A \ cap B) $
Example- Siano $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 6, 12, 42 \ rbrace $. C'è un elemento comune "6", quindi questi insiemi sono insiemi sovrapposti.
Insieme disgiunto
Due insiemi A e B sono chiamati insiemi disgiunti se non hanno nemmeno un elemento in comune. Pertanto, gli insiemi disgiunti hanno le seguenti proprietà:
$ n (A \ cap B) = \ emptyset $
$ n (A \ cup B) = n (A) + n (B) $
Example - Sia $ A = \ lbrace 1, 2, 6 \ rbrace $ e $ B = \ lbrace 7, 9, 14 \ rbrace $, non c'è un singolo elemento comune, quindi questi insiemi sono insiemi sovrapposti.
Diagrammi di Venn
Il diagramma di Venn, inventato nel 1880 da John Venn, è un diagramma schematico che mostra tutte le possibili relazioni logiche tra diversi insiemi matematici.
Examples
![](https://assets.edu.lat/discrete_mathematics/images/venn_diagram.jpg)
Imposta operazioni
Le operazioni di gruppo includono Unione di gruppi, Intersezione di gruppo, Differenza di gruppo, Complemento di gruppo e Prodotto cartesiano.
Set Union
L'unione degli insiemi A e B (indicata con $ A \ cup B $) è l'insieme di elementi che si trovano in A, in B, o sia in A che in B. Quindi, $ A \ cup B = \ lbrace x \: | \: x \ in A \ OR \ x \ in B \ rbrace $.
Example- Se $ A = \ lbrace 10, 11, 12, 13 \ rbrace $ e B = $ \ lbrace 13, 14, 15 \ rbrace $, allora $ A \ cup B = \ lbrace 10, 11, 12, 13, 14 , 15 \ rbraccia $. (L'elemento comune si verifica una sola volta)
![](https://assets.edu.lat/discrete_mathematics/images/set_union.jpg)
Imposta intersezione
L'intersezione degli insiemi A e B (indicata da $ A \ cap B $) è l'insieme di elementi che si trovano sia in A che in B. Quindi, $ A \ cap B = \ lbrace x \: | \: x \ in A \ AND \ x \ in B \ rbrace $.
Example - Se $ A = \ lbrace 11, 12, 13 \ rbrace $ e $ B = \ lbrace 13, 14, 15 \ rbrace $, allora $ A \ cap B = \ lbrace 13 \ rbrace $.
![](https://assets.edu.lat/discrete_mathematics/images/set_intersection.jpg)
Imposta differenza / complemento relativo
La differenza di insiemi degli insiemi A e B (indicata con $ A - B $) è l'insieme di elementi che si trovano solo in A ma non in B. Quindi, $ A - B = \ lbrace x \: | \: x \ in A \ AND \ x \ notin B \ rbrace $.
Example- Se $ A = \ lbrace 10, 11, 12, 13 \ rbrace $ e $ B = \ lbrace 13, 14, 15 \ rbrace $, allora $ (A - B) = \ lbrace 10, 11, 12 \ rbrace $ e $ (B - A) = \ lbrace 14, 15 \ rbrace $. Qui possiamo vedere $ (A - B) \ ne (B - A) $
![](https://assets.edu.lat/discrete_mathematics/images/set_difference.jpg)
Complemento di un set
Il complemento di un insieme A (indicato con $ A '$) è l'insieme di elementi che non sono nell'insieme A. Quindi, $ A' = \ lbrace x | x \ notin A \ rbrace $.
Più specificamente, $ A '= (U - A) $ dove $ U $ è un insieme universale che contiene tutti gli oggetti.
Example- Se $ A = \ lbrace x \: | \: x \ \: {appartiene \: a \: set \: di \: dispari \: interi} \ rbrace $ poi $ A '= \ lbrace y \: | \: y \ \: {non \: non \: appartiene \: a \: set \: di \: dispari \: interi} \ rbrace $
![](https://assets.edu.lat/discrete_mathematics/images/complement_set.jpg)
Prodotto cartesiano / Prodotto incrociato
Il prodotto cartesiano di n numero di insiemi $ A_1, A_2, \ dots A_n $ indicato come $ A_1 \ times A_2 \ dots \ times A_n $ può essere definito come tutte le possibili coppie ordinate $ (x_1, x_2, \ dots x_n) $ dove $ x_1 \ in A_1, x_2 \ in A_2, \ punti x_n \ in A_n $
Example - Se prendiamo due set $ A = \ lbrace a, b \ rbrace $ e $ B = \ lbrace 1, 2 \ rbrace $,
Il prodotto cartesiano di A e B è scritto come - $ A \ times B = \ lbrace (a, 1), (a, 2), (b, 1), (b, 2) \ rbrace $
Il prodotto cartesiano di B e A è scritto come - $ B \ times A = \ lbrace (1, a), (1, b), (2, a), (2, b) \ rbrace $
Power Set
Insieme di potenza di un insieme S è l'insieme di tutti i sottoinsiemi di S compreso l'insieme vuoto. La cardinalità di un insieme di potenze di un insieme S di cardinalità n è $ 2 ^ n $. Il set di alimentazione è indicato come $ P (S) $.
Example −
Per un insieme $ S = \ lbrace a, b, c, d \ rbrace $ calcoliamo i sottoinsiemi -
Sottoinsiemi con 0 elementi - $ \ lbrace \ emptyset \ rbrace $ (l'insieme vuoto)
Sottoinsiemi con 1 elemento: $ \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace c \ rbrace, \ lbrace d \ rbrace $
Sottoinsiemi con 2 elementi: $ \ lbrace a, b \ rbrace, \ lbrace a, c \ rbrace, \ lbrace a, d \ rbrace, \ lbrace b, c \ rbrace, \ lbrace b, d \ rbrace, \ lbrace c, d \ rbraccia $
Sottoinsiemi con 3 elementi: $ \ lbrace a, b, c \ rbrace, \ lbrace a, b, d \ rbrace, \ lbrace a, c, d \ rbrace, \ lbrace b, c, d \ rbrace $
Sottoinsiemi con 4 elementi: $ \ lbrace a, b, c, d \ rbrace $
Quindi, $ P (S) = $
$ \ lbrace \ quad \ lbrace \ emptyset \ rbrace, \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace c \ rbrace, \ lbrace d \ rbrace, \ lbrace a, b \ rbrace, \ lbrace a, c \ rbrace, \ lbrace a, d \ rbrace, \ lbrace b, c \ rbrace, \ lbrace b, d \ rbrace, \ lbrace c, d \ rbrace, \ lbrace a, b, c \ rbrace, \ lbrace a, b, d \ rbrace, \ lbrace a, c, d \ rbrace, \ lbrace b, c, d \ rbrace, \ lbrace a, b, c, d \ rbrace \ quad \ rbrace $
$ | P (S) | = 2 ^ 4 = 16 $
Note - Anche il power set di un set vuoto è un set vuoto.
$ | P (\ lbrace \ emptyset \ rbrace) | = 2 ^ 0 = 1 $
Partizionamento di un set
La partizione di un insieme, diciamo S , è una raccolta di n sottoinsiemi disgiunti, diciamo $ P_1, P_2, \ dots P_n $ che soddisfa le seguenti tre condizioni:
$ P_i $ non contiene l'insieme vuoto.
$ \ lbrack P_i \ ne \ lbrace \ emptyset \ rbrace \ for \ all \ 0 \ lt i \ le n \ rbrack $
L'unione dei sottoinsiemi deve essere uguale all'intero insieme originale.
$ \ lbrack P_1 \ cup P_2 \ cup \ dots \ cup P_n = S \ rbrack $
L'intersezione di due insiemi distinti è vuota.
$ \ lbrack P_a \ cap P_b = \ lbrace \ emptyset \ rbrace, \ for \ a \ ne b \ where \ n \ ge a, \: b \ ge 0 \ rbrack $
Example
Sia $ S = \ lbraccia a, b, c, d, e, f, g, h \ rbrace $
Un probabile partizionamento è $ \ lbrace a \ rbrace, \ lbrace b, c, d \ rbrace, \ lbrace e, f, g, h \ rbrace $
Un altro probabile partizionamento è $ \ lbrace a, b \ rbrace, \ lbrace c, d \ rbrace, \ lbrace e, f, g, h \ rbrace $
Numeri di campana
I numeri di campana forniscono il conteggio del numero di modi per partizionare un set. Sono indicati con $ B_n $ dove n è la cardinalità dell'insieme.
Example -
Sia $ S = \ lbraccia 1, 2, 3 \ rbrace $, $ n = | S | = 3 $
Le partizioni alternative sono:
1. $ \ emptyset, \ lbrace 1, 2, 3 \ rbrace $
2. $ \ lbrace 1 \ rbrace, \ lbrace 2, 3 \ rbrace $
3. $ \ lbrace 1, 2 \ rbrace, \ lbrace 3 \ rbrace $
4. $ \ lbrace 1, 3 \ rbrace, \ lbrace 2 \ rbrace $
5. $ \ lbrace 1 \ rbrace, \ lbrace 2 \ rbrace, \ lbrace 3 \ rbrace $
Quindi $ B_3 = 5 $