2. Algebra di Boole

L’algebra booleana ha notevole importanza in diversi contesti ingegneristici e matematici. Ad esempio nella progettazione di componenti elettronici digitali.

Per questo motivo la ribadiamo: un’algebra di Boole è un insieme B nel quale sono definite due operazioni binarie: \(\wedge\), \(\vee\), e una operazione unaria. L’insieme contiene due elementi distinti: 0 e 1.

Nell’algebra di Boole valgono i seguenti assiomi rispetto le operazioni predette:

  1. proprietà commutativa per \(\wedge\) e \(\vee\);
  2. proprietà distributiva per \(\wedge\) e \(\vee\);
  3. esistenza dell’elemento neutro per \(\wedge\) e \(\vee\);
  4. esistenza dell’elemento simmetrico per \(\wedge\) e \(\vee\).

Nota

In modo formale: \(\forall x, y, z \in B\)

\[\begin{split}& 1)\; x \vee y = y \vee x \\ & 2)\; x \wedge y = y \wedge x \\ & 3)\; x \wedge ( y \vee z) = (x \wedge y) \vee (x \wedge z) \\ & 4)\; x \vee ( y \wedge z) = (x \vee y) \wedge (x \vee z) \\ & 5)\; x \vee 0 = x \\ & 6)\; x \wedge 1 = x \\ & 7)\; x \vee x' = 1 \\ & 8)\; x \wedge x' = 0\end{split}\]

Nell’algebra booleana, data una espressione (ovvero: proposizione) composta da elementi e operazioni su di essi, è sempre possibile scrivere la sua proposizione duale. Ovvero quella che si ottiene sostituendo l’operazione \(\vee\) con \(\wedge\) e viceversa, nonché l’elemento \(0\) con \(1\) e viceversa.

Vale la legge di dualità: se una proposizione è derivata dagli assiomi dell’algebra booleana, anche la sua duale lo è.

Nell’algebra booleana si dimostrano le seguenti proprietà:

  1. dato un elemento di B esiste il suo complementare ed è unico;

  2. gli elementi \(0\) e \(1\) sono entrambi unici;

  3. vale la proprietà di idempotenza:

    Nota

    Ovvero: \(x \wedge x = x\) e \(x \vee x = x\)

  4. il simmetrico del simmetrico restituisce l’elemento di partenza;

    Nota

    Ovvero: \((x')' = x\)

  5. lo zero è il risultato dell’operazione \(\wedge\) per ogni elemento di B; analogamento l’unità è il risultato dell’operazione \(\vee\) per ogni elemento di B;

    Nota

    Ovvero: \(x \wedge 0 = 0\) e \(x \vee 1 = 1\)

  6. esiste la proprietà di assorbimento delle operazioni;

    Nota

    Ovvero:

    \[\begin{split}& x \wedge (x \vee y) = x \\ & x \vee (x \wedge y) = x\end{split}\]
  7. l’uguaglianza dei risultati dell’operatore \(\wedge\) implica l’uguaglianza degli operatori;

    Nota

    Ovvero:

    \[\begin{split}{y \wedge x = z \wedge x \\ y \wedge x' = z \wedge x'} \Biggr\} \Longrightarrow y = z\end{split}\]
  8. la proprietà associativa;

    Nota

    Ovvero:

    \[\begin{split}x \vee (y \vee z) = (x \vee y) \vee z \\ x \wedge (y \wedge z) = (x \wedge y) \wedge z\end{split}\]
  9. la legge di Morgan;

    Nota

    Ovvero:

    \[\begin{split}(x \vee y)' = x' \wedge y' \\ (x \wedge y)' = x' \vee y'\end{split}\]
  10. dalla legge di Morgan deriva la possibilità di passare da un operatore all’altro complementando la proposizione duale;

    Nota

    Ovvero:

    \[\begin{split}x \vee y = (x' \wedge y')' \\ x \wedge y = (x' \vee y')'\end{split}\]