This would be the fifth article on AI to be presented to the readers in diGIT. Just to recap what we had looked at throughout this series of articles; we first introduced you to the history and the field of AI at a glance, then we moved on to identify the basic concepts of AI and next we moved on to the area of Knowledge representation and reasoning which is one of the key areas in AI. We are still in the process of explaining about various methods and ways of knowledge representation and reasoning. In the previous article we focused on how to represent some more general statements in propositional logic, reasoning methods and the advantages and disadvantages of using propositional logic. Now let’s move forward and look at a more expressive language which is widely used for knowledge representation and reasoning in AI. It is none other than ‘Predicate Logic’ which is also known as ‘First order Logic’. Throughout this article we would be looking in to the basics of Predicate logic and how to represent simple knowledge in a knowledgebase using this method.
‘Predicate Logic’ also known as ‘First Order Logic’
First order logic (which would be referred to as ‘FOL’ in the rest of the article) is another way of expressing and representing knowledge apart from the propositional logic which we learnt in the previous articles. FOL has some additions to the propositional way of knowledge representation with the inclusion of predicated and quantifiers which have more representation power when compared to just propositions, which we are looking at now.
First as we have to look at the syntax of FOL. Syntax means the groups of symbols are other things when arranged in a certain way give properly formed sentences. It is extremely essential to know the syntax of a logical language in order to use it correctly and effectively in knowledge representation and reasoning.
Syntax of FOL
FOL has two types of symbols used which are known as logical symbols and non-logical symbols. First let’s take a look at the details about the above two types of symbols used.
There are three sorts of logical symbols used in FOL which are explained as follows.
Punctuation – Just as in English language we have the punctuation symbols to express the meaning of the sentence in a proper manner. The main punctuation symbols used in FOL are comma, period, and brackets (“,”, “.”,”(…)”)
Connectives – These help to connect two or more predicates together to form a meaningful sentence that is expressed in FOL. There are general binary connectives such as negation (~), conjunction (^), disjunction (V), implication (->), bi-conditional (<->) while in addition to them there are some new connectives known as quantifiers which are used to express the meanings such as ‘There exists’ , ‘For all’ and ‘logical equality’ (=). These quantifiers were lacking in the propositional logic we learnt before so the knowledge expressive power was limited. But here with the existence of quantifiers more useful facts can be expressed about the domain in concern
Variables – These are used to specify the symbols that can be used for the predicate which are usually named as a,b,c,…or x,y,z,….The convention is to write variable in lower case letters.
Then the non-logical symbols which are applicable and defined based on the domain in which it is being used for are discussed as follows. The naming as well as the usage of such depends on the application or the domain in concern unlike the logical symbols which are like the ground terms for FOL
Predicate symbols– As the name implies the other term, ‘Predicate Logic’ is used for FOL due to the fact that it uses predicate symbols. These can be defined as any way as we like based on the domain in concern having variables describing what each predicate is linked/referred to. These merely show the relationship between variables based on the predicate they are attached to. Each predicate symbols has an ‘arity’ (arity >=0) which defines the number of arguments it takes. Usual convention is to start predicate symbols names with upper case letters and no spaces are kept to separate words but each new word is started with an upper case letter. Following are some examples of predicate symbols.
§ OlderThan(a,b) – This means ‘a’ is older than ‘b’. Here the predicate is the terms ‘OlderThan’ with two variables linked to it as ‘a’ and ‘b’. Therefore we can say that this predicate has two arguments thus its arity is two.
Female(a) – This specifies a predicate which defines the term ‘Female’ and shows that variable ‘a’ is a female. The arity of this predicate is one
- Function symbols – In addition to just predicates, FOL has the capability of expressing functions. These also has the same features as predicates like consisting of number of arguments. Usually the functions names are started with a lowercase letter but the each new work is started with an upper case letter. Following are some examples of function symbols
§ bestFriend(c,a) – Which defines the function that ‘c’ is the best friend of ‘a’
§ fatherOf(c,b) – This tells that ‘c’ is the father of ‘b’.
Scope of quantifiers
Further we need to have a look at the scope of quantifiers that we described in the logical symbol section.
Generally when the quantifier ‘for all’ > is used, it means for all the variables defined under that should be true. For example if we say:-
OlderThan(x,y) – This means for all the variables in x and all the variables in y, always x is older than y. Therefore, the scope of the quantifiers are there for the entire predicate OlderThan(..,..). Further, this can also be written as x,y. OlderThan(x,y) – where the ‘for all’ quantifier is applicable to both variables x and y so there are specified as separated by commas instead of indicating two quantifier symbols, which gives the same meaning as above.
If we have a sentence like below, the identification of scope of the quantifiers become more complex.
In the above FOL statement, the predicates appear as general terms without specific names as ‘P’ and ‘Q’. The occurrence of variable ‘x’ in both locations are bound by the ‘for all’ quantifier appearing at the start while the scope of the ‘y’ variable is bound by the existential quantifier at the middle. There is no free variable here in this sentence because both the variables x and y are bound by the scope of the two quantifiers, If we have a look at the following slightly different example, we would be able to see that the there is a free variable which is not bound by any quantifier. When there is a free variable, we can assign that variable with any value we like since it is not bound by the scope of the quantifiers in use. This is useful in the reasoning of the knowledgebase with different reasoning methods which we would look at later in the articles to follow during the next months.
x. Q(y) ^ $y(P(x) V Q(y)) – Here you can see that the variable ‘y’ appearing for predicate Q at the start is not bound by any quantifier because it is out of the scope of such and thus ne considered as a ‘free variable’.
Semantics of FOL
As we already know from the previous article about propositional logic, what ‘Semantics’ mean of a language, let’s quickly recap what it is again. Semantics describe the meaning of the sentences. After we express knowledge in based on the syntax of the language, the sentences that we constructed have to be meaningful in terms of providing useful information. The semantics describe such meaning of those expressions.
Based on the logical and non logical symbols which are shown in the FOL statement, we arrive at its meaning. Since the non logical symbols are application/domain dependent we cannot specifically arrive at hard and fast rules for the meanings across all domain. Instead, what we do it based on the non-logical symbols such as predicates and function symbols introduced for a certain domain, we arrive at meaning for those FOL statements which only apply to that domain.
For example the following FOL statements mean in terms of explaining family relationships:-
brotherOf (tom, jane) – Tom is the brother of Jane
Female(jane) – means Jane is a female
Male(tom) – Tom is a male
x. Boy(x) à Person(x) ^ Male(x) – This means for all the constants which can be substituted for variable ‘x’ a boy is a person who is a male.
Now based on the above syntax and semantics if the language we can represent the knowledge according to FOL. Further how do we know what is true and what is false. Every sentence that is expressed as a FOL statement in the knowledgebase is considered as true. Al so remember that, all the things which are not expressed and defined in the knowledgebase are considered false when we are trying to reason using this knowledge. For example, assume that we have been given the following knowledgebase describing about some sports preferences of some students which is represented in FOL.
From the above we can conclude based on the semantics, that the following are true.
Peter is a boy
Susan is not a boy
Peter plays Soccer
Susan plays Tennis
All the other things (although we know by common sense can be true) which are shown as below are considered false, because they have not been explicitly defined in the knowledgebase. The knowledgebase only knows the facts that we have clearly expressed in terms of the FOL statements and hence anything else is considered as false.
Susan is a girl
Peter also plays tennis
Let’s also look at constructing more complex sentences with the use of FOL for a domain considered as a school
“All the students in school ‘ABC’ are boys” (‘ABC’ is a boys’ school)
- x. StudentOf(‘ABC’,x) -> Boy(x)
§ This shows that using the predicate ‘StudentOf’ we are specifying the relationship between the school and the students and the first argument given as ‘ABC’ shows that we are talking about students of school specifically named as ‘ABC’.
Or without going in to details we can specify it simply with a single predicate as BoysSchool(‘ABC’). But the problem here is there is no mentioning about the characteristics/definitions about the students of the school which we might need in the other statements about the school.
- “Some students of ‘ABC’ who are good in studies(intelligent) are also good in sporty
y. StudentOf(‘ABC’,y) ^ Intelligent(y) -> Sporty(y)
See the difference here. Since only some of the students are good in both studies and sports we use the quantifier ‘There exists some’
Likewise, you can define any domain you like and try to express those in FOL using the logical and non logical symbols explained in this article as way of practicing and getting used to these syntax and semantics.
FOL vs. Propositional Logic
Now let’s have glance as to what are the main differences between Propositional Logic which we learnt in the previous two articles and FOL which we learnt today. It can be seen that the FOL is way better than propositional logic to express complex domains in a much easier and effective way. This is made possible with the introduction of predicates and function symbols which can have any number of arguments as required depending on the domain/application and also with the availability of quantifiers and other added logical symbols. The following table provides a descriptive explanation of the differences between these two methods of knowledge representation we have learnt so far.
Something to look forward to
Today, we looked at FOL and its basics with respect to introduction, syntax, semantics, scope of quantifiers, representing statements in FOL and comparison with propositional logic. These provide the building blocks of understanding how to express knowledge with the using FOL, which is extremely important to know and master as a person interested in AI, because the concepts of FOL and knowledge representation is widely used across domains in real world applications as well as in theory which is vital to understand more complex reasoning and representation methods. Next time, we would be going in to more advanced topics in FOL such as interpretations, reasoning and resolution which are significant concepts and processes that one must understand with respect to the area of knowledge representation and reasoning.
Artificial Intelligence – A modern Approach, Second edition, Stuart Russell&Peter Noving
>Knowledge Representation&Reasoning – Ronald Brachman&Hector Levesque