# Linearly separate a cube

I am facing the problem of the linear separability of a three dimensional cube.

Let's take the opposite vertexes of the cube as $(0, 0, 0), (1, 1, 1)$. It is possible to split it with a plane in two tetrahedron-like parts, and so define two sets, each containing lying points lying on a specific side of the plane. Let's take one of the set $t=\{(0, 1, 1), (1, 1, 1), (1, 0, 1), (1, 1, 0)\}$ and the other the obvious complement.The question is: what is the simplest form of the boolean function $P$ such that $\forall x \in t: P(x)=1$?

-
$(x \wedge y) \vee (x \wedge z) \vee (y \wedge z)$ is nice and symmetric. – mjqxxxx Oct 8 '12 at 1:37
@mjqxxxx that sounds good for my ultimate aim, which is to predict how many ways there are to linearly separate the cube. Starting from the 0-d, 1-d and 2-d case, I was including functions in which at most 0, 1, 2 or 3 arguments (between x, y, z) appeared, but I was missing exactly 8 cases, which I reckon to be a variation of your suggestion (x -> !x, etc.). Now I should figure out why exactly at space dimension 3 there is the need of this additional function. – Lorenzo Pistone Oct 8 '12 at 1:47
I'm not sure I understand your question. Are you looking for a function like $P(x,y,z)=1$ if $x+y+z\geq 3/2$ and $0$ otherwise? This effectively cuts your cube into two congruent pieces - not tetrahedra, of course, but it meets the other criteria of your question the way you've stated it. – user22805 Oct 8 '12 at 8:12
@DavidWallace Unfortunately I can express this $P$ only in terms of the boolean operators (and, or, not). – Lorenzo Pistone Oct 8 '12 at 9:16
So you're not working in ${\Bbb R}^3$ at all then? Your question really didn't make this clear. Your talk of points, planes, cubes and tetrahedra makes the question sound like a geometry problem. If x,y,z can only be true or false, then the expression that you want would be something like ( x and (y or z )) or (y and z ). Is that what you had in mind? – user22805 Oct 8 '12 at 17:38

Any subset of the collection of triples (a,b,c) with a,b,c all in {0,1} can easily be described using and, or, not: Make the corresponding truth table, and for each row write that row as a conjunction of "literals", i.e. v or (not v) for a variable v.

For example if the vars are x,y,z in that order, one row of a truth table would have x true, y false, and z true. Then this row corresponds to the conjunction

x and (not y) and z.

Now just put the rows that appear each in this format, put parentheses around each row result, and put "or" between them in case there are more than one row giving true. This is a standard method to get a boolean from the initial collection of triples.

I think you're asking whether one can realize any such collection of triples by means of a plane which cuts the cube without going through any vertices, and using one side of that plane for the "true" triples.

But this can't give all possible subsets, since the set {(0,0,0), (1,1,1)} would be two diagonally opposite points on the cube, and any plane cutting the cube with these two on one side will definitely have more triples on that same side. The boolean for this is of course (not x and not y and not z) or (x and y and z).

-
"But this can't give all possible subsets". Can you explain why this start happening with 3 dimensions? For example, if you redo the calculation on a 2-d space, you don't have to consider more than 2 coordinates in the $P$ function (counting also the number of times that a variable appear) to get all the possible "splits". I was led to think that the necessary number of coordinates in $P$ was equal to the dimension of the space, but indeed this way I miss exactly 8 cases in the 3 dimensional case (and the question shows one of them, the others correspond to the other vertexes of the cube). – Lorenzo Pistone Oct 8 '12 at 16:09
For 2 dimensions, there are 4 rows in a truth table using two variables, for a total of 2^4=16 subsets of the set of 4 vertices of the square. It's easy to get the singletons e.g the set {(0,1)} by cutting the square with a line which "cuts of that one corner" (0,1). And using complements we get the three element subsets. We can get the empty subset or the complete set of all eight using a line that doesn't cut the square at all. But I can't see how to get a "diagonal doubleton" like {(0,0),(1,1)} by cutting the square with one line. So I think you miss some combinations even in the 2d case. – coffeemath Oct 8 '12 at 22:57