Multilinear Representation of Boolean Functions

A boolean function is a any function $f: \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2$ . Volume 4 of Knuth's Art of Computer Programming contains a proof that any boolean function is equivalent to a multilinear expression using only products and sums in $\mathbb{Z}_2$ . The gist of the proof is the following recursion:

f(x_1, x_2, \ldots, x_n) = f(0, x_2, \ldots, x_n) + x_1 f(0, x_2, \ldots, x_n) + x_1 f(1, x_2, \ldots, x_n)

For example, a function with binary truth table given by $1011010100000111$ has multilinear representation:

f(a, b, c, d) = 1+a+ab+abc+abd+acd+ad+b+bcd+cd+d.

In The Art of Computer Programming, Knuth's equation recurses on the last variable, $x_n$ , but here I did it on the first variable. This will allow a simpler treatment of the truth table as shown below.

Now, assume we are give the truth table of a boolean function as a binary string, and would like to calculate its multilinear representation. To do so, we can recursively apply the above equation. That is, we first find a multilinear representation of $f(0, x_2, \ldots, x_n)$ and then that of $f(0, x_2, \ldots, x_n) + f(1, x_2, \ldots, x_n)$ and then simply applying the formula above. Note that the truth table for $f(0, x_2, \ldots, x_n)$ is simply the left half of the binary string for the truth table of $f(x_1, x_2, \ldots, x_n)$ and the one for $f(1, x_2, \ldots, x_n)$ is the right half. These two halves can be easily extracted using binary shift and mask operations.

This leads to the code below. Note that once the multilinear form is calculated using the above method, it needs to be expanded and simplified to give us the final form. That's what the flatten and expand methods do in the code below.

__author__ = "Sahand Saba"

from itertools import product
from random import randint


def _multilinear(truth, n, N, k):
    if n == 0:
        return Constant(truth)

    L = truth >> k
    R = truth & (2 ** k - 1)
    g = _multilinear(L, n - 1, N, k // 2)
    h = _multilinear(L ^ R, n - 1, N, k // 2)
    if h == 0:
        return g
    if h == 1:
        if g == 0:
            return Variable(N - n)
        else:
            return Xor(Variable(N - n), g)
    else:
        if g == 0:
            return Conjunction(Variable(N - n), h)
        else:
            return Xor(g, Conjunction(Variable(N - n), h))


def multilinear(truth, n):
    """
    Treating input 'truth' as a 2^n bit number representing the truth table of
    a boolean function of n variables, calculate the multilinear representation
    of the boolean function and return it.
    """
    return _multilinear(truth, n, n, 2 ** (n - 1))


class Expression(object):
    def flatten(self):
        pass

    def expand(self):
        return self


class Constant(Expression):
    value = 0

    def __init__(self, val):
        self.value = val

    def __eq__(self, v):
        return self.value == v

    def __str__(self):
        return str(self.value)

    def evaluate(self, assignment):
        return self.value


class Variable(Expression):
    index = 0

    def __init__(self, index):
        self.index = index

    def __str__(self):
        return chr(ord('a') + self.index)

    def evaluate(self, assignment):
        return assignment[self.index]


class AssociativeOperator(Expression):
    operands = []

    def flatten(self):
        for o in self.operands:
            o.flatten()

    def sort(self):
        self.operands.sort(key=lambda x: str(x))


class Conjunction(AssociativeOperator):
    def __init__(self, *args):
        self.operands = args

    def __str__(self):
        return ''.join('(' + str(a) + ')' if type(a) is Xor else str(a)
                       for a in self.operands)

    def evaluate(self, assignment):
        return reduce(lambda s, a: a.evaluate(assignment) * s,
                      self.operands, 1)

    def flatten(self):
        operands = []
        for o in self.operands:
            o.flatten()
            if type(o) is Conjunction:
                operands.extend(o.operands)
            elif type(o) is Constant and o.value == 1:
                continue
            elif type(o) is Constant and o.value == 0:
                operands = [Constant(0)]
                break
            else:
                operands.append(o)
        self.operands = operands

    def expand(self):
        self.flatten()
        p = [o.expand().operands if type(o) is Xor else [o.expand()]
             for o in self.operands]
        operands = []
        for t in product(*p):
            operands.append(Conjunction(*t))
        m = Xor(*operands)
        m.flatten()
        return m


class Xor(AssociativeOperator):
    def __init__(self, *args):
        self.operands = args

    def __str__(self):
        return '+'.join(str(a) for a in self.operands)

    def evaluate(self, assignment):
        return reduce(lambda s, a: (a.evaluate(assignment) + s) % 2,
                      self.operands, 0)

    def flatten(self):
        super(Xor, self).flatten()
        operands = []
        for o in self.operands:
            if type(o) is Xor:
                operands.extend(o.operands)
            else:
                operands.append(o)
        self.operands = operands

    def expand(self):
        operands = [o.expand() for o in self.operands]
        m = Xor(*operands)
        m.flatten()
        return m


def test(truth, n):
    m = multilinear(truth, n)
    m = m.expand()
    m.sort()
    s = ""
    for assignment in product(*[[0, 1] for i in xrange(n)]):
        s += str(m.evaluate(assignment))

    check = int(s, 2) == truth
    return s, m, check


if __name__ == '__main__':
    N = 100  # Test with this many test cases
    n = 4  # Number of variables for the test boolean functions
    table_row_format = "{0: <20}\t{1: <32}\t{2: <20}\t{3: <6}"
    print table_row_format.format("Truth table", "Multilinear expression",
                                  "Evaluated truth table", "Check")
    for __ in xrange(N):
        truth = randint(0, 2 ** (2 ** n))
        s, m, check = test(truth, n)
        print table_row_format.format(bin(truth), m, s, str(check))
        if not check:
            print "Mismath: test failed with truth table " + str(truth)

Math ∪ Code

by Sahand Saba

Multilinear Representation of Boolean Functions

Comments