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?

  • $\begingroup$ This looks similar to this question: math.stackexchange.com/questions/17852/… $\endgroup$ – PrimeNumber Jan 19 '11 at 1:58
  • $\begingroup$ @Brainlag: Something is wrong with your list of functions; because you lack the two trivial functions in your list: $f(a,b)=0$ and $f(a,b)=1$ But you are still correct that there are $2^{2^n}$ boolean functions; your (10), (15), and (16) all represent the same function. $\endgroup$ – Chas Brown Jan 19 '11 at 5:33
  • $\begingroup$ @PEV : Yes but i know how many functions are possible. The Question is how many functions are separable for n (not only n=2) $\endgroup$ – user6006 Jan 19 '11 at 12:24
  • $\begingroup$ @Chas Brown I don't get it. I don't see they are the same. $\endgroup$ – user6006 Jan 19 '11 at 12:24
  • $\begingroup$ all three have the truth table: $\endgroup$ – Chas Brown Jan 19 '11 at 17:17

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 and NOT 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy