9
\$\begingroup\$

This code creates a truth table from a statement in logic. The statement is input as a string, and it is identified as a tautology if it is true for all true and false combinations of the variables.

Note: brackets must contain only one logical operator. For example, \$(A \lor B \lor C)\$ does not work, but \$(A \lor B) \lor C\$ does.

import itertools
import re
from tabulate import tabulate
from collections import OrderedDict

symbols = {'∧', '∨', '→', '↔'} # Symbols for easy copying into logical statement

statement = '~(A ∧ B) ↔ (~A ∨ ~B)'


def parenthetic_contents(string):
    """
    From http://stackoverflow.com/questions/4284991/parsing-nested-parentheses-in-python-grab-content-by-level

    Generates parenthesized contents in string as pairs (level, contents).

    >>> list(parenthetic_contents('~(p ∨ q) ↔ (~p ∧ ~q)')
    [(0, 'p ∨ q'), (0, '~p ∧ ~q')]
    """
    stack = []
    for i, char in enumerate(string):
        if char == '(':
            stack.append(i)
        elif char == ')' and stack:
            start = stack.pop()
            yield (len(stack), string[start + 1: i])


def conditional(p, q):
    """Evaluates truth of conditional for boolean variables p and q."""
    return False if p and not q else True


def biconditional(p, q):
    """ Evaluates truth of biconditional for boolean variables p and q."""
    return (True if p and q
        else True if not p and not q 
        else False)


def and_func(p, q):
    """ Evaluates truth of AND operator for boolean variables p and q."""
    return p and q


def or_func(p, q):
    """ Evaluates truth of OR operator for boolean variables p and q."""
    return p or q

def negate(p):
    """ Evaluates truth of NOT operator for boolean variables p and q."""
    return not p

def apply_negations(string):
    """ 
    Applies the '~' operator when it appears directly before a binary number.

    >>> apply_negations('~1 ∧ 0')
    '0 ∧ 0'
    """
    new_string = string[:]
    for i, char in enumerate(string):
        if char == '~':
            try:
                next_char = string[i+1] # Character proceeding '~'
                num = int(next_char)
                negated = str(int(negate(num)))
                new_string = new_string.replace('~'+string[i+1], negated)
            except:
                # Character proceeding '~' is not a number
                pass
    return new_string


def eval_logic(string):
    """
    Returns the value of a simple logical statement with binary numbers.

    >>> eval_logic('1 ∧ 0')
    0
    """

    string = string.replace(' ', '') # Remove spaces
    string = apply_negations(string) # Switch ~0 to 1, ~1 to 0
    new_string = string[:]
    operators = {
        '∧': and_func,
        '∨': or_func,
        '→': conditional,
        '↔': biconditional,
        }
    for i, char in enumerate(string):
        if char in operators:
            logical_expression = string[i-1 : i+2]
            truth_value_1, truth_value_2 = int(string[i-1]), int(string[i+1])
            boolean = operators[char](truth_value_1, truth_value_2)
    try:
        return int(boolean) # Return boolean as 0 or 1
    except:
        # None of the logical operators were found in the string
        return int(string) # Return the value of the string itself


def get_variables(statement):
    """
    Finds all alphabetic characters in a logical statement string.
    Returns characters in a list.

    statement : str
        Statement containing variables and logical operators

    >>> get_variables('~(p ∨ q) ↔ (~p ∧ ~q)')
    ['p', 'q']
    """
    variables = {char for char in statement if char.isalpha()} # Identify variables
    variables = list(variables)
    variables.sort()
    return variables


def truth_combos(statement):
    """
    Returns a list of dictionaries, containing all possible values of the variables in a logical statement string.

    statement : str
        Statement containing variables and logical operators

    >>> truth_combos('(~(p ∨ q) ↔ (~p ∧ ~q))')
    [{'q': 1, 'p': 1}, {'q': 0, 'p': 1}, {'q': 1, 'p': 0}, {'q': 0, 'p': 0}]
    """
    variables = get_variables(statement)
    combo_list = []
    for booleans in itertools.product([True, False], repeat = len(variables)):
        int_bool = [int(x) for x in booleans] # Replace True with 1, False with 0
        combo_list.append(dict(zip(variables, int_bool)))
    return combo_list


def replace_variables(string, truth_values):
    """
    Replaces logical variables with truth values in a string.

    string : str
        Logical expression

    truth_values : dict
        Dictionary mapping variable letters to their current truth values (0/1)

    >>> replace_variables('Q ∨ R', {'Q': 1, 'R': 1, 'P': 1})
    '1 ∨ 1'
    """
    for variable in truth_values:
        bool_string = str(truth_values[variable])
        string = string.replace(variable, bool_string)
    return string


def simplify(valued_statement):
    """
    Simplifies a logical statement by evaluating the statements contained in the innermost parentheses.

    valued_statement : str
        Statement containing binary numbers and logical operators

    >>> simplify('(~(0 ∧ 0) ↔ (~0 ∨ ~0))')
    '(~0 ↔ 1)'
    """
    brackets_list = list(parenthetic_contents(valued_statement))
    if not brackets_list:
        # There are no brackets in the statement
        return str(eval_logic(valued_statement))
    deepest_level = max([i for (i,j) in brackets_list]) # Deepest level of nested brackets
    for level, string in brackets_list:
        if level == deepest_level:
            bool_string = str(eval_logic(string))
            valued_statement = valued_statement.replace('('+string+')', bool_string)
    return valued_statement


def solve(valued_statement):
    """ 
    Fully solves a logical statement. Returns answer as binary integer.

    valued_statement : str
        Statement containing binary numbers and logical operators

    >>> solve('(~(0 ∧ 0) ↔ (~0 ∨ ~0))')
    1
    """
    while len(valued_statement) > 1:
        valued_statement = simplify(valued_statement)
    return int(valued_statement)


def get_truth_table(statement):
    """ 

    Returns a truth table in the form of nested list.
    Also returns a boolean 'tautology' which is True if the logical statement is always true.

    statement : str
        Statement containing variables and logical operators

    >>> get_truth_table('~(A ∧ B) ↔ (~A ∨ ~B)')
    ([[1, 1, 1], [1, 0, 1], [0, 1, 1], [0, 0, 1]], True)
    """
    if statement[0] != '(':
        statement = '('+statement+')' # Add brackets to ends
    variables = get_variables(statement)
    combo_list = truth_combos(statement)
    truth_table_values = []
    tautology = True
    for truth_values in combo_list:
        valued_statement = replace_variables(statement, truth_values)
        ordered_truth_values = OrderedDict(sorted(truth_values.items()))
        answer = solve(valued_statement)
        truth_table_values.append(list(ordered_truth_values.values()) + [answer])
        if answer != 1:
            tautology = False
    return truth_table_values, tautology


variables = get_variables(statement)
truth_table_values, tautology = get_truth_table(statement)


print(
""" 
Logical statement: 

{}

Truth Table: 

{}

Statement {} a tautology
""".format(
    statement,
    tabulate(truth_table_values, headers=variables + ['Answer']),
    'is' if tautology else 'is not'
))  

Output:

Logical statement: 

~(A ∧ B) ↔ (~A ∨ ~B)

Truth Table: 

  A    B    Answer
---  ---  --------
  1    1         1
  1    0         1
  0    1         1
  0    0         1

Statement is a tautology

Another example, using \$ (((A \lor B) \land (A \rightarrow C)) \land (B \rightarrow C)) \rightarrow C\$:

Logical statement: 

(((A ∨ B) ∧ (A → C)) ∧ (B → C)) → C

Truth Table: 

  A    B    C    Answer
---  ---  ---  --------
  1    1    1         1
  1    1    0         1
  1    0    1         1
  1    0    0         1
  0    1    1         1
  0    1    0         1
  0    0    1         1
  0    0    0         1

Statement is a tautology
\$\endgroup\$
7
\$\begingroup\$

1. Bugs

  1. There's an infinite loop in solve:

    >>> get_truth_table('AB')
    ^C
      File "<stdin>", line 1, in <module>
      File "cr145465.py", line 215, in get_truth_table
        answer = solve(valued_statement)
      File "cr145465.py", line 190, in solve
        valued_statement = simplify(valued_statement)
      File "cr145465.py", line 170, in simplify
        return str(eval_logic(valued_statement))
    KeyboardInterrupt
    

    The problem is here:

    while len(valued_statement) > 1:
        valued_statement = simplify(valued_statement)
    

    Of course the input 'AB' is invalid, but I would expect to get a SyntaxError instead of an infinite loop.

  2. Other inputs containing syntax errors result in exceptions that are hard to understand. For example:

    >>> get_truth_table('')
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
      File "cr145465.py", line 206, in get_truth_table
        if statement[0] != '(':
    IndexError: string index out of range
    

    Another example:

    >>> get_truth_table('~~A')
    Traceback (most recent call last):
      File "cr145465.py", line 97, in eval_logic
        return int(boolean) # Return boolean as 0 or 1
    UnboundLocalError: local variable 'boolean' referenced before assignment
    
    During handling of the above exception, another exception occurred:
    
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
      File "cr145465.py", line 215, in get_truth_table
        answer = solve(valued_statement)
      File "cr145465.py", line 190, in solve
        valued_statement = simplify(valued_statement)
      File "cr145465.py", line 174, in simplify
        bool_string = str(eval_logic(string))
      File "cr145465.py", line 100, in eval_logic
        return int(string) # Return the value of the string itself
    ValueError: invalid literal for int() with base 10: '~0'
    
  3. Some incorrect inputs succeed but produce meaningless results:

    >>> get_truth_table('7')
    ([[7]], False)
    

    When invalid input is encountered, it is a good idea to raise a SyntaxError with an explanation of the problem.

2. Alternative approach

I'm not going to review the code in any detail, because the approach taken here (repeated string substitution) is slow and fragile and hard to get good error messages out of.

So instead, I'm going to demonstrate the standard way to tackle this kind of problem. The idea is to combine three processing stages:

  1. Tokenization. In this stage the input string is turned into a sequence of tokens. For example, given this input:

    ~(A ∧ B) ↔ (~A ∨ ~B)
    

    the tokenizer might emit this sequence of tokens:

    '~', '(', 'A', '∧', 'B', ')', '↔', '(', '~', 'A', '∨', '~', 'B', ')', <end of input>
    
  2. Parsing. In this stage the sequence of tokens is turned into a parse tree, a data structure corresponding to the syntactic structure of the input. For example, given the input above, the parser might construct the following data structure:

    BinaryOp(
        left=UnaryOp(
            op=<built-in function not_>,
            operand=BinaryOp(
                left=Variable(name='A'),
                op=<built-in function and_>,
                right=Variable(name='B'))),
        op=<built-in function eq>,
        right=BinaryOp(
            left=UnaryOp(
                op=<built-in function not_>,
                operand=Variable(name='A')),
            op=<built-in function or_>,
            right=UnaryOp(
                op=<built-in function not_>,
                operand=Variable(name='B'))))
    
  3. Expression evaluation. This stage takes a parse tree for an expression, together with an environment (a data structure mapping variables to their values), and returns the value of the expression.

There are several good reasons to solve the problem using this approach:

  1. It's the standard approach, so other programmers will easily understand how it works.

  2. It's efficient: each stage needs to pass over its input exactly once, thus avoiding the repeated string substitutions of the code in the post.

  3. Splitting the work into steps with clearly defined inputs and outputs makes it easier to test.

  4. The approach extends to more complicated applications, such as interpretation of programming languages.

3. Tokenization

Tokenization is often implemented using a finite-state machine but it's also often convenient to use a regular expression.

import re

# Regular expression matching optional whitespace followed by a token
# (if group 1 matches) or an error (if group 2 matches).
TOKEN_RE = re.compile(r'\s*(?:([A-Za-z01()~∧∨→↔])|(\S))')

# Special token indicating the end of the input string.
TOKEN_END = '<end of input>'

def tokenize(s):
    """Generate tokens from the string s, followed by TOKEN_END."""
    for match in TOKEN_RE.finditer(s):
        token, error = match.groups()
        if token:
            yield token
        else:
            raise SyntaxError("Unexpected character {!r}".format(error))
    yield TOKEN_END

4. Parsing

Before you can write a parser, you need to make a formal grammar. This is probably the most difficult bit of the whole thing. Here's the grammar that I'm going to use, written in Backus–Naur form:

  1. 〈Variable〉 ::= "A" | "B" | … | "Z" | "a" | "b" | ... | "z"

  2. 〈Constant〉 ::= "0" | "1"

  3. 〈Term〉 ::= 〈Variable〉 | 〈Constant〉 | "(" 〈Disjunction〉 ")"

  4. 〈UnaryExpr〉 ::= "~" 〈UnaryExpr〉 | 〈Term〉

  5. 〈Implication〉 ::= 〈UnaryExpr〉 (("" | "") 〈Implication〉)?

  6. 〈Conjunction〉 ::= 〈Implication〉 ("" 〈Conjunction〉)?

  7. 〈Disjunction〉 ::= 〈Conjunction〉 ("" 〈Disjunction〉)?

In order to construct the parse tree, we'll need data structures for each kind of node in the tree, most easily defined using collections.namedtuple:

from collections import namedtuple

Constant = namedtuple('Constant', 'value')
Variable = namedtuple('Variable', 'name')
UnaryOp = namedtuple('UnaryOp', 'op operand')
BinaryOp = namedtuple('BinaryOp', 'left op right')

There are lots of different techniques for writing parsers. I could use a parser generator like pyparsing, that constructs the parser from a representation of the formal grammar, but I think it's more illustrative to write a recursive descent parser by hand.

We'll start with some global constants:

import operator
from string import ascii_lowercase, ascii_uppercase

# Tokens representing Boolean constants (0=False, 1=True).
CONSTANTS = '01'

# Tokens representing variables.
VARIABLES = set(ascii_lowercase) | set(ascii_uppercase)

# Map from unary operator to function implementing it.
UNARY_OPERATORS = {
    '~': operator.not_,
}

# Map from binary operator to function implementing it.
BINARY_OPERATORS = {
    '∧': operator.and_,
    '∨': operator.or_,
    '→': lambda a, b: not a or b,
    '↔': operator.eq,
}

Note that I've used the built-in functions operator.eq, operator.and_, operator.or_, and operator.not_, instead of biconditional, and_func, or_func, and negate respectively.

Now for the recursive descent parser:

def parse(s):
    """Parse s as a Boolean expression and return the parse tree."""
    tokens = tokenize(s)        # Stream of tokens.
    token = next(tokens)        # The current token.

    def error(expected):
        # Current token failed to match, so raise syntax error.
        raise SyntaxError("Expected {} but found {!r}"
                          .format(expected, token))

    def match(valid_tokens):
        # If the current token is found in valid_tokens, consume it
        # and return True. Otherwise, return False.
        nonlocal token
        if token in valid_tokens:
            token = next(tokens)
            return True
        else:
            return False

    def term():
        # Parse a <Term> starting at the current token.
        t = token
        if match(VARIABLES):
            return Variable(name=t)
        elif match(CONSTANTS):
            return Constant(value=(t == '1'))
        elif match('('):
            tree = disjunction()
            if match(')'):
                return tree
            else:
                error("')'")
        else:
            error("term")

    def unary_expr():
        # Parse a <UnaryExpr> starting at the current token.
        t = token
        if match('~'):
            operand = unary_expr()
            return UnaryOp(op=UNARY_OPERATORS[t], operand=operand)
        else:
            return term()

    def binary_expr(parse_left, valid_operators, parse_right):
        # Parse a binary expression starting at the current token.
        # Call parse_left to parse the left operand; the operator must
        # be found in valid_operators; call parse_right to parse the
        # right operand.
        left = parse_left()
        t = token
        if match(valid_operators):
            right = parse_right()
            return BinaryOp(left=left, op=BINARY_OPERATORS[t], right=right)
        else:
            return left

    def implication():
        # Parse an <Implication> starting at the current token.
        return binary_expr(unary_expr, '→↔', implication)

    def conjunction():
        # Parse a <Conjunction> starting at the current token.
        return binary_expr(implication, '∧', conjunction)

    def disjunction():
        # Parse a <Disjunction> starting at the current token.
        return binary_expr(conjunction, '∨', disjunction)

    tree = disjunction()
    if token != TOKEN_END:
        error("end of input")
    return tree

Let's try it:

>>> parse('~(A ∨ B) ↔ (~A ∧ ~B)')
BinaryOp(left=UnaryOp(op=<built-in function not_>, operand=BinaryOp(left=Variable(name='A'), op=<built-in function or_>, right=Variable(name='B'))), op=<built-in function eq>, right=BinaryOp(left=UnaryOp(op=<built-in function not_>, operand=Variable(name='A')), op=<built-in function and_>, right=UnaryOp(op=<built-in function not_>, operand=Variable(name='B'))))

5. Evaluation

Evaluation of a parse tree can be done by recursively evaluating the subtrees and then combining the results:

def evaluate(tree, env):
    """Evaluate the expression in the parse tree in the context of an
    environment mapping variable names to their values.

    """
    if isinstance(tree, Constant):
        return tree.value
    elif isinstance(tree, Variable):
        return env[tree.name]
    elif isinstance(tree, UnaryOp):
        return tree.op(evaluate(tree.operand, env))
    elif isinstance(tree, BinaryOp):
        return tree.op(evaluate(tree.left, env), evaluate(tree.right, env))
    else:
        raise TypeError("Expected tree, found {!r}".format(type(tree)))

For example:

>>> evaluate(parse('~A ∧ B'), dict(A=True, B=True))
False

6. Truth table

It should be clear now how to build the truth table for an expression using the new approach:

  1. Call parse to parse the expression, getting a parse tree.

  2. Compute the set of variables in the tree. (This step will follow the same kind of implementation pattern as evaluate above.)

  3. Iterate over the rows of the truth table, for example using itertools.product.

  4. For each row, build a dictionary mapping each variable to its value in the row, and then call evaluate to get the result for the row.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.