Is there a Horn formula which is equivalent to ( p &#x2228;<!-- ∨ --> q ) ? Is there a H

Ayanna Trujillo

Ayanna Trujillo

Answered question

2022-06-09

Is there a Horn formula which is equivalent to ( p q )?
Is there a Horn formula which is equivalent to ( p q )?
Given any formula ϕ, is it possible to find a Horn formula equivalent to ϕ?
I know that a formula is Horn's if in its conjunctive normal form all clauses are Horn's.
But in this case ϕ is already in it's conjunctive normal form, but ϕ 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) ¬ p 1 ¬ p 2 , . . . , ¬ p n
Since ( p q ) is not equivalent to ( p q ) s, and ( p q ) is not equivalent to ( ¬ p ¬ q ).
There ( p q ) can't be equivalent to any Horn formula.

Answer & Explanation

Marlee Guerra

Marlee Guerra

Beginner2022-06-10Added 25 answers

Step 1
Any formula φ which is equivalent to a Horn formula has the following property: if v 1 and v 2 are two valuations that make φ true, then the valuation v 1 v 2 also makes φ true.
Step 2
The formula φ = ( p q ) does not have this property, since it is true under the valuations (T, F) and (F, T) but false under the valuation ( T F , F T ) = ( F , F ). Therefore ( p 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 A and B , then it's true in their direct product A × B . However, not every first-order sentence with this property is equivalent to a Horn sentence.)
Arraryeldergox2

Arraryeldergox2

Beginner2022-06-11Added 10 answers

Step 1
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 ¬ b ) ( ¬ a b ) ( a b ) are both in CNF and are logically equivalent - but one is Horn and the other is not.
Step 2
So you need something better to show that p 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 needs to accept.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?