Artificial
Intelligence

5.4.4.1 Bottom-Up Implementation

The bottom-up implementation is an augmented version of the bottom-up algorithm for definite clauses presented in Section 5.2.2.1.

The modification to that algorithm is that the conclusions are pairs ⟨a,A⟩, where a is an atom and A is a set of assumables that imply a in the context of Horn clause knowledge base KB.

Initially, the conclusion set C is {⟨a,{a}⟩:a is assumable}. Clauses can be used to derive new conclusions. If there is a clause h←b₁∧...∧b_m such that for each b_i there is some A_i such that ⟨b_i,A_i⟩ ∈C, then ⟨h,A₁∪...∪A_m⟩ can be added to C. Note that this covers the case of atomic clauses, with m=0, where ⟨h,{}⟩ is added to C.

Figure 5.9 gives code for the algorithm.

When the pair ⟨false,A⟩ is generated, the assumptions A form a conflict. One refinement of this program is to prune supersets of assumptions. If ⟨a,A₁⟩ and ⟨a,A₂⟩ are in C, where A₁⊂A₂, then ⟨a,A₂⟩ can be removed from C or not added to C. There is no reason to use the extra assumptions to imply a. Similarly, if ⟨false,A₁⟩ and ⟨a,A₂⟩ are in C, where A₁⊆A₂, then ⟨a,A₂⟩ can be removed from C because A₁ and any superset - including A₂ - are inconsistent with the clauses given, and so nothing more can be learned from considering such sets of assumables.