An algorithm for producing median formulas for Boolean functions

Proceedings of the Reed–Muller 2011 Workshop, Tampere International Center for Signal Processing (TICSP), (2011), 49-54


We review various normal form representations of Boolean functions and outline a comparative study between them, which shows that the median normal form system provides representations that are more efficient than the classical DNF, CNF and Reed–Muller (polynomial) normal form representations. We present an algorithm for producing median normal form representations of Boolean functions.