

Introduction to Logic

Tools for Thought


The Blocks World is a popular application area for illustrating ideas in the field of Artificial Intelligence. A typical Blocks World scene is shown here.

Most people looking at this figure interpret it as a configuration of five toy blocks. Some people conceptualize the table on which the blocks are resting as an object as well; but, for simplicity, we ignore it here.
In order to describe this scene, we adopt a vocabulary with five object constants, as shown below, with one object constant for each of the five blocks in the scene. The intent here is for each of these object constants to represent the block marked with the corresponding capital letter in the scene.
{a, b, c, d, e}

In a spatial conceptualization of the Blocks World, there are numerous meaningful relations. For example, it makes sense to think about the relation that holds between two blocks if and only if one is resting on the other. In what follows, we use the relation constant on to refer to this relation. We might also think about the relation that holds between two blocks if and only if one is anywhere above the other, i.e. the first is resting on the second or is resting on a block that is resting on the second, and so forth. In what follows, we use the relation constant above to talk about this relation. There is the relation that holds of three blocks that are stacked one on top of the other. We use the relation constant stack as a name for this relation. We use the relation constant clear to denote the relation that holds of a block if and only if there is no block on top of it. We use the relation constant table to denote the relation that holds of a block if and only if that block is resting on the table. The set of relation constants corresponding to this conceptualization is shown below.
{on, above, stack, clear, table}
The arities of these relation constants are determined by their intended use. Since on is intended to denote a relation between two blocks, it has arity 2. Similarly, above has arity 2. The stack relation constant has arity 3. Relation constants clear and table each have arity 1.

Given this vocabulary, we can describe our scene by writing ground literals that state which relations hold of which objects or groups of objects. Let's start with on. The following sentences tell us directly for each ground relational sentence whether it is true or false. (Once again, we have written the positive literals in black and the negative literals in grey in order to distinguish the two more easily.)
¬  on(a,a) 

 on(a,b) 

¬  on(a,c) 

¬  on(a,d) 

¬  on(a,e) 
¬  on(b,a) 

¬  on(b,b) 

 on(b,c) 

¬  on(b,d) 

¬  on(b,e) 
¬  on(c,a) 

¬  on(c,b) 

¬  on(c,c) 

¬  on(c,d) 

¬  on(c,e) 
¬  on(d,a) 

¬  on(d,b) 

¬  on(d,c) 

¬  on(d,d) 

 on(d,e) 
¬  on(e,a) 

¬  on(e,b) 

¬  on(e,c) 

¬  on(e,d) 

¬  on(e,e) 

We can do the same for the other relations. However, there is an easier way. Each of the remaining relations can be defined in terms of on. These definitions together with our facts about the on relation logically entail every other ground relational sentence or its negation. Hence, given these definitions, we do not need to write out any additional data.
A block satisfies the clear relation if and only if there is nothing on it.
∀y.(clear(y) ⇔ ¬∃x.on(x,y))
A block satisfies the table relation if and only if it is not on some block.
∀x.(table(x) ⇔ ¬∃y.on(x,y))
Three blocks satisfy the stack relation if and only if the first is on the second and the second is on the third.
∀x.∀y.∀z.(stack(x,y,z) ⇔ on(x,y) ∧ on(y,z))

The above relation is a bit tricky to define correctly. One block is above another block if and only if the first block is on the second block or it is on another block that is above the second block. Also, no block can be above itself. Given a complete definition for the on relation, these two axioms determine a unique above relation.
∀x.∀z.(above(x,z) ⇔ on(x,z) ∨ ∃y.(on(x,y) ∧ above(y,z)))
¬∃x.above(x,x)

One advantage to defining relations in terms of other relations is economy. If we record on information for every object and encode the relationship between the on relation and these other relations, there is no need to record any ground relational sentences for those relations.
Another advantage is that these general sentences apply to Blocks World scenes other than the one pictured here. It is possible to create a Blocks World scene in which none of the on sentences we have listed is true, but these general definitions are still correct.

Use the arrow keys to navigate.
Press the escape key to toggle all / one.

