Is it possible to translate a boolean formula B into an equivalent conjunction of Horn clauses? The Wikipedia article about HornSAT seems to imply that it is, but I have not been able to chase down any reference. Note that I do not mean in polynomial time, but rather at all.
Translating SAT to HornSAT
reference request;lo.logic;sat
No.  Conjunctions of Horn clauses admit least Herbrand models, which disjunctions of positive literals don't.  Cf. Lloyd, 1987, Foundations of Logic Programming.Least Herbrand models have the property that they are in the intersections of all satisfiers.  The Herbrand models for $(a \lor b)$ are $\{\{a\}, \{b\}, \{a,b\}\}$, which doesn't contain its intersection, so as arnab says, $(a \lor b)$ is an example of a formula which can't be expressed as a conjunction of Horn clauses.Incorrect answer overwritten