Clauses in Boolean Algebra

In Boolean algebra, a clause consists of several literals $ x_i $ linked by OR ($\lor$), or it can simply be a single literal. $$ (x_1 \lor \overline{x_2} \lor ... \lor x_n ) $$

The truth of a clause, either true (1) or false (0), depends on the values assigned to its literals.

A clause, by virtue of its structure—literals connected by OR (\or;)—follows a straightforward rule:

If any one of the literals is true, the whole clause is considered true.
If all literals are false, then the clause is deemed false.

Example

Consider the following clause:

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

This clause will be true if at least one of its included literals is true. For example, if $x$ is true, or if $y$ is false (making $\overline{y}$ true), or if $z$ is true, then the clause will be true.

Let's create a truth table for the clause $ (x_1 \lor \overline{x_2} \lor x_3) $:

Here's the truth table:

\[
\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}
\]

Each row in the truth table illustrates a possible set of truth values for the variables $ x_1 $, $ x_2 $, and $ x_3 $, along with the corresponding result of the clause.

Noticeably, the clause is only false in the case where $ x_1 $ is 0, $ x_2 $ is 1, and $ x_3 $ is 0, as there are no true literals in that configuration (row 3).

In every other case, the clause proves to be true.

Usage of Clauses

Clauses are frequently used in normal forms of Boolean expressions, especially in Conjunctive Normal Form (CNF).

In CNF, a Boolean function is expressed as an AND ($\land$) of multiple clauses. Each clause poses a condition that must be met for the entire expression to be true.

For instance, in CNF, the function

$$ f(x, y, z) = (x \lor \overline{y}) \land (\overline{x} \lor z) $$ is comprised of two clauses:

$ (x \lor \overline{y}) $
$ (\overline{x} \lor z) $

For the function $f$ to be true, both clauses must be satisfied; either $x$ is true or $y$ is false for the first clause, and simultaneously, $x$ must be false or $z$ true for the second clause.

```