La clausola in algebra booleana

In algebra booleana una clausola è un'espressione che contiene un insieme di letterali $ x_i $ connessi da OR (\(\lor\)) oppure un singolo letterale. $$ (x_1 \lor \overline{x_2} \lor  ... \lor  x_n ) $$

Una clausola può essere valutata come vera (1) o falsa (0) a seconda dei valori assegnati ai suoi letterali.

Poiché è composta da un insieme di letterali collegati da OR (∨), la clausola si comporta secondo la regola che:

• se almeno uno dei letterali è vero, allora l'intera clausola è vera
• se tutti i letterali sono falsi, allora la clausola è falsa.

Esempio

Prendiamo questa clausola

$$ (x_1 \lor \overline{x_2} \lor x_3) $$

Questa clausola è vera se almeno uno dei letterali al suo interno è vero.

Questo significa che se \(x\) è vero, o \(y\) è falso, cioè \(\overline{y}\) è vero), o \(z\) è vero, allora la clausola è vera.

Possiamo creare la tavola di verità per la clausola \( (x_1 \lor \overline{x_2} \lor x_3) \).

Ecco la tavola di verità:

\[
\begin{array}{ccc|c}
x_1 & x_2 & x_3 & (x_1 \lor \overline{x_2} \lor x_3) \\
\hline
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 \\
\end{array}
\]

Nella tavola di verità, ogni riga rappresenta una possibile combinazione di valori di verità per le variabili \( x_1 \), \( x_2 \), e \( x_3 \), e il risultato della clausola per quella combinazione.

In questo caso, l'unico caso in cui la clausola è falsa è quando \( x_1 \) è 0, \( x_2 \) è 1, e \( x_3 \) è 0, perché non ci sono letterali veri in quella combinazione (riga 3).

In tutti gli altri casi la clausola è vera.

Quando si utilizzano le clausole?

Le clausole sono spesso utilizzate nelle forme normali delle espressioni booleane, in particolare nella Forma Normale Congiuntiva (CNF).

Nella CNF, una funzione booleana è espressa come un AND (\(\land\)) di clausole. Ogni clausola rappresenta una condizione che può rendere l'intera espressione vera se quella clausola è vera.