Boolean functions

Section 10.2 Boolean functions

A Boolean function is a function that takes only values 0 or 1 and whose domain is the Cartesian product \({\{0, 1\}^n}\text{.}\)

A minterm of the Boolean variables \(x_1, x_2, \ldots, x_n\) is the Boolean product \(y_1 \cdot y_2 \cdot \ldots \cdot y_n\) where each \(y_i = x_i\) or \(y_i = \overline{x_i}\text{.}\)

A sum of minterms is called a sum-of-products expansion. In this section, we will examine various methods for finding the sum-of-products expansion of a Boolean function.

To find the sum-of-products expansion using a truth table, we first convert the truthtable() into a form that is iterable with get_table_list(). For every row where the output value is True, we construct a minterm:

Include the variable as is if its value is True
Include the negation of the variable if its value is False
The zip function pairs each variable with its corresponding value, allowing us to create minterms efficiently.
We add each minterm to the sop_expansion list using the & operator.
Finally, we join all minterms with the | operator to form the sum-of-products expansion.
The function returns the sum-of-products expansion as a sage.logic.boolformula.BooleanFormula instance.

For your convenience, our truth_table_sop function converts String input with propcalc.formula. Therefore, the input accepts String representations of Boolean expressions. Alternatively, you may pass an instance of sage.logic.boolformula.BooleanFormula directly to the function.

Let’s verify that the sum-of-products expansion we found with the truth table is equivalent to the original expression.

Our sop_expansion function mimics the manual process of finding the sum-of-products expansion of a Boolean function. This process does not guarantee the minimal form of the Boolean expression.

If we dig around in the Sage source code, we can find a commented-out Simplify() function that relied on the Boolopt package and the Quine-McCluskey algorithm. The Quine-McCluskey algorithm guarantees the minimal form of the Boolean expression, but the exponential complexity of the algorithm makes it impractical for large expressions. Moreover, in the Sage documentation, we see a placeholder function called Simplify() that returns a NotImplementedError message. The Sage community is waiting for someone to implement this function with the Espresso algorithm. While the Espresso algorithm does not guarantee the minimal form of the Boolean expression, it is more efficient than the Quine-McCluskey algorithm.

Sage integrates well with Python libraries like SymPy, which have built-in functions for Boolean simplification. The SymPy SOPform function takes the variables as the first argument and the minterms as the second argument. The function returns the sum-of-products expansion of the Boolean function in the smallest sum-of-products form. To use the SymPy SOPform function in Sage, first extract the variables and minterms of an expression.

We extract the variables from the first row of the truth table.

We make the variables compatible with the SymPy SOPform function by converting them to SymPy symbols.

We extract the minterms from the rows where the output is True.

Now that we have the variables and minterms, we can use the SymPy SOPform function to find the sum-of-products expansion of the Boolean function.

Let’s verify that the sum-of-products expansion we found with SymPy is equivalent to the original expression.

Now, we present a manual method for finding the sum of products by applying the Boolean identities. Let’s find the sum-of-products expansion of the Boolean function

\begin{equation*} h(x, y) = x + \bar{y}\text{.} \end{equation*}

We can apply the Boolean identities and use Sage to verify our work. Currently, we have a sum of two terms but no products. We can apply the identity law to introduce the product terms. Now, we have the equivalent expression

\begin{equation*} h(x, y) = x \cdot 1 + 1 \cdot \bar{y}\text{.} \end{equation*}

Warning: Do not attempt to apply the identity law or null law within the formula function. If you try to directly apply the identity law within the formula function like so, propcalc.formula("x & 1 | 1 ~y"), Sage will raise an error because propcalc.formula interprets 1 as a variable. Variables cannot start with a number.

The formula function only supports variables and the following operators:

& \(and\)
| \(or\)
~ \(not\)
^ \(xor\)
-> \(if\; then\)
<-> \(if\; and\; only\; if\)

Apply the complement law and verify that our transformed expression is equivalent to the original expression.

Apply the distributive law and verify that our transformed expression is equivalent to the original expression.

Apply the idempotent law and verify that our transformed expression is equivalent to the original expression.

We started with the expression,

\begin{equation*} h(x, y) = x + \bar{y} \end{equation*}

After applying the identity, complement, and distributive laws, we transformed the Boolean function into the sum-of-products expansion

\begin{equation*} h(x, y) = x \cdot y + x \cdot \bar{y} + x \cdot \bar{y} + \bar{x} \cdot \bar{y}\text{.} \end{equation*}

Prev Top Next