Notes

Chapter 10: Processes of Perception and Analysis

Section 11: Traditional Mathematics and Mathematical Formulas


[Boolean] formula sizes

There are a total of 22n

Copy to clipboard.
\!\(\*SuperscriptBox[\(2\),\(\!\(\*SuperscriptBox[\(2\),\(n\)]\)\)]\) possible Boolean functions of n variables. The maximum number of terms needed to represent any of these functions in DNF is 2n - 1
Copy to clipboard.
\!\(\*SuperscriptBox[\(2\),\(n-1\)]\)
. The actual numbers of functions which require 0, 1, 2, ... terms is for n = 2
Copy to clipboard.
n = 2
: {1, 9, 6}
Copy to clipboard.
{1, 9, 6}
; for n = 3
Copy to clipboard.
n = 3
: {1, 27, 130, 88, 10}
Copy to clipboard.
{1, 27, 130, 88, 10}
, and for n = 4
Copy to clipboard.
n = 4
: {1, 81, 1804, 13472, 28904, 17032, 3704, 512, 26}
Copy to clipboard.
{1, 81, 1804, 13472, 28904, 17032, 3704, 512, 26}
. The maximal length turns out always to be realized for the simple parity function Xor
Copy to clipboard.
Xor
, as well as its negation. The reason for this is essentially that these functions are the ones that make the coloring of the Boolean hypercube maximally fragmented. (Other functions with maximal length are never additive, at least for n 4
Copy to clipboard.
n ≤ 4
.)



Image Source Notebooks:

From Stephen Wolfram: A New Kind of Science [citation]