Given a set of binary strings, all of length $s$, is it possible to construct a SAT instance with s literals that is satisfied only by those binary strings as assignments?


For example, consider the set $\{101, 110\}$. Can we construct a SAT instance with literals $x\_1$, $x\_2$, and $x\_3$ such that it is satisfied only by the assignments $x\_1 = 1$, $x\_2 = 0$, $x\_3 = 1$ or $x\_1 = 1$, $x\_2 = 1$, $x\_3 = 0$?


It would be even more useful if this instance is an instance of k-SAT for some k. 



Constructing Useful SAT Instances
Every such set of strings determines a collection of rows in the truth table, and so you want an expression that is logically equivalent to the disjunction of those rows. This gives a logical expression in disjunctive normal form, but every propositional assertion can be put into [conjunctive normal form](http://en.wikipedia.org/wiki/Conjunctive_normal_form), which makes it an instance of SAT.


