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:
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']
Apply func to each node of tree, and return a new parse tree.
INPUT:
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']]
Return the full syntax parse trees of the statements.
INPUT:
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:
Return a parse tree from a boolean formula s.
INPUT:
OUTPUT:
A list containing the prase tree and a list containing the variables in a boolean formula in this order:
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'])
Return a parse tree from toks, where each token in toks is atomic.
INPUT:
OUTPUT:
The parse tree as a nested list that depends on polish as follows:
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']]]
Return the full syntax parse tree from a boolean formula s.
INPUT:
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:
Convert a parse tree from prefix form to infix form.
INPUT:
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:
Recover the formula from a parse tree in prefix form.
INPUT:
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:
Recover the formula from a parse tree in prefix form.
INPUT:
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:
Convert a simple parse tree from prefix form to infix form.
INPUT:
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:
Return the tokens and the distinct variables appearing in a boolean formula s.
INPUT:
OUTPUT:
The tokens and variables as an ordered pair of lists in the following order:
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'])
Return a parse tree from the tokens in toks.
INPUT:
OUTPUT:
A parse tree in the form of a nested list that depends on polish as follows:
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']]]