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.

class UnbalancedParentheses(Exception): pass
class MissingTruthValue(Exception): pass
class OperatorMismatch(Exception): pass
class MissingValue(Exception): pass

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.

class LogicVar:
def __init__(self, value = None, has_not = False, *, var_dict = None):
# If the value is given, we are loading it in by the value and has_not parameters
if value != None:
self._value = value
self._has_not = has_not
# If the var_dict is given, we are recursively initializing this LogicVar.
elif var_dict != None:
# Try loading the value key from var_dict
try:
self._value = var_dict["value"]
except:
raise MissingValue("Required key for LogicVar. Must have \"value\" key in var_dict.")
# Try loading the has_not key from var_dict
try:
self._has_not = var_dict["has_not"]
except:
self._has_not = has_not
# If both value and var_dict are missing, we raise an Exception
elif value == None and var_dict == None:
raise MissingValue("Required variable for LogicVar. Must use either value or var_dict.")
def __str__(self):
if self.has_not():
return "~" + self.get_value()
return self.get_value()
def __eq__(self, value):
if not isinstance(value, LogicVar):
return False
return (
self.get_value() == value.get_value() and
self.has_not() == value.has_not()
)
...

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.

...
def evaluate(self, truth_value = {}):
if self.get_value() not in truth_value:
raise MissingTruthValue("Required truth value for the variable \"{}\"".format(self.get_value()))
if self.has_not():
return not truth_value[self.get_value()]
return truth_value[self.get_value()]
def get_truth_values(self, truth_values = []):
# Keep track of evaluations
evaluations = []
# Only run this if there is a has_not
if self.has_not():
# Iterate through truth values
for truth_value in truth_values:
# Evaluate the value given by this LogicVar
evaluation = {
"expression": str(self),
"truth_value": truth_value,
"value": self.evaluate(truth_value)
}
# Only add the evaluation if it doesn't already exist
if evaluation not in evaluations:
evaluations.append(evaluation)
return evaluations

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": True,
"b": True
}

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:

| a | b |
|---+---|
| T | T |
| T | F |
| F | T |
| F | F |

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

class LogicNode:
def __init__(self, operator = None, left = None, right = None, has_not = False, *, node_dict = None):
# If operator, left, and right are given, we are loading it in by those parameters
if operator != None and left != None and right != None:
self._operator = operator
self._left = left
self._right = right
self._has_not = has_not
# If node_dict is given, we are recursively initializing this LogicNode.
elif node_dict != None:
# Try loading operator
try:
self._operator = node_dict["operator"]
except:
raise MissingValue("Required key for LogicNode. Must have \"operator\" key in node_dict.")
# Try loading left
try:
self._left = node_dict["left"]
except:
raise MissingValue("Required key for LogicNode. Must have \"left\" key in node_dict.")
# Try loading right
try:
self._right = node_dict["right"]
except:
raise MissingValue("Required key for LogicNode. Must have \"right\" key in node_dict.")
# Try loading has_not
try:
self._has_not = node_dict["has_not"]
except:
self._has_not = has_not
# If operator, left, right, and node_dict are all missing, raise an Exception
elif (operator == None or left == None or right == None) or node_dict == None:
raise MissingValue("Required variable(s) for LogicNode. Must use either operator, left, and right or node_dict.")
# Turn the left and right values into either `LogicNode` or `LogicVar` objects
if isinstance(self._left, dict):
if "value" in self._left:
self._left = LogicVar(var_dict = self._left)
else:
self._left = LogicNode(node_dict = self._left)
if isinstance(self._right, dict):
if "value" in self._right:
self._right = LogicVar(var_dict = self._right)
else:
self._right = LogicNode(node_dict = self._right)
def __str__(self):
left = str(self.get_left())
right = str(self.get_right())
# Only put parentheses around expressions that don't have a ~ (NOT) operator attached to it
if isinstance(self.get_left(), LogicNode) and not self.get_left().has_not():
left = "(" + left + ")"
if isinstance(self.get_right(), LogicNode) and not self.get_right().has_not():
right = "(" + right + ")"
operator = self.get_operator()
if self.has_not():
return "~({} {} {})".format(
left, operator, right
)
return "{} {} {}".format(
left, operator, right
)
def __eq__(self, value):
if not isinstance(value, LogicNode):
return False
return (
self.get_left() == compare.get_left() and
self.get_right() == compare.get_right() and
self.get_opoerator() == compare.get_operator() and
self.has_not() == compare.has_not()
)
...

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.

...
def evaluate(self, truth_value = {}):
left = self.get_left().evaluate(truth_value)
right = self.get_right().evaluate(truth_value)
if self._operator == "^":
if self.has_not():
return not (left and right)
return left and right
if self._operator == "v":
if self.has_not():
return not (left or right)
return left or right
def get_truth_values(self, truth_values = []):
# Keep track of evaluations
evaluations = []
# Get left evaluations
left_evaluations = self.get_left().get_truth_values(truth_values)
for left_evaluation in left_evaluations:
if left_evaluation not in evaluations:
evaluations.append(left_evaluation)
# Get right evaluations
right_evaluations = self.get_right().get_truth_values(truth_values)
for right_evaluation in right_evaluations:
if right_evaluation not in evaluations:
evaluations.append(right_evaluation)
# Iterate through truth values
for truth_value in truth_values:
# Evaluate this LogicNode object
evaluation = {
"expression": str(self),
"truth_value": truth_value,
"value": self.evaluate(truth_value)
}
# Only add the evaluation if it doesn't already exist
if evaluation not in evaluations:
evaluations.append(evaluation)
return evaluations

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.

...
def parse(self):
expression = parse_expression(self.get_expression())
expression = expression["expression"]
variables = expression["variables"]
self._root = LogicNode(node_dict = expression)
self._variables = variables
self._expression = str(self._root)
def make_table(self):
lines = []
result = ""
# Evaluate the root LogicNode
evaluations = self.get_truth_values()
table_dict = {}
for evaluation in evaluations:
if evaluation["expression"] not in table_dict:
table_dict[evaluation["expression"]] = []
table_dict[evaluation["expression"]].append(evaluation["value"])
# Add column labels
count = 0
length = len(table_dict)
for column in table_dict:
line = "| " + column.center(len(column))
if count > 0:
line = " " + line
elif count == length - 1:
line += " |"
result += line
count += 1
lines.append(result)
result = ""
# Add label split line
count = 0
for column in table_dict:
line = "+" + "-".center(len(column) + 1, "-")
if count > 0:
line = "-" + line
elif count == length - 1:
line += "-+"
result += line
count += 1
lines.append(result)
result = ""
# Add truth values
max_truths = -1
for column in table_dict:
if max_truths == -1:
max_truths = len(table_dict[column])
break
for index in range(max_truths):
count = 0
for column in table_dict:
value = table_dict[column][index]
if value:
value = "T"
elif value == False:
value = "F"
else:
value = "-"
line = "| " + value.center(len(column))
if count > 0:
line = " " + line
elif count == length - 1:
line += " |"
result += line
count += 1
lines.append(result)
result = ""
return lines
...

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

# Evaluate the root LogicNode
evaluations = self.get_truth_values()
table_dict = {}
for evaluation in evaluations:
if evaluation["expression"] not in table_dict:
table_dict[evaluation["expression"]] = []
table_dict[evaluation["expression"]].append(evaluation["value"])

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.

# Add column labels
count = 0
length = len(table_dict)
for column in table_dict:
line = "| " + column.center(len(column))
if count > 0:
line = " " + line
elif count == length - 1:
line += " |"
result += line
count += 1
lines.append(result)
result = ""

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:

| a | b | a ^ b |

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

# Add label split line
count = 0
for column in table_dict:
line = "+" + "-".center(len(column) + 1, "-")
if count > 0:
line = "-" + line
elif count == length - 1:
line += "-+"
result += line
count += 1
lines.append(result)
result = ""

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:

| a | b | a ^ b |
+---+---+-------+

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

# Add truth values
max_truths = -1
for column in table_dict:
if max_truths == -1:
max_truths = len(table_dict[column])
break
for index in range(max_truths):
count = 0
for column in table_dict:
value = table_dict[column][index]
if value:
value = "T"
elif value == False:
value = "F"
else:
value = "-"
line = "| " + value.center(len(column))
if count > 0:
line = " " + line
elif count == length - 1:
line += " |"
result += line
count += 1
lines.append(result)
result = ""

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

max_truths = -1
for column in table_dict:
if max_truths == -1:
max_truths = len(table_dict[column])
break

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

| a | b |
+---+---+
| T | T |
| T | F |
| F | T |
| F | F |

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

The next part,

for index in range(max_truths):
count = 0
for column in table_dict:
value = table_dict[column][index]
if value:
value = "T"
elif value == False:
value = "F"
else:
value = "-"
line = "| " + value.center(len(column))
if count > 0:
line = " " + line
elif count == length - 1:
line += " |"
result += line
count += 1
lines.append(result)
result = ""

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:

| a | b | a ^ b |
+---+---+-------+
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |

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

| a |
+---+
| T |
| F |

2 variables have 4 possible truth values

| a | b |
+---+---+
| T | T |
| T | F |
| F | T |
| F | F |

3 variables have 8 possible truth values

| a | b | c |
+---+---+---+
| T | T | T |
| T | T | F |
| T | F | T |
| T | F | F |
| F | T | T |
| F | T | F |
| F | F | T |
| F | F | F |

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.

...
def get_truth_values(self):
# Create every possible truth combination for all variables
truth_values = []
# Iterate through 2 ** variable_amount possible combinations
for value in range(2 ** len(self.get_variables())):
# Iterate through all variables
value_dict = {}
for index in range(len(self.get_variables())):
# Get the power based off of the variable's index in the list
power = len(self.get_variables()) - index - 1
variable = self.get_variables()[index]
# Get the truth value using the get_truth_value function
value_dict[variable] = get_truth_value(value, power)
truth_values.append(value_dict)
# Create truth values for other operations
# For example, if there is a "~a", then there will be a column designated to that.
# if there is a "~(a v b)", then there will be a column designated to that
# as well as the "a v b" part.
truth_evaluations = []
root_truth_evaluations = self._root.get_truth_values(truth_values)
# Add all the truth evaluations from the root
for truth_evaluation in root_truth_evaluations:
if truth_evaluation not in truth_evaluations:
truth_evaluations.append(truth_evaluation)
# Add all the truth values as evaluations
for truth_value in truth_values:
for truth_variable in truth_value:
truth_evaluation = {
"expression": truth_variable,
"truth_value": {
truth_variable: truth_value[truth_variable]
},
"value": truth_value[truth_variable]
}
truth_evaluations.append(truth_evaluation)
truth_evaluations = sorted(truth_evaluations, key = lambda i: len(i["expression"]))
return truth_evaluations

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

# Create every possible truth combination for all variables
truth_values = []
# Iterate through 2 ** variable_amount possible combinations
for value in range(2 ** len(self.get_variables())):
# Iterate through all variables
value_dict = {}
for index in range(len(self.get_variables())):
# Get the power based off of the variable's index in the list
power = len(self.get_variables()) - index - 1
variable = self.get_variables()[index]
# Get the truth value using the get_truth_value function
value_dict[variable] = get_truth_value(value, power)
truth_values.append(value_dict)

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:

| a | b |
+---+---+
| T | T |

and the matching dictionary would be:

{
"a": True,
"b": True
}

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

# Create truth values for other operations
# For example, if there is a "~a", then there will be a column designated to that.
# if there is a "~(a v b)", then there will be a column designated to that
# as well as the "a v b" part.
truth_evaluations = []
root_truth_evaluations = self._root.get_truth_values(truth_values)
# Add all the truth evaluations from the root
for truth_evaluation in root_truth_evaluations:
if truth_evaluation not in truth_evaluations:
truth_evaluations.append(truth_evaluation)

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.

# Add all the truth values as evaluations
for truth_value in truth_values:
for truth_variable in truth_value:
truth_evaluation = {
"expression": truth_variable,
"truth_value": {
truth_variable: truth_value[truth_variable]
},
"value": truth_value[truth_variable]
}
truth_evaluations.append(truth_evaluation)
truth_evaluations = sorted(truth_evaluations, key = lambda i: len(i["expression"]))

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.

def parse_expression(expression, has_not = False):
# Remove all spaces from the expression
expression = expression.replace(" ", "")
# Loop through and find any ^ (AND) or v (OR) operators as expressions
has_not = has_not
left = None
operator = None
right = None
variables =[]
parent_depth = 0
last = 0
char_has_not = False
temp_has_not = False
for index in range(len(expression)):
char = expression[index]
# Check for open parenthesis
if char == "(":
if parent_depth == 0:
last = index + 1
parent_depth += 1
# Check for close parenthesis
elif char == ")":
parent_depth -= 1
# Parse expression if parenthesis depth reaches 0
if parent_depth == 0:
# Check if there is a ~ (NOT) operator directly in front of the parenthesis
if last - 1 > 0:
if expression[last - 2] == "~":
temp_has_not = True
exp = parse_expression(expression[last: index], temp_has_not)
if index == len(expression) - 1 and last == 0:
has_not = temp_has_not
temp_has_not = False
# Check if there is no operator; Must be left side
if operator == None:
left = exp["expression"]
else:
right = exp["expression"]
# No parenthesis depth anymore
if parent_depth == 0:
# Check for operator only if not within a parenthesis
if char in ["^", "v"]:
# Check if operator does not exist yet
if operator == None:
if char == "^":
operator = "^"
elif char == "v":
operator = "v"
# Operator exists; String of logical expressions exists
# Make the left, operator, right into the left expression
else:
left = {
"has_not": has_not,
"left": left,
"operator": operator,
"right": right
}
if char == "^":
operator = "^"
elif char == "v":
operator = "v"
right = None
has_not = False
# Check for variable only if not within parentheses
if ord(char) in range(ord('a'), ord('z') + 1) and ord(char) != ord('v'):
# See if there is a ~ (NOT) operator directly in front of the variable
if index > 0:
if expression[index - 1] == "~":
char_has_not = True
else:
char_has_not = False
# Check if there is no operator; Must be left side
if operator == None:
left = {
"has_not": char_has_not,
"value": char
}
else:
right = {
"has_not": char_has_not,
"value": char
}
char_has_not = False
if char not in variables:
variables.append(char)
if parent_depth != 0:
raise UnbalancedParentheses("You have a missing parenthesis somewhere.")
variables.sort()
# Check if the expression is a single expression wrapped in parentheses
if operator == right == None:
has_not = left["has_not"]
operator = left["operator"]
right = left["right"]
left = left["left"]
return {
"expression": {
"has_not": has_not,
"left": left,
"operator": operator,
"right": right
},
"variables": variables
}

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

# Remove all spaces from the expression
expression = expression.replace(" ", "")
# Loop through and find any ^ (AND) or v (OR) operators as expressions
has_not = has_not
left = None
operator = None
right = None
variables = []
parent_depth = 0
last = 0
char_has_not = False
temp_has_not = False

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.

for index in range(len(expression)):
char = expression[index]
# Check for open parenthesis
if char == "(":
if parent_depth == 0:
last = index + 1
parent_depth += 1
# Check for close parenthesis
elif char == ")":
parent_depth -= 1
# Parse expression if parenthesis depth reaches 0
if parent_depth == 0:
# Check if there is a ~ (NOT) operator directly in front of the parenthesis
if last - 1 > 0:
if expression[last - 2] == "~":
temp_has_not = True
exp = parse_expression(expression[last: index], temp_has_not)
if index == len(expression) - 1 and last == 0:
has_not = temp_has_not
temp_has_not = False
# Check if there is no operator; Must be left side
if operator == None:
left = exp["expression"]
else:
right = exp["expression"]

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.

# No parenthesis depth anymore
if parent_depth == 0:
# Check for operator only if not within a parenthesis
if char in ["^", "v"]:
# Check if operator does not exist yet
if operator == None:
if char == "^":
operator = "^"
elif char == "v":
operator = "v"
# Operator exists; String of logical expressions exists
# Make the left, operator, right into the left expression
else:
left = {
"has_not": has_not,
"left": left,
"operator": operator,
"right": right
}
if char == "^":
operator = "^"
elif char == "v":
operator = "v"
right = None
has_not = False

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.

# Check for variable only if not within parentheses
if ord(char) in range(ord('a'), ord('z') + 1) and ord(char) != ord('v'):
# See if there is a ~ (NOT) operator directly in front of the variable
if index > 0:
if expression[index - 1] == "~":
char_has_not = True
else:
char_has_not = False
# Check if there is no operator; Must be left side
if operator == None:
left = {
"has_not": char_has_not,
"value": char
}
else:
right = {
"has_not": char_has_not,
"value": char
}
char_has_not = False
if char not in variables:
variables.append(char)

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 parent_depth != 0:
raise UnbalancedParentheses("You have a missing parenthesis somewhere.")
variables.sort()
# Check if the expression is a single expression wrapped in parentheses
if operator == right == None:
has_not = left["has_not"]
operator = left["operator"]
right = left["right"]
left = left["left"]
return {
"expression": {
"has_not": has_not,
"left": left,
"operator": operator,
"right": right
},
"variables": variables
}

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 (->)

if self._operator == "->":
if self.has_not():
return not (not left or right)
return not left or right

Biconditional (<->)

if self._operator == "<->":
if self.has_not():
return not (left == right)
return left == right

NAND (|)

if self._operator == "|":
if self.has_not():
return left and right
return not (left and right)

NOR (⬇)

if self._operator == "⬇":
if self.has_not():
return left or right
return not (left or right)

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.

## (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 ^ qIn discrete math, the basic operators are:

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

## Logic Parser Layout

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

`errors.py`

which will hold all the`Exception`

s 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 expressionNow 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: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 expressionsuch 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 holdsAgain, 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 values2 variables have 4 possible truth values3 variables have 8 possible truth valuesAs 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

ncolumns wherenis 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

endlessamount of columns that exist.Now this last segment will add all the truth values for a

variable into it's own evaluation.singleThe 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'ttoocomplex 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 theentireexpression 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 reasonorif 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

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,

definitelylet me know either by leaving a comment, pinging me in Repl.it's Discord Server, or pinging me in my own Discord Server.Nice work on this :) check out your profile, you now have the Content Creator badge!

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