Problem 34 - Discrete Mathematics with Applications

Question

Find the DNFs of the boolean functions $$\begin{array}{|ccc||c|} \hline x & y & z & f(x, y, z) \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \hline \end{array}$$

Step-by-Step Solution

Answer

The short answer for the DNF of the given boolean function is: \( f(x,y,z) = \overline{x}\cdot y\cdot z + x\cdot \overline{y}\cdot z + x\cdot y\cdot \overline{z} \).

Step 1: Identify the input combinations

To find the DNF of the given boolean function, first, identify the input combinations where the output value 'f(x, y, z)' is equal to 1. From the given truth table, we can observe that the input combinations (x, y, z) that produce an output of 1 are: (0, 1, 1), (1, 0, 1), and (1, 1, 0).

Step 2: Create product terms

Now, create the product term for each of these input combinations. In a product term, a variable appears in complemented form if it is 0 and uncomplemented form if it is 1. So, we will have the following product terms: For (0, 1, 1): \( \overline{x}\cdot y\cdot z \) For (1, 0, 1): \(x\cdot \overline{y}\cdot z\) For (1, 1, 0): \(x\cdot y\cdot \overline{z}\)

Step 3: Combine product terms

Combine the product terms obtained in step 2 using OR operations to form the Disjunctive Normal Form (DNF) of the given boolean function: DNF = (\(\overline{x}\cdot y\cdot z \)) \( \ + \) (\(x\cdot \overline{y}\cdot z\)) \( \ + \) (\(x\cdot y\cdot \overline{z}\)) This is the DNF representation of the given boolean function: $$ f(x,y,z) = \overline{x}\cdot y\cdot z \ + \ x\cdot \overline{y}\cdot z \ + \ x\cdot y\cdot \overline{z}$$

Key Concepts

Disjunctive Normal Form

Disjunctive Normal Form (DNF) is a way of expressing a boolean function as a sum (OR operation) of product terms (AND operations). Each product term in a DNF represents a specific combination of input variables that make the function true (output = 1). Being in DNF means every logical OR (disjunction) operation is between complete AND (conjunction) operations of literals.
To effectively create a DNF, follow these steps:

• Identify the rows in a truth table where the function output is 1.
• Write product terms for each of these rows.
• Combine these terms using OR operations.

The DNF makes it simple to analyze and deploy logical functions because it directly corresponds to physical implementations like circuit design.

Truth Table

A Truth Table is a mathematical table used to tell if a boolean expression is true or false under all possible combinations of its variables. Each row represents a possible input combination, and the resulting output is recorded next to it.
To construct a truth table:

• Determine the number of variables (e.g., x, y, z).
• List all possible combinations of 0s and 1s for these variables (for three variables, you will have 8 combinations as seen in the truth table given in the exercise).
• For each combination, evaluate the boolean function and record whether the output is 0 or 1.

Using a truth table, you can visualize which combinations of variables satisfy the function (output is 1). It is a valuable tool for simplifying expressions into DNF.

Product Terms

Product Terms are essential components when converting a truth table into Disjunctive Normal Form. They are formed by ANDing variables, where each variable is either in its complemented (negated) or uncomplemented (non-negated) form. Each row in the truth table that produces a 1 in the output can be represented by a product term.
Here's how to form product terms for the truth table provided:

• If a variable is 0 for a specific row, write it in complemented form (e.g., 0 for x results in \(\overline{x}\)).
• If a variable is 1, write it in uncomplemented form (e.g., 1 for y results in \(y\)).
• Combine all variables for that row using AND (e.g., \(\overline{x} \cdot y \cdot z\)).

These product terms represent the minimal conditions required to make a function output true.

Complemented and Uncomplemented Form

Understanding the complemented and uncomplemented forms of a variable is crucial when dealing with boolean algebra. A variable can appear in either form based on the truth table's input values. When a variable is in complemented form, it signifies logical NOT, depicted by a bar over the variable, such as \(\overline{x}\), which means x is 0. Conversely, uncomplemented form is where the variable remains unchanged, indicating the variable is 1.
Here's how you convert variables based on truth table data:

• Check the input: if it's 0, use the complimented form \(\overline{x}\).
• If it's 1, use the uncomplemented form \(x\).

This transformation is vital for creating product terms that reflect the specific conditions where the boolean function is true, enabling a straightforward transition to the DNF.