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 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) 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 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