1
$\begingroup$

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?

  • 0
    @Brainlag: (Sorry, previous comment timed out) Try writing out the truth table for the three functions. Alternatively, think of a xor b as not (a == b); then a xor (not b) <-> not (a == not b) <-> not (a != b) <-> (a == b) <-> a xnor b; etc.2011-01-19

1 Answers 1

1

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.