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[source]#
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 |
>>> from sage.all import * >>> log = SymbolicLogic() >>> s = log.statement("a&b|!(c|a)") >>> t = log.truthtable(s) >>> 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)[source]#
Return a new statement which contains the two statements or’d together.
INPUT:
statement1
– the first statementstatement2
– 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']]
>>> from sage.all import * >>> log = SymbolicLogic() >>> s1 = log.statement("(a&b)") >>> s2 = log.statement("b") >>> 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)[source]#
Return a truthtable corresponding to the given statement.
INPUT:
table
– object created bytruthtable()
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 |
>>> from sage.all import * >>> log = SymbolicLogic() >>> s = log.statement("a&b|!(c|a)") >>> t = log.truthtable(s) #creates the whole truth table >>> 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 |
>>> from sage.all import * >>> t = log.truthtable(s, Integer(1), Integer(5)) >>> 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)[source]#
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
>>> from sage.all import * >>> log = SymbolicLogic() >>> s = log.statement("a&b|!(c|a)") >>> log.prove(s) Traceback (most recent call last): ... NotImplementedError
- simplify(table)[source]#
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
>>> from sage.all import * >>> log = SymbolicLogic() >>> s = log.statement("a&b|!(c|a)") >>> t = log.truthtable(s) >>> log.simplify(t) Traceback (most recent call last): ... NotImplementedError
- statement(s)[source]#
Return a token list to be used by other functions in the class
INPUT:
s
– a string containing the logic expression to be manipulatedglobal vars
– a dictionary with variable names as keys and the variables’ current boolean values as dictionary valuesglobal 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:
a list of tokens
a dictionary of variable/value pairs
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)))")
>>> from sage.all import * >>> log = SymbolicLogic() >>> s = log.statement("a&b|!(c|a)") >>> 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
>>> from sage.all import * >>> 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
>>> from sage.all import * >>> s = log.statement("a&&b") Malformed Statement >>> s = log.statement("a&((b)") Malformed Statement
- truthtable(statement, start=0, end=-1)[source]#
Return a truth table.
INPUT:
statement
– a list; it contains the tokens and the two global variables vars and vars_orderstart
– (default: 0) an integer; this represents the row of the truth table from which to startend
– (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
>>> from sage.all import * >>> log = SymbolicLogic() >>> s = log.statement("a&b|!(c|a)") >>> 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']]
>>> from sage.all import * >>> s2 = log.truthtable(s, Integer(1), Integer(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)[source]#
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 toTrue
.False
if expression evaluates toFalse
.
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)[source]#
Apply the ‘and’ operator to
lval
andrval
.INPUT:
lval
– a string; this represents the value of the variable appearing to the left of the ‘and’ operatorrval
– 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
andrval
as a string.Note
This function is for internal use by the
SymbolicLogic
class.
- sage.logic.logic.eval_bin_op(args)[source]#
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)[source]#
Apply the ‘if and only if’ operator to
lval
andrval
.INPUT:
lval
– a string; this represents the value of the variable appearing to the left of the ‘if and only if’ operatorrval
– 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
andrval
.Note
This function is for internal use by the
SymbolicLogic
class.
- sage.logic.logic.eval_ifthen_op(lval, rval)[source]#
Apply the ‘if then’ operator to
lval
andrval
.INPUT:
lval
– a string; this represents the value of the variable appearing to the left of the ‘if then’ operatorrval
– 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
andrval
.Note
This function is for internal use by the
SymbolicLogic
class.
- sage.logic.logic.eval_ltor_toks(lrtoks)[source]#
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 toTrue
.False
if expression evaluates toFalse
.
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)[source]#
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 inargs
isFalse
.False
if the variable inargs
isTrue
.
Note
This function is for internal use by the
SymbolicLogic
class.
- sage.logic.logic.eval_or_op(lval, rval)[source]#
Apply the ‘or’ operator to
lval
andrval
.INPUT:
lval
– a string; this represents the value of the variable appearing to the left of the ‘or’ operatorrval
– 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
andrval
.Note
This function is for internal use by the
SymbolicLogic
class.
- sage.logic.logic.get_bit(x, c)[source]#
Determine if bit
c
of the numberx
is 1.INPUT:
x
– an integer; this is the number from which to take the bitc
– an integer; this is the bit number to be taken
OUTPUT:
A boolean value to be determined as follows:
True
if bitc
ofx
is 1.False
if bitc
ofx
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'
>>> from sage.all import * >>> from sage.logic.logic import get_bit >>> get_bit(int(Integer(2)), int(Integer(1))) 'True' >>> get_bit(int(Integer(8)), int(Integer(0))) 'False'
- sage.logic.logic.reduce_bins(lrtoks)[source]#
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 containingTrue
orFalse
.Note
This function is for internal use by the
SymbolicLogic
class.
- sage.logic.logic.reduce_monos(lrtoks)[source]#
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 tolrtoks
is now a list containing monotonic operators.Note
This function is for internal use by the
SymbolicLogic
class.
- sage.logic.logic.tokenize(s, toks)[source]#
Tokenize
s
and place the tokens ofs
intoks
.INPUT:
s
– a string; this contains a boolean expressiontoks
– a list; this will be populated with the tokens ofs
OUTPUT:
None
; the tokens ofs
are placed intoks
.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']
>>> from sage.all import * >>> from sage.logic.logic import tokenize >>> toks = [] >>> tokenize("(a&b)|c", toks) >>> toks ['OPAREN', 'a', 'AND', 'b', 'CPAREN', 'OR', 'c', 'CPAREN']