0
$\begingroup$

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$?

  • 0
    $(x \wedge y) \vee (x \wedge z) \vee (y \wedge z)$ is nice and symmetric.2012-10-08
  • 0
    @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.2012-10-08
  • 0
    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.2012-10-08
  • 0
    @DavidWallace Unfortunately I can express this $P$ only in terms of the boolean operators (and, or, not).2012-10-08
  • 0
    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?2012-10-08

1 Answers 1