Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 37 ยท Getting Started

A Python Toolkit for Logic

Build a small Python toolkit for logic: formula classes with operator overloading, evaluation, variable discovery, and a comparison with the SymPy library.

Reading about logic is useful; running it is better. In this lesson we build a small toolkit that represents formulas as Python objects, evaluates them, and lists their variables. Later lessons reuse the same ideas for truth tables, normal forms, SAT solving and proof checking. At the end we compare our work with SymPy, a real symbolic mathematics library.

Design: formulas as immutable objects

A formula is one of: a variable, a negation, or a binary connective applied to two sub-formulas. We make one small class per kind and overload Python operators so formulas read almost like the math:

  • ~p for ยฌp
  • p & q for p โˆง q
  • p | q for p โˆจ q
  • p >> q for p โ†’ q (the right-shift operator looks like an arrow)

Operator overloading is a good fit because Python lets a class define __invert__, __and__, __or__ and __rshift__.

Python A formula class with operators

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that repr prints the formula in logical notation and fully parenthesized, so there is never any doubt about grouping.

Python's operator precedence is not logical precedence. In Python & binds tighter than |, which matches โˆง over โˆจ, but >> binds tighter than &, so p & q >> r means p & (q >> r). Always parenthesize: (p & q) >> r.

Enumerating all assignments

To test a formula we need every assignment of truth values to its variables. For n variables there are 2**n of them, and itertools.product generates them in order. We encode "true first" so tables read like textbooks.

Python All assignments and a first table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line is a warning about growth: brute force is fine for ten variables and hopeless for a hundred. Chapter 2 shows how SAT solvers cope.

Comparing with SymPy

SymPy ships a sympy.logic module with symbols, operators (&, |, ~, >>) and functions such as satisfiable and simplify_logic. Our toolkit imitates its interface on purpose. Running the same formula in both is a good sanity check, and a habit worth keeping: implement from scratch to understand, then compare with a trusted library.

Python Our evaluator versus SymPy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If this block fails to load on your machine, the pure-Python versions above still work; SymPy is a convenience, not a requirement.

Why bother with our own classes?

A library is a black box until you have built a toy version. By writing Var, Not and Bin yourself you learn that:

  • a formula is data (a tree) that a function can inspect, not just compute;
  • evaluation is a recursive function over that tree;
  • operations like "list the variables" and "substitute a value" are also tree walks.

That viewpoint, formulas are data, powers every tool in the area, from compilers that simplify boolean expressions to proof assistants that check derivations.

Design checklist for your own logic code

  1. Keep formulas immutable; transformations return new formulas.
  2. Separate syntax (the tree) from semantics (ev).
  3. Write a pretty-printer early; unreadable output wastes hours.
  4. Test against a second implementation (a library or a truth table).
  5. Parenthesize in output; never rely on precedence for readers.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many assignments does a formula with 4 propositional variables have?

    Each variable is true or false independently, giving 2^4 = 16 assignments.
  2. 2. Why do we parenthesize when using Python operators for logic?

    For instance >> binds tighter than &, so p & q >> r groups differently from logical convention.
  3. 3. What does it mean that formulas are 'data'?

    Representing a formula as a tree lets us write functions that walk, rewrite and analyze it.
  4. 4. Which Python method name overloads the ~ operator?

    ~x calls x.__invert__(), which we use for negation.

Summary

  • Represent formulas as small immutable classes: variables, negation and binary connectives.
  • Overload ~, &, | and >>, but parenthesize because Python precedence differs from logic.
  • itertools.product enumerates all 2**n assignments; brute force does not scale.
  • Compare hand-written code with SymPy as a correctness check.
  • Seeing formulas as data is the idea behind every automated reasoning tool.

Next: Arguments, Validity and Fallacies