Problem 36 - Discrete Mathematics with Applications

Question

Find the DNFs of the boolean functions $$f(x, y)=x+x y^{\prime}$$

Step-by-Step Solution

Answer

The Disjunctive Normal Form (DNF) of the given Boolean function $$f(x, y) = x + x y'$$ is: $$f(x, y) = x\bar{y} + xy$$

Step 1: Create the Truth Table

To find the DNF, we first need to create a truth table for the given function. The truth table should display the values of input variables x and y, the negation of y, and the output of the function f(x, y). x | y | y' | f(x, y) --|--|---|-------- 0 | 0 | 1 | 0 0 | 1 | 0 | 0 1 | 0 | 1 | 1 1 | 1 | 0 | 1

Step 2: Identify rows with f(x, y) = 1

In the truth table, we need to locate the rows in which the output function, f(x, y), equals 1. These rows correspond to the true (1) minterms in the DNF representation. In our truth table, we can see that f(x, y) is 1 in the following rows: - when x = 1 and y = 0 - when x = 1 and y = 1

Step 3: Write the conjunction (AND) for each row with f(x, y) = 1

For each of these rows, we will write a conjunction (AND) of literals using the variable whose value is 1 and its negation when the variable is 0. - For the row with x = 1 and y = 0, the conjunction is \(x\bar{y}\). - For the row with x = 1 and y = 1, the conjunction is \(xy\).

Step 4: Combine the conjunctions with disjunctions (OR) to find the DNF

Finally, we combine the conjunctions obtained in step 3 with disjunctions (OR) to get the DNF representation. So, the DNF of the given Boolean function is: $$f(x, y) = x\bar{y} + xy$$

Key Concepts

Truth Table

A truth table is essential for understanding Boolean functions. It enumerates all possible values of input variables and their resulting outputs from a logical function. For example, in the given function

• \( f(x, y) = x + x\overline{y} \),
• the table lists all potential combinations of \(x\) and \(y\), alongside the negation \(\overline{y}\).
• It helps in visualizing how different inputs affect the function’s outcome.

In our example, the truth table is as follows:- **00:** The output is 0, as neither \(x\) nor \(x\overline{y}\) are true.- **01:** Again, the output is 0 since \(x\) is false and hence the entire expression is false.- **10:** Here, \(x\) is 1, making the whole function true.- **11:** Both \(x\) and \(xy\) contribute to the output being 1.

• The truth table makes it easier to pinpoint which input combinations yield a true (1) result.

Disjunctive Normal Form (DNF)

Disjunctive Normal Form (DNF) represents a Boolean function as a disjunction (OR) of conjunctions (AND). Each conjunction is a combination of literals that make the function true.

• Literals are simply the variables or their negations.
• For a function to be in DNF, it should cover all true outcomes from the truth table.

To find the DNF:

• Identify rows where the output is 1. In the given example, it's 10 and 11.
• For \(x = 1\) and \(y = 0\), the conjunction is \(x\overline{y}\).
• For \(x = 1\) and \(y = 1\), the conjunction is \(xy\).

Combine these conjunctions with ORs:

• \(f(x, y) = x\overline{y} + xy\)

This DNF formula completely describes the function according to the truth table.

Boolean Function

A Boolean function is a mathematical representation of logic using variables that take on binary values (0 and 1). These functions are expressed using logical

• operations such as AND, OR, and NOT.
• They are foundational in digital circuits, computer programs, and mathematical logic.

In our example, the Boolean function is:

• \(f(x, y) = x + x\overline{y}\).

Here's how it works:

• The expression \(x\) alone can dictate the truth value, as shown in the truth table.
• The term \(x\overline{y}\) adds an additional condition where \(y\) being false allows the function to be true solely on \(x\).

This illustrates how Boolean functions are used to manipulate and simplify logic expressions.