Home Classroom Artificial Intelligence Artificial Intelligence – Part 4

# Artificial Intelligence – Part 4

1763

Recap and what’s next?

In the previous article we looked at the what ‘Knowledge Representation and Reasoning’ is all about and how it is linked to Artificial Intelligence and also went on to look at the basics of the most simple knowledge representation method with the use of propositional logic. We learnt the syntax and semantics of propositional logic and how to represent general statement in accordance. Today, we would focus on how to represent some more general statements in propositional logic which would ultimately build the knowledge base while looking at some reasoning methods and the advantages and disadvantages of using propositional logic in this context.

Representing a problem in propositional logic

Let’s take a simple domain and try to represent the facts and knowledge about that domain using the basics of propositional logic that we have learnt so far.

Domain/Problem in concern:- There is 3X3 grid structure (composed of 9 squares) where a robot has to traverse from one square to the other starting from his initial location to get to the location where a secret box is kept. There is a hole in one square location for which if the robot went in to it, it would fall and break. The robot has to avoid that square. The requirement is that the robot has to safely traverse this grid and get to the location of the box which in which he can find some gold. Another condition is that the robot can only move left, right, up and down (it cannot traverse in the diagonal direction). When it reaches a square with the location of the hole adjacent to it, it would give an alarm.

Let’s represent the domain with an illustration as follows.

For ease of demonstration I have named the squares in the grid according to the row number and column number as (1,1), (1,2), (1,3) etc.

Now let’s try to represent this simple domain in propositional logic. Let’s define the following propositional symbols required.

H(x,y) – represents that there is a hole in the square represented by (x,y)

G(x,y) – represents that the secret box with gold in located at square (x,y)

A(x,y) – represents that the alarm to notify that one of the adjacent squares has a hole in it when the robot reaches (x,y)

R(x,y) – represent where robot is located

Propositional logic rules constructed out of the above symbols are as follows.

Rule 1(About where the hole is)  :-     H(2,2)

Rule 2(Where the secret box with gold is):- G(3,3)

Under what conditions the alarm would be sounded which has to be written for all the squares, but here only written for some squares for simplicity ( Alarm would be sounded if and only if there is a hole in one of the adjacent squares)

Rule 6(Where the robot is initially) :- R(1,1)

Rule 7(Possible moves for robot from initial position to a square where there is no hole):- These also have to be defined for each square for the robot movement and here only 2 such statements are shown for simplicity.

Once all such statements are defined we can insert those in to the knowledge base. All the rules we have come up with are true (saying that based on the domain in consideration, the truth value for each of the rules are true) Therefore, if we combine them with conjunction connective (˄) , then the entire long statement should be true as well, based on the truth values and semantics of the conjunction connective which we discussed last time.

Now let’s move on to see what logical inference is and how it would be used.

Logical inference

The term ‘inference’ is defined as an ‘act or process of deriving a logical consequence conclusion from premises’ as per Wikipedia. This simply means, based on the facts that we know about the domain in concern (such as the rules we defined above for the robot’s example) how do we arrive at a conclusion (like whether it is good for the robot to move to square(2,2), etc).

Inference is related with the notion of ‘entailment’ which I would try to describe as simply as possible. If there are two sentences A and B A is logically entailed by B is denoted as

A |= B

This means that the sentence A is logically followed by sentence B. If we try to define it more formally, the term entailment stands for A|= B, if and only if every model or assignment which makes A true makes B also true.

Reasoning with Propositional Logic

In order to come up with conclusions based on the defined facts about the domain in a knowledge base we should know the different methods in which we can derive such conclusions or inference. Following are some methods which can be used for reasoning.

1. Inference Rules

a. Modes Ponens rule:- This says if we are given that A -> B (A implies B) is true and also that A is true, then we can conclude that B is also true. We can show by the definition of implication based on truth tables that this rule is valid such that if A˄ (A->B) is true then B should also be true.

b.    AND elimination rule:- If we have a statement as A˄B is true, then we know by the semantics of AND- connective that for this to be true it is necessary for both A as well as B to be true individually. Therefore, when given that A˄B is true, we can either infer A or infer B.

c. Using Resolution:- This is a technique is very common in use for coming up with inference in most of the logics not only with propositional logic. For this to be applied we have to first convert the statements we have defined for the knowledge base in to a form known as “Conjunctive Normal Form” or CNF for short. This means nothing but, all the statements have to be converted so that the statements appear as a “conjunction of disjunctions of literals” as in the form below.

(A˅B˅C) ˄ (D˅E˅F) ˄ (G˅H) ˄ ………………..

In this case all the other connectives such as implication, bi-conditional has to be replaced with respective conjunctions and disjunctions and there are some specific steps to follow in order to convert a general statement in propositional logic into CNF form. Following are the steps required to be followed in order to convert a general statement in to CNF form. The steps have to be considered in the given order.

Once we have followed the above steps and convert propositional logic statements in the knowledge base in to CNF, we can use the resolution algorithm to come up with conclusions. The details about resolution algorithm is too complicated to be shown in a article like this which only focuses on giving the basics of the topic, so I would leave it out for now and introduce the resolution algorithm in the later articles where it would come in again when we move on to predicate logic and other reasoning methods.

Advantages and Disadvantages of Propositional Logic

Now let’s have a quick look at what are the plus points for using propositional logic in knowledge representation as well as identify why it is not the best method to do so.

Some of the advantages of using propositional logic are as follows.

· Simplest logic

·  Limited number of connectives and less syntax

· Easy to construct the knowledge base

Despite the above good points about propositional logic, it is not one of the most commonly used logical representations in knowledge based systems used in practice other than for small examples, small problems for understanding purposes because of the following limitations.

· Have to define a propositional symbol for each of the facts you want to represent about the domain. If there are so many facts you have to define in the given domain, this would not be practically efficient

· Very primitive and is difficult to define relationships between the objects in the domain

· The definitions such as for all, for some kind of quantifiers are not available therefore, we have to explicitly define rules for each and every condition which is a tedious task

Coming up

In this article we emphasized on the usage of propositional logic as a knowledge representation language while looking at how to reason with it, methods used in such case and also advantages and disadvantages of using this type of logic. In the next article, we would be moving to a more complex more useful and practically used type of logic known as ‘Predicate logic’ or ‘First order Logic’. We would try to understand the similarities or differences between these two logics and also get an idea about the basics of predicate logic in the next article.

### Comments

comments

Chathra Hendahewa is a graduate student at Rutgers –The State University of New Jersey since fall 2008 and currently in her second year of studies. She is studying towards her Doctorate in Computer Science and her major research interests are Pattern Classification with application to financial systems, Machine Learning and Cognitive Sciences. She was the first ever International Fulbright Science &Technology awardscholar from Sri Lanka. Chathra graduated from Faculty of Information Technology, University of Moratuwa in year 2007. She is also a passed finalist and a multiple gold medalist of CIMA (Chartered Institute of Management Accountants –UK). She has professional experience in working as a Business Systems Analyst for more than a year at IFS R&D and has completed an internship period in developing modules for‘Sahana-Disaster Management System’. She loves reading biographies, mysteries and science fiction and listening to music during her free time.