Symbolic Logic Expressions

An expression is created from a string that consists of the operators !, &, |, ->, <->, which correspond to the logical functions not, and, or, if then, if and only if, respectively. Variable names must start with a letter and contain only alpha-numerics and the underscore character.

AUTHORS:

• Chris Gorecki (2007): initial version

• William Stein (2007-08-31): integration into Sage 2.8.4

• Paul Scurek (2013-08-03): updated docstring formatting

class sage.logic.logic.SymbolicLogic

Bases: object

EXAMPLES:

This example illustrates how to create a boolean formula and print its table:

sage: log = SymbolicLogic()
sage: s = log.statement("a&b|!(c|a)")
sage: t = log.truthtable(s)
sage: log.print_table(t)
a     | b     | c     | value |
--------------------------------
False | False | False | True  |
False | False | True  | False |
False | True  | False | True  |
False | True  | True  | False |
True  | False | False | False |
True  | False | True  | False |
True  | True  | False | True  |
True  | True  | True  | True  |

combine(statement1, statement2)

Return a new statement which contains the two statements or’d together.

INPUT:

• statement1 – the first statement

• statement2 – the second statement

OUTPUT:

A new statement which or’d the given statements together.

EXAMPLES:

sage: log = SymbolicLogic()
sage: s1 = log.statement("(a&b)")
sage: s2 = log.statement("b")
sage: log.combine(s1,s2)
[['OPAREN',
  'OPAREN',
  'OPAREN',
  'a',
  'AND',
  'b',
  'CPAREN',
  'CPAREN',
  'OR',
  'OPAREN',
  'b',
  'CPAREN',
  'CPAREN'],
 {'a': 'False', 'b': 'False'},
 ['a', 'b', 'b']]

print_table(table)

Return a truthtable corresponding to the given statement.

INPUT:

• table – object created by truthtable() method; it contains the variable values and the evaluation of the statement

OUTPUT:

A formatted version of the truth table.

EXAMPLES:

This example illustrates the creation of a statement and its truth table:

sage: log = SymbolicLogic()
sage: s = log.statement("a&b|!(c|a)")
sage: t = log.truthtable(s) #creates the whole truth table
sage: log.print_table(t)
a     | b     | c     | value |
--------------------------------
False | False | False | True  |
False | False | True  | False |
False | True  | False | True  |
False | True  | True  | False |
True  | False | False | False |
True  | False | True  | False |
True  | True  | False | True  |
True  | True  | True  | True  |

We can also print a shortened table:

sage: t = log.truthtable(s, 1, 5)
sage: log.print_table(t)
a     | b     | c     | value |
--------------------------------
False | False | True  | False |
False | True  | False | True  |
False | True  | True  | False |
True  | False | False | False |

prove(statement)

A function to test to see if the statement is a tautology or contradiction by calling a C++ library.

Todo

Implement this method.

EXAMPLES:

sage: log = SymbolicLogic()
sage: s = log.statement("a&b|!(c|a)")
sage: log.prove(s)
Traceback (most recent call last):
...
NotImplementedError

simplify(table)

Call a C++ implementation of the ESPRESSO algorithm to simplify the given truth table.

Todo

Implement this method.

EXAMPLES:

sage: log = SymbolicLogic()
sage: s = log.statement("a&b|!(c|a)")
sage: t = log.truthtable(s)
sage: log.simplify(t)
Traceback (most recent call last):
...
NotImplementedError

statement(s)

Return a token list to be used by other functions in the class

INPUT:

• s – a string containing the logic expression to be manipulated

• global vars – a dictionary with variable names as keys and the variables’ current boolean values as dictionary values

• global vars_order – a list of the variables in the order that they are found

OUTPUT:

A list of length three containing the following in this order:

1. a list of tokens

2. a dictionary of variable/value pairs

3. a list of the variables in the order they were found

EXAMPLES:

This example illustrates the creation of a statement:

sage: log = SymbolicLogic()
sage: s = log.statement("a&b|!(c|a)")
sage: s2 = log.statement("!((!(a&b)))")

It is an error to use invalid variable names:

sage: s = log.statement("3fe & @q")
Invalid variable name:  3fe
Invalid variable name:  @q

It is also an error to use invalid syntax:

sage: s = log.statement("a&&b")
Malformed Statement
sage: s = log.statement("a&((b)")
Malformed Statement

truthtable(statement, start=0, end=-1)

Return a truth table.

INPUT:

• statement – a list; it contains the tokens and the two global variables vars and vars_order

• start – (default: 0) an integer; this represents the row of the truth table from which to start

• end – (default: -1) an integer; this represents the last row of the truth table to be created

OUTPUT:

The truth table as a 2d array with the creating formula tacked to the front.

EXAMPLES:

This example illustrates the creation of a statement:

sage: log = SymbolicLogic()
sage: s = log.statement("a&b|!(c|a)")
sage: t = log.truthtable(s) #creates the whole truth table

We can now create truthtable of rows 1 to 5:

sage: s2 = log.truthtable(s, 1, 5); s2
[[['OPAREN',
   'a',
   'AND',
   'b',
   'OR',
   'NOT',
   'OPAREN',
   'c',
   'OR',
   'a',
   'CPAREN',
   'CPAREN'],
  {'a': 'True', 'b': 'False', 'c': 'False'},
  ['a', 'b', 'c']],
 ['False', 'False', 'True', 'False'],
 ['False', 'True', 'False', 'True'],
 ['False', 'True', 'True', 'False'],
 ['True', 'False', 'False', 'False']]

Note

When sent with no start or end parameters this is an exponential time function requiring \(O(2^n)\) time, where \(n\) is the number of variables in the logic expression

sage.logic.logic.eval(toks)

Evaluate the expression contained in toks.

INPUT:

• toks – a list of tokens; this represents a boolean expression

OUTPUT:

A boolean value to be determined as follows:

• True if expression evaluates to True.

• False if expression evaluates to False.

Note

This function is for internal use by the SymbolicLogic class. The evaluations rely on setting the values of the variables in the global dictionary vars.

sage.logic.logic.eval_and_op(lval, rval)

Apply the ‘and’ operator to lval and rval.

INPUT:

• lval – a string; this represents the value of the variable appearing to the left of the ‘and’ operator

• rval – a string; this represents the value of the variable appearing to the right of the ‘and’ operator

OUTPUT:

The result of applying ‘and’ to lval and rval as a string.

Note

This function is for internal use by the SymbolicLogic class.

sage.logic.logic.eval_bin_op(args)

Return a boolean value based on the truth table of the operator in args.

INPUT:

• args – a list of length 3; this contains a variable name, then a binary operator, and then a variable name, in that order

OUTPUT:

A boolean value; this is the evaluation of the operator based on the truth values of the variables.

Note

This function is for internal use by the SymbolicLogic class.

sage.logic.logic.eval_iff_op(lval, rval)

Apply the ‘if and only if’ operator to lval and rval.

INPUT:

• lval – a string; this represents the value of the variable appearing to the left of the ‘if and only if’ operator

• rval – a string; this represents the value of the variable appearing to the right of the ‘if and only if’ operator

OUTPUT:

A string representing the result of applying ‘if and only if’ to lval and rval.

Note

This function is for internal use by the SymbolicLogic class.

sage.logic.logic.eval_ifthen_op(lval, rval)

Apply the ‘if then’ operator to lval and rval.

INPUT:

• lval – a string; this represents the value of the variable appearing to the left of the ‘if then’ operator

• rval – a string;t his represents the value of the variable appearing to the right of the ‘if then’ operator

OUTPUT:

A string representing the result of applying ‘if then’ to lval and rval.

Note

This function is for internal use by the SymbolicLogic class.

sage.logic.logic.eval_ltor_toks(lrtoks)

Evaluates the expression contained in lrtoks.

INPUT:

• lrtoks – a list of tokens; this represents a part of a boolean formula that contains no inner parentheses

OUTPUT:

A boolean value to be determined as follows:

• True if expression evaluates to True.

• False if expression evaluates to False.

Note

This function is for internal use by the SymbolicLogic class. The evaluations rely on setting the values of the variables in the global dictionary vars.

sage.logic.logic.eval_mon_op(args)

Return a boolean value based on the truth table of the operator in args.

INPUT:

• args – a list of length 2; this contains the token ‘NOT’ and then a variable name

OUTPUT:

A boolean value to be determined as follows:

• True if the variable in args is False.

• False if the variable in args is True.

Note

This function is for internal use by the SymbolicLogic class.

sage.logic.logic.eval_or_op(lval, rval)

Apply the ‘or’ operator to lval and rval.

INPUT:

• lval – a string; this represents the value of the variable appearing to the left of the ‘or’ operator

• rval – a string; this represents the value of the variable appearing to the right of the ‘or’ operator

OUTPUT:

A string representing the result of applying ‘or’ to lval and rval.

Note

This function is for internal use by the SymbolicLogic class.

sage.logic.logic.get_bit(x, c)

Determine if bit c of the number x is 1.

INPUT:

• x – an integer; this is the number from which to take the bit

• c – an integer; this is the bit number to be taken

OUTPUT:

A boolean value to be determined as follows:

• True if bit c of x is 1.

• False if bit c of x is not 1.

Note

This function is for internal use by the SymbolicLogic class.

EXAMPLES:

sage: from sage.logic.logic import get_bit
sage: get_bit(int(2), int(1))
'True'
sage: get_bit(int(8), int(0))
'False'

sage.logic.logic.reduce_bins(lrtoks)

Evaluate lrtoks to a single boolean value.

INPUT:

• lrtoks – a list of tokens; this represents a part of a boolean formula that contains no inner parentheses or monotonic operators

OUTPUT:

None; the pointer to lrtoks is now a list containing True or False.

Note

This function is for internal use by the SymbolicLogic class.

sage.logic.logic.reduce_monos(lrtoks)

Replace monotonic operator/variable pairs with a boolean value.

INPUT:

• lrtoks – a list of tokens; this represents a part of a boolean expression that contains now inner parentheses

OUTPUT:

None; the pointer to lrtoks is now a list containing monotonic operators.

Note

This function is for internal use by the SymbolicLogic class.

sage.logic.logic.tokenize(s, toks)

Tokenize s and place the tokens of s in toks.

INPUT:

• s – a string; this contains a boolean expression

• toks – a list; this will be populated with the tokens of s

OUTPUT:

None; the tokens of s are placed in toks.

Note

This function is for internal use by the SymbolicLogic class.

EXAMPLES:

sage: from sage.logic.logic import tokenize
sage: toks = []
sage: tokenize("(a&b)|c", toks)
sage: toks
['OPAREN', 'a', 'AND', 'b', 'CPAREN', 'OR', 'c', 'CPAREN']