# Problem with bitwise AND/OR on binary strings

Let $W = \{s_1, s_2, \ldots, s_n\}$ be a set of $m$-length binary strings and let $\land$ and $\lor$ be the binary operators of bitwise AND and OR. A bitwise formula $\phi$ is composed of operands in $A \subseteq W$, operators in $\{(,),\land, \lor\}$, and computes a $m$-length binary string $x = \phi$. Then we say that $x$ can be expressed by $W$.

We say a set $W$ is expressive complete if for any $x \in W$, $x$ can be expressed by a bitwise formula using operands in $W \setminus \{x\}$.

Question: Given $W$, determine the minimum number $n$ of $m$-length binary strings that need to be added to $W$ to make it expressive complete.

Example 1: Let $m = 2$ and $W = \{01, 10\}$. Then then both 00 and 11 need to be added to $W$ to make it expressive complete. Thus, $n = 2$.

Example 2: Let $m = 3$ and $W = \{001, 010, 100, 011, 110, 101\}$. $W$ is already expressive complete, so $n = 0$.

A Trivial Upperbound: $2m$ is an upperbound, because for vector space $\{0,1\}^m$, $\{ 0...01, 0...010,..., 10...0\}$ is a base and $\{1...10, 1...101,...,01...1\}$ is also a base. After adding these two bases to $W$, $W$ is certainly expressive complete.

Related result (might be helpful for the question) proved: $x$ could be expressed from $A\subseteq W$ if and only if $\bigwedge_{i \in \mathsf{Zero}(x)} {t_i} = x$. Where $\mathsf{Zero}(x)$ is the set of 0 valued indicies of $x$. And $t_i$ is the $\lor$ opreated on all the binary strings in $A$ whose $i^{th}$ bit is 0.

• Can you give an example of an expressive complete set $W$ that is not trivial (i.e. does not contain all the strings of length $m$)? – Tyson Williams Aug 24 '11 at 12:37
• @Tyson: $W=\{001, 010, 100, 011, 110, 101\}$ is one. – Peng Zhang Aug 24 '11 at 12:52