computer science

Horn-satisfiability

Horn-satisfiability is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Horn-satisfiability rather than just read about it. In short: In formal logic, Horn-satisfiability, or HORNSAT, is the problem of deciding whether a given conjunction of propositional Horn clauses is satisfiable or not. Horn-satisfiability and Horn clauses are named after Alfred Horn.

Key takeaways

Horn-satisfiability belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Horn-satisfiability to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Horn-satisfiability from memory before moving on to harder problems.

Reference excerpt

In formal logic, Horn-satisfiability, or HORNSAT, is the problem of deciding whether a given conjunction of propositional Horn clauses is satisfiable or not. Horn-satisfiability and Horn clauses are named after Alfred Horn. A Horn clause is a clause with at most one positive literal, called the head of the clause, and any number of negative literals, forming the body of the clause. A Horn formula is a propositional formula formed by conjunction of Horn clauses. Horn satisfiability is actually one of the "hardest" or "most expressive" problems which is known to be computable in polynomial time, in the sense that it is a P-complete problem. The extension of the problem for quantified Horn formulae can be also solved in polynomial time. The Horn satisfiability problem can also be asked for propositional many-valued logics. The algorithms are not usually linear, but some are polynomial; see Hähnle (2001 or 2003) for a survey.

Algorithm The problem of Horn satisfiability is solvable in linear time. A polynomial-time algorithm for Horn satisfiability is recursive:

A first termination condition is a formula in which all the clauses currently existing contain negative literals. In this case, all the variables currently in the clauses can be set to false. A second termination condition is an empty clause. In this case, the formula has no solutions. In the other cases, the formula contains a positive unit clause l {\displaystyle l} , so we do a unit propagation: the literal l {\displaystyle l} is set to true, all the clauses containing l {\displaystyle l} are removed, and all clauses containing ¬ l {\displaystyle \neg l} have this literal removed. The result is a new Horn formula, so we reiterate. This algorithm also allows determining a truth assignment of satisfiable Horn formulae: all variables contained in a unit clause are set to the value satisfying that unit clause; all other literals are set to false. The resulting assignment is the minimal model of the Horn formula, that is, the assignment having a minimal set of variables assigned to true, where comparison is made using set containment. Using a linear algorithm for unit propagation, the algorithm is quadratic in the size of the formula. However, it's possible to re-order the order of execution of this algorithm to obtain a linear-time algorithm.

Examples

Trivial case In the Horn formula

(¬a ∨ ¬b ∨ c) ∧ (¬b ∨ ¬c ∨ d) ∧ (¬f ∨ ¬a ∨ b) ∧ (¬e ∨ ¬c ∨ a) ∧ (¬e ∨ f) ∧ (¬d ∨ e) ∧ (¬b ∨ ¬c), each clause has a negated literal. Therefore, setting each variable to false satisfies all clauses, hence it is a solution.

Solvable case In the Horn formula

(¬a ∨ ¬b ∨ c) ∧ (¬b ∨ ¬c ∨ f) ∧ (¬f ∨ b) ∧ (¬e ∨ ¬c ∨ a) ∧ (f) ∧ (¬d ∨ e) ∧ (¬b ∨ ¬c), one clause forces f to be true. Setting f to true and simplifying gives

(¬a ∨ ¬b ∨ c) ∧ (b) ∧ (¬e ∨ ¬c ∨ a) ∧ (¬d ∨ e) ∧ (¬b ∨ ¬c). Now b must be true. Simplification gives

(¬a ∨ c) ∧ (¬e ∨ ¬c ∨ a) ∧ (¬d ∨ e) ∧ (¬c). Now it is a trivial case, so the remaining variables can all be set to false. Thus, a satisfying assignment is

a = false, b = true, c = false, d = false, e = false, f = true.

Unsolvable case In the Horn formula

(¬a ∨ ¬b ∨ c) ∧ (¬b ∨ ¬c ∨ f) ∧ (¬f ∨ b) ∧ (¬e ∨ ¬c ∨ a) ∧ (f) ∧ (¬d ∨ e) ∧ (¬b), one clause forces f to be true. Subsequent simplification gives

(¬a ∨ ¬b ∨ c) ∧ (b) ∧ (¬e ∨ ¬c ∨ a) ∧ (¬d ∨ e) ∧ (¬b). Now b has to be true. Simplification gives

(¬a ∨ c) ∧ (¬e ∨ ¬c ∨ a) ∧ (¬d ∨ e) ∧ (). We obtained an empty clause, hence the formula is unsatisfiable.

Generalization A generalization of the class of Horn formulae is that of renamable-Horn formulae, which is the set of formulae that can be placed in Horn form by replacing some variables with their respective negation. Checking the existence of such a replacement can be done in linear time; therefore, the satisfiability of such formulae is in P as it can be solved by first performing this replacement and then checking the satisfiability of the resulting Horn formula. Horn satisfiability and renamable Horn satisfiability provide one of two important subclasses of satisfiability that are solvable in polynomial time; the other such subclass is 2-satisfiability.

Dual-Horn SAT A dual variant of Horn SAT is Dual-Horn SAT, in which each clause has at most one negative literal. Negating all variables transforms an instance of Dual-Horn SAT into Horn SAT. The problem is also in P by the same transformation: any satisfying assignment to this Horn formula is the negation of a satisfying assignment to the original Dual-Horn formula, and vice versa.

See also Unit propagation Boolean satisfiability problem 2-satisfiability

References

Further reading Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 978-3-540-00428-8. Zbl 1133.03001.

Worked examples

Example 1 — a first encounter with Horn-satisfiability

Start with the simplest possible case. Write down what Horn-satisfiability claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Horn-satisfiability before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Horn-satisfiability ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Horn-satisfiability

In research: Horn-satisfiability appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Horn-satisfiability in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Horn-satisfiability is common in secondary-school and first-year university syllabi. It links to neighbouring topics Logic in computer science, P-complete problems, Satisfiability problems, so understanding it makes those chapters shorter.
In everyday life: Look for Horn-satisfiability outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Horn-satisfiability” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Horn-satisfiability in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Horn-satisfiability means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Horn-satisfiability out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Horn-satisfiability in simple terms?

Why does Horn-satisfiability matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Horn-satisfiability?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Horn-satisfiability.