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

i think you can for $\displaystyle \{0,1\}^n$, 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 $\displaystyle X\subseteq \{0,1\}^n$. Suppose X spans the space. Then there must be a combination of vectors in X that is equal to $\displaystyle e_i.$ Suppose $\displaystyle e_i\not\in X.$ Then since $\displaystyle X\neq\{0\},$ every vector in X has 1 on some coordinate different from $\displaystyle i$. No combination of such vectors can be equal to $\displaystyle e_i$. Therefore for any $\displaystyle i=1,2,...,n,\, e_i$ must be in X. If we suppose that X is independent, there can be no other vectors in it.