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'])
>>> from sage.all import *
>>> import sage.logic.logicparser as logicparser
>>> s = 'a|b&c'
>>> t = logicparser.parse(s)
>>> 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']]]
>>> from sage.all import *
>>> import sage.logic.logicparser as logicparser
>>> s = '(a&b)->~~c'
>>> 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'])
>>> from sage.all import *
>>> import sage.logic.logicparser as logicparser
>>> s = '~(a|~b)<->(c->c)'
>>> 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']
>>> from sage.all import *
>>> import sage.logic.logicparser as logicparser
>>> t = ['(', 'a', '->', '~', 'c', ')']
>>> logicparser.tree_parse(t)
['->', 'a', ['~', 'c', None]]
>>> r = ['(', '~', '~', 'a', '|', 'b', ')']
>>> 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']
>>> from sage.all import *
>>> import sage.logic.logicparser as logicparser
>>> t = ['(', 'a', '->', '~', 'c', ')']
>>> logicparser.tree_parse(t, polish = True)
['->', 'a', ['~', 'c']]
>>> r = ['(', '~', '~', 'a', '|', 'b', ')']
>>> logicparser.tree_parse(r, polish = True)
['|', ['~', ['~', 'a']], 'b']
- sage.logic.logicparser.apply_func(tree, func)[source]¶
Apply
func
to each node oftree
, and return a new parse tree.INPUT:
tree
– a parse tree of a boolean formulafunc
– 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()
wherefunc
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']]
>>> from sage.all import * >>> import sage.logic.logicparser as logicparser >>> t = ['|', ['&', 'a', 'b'], ['&', 'a', 'c']] >>> f = lambda t: [t[Integer(0)], t[Integer(2)], t[Integer(1)]] >>> logicparser.apply_func(t, f) ['|', ['&', 'c', 'a'], ['&', 'b', 'a']]
- sage.logic.logicparser.get_trees(*statements)[source]¶
Return the full syntax parse trees of the statements.
INPUT:
*statements
– strings orBooleanFormula
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']]
>>> from sage.all import * >>> import sage.logic.propcalc as propcalc >>> import sage.logic.logicparser as logicparser >>> f = propcalc.formula("((a|b)&~~c)") >>> g = "a<->(~(c))" >>> h = "~b" >>> 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']]
>>> from sage.all import * >>> i = "(~q->p)" >>> j = propcalc.formula("a") >>> logicparser.get_trees(i, j) [['->', ['~', 'q'], 'p'], ['a']]
sage: k = "p" sage: logicparser.get_trees(k) [['p']]
>>> from sage.all import * >>> k = "p" >>> logicparser.get_trees(k) [['p']]
AUTHORS:
Paul Scurek (2013-08-06)
- sage.logic.logicparser.parse(s)[source]¶
Return a parse tree from a boolean formula
s
.INPUT:
s
– 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'])
>>> from sage.all import * >>> import sage.logic.logicparser as logicparser >>> s = 'a|b&c' >>> t = logicparser.parse(s) >>> t (['|', 'a', ['&', 'b', 'c']], ['a', 'b', 'c'])
- sage.logic.logicparser.parse_ltor(toks, n=0, polish=False)[source]¶
Return a parse tree from
toks
, where each token intoks
is atomic.INPUT:
toks
– list of tokens; each token is atomicn
– integer (default: 0) representing which order of operations are occurringpolish
– boolean (default:False
); whenTrue
, 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()
whenpolish
isFalse
:sage: import sage.logic.logicparser as logicparser sage: t = ['a', '|', 'b', '&', 'c'] sage: logicparser.parse_ltor(t) ['|', 'a', ['&', 'b', 'c']]
>>> from sage.all import * >>> import sage.logic.logicparser as logicparser >>> t = ['a', '|', 'b', '&', 'c'] >>> 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']
>>> from sage.all import * >>> import sage.logic.logicparser as logicparser >>> t = ['a', '->', '~', '~', 'b'] >>> logicparser.parse_ltor(t) ['->', 'a', 'b']
We now repeat the previous example, but with
polish
beingTrue
:sage: import sage.logic.logicparser as logicparser sage: t = ['a', '->', '~', '~', 'b'] sage: logicparser.parse_ltor(t, polish = True) ['->', 'a', ['~', ['~', 'b']]]
>>> from sage.all import * >>> import sage.logic.logicparser as logicparser >>> t = ['a', '->', '~', '~', 'b'] >>> logicparser.parse_ltor(t, polish = True) ['->', 'a', ['~', ['~', 'b']]]
- sage.logic.logicparser.polish_parse(s)[source]¶
Return the full syntax parse tree from a boolean formula
s
.INPUT:
s
– 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']]]
>>> from sage.all import * >>> import sage.logic.logicparser as logicparser >>> s = 'a|~~b' >>> t = logicparser.polish_parse(s) >>> t ['|', 'a', ['~', ['~', 'b']]]
AUTHORS:
Paul Scurek (2013-08-03)
- sage.logic.logicparser.prefix_to_infix(prefix_tree)[source]¶
Convert a parse tree from prefix form to infix form.
INPUT:
prefix_tree
– list; this is a full syntax parse tree in prefix form
OUTPUT: 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']]
>>> from sage.all import * >>> import sage.logic.logicparser as logicparser >>> import sage.logic.propcalc as propcalc >>> t = ['|', ['~', 'a'], ['&', 'b', 'c']] >>> 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']]]]]
>>> from sage.all import * >>> f = propcalc.formula("(a&~b)<->~~~(c|d)") >>> logicparser.prefix_to_infix(f.full_tree()) [['a', '&', ['~', 'b']], '<->', ['~', ['~', ['~', ['c', '|', 'd']]]]]
Note
The function
polish_parse()
may be passed as an argument, buttree_parse()
may not unless the parameterpolish
is set toTrue
.AUTHORS:
Paul Scurek (2013-08-06)
- sage.logic.logicparser.recover_formula(prefix_tree)[source]¶
Recover the formula from a parse tree in prefix form.
INPUT:
prefix_tree
– 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'
>>> from sage.all import * >>> import sage.logic.propcalc as propcalc >>> import sage.logic.logicparser as logicparser >>> t = ['->', ['&', 'a', ['~', ['~', 'c']]], ['~', ['|', ['~', 'c'], 'd']]] >>> logicparser.recover_formula(t) '(a&~~c)->~(~c|d)' >>> f = propcalc.formula("a&(~~c|d)") >>> logicparser.recover_formula(f.full_tree()) 'a&(~~c|d)' >>> r = ['~', 'a'] >>> logicparser.recover_formula(r) '~a' >>> s = ['d'] >>> logicparser.recover_formula(s) 'd'
Note
The function
polish_parse()
may be passed as an argument, buttree_parse()
may not unless the parameterpolish
is set toTrue
.AUTHORS:
Paul Scurek (2013-08-06)
- sage.logic.logicparser.recover_formula_internal(prefix_tree)[source]¶
Recover the formula from a parse tree in prefix form.
INPUT:
prefix_tree
– 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'
>>> from sage.all import * >>> import sage.logic.logicparser as logicparser >>> import sage.logic.propcalc as propcalc >>> t = ['->', 'a', 'b'] >>> logicparser.recover_formula_internal(t) '(a->b)' >>> r = ['~', 'c'] >>> logicparser.recover_formula_internal(r) '~c' >>> s = ['d'] >>> logicparser.recover_formula_internal(s) 'd'
We can pass
recover_formula_internal()
as an argument inapply_func()
:sage: f = propcalc.formula("~(d|c)<->(a&~~~c)") sage: logicparser.apply_func(f.full_tree(), logicparser.recover_formula_internal) '(~(d|c)<->(a&~~~c))'
>>> from sage.all import * >>> f = propcalc.formula("~(d|c)<->(a&~~~c)") >>> 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, buttree_parse()
may not unless the parameterpolish
is set toTrue
.AUTHORS:
Paul Scurek (2013-08-06)
- sage.logic.logicparser.to_infix_internal(prefix_tree)[source]¶
Convert a simple parse tree from prefix form to infix form.
INPUT:
prefix_tree
– 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']
>>> from sage.all import * >>> import sage.logic.logicparser as logicparser >>> import sage.logic.propcalc as propcalc >>> t = ['|', 'a', 'b'] >>> logicparser.to_infix_internal(t) ['a', '|', 'b']
We can pass
to_infix_internal()
as an argument inapply_func()
:sage: f = propcalc.formula("(a&~b)<->~~~(c|d)") sage: logicparser.apply_func(f.full_tree(), logicparser.to_infix_internal) [['a', '&', ['~', 'b']], '<->', ['~', ['~', ['~', ['c', '|', 'd']]]]]
>>> from sage.all import * >>> f = propcalc.formula("(a&~b)<->~~~(c|d)") >>> 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, buttree_parse()
may not unless the parameterpolish
is set toTrue
.AUTHORS:
Paul Scurek (2013-08-06)
- sage.logic.logicparser.tokenize(s)[source]¶
Return the tokens and the distinct variables appearing in a boolean formula
s
.INPUT:
s
– 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 ins
A list containing the distinct variables in
s
, in the order they appear ins
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'])
>>> from sage.all import * >>> import sage.logic.logicparser as logicparser >>> s = 'a|b&c' >>> t = logicparser.tokenize(s) >>> t (['(', 'a', '|', 'b', '&', 'c', ')'], ['a', 'b', 'c'])
- sage.logic.logicparser.tree_parse(toks, polish=False)[source]¶
Return a parse tree from the tokens in
toks
.INPUT:
toks
– list of tokens from a boolean formulapolish
– boolean (default:False
); whenTrue
,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()
whenpolish
isFalse
:sage: import sage.logic.logicparser as logicparser sage: t = ['(', 'a', '|', 'b', '&', 'c', ')'] sage: logicparser.tree_parse(t) ['|', 'a', ['&', 'b', 'c']]
>>> from sage.all import * >>> import sage.logic.logicparser as logicparser >>> t = ['(', 'a', '|', 'b', '&', 'c', ')'] >>> logicparser.tree_parse(t) ['|', 'a', ['&', 'b', 'c']]
We now demonstrate the use of
tree_parse()
whenpolish
isTrue
:sage: t = ['(', 'a', '->', '~', '~', 'b', ')'] sage: logicparser.tree_parse(t) ['->', 'a', 'b'] sage: t = ['(', 'a', '->', '~', '~', 'b', ')'] sage: logicparser.tree_parse(t, polish = True) ['->', 'a', ['~', ['~', 'b']]]
>>> from sage.all import * >>> t = ['(', 'a', '->', '~', '~', 'b', ')'] >>> logicparser.tree_parse(t) ['->', 'a', 'b'] >>> t = ['(', 'a', '->', '~', '~', 'b', ')'] >>> logicparser.tree_parse(t, polish = True) ['->', 'a', ['~', ['~', 'b']]]