Disjunctive Normal Form (DNF)

The Disjunctive Normal Form (DNF) represents a Boolean function using a logical sum (OR) of multiple logical conjunctions (AND) of variables, which can appear either in direct form $ x_i $ or in negated form $ \overline{x_i} $. Each logical conjunction makes the Boolean function true (1).

This structure makes DNF particularly suitable for concisely describing complex relationships.

Example

Let's consider a Boolean function $ f(x_1, x_2, x_3) $ defined by three variables: $ x_1 $, $ x_2 $, and $ x_3 $.

A possible DNF for a function that becomes true under specific conditions might be:

$$ f(x_1, x_2, x_3) = ( x_1 \land x_2 \land \overline{x_3}) \lor ( \overline{x_1} \land x_2 \land x_3) $$

The function is the sum (OR) of these terms. Each term is a product (AND) of variables or their negations.

In this case, the DNF consists of two terms that make the Boolean function $ f(x_1, x_2, x_3) $ true, called minterms.

• $ ( x_1 \land x_2 \land \overline{x_3}) $
• $ ( \overline{x_1} \land x_2 \land x_3) $

The function is true in two specific cases: when $ x_1 $ is true, $ x_2 $ is true and $ x_3 $ is false, or when $ x_1 $ is false, $ x_2 $ is true and $ x_3 $ is true.

In Boolean algebra, a variable is true if it is 1, while it is false if it is 0.

Thus, if at least one of the terms $ ( x_1 \land x_2 \land \overline{x_3}) $ or $ ( \overline{x_1} \land x_2 \land x_3) $ is true, then the entire function \( f \) will be true.

How is a DNF Constructed?

Constructing a DNF can be derived directly from the truth table of the Boolean function.

1. Select the true rows. Identify all the rows in the truth table where the output of the function is true (y=1).
2. Formulate the terms. For each selected row, create a conjunction term (AND) that matches that specific combination of values. Use the variables directly $ x_i $ if their value is true (1) in the combination, or their negation $ \overline{x_i} $ if their value is false (0).
3. Combine the terms with OR. Join all the conjunction terms using the OR operator. This brings together all the conditions under which the function is true.

For example, suppose we have a Boolean function $ f(x_1, x_2, x_3) $ and the following truth table:

\begin{array}{|c|c|c|c|}
\hline
x_1 & x_2 & x_3 & f(x_1, x_2, x_3) \\
\hline
0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 \\
\hline
\end{array}

To construct the DNF, only consider the rows where \( f \) is 1:

• For row 2: \( \overline{x_1} \land \overline{x_2} \land x_3 \ )
• For row 4: \(\overline{x_1} \land x_2 \land x_3 \)
• For row 6: \( x_1 \land \overline{x_2} \land x_3 \)

The DNF will therefore be:

$$ f(x_1, x_2, x_3) = ( \overline{x_1} \land \overline{x_2} \land x_3 ) \lor ( \overline{x_1} \land x_2 \land x_3 ) \lor ( x_1 \land \overline{x_2} \land x_3 ) $$

This process demonstrates how the DNF focuses exclusively on the conditions that make the Boolean function true.

It does not consider configurations that yield a false output, as the DNF aims to explicitly express when the function is true, providing a clear and direct representation of the truth conditions.

DNF is used in the design of logic circuits, as it allows for a clear and direct representation of the conditions that make a Boolean function true. It is also used in computing to optimize the logical conditions that activate or deactivate the execution of an algorithm.