Boolean circuit evaluation using bitwise operations.
2 Stars
Updated Last
2 Years Ago
Started In
November 2014


Build Status

Boolean circuit tree implementation that uses bit strings to cache evaluation results and bitwise operations to evaluate new circuits based on existing trees.


The API is very simple. Trees consist of Operations (interior nodes), Variables, and Constants (both of which are leaf nodes). Right now all operations are functions of two parameters.


The constructor takes a single parameter, an integer in [0,5] (there are six possible variables.


The constructor takes a single boolean.


The constructor takes a function to apply, this must be a bitwise function that can operate on integers, and two sub-trees, to which the function will be applied.


Evaluates a tree for a given set of variable values. The variable values are specified as a bit string, where variable 5 is the high order bit and variable 0 is the low order bit.


Determine whether two trees describe the same function.


using BitCircuits

and(left, right) = left & right
or(left, right) = left | right

a = Variable(0)
b = Variable(1)

p = Operation(or, a, b) # p = a + b
q = Operation(and, a, b) # q = ab
r = Operation(and, a, p) # r = a(a + b)

evaluate(p, 0b000010) # true
evaluate(p, 0b000000) # false

equal(p, q) # false