4
$\begingroup$

Let $H$ be a set of non-positive Horn clauses. Show that $H$ it is satisfying.

Is this true if there are positive clauses in $H$?

I'm finding hard to answer this questio, I have think about it for a long time, but can't find a good example/aproach

Can somebody help me? I'm just starting to see Horn clauses

$\endgroup$
1
  • $\begingroup$ Maybe: "H is satisfiable"... $\endgroup$ Oct 25, 2021 at 10:03

2 Answers 2

2
$\begingroup$

If none of the Horn clauses is positive, then a satisfying valuation is one which maps all propositional symbols to $0$. If there is even a single positive clause, then there are unsatisfiable sets of Horn clauses, such as: $$p \land (p\to \neg p)$$

$\endgroup$
1
$\begingroup$

Yes there're positive Horn clauses according to reference here:

A Horn clause is a clause (a disjunction of literals) with at most one positive, i.e. unnegated, literal.

A Horn clause with exactly one positive literal is a definite clause or a strict Horn clause; a definite clause with no negative literals is a unit clause, and a unit clause without variables is a fact; A Horn clause without a positive literal is a goal clause.

So the $H$ in your first line question is a goal clause.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .