Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

i think you can for , especially since you know that spanning is the hard part. it might be more challenging to prove the more general result (an arbitrary idempotent semiring).

Re: a "basis" in {0,1}^n with operations induced from the boolean algebra {0,1}

OK. It's actually very easy when you know what you want to prove. Unless I'm mistaken of course.

Let . Suppose X spans the space. Then there must be a combination of vectors in X that is equal to Suppose Then since every vector in X has 1 on some coordinate different from . No combination of such vectors can be equal to . Therefore for any must be in X. If we suppose that X is independent, there can be no other vectors in it.