Proving the Non-Equivalence of 'P V Q' to Any Horn Formula

[nounou]

How can we prove that "P V Q" is not a Horn Clause

Does anyone have an idea how to prove that "P V Q" is not equivalent to any horn formula. All I seem to find is people saying that it is a very clear counter-example, but I need more of a formal method of proof.
Any ideas?

 

[honestrosewater]

What do "P" and "Q" denote? Your title and post say different things- do you want to prove that "P v Q" is not a Horn Clause or that "P v Q" is not equivalent to any Horn Fornmula?

 

[nounou]

I woud like to show that "P V Q" is not equivalent to any horn formula, where P and Q are primitive propositions. The point is that all sources I read are saying that this is the most obvious example showing that not everything can be represented as a horn clause (and therefore not equivalent to any horn formula), but I never found any formal explanation. I just need the logic behind why "P V Q" is not equivalent to any horn formula.
Thanx.

 

[honestrosewater]

Well, I don't know much about Horn anything- I just looked up some definitions yesterday. But you have two things to prove.
1) If a formula F is not equivalent to any Horn Clause, then F is not equivalent to any Horn Formula.
2) If Q₁ and Q₂ denote positive literals, then (Q₁ v Q₂) is not equivalent to any Horn Clause.
You already stated (1) in your post- do you know a proof of it? Notice that a Horn Formula (HF) is just a conjunction of one or more Horn Clauses (HC). So the following rules will give you every HF:
3) If F is a HC, then F is a HF.
4) If F and G are HC, then (F & G) is a HF.
Can you use this to prove (1)?
For (2), notice that every HC is equivalent to a formula of one the following forms, where P denotes a positive literal:
5) ~(P₁ & P₂ & ... & P_n). (when HC has no positive literal)
6) (P₁ & P₂ & ... & P_n) -> P. (when HC has one positive literal)
Is (Q₁ v Q₂) equivalent to a formula of one of those forms?
There may be a shorter way to do this, and it uses some theorems I won't prove, (Edit: unless you ask me to- the first theorem is very handy so you may want a proof of it) but here goes. Since (Q₁ v Q₂) is contingent, any formula equivalent to (Q₁ v Q₂) must contain Q₁ and Q₂ as subformulas.
(Q₁ v Q₂) is not equivalent to ~(Q₁ & Q₂) (form (5)), and adding more P_ns won't change this. Just construct their truth tables to see the first part. To see that adding more P_ns won't help, just look at the truth tables you've constructed. Notice that a disjunction has only one F entry in its column, in the row where all the disjuncts are F- no matter how many disjuncts there are. Similarly, a conjunction has only one T entry, in the row where all the conjuncts are T. So the negation of a conjunction has only one F entry, in the row where all the conjuncts are T. So no matter how many P_ns you have, their disjunction and the negation of their conjunction will have only one F entry- but never in the same row. So they aren't equivalent. I know you like "formal" proofs, but that would take more work- so I'll leave it to you.
For form (6), you have three cases to check.
7) (Q₁ v Q₂) <-> (Q₁ -> Q₂)
8) (Q₁ v Q₂) <-> (Q₂ -> Q₁)
9) (Q₁ v Q₂) <-> ((Q₁ & Q₂) -> P)
You'll see that these are all false, and you already know that adding more P_ns as conjuncts won't change it.
Since (Q₁ v Q₂) is not equivalent to any formula of form (5) or (6), (Q₁ v Q₂) is not equivalent to any HC.

 

[nounou]

Thank uuuuu honestrosewater