Module that creates and modifies parse trees of well formed boolean formulas.#

A parse tree of a boolean formula is a nested list, where each branch is either a single variable, or a formula composed of either two variables and a binary operator or one variable and a unary operator. The function parse produces a parse tree that is simplified for the purposes of more efficient truth value evaluation. The function polish_parse() produces the full parse tree of a boolean formula which is used in functions related to proof and inference. That is, parse() is meant to be used with functions in the logic module that perform semantic operations on a boolean formula, and polish_parse() is to be used with functions that perform syntactic operations on a boolean formula.

AUTHORS:

Chris Gorecki (2007): initial version
Paul Scurek (2013-08-01): added polish_parse, cleaned up python code, updated docstring formatting
Paul Scurek (2013-08-06): added recover_formula(), recover_formula_internal(), prefix_to_infix(), to_infix_internal()
Paul Scurek (2013-08-08): added get_trees, error handling in polish_parse, recover_formula_internal, and tree_parse

EXAMPLES:

Find the parse tree and variables of a string representation of a boolean formula:

sage: import sage.logic.logicparser as logicparser
sage: s = 'a|b&c'
sage: t = logicparser.parse(s)
sage: t
(['|', 'a', ['&', 'b', 'c']], ['a', 'b', 'c'])

Find the full syntax parse tree of a string representation of a boolean formula:

sage: import sage.logic.logicparser as logicparser
sage: s = '(a&b)->~~c'
sage: logicparser.polish_parse(s)
['->', ['&', 'a', 'b'], ['~', ['~', 'c']]]

Find the tokens and distinct variables of a boolean formula:

sage: import sage.logic.logicparser as logicparser
sage: s = '~(a|~b)<->(c->c)'
sage: logicparser.tokenize(s)
(['(', '~', '(', 'a', '|', '~', 'b', ')', '<->', '(', 'c', '->', 'c', ')', ')'], ['a', 'b', 'c'])

Find the parse tree of a boolean formula from a list of the formula’s tokens:

sage: import sage.logic.logicparser as logicparser
sage: t = ['(', 'a', '->', '~', 'c', ')']
sage: logicparser.tree_parse(t)
['->', 'a', ['~', 'c', None]]
sage: r = ['(', '~', '~', 'a', '|', 'b', ')']
sage: logicparser.tree_parse(r)
['|', 'a', 'b']

Find the full syntax parse tree of a boolean formula from a list of tokens:

sage: import sage.logic.logicparser as logicparser
sage: t = ['(', 'a', '->', '~', 'c', ')']
sage: logicparser.tree_parse(t, polish = True)
['->', 'a', ['~', 'c']]
sage: r = ['(', '~', '~', 'a', '|', 'b', ')']
sage: logicparser.tree_parse(r, polish = True)
['|', ['~', ['~', 'a']], 'b']

sage.logic.logicparser.apply_func(tree, func)#

Apply func to each node of tree, and return a new parse tree.

INPUT:

tree – a parse tree of a boolean formula
func – a function to be applied to each node of tree; this may be a function that comes from elsewhere in the logic module

OUTPUT:

The new parse tree in the form of a nested list.

EXAMPLES:

This example uses apply_func() where func switches two entries of tree:

sage: import sage.logic.logicparser as logicparser
sage: t = ['|', ['&', 'a', 'b'], ['&', 'a', 'c']]
sage: f = lambda t: [t[0], t[2], t[1]]
sage: logicparser.apply_func(t, f)
['|', ['&', 'c', 'a'], ['&', 'b', 'a']]

sage.logic.logicparser.get_trees(*statements)#

Return the full syntax parse trees of the statements.

INPUT:

*statements – strings or BooleanFormula instances

OUTPUT:

The parse trees in a list.

EXAMPLES:

This example illustrates finding the parse trees of multiple formulas.

sage: import sage.logic.propcalc as propcalc
sage: import sage.logic.logicparser as logicparser
sage: f = propcalc.formula("((a|b)&~~c)")
sage: g = "a<->(~(c))"
sage: h = "~b"
sage: logicparser.get_trees(f, g, h)
[['&', ['|', 'a', 'b'], ['~', ['~', 'c']]],
['<->', 'a', ['~', 'c']],
['~', 'b']]

sage: i = "(~q->p)"
sage: j = propcalc.formula("a")
sage: logicparser.get_trees(i, j)
[['->', ['~', 'q'], 'p'], ['a']]

sage: k = "p"
sage: logicparser.get_trees(k)
[['p']]

AUTHORS:

Paul Scurek (2013-08-06)

sage.logic.logicparser.parse(s)#

Return a parse tree from a boolean formula s.

INPUT:

s – a string containing a boolean formula

OUTPUT:

A list containing the parse tree and a list containing the variables in a boolean formula in this order:

the list containing the parse tree
the list containing the variables

EXAMPLES:

This example illustrates how to produce the parse tree of a boolean formula s:

sage: import sage.logic.logicparser as logicparser
sage: s = 'a|b&c'
sage: t = logicparser.parse(s)
sage: t
(['|', 'a', ['&', 'b', 'c']], ['a', 'b', 'c'])

sage.logic.logicparser.parse_ltor(toks, n=0, polish=False)#

Return a parse tree from toks, where each token in toks is atomic.

INPUT:

toks – a list of tokens. Each token is atomic.
n – (default: 0) an integer representing which order of operations are occurring
polish – (default: False) a boolean; when True, double negations are not cancelled and negated statements are turned into list of length two.

OUTPUT:

The parse tree as a nested list that depends on polish as follows:

If False, then return a simplified parse tree.
If True, then return the full syntax parse tree.

EXAMPLES:

This example illustrates the use of parse_ltor() when polish is False:

sage: import sage.logic.logicparser as logicparser
sage: t = ['a', '|', 'b', '&', 'c']
sage: logicparser.parse_ltor(t)
['|', 'a', ['&', 'b', 'c']]

sage: import sage.logic.logicparser as logicparser
sage: t = ['a', '->', '~', '~', 'b']
sage: logicparser.parse_ltor(t)
['->', 'a', 'b']

We now repeat the previous example, but with polish being True:

sage: import sage.logic.logicparser as logicparser
sage: t = ['a', '->', '~', '~', 'b']
sage: logicparser.parse_ltor(t, polish = True)
['->', 'a', ['~', ['~', 'b']]]

sage.logic.logicparser.polish_parse(s)#

Return the full syntax parse tree from a boolean formula s.

INPUT:

s – a string containing a boolean expression

OUTPUT:

The full syntax parse tree as a nested list.

EXAMPLES:

This example illustrates how to find the full syntax parse tree of a boolean formula:

sage: import sage.logic.logicparser as logicparser
sage: s = 'a|~~b'
sage: t = logicparser.polish_parse(s)
sage: t
['|', 'a', ['~', ['~', 'b']]]

AUTHORS:

Paul Scurek (2013-08-03)

sage.logic.logicparser.prefix_to_infix(prefix_tree)#

Convert a parse tree from prefix form to infix form.

INPUT:

prefix_tree – a list; this is a full syntax parse tree in prefix form

OUTPUT:

A list containing the tree in infix form.

EXAMPLES:

This example illustrates converting a prefix tree to an infix tree:

sage: import sage.logic.logicparser as logicparser
sage: import sage.logic.propcalc as propcalc
sage: t = ['|', ['~', 'a'], ['&', 'b', 'c']]
sage: logicparser.prefix_to_infix(t)
[['~', 'a'], '|', ['b', '&', 'c']]

sage: f = propcalc.formula("(a&~b)<->~~~(c|d)")
sage: logicparser.prefix_to_infix(f.full_tree())
[['a', '&', ['~', 'b']], '<->', ['~', ['~', ['~', ['c', '|', 'd']]]]]

Note

The function polish_parse() may be passed as an argument, but tree_parse() may not unless the parameter polish is set to True.

AUTHORS:

Paul Scurek (2013-08-06)

sage.logic.logicparser.recover_formula(prefix_tree)#

Recover the formula from a parse tree in prefix form.

INPUT:

prefix_tree – a list; this is a full syntax parse tree in prefix form

OUTPUT:

The formula as a string.

EXAMPLES:

This example illustrates the recovery of a formula from a parse tree:

sage: import sage.logic.propcalc as propcalc
sage: import sage.logic.logicparser as logicparser
sage: t = ['->', ['&', 'a', ['~', ['~', 'c']]], ['~', ['|', ['~', 'c'], 'd']]]
sage: logicparser.recover_formula(t)
'(a&~~c)->~(~c|d)'

sage: f = propcalc.formula("a&(~~c|d)")
sage: logicparser.recover_formula(f.full_tree())
'a&(~~c|d)'

sage: r = ['~', 'a']
sage: logicparser.recover_formula(r)
'~a'

sage: s = ['d']
sage: logicparser.recover_formula(s)
'd'

Note

The function polish_parse() may be passed as an argument, but tree_parse() may not unless the parameter polish is set to True.

AUTHORS:

Paul Scurek (2013-08-06)

sage.logic.logicparser.recover_formula_internal(prefix_tree)#

Recover the formula from a parse tree in prefix form.

INPUT:

prefix_tree – a list; this is a simple tree with at most one operator in prefix form

OUTPUT:

The formula as a string.

EXAMPLES:

This example illustrates recovering the formula from a parse tree:

sage: import sage.logic.logicparser as logicparser
sage: import sage.logic.propcalc as propcalc
sage: t = ['->', 'a', 'b']
sage: logicparser.recover_formula_internal(t)
'(a->b)'

sage: r = ['~', 'c']
sage: logicparser.recover_formula_internal(r)
'~c'

sage: s = ['d']
sage: logicparser.recover_formula_internal(s)
'd'

We can pass recover_formula_internal() as an argument in apply_func():

sage: f = propcalc.formula("~(d|c)<->(a&~~~c)")
sage: logicparser.apply_func(f.full_tree(), logicparser.recover_formula_internal)
'(~(d|c)<->(a&~~~c))'

Note

This function is for internal use by logicparser. The function recovers the formula of a simple parse tree in prefix form. A simple parse tree contains at most one operator.

The function polish_parse() may be passed as an argument, but tree_parse() may not unless the parameter polish is set to True.

AUTHORS:

Paul Scurek (2013-08-06)

sage.logic.logicparser.to_infix_internal(prefix_tree)#

Convert a simple parse tree from prefix form to infix form.

INPUT:

prefix_tree – a list; this is a simple parse tree in prefix form with at most one operator

OUTPUT:

The tree in infix form as a list.

EXAMPLES:

This example illustrates converting a simple tree from prefix to infix form:

sage: import sage.logic.logicparser as logicparser
sage: import sage.logic.propcalc as propcalc
sage: t = ['|', 'a', 'b']
sage: logicparser.to_infix_internal(t)
['a', '|', 'b']

We can pass to_infix_internal() as an argument in apply_func():

sage: f = propcalc.formula("(a&~b)<->~~~(c|d)")
sage: logicparser.apply_func(f.full_tree(), logicparser.to_infix_internal)
[['a', '&', ['~', 'b']], '<->', ['~', ['~', ['~', ['c', '|', 'd']]]]]

Note

This function is for internal use by logicparser. It converts a simple parse tree from prefix form to infix form. A simple parse tree contains at most one operator.

The function polish_parse() may be passed as an argument, but tree_parse() may not unless the parameter polish is set to True.

AUTHORS:

Paul Scurek (2013-08-06)

sage.logic.logicparser.tokenize(s)#

Return the tokens and the distinct variables appearing in a boolean formula s.

INPUT:

s – a string representation of a boolean formula

OUTPUT:

The tokens and variables as an ordered pair of lists in the following order:

A list containing the tokens of s, in the order they appear in s
A list containing the distinct variables in s, in the order they appear in s

EXAMPLES:

This example illustrates how to tokenize a string representation of a boolean formula:

sage: import sage.logic.logicparser as logicparser
sage: s = 'a|b&c'
sage: t = logicparser.tokenize(s)
sage: t
(['(', 'a', '|', 'b', '&', 'c', ')'], ['a', 'b', 'c'])

sage.logic.logicparser.tree_parse(toks, polish=False)#

Return a parse tree from the tokens in toks.

INPUT:

toks – a list of tokens from a boolean formula
polish – (default: False) a boolean; when True, tree_parse() will return the full syntax parse tree

OUTPUT:

A parse tree in the form of a nested list that depends on polish as follows:

If False, then return a simplified parse tree.
If True, then return the full syntax parse tree.

EXAMPLES:

This example illustrates the use of tree_parse() when polish is False:

sage: import sage.logic.logicparser as logicparser
sage: t = ['(', 'a', '|', 'b', '&', 'c', ')']
sage: logicparser.tree_parse(t)
['|', 'a', ['&', 'b', 'c']]

We now demonstrate the use of tree_parse() when polish is True:

sage: t = ['(', 'a', '->', '~', '~', 'b', ')']
sage: logicparser.tree_parse(t)
['->', 'a', 'b']
sage: t = ['(', 'a', '->', '~', '~', 'b', ')']
sage: logicparser.tree_parse(t, polish = True)
['->', 'a', ['~', ['~', 'b']]]