Reticoli di Boole

In un insieme E si suppongano definite due operazioni che indichiamo con i segni ∧, ∨ soddisfacenti alle seguenti condizioni:

Si può introdurre una relazione che indichiamo con "<" col seguente significato: a < b se e solo se a ∧ b = a. Si può provare che si tratta di una relazione d'ordine.

Un reticolo è detto distributivo se in esso ognuna delle due operazioni ∨, ∧ è distributiva rispetto all'altra, ossia se:

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Notiamo che una qualunque delle due proprietà distributive implica l'altra, sicchè per verificare che un reticolo è distributivo basta constatare la validità di una delle due.

Semplificazione di combinazioni di operazioni logiche

Una prima semplificazione sulla notazione è la seguente: ∧ = *, ∨ = +. La motivazione di questa semplificazione deriva dal fatto che Boole fa corrispondere al numero zero il falso e al numero uno il vero.

Una delle caratteristiche delle operazioni booleane e che vi è più di una combinazione di operazioni in grado di produrre lo stesso risultato. In altri termini, la stessa tabella di verità può essere ottenuta con più di un circuito logico. L'obiettivo principale della semplificazione di circuiti logici consiste nel determinare le combinazioni di operazioni logiche che produrranno il risultato desiderato, usando il minimo numero di porte. Ciò ridece i costi e il consumo di energia dei circuiti logici e aumenta la loro velocità operativa. Talvolta un secondo obiettivo è quello di produrre un circuito logico che impiega soltanto un certo tipo di porte. Elenchiamo alcune proprietà algebriche delle operazioni booleane.

¬(¬A) = A

(A + B) + C = A + (B + C)

(A * B) * C = A * (B * C)

A + (B * C) = (A + B) * (A + C)

A * (B + C) = (A * B) + (A * C)

A * A = A

¬(A + B) = ¬A * ¬B

¬(A * B) = ¬A + ¬B

Concludendo la base teorica per il funzionamento degli elaboratori è la logica di Boole che consiste in un certo numero di operazioni che possono essere applicate a variabili logiche o Booleane aventi due soli stati. Le operazioni booleane possono essere rappresentate dai simboli dell'algebra booleana, da circuiti logici in cui essi appaiono come porte o da tabelle di verità. Tutte le operazioni logiche possono essere espresse come combinazioni di operazioni elementari AND, OR, NOT, però sono impiegate altre tre operazioni NAND, NOR, EOR. Le espressioni logiche possono essere semplificate per ridurre il numero di operazioni o per usare soltanto certe operazioni, pur ottenendo gli stessi risultati.

Esempi di semplificazioni di circuiti logici

Il circuito di sopra può essere tradotto con la seguente proposizione: z = ¬(¬(x * y))

Semplificando: z = ¬(¬(x * y)) = ¬(¬(x + y)) = x + y

Quindi il circuito precedente si può semplificare riducendolo al seguente:

Analogamente questo circuito:

può essere semplificato riducendolo al seguente:

Analogamente questo circuito:

può essere semplificato riducendolo al seguente: