Monotone Modulo-m Functions

Using Mathematica to find the number of Monotone Modulo-m Functions for v number of variables

Rodrigo A. Obando

Columbus State University

Monotone Boolean Functions

Every set of Boolean Functions of v variables has a subset
of functions called Monotone Boolean Functions of v variables. A Boolean function m belongs to this subset if and only if

a  ≤  b  ->  m[a] ≤ m[b]

In 1897, Richard Dedekind asked the question: How many Monotone Boolean Functions of a given number of variables are there?

In reality he wanted to determine the number of elements in a free distributive lattice FD(v) on v generators. Both questions are equivalent to each other.

He computed the number for boolean functions of 0, 1, 2, 3 and 4 variables. The sequence of these numbers is known as Dedekind numbers. He found the sequence: 2, 3, 6, 20, 168.

The sequence has been reportedly found up to 8 variables:

DedekindNumbers =  {2, 3, 6, 20, 168, 7581, 7828354, 
          2414682040998, 56130437228687557907788}

There is not closed form for computing this sequence.

Example: Boolean functions of 2 variables

nVars = 2;
MatrixForm[
      Map[{IntegerDigits[#, 2, (2^nVars)], #} &, 
        Table[n, {n, 0, (2^((2^nVars))) - 1}]]]

Example: Monotone Boolean Functions of 2 variables

nVars = 2;
MBFEquationsTable[nVars]

Finding The Monotone Boolean Functions

There are various ways to find the number of Monotone Boolean Functions.  In general, in order to count them, we need to enumerate them. A way to do this is by finding all `Closed from Above Subsets' of (E^v), where (E^v) is the hypercube of v dimensions. This is a combinatorial problem.

It can be shown that every Monotone Boolean Function of v variables is made up by juxtaposing two Monotone Boolean Functions of v-1 variables.

(Subscript[m, i])[v] = (Subscript[m, j])[v - 1] || (Subscript[m, k])[v - 1]
(Subscript[m, j])[v - 1] ≤ (Subscript[m, k])[v - 1]

We could recursively find all Monotone Boolean Functions of v
variables by first finding all Monotone Boolean Functions of v-1 variables and using them as long as they comply with the
requirements stated above. The disadvantage is that we need to test every pair to determine if they are comparable and hence it becomes not as efficient. We could also generate all Boolean Functions for v variables and test each for monotonicity but this is extremely inefficient.

The distribution of monotone boolean functions made by joining other monotone boolean functions, although confined to the upper diagonal, becomes sparse a we increase the number of variables.

nVars = 5;
FractalGraphicsMBF[nVars] // Show

Free Distributive Lattices

The original problem stated by Dedekind created Free Distributive Lattices that in turn contain all Monotone Boolean Functions and these are represented by the nodes in the lattice. The number of Monotone Boolean Functions is equal to the cardinality of the lattices.
Given a v-dimensional hypercube we are able to find the set of
Monotone Boolean Functions but we need to start from scratch for every hypercube. There have been shortcuts created to accelerate the process but it is still very time consuming.  The number of Monotone Boolean Functions of 8 variables was computed using a Cray-1 Supercomputer for 200 hours back in 1991.

We discovered that we could find the (Subscript[FDL, v]) using (Subscript[FDL, v - 1]). This process directly uses the Monotone Boolean Functions of v-1 variables to find all the Monotone Boolean Functions of v variables without having to test as stated before.

Partially Ordered Product

There exist a Partially Ordered Lattice Product that recursively computes the Free Distributive Lattices created by the process outlined above, such that

(Subscript[FDL, v]) = (Subscript[FDL, v - 1]) (Subscript[FDL, v - 1]) = 
          ((Subscript[FDL, v - 1])^2)

This was implemented in Mathematica.

Sequence of the first 5 Free Distributive Lattices

GraphicsArray[
        Map[ShowGraph[
              RankedEmbedding[
                FromAdjacencyLists[FreeDistributiveLattice[#, 
                      2][[1]]], {1}], VertexStyle -> Disk[Small], 
              VertexColor -> Blue, EdgeColor -> Green, 
              EdgeStyle -> Thin, 
              PlotLabel -> ToString[#] <> " generators.", 
              DisplayFunction -> Identity] &, Table[n, {n, 0, 4}]], 
        PlotLabel -> "Modulo-2 FDLs"] // Show

Monotone Modulo-m Functions

We generalize this process to more than 2-value variables (Boolean) and we can generate the Free Distributive Lattices that contain the Monotone Modulo-m Functions.

If we apply the Partially Ordered Lattice m-th Product to an m-element chain C v number of times, the resulting lattice is the Monotone Modulo-m Function lattice for v variables.

Examples of FDL's for Monotone Modulo-m Functions

GraphicsArray[
        Map[ShowGraph[
              RankedEmbedding[
                FromAdjacencyLists[FreeDistributiveLattice[#, 
                      3][[1]]], {1}], VertexStyle -> Disk[Small], 
              VertexColor -> Blue, EdgeColor -> Green, 
              EdgeStyle -> Thin, 
              PlotLabel -> ToString[#] <> " generators.", 
              DisplayFunction -> Identity] &, Table[n, {n, 0, 2}]], 
        PlotLabel -> "Modulo-3 FDLs"] // Show

GraphicsArray[
        Map[ShowGraph[
              RankedEmbedding[
                FromAdjacencyLists[FreeDistributiveLattice[#, 
                      4][[1]]], {1}], VertexStyle -> Disk[Small], 
              VertexColor -> Blue, EdgeColor -> Green, 
              EdgeStyle -> Thin, 
              PlotLabel -> ToString[#] <> " generators.", 
              DisplayFunction -> Identity] &, Table[n, {n, 0, 1}]], 
        PlotLabel -> "Modulo-4 FDLs"] // Show

GraphicsArray[
        Map[ShowGraph[
              RankedEmbedding[
                FromAdjacencyLists[FreeDistributiveLattice[#, 
                      5][[1]]], {1}], VertexStyle -> Disk[Small], 
              VertexColor -> Blue, EdgeColor -> Green, 
              EdgeStyle -> Thin, 
              PlotLabel -> ToString[#] <> " generators.", 
              DisplayFunction -> Identity] &, Table[n, {n, 0, 1}]], 
        PlotLabel -> "Modulo-5 FDLs"] // Show

Conclusion

The facilities of Mathematica were instrumental in implementing the Partially Ordered Lattice Product mentioned above. The fact that we could generate functions and compiling them on the fly served in the acceleration to generate the lattices. As it stands, the algorithm was implemented so that we simply pass the number of variables v and the modulo m and it generates the proper lattice. The new addition to the Wolfram family of products Workbench 1.0 helped very much in the development and testing of the final algorithm.