UoL CS Notes
Menu

Rule Based Languages

COMP111 Lectures

Syntax

An individual name denote an individual object. They are also called constant symbols:

  • England
  • We also use lower case letters: $a,b,c,a_1,a_2,\ldots$

An individual variable is a placeholder for an individual name. They are denoted by lower case letters:

  • $x,y,z,x_1,x_2,\ldots$

A class name denotes a set of individual objects. They are often also called unary predicate symbols:

  • Human_Being
  • We also often use upper case letters such as $A,B,C,A_1,A_2$

Atomic Assertions

An atomic assertion takes the form $A(b)$ and state the $b$ is in the class $A$:

  • The assertion, \(\text{CompetesInPremierLeague}(\text{LiverpoolFC})\) states that Liverpool FC competes in the Premier League.

Unary Rule

A unary rule take the form: \(A_1(x)\wedge\ldots\wedge A_n(x)\rightarrow A(x)\) Where $A_1,ldots,A_n$ and $A$ are class names and $x$ is an individual variable.

  • The $\wedge$ symbol is the symbol for logical AND.
  • The $\rightarrow$ symbol means implies that.

The rule states the everything in all classes $A_1,A_2,\ldots,A_n$ is in the class A.

Example

The rule, $\text{Disease}(x)\wedge\text{LocatedInHeart}(x)\rightarrow$ $\text{HeartDisease}(x)$, states that every disease located in the heart is a heart disease.

You can also say that the result of the evaluation on the left side is a subset of the objects in the set on the right hand side.

Unary Rule-Based Systems

A unary rule-based knowledge base $K$ is a collection $K_a$ of atomic assertions and $K_r$ of unary rules.

Example

Let $K_a$ contain the following atomic assertions:

  • $\text{CompetesInPremierLeague}(\text{LiverpoolFC})$
  • $\text{CompetesInPremierLeague}(\text{Everton})$ and so on for all members of the class $\text{CompetesInPremierLeague}$

Let $K_r$ contain the following rules:

  • $\text{CompetesInPremierLeague}(x)\rightarrow$ $\text{CompetesInFACup}(x)$
  • $\text{CompetesInPremierLeague}(x)\rightarrow$ $\text{FootballClub}(x)$
  • $\text{CompetesInPremierLeague}(x)\rightarrow$ $\text{BasedInEngland}(x)$

The follwoing atomic asseritons follow from $K$:

  • $\text{CompetesInFACup}(\text{LiverpoolFC})$
  • $\text{FootBallClub}(\text{Everton})$, and so on.

Thus from 20 facts and 3 rules, we can deduce 60 additional facts. This allows us to store much more data in a compact way.

Reasoning in Rule-Based Systems

Let $K$ be a knowledge base and $A(b)$ an atomic assertion. Then $A(b)$ follows from $K$: \(K\models A(b)\)

You can also say that $K$ models $A(b)$.

This means that whenever $K$ is true, then $A(b)$ is true. If that is not the case you can write $K\nvDash A(b)$.

Example 1

In the example $K$ earlier: \(K\models\text{CompetesInFACup}(\text{LiverpoolFC})\)

Example 2

Let:

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

Let $K$ contain $K_a$ and $K_r$. Then:

  • $K\models A_1(a)$
  • $K\models A_2(a)$
  • $K\models A_3(a)$

This chaining shows that if $a$ is in $A_1$ then is also in $A_2$ and so on.