Rules form the core of Logic Programming, enabling the expression of logical relationships between atoms. The fundamental syntax and semantics of ASP rules define what must be true given certain conditions.
A rule consists of the head, an operator and the body:
head :- body .
In this case the atom head is the head, the atom body is the body and :- is an arrow pointing to the left (←, which is also an allowed operator) and is read as "if ":
If body is in the answer set then head is in the answer set;
head must be in the answer set if body is in the answer set ;
If bodyholds then headholds.
In traditional logic this relation is call an implication: body (logically) implies head.By itself (1) results in the empty set (
{}
) since body is not in the answer set. If body is added as a fact to the program then head will be in the result.
body .
(1) and (2) together result in
{bodyhead}
. Because body is in the answer set then head is in the answer set.We will use "←" rather than the more traditional ":-" throughout the rest of this series.
Warnings
Did you notice that the result for (1) had yellow warning icon associated with it (
{}
)? Hovering over the answer set reveals the warning:
Atom 'body' does not occur in any rule head.
The solver informs the programmer that they may have made a mistake (e.g. perhaps body was spelled wrong?) if an atom in the body is not referenced in the head of any other rule. When (1) and (2) are combined, the answer set is in green and hovering reveals no warning (only information about the processing of that program and the resulting answer sets).
Facts are Rules!
One can rewrite (2):
body ← #true .
where #true is a directive (an atom that starts with # that is handled differently by the solver) that represents the truth value true (⊤). (The truth value false (⊥) is written #false.) Written in this way you can see that facts are simply rules in which the body is implicitly #true! (Processing (1) and (3) together results in the expected
{bodyhead}
.)
Rules whose Body Evaluates to false
If one were to write:
body ← #false .
then the result of (1) and (4) is
{}
. (Notice that in this case there is no warning associated with the answer sets since bodydoes occur in the head of a rule.) In fact, the result of (4) itself is simply the empty set
{}
. When the solver evaluates the body of a rule to the truth value false then that rule is removed. A false body does not mean that the head of that rule will not be found in the answer set. It simply means that that rule doesn't contribute it.Taking this one step further:
p ← #false .
p ← #true .
results in the answer set
{p}
! Why is that? In (5) the first rule is simply removed since its body evaluates to false leaving the second rule which causes p to be in the answer set. Remember: a false body does not mean that the head of that rule will not be found in the answer set — it may be if other rules contribute it.Much much more will be said about this in the sections on "Negation".We will use "⊤" and "⊥" rather than "#true" and "#false", respectively, for the rest of this series.
Answer Sets
Answer sets represent the stable states of your logical world. They're like snapshots of everything that can be definitively concluded from your program's rules and facts. Think of it as a chain reaction: facts activate rules, which generate new facts, which in turn might activate other rules. This process (called grounding) continues until a stable state is reached, where no new facts can be derived. Each such stable state is an answer set.
Multiple Rules
A program with a single rule isn't very interesting so let's add more and investigate the results.
m .
p ← m .
q ← n .
This reads "m. If m then p . If n then q." (or literally "m. p if m. q if n.") with an answer set of
{mp}
(with a warning!). Since we stated m and the rule p ← m means "if m is in the answer set then p must also be in the answer set" then we expect the answer set to contain both m and p. But what about q? Since the rule q ← n means "if n is in the answer set then q must also be in the answer set" because there is no rule with n in the head we should not expect q. Notice that we just stated what the warning is for this program: Atom 'n' does not occur in any rule head!
Answer Sets and Grounding
For programs without negation or recursive rules, answer sets can be found by continually substituting the truth value associated with each atom in the body of rules until all rules have been evaluated. Looking at (6) as an example, the fact m can be replaced with its rule form m ← ⊤ which associates the truth value true (⊤) with the atom m. Next, looking at the rule p ← m we can substitute ⊤ for m which results in p ← ⊤ (which looks like a rule!). This makes it clear why we find p in the answer set if we found m . Finally, looking at the rule q ← n, we have to stop and think for a moment since it's not obvious what to do next. n doesn't have a truth value associated with it since it is not found in the head of any rule. We want to assign the truth value false to n since that would then result in q ← ⊥. As we have already seen in (4), this rule means that our answer set does not contain q. If we define that our programs are subject to the closed world assumption which states that what is not currently known to be true, is false, then we can substitute ⊥ for any unknown atoms! This process of sequentially substituting atoms is called grounding.For the curious reader, the literature formalizes this process of substitution using program stratification which involves dependency graphs to determine the order in which rules must be evaluated in order to find all answer sets for a program.Justification for atoms in an answer set can be boiled down to finding witness rules. If a rule whose body evaluates to true can be found then that rule is called a witness for that atom.
Multiple Facts and Multiple Rules
We can use a disjunction in our fact to investigate this program further:
m ; n .
p ← m .
q ← n .
The answer sets are
{nq}{mp}
. (Notice that there is no warning since all atoms in rule bodies are found in the heads of rules (in this case, the fact)!) Solving this program proceeds in the same manner as above except that there are two different sets of atoms (m and n) due to the conjunction m ; n which are substituted into the rules. One answer set contains m which causes p ← m to be substituted for p ← ⊤ and q ← n to be substituted for q ← ⊥ which results in { m p }. The other answer set contains n which causes p ← m to be substituted for p ← ⊥ and q ← n to be substituted for q ← ⊤ which results in { n q }.If a conjunction is used in the facts:
m .
n .
p ← m .
q ← n .
then there is a single answer set
{mnpq}
.Chaining together multiple rules such as
m .
p ← m .
q ← p .
r ← q .
follows the same process of sequentially substituting the atoms from the head of one rule to the body of the next one until all rules have been grounded and the result is
{mpqr}
.
Minimal Sets can be Tricky!
Think about what you expect the answer sets to be before looking at the results:
p ; q .
p ← q .
{p}
This result may seem counterintuitive at first so let's break it down:
The first line p ; q . says we must have either p or q (but not both, since we want minimal sets — remember that answer sets are minimal sets)
The second line p ← q . says if we have q, we must also have p
So if we chose q from the first line, the second rule would force us to also include p
But that would give us { p, q } which isn't minimal since { p } alone satisfies all rules
Therefore { p } is the only minimal answer set
A more real-world example of this case is:
active ; awake ; sleeping .
awake ← active .
{sleeping}{awake}
Think of these rules as constraints rather than imperative commands. The rule awake ← active . means "you can't be awake unless you're also active". The rule active ; awake ; sleeping . says you must be in one of these states. So, you can be sleeping (which doesn't violate any rules), or you can be awake, but then you must also be active to satisfy the constraint. This leads to the two possible minimal answer sets
{sleeping}{awake}
.This may be confusing and will take a while to wrap your head around it. Our suggestion at least initially is simply to memorize these cases. When we introduce choice rules some of the confusion may be resolved.
Rules with Predicates
We can use some of the examples from the "Just The Facts ..." section to investigate rules with predicates.
which is a semantically identical encoding of the domain and it produces an equivalent answer set (
{fruit_applefruit_orangehas_apple}
) but with a warning.At this point, you might be wondering, "Why bother with predicates if I can represent the same information with simpler atoms?" The real power of predicates shines through when we introduce variables, allowing us to express general relationships and patterns, instead of just specific instances. This is where logic programming truly takes off, enabling us to tackle complex problems with elegance and efficiency. More on that in the next installment!
Limiting Predicates in Answer Sets
Answer sets contain all of the atoms that are in the head of rules whose bodies evaluate to ⊤. When viewing the answer sets this may not be convenient, especially if there are many facts or intermediate atoms that are used to build to a result. For example, in (12) the answer set is
{fruit(apple) fruit(orange)has(apple)}
but only the has(apple) part is of interest. In order to remove superfluous atoms from an answer set, ASP has a #show directive that allows the programmer to specify the predicates (including their arity) that are to be included. Multiple predicates can be included, providing maximal flexibility.So as to not clutter up the program with these directives, the answer set elements in these workspaces allow the author to specify which predicates are to be shown. Using "#show has/1", (12) can be reduced to a salient result of
{has(apple)}
.
Caution!
One thing to note about limiting predicates in answer sets is that it may appear as if you have multiple identical answer sets. Remember that the set of answer sets does not contain duplicates!
a ; b .
p .
The result of (14)without limiting any predicates is
{bp}{ap}
. If this were to be limited to only p/0 then the result is
{p}{p}
. In this case, the answer sets are not duplicates. We've simply hidden the atoms that make the sets unique! If you ever encounter a result that appears to have duplicates then there must be a filter in place!
The Minimality Principle
If you're still scratching your head about the minimality of answer sets (and many people do!), let's look at one more example that might help make it click. Think of it like packing for a trip. You want to bring exactly what you need — no extra baggage! ASP follows the same philosophy. If an atom can be left out of an answer set while still satisfying all the rules, it must be left out.Let's see this in action with a simple example:
sunny ; cloudy .
warm ← sunny .
This program says:
It must be either sunny or cloudy
If it's sunny, then it's also warm
You might think we'd get these possible combinations:
{ sunny, warm }
{ cloudy }
{ sunny, warm, cloudy }
But that last one can't be an answer set — it includes cloudy when it doesn't have to! The minimality principle means we only get:
{ sunny, warm }
{ cloudy }
Each answer set contains just enough atoms to satisfy all the rules, and not a single atom more.This "keep it minimal" approach is why some programs produce surprising results at first glance. It's not just about what could be true — it's about what must be true to satisfy the rules with the smallest possible set of atoms.
Variables in ASP allow rules to express general patterns rather than just specific instances, enabling more powerful and reusable logic programs. Variables work as placeholders that match terms, expanding the expressivity of predicates.4 January 2025
