Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

#### 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 _{1}∧...∧b_{m}* such that for each

*b*there is some

_{i}*A*such that

_{i}*⟨b*, then

_{i},A_{i}⟩ ∈C*⟨h,A*can be added to

_{1}∪...∪A_{m}⟩*C*. Note that this covers the case of atomic clauses, with

*m=0*, where

*⟨h,{}⟩*is added to

*C*.

**Procedure**ConflictBU(

*KB,Assumables*)

2:

**Inputs**

3:

*KB*: a set Horn clauses

4:

*Assumables*: a set of atoms that can be assumed

**Output**

5: set of conflicts

6:

**Local**

7:

*C*is a set of pairs of an atom and a set of assumables

8:

*C←{⟨a,{a}⟩:a*is assumable

*}*

9:

**repeat**

10:

**select**clause "

*h←b*" in

_{1}∧...∧b_{m}*KB*such that

11:

*⟨b*for all

_{i},A_{i}⟩∈C*i*and

12:

*⟨h,A⟩∉C*where

*A=A*

_{1}∪...∪A_{m}13:

*C←C∪{⟨h,A⟩}*

14:

**until**no more selections are possible

15:

**return**

*{A: ⟨false,A⟩∈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 _{1}⟩* and

*⟨a,A*are in

_{2}⟩*C*, where

*A*, then

_{1}⊂A_{2}*⟨a,A*can be removed from

_{2}⟩*C*or not added to

*C*. There is no reason to use the extra assumptions to imply

*a*. Similarly, if

*⟨false,A*and

_{1}⟩*⟨a,A*are in

_{2}⟩*C*, where

*A*, then

_{1}⊆A_{2}*⟨a,A*can be removed from

_{2}⟩*C*because

*A*and any superset - including

_{1}*A*- are inconsistent with the clauses given, and so nothing more can be learned from considering such sets of assumables.

_{2}**Example 5.22:**Consider the axiomatization of Figure 5.8, discussed in Example 5.20.

Initially, in the algorithm of Figure 5.9,
*C* has the value

*{⟨ok_l*

_{1},{ok_l_{1}}⟩,⟨ok_l_{2},{ok_l_{2}}⟩, ⟨ok_s_{1},{ok_s_{1}}⟩,⟨ok_s_{2},{ok_s_{2}}⟩,*⟨ok_s*

_{3},{ok_s_{3}}⟩, ⟨ok_cb_{1},{ok_cb_{1}}⟩, ⟨ok_cb_{2},{ok_cb_{2}}⟩}.The following shows a sequence of values added to
*C* under one sequence of selections:

*⟨live_outside,{}⟩*

*⟨live_w5,{}⟩*

*⟨live_w3,{ok_cb*

_{1}}⟩*⟨up_s*

_{3},{}⟩*⟨live_w4,{ok_cb*

_{1},ok_s_{3}}⟩*⟨live_l*

_{2},{ok_cb_{1},ok_s_{3}}⟩*⟨light_l*

_{2},{}⟩*⟨lit_l*

_{2},{ok_cb_{1},ok_s_{3},ok_l_{2}}⟩*⟨dark_l*

_{2},{}⟩*⟨false,{ok_cb*

_{1},ok_s_{3},ok_l_{2}}⟩.Thus, the knowledge base entails

*¬ok_cb*

_{1}∨ ¬ok_s_{3}∨ ¬ok_l_{2}.The other conflict can be found by continuing the algorithm.