How many boolean functions of $F(x,y,z) = F(x',y,z') + F(x,y',z)$?

Question

How to find total number of boolean functions of the equation :

$F(x,y,z) = F(x',y,z') + F(x,y',z)$

---

Is there any procedure for this ?

Answer 1

A function with three variables is described in a truth-table with eight (2*2*2) rows:

x y z F
0 0 0 f0
0 0 1 f1
0 1 0 f2
0 1 1 f3
1 0 0 f4
1 0 1 f5
1 1 0 f6
1 1 1 f7

As any value in the output column can be either 0 or 1, disregarding the equation constraint, the total number of different Boolean functions with three input variables is 2^(2*2*2) = 2^8 = 256

The given equation translates to a set of equations (+ = or):

f0 = f5 + f2 =        f2         + f5
f1 = f4 + f3 =           f3 + f4
f2 = f7 + f0 = f0                          + f7
f3 = f6 + f1 =     f1                 + f6
f4 = f1 + f6 =     f1                 + f6
f5 = f0 + f7 = f0                          + f7
f6 = f3 + f4 =           f3 + f4
f7 = f2 + f5 =        f2         + f5

Each of the eight equations has one other equation with the same right-hand-side. This leads to:

f0 = f7
f1 = f6
f2 = f5
f3 = f4

Inserted in the set of equations:

f0 = f2 = f5 = f7
f1 = f3 = f4 = f6

There are four solutions for (f0; f1): (0; 0), (0; 1), (1; 0) and (1; 1)

Translated back - as an example - to the original truth-table for (f0=1; f1=0):

x y z F     x'y z' F1  x y' z F2  F=F1+F2
0 0 0 f0 1  1 0 1  1   0 1  0  1    1
0 0 1 f1 0  1 0 0  0   0 1  1  0    0
0 1 0 f2 1  1 1 1  1   0 0  0  1    1
0 1 1 f3 0  1 1 0  0   0 0  1  0    0
1 0 0 f4 0  0 0 1  0   1 1  0  0    0
1 0 1 f5 1  0 0 0  1   1 1  1  1    1
1 1 0 f6 0  0 1 1  0   1 0  0  0    0
1 1 1 f7 1  0 1 0  1   1 0  1  1    1

The total number of functions which fulfil the equation is four.

Two of these are trivial constant functions: always 0, or always 1

---

Alternative approach using the MiniZinc constraint solver:

 % function F is determined by 2^n = 8 function values:
array[0..7] of var bool: f;

function var bool: F(bool: x, bool: y, bool: z) = 
  %  bool variable are automatically converted (coerced) in 0 .. 1
  f[4*x+2*y+z];

constraint forall(x,y,z in [false,true]) (
  F(x, y, z) == (F(not x, y, not z) \/ F(x, not y, z))
);

MiniZinc comes up with four solutions as expected:

[false, false, false, false, false, false, false, false]
[false, true,  false, true,  true,  false, true,  false]
[true,  false, true,  false, false, true,  false, true ]
[true,  true,  true,  true,  true,  true,  true,  true ]