Answer Set Programming Assignment 2

COMP4418, 

Worth: 15 %
This assignment consists of five questions.
1. [20 Marks] (Answer Set Programming)
A clique of a graph is a set of vertices C that are all adjacent to each other. That is, for a graph
with vertices V and undirected edges E ⊆ {{x, y} | x, y ∈ V }, a clique is a set C ⊆ V such that for
all x ∈ C and y ∈ C, if x 6= y, then {x, y} ∈ E. A k-clique is a clique of size k, that is, |C| = k.
(a) Write an ASP program that decides the k-Clique problem:
Input: A graph with vertices V and edges E ⊆ V × V , and a natural number k ≥ 0.
Problem: decide if there is a k-clique.
Assume the input parameters V , E, k are encoded in ASP in the form of a unary predicate
v, a binary predicate e, and a constant symbol k, respectively. Use a unary predicate c to
represent the vertex cover C. Your program should have no more than two rules.
(b) Use an ASP solver1
to determine how many k-cliques the graph has for k ∈ {3, 4, 5, 6}.
Hint: the number of 2-cliques is 11.
1 2
3
4
5
6
2. [20 Marks] (Answer Set Programming)
Consider the following logic program P.
a :- not b, not c.
b :- not a, not c.
c :- not a, not b.
d :- a.
d :- b.
d :- c.
Determine stable models of this program. For every candidate interpretation S, specify the reduct
P
S. Give your solution in a table of exactly (!) the following form and order:
1E.g., download the Clingo solver from https://potassco.org/ and run your program with clingo clique.lp.
1
Candidate S Reduct P
S Stable model?
{a, b, c, d} d :- a. d :- b. d :- c. ✗
{a, b, c}
{a, b, d}
{a, c, d}
{b, c, d}
{a, b}
{a, c}
{a, d}
{b, c}
{b, d}
{c, d}
{a}
{b}
{c}
{d}
{}
2
3. [20 Marks] (Reasoning about Knowledge)
Suppose all you know is the KB
∀x(P(x) ↔ x = #1 ∨ x = #2) ∧ ∀x(P(x) ↔ ¬Q(x))
(a) Determine the set of known instances of P(x) ∧ Q(y), that is, all pairs of standard names
(n1, n2) ∈ {#1, #2, #3, . . .} × {#1, #2, #3, . . .} such that OKB |= K

P(n1) ∧ Q(n2)


.
(b) Determine RES[KB,(P(x) ∧ ¬Q(y))].
You may simplify the resulting formula to eliminate true and false.
4. [20 Marks] (Limited Belief)
Consider the knowledge base
(F → C) ∧ (C ↔ ¬U).
(a) Bring this knowledge base into proper+ form.
Let KB denote the resulting proper+ knowledge base.
(b) Determine the minimal k ≥ 0 such that OKB |≈ Kk (F ∨ U ∨ C) hold?
(c) Determine the minimal k ≥ 0 such that OKB |≈ ¬Kk¬(¬F ∧ ¬U) hold?
5. [20 Marks] (Reasoning about Action)
Suppose we have a domestic service robot cleaning up our house. It has a box, and into that box
it can put objects. The robot can also shake the box to test whether something is in it. Finally
it can move the box and its contents to other locations. We assume that in reality, the box does
contain some object, but the robot does not know that. This scenario is modelled by the following
basic action theory:
Σ0 = {∃xInBox(x)}
Σdyn = {Poss(a) ↔ true
SF(a) ↔ (a = shakeBox → ∃xInBox(x))
[a]InBox(x) ↔ a = putInBox(x) ∨ InBox(x)
[a]location(x) = y ↔ (a = moveBox(y) ∧ InBox(x)) ∨ (∀y
0
a 6= moveBox(y
0
) ∧ location(x) = y)}
Prove or disprove the following projection problems using regression:
(a) Σ0 ∧ Σdyn |= ∀x[putInBox(x)]InBox(x)
(b) Σ0 ∧ Σdyn |= ∀y [moveBox(y)]∀x(InBox(x) → location(x) = y)
(c) Σ0 ∧ Σdyn ∧ OΣdyn |= [shakeBox]K∃xInBox(x)
(d) Σ0 ∧ Σdyn ∧ OΣdyn |= [shakeBox]∃xKInBox(x)
You may abbreviate putInBox by p, moveBox by m, shakeBox by s, InBox by I, and location by `
for better readability.
Submission
You will need to answer the questions in a file named assn2.pdf Submit using the command:
give cs4418 assn2 assn2.pdf
The deadline for this submission is 14:59:59pm 27 September.

Late Submissions
In case of late submissions, the maximum available mark is reduced by 10 points for each day late.
No extensions will be given for the assignment (except in case of illness or misadventure).