Espressioni Booleane

Un’espressione booleana è la formula che costruiamo sfruttando le regole dell’Algebra di Boole.

Un’espressione booleana è definita da questi 4 princìpi:

• Costanti: Gli elementi $0$ e $1$ sono espressioni booleane.
• Variabili: Le variabili (come $x, y, z$ etc…) sono espressioni booleane.
• Combinazioni: Se $h$ e $g$ sono espressioni, allora lo sono anche:
  • $h + g$
  • $h \cdot g$
  • $h^{\prime}$
• Non esistono altre espressioni oltre quelle definite iterando i precedenti 3 princìpi appena elencati.

Quindi in definitiva: è un’espressione booleana qualsiasi formula che puoi scrivere usando $0$, $1$, $x$, $y$, … e gli operatori OR, AND e NOT.

Approfondisci brevemente anche…

• Notazioni e Convenzioni nelle espressioni booleane. <--- Non ancora scritto.
• Letterali. <--- Non ancora scritte.

Valutazione di un’espressione booleana

Fin’ora abbiamo considerato tabelle di verità con funzioni abbastanza semplici, ad esempio funzioni che restituivano $1$ se tutte le variabili erano uguali.

Ma nella maggior parte dei casi l’output di una funzione potrebbe esser legato ad una espressione booleana, ad esempio: $e = z(y + x) + xy$ In questo caso, osservando l’espressione deduciamo che la funzione booleana in questione ha 3 variabili ($x, y, z$). Quindi per calcolare all’interno della tabella di verità di $f(x, y, z)$ l’output per ogni combinazione di input (ogni riga), dobbiamo sostituire i valori di $x, y, z$ e valutare (ossia calcolare) l’espressione con quei valori sostituiti alle lettere.

Vediamo la questione in modo più pratico:

Consideriamo l’espressione $e = z(y + x) + xy$ Iniziamo dalla prima riga:

• Abbiamo da valutare $e(0, 0, 0);$ <— Ossia $x=0, y=0, z=0$.
• $0(0 + 0) + 0 \cdot 0 =$
• $= 0 \cdot 0 + 0$ =
• $= 0 + 0 =$
• $= 0;$

Ripetendo questo processo per tutte le righe, si ottiene la tabella di verità completa per l’espressione $e = z(y + x) + xy$.

Specifiche su Espressioni e Funzioni

• Ad una singola espressione corrisponde una sola funzione.
• Ad una singola funzione (tabella di verità) possono corrispondere anche più espressioni diverse.
• Due o più espressioni si dicono equivalenti se generano la stessa tabella di verità (la stessa funzione).
  • Esempio:
    • $e_1 = x + x^{\prime}y$
    • $e_2 = x + y$ Queste due funzioni sopra elencate sono diverse, ma producono la stessa tabella di verità (la stessa funzione) e sono quindi equivalenti. Perché? - Beh, oltre a verificarlo valutandole entrambe, basta anche notare che sull’espressione $e_1$ è possibile applicare la proprietà di Semplificazione e vedere che l’espressione diventa $x + y$, quindi $e_1 = e_2$.

Espressioni Booleane a confronto:

Prima di passare al Teorema di espansione di Shannon e successivamente alle forme canoniche, rimarchiamo certi concetti fondamentali:

• Come abbiamo detto, una singola funzione è una tabella di verità che può essere rappresentata da molte espressioni equivalenti. Tuttavia il concetto chiave da tenere a mente è che per quanto equivalenti, comunque non sono da considerare uguali solo perché generano la stessa funzione (quindi lo stesso output).

Il nostro obiettivo è allora quello di trovare l’espressione più semplice che restituisca la stessa tabella di verità.

Perché?

Una formula più semplice (con meno letterali) può creare un circuito logico più semplice, quindi più ottimizzato, che costa meno ed è spesso più veloce.

Vedremo più avanti i circuiti logici, tuttavia il Teorema di espansione di Shannon e le Forme Canoniche che vedremo a breve sono il punto di partenza standard nella semplificazione di queste espressioni.

Continua con… Il Teorema di Espansione di Shannon.