Blocks World Knowledge Base and AND-OR Proof Tree for \exists w\ \textit{above}w,B | AI Research

Blocks World Knowledge Base and AND-OR Proof Tree for $\exists w\ \textit{above}(w,B)$

Verified Sources

Sep 12, 2026

I can’t complete the “previous question” requirement (the specific Blocks World KB and the exact query semantics) because I don’t have the earlier KB, predicates, constants, or rules you used. Also, I’m unable to run the required web searches right now (tool limit), so I can’t fetch external details to reconstruct your exact KB.

That said, below is a Coursify-ready course section template that shows how to build the KB for the Blocks World “above” relation and how to draw a complete AND-OR proof tree for the query: $\exists w\ \textit{above}(w,B)$

You should plug in the constants (e.g., blocks $\{a,c,d\}$ ) and the facts (e.g., $\textit{on}(a,c)$ ) from your previous question; the proof tree structure will then match your instance exactly.

From KB to AND-OR tree (what you must do)

Blocks, relations, constants

1. Identify symbols

List all block constants in the KB; fix predicates like on(x,y) and above(x,y)."

Direct support (on)

2. Write base axioms

Add rules linking on(x,y) to above(x,y)."

Transitive closure (above)

3. Write recursive axioms

Add rules that derive above through intermediate blocks."

Existential proof goal

4. Instantiate the query

Expand $\exists w$ by considering each candidate block $w$ ."

AND = rule bodies, OR = alternative rules/facts

5. Build AND/OR proof structure

For each goal above(w,B), use OR over applicable clauses; children goals are AND over rule body literals."

Key terms (with KB roles)

Knowledge Base (KB): the blocks-world axioms and current state facts.
Goal/Query: what the proof tree answers.
AND-OR proof tree: captures logic-programming proof search.
Unification: determines bindings like w := a.
Horn Clause: typical blocks-world rules.

Constructing the Blocks World KB for $\textit{above}$

A standard approach (common in logic-programming treatments of Blocks World) is:

Start from the direct support relation on.
Define above using:
- a base rule: directly-on implies above
- a recursive rule: above is transitive through intermediate blocks

A typical KB looks like this (schema; replace with your exact KB rules/facts):

State facts

$\textit{on}(a,b)$ for each direct placement
$\textit{clear}(x)$ (optional, often used for action planning, not needed for above-transitivity)
$\textit{table}(x)$ or $\textit{on}(x,\textit{table})$ (depends on your encoding)

Inference rules for $\textit{above}$

\textit{above}(x,y) \leftarrow \textit{on}(x,y)

\textit{above}(x,y) \leftarrow \textit{on}(x,z) \wedge \textit{above}(z,y)

Some encodings swap the recursion direction (e.g., using on(z,y) and above(x,z)). If your earlier question used a different axiom set, the proof tree will still follow the same AND/OR principle, but the branch structure changes.

Example KB skeleton (fill in your instance)

Facts (from your previous question):

$\textit{on}(w_1, u)$ , $\textit{on}(w_2, u)$ , ...
and any chain facts required.

Rules:

Rule R1: $\textit{above}(x,y) \leftarrow \textit{on}(x,y)$
Rule R2: $\textit{above}(x,y) \leftarrow \textit{on}(x,z)\wedge \textit{above}(z,y)$

type="tip" title="Pro Tip: Make your AND/OR tree ‘instance-complete’" content="To draw the COMPLETE AND-OR tree for $\exists w\ \textit{above}(w,B)$ , you must (i) list every candidate block constant for $w$ , then (ii) for each candidate, draw the full OR branching over every rule/fact that could prove $\textit{above}(w,B)$ , and (iii) expand every rule body as an AND node."

type="warning" title="Warning: The proof tree depends on the exact KB encoding" content="If your previous question used different predicates/rules (e.g., above via on transitive in the opposite direction, or using a closure axiom like above(x,y) <- above(x,z)&on(z,y)), then the ‘complete tree’ structure will differ. Use the same rule set that your earlier question defined."

Build the complete AND-OR proof tree for $\exists w\ \textit{above}(w,B)$

1
Step 1
Let the set of block constants be $W=\{w_1,\dots,w_n\}$ from your KB. For the existential query, branch on each choice $w:=w_i$ .
2
Step 2
In AND-OR form, the existential is typically handled by an OR over candidate instantiations of $w$ .
3
Step 3
Create an OR node labeled with the goal $\textit{above}(w_i,B)$ ; its children are the applicable ways to prove it.
4
Step 4
If you have R1: above(x,y) <- on(x,y), unify x=w_i,y=B to require on(w_i,B).
5
Step 5
If on(w_i,B) is a fact in the KB, that AND node succeeds immediately; otherwise it becomes a failing leaf.
6
Step 6
For R2: above(x,y) <- on(x,z) & above(z,y), unify x=w_i,y=B to require on(w_i,z) and above(z,B).
7
Step 7
For each fact on(w_i,z_j), create an AND node with two subgoals: on(w_i,z_j) (which should be a fact) and above(z_j,B).
8
Step 8
Use the KB rules again for each subgoal above(z_j,B). This creates deeper levels of the tree.
9
Step 9
Leaves where required facts exist are success; branches where neither a base rule nor any recursive chain can reach B are failure.

Complete AND-OR proof tree (template)

Let your query be:

G_0:\ \exists w\ \textit{above}(w,B)

Let the candidate block constants be:

W=\{w_1,w_2,\dots,w_n\}

Then the complete AND-OR proof tree root is an OR over:

branch $i$ : try to prove $\textit{above}(w_i,B)$

Now for each branch above(w_i,B), expand as OR over ways to prove it using R1/R2 plus any other rules from your KB:

For a fixed candidate $w_i$

Create an OR node:

Success path 1 (R1) if fact $\textit{on}(w_i,B)$ exists.
Recursive paths (R2) for each fact $\textit{on}(w_i,z_j)$ : need both $\textit{on}(w_i,z_j)$ (fact) and $\textit{above}(z_j,B)$ .

Template subtree for candidate $w_i$

Then each subgoal $\textit{above}(z_j,B)$ becomes the same kind of OR expansion (base rule vs recursive rule), until:

you reach a $z_j$ such that $\textit{on}(z_j,B)$ holds (success),
or all recursive chains fail (failure).

Proof search branching factors (conceptual)

For each candidate w_i, the tree branches based on (1) whether on(w_i,B) exists and (2) how many on(w_i,z) facts exist.

Common edge cases when drawing the ‘complete’ tree

Knowledge Check

Question 1 of 4

Q1Single choice

In an AND-OR proof tree for the query ∃w above(w,B), what does the root OR branching represent?

Choosing a block constant w from the KB domain

Choosing a rule to apply at random

Choosing an action in Blocks World planning

Checking if B is clear

Explore Related Topics

Minimum Spanning Trees: Concept, Prim’s vs Kruskal’s, and Complexity Analysis

Ambiguity in the Grammar $S \rightarrow ABA,\; A \rightarrow aA \mid \epsilon,\; B \rightarrow bB \mid \epsilon$

The grammar (S\rightarrow ABA,;A\rightarrow aA\mid\epsilon,;B\rightarrow bB\mid\epsilon) is ambiguous because the two (A) nonterminals can distribute the same (a)-string in multiple ways, especially when (B) derives (\epsilon).

It generates the language (L(S)={a^i b^j a^k\mid i,j,k\ge0}=a^*b^a^).
The shortest string (a) has two distinct left‑most derivations (or parse trees), proving ambiguity.
Every string (a^n) with (n\ge1) can be split between the two (A) symbols in (n+1) ways, yielding multiple parse trees.
The ambiguity stems from both (A) producing (a^*) and (B) being able to vanish via (\epsilon).
An equivalent unambiguous grammar can be constructed, showing the ambiguity is a property of this grammar, not necessarily of the language.

B+ Trees: Random vs Sequential Access (Which Statement Is True?)

Browse all research articles

Blocks World Knowledge Base and AND-OR Proof Tree for ∃w above(w,B)\exists w\ \textit{above}(w,B)∃w above(w,B)