Minimal Boolean Formulas (2011)
Minimal Boolean Formulas Posted on Wednesday, May 18, 2011. 28. That's the minimum number of AND or OR operators you need in order to write any Boolean function of five variables. Alex Healy and I computed that in April 2010. Until then, I believe no one had ever known that little fact. This post describes how we computed it and how we almost got scooped by Knuth's Volume 4A which considers the problem for AND, OR, and XOR. A Naive Brute Force Approach Any Boolean function of two variables ca