Existential Query Answering in the Blocks World

The Blocks World is a classic symbolic-AI domain in which named blocks are related by predicates such as on(x, y). A knowledge base (KB) stores facts about the current configuration, and a query asks whether a logical statement follows from those facts.

Given:

1. $on(A,C)$
2. $on(D,B)$

the query is:

$$\exists w\; above(w,B)$$

This asks:

Does there exist at least one object $w$ that is above block $B$?

In standard Blocks World terminology, on(x, y) usually means that block $x$ is directly on block $y$. The relation above may either be interpreted as a synonym for direct on, or as a transitive relation meaning “somewhere higher in the same stack.” Under either interpretation, the fact $on(D,B)$ provides a witness: $D$.

Therefore, the answer is true, with substitution:

$$w = D$$

and proof:

$$on(D,B) \models above(D,B)$$

Hence:

$$\boxed{\exists w\; above(w,B)\text{ is true}}$$

Footnotes

1. Blocks world - Overview of the classic symbolic-AI planning domain. ↩

1. Formalizing the Knowledge Base

The constants are:

• $A$: a block
• $B$: a block
• $C$: a block
• $D$: a block

The binary predicate on(x, y) represents a direct spatial relationship:

$$on(x,y) = \text{“block }x\text{ is directly on block }y\text{”}$$

The KB is:

$$KB = \{on(A,C),\; on(D,B)\}$$

The query uses the predicate above:

$$Q = \exists w\; above(w,B)$$

In a simple representation, we can define:

$$above(x,y) \leftarrow on(x,y)$$

This rule states that anything directly on $y$ is also above $y$.

Thus:

$$on(D,B) \rightarrow above(D,B)$$

Since $D$ is an object for which above(D, B) is true, the existential query succeeds.

Important terms include constant, predicate, knowledge base, and witness.

2. Understanding the Existential Quantifier

The symbol $\exists$ is the existential quantifier.

The expression:

$$\exists w\; above(w,B)$$

means:

There is at least one object $w$ such that $w$ is above $B$.

The variable $w$ can be replaced by each known object:

$$above(A,B) \lor above(B,B) \lor above(C,B) \lor above(D,B)$$

The query is true if at least one of these grounded statements is true. From the KB:

• $above(A,B)$ is not given.
• $above(B,B)$ is not given.
• $above(C,B)$ is not given.
• $above(D,B)$ follows from $on(D,B)$.

Therefore:

$$\exists w\; above(w,B)$$

is true with witness $D$.

The existential query does not require every object to be above $B$, nor does it require the witness to be unique. It only requires one satisfying object.

3. Direct on Versus General above

A crucial modeling issue is the intended meaning of above.

Direct interpretation

If above(x, y) means exactly “$x$ is directly on $y$,” then:

$$on(D,B) \Rightarrow above(D,B)$$

The query is immediately answered by $D$.

Transitive interpretation

If above(x, y) means “$x$ is anywhere above $y$ in a stack,” then the relation is transitive:

$$above(x,y) \land above(y,z) \rightarrow above(x,z)$$

For example, if the KB contained:

$$on(A,D)$$

then we could infer:

$$above(A,D)$$

and, because $D$ is on $B$:

$$above(D,B)$$

we could also infer:

$$above(A,B)$$

However, the supplied KB contains only $on(A,C)$ and $on(D,B)$. There is no connection between the stack containing $A,C$ and the stack containing $D,B$. The direct witness $D$ is already sufficient.

4. Visualizing the Two Stacks

The facts describe two independent stacks:

The relevant stack is:

$$D \text{ is above } B$$

The fact involving $A$ and $C$ is irrelevant to the query because it does not place any object above $B$:

$$on(A,C)$$

does not imply:

$$above(A,B)$$

No rule connects $C$ to $B$, and no rule connects the two stacks.

Key terms include direct relation, transitivity, stack, and ground atom.

5. Proof by Substitution

Existential queries can be answered by finding a substitution that makes the formula true.

Start with:

$$\exists w\; above(w,B)$$

Choose the substitution:

$$\theta = \{w/D\}$$

Applying $\theta$ gives:

$$above(w,B)\theta = above(D,B)$$

From the KB:

$$on(D,B)$$

Using the rule:

$$on(x,y) \rightarrow above(x,y)$$

we derive:

$$above(D,B)$$

Therefore:

$$KB \models above(D,B)$$

and consequently:

$$KB \models \exists w\; above(w,B)$$

The notation $KB \models Q$ means that the query $Q$ is logically entailed by the KB: every interpretation that satisfies the KB also satisfies $Q$.

6. Why the Other Fact Does Not Answer the Query

The first fact is:

$$on(A,C)$$

It supports the conclusion:

$$above(A,C)$$

but the query requires an object above $B$:

$$above(w,B)$$

The second argument does not match:

• Fact: $on(A,C)$
• Required target: $B$

Therefore, this fact cannot directly satisfy the query.

The second fact is:

$$on(D,B)$$

Its second argument is exactly $B$, so it supplies the required witness.

This illustrates unification, argument position, and logical entailment.

7. Closed-World and Open-World Readings

The interpretation of missing facts matters in knowledge representation.

Closed-world assumption

Under a closed-world assumption, facts not present in the KB are treated as false. This is common in database-style reasoning.

Under this interpretation:

• $above(D,B)$ is true.
• $above(A,B)$, $above(B,B)$, and $above(C,B)$ are false unless derived.
• The existential query is true because $D$ is a witness.

Open-world assumption

Under an open-world assumption, missing facts are unknown rather than false. This is common in formal knowledge representation and ontology-based systems.

Even under the open-world assumption, the query is still true because the KB explicitly supports:

$$above(D,B)$$

The distinction would matter for a negative query such as:

$$\neg\exists w\; above(w,B)$$

The absence of a known witness would not necessarily establish that negative claim under open-world reasoning.

8. Relation to Blocks World Planning

In planning systems, a Blocks World state is commonly represented as a set of predicates such as On-Block(x, y), On-Table(x), Clear(x), and HandEmpty(). Operators change the state by adding and deleting predicates; their preconditions determine when an action is legal.

The present problem is not asking for a plan. It is a state-query problem:

• It does not ask how to move a block.
• It does not specify a goal configuration.
• It asks whether a relation is supported by the current KB.

The distinction is important:

The same predicate vocabulary can support both querying and planning, but the reasoning task is different.

Footnotes

1. The Blocks World - Course material describing state representations and predicates. ↩

2. Classical Planning - Lecture notes on Blocks World operators, preconditions, add effects, and delete effects. ↩