ASP / Clingo Flashcards
What does ASP stand for?
Answer Set Programming
Define an atom in the context of ASP.
An atom is a basic unit of meaning in ASP, usually representing a proposition.
What is a literal?
A literal is an atom or its negation.
Identify the atoms in the following ASP statement: a :- b, not c.
The atoms are a, b, and c.
What is Clingo?
Clingo is a software package that includes an ASP grounder (gringo) and solver (clasp). It’s used to find stable models of logic programs.
Name a primary function of Clingo’s grounder (gringo).
It converts a high-level logic program into a ground (variable-free) format.
Name a primary function of Clingo’s solver (clasp).
It finds the stable models of a ground logic program.
Define a rule in ASP.
A rule in ASP is a statement of the form head <- body, where head is an atom and body is a conjunction of literals.
What does the head of a rule represent?
The head represents what is derived when the body of the rule is satisfied.
What does the body of a rule represent?
The body represents the conditions that must be satisfied for the head to be derived.
Identify the head and body in the following ASP rule: a :- b, not c.
The head is a and the body is b, not c.
What is a stable model?
A stable model is a set of atoms that represents a possible world where all the rules of the program are satisfied.
How does a stable model relate to ground instances?
A stable model is a set of ground instances of atoms that make the program self-consistent.
Are stable models unique?
No, an ASP program can have multiple stable models, or none at all.
What are ground instances in ASP?
Ground instances are specific atoms that result from substituting all variables in a rule with concrete terms. For example, for the rule p(X) :- q(X, Y), r(Y). and terms X = 1, Y = 2, the ground instance is p(1) :- q(1, 2), r(2).
What does negation as failure mean in the context of stable models?
Negation as failure, denoted as not a, means that a is not part of the stable model. In other words, not a is true in a stable model if a cannot be derived from the program rules given the stable model.
How would you write a rule to express that if a is true then b must be true?
b :- a.
How would you write a rule to express that c is true only if a and b are false?
c :- not a, not b.
How would you write a rule to express that d is true if either a or b is true, but not both?
d :- a, not b. d :- b, not a.
How would you write a rule to express that if a and b are true, then c or d must be true, but not both?
{ c; d } :- a, b. :- c, d, a, b.
What is a choice rule in ASP?
A choice rule allows for optional inclusion of atoms in the stable model. It has the form { head } :- body.
How would you write a choice rule to express that a can be true if b is true?
{ a } :- b.
What does the following choice rule express: { a; b } :- c.
If c is true, either a, b, or both a and b can be true.
What is a proposition in ASP?
A proposition is an atom without variables, essentially a statement that is either true or false.
What is a predicate in ASP?
A predicate is a template for generating atoms. It consists of a name and a list of variables or terms.
How would you write a predicate to represent a relation between x and y?
relation(x, y).
Can a predicate have a single variable? Provide an example.
Yes, for example, student(X).
How would you write a predicate to express the parent-child relationship?
parent(x, y). where x is the parent and y is the child.
What would the atom sibling(a, b) represent if sibling is a predicate?
It would represent that a and b are siblings.
How would you write a predicate to express the ancestor relationship recursively?
ancestor(X, Y) :- parent(X, Y). ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
What is a common use of predicates involving arithmetic operations?
Predicates often use arithmetic to express relationships like greater than or less than. For example, greater(X, Y) :- X = Y + 1.
What are cardinality restrictions in ASP?
Cardinality restrictions specify the minimum and/or maximum number of literals that must be true in a stable model.
How would you write a rule that allows for at least 2 and at most 3 instances of a to be true?
2 { a(X) } 3.
How would you enforce that exactly one of a, b, or c is true?
1 { a; b; c } 1.
What does the cardinality restriction 2 { a(X); b(X) } 3 mean when combined with a(1). a(2). b(1). b(2). b(3).
It means that in a stable model, at least 2 and at most 3 of the atoms generated from a(X) and b(X) must be true. Possible combinations could be { a(1), a(2) }, { b(1), b(2), b(3) }, etc.
How would you use cardinality to express that at least one student must be in a class?
1 { in_class(X) : student(X) }.
How would you use cardinality to express that a committee must have between 3 and 5 members?
3 { committee_member(X) : person(X) } 5.
What are the stable models for the program a :- not a.?
The stable model is {} (empty). This might seem counterintuitive because one could think that a should be true if a is not true. However, in stable model semantics, the empty set is the only closed set under this program.
What are the stable models for the program a :- b. b :- a.?
There are no stable models. This can be counterintuitive due to the cyclic dependency between a and b.
What are the stable models for the choice rule { a } :- b. combined with b.?
The stable models are {b} and {a, b}. This may seem counterintuitive if you’re expecting a deterministic outcome.
Given the program a :- b, not c. b. c :- not a. what are the stable models?
There are no stable models. This might be counterintuitive as one could expect b to lead to a, but a being absent also leads to c, creating a contradiction.
Given the program 1 { a; b } 1. a :- b. b :- a. what are the stable models?
The stable models are {a} and {b}. This might be counterintuitive because despite the cyclic dependency, the cardinality restriction enforces that only one of a or b can be true.
What is an aggregate in Clingo?
An aggregate in Clingo is a construct like #sum, #count, or #min that performs an operation over a set. For example, #count { X:fruit(X) } = N counts the number of fruits and stores the count in N.
How do you use external atoms in Clingo?
External atoms in Clingo are prefixed with & and can be used to interface with external computations. For example, &is_prime(X) could check if X is a prime number.
What is optimization in Clingo, and how is it done?
Optimization in Clingo is done using #minimize or #maximize. For example, #minimize { X:fruit(X) } would find the answer set that minimizes the number of fruits.
How do you specify constraints in Clingo?
Constraints in Clingo are rules with an empty head. For example, :- not fruit(X), eat(X). specifies that you cannot eat X if X is not a fruit.
