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

  • Thread starter nounou
  • Start date
In summary, these are the steps you need to take to prove that "P V Q" is not equivalent to any Horn Clause: 1) Prove that if a formula F is not equivalent to any Horn Clause, then F is not equivalent to any Horn Formula. 2) Check that if Q1 and Q2 denote positive literals, then (Q1 v Q2) is not equivalent to any Horn Clause.
  • #1
nounou
27
0
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?
:bugeye:
 
Last edited:
Physics news on Phys.org
  • #2
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?
 
  • #3
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.
 
  • #4
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. :biggrin:
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:
  • #5
Thank uuuuu honestrosewater :smile:
 

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

What is a Horn Clause?

A Horn clause is a logical statement that has at most one positive literal. It is of the form P1 ∧ P2 ∧ P3 ∧ ... ∧ Pn → Q, where P1, P2, P3, ..., Pn are positive literals (propositional variables or their negations) and Q is a single positive literal.

What is the difference between a Horn Clause and a non-Horn Clause?

The main difference between a Horn clause and a non-Horn clause is that a Horn clause can only have one positive literal, while a non-Horn clause can have multiple positive literals. This means that a Horn clause has a more restricted form compared to a non-Horn clause.

Why is P V Q not a Horn Clause?

P V Q is not a Horn clause because it does not follow the form of P1 ∧ P2 ∧ P3 ∧ ... ∧ Pn → Q, where P1, P2, P3, ..., Pn are positive literals. Instead, it is a disjunction (logical OR) of two propositional variables, which does not fit the definition of a Horn clause.

What is an example of a Horn Clause?

An example of a Horn clause is P ∧ Q → R, where P, Q, and R are positive literals. This means that if both P and Q are true, then R must also be true. It follows the form of a Horn clause, with one positive literal on the left side (P ∧ Q) and one positive literal on the right side (R).

What is the significance of Horn Clauses in logic?

Horn clauses are significant in logic because they have efficient algorithms for logical inference and can be used to represent logical statements in a concise way. They are also used in the field of artificial intelligence for knowledge representation and reasoning. Additionally, Horn clauses are closely related to propositional logic, making them an important concept to understand in logic and mathematics.

Back
Top