Proprietà dell'Algebra di Boole

Le seguenti proprietà non sono vere e proprie novità oltre ai postulati di Huntington, ma bensì sono conseguenze di questi postulati.

Tutte queste proprietà sono dimostrabili, ad esempio è possibile farlo con i diagrammi di Venn.

1. Associativa:

In una catena/espressione di operazioni identiche (es: tutti OR oppure tutti AND), a prescindere dalla posizione delle variabili all’interno di parentesi, il risultato rimane identico.

Formule:

• $x + (y + z) = (x + y) + z$
• $x \cdot (y \cdot z) = (x \cdot y) \cdot z$

2. Idempotenza:

“Idem” significa “stesso”. Questa proprietà ci dice che qualsiasi variabile combinata con se stessa attraverso qualunque operatore, restituisce come risultato se stessa.

Formule:

• $x + x = x$
  • Esempi: ($0 + 0 = 0$); ($1 + 1 = 1$);
• $x \cdot x = x$
  • Esempi: ($0 \cdot 0 = 0$); ($1 \cdot 1 = 1$);

3. Elemento Nullo:

È letteralmente l’opposto dell’elemento neutro. Se possiamo dire che un elemento neutro non viene praticamente contato nel calcolo in quanto tale, essendo i supporti soltanto 2 valori ($\{0$, $1\}$), possiamo altrettanto affermare che l’altro valore non neutro (quindi l’opposto) “domina”/“forza” l’operazione a restituire se stesso. Questo valore viene chiamato Elemento Nullo.

Formule:

• $x + 1 = 1$ <--- (Basta un solo $1$ in un OR per forzare l’uscita a $1$).
• $x \cdot 0 = 0$ <--- (Basta un solo $0$ in un AND per forzare l’uscita a $0$).

4. Unicità del Complemento:

Ogni variabile $x$ ha un solo e unico opposto $x^{\prime}$ .

5. Assorbimento:

Se una variabile $x$ appare sia “da sola” che in un altro termine dell’espressione, e sono “operati” (diciamo così lol) tra di loro, allora la variabile da sola “assorbe” (semplifica) la sua gemella presente nell’altro termine.

Formule ed esempi:

• $x + (x \cdot y) = x$
  • Esempio 1: Se ipotizziamo $x = 1$, allora l’espressione sarà: $1 + (1 \cdot y) = 1;$ Che sfruttando la proprietà di Assorbimento diventa: $1 + y = 1;$
  • Esempio 2: Se ipotizziamo $x = 0$, allora l’espressione sarà: $0 + (0 \cdot y) = 0;$ Che sfruttando la proprietà di Assorbimento diventa: $0 + y = 0;$
• $x \cdot (x + y) = x$ <--- (Questa formula è la duale della prima).

**Funziona esclusivamente con OR ed AND.

6. Semplificazione:

Una variabile $x$ può eliminare (semplificare) il termine contenente la sua versione negata $x^{\prime}$, quando quest’ultima compare nella stessa espressione con altre variabili, ma esclusivamente se con gli operatori OR ($+$) ed AND ($\cdot$).

Formule ed esempi:

• $x + x^{\prime} \cdot y = x + y$ <— La variabile $x$ semplifica $x^{\prime}$ perché essa è in AND con $y$. La proprietà è effettivamente valida se dopo la semplificazione l’espressione ha il valore dell’OR tra $x$ e $y$ .

  • Esempio 1: Se poniamo $x = 1$ e $y=0$, allora l’espressione sarà: $1 + 0 \cdot 0;$ Avendo l’AND ($\cdot$) priorità nell’ordine di calcolo (come il prodotto nell’algebra tradizionale), calcolando nell’espressione, vedremo che $0 \cdot 0$ è uguale ad $0$, quindi rimane $1 + 0$ che fa $1$.

  • Esempio 2: Se poniamo $x = 0$ e $y=1$, allora l’espressione sarà: $0 + 1 \cdot 1;$ Avendo l’AND ($\cdot$) priorità nell’ordine di calcolo (come il prodotto nell’algebra tradizionale), calcolando nell’espressione, vedremo che $0 \cdot 1$ è uguale ad $0$, quindi rimane $0 + 1$ che fa $1$.

  • Esempio 3: Se poniamo $x=0$ e $y=0$, allora l’espressione sarà: $0 + 1 \cdot 0;$ Avendo l’AND ($\cdot$) priorità nell’ordine di calcolo (come il prodotto nell’algebra tradizionale), calcolando nell’espressione, vedremo che $1 \cdot 0$ è uguale a $0$, quindi ci rimane $0 + 0$ che fa $0$.

  • Esempio 4: Se poniamo $x = 1$ e $y = 1$, allora l’espressione sarà: $1 + 0 \cdot 1;$ Avendo l’AND ($\cdot$) priorità nell’ordine di calcolo (come il prodotto nell’algebra tradizionale), calcolando nell’espressione, vedremo che $0 \cdot 1$ è uguale a $0$, quindi rimane $1 + 0$ che fa $1$.

  • **La formula della semplificazione ci dice che la proprietà per essere valida, tutta l’espressione deve avere il valore di $x + y$, ebbene in questi esempi è stata dimostrata la formula, mostrando che i risultati di queste espressioni sono uguali all’OR tra i valori delle $x$ e $y$ poste all’inizio di ogni espressione.

• $x \cdot (x^{\prime} y) = x \cdot y$ <— La variabile $x$ semplifica $x^{\prime}$ perché quest’ultima è in OR con $y$. È la formula duale della prima, che in questo caso rende valida la semplificazione se l’espressione ha il valore dell’AND tra $x$ e $y$ .

7. Involuzione:

È la doppia negazione di una variabile. Negare una negazione riporta alla stessa variabile non negata.

Formula ed esempio:

• $(x^{\prime})^\prime = x$
  • Esempio: $(1^{\prime})^{\prime} = 0^{\prime} = 1;$

8. Leggi di De Morgan:

Sono regole fondamentali che permettono di passare da OR ad AND e viceversa attraverso lo “spezzare” o “unire” delle negazioni.

**Regola 1:

• $(x + y)^{\prime} = x^{\prime} \cdot y^{\prime}$

  • Spiegazione: Dire “NON (A o B)” è come dire “NON A e NON B”.

• $(x \cdot y)^{\prime} = x^{\prime} + y^{\prime}$

  • Spiegazione: Dire “NON (A e B)” è come dire “NON A o NON B”.

9. Consenso:

È una regola di semplificazione di espressioni booleane molto potente, anche se meno intuitiva e a volte difficile da riconoscere.

**Formule e spiegazioni:

• $x \cdot y + x^{\prime} \cdot z + y \cdot z = x \cdot y + x^{\prime} \cdot z$

  • Cosa ci dice la formula? L’espressione dice che il termine $y \cdot z$ è inutile in quanto ridondante
    • Perché? In qualunque combinazione di valori assegnati a $x, y, z$, questa espressione farà risultare il termine $y \cdot z$ sempre ridondante, in quanto per ogni combinazione: confrontando il risultato di $x \cdot y + x^{\prime} \cdot z + y \cdot z$ con quello di $x \cdot y + x^{\prime} \cdot z$ (la stessa espressione ma senza $y \cdot z$) avremmo lo stesso valore come risultato.
  • Come riconoscere il Pattern di questa formula in un’espressione?
    • 1° Termine: Una variabile $x$ in AND con qualcos’altro $y$.
    • 2° Termine: $x^{\prime}$ in AND con qualcos’altro ancora $z$.
    • 3° Termine: L’AND delle due altre cose ($y \cdot z$).

• $(x + y) \cdot (x^{\prime} + z) \cdot (y + z) = (x + y) \cdot (x^{\prime} + z)$ <— La forma duale della prima formula.

  • Le stesse motivazioni che dimostrano il funzionamento della proprietà nella prima formula, valgono anche nella forma duale.
  • Come riconoscere il Pattern di questa formula in un’espressione?
    • 1° Termine: Una variabile $x$ in OR con qualcos’altro $y$.
    • 2° Termine: $x^{\prime}$ in OR con qualcos’altro ancora $z$.
    • 3° Termine: L’OR delle due altre cose ((y + z)).

Continua con… Le Funzioni Booleane e Tabelle di verità.