The aim is to find a formula for the question.
For $n=2$ i get $2^{2^n}=16$ possible functions.
This is the solution for a boolean function with 2 attributes:
01) a -> separable
02) b -> separable
03) not a -> separable
04) not b -> separable
05) a and b -> separable
06) a or b -> separable
07) a xor b -> not separable
08) a nand b -> separable
09) a nor b -> separable
10) a xnor b -> not separable
11) (not a) and b -> separable
12) a and (not b) -> separable
13) (not a) or b -> separable
14) a or (not b) -> separable
15) (not a) xor b -> not separable
16) a xor (not b) -> not separable
But what is the formular for n?
Best Answer
It may be easier to think in terms of linearly separable subsets of $\{0,1\}^n$ (that is, those that are cut off from the cube by a hyperplane). For $n=2$ we are looking at subsets of the vertex set of a square: the only two that are not linearly separable are the diagonals. This makes $2^{2^2}-2=14$ separable functions: all except
XOR
andNOT XOR
.There is no formula for general $n$, in fact only a handful of counts are known. This is the OEIS sequence A000609, labeled "hard". By the way, the Wikipedia page on linear separability references OEIS.