and B. A says “I am a knave, or B is a knight.” What are
A and B?
Step 1: Understanding Text (and Diagrams)
In this case, identifying the problem’s parts or com-
ponents (for example, assertions, goals) amounts to
discovering at least that:
There are two inhabitants A and B.
Either A is a knight, or A is a knave (exclusive or operator).
Either B is a knight, or B is a knave (exclusive or operator).
If A is a knight, then A always says the truth. Otherwise, he always lies.
If B is a knight, then B always says the truth. Otherwise, he always lies.
A says that A is a knave, or B is a knight (inclusive or
Is A a knight or a knave? Is B a knight or a knave?
Step 2: Identify Modeling and Solving Techniques
Being a logical problem, a number of different
approaches can be exploited for automatic theorem
proving. This problem can be represented through
propositional logic: as a consequence, techniques
like, for example, truth tables or resolution might be
suitable for solving the problem.
Step 3: Identify Problem Components
and Hidden Knowledge
Problem components are four propositional symbols
with obvious meaning. We have not identified any
hidden knowledge useful to solve this problem.
Step 4: Frame the Model
The problem model is made of the logical, propositional sentences, together with the goals to be
proved, namely the truth value of a_is_knight and
b_is_knight. Given the exclusive or between knights
and knaves, we also have:
a_is_knight ex-or a_is_knave
b_is_knight ex-or b_is_knave
Finally, from the sentence, A says “I am a knave, or B is
a knight.” we should be able to understand also that:
a_is_knight → (a_is_knave ∨ b_is_knight)
a_is_knave → ¬ (a_is_knave ∨ b_is_knight)
Step 5: Solve the Problem
To solve this problem we can, for example, use resolution (Robinson 1965): taking as the goal the propositional fact that a_is_knight, it is possible to prove
that A is a knight in two resolution steps. Similarly for
the B inhabitant.
Example 4: Triangles
This example has a very simple text: How many triangles are in figure 2?
Notice that the accompanying picture is quite easy
to understand: generally speaking, pictures can be
much more complex, and could require a deeper
understanding, as well understanding of the textual
part. For example, understanding such an easy pic-
ture would require spatial interpretation and reason-
ing, the ability to cope with spatial and textual
knowledge in a correlated manner, and some form of
abstraction toward simple concepts such as triangles
(Seo et al. 2014).
Example 5: The Castle Puzzle
This problem21 is again defined partly through natural language text, and partly by means of an accompanying diagram: Given the picture in figure 3, which
is bigger: the total area of blue or the total area of
Different ways for solving this puzzle exist. For
example, one way would be to understand that:
The picture is a rectangle 8 units wide and 10 units
In the picture there are two areas: a blue one and a
The blue part from the picture is composed by two triangles and a rectangle; from the rectangle a small
square has been subtracted.
The question addressed by the problem is to determine
which of the two areas is bigger.
Given this knowledge, and a background knowledge about simple geometry concepts (that is, how to
compute areas of rectangles and triangles), it would
be possible to compare the two areas and solve the
problem by planning a set of actions such as determining the important data for each shape (number
and type of different geometric shapes composing the
blue or white areas, size of the edges for each rectangle, and edges of the triangles), compute the areas,
and compare them. Note that for the computation of
the blue area the machine should understand that it
can be derived by summing the area of the rectangle
and of the two triangles, and by subtracting from the
total the area of the small white square. Solving the
problem therefore means the ordered execution of
the actions determined by such a plan.
Notice that we assume a background knowledge
about the area of triangles and rectangles. Indeed, a
human player might observe that the two triangles
can be joined to form a rectangle (after a
rotation/translation of one triangle). In such a case,
to solve the puzzle it would suffice to count the number of square units: no knowledge about the computation of areas would be needed.
Another approach instead, would be to exploit the
low-level picture representation: a computer, for
example, might solve the problem by simply counting the number of pixels of one color. Such a solution
would not require any understanding of what is in
the image, and we believe it is not a solution
exploitable by a human player.