precursori della formalizzazione logica: da Aristotele a Leibniz

• teoria del sillogismo: forme valide del ragionamento
• la visione di Leibniz: Mathesis Rationis

Leibniz anticipa di un paio di secoli l'intuizione di George Boole: le leggi di un'algebra del pensiero

• ma cos'è un'algebra ?

in prima approssimazione: un insieme + operazioni su di esso

• esempi: l'aritmetica dei naturali, degli interi, dei reali, ...

le equazioni giocano un ruolo fondamentale nell'algebra tradizionale:

• incognite: le variabili

le equazioni sono non meno fondamentali nell'algebra astratta (XX secolo):

• incognite: i simboli di operazione

il concetto di algebra, nella prima approssimazione introdotta sopra, si generalizza a quello di struttura algebrica, in cui si distingue:

• il sostegno, costituito da uno o più insiemi, su cui sono definite:
• le operazioni e/o relazioni di cui la struttura è dotata

una ridotta di una struttura A è una struttura costituita da un sottoinsieme delle operazioni e relazioni di A, definite sullo stesso sostegno

una struttura si dice omogenea se il sostegno consta di un solo insieme, eterogenea altrimenti (N.B.: il sostegno di una ridotta di una struttura eterogenea A può essere costituito da un sottoinsieme proprio della famiglia di insiemi sostegno di A, purché tutte le operazioni della ridotta siano definite nel suo sostegno)

una struttura dotata solo di operazioni totali è detta algebra in senso stretto, altrimenti è un'algebra in senso lato

• tali sono anche le strutture relazionali, dotate solo di relazioni

N.B.: è sempre possibile rappresentare una struttura algebrica come

• un'algebra (eterogenea) in senso stretto, rappresentando le relazioni per il tramite delle loro proprietà caratteristiche, intese come operazioni
• una struttura relazionale, rappresentando le operazioni k-arie come relazioni (k+1)-arie

semigruppo: (A; ⋅ ), con ⋅ un'operazione binaria associativa

• il semigruppo è detto commutativo se tale è l'operazione binaria

monoide: (A; e, ⋅ ), un semigruppo (A; ⋅ ) con e costante neutra rispetto a ⋅

• il monoide è detto commutativo se lo è il suo ridotto semigruppo

gruppo [commutativo]: (A; e, ⋅, — ), un monoide [commutativo] (A; e, ⋅) con un'operazione unaria — che dà l'inverso rispetto a ⋅ ed e:     x⋅—x = —x⋅x = e

semianello [commutativo]: (A; 0, 1, +, ⋅), un monoide commutativo (A; 0, +), detto additivo, e un monoide [commutativo] (A; 1, ⋅), detto moltiplicativo, tali da soddisfare:

1. distributività:   x⋅(y+z) = (x⋅y)+(x⋅z),   (x+y)⋅z = (x⋅z)+(y⋅z)
2. cancellazione:   0 ⋅ x = x ⋅ 0 = 0

anello [commutativo]: (A; 0, 1, +, ⋅,—), un semianello [commutativo]
(A; 0, 1, +, ⋅), con il monoide additivo esteso a un gruppo commutativo (A; 0, +, —)

classi di algebre in senso stretto quali quelle viste in precedenza sono caratterizzate da assiomi di forma molto semplice:

• equazioni di termini, costituiti da simboli di operazione e variabili:   t₁ = t₂ (con implicita quantificazione universale)

quando una classe di algebre è caratterizzata da un insieme di equazioni, che ne costituisce la base assiomatica, è possibile dedurre da tale base tutte le equazioni valide in ogni algebra della classe mediante le regole del calcolo equazionale di Garrett Birkhoff:

• riflessività: t = t
• simmetria: se t₁ = t₂ allora t₂ = t₁
• transitività: se t₁ = t₂, t₂ = t₃ allora t₁ = t₃
• sostituzione: se t₁ = t₂ allora τ(t₁) = τ(t₂)
• rimpiazzamento: se t₁ = t₂ allora t[u←t₁] = t[u←t₂]

dove il termine τ(t) è ottenuto dal termine t per sostituzione simultanea di tutte le occorrenze di ciascuna variabile con uno stesso termine, mentre il termine t[u←t'] è ottenuto dal termine t rimpiazzando il suo sottotermine al posto u con il termine t'

un reticolo è un ordinamento parziale in cui ogni coppia di elementi abbia:

• un minimo maggiorante (ingl. join, o l.u.b.: least upper bound ) e
• un massimo minorante (ingl. meet, o g.l.b.: greatest lower bound)

alternativamente, per via strettamente algebrica:

• un semireticolo è un semigruppo commutativo idempotente (assiomi ACI: l'idempotenza di un'operazione binaria ⋅ è espressa dall'equazione x⋅x = x)
• un reticolo è un'algebra (A; ∨,∧) tale che le sue due ridotte (A; ∨), (A; ∧) sono semireticoli, e inoltre valgono gli assiomi di assorbimento:
  • x ∨ (x ∧ y) = x                 x ∧ (x ∨ y) = x

occorrono dunque 8 equazioni per la base assiomatica dei reticoli?

• no, ne bastano 6: l'idempotenza è deducibile dagli altri, v. esercizio

che fine ha fatto l'ordinamento del reticolo? può essere definito algebricamente come abbreviazione di equazioni (equivalenti) in ciascuna delle due operazioni binarie:

•           x ≤ y   ≡   x ∨ y = y       oppure: x ≤ y   ≡   x ∧ y = x

        N.B.: v. in proposito l'esercizio sull'ordinamento nei reticoli algebrici

un reticolo è completo se ogni insieme di suoi elementi ha minimo maggiorante e massimo minorante

un reticolo è detto distributivo se ciascuna delle sue due operazioni è distributiva rispetto all'altra

caratterizzazione M₃-N₅ dei reticoli non distributivi:

• un reticolo è non distributivo sse ha almeno un sottoreticolo con diagramma di Hasse M₃ o N₅

un reticolo è detto limitato se ha un massimo 1 e un minimo 0

un reticolo limitato è detto complementato se ammette un'operazione unaria di complemento - tale da soddisfare:     x ∨ -x = 1   e:   x ∧ -x = 0

• e finalmente ...:

un'algebra di Boole (o booleana) è un reticolo distributivo complementato

• un'algebra di Boole è completa se tale è il suo ridotto reticolo

mettendo assieme le equazioni che caratterizzano i reticoli distributivi complementati, si ottiene una base assiomatica di 12 equazioni per le algebre di Boole

• reticoli: 6, distributività: 2, limiti: 2, complemento: 2

un paio di domande si sono presto imposte all'attenzione:

• tale base costituisce un sistema di assiomi indipendenti?
• qual è il minimo numero di assiomi atti a caratterizzare le algebre di Boole?

alla risposta (negativa) alla prima domanda ha fatto seguito la ricerca di di una risposta alla seconda, con riferimento alla ridotta costituita da una delle due operazioni di reticolo e dal complemento

• ciò perché è possibile definire l'altra operazione di reticolo mediante una delle leggi di De Morgan (dualità Booleana), e usare le due equazioni imposte al complemento come definizioni delle costanti 0, 1

una celebre assiomatizzazione delle algebre di Boole (A; +, —) così ridotte, dovuta a E.V. Huntington (1933), consta di solo 3 equazioni: associatività e commutatività del join + e:

• assioma di Huntington: —(—x + y) + —(—x + —y) = x

è l'assiomatizzazione più economica? v. il tema di approfondimento 2

su qualsiasi insieme non vuoto S possono costruirsi algebre booleane di insiemi, ciascuna così fatta:

• il sostegno è una famiglia di sottoinsiemi di S, che contenga S e l'insieme vuoto, e sia chiusa rispetto alle operazioni seguenti
• gli operatori join, meet e complemento sono risp. interpretati dalle operazioni di unione, intersezione e complemento in S
• l'insieme vuoto e S sono risp. il minimo e il massimo elemento
• si verifica che l'ordinamento booleano è l'inclusione di insiemi nella famiglia

Teorema di rappresentazione di Stone:

• ogni algebra booleana è isomorfa a un'algebra booleana di insiemi

qualsiasi sistema di assiomi completo per le algebre di Boole fornisce un calcolo deduttivo completo per la logica proposizionale

• infatti, gli assiomi booleani bastano a trasformare ogni formula in una equivalente DNF, che determina la tavola di verità della formula

dagli assiomi booleani si deriva φ = ψ sse ⊨ φ ↔ ψ, e φ = 1 sse ⊨ φ

• possiamo costruire un'algebra booleana delle formule proposizionali, dove si identifichino formule equivalenti? (semantica algebrica della logica proposizionale)

l'algebra di Lindenbaum-Tarski è una tal costruzione; fissato un insieme V di variabili proposizionali:

• dominio: il quoziente dell'insieme delle formule proposizionali con variabili in V per la relazione di equivalenza proposizionale
• operazioni booleane sulle classi di equivalenza: definite per il tramite dei connettivi proposizionali su rappresentanti delle classi

si veda l'esercizio in proposito

di particolare interesse per la realizzazione di macchine da calcolo fisiche è l'algebra booleana minimale, o algebra binaria di commutazione (ingl. Switching Algebra), caratterizzata dal fatto che il sostegno consta solo delle due costanti booleane (distinte)

• N.B. tale algebra, unica a meno di isomorfismo, è detta minimale perché tale è l'insieme di equazioni che soddisfa: ogni equazione booleana valida in essa lo è in qualsiasi algebra booleana

l'algebra booleana minimale è isomorfa all'algebra di Lindenbaum-Tarski generata dall'insieme vuoto di variabili

• l'algebra booleana minimale offre un'interpretazione dei simboli di costante come valori di verità e degli operatori booleani come connettivi proposizionali

i due operatori (∨,—) sono sufficienti a definire qualsiasi funzione booleana, cioè funzione n-aria su {0,1}

• basta infatti "leggere" la definizione della funzione come una DNF proposizionale, ed eliminare ∧ con una legge di De Morgan

Un insieme di operatori booleani si dice funzionalmente completo quando ogni funzione booleana si può rappresentare con un termine contenente solo variabili e operatori appartenenti all'insieme

• altri insiemi funzionalmente completi sono: (∧,—), e i singoli ∨ e ∧

funzioni numeriche finite possono essere definite mediante funzioni booleane grazie alla rappresentazione binaria dei numeri (intuita per primo da Leibniz)

• se occorrono k bit per rappresentare il massimo valore assunto dalla funzione, questa è rappresentabile mediante una sequenza di k funzioni booleane (una per ogni bit dell'immagine)

sono detti porte logiche (ingl. gate) componenti fisici con vie di ingresso e di uscita che esibiscano il comportamento di ingresso/uscita proprio di operatori booleani

• la composizione di operatori booleani è realizzata fisicamente da corrispondenti collegamenti di uscite a ingressi di porte logiche

si realizzano in tal modo circuiti logici, classificabili in due categorie:

• reti combinatorie: circuiti logici privi di cicli
• circuiti sequenziali: circuiti logici con cicli (ingl. feedback)

in una rete combinatoria l'output a un dato istante dipende solo dai valori in input a quell'istante, mentre in un circuito sequenziale si ha la dipendenza dell'output dalla precedente sequenza temporale degli input

• le reti combinatorie sono prive di memoria, mentre con i circuiti sequenziali si possono realizzare memorie di capacità finita

1. Il lavoro originale di George Boole
   Il testo fondamentale del 1854: An investigation of the laws of thought, on which are founded the mathematical theories of logic and probabilities, è liberamente disponibile in rete:
       http://www.archive.org/details/investigationofl00boolrich
   
2. Assiomatizzazione di Robbins delle algebre di Boole
   Un'assiomatizzazione delle algebre di Boole alternativa a quella di Huntington, e non meno concisa, è stata proposta da H. Robbins nel 1933. Il problema di dimostrare l'equivalenza degli assiomi di Robbins a quelli di Huntington si è rivelato difficile, ed è stato risolto da McCune nel 1996, grazie ad un uso molto accorto di vari sistemi di deduzione automatica. Informazioni sulla storia del Problema e sulla sua soluzione sono reperibili al sito http://www.cs.unm.edu/~mccune/papers/robbins