PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
Let the number of variables be n. We will calculate the amount of functions in different possible intersection of our clones. There are a total of 2^2^n different n-ary Boolean functions. This is derived from the fact that there are 2^n different binary sequences of length n. We can set a certain function to have value 0 or 1 for each sequence. So we have 2^2^n possibilities to do so.
Now considering 0-preserving functions we have to set each such function a value of 0 for the sequence (0, …, 0). So we are left with one less sequence and there 2^(2^n-1) such functions. The same goes for 1-preserving function.
For the self-dual function we can see that setting the value f(a1, …, an) = b, forces us to set the value f(!a1, …, !an) = !b. So we have only half of the choices. That gives the amount of such functions to be 2^2^(n-1).
It can be shown that the affine function are those that can be represented in a form: f(x1, …, xn) = a0 + a1x1 + … + anxn, where ai = {0, 1}. We can choose each ai to be either 0 or 1. We have 2^(n+1) possibilities to do so. So there are 2^(n+1) affine function.
Using the same logic we can derive the cardinalities for any intersection of those clones. We can use the calculated cardinalities to count the number of functions in any set formed by those clones.
Now let’s consider the following sets: function belonging to none of those clones, functions that belong to Z only, that belong to P only, that belong to D only, that belong to A only, that belong to both and Z and P only, …, that belong to all of Z and P and D and A. There will be a total of 16 such sets. Those sets will be disjoint and their union will be the set of all Boolean functions. The cardinalities of those sets can be calculated using inclusion-exclusion principle using the cardinalities calculated before.
So now we parse the given expression and calculate of what sets it is formed and just sum the cardinalities of those sets. This can be easily done using the bitmask (as there are just 16 disjoint sets) and bitwise logical operations.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here