Is there a Horn formula which is equivalent to $(p \lor q)$? Is there a Horn formula which is equivalent to $(p \lor q)$?
Hi I have to answer the following question:
Given any formula $\phi$, is it possible to find a Horn formula equivalent to $\phi$?
I know that a formula is Horn's if in its conjunctive normal form all clauses are Horn's.
But in this case $\phi$ is already in it's conjunctive normal form, but $\phi$ has 2 positive literal.
So, this would be a example that proves that what I have to answer is not possible, right?
Thanks in advance
UPDATE
I just thought of something; let me know if I'm right.
So a Horn Clause has the form:
a) $(p_1 ∧...∧ p_n) → q$
b) $ \lnot p_1 \lor \lnot p_2, ... , \lnot p_n $
Since $(p \lor q)$ is not equivalent to $(p \land q) → s$, and
$(p \lor q)$ is not equivalent to $(\lnot p \lor \lnot q)$
There $(p \lor q)$ can't be equivalent to any Horn formula.
Is this reasoning right?
 A: Any formula $\varphi$ which is equivalent to a Horn formula has the following property: if $v_1$ and $v_2$ are two valuations that make $\varphi$ true, then the valuation $v_1\land v_2$ also makes $\varphi$ true.
The formula $\varphi=(p\lor q)$ does not have this property, since it is true under the valuations $(T,F)$ and $(F,T)$ but false under the valuation $(T\land F,F\land T)=(F,F)$. Therefore $(p\lor q)$ is not equivalent to a Horn formula.
(More generally, if a first-order sentence is equivalent to a Horn sentence, then it has the property: if it's true in two models $\mathfrak A$ and $\mathfrak B$, then it's true in their direct product $\mathfrak A\times\mathfrak B$. However, not every first-order sentence with this property is equivalent to a Horn sentence.)
A: The problem with this reasoning is that the wording "its conjunctive normal form" seems to imply that there is a unique CNF representation of every boolean function. But that is not the case. For example
$$ (a \lor \neg b) \land (\neg a \lor b) \land (a \lor b) $$
$$ (a) \land (b)$$
are both in CNF and are logically equivalent -- but one is Horn and the other is not.

So you need something better to show that $p\lor q$ is not equivalent to any Horn CNF (which indeed it isn't). The best I can think of is to enumerate all the possible Horn clauses that mention only $p$ and $q$ -- there are not that many -- and notice that each of them is either a tautology (and thus useless) or would reject a truth assignment that $\lor$ needs to accept.
A: A useful concept here is called minterm (maxterm) canonical form for DNF:

In Boolean algebra, any Boolean function can be put into the canonical disjunctive normal form (CDNF) or minterm canonical form and its dual canonical conjunctive normal form (CCNF) or maxterm canonical form.... For a boolean function of $n$ variables $x_1, \dots, x_n$, a sum term in which each of the $n$ variables appears once (either in its complemented or uncomplemented form) is called a maxterm.

So the CDNF/CCNF for any propositional formula is unique and each of its disjuncts/conjuncts contains each variable occurring in the formula exactly once. For your case $(p \lor q)$ here, its CCNF is easy to be expressed as $(p \lor q)$. As you see here we still have 2 positive literals in the CCNF and since it's unique, therefore it cannot be a Horn clause...
