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\models E(a)$. This set is stored in: $\text{DerivedAssertions}$ In only remains to check whether $A(b)$ is in $\text{DerivedAssertions}$.

The algorithm computes the set $\text{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 $\text{DerivedAssertions}$ by applying the rule: $A_1(x)\wedge\ldots\wedge A_n\rightarrow E(x)$ to the atomic assertions: $A_1(x),\ldots,A_n\in\text{DerivedAssertions}$

Example

Let:

$K_a=\{A_1(a)\}$
$K_a=\{A_1(x)\rightarrow A_2(x),A_2(x)\rightarrow A_3(x)\}$

In:

First $\text{DerivedAssertions}$ contains $K_a$ only.
Then an application of $A_1(x)\rightarrow A_2(x)$ to $A_1(a)$ adds $A_2(a)$ to $\text{DerivedAssertions}$.
Then an application of $A_2(x)\rightarrow A_3(x)$ to $A_2(a)$ adds $A_3(a)$ to $\text{DerivedAssertions}$.
Now no rule is applicable. Thus: $\text{DerivedAssertions}=\{A_1(a),A_2(a),A_3(a)\}$ is returned.