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

0

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).

  • 0
    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.2012-10-08