Problem 33 - 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 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ \hline \end{array}$$

Step-by-Step Solution

Answer

The Disjunctive Normal Form of the given Boolean function is: \((\bar{x}. \bar{y}. z) \lor (\bar{x}. y. \bar{z}) \lor (x. \bar{y}. \bar{z})\).

Step 1 - Identify Rows with Output = 1

First, we need to look at the truth table and identify the rows where the output is 1. In this case, the rows are: - Row 2: \(x=0, y=0, z=1\) - Row 3: \(x=0, y=1, z=0\) - Row 5: \(x=1, y=0, z=0\)

Step 2 - Write Conjunction of Literals for Each Row with Output 1

Next, we write the conjunction of literals for each identified row. Use the negation of the variable if the value is 0, and use the variable itself if the value is 1. For Row 2: \(\bar{x}. \bar{y}. (z)\) For Row 3: \(\bar{x}. (y). \bar{z}\) For Row 5: \((x). \bar{y}. \bar{z}\)

Step 3 - Write the DNF of the Function

The final step is to write the DNF of the function, which is the disjunction of the conjunctions obtained in Step 2: DNF: \((\bar{x}. \bar{y}. z) \lor (\bar{x}. y. \bar{z}) \lor (x. \bar{y}. \bar{z})\) Thus, the Disjunctive Normal Form of the given Boolean function is: \((\bar{x}. \bar{y}. z) \lor (\bar{x}. y. \bar{z}) \lor (x. \bar{y}. \bar{z})\).

Key Concepts

Boolean Functions

Boolean functions are the heart of digital logic systems, serving as the building blocks for computing and digital electronics. Imagine them like light switches in your home—each switch can be either on (1) or off (0), and different combinations of these on-off states can control different lights or devices. Similarly, Boolean functions take a set of inputs, which are binary values (1s and 0s), and produce a single binary output.
In our home analogy, you might have a function where the output light turns on if either the kitchen or the living room switch is on. This could be represented by the Boolean function 'kitchen OR living room'. Mathematically, Boolean functions use logical operators like AND (conjunction), OR (disjunction), NOT (negation) to combine variables into an expression that describes a logical process or a set of conditions. For instance, the function represented in the exercise, \(f(x, y, z)\), gives us a binary output based on the values of \(x\), \(y\), and \(z\).
To make working with Boolean functions easier, we often translate them into a form that can be processed or implemented in digital systems, such as the Disjunctive Normal Form (DNF) highlighted in the exercise.

Truth Tables

A truth table is like a map for understanding how a Boolean function behaves. It's a systematic way of listing all possible combinations of inputs and their corresponding outputs. Think of it like a complete schedule of a train station, showing all departures (inputs) and arrivals (outputs).
In our exercise, we have a truth table listing all possible states of the three variables \(x\), \(y\), and \(z\). Each row of the table represents a unique combination of these binary variables and the resulting output of the Boolean function. By examining a truth table, one can predict the outcome for any set of inputs or reverse-engineer the function's behavior. In complex digital systems, truth tables become essential tools for designers to ensure that every possible scenario has been accounted for and that the system will behave as intended for each one.
Furthermore, truth tables are critical when converting a Boolean function into its Disjunctive Normal Form, as they let us see precisely which combinations of variables yield a true output (1), and therefore, which ones we need to include in the DNF expression.

Conjunction of Literals

At its core, a conjunction of literals in a Boolean context is like a team of players where every single one needs to participate to win a game. In logical terms, a 'literal' is simply a variable or its negation. For instance, \(x\) and \(\bar{x}\) are both literals.
A conjunction links literals using the logical AND operator. It reflects a scenario where all conditions must be met for the output to be true. In the exercise solution, for each row where the function's output is true (1), a conjunction of literals is written. The conjunction reflects the exact state of inputs that result in the output being true.

• If the variable in the truth table is 0, the corresponding literal in the conjunction is the negated variable (e.g., \(\bar{x}\)).
• If the variable is 1, the literal is the variable itself (e.g., \(x\)).

So, connecting the literals with AND operators ensures that the function will only return true if all the conditions are satisfied simultaneously—just like needing every player on the field for a win. By combining these conjunctions with OR operations (like forming alliances among several teams), the resultant expression is the Disjunctive Normal Form, revealing all possible 'winning' combinations for the Boolean function.