Learn to Code via Tutorials on Repl.it!

← Back to all posts
Python - Discrete Math Logic Parser
h
FellowHashbrown

(Python) Discrete Math Logic Parser

What is Discrete Math Logic?

Discrete Math Logic is a basic form of logic. In its simplest form, it can be represented by p ^ q
In discrete math, the basic operators are:

  • ^ (which denotes AND)
  • v (which denotes OR)
  • ~ (which denotes NOT)

There are more operators that exist but for this tutorial, we will only cover these simple ones. If you want to include the other operators, I will have them at the end of this post along with the code for each operator.

Requirements

  • Basic Knowledge of Python
    • Classes
    • Functions
  • Knowledge of Recursion

Logic Parser Layout

Now for this tutorial, we are going to have 4 different python files.

  • errors.py which will hold all the Exceptions we will use
  • logic_var.py which will hold the class for a variable such as a or b
  • logic_node.py which will be the basics for a left and right logical expression such as a ^ b
  • logic_tree.py which will be the primary class for a logical expression

Now we can get started with the tutorial.


errors.py

Now this is the simple stuff. All we really have in this file are just four simple classes that extend Python's Exception object.

And we're done with that part! That was easy.


logic_var.py

In this file, we have a LogicVar class that will hold all information about a single variable in a logical expression.
This class is very simple as we only have 2 attributes that a LogicVar object holds:

  • Whether or not it has a ~ (NOT) operator attached to it
  • The variable itself

I'm going to layout the contents of each set of functions so hopefully you understand it better.

All these functions are built-in functions for Python classes.
The __eq__ function is overridden so we can compare a LogicVar object with some other object later on.
The __str__ function is overridden so we can easily print out a LogicVar object when we print the parsed expression.

These functions should be pretty straight forward. They are just getter methods for a LogicVar object.

Now the evaluate function will be given a dictionary of truth values to use to evaluate.
For example, let's say that there is a LogicVar object whose variable is a,
when the evaluate function runs, there is a truth_value given to it such as:

A truth value dictionary just holds the truth values for all the variables that exist in a logical expression.

The get_truth_values function will run through all the possible truth values that exist for a logical expression.
It depends on the amount of variables where this comes from.
To explain better, let's say we are given an expression such as a ^ b
All the possible truth values include:

So there are 2ⁿ possible combinations of truth values and that is where the list of truth values comes from.


logic_node.py

Now this file holds the information behind a logical expression such as a ^ b.
In that expression, a would be the left side, b would be the right side, and ^ would be the operator.
This is exactly what the LogicNode class holds

Again, this just sets up the LogicNode class and any object that is an instance of it.
Notice that in the __init__ method, the left and right parameters would normally take in a LogicNode or LogicVar object as the parameter. The way I will show how to load it in is using the node_dict keyword parameter.That will be shown in the next portion for the LogicTree class.

More getter methods! There's really no need to explain this but I added it in just so there's not missing code for this tutorial.

Now the evaluate method in the LogicNode class will take into account the operator of the expression.
So if the expression held in the LogicNode is an ^ (AND) operator, then it will evaluate the left recursively until it hits any LogicVar objects, and finally it will evaluate the right recursively.
If there is a ~ (NOT) operator attached to the LogicNode object, it will handle that as well.

The get_truth_values method will recursively evaluate both the left and right sides of the LogicNode object and then it will evaluate itself. Again, it will only add any evaluations that haven't already been made before. This is used when creating a truth table in the LogicTree class. It is helpful for sure when using it to evaluate a logical expression.


logic_tree.py

Now comes the almost-grand finale of this tutorial: The LogicTree class which is the root of the expresssion parsing.

This time I merged the getters in with the built-in methods only because the bulk of the code in this class isn't in the basics of the class.

Now this code may seem confusing at first but I'll break it down into what each section does.

This code segment will just evaluate itself and get a list of truth values from the LogicNode object held in the self._root variable. The get_truth_values method will actually run all the evaluations for said object.

This code segment will create the table labels in a truth table.
For example, say your expression was a ^ b
The resulting label would look like this:

It looks exactly as you would write a regular truth table!

This code segment will add a line that separates the variable or expression in the label from the truth values.
For example, we'll add onto the previous truth table:

That just adds that last little line and makes it neat in raw text.

Now this next code segment has 2 parts.
The first part,

will find the maximum amount of truth values that are given from an expression.
For example,

this truth table would have 4 truth values to go through.

The next part,

will add all the other truth values to the table itself.
So if you took the expression from above, a ^ b
The final truth table would look like this:

Now we'll move on to the get_truth_value and get_truth_values methods. This is where the height of the truth table comes from and how we manage to create every combination (not permutation) of truth values.

This will be used in a for loop that iterates through 2ⁿ combinations for each truth value.
To simplify that, we'll use three different tables to express this.

1 variable has 2 possible truth values

2 variables have 4 possible truth values

3 variables have 8 possible truth values

As you can see, we want to be able to hop back and forth between each True or False value for however many variables are in the expression.

Now let's get to the code for the get_truth_values method.

We'll go segment by segment to explain this method.

This code segment will create each dictionary for the combination of truth values given by how many variables there are.
So the elements in the list that is used to evaluate expressions would match the first n columns where n is the number of different variables.
So if the first row of the expression a ^ b would be:

and the matching dictionary would be:

This will repeat for all the rows in the truth table.

As the first comment says, any variables with a ~ (NOT) operator attached to it will have their own column designated to it. This is to make it more like a truth table that you would write yourself to simplify the boolean evaluations.
Again, it will only add evaluations that haven't already been evaluated. If we didn't check for that, there would be an endless amount of columns that exist.

Now this last segment will add all the truth values for a single variable into it's own evaluation.
The final line uses Python's built-in sorted method to sort the expressions by their lengths in order to show the build up to the final expression which is the one you want to evaluate.

I know this has already been a long tutorial but just hold off for a few more explanations.
The method that actually does the parsing, parse_expression, isn't too complex but it definitely requires some explanation or else you might be lost.

Now let's go step-by-step to explain what is going on.

This is just the basic setup. All the variables we need, all the temporary variables we need. The reason for the has_not in the parameter will be explained in a little bit.

Now the loop obviously goes through the expression as a whole which is stripped of whitespace so any spaces you put in an expression is just immediately removed.

The first if statement, if char == "(", will help to keep track of the expression that is bound in parentheses. It will only match with the one that is at the same depth as it so if you have parentheses within parentheses, they will each get evaluated separately.

The second if statement, if char == ")", will determine if the current parenthesis closes off the parent parenthesis based off the parent_depth. If it does, then it will determine if there is a ~ (NOT) operator directly attached to it and will recursively parse through whatever is within the parenthesis. It will not include the initial set of parentheses or else that would cause infinite recursion and we don't want that.

After the recursive call completes, it will reset the has_not variable. If we don't do that, we get incorrect expressions for specific original expressions.
For example, if the original expression was ~(a ^ b) ^ c, the parser would assume that the entire expression has a ~ (NOT) operator attached to it and when you printed that out, it would be ~(~(a ^ b) ^ c).

Finally, it will determine if the parsed expression belongs to the left side or the right side based off if there is an operator or not.

Once the parenthesis depth reaches 0, it will find if there is an operator yet to get.
The else statement is there in case you have an expression that doesn't include parentheses but has more than two variables to evaluate.
For example, if you give the parser a ^ b ^ c, it will automatically put the a ^ b in the left side and the resulting expression will look like this: (a ^ b) ^ c. An easy way to get around that is by placing your own parentheses.

This segment will only run if it is not in parentheses.
What it will do is find any letter that is not the letter v (this is used as the OR operator) and add that to the list of variables which is used in the parse method mentioned earlier.
It will then determine if the variable given will belong to the left or right side of the expression.

Last, but not least, we have the final part of the parse_expression method. (yippee kayak!)

If the for loop reaches the end of the expression and the parent_depth is not 0, it will obviously raise an error because you can't have an unclosed parenthesis!
Then it will sort the variables in place so the truth table, when created, will show each variable in ascending order.

The if statement there, if operator == right == None, is for any expression that might be enclosed in parentheses for no apparent reason or if the expression as a whole has a ~ (NOT) operator attached to it.
For example, ~(a ^ b) would be properly processed as the whole expression.

Then obviously the return statement will give you the expression and all its attributes and the variables that are in the expression itself.


Other Discrete Math Operators

  • Implies (->)
  • Biconditional (<->)
  • NAND (|)
  • NOR (⬇)


Final Comments

I know this was a long tutorial. I did not expect it to be this long. However, I hope I helped to provide some inspiration to create a more complex logic parser. My Logic Parser Repl actually has a few more operators that are in discrete math along with more operator flexibility meaning that you could type in a and b and it will be properly processed as a ^ b.


If you have any suggestions or see any issues, please let me know that way I can fix it!
If you find any bugs in my parser, definitely let me know either by leaving a comment, pinging me in Repl.it's Discord Server, or pinging me in my own Discord Server.

Voters
MajdZaher
thelonecodist
fifiinart
MingNg
yt_jayoneil5
a5rocks
HappyFakeboulde
PYer
timmy_i_chen
21natzil
Comments
hotnewtop
timmy_i_chen

Nice work on this :) check out your profile, you now have the Content Creator badge!

FellowHashbrown

@timmy_i_chen oh sweet thanks! Thank you for your feedback :)

thelonecodist

This post is older, but I'll comment here.

As a CS student in a university who took introductory discrete math, this was interesting. It's very loosely related to this, but I am tempted to finish a full-on project for reading and converting my own data format language here, but I lack some time. Writing in C really consumes my time. However, it does give good practice in planning and knowing the inner workings of my code. It's nice to see a fellow Repler code in lower level languages too!

Also, I have a suggestion. Could this project be something bigger: a program that checks simple arguments (less than 4 premises) by the "shortcut" method?

I would like to hear from you!

FellowHashbrown

@thelonecodist Thank you for taking the time to look at this! So as far as your suggestion, I do have a more streamlined integration using grammar parsers at this link. It takes advantage of the Quine-McCluskey Algorithm which I wrote in Python, Java, and JavaScript as well! Those are also on my website and on my GitHub Org if you'd like to take a look!