# P V Q is not a Horn Clause

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? Last edited:

honestrosewater
Gold Member
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?

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
Gold Member
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 Q1 and Q2 denote positive literals, then (Q1 v Q2) 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) ~(P1 & P2 & ... & Pn). (when HC has no positive literal)
6) (P1 & P2 & ... & Pn) -> P. (when HC has one positive literal)
Is (Q1 v Q2) 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 (Q1 v Q2) is contingent, any formula equivalent to (Q1 v Q2) must contain Q1 and Q2 as subformulas.
(Q1 v Q2) is not equivalent to ~(Q1 & Q2) (form (5)), and adding more Pns won't change this. Just construct their truth tables to see the first part. To see that adding more Pns 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 Pns 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) (Q1 v Q2) <-> (Q1 -> Q2)
8) (Q1 v Q2) <-> (Q2 -> Q1)
9) (Q1 v Q2) <-> ((Q1 & Q2) -> P)
You'll see that these are all false, and you already know that adding more Pns as conjuncts won't change it.
Since (Q1 v Q2) is not equivalent to any formula of form (5) or (6), (Q1 v Q2) is not equivalent to any HC.

Last edited:
Thank uuuuu honestrosewater :rofl: