15.6. Finding a Boolean propositional formula from a truth table

IPython Cookbook, Second Edition This is one of the 100+ free recipes of the IPython Cookbook, Second Edition, by Cyrille Rossant, a guide to numerical computing and data science in the Jupyter Notebook. The ebook and printed book are available for purchase at Packt Publishing.

▶  Text on GitHub with a CC-BY-NC-ND license
▶  Code on GitHub with a MIT license

▶  Go to Chapter 15 : Symbolic and Numerical Mathematics
▶  Get the Jupyter notebook

The logic module in SymPy lets us manipulate complex Boolean expressions, also known as propositional formulas.

This recipe will show an example where this module can be useful. Let's suppose that, in a program, we need to write a complex if statement depending on three Boolean variables. We can think about each of the eight possible cases (true, true and false, and so on) and evaluate what the outcome should be. SymPy offers a function to generate a compact logic expression that satisfies our truth table.

How to do it...

1.  Let's import SymPy:

from sympy import *
init_printing()

2.  Let's define a few symbols:

var('x y z')

(x, y, z)

3.  We can define propositional formulas with symbols and a few operators:

P = x & (y | ~z)
P

Formula

4.  We can use subs() to evaluate a formula on actual Boolean values:

P.subs({x: True, y: False, z: True})

False

5.  Now, we want to find a propositional formula depending on x, y, and z, with the following truth table:

A truth table

6.  Let's write down all combinations that we want to evaluate to True, and those for which the outcome does not matter:

minterms = [[1, 0, 1], [1, 0, 0], [0, 0, 0]]
dontcare = [[1, 1, 1], [1, 1, 0]]

7.  Now, we use the SOPform() function to derive an adequate formula:

Q = SOPform(['x', 'y', 'z'], minterms, dontcare)
Q

SOP form

8.  Let's test that this proposition works:

Q.subs({x: True, y: False, z: False}), Q.subs(
    {x: False, y: True, z: True})

(True, False)

How it works...

The SOPform() function generates a full expression corresponding to a truth table and simplifies it using the Quine-McCluskey algorithm. It returns the smallest Sum of Products form (or disjunction of conjunctions). Similarly, the POSform() function returns a Product of Sums.

The given truth table can occur in this case: suppose that we want to write a file if it doesn't already exist (z), or if the user wants to force the writing (x). In addition, the user can prevent the writing (y). The expression evaluates to True if the file is to be written. The resulting SOP formula works if we explicitly forbid x and y in the first place (forcing and preventing the writing at the same time is forbidden).

There's more...

Here are a few references: