Ordinamento



E' fondamentale in informatica considerare l'ordine in cui vengono date le informazioni: ho gia' detto che, semplificando, e' come un lungo nastro di dati che scorre davanti ad un lettore, di conseguenza i dati dovranno essere ordinati per poter essere utilizzati
Ripartiamo dal concetto di relazione d'ordine e vediamo il concetto di ordine parziale
Diremo che una relazione R su un insieme A e' una relazione di ordine se e'
  • riflessiva
  • antisimmetrica
  • transitiva

E qui sarebbe meglio ripassare tutto il capitolo sulle relazioni

Diremo che una relazione e' di ordine totale su un insieme B se dati comunque due elementi a e b appartenenti a B vale sempre
o aRb oppure bRa
Cioe' tutti gli elementi sono confrontabili fra loro secondo la relazione
esempio: l'insieme dei numeri naturali N con la relazione < e' un insieme totalmente ordinato perche' per due qualunque numeri naturali a e b posso sempre dire se vale a<b oppure b<a
se pero' esistono elementi di B fra loro non confrontabili secondo la relazione allora la relazione si dice di ordine parziale e l'insieme B si dice parzialmente ordinato
L'insieme degli esseri umani con la relazione "e' antenato o identico di" e' solo di ordine parziale perche' due che siano fratelli non appartengono alla relazione
ripassiamo le relazioni nei particolari
  1. riflessiva:
    a ≤ a    ∀ a ∈ B
    Si legge a e' minore od uguale ad a per ogni elemento a appartenente a B
    cioe', in B ogni elemento e' minore od uguale a se' stesso (oppure, che e' la stessa cosa, non e' superiore a se' stesso)
  2. antisimmetrica:
    se a≤b e b≤a ⇒ a=b    ∀ a,b ∈ B
    Si legge: se a e' minore od uguale a b e b e' minore od uguale ad a, allora a e' uguale a b per ogni coppia di elementi a,b appartenenti a B
    cioe' se a non e' maggiore di b e b non e' maggiore di a allora a e b sono uguali
  3. transitiva:
    a≤b, b≤c ⇒ a≤c    ∀ a,b,c ∈ B
    Si legge se a e' minore od uguale a b e b e' minore od uguale a c allora a e' minore od uguale a c per ogni terna di elementi a,b,c appartenenti a B


Le algebre di Boole sono parzialmente ordinate a causa del teorema:

Sia B un' algebra di Boole, allora B e' un insieme parzialmente ordinato con a≤b se e solo se a+b=b

Dimostriamolo "alla buona" con una dimostrazione non rigorosa, ma efficace, valida solo per l'algebra binaria di Boole (abbiamo solo gli elementi 0 ed 1)
La condizione e' necessaria e sufficiente (corrisponde a se e solo se) prima consideriamo la dimostrazione diretta

Ipotesi: supponiamo che nell'algebra binaria valga a + b = b
tesi: devo dimostrare che vale a ≤ b

l'ipotesi significa: 0 + 0 = 0;   0 + 1 = 1;   1 + 1 = 1
cioe' la somma equivale al secondo addendo se sono contemporaneamente nulli entrambe gli addendi oppure se il secondo addendo vale 1
di conseguenza segue per ogni elemento a (che puo' essere 0 od 1
se a=0 e se b=0    0 ≤ 0 cioe' a ≤ b
se a=0 e se b=1    0 ≤ 1 cioe' a ≤ b
se a=1 e se b=1     1 ≤ 1 cioe' a ≤ b
quindi
a ≤ b

Dimostrazione inversa

Ipotesi: supponiamo che in B valga a ≤ b
tesi: devo dimostrare che vale a + b = b

gli unici elementi dell'insieme B sono 0 ed 1
Vale: 0 ≤ 0,   0 ≤ 1,   1 ≤ 1,
quindi si ha, considerando i casi possibili
se a=0 e se b=0 0+0=0=a+b=b
se a=0 e se b=1 0+1=1=a+b=b
se a=1 e se b=1 1+1=1=a+b=b
(a=1 e b=0 non lo posso considerare perche' contrario all'ipotesi)
il che equivale a dire
a + b = b
come volevamo