“Maybe the only significant difference between a really smart AI and a human being was the noise they made when you punched them” — Terry Prattchet

What is Knowledge Representation and Reasoning (KR&R)?

Humans are amazing at interpreting knowledge and reasoning about the knowledge, machines — not so much.

Take the below question for example, try to infer what day it is:

If I have an AI lecture today, then it is Monday or Wednesday
It is not Monday
I have an AI lecture today or I have no class today
If I have no class today then I am sad
I am not sad

Did you manage to work out the day? It’s Wednesday. You took multiple sources of information and combinded them to reason that it was Wednesday. That was great, but how would a machine do that?

This is where KR&R comes in.

Declarative approach to building knowledge based agents

The declarative way to build a knowledge based agent is to provide the agent with two things:

  1. A knowledge base which contains facts (assertions, propositions) and general knowledge about a domain in a formal language
  2. A reasoning engine that produces relevant consequences of the knowledge base.

In other words, the agent needs a knowledge base which is a set of facts (Liverpool is in Merseyside, Merseyside is in the UK) and it needs a means to reason and produce relevant consequences of these facts (therefore Liverpool is in the UK).

Languages for KR&R

To store knowledge in a knowledge base (KB) and perform reasoning you have to represent the knowledge in a formal language that machines can understand.

Languages in KR&R are similar to logical languages which some readers may be familar with.

Syntax

An indivudal name denotes an indivudal object, also often called constant symbols. These are objects such as LiverpoolFC, England, the Queen. Letters such as a, b, c, d etc can also be used to denote objects.

An individual variable is a placeholder for an indivual name. In other words, you can denote a variable, a, which represents LiverpoolFC. So a = LiverpoolFC.

A class name denotes a set of indivudal objects. They are also called unary predicate symbols. Examples of classes are: CompetesInPremierLeauge, InEngland, FootballClub.

Atomic Assertion

An atomic assertion has the form A(b) and states that object b is in the class A. Examples of this include CompetesInPremierLeauge(LiverpoolFC). Liverpool is in England so as an atomic assertion this would be InEngland(Liverpool)

Unary rule

A Unary Rule annoyingly takes the form A1 (x) ^ … ^ An(x) → A(x).

The symbol “^” means and, the symbol “ →” means implies. The above can be read that if X is in the class A1, A2, A3 up to An then X is in A. This is useful because we can infer knowledge using the unary rule. For example the rule:

CompetesInPremierLeauge(x) → CompetesInFACup(x)

You can infer that a football team that competes in the Premeir Leauge also competes in the FA cup.

Unary Rule-Based Systems

A unary rule-based knowledge base, K, is a collection of Ka of atomic assertions and Kr, of unary rules.

In non geeky lingo, a unary knowledge based contains facts about objects belonging to classes and unary rules which show connections between classes and objects.

An example of what Kr may hold is:

  1. CompetesInPremierLeauge(x) → CompetesInFACup(x)
  2. CompetesInPremierLeauge(x) → FootballClub(x)

An example of what Ka might hold is:

  1. CompetesInPremierLeauge(LiverpoolFC)
  2. CompetesInPremierLeauge(Arsenal)

Reasoning in Rule-Based Systems

This section will help you to begin to reason in rule-based systems.

Let’s start with an example. Let K be a knowledge base and A(b) an atomic assertion. Then A(b) follows from K, symbolically that is shown as:

K |= A(b)

If whenever K is true, then A(b) is true. This implies a relationship. If this is not true then we write K V = A(b). Note: the V has 2 horizon lines through it, although the symbol isn’t supported on this platform. A symbolic example can be seen below:

K |= CompetesInFACup(LiverpoolFC)

The symbol x |= y means y is provable from x, therefore the above statement:

K |= CompetesInFACup(LiverpoolFC)

Means that the assertion CompetesInFACup(LiverpoolFC) is provable from the knowledge base.

Using this knowledge we can deduct facts from a knowledge base. Let Ka (Atomic assertions in knowledge base) = {A1(a)}; and Kr (unary rules) = {A1(x) →A2(x), A2(x) →A3(x)}

From this we can reason these facts in knowledge base K, if K is Kr and Ka.

K |= A1(a), K |= A2(a), K |= A3(a)

Derived Assertions

A derived assertion is an assertion that is not strictly talked about but can be derived from atomic assertions and unary rules. To find derived assertions one needs to run an algorithm which starts with Ka (knowledge base K assertions) and applys every rule in Kr (unary rules) exhaustivly to the already derived atomic assertions.

Example

First we need to set up our knowledge base:

Knowledge Base
Ka = {A1(a)};
Kr = {A1(x) → A2(x), A2(x) → A3(x)}First Derived Assertions only contain Ka
An application of
A1(x) → A2(x) to A1(a) results in A2(a)
Adds A2(a) to derived assertations

In other words, we know that the unary rule A1(x) → A2(x) exists. So if an object is in the class A1 then it is also in the class A2. Therefore we take the variable, “a”, that we know is in class A1 because of the atomic assertion defined in the knowledge base and by knowing it’s in A1 we also know it’s in A2.

We can run this algorithm until we have all the derived assertions

All derived assertions
A1(x) → A2(x) to A1(a) results in A2(a)
A2(x) → A3(c) to A2(a) results in A3(a)
These are all the possible derived assertions, thus the final result is the set of all derived assertions
DerivedAssertions = {A1(a), A2(a), A3(a)}

Remember, a derived assertion is simply a fact derived from other facts. You are inferring something.

Towards Non-Unary Rule Based Systems

In this section we will explore non-unary rule based systems and attempt to explain the concepts of non-unary rule based systems. A syllogism is a deductive argument used to arrive at a conclusion. A famous syllogism is:

All men are mortal
Socrates is a man
Therefore Socrates is mortal

Another syllogism used is:

Peter is a son of John
John is a son of Joseph
Therefore Peter is a grandson of John

In non-unary rule based systems we require names for relations. A relation is how 2 objects are related together. Examples of relation names are SonOf or grandsonOf. Relations are also called binary predicates and are often denoted as R1, R2 etc.

We can create atomic assertions using relationships in the same sort of way an atomic assertion was made earlier, except this time it accecpts 2 objects. For example, sonOf(Peter, John) denotes that Peter is the son of John.

Rule Based Systems

Rule based systems are based around rules. A rule has the form:

R1(x, y) ^ … ^ Rn(Xn, Yn) ^ A1(Xn+1)^Am(Xm, m) → A(x)

It looks pretty confusing so here’s an explanation. The R1, Rn are relation names. The A1, An and A are class names. X1, X2, Y1, Y2 are variable names. Note that “^” means and.

A rule-based knowledge base is a collection of atomic assertions and rules.

An example may help to clear this up:

Example of Rule-based systems
Set of Atomic Assertions
SonOf(Peter, John)
SonOf(John, Joesph)And the following rules:
sonOf(x, y) ^ sonOf(y, z) -> grandsonOf(x, z)
The above rule states that if X is the son of y and if y is the son of z then x must be the grandson of z.
The grandsonOf(Peter, Joesph) shown symbolically isK |= grandsonOf(Peter, Joesph)

Propositional Logic

Propositional Logic (sometimes called Propositional Calculus) is a branch of logic that defiens way to combine statements or sentences together.

In previous systems seen above there is no way to say that something is not. For example, Not CompetesInPremierLeauge(LiverpoolFC) which denotes that LiverpoolFC does not play in the premier leauge is not possible in previous systems.

You also cannot connect sentences using “or”. Today I will sleep or I will study.

A proposition is a statement that can be true or false, but not both at the same time.

Compound Propositional Statements

Given knowledge, which is the below paragraph:

The meeting can take place if all members have been informed in advance, and it is quorate. It is quorate provided that there are at least 15 people present. Members will have been informed in advance if there is not a postal strike. Therefore, if the meeting was cancelled, we conclude that there were fewer than 15 members present, or there was a postal strike

We can turn it into a propositional statement. Atomic propositions are created from statements, the simplest statements from the paragraph are shown below:

M: The meeting takes place
A: all members have been informed
P: There is a postal strike
Q: The meeting is quorate.
F: there are at least 15 members present

Remember, the above statement was changed into atomic propositions to allow the computer to read it easily.

We can turn this into a statement

If A and Q then M. If F then Q. If not P then A.

And we can conclude

If not M then not F or P.

Propositions may be combinded with other propositions to form compound propositions. The connects used to combind propositions together are:

Some authors use different notations, these are given in brackets.

Propositional formulae

An atomic proposition is a proposition that cannot be broken down anymore. For example, the proposition

I really like pizza or I hate bridges

Contains a connective and 2 propositional statements. An atomic proposition is one that has no sub-propositions and no connectives such as “I like pizza”. If P and Q are atomic propositions then the following can apply:

P ^ Q
P v Q
P <=> Q
P => Q

The meanings of each symbol are

P ^ Q = P and Q
p v Q = P or Q
P <=> Q = P is true if and only if Q is true
P => Q = P entails, implies, or has a consequence Q.
¬P = Not P.

If P is a propositional formula then ¬P is a propositional formula as well.

Truth Values of Propositonal Statements

All propositional statements have a truth value, either True or False. An interpertation “i” gives a truth value to every atomic proposition. Symbolically this is shown as I(p)∈{0,1}. The value p can either be 0 (false) or 1 (true).

Truth Tables

A trurth table is a table showing the truth value of an atomic proposition under certain circumstances.

Seen above is an example of a truth table. T represents True, F represents False.

Conjunction

Conjunction is the name used to mean “and” in propositional logic. True and True would equal True whereas True and False would equal False.

Below is a truth table for the statement (P ^ Q) which is (P and Q).

Below are propositional statements in example format.

Disjunction

Disjunction is the name used to mean “or” in propositional logic. True or False would equate to True.

Below is an image showing the disjunction of (P v Q) otherwise known as (P or Q) and the truth table for it.

Below is an image showing different examples of the disjunction

Equivilance

Given P < = > Q, True is only returned if P is the same as Q. In other words, they have to hold the same value for it to be true.

Below is the truth table for equivilance.

Below is an image showing different examples of equivilance

Implication

Logical Implication is a type of relationship between two statements where one implies the other. The statement can be read as “logically implies” or just “Implies”. If A and B represent statements then A implies B or A → B.

Many students of logic find implication the hardest, so let’s start with what implication is not.

  • It doesn’t mean “suggests”.

If you say Bill doesn’t want to go to dinner with you friday night implies Bill doesn’t like you, this may be a perfectly good statement in English but in logic it’s not a good statement. All it implies is some sort of suggestion of something, such as Bill not liking you.

  • It doesn’t mean “causes”

There is no caustation in implication. One could say that green is a colour implies January is a month and that is a logical true implication even though there is no causaility in that. Just because green is a colour does not cause January to be a month.

  • Statements with implications must always hold a truth value

We have to give truth values even in cases where you might not think it needs a truth value

Below is an image showing the truth table of implications.

One might care to notice that if Q is false then the statement is true.

Logical implication doesn’t work both ways. A → B does not equal B → A. However, the negation of the statement is equal to the original statement.

A -> B = -A -> -B

Below is an image showing different examples for implication

Logical implication when shown in this format is weak. A → B has little meaning for readers. Instead I invite the reader to look at a real world example of implication.

It is often possible to assert a universal statement using logical implication, as seen below.

x > 2 ∧ x is prime ⟹ x is odd.

X is more than 2 and X is prime implies that X is odd. What makes this statement useful is that there isn’t a single number that holds for X where it is greater than 2 and prime, but not odd.

Truth under an interpretation

Given an interpretation (that is, an assignment of meaning to the symbols. Often giving meaning such as words or numbers to algebraic symbols) we can compute the truth value of any proposition under I (interpretation).

I(P) = 1, therefore under this interpretation P is true.
I(p) = 0, therefore under this interpretation P is false.

Satisfiability

A proposition is considered satisfiable if there exists an interpretation under which it is true. The formula

I(p∧¬p)

Is not satisfiable because it will always result in 0 (try making p 1 or 0 yourself)

Again, a proposition is satisfiable if there exists an input that results in the proposition being true.

I(P) is satisfiable if for some interpretation P is True. In this case, P is true when it is equal to 1, or it is true when it is true.

** There are 2^n interpretations if P has n propositional atoms. **

Thus to generate a truth table a table with 2^n rows is needed. This is not practical and will take forever to compute, even with a small number of interpretations such as 100. This will cause a combinatorial explosion.

Knowledge Bases

Let’s go back to the knowledge base question first purposed at the start of this article:

The meeting can take place if all members have beeninformed in advance, and it is quorate. It is quorateprovided that there are at least 15 people present.Members will have been informed in advance if there isnot a postal strike. Therefore, if the meeting wascancelled, we conclude that there were fewer than 15members present, or there was a postal strike

Then that gives us the propositional statements:

m : “the meeting takes place”a: “all members have been informed”p: “there is a postal strike”q: “the meeting is quorate”f: “there are at least 15 members present”

Which we can formalise as:

((a∧q)⇒m),(f⇒q),(¬p⇒a)

This was simply to remind you of knowledge bases.

Propositional Knowledge Bases and Reasoning

A propositional knowledge base is a finite set of propositional formulae, just like normal knowledge bases.

Suppose a propositional knowledge base, X, is given to us. Then a propositional formula, P, follows from X, if the following holds for every interpretation, I.

If I(Q) = 1 for all Q∈X, then I(P) = 1.

This can be read as:

X |= P

Which just means that P is provable from the knowledge base X. The proposition is provable from the knowledge base X. Propositional knowledge bases and reasoning is pretty much the same as ordinary knowledge base and reasoning discussed earlier.