Derived Assertions Algorithm

COMP111 Lectures 2020-11-05

The following algorithm take as input the knowledge base $K$ containing $K_{a}$ and $K_{r}$ and computes all assertions $E (a)$ with $E$ a class name and $a$ an individual name such that $K ⊨ E (a)$ . This set is stored in: $DerivedAssertions$ In only remains to check whether $A (b)$ is in $DerivedAssertions$ .

The algorithm computes the set $DerivedAssertions$ by starting with $K_{a}$ and then applying the rules $K_{r}$ exhaustively to already derived atomic assertions.

Input: a knowledge base K containing assertions K_a and rules K_r
	
DerivedAssertions := K_a
repeat
	if there exits E(a) not in DerivedAssertions
		and A_1(x)^...^A_n(x) --> E(x) in K_r
		and A_1(x),...,A_n(x) in DerivedAssertions
	then 
		add E(a) to DerivedAssertions
		NewAssertion := true
	else 
		NewAssertion := false
	endif
until NewAssertion = false
return Derived Assertions

Rule Application

In the algorithm above we say that:

$E (a)$ is added to $DerivedAssertions$ by applying the rule: $A_{1} (x) \land \dots \land A_{n} \to E (x)$ to the atomic assertions: $A_{1} (x), \dots, A_{n} \in DerivedAssertions$

Example

Let:

$K_{a} = {A_{1} (a)}$
$K_{a} = {A_{1} (x) \to A_{2} (x), A_{2} (x) \to A_{3} (x)}$

In:

First $DerivedAssertions$ contains $K_{a}$ only.
Then an application of $A_{1} (x) \to A_{2} (x)$ to $A_{1} (a)$ adds $A_{2} (a)$ to $DerivedAssertions$ .
Then an application of $A_{2} (x) \to A_{3} (x)$ to $A_{2} (a)$ adds $A_{3} (a)$ to $DerivedAssertions$ .
Now no rule is applicable. Thus: $DerivedAssertions = {A_{1} (a), A_{2} (a), A_{3} (a)}$ is returned.