Fondamenti dell'Informatica

Fondamenti dell'informatica

Cambiago Silvia

Anno Accademico 2021-2022

Prof. Ugo Emanuele Moscato

Insiemi, multinsiemi, sequenze

Dati 3 insiemi A={1,2,3}, B={1,2,1,3}, C={1,3,2}, risulta che A=B=C, in quanto ordine e molteplicità non costituiscono un parametro per distinguere gli insiemi.

Una t-upla (sequenza) di SQL non è considerabile insieme, in quanto nelle t-uple non si prescinde né dall’ordine né dalla molteplicità:

• A’=<1,A,1,B,C>
• B’=<1,A,B,1,C>

A’≠B’

In un multinsieme viene considerato invece il numero di occorrenze dello stesso elemento, ma non l’ordine degli elementi:

• A”= (1,2,3)
• B”=(1,2,1,3)
• C”=(2,1,1,3)

A”≠B” B”=C”

Dato il multinsieme D=(A,A,A,B,B,C), può essere scritto come D’=(3A,2B,1C).

Cardinalità insiemi

Dato un qualsiasi insieme A, la cardinalità di A (si indica con |A|) è definita come il numero di elementi che costituiscono l’insieme A.

Considerati gli insiemi A={1,2,3}, B={1,2,1,3}, C={1,3,2}, il multinsieme B”=(1,2,1,3) e la sequenza A’=<1,A,1,B,C>, le rispettive cardinalità sono:

• |A|=|B|=|C| = 3 non si tiene conto della molteplicità
• |B”| = 4 si tiene conto della molteplicità
• |A’| = 5 si tiene conto della molteplicità

Insiemi numerici

La definizione di numero naturale secondo Peano è la seguente: Gli altri insiemi numerici, estensioni di ℕ, sono ℤ (relativi), ℚ (razionali) e ℝ (reali).

Per quanto concerne la cardinalità, |ℕ| = |ℤ| = |ℚ| = ℵ₀. L’insieme ℝ ha invece cardinalità |ℝ| = 2^ℵ₀.

Dato che due insiemi hanno la stessa cardinalità se e solo se si può stabilire una relazione biunivoca tra loro, quindi se e solo se è possibile trovare una funzione che lega ℕ e ℤ biunivocamente. Tale funzione è: 2n + (n - 1). In ℕ, ℤ, ℚ esiste corrispondenza biunivoca, quindi la cardinalità rimane necessariamente uguale. Con ℝ non si verifica tale corrispondenza.

Insiemi: operazioni e classificazioni

Nel 1901 il matematico Bertrand Russell pose il problema noto oggi come paradosso di Russell. Secondo le teorie di Gottlob Frege, un insieme appartiene a se stesso quando è della sua stessa natura. Il problema sorge nel momento in cui si considera l’insieme degli insiemi che non appartengono a loro stessi: appartiene o no a se stesso?

Il paradosso di cui sopra si risolve considerando l'insieme prima citato non come insieme, ma come classe, definita come aggregato generico di oggetti.

Insieme delle parti

Per ogni insieme A si può definire l’insieme P(A), ossia l’insieme delle parti di A, quindi l’insieme di tutti i sottoinsiemi di A. Il numero di sottoinsiemi di un insieme di n elementi sarà logicamente 2ⁿ.

Prodotto cartesiano

Considerando due insiemi A e B, il prodotto cartesiano A×B di tali insiemi è definito come: Ha cardinalità pari al prodotto delle cardinalità di A e di B. Il prodotto cartesiano di A con se stesso per n volte è Aⁿ.

Partizione

Dato un insieme A, la partizione è un insieme di insiemi in cui ogni elemento di A deve appartenere alla partizione e l’intersezione tra gli elementi della partizione è nulla.

Differenza simmetrica

La differenza simmetrica fra due insiemi A e B, indicata con AΔB, è definita come:

Relazioni

Siano A,B due insiemi, R ⊆ A × B è una relazione binaria. Gli elementi della relazione sono sequenze ordinate <a,b> | a ∈ A, b ∈ B. La relazione potrebbe non coprire tutto il prodotto cartesiano. Es. R : ℕ × ℕ = {<5,7>, <1,3>, <21,74>, <2,5>, ...}

R ha arietà 2 su ℕ (numero di insiemi del prodotto cartesiano e natura, ossia il tipo degli elementi di R). È una relazione binaria definita su coppie di numeri naturali. R si potrebbe sostituire con <, in quanto vi sono contenute coppie di numeri dove il primo è strettamente minore del secondo. Se fosse ≤ si dovrebbero aggiungere <1,1>, <2,2>, ... (< ⊆ ≤).

Composizione di relazioni

Una relazione composta è definita come: {<a, b> | a ∈ A ∧ b ∈ B ∧ ∃p | <a, p> ∈ R ∧ <p, b> ∈ S} quindi un insieme di coppie <a,b> tali che a è un elemento del dominio che, inserito nella relazione, restituisce un certo valore p. Prendendo poi p e inserendolo nella relazione, esso restituisce b. <a,b> appartiene alla relazione composta.

Relazioni e funzioni

Il dominio di definizione è un sottoinsieme del prodotto cartesiano degli insiemi di partenza. + : ℕ × ℕ × ℕ = {<1,2,3>, <7,7,14>, <3,1,4>, <1,3,4>, ...}

Nella relazione di cui sopra, ovvero la relazione di somma, dati i primi 2 elementi, il terzo è unico. Una funzione è una particolare relazione che associa a un valore del dominio uno e un solo valore del codominio. Es. S : ℕ × ℕ = {<0,1>, <1,2>, <2,3>, <3,4>, ...} S: funzione che associa ad ogni numero il suo successore. Si noti come tutte le funzioni sono relazioni, ma non tutte le relazioni sono funzioni.

Funzioni: informazioni e sequenze di bit

Se si vogliono rappresentare informazioni, è intuitivo dedurre che si necessiterà di log₂ n bit. Dati n bit, le sequenze distinte di bit sono 2ⁿ.

Informazioni sequenze di bit

• I <000>0
• I <001>1
• I <010>2
• I <011>3
• I <100>4

Una funzione f : A → B, A ⊆ B può essere totale o parziale.

• Se ogni elemento di A è in coppia con al più un elemento di B la funzione è parziale, quindi se presenta valori per cui la funzione non è valida;
• Se a ogni elemento di A è associato un elemento di B la funzione è totale.

TOTALE: x-4 × ℕ → ℤ

FUNZIONE PARZIALE: x-4 × ℕ risulta totale solo in [4,+∞) × ℕ → ℕ

• Una funzione è biiettiva se è iniettiva, suriettiva e parziale;
• Una funzione è biunivoca se è iniettiva, suriettiva e totale.

Funzione caratteristica

Dati un insieme universo U e un insieme A ⊆ U, con un elemento x ∈ U, la funzione caratteristica è definita come:

Classificazione delle relazioni

Data una qualsiasi relazione R, può essere:

• Riflessiva: ∀x xRx (x è in relazione con se stessa)
• Irriflessiva: ∀x ¬xRx (x non è in relazione con se stessa)
• Simmetrica: ∀x,y se xRy allora yRx
• Asimmetrica: ∀x,y se xRy allora ¬yRx
• Antisimmetrica: ∀x,y se xRy ∧ yRx allora x=y
• Transitiva: ∀x,y,z se xRy ∧ yRz allora xRz
• Se una relazione è asimmetrica, allora è irriflessiva;
• Se una relazione è transitiva e irriflessiva, allora è asimmetrica;
• Se una relazione è asimmetrica allora è ...