Moving another step forward
Last time, you were able to get an idea about the philosophical and scientific aspects which are at the heart of AI based solutions. The definitions and thoughts about intelligence and how we try to mimic intelligence in the machines are some of the areas that we had a look in to. Now let’s move forward to discuss about the basics of Knowledge representation and Reasoning in AI. This is one of the most interesting and importance sub areas in AI due to the fact that knowledge and how it is represented in order to come up with reasoning methods to take better decisions is a ‘must’ factor in an intelligent agent/machine if we are trying to model them to behave in the general world. Therefore, let’s have a look at what this is all about while focusing on propositional logic for knowledge representation as a starting point to such vast area of study, throughout this article.
Knowledge is a very difficult term to define just as ‘Intelligence’. It defines what and how much we know and about something. For example, if I say that I know “Sri Lanka is an island” it tells that I have certain knowledge about the country Sri Lanka and I know for sure that it is an island. There could be another instance where I say “I hope that my friend would come to have tea with me today”. In this sentence, I am not sure whether my friend would turn up to have tea or not, but I just hope he/she does. So there is a distinction between the former in which I was sure about what I was saying and in the latter, I was not so sure. Therefore, with knowledge the notion of belief is also linked. If we say “I believe that it would rain tomorrow” there is a certain amount of belief in it like there can be a 60% chance of rain whereas if I say that “I am confident that I would rain tomorrow” there is a far better conviction level associated. Thus knowledge is something which is extremely hard to describe and even to represent with such different variations, levels of certainly/conviction and ways of expression based on the different individuals in concern.
Representing knowledge in machines is a way of storing the knowledge in the machines in a manner which could be used to define a model of the world we know of. In the context of AI, a Knowledgebase is used to describe the storage of knowledge in machines which would have representations of the knowledge we have gathered, stored in a variety of ways based on the type of knowledgebase used. It could use a normal database with data, a logical model, a symbolic representation model, etc.
A part of intelligence is the ability to reason out things based on the knowledge we have gathered about a certain thing/situation based on our past experience, on what others have told, from literature and other various means of gathering knowledge. So based on those, we do reason about things which is required for us to take decisions in everyday life. So in the subject of AI, there is a specific sub area called Knowledge representation and reasoning which is used to define the knowledge inside the machines on what we know of the world in which they operate and then to use that knowledge so that the machines could do reasoning to come up with decisions in performing the actions they have to do. In this aspect, there are different ways in which we can represent the knowledge which some are listed as follows.
- Propositional logic
- Predicate Logic (First order logic)
- Description logics
- Modal Logic
- Intuitionist Logic
- Semantic nets
- Ontological modeling
In this article we would mainly focus on defining what ‘Propositional Logic’ is all about and how machines can represent knowledge using it.
“First things first”: Propositional Logic
‘Propositional Logic’ is also known as ‘Boolean logic’. This language was invented by a logician called George Boole in the 18th century. This language was used by AI researchers in the area of knowledge representation due to its simplicity and reasoning ability although it has its limitations when dealing with complex domains which we would look in to later in the next article. Propositional logic is the simplest logical language to learn the basics. Before learning any knowledge representation language we have to understand the foundations of such which are described as follows.
- Syntax – How we have to use the group of symbols and other items used in the representation language in a way that sentences constructed out of those are properly formed. In other words it can be said as this is the ‘grammar’ of the language which defines the different ways which would yield correct sentences adhering to the grammar of the language (as the grammar in English defines that a verb has to be followed by a noun as in “She eats”.)
- Semantics – What is the meaning of each of the sentences that we have constructed based on the syntax of that language. In logical terms this means, it defines the truth of each sentence based in each possible world being considered.
Now we would look at each of the above aspects in detail with regard to Propositional logic.
‘Syntax’ in detail
In the section of syntax, the following are the things used in Propositional logic.
- Propositional symbols – Each symbol stands for a proposition that can be either ‘true’ or ‘false’. Since we are dealing with Boolean logic, a proposition can only take either of the two states; true or false. Propositional symbols are usually written as upper case English letters like P, Q, R, etc.
- Logical connectives – There are number of logical connectives which we can use to combine more than one propositional symbol to define meaningful sentences.
· Conjunction – Is simply the ‘AND’ and is usually denoted by ˄
· Negation – This is simply the ‘Not’ connective to tell negate the truth value of a proposition which is denoted by ̚ or ~
· Disjunction – Means ‘OR’ and is denoted by the symbol ˅
· Implication – Two parts of propositions are linked with this connective. The premise or antecedent is the part on the side of the tail of the connective and the conclusion or consequent of those is on the head side of the connective and is denoted by ->
oFor example:- P˅Q-> R (where antecedent is P˅Q and the conclusion is R)
·Biconditional – This means the statement is true ‘if and only if’ the right hand side of the connective implies that left hand side is true and vice versa. This is denoted by the symbol .
Sentences made out of propositional symbols can be of two kinds.
- Atomic sentences – Having one propositional symbol which can have either the truth value ‘True’ or ‘False’
- Complex sentences – Having more than one propositional symbols being connected with the use of one or more logical connectives shown above
- Examples: – ((P ˄ Q)˅ R), ((P ˄ Q)->R), (((~P) ˅ Q)-> (R ˄ S))
Some more rules in the propositional logic syntax to remember is that it is very important to use parentheses to enclose every sentence which is created with the use of logical connectives and also to remember the order of precedence of logical connectives.
- Use of parentheses is done to ensure that the syntax does not lead to any unambiguity as well as makes reading and understanding complex sentences easy. This rule is sometimes not followed by all the books and other material written on this topic but, it is always advisable to adhere to it to avoid any confusion later.
- The order of precedence (as the order of precedence in arithmetic operators such as (), /, X, +, -) in logical connectives from highest to lowest precedence are as follows.
Negation, Conjunction, Disjunction, Implication, Biconditional (~, ˄, ˅,->,)
What are the ‘Semantics’?
Once the sentences of propositional logic are formed with guidelines from the syntax section, then we have to define its meaning based on its truth value. Based on the number of propositional symbols (let’s say ‘n’) used in a sentence there can be 2n number of possible models to how we can assign truth values to those propositional symbols. For example, if we use two propositional symbols we can assign the truth values ‘true’/’false’ to the two symbols in 4 (= 22)different ways as shown table
Table 1: Possible models of truth values for a two propositional case
Likewise, if the number of propositional symbols is 4 then there can be 24 = 16 different models of how truth values could be assigned. Then to come up with the semantics(meaning in terms of truth value for the entire sentence as a whole) of a sentence based on the truth models for the propositional symbols appearing in them, we use a method called ‘Truth tables’.
As you may have already come across Boolean logic, you may know that each statement linked with above defined connectives has a truth value associated with it based on the truth value of the propositions appearing in them. Let’s assume there are two propositional logic symbols in concern known as P and Q. Then the following truth table depicts each of the truth values based on the various ways in which those two can be linked with the logical connectives discussed in the section is syntax.
Table 2: Truth Table
Now let’s try to model some sentences using propositional logic we learnt so far.
Let’s assume a small world like below where we have the following knowledge.
- It is cloudy today.
- It is gloomy today.
- If it is cloudy and gloomy, it is definitely going to rain today.
So let’s represent the above sentences in propositional logic.
- C -Cloudy
- G – Gloomy Propositional symbols required to represent the world in concern
- R – Rain
- ((C ˄ G) -> R) (It is known that if it is both cloudy and gloomy then it would rain, so we have link C and G with a logical conjunction and then R with an implication)
Since there are 3 propositions in this sentence there are 23 = 8 possible models of truth values for which we can define the semantics of this sentence. But out of those 8 models, the sentence ((C ˄ G) -> R) would only be false in the model where C = True, G = True and R= False (where “it is both cloudy and gloomy but, it does not rain” which contradicts our knowledge of rain as per the assumption made) as per the truth table. (You can try this out by constructing the truth table for this sentence)
Likewise for anything in concern for each of the known facts (knowledge about the world in concern) you can construct propositional sentences using propositional symbols and connectives based on the syntax to come up with different semantics which in turn would yield a knowledge base full of propositional sentences.
In this article we looked at what Knowledge representation and reasoning with regard to AI is all about as well as went in to learning how to use simple propositional logic in this matter. We would go in to discuss reasoning with propositional logic, advantages and disadvantages of propositional logic in the next article, for which you would need to have grasped the basics I have described today. So make sure, you understand these simple concepts which would be extremely essential in learning how to use a knowledgebase to reason out things and also to understand more complex logics such as predicate logic and other knowledge representation languages to follow.
· Artificial Intelligence – A modern Approach, Second edition, Stuart Russell&Peter Norvig
· Knowledge Representation&Reasoning – Ronald Brachman&Hector Levesque