25 Using Predicate logic

Bhushan Trivedi

Introduction

In this module we will see how one can use predicate logic for representing statements and infer from them. We will see some issues related to reference using examples. We will reemphasise an important issue of common sense knowledge in due course. Variable binding is an important issue while backward chaining; the process for generating proof using predicate logic. When statements contains universal and existential quantifiers we need to handle them with special care, which we will see in this module as well. The predicate that we want to prove needs to match with predicate which is part of premise. The process of matching is not straight forward. It requires variable binding which is consistent and do not alter the truthfulness. That process is known as Unification. We will see how Unification process works at the end of this module.

The impact of universal and existential quantifiers

Let us elaborate the process of inference using predicate logic in light of existential and universal quantifier using an example.

Here is a set of statements known to be true. Ex. 25.1

1. Ramji is a man.

2. Ramji is a farmer

3. All Kuchchhis are Gujaratis

4. Ramji belongs to Bhachau.

5. All people of Bhachau lost their houses during the earthquake in 2000

6. Government provided relief to all those who lost their houses during the earthquake. Can we prove using backward reasoning, that Ramji received the government relief? Let us try to represent these statements and answer questions.

1. Man (Ramji)

2. Farmer(Ramji)

3. ∀??Kuchchhi(X) →Gujrati (X)

4. Belongto (Ramji, Bhachau)

5. ∀??∃??Person(X) ⋀Belongsto (X,Bhachau) ⋀House (H,X) →Lost (X,H,2000)

6. ∀??∃??Person(X) ⋀House (H,X) ⋀Lost (X,H,2000) →Relief (Government, X)

Let us try to understand our representation. First is about Ramji is a man. We will forgo the present tense indication and represent the statement in a simpler form. Same with Ramji being a farmer. Every Kutchchhi is a Gujarati is represented using the variable X and a universal quantifier. For Ramji belong to Bhachau, we have used the simpler representation like previous module. In 5 and 6 we have used universal quantifiers to represent variable’s scope. We have ignored the mention of the earthquake in the representation. Somebody who looked at the representation only understands that those who belong to Bhachau host their house in 2000. If there is a query about the reason, we may not be in a position to answer. Look at the representation of the predicate ‘Lost’. The third argument indicates the time when the house was lost. The 6th  statement is about relief of the government received by people who lost their houses. Now let us represent the statement that we want to prove first. We want to prove that Ramji has received the government relief. Let us use backward chaining. Now we will use a common notation to represent a replacement of a variable by a value as Variable/Value as X/Ramji in this example.

Relief (Government, Ramji)

← ∃??Person (Ramji) ⋀ House (H,Ramji) ⋀ Lost (Ramji, H, 2000) //using 6, X/Ramji

← ∃??Person(Ramji) ⋀House (H,Ramji) ⋀ Person(Ramji) ⋀Belongsto (Ramji,Bhachau) ⋀House   (H,Ramji)     //  using 5, X/Ramji

←∃??Person(Ramji) ⋀House (H,Ramji) ⋀Belongsto (Ramji,Bhachau)

// using X ⋀ X = X

← ∃??Person(Ramji)           ⋀House           (H,Ramji)                                // using 4

Now we stuck as these two things are not possible to be proven using existing predicates.  The first one is again an issue of common sense. We want Ramji to be a person (male or female) and we have Ramji is a Man (male). It is obvious that all man are person but that is to be added to database explicitly. Let us do so.

7.  ∀??Man (X) → Person(X)

Now we can proceed further

←∃??Man (Ramji)⋀House (H,Ramji)                         // using 4 x/Ramji

←∃??House (H,Ramji)

Now we stuck again. Why we stuck? What is the reason that we cannot move forward to proof? It is an important issue, let us elaborate.

Incomplete information

If you probe deeper you may find that we have no evidence of Ramji owned a house in 2000. We do not have a premise which says so. This is not a common sense case. This is a case of incomplete information. We cannot prove that Ramji has received compensation unless we can prove that he owned a house before 2000 in Bhachau.

Let us assume that Ramji owned a house in Bhachau at the time of earthquake. That means We have to add following statement in our database.

8.  ∃??House (H,Ramji)

Once above statement is added, we have no predicate left to be proven so, we achieves the proof.

←<true>       // using 8

This is not a simple case. Ramji may not own a house or may own a house in some other city, we do not know. Ramji may own a house in Bhachau but may be AFTER 2000. We ignore all such possibilities for simple representation here. Unless we have information it is hard to prove that he owns a house. So we just assume that.

Answering a question

Question answering is another important capability of predicate logic representation. Obviously the questions are confined to Yes/No type or a single term, which is quite similar to proving something. Let us see how a question can be answered in predicate logic.

Can we answer a question, whether Ramji is Gujrati or not?

Again, we will do a simple backward chaining and start. Let us try to prove Ramji is Gujarati, if we cannot prove, we may try opposite predicate later.

Gujarati(Ramji)

←Kachchhi(Ramji)           // X= Ramji and 3

We again stuck here and need to add

All who belong to Bhachau are Kachchhi.

9.  ∀??Belongsto(X,Bhachau) →Kachchhi(X)

← Belongsto (Ramji, Bhachau)         // from 9 and X=Ramji

←<true>      // from 4

Here is one more example which clearly indicates missing information as the question presenter has omitted due to obvious reasons. Bhacahu is a village of Kuchchhwhich was assumed to be known by the presenter.

What if we could not prove above? We need to again start with ¬Gujarati(Ramji).  If can prove it, fine. What if we cannot prove? In fact you may ask a question, when we cannot prove him to be a Gujarati, isn’t that obvious that he is not? Why we need proof for not being Gujrati? Also; what is the meaning if neither is provable? If neither is provable, we can only say that we are unsure. The predicate logic is dealing with limited and not complete data and thus all three results, true, false and unsure about the truthfulness are possible.

Using functions

Predicate logic is not only about adding predicates which are true or false. We also need functions to calculate and find out if something is true or not. A single function can serve the purpose of many predicates, in some cases infinite predicates. For example we can have a function Greater(X, Y) which returns true of X is greater than Y. We can continue adding facts about numbers or strings (while we are checking if a string is greater than another, we consider lexicographical order which is observed in library, thus amar comes before azad which in turn comes before babu. ) to replace such function and we get infinite such predicates like Greater(Amar, Azad), Greater (Azad, Babu) and so on…

Let us take another example to see how we can use functions to determine something. Let us have following details.

Ex. 25.2

1. Ramji is a man.

2. Ramji is a farmer

3. Ramji belongs to Bhachau.

4. All people of Bhachau lost their houses during the earthquake in 2000

5. Government provided relief to all those who lost their home during the earthquake.

6. Ramji has not changed his house from 2003 till now.

Now Government asks for a proof that Ramji was living in the new house in 2010 to release another grant. Can we do that? Let us first of all build the predicate logic representation.

1. Man (Ramji)

2. Farmer(Ramji)

3. Belongsto (Ramji, Bhachau)

4. ∀??∃??Person(X) ⋀Belongsto (X,Bhachau) ⋀House (H,X) → Lost (X,H,2000)

5. ∀??∃??Person(X) ⋀House (H,X) ⋀Lost (X,H,2000) → Relief (Government, X)

6. ∃??BuildHouse (H, Ramji, 2003)⋀ ¬ Changedhouse(Ramji,H,2015)

It is giventhat Ramji built a new house in 2003 with government relief. How can we also prove that he was living in the new house in 2010, wherewe have the fact known that he is living in the same house now and not changed house since 2003? We will have to prove that

if one starts living in a new house, and he has not changed his house thereafter, he was leaving in that house at any point of time in between.

That means, he is living in the house in 2015 and he started living in the house from 2003, we can also prove that he was living in the same house in 2010. You can easily understand that this is a type of problem we encounter many times. We need to have a function called between(X,Y,Z) where if X belongs to the range between Y and Z, the function returns true. Thus that simple function can serve the purpose of many predicates. The statement is represented as follows.

7.  ∀??∀??1∀??2∀??3∃??Buildhouse(H,X,T1)⋀ ¬ Changedhouse(X,H,T2)   ⋀   Between(T3,T1,T2)

→Liveinhouse(H,X,T3)

Using above predicate, we can prove Ramji is living in new house not only in 2015 but in 2010 as well as any other year falling between 2003 and 2015. Now, for Ramji to have another round of relief, we will have to prove that Ramji was living in the new house in 2010. Thus we want to prove that

∃??Buildhouse(H, Ramji,2003)⋀Liveinhouse(H,Ramji,2010)

Why we also need to provide another predicate with Liveinhouse? Because we have a relation of Ramji with house using an existential quantifier, we do not have that statement true for all houses. It is true for a single one which we indicate as H. We are not worrying about the value of H in this case. We are worrying about the same variable value being used in Liveinhouse. Though it is not stated, we need to prove that Ramji is living in the same house as in 2003. That is enforced by using the same variable value H1 in both predicates to be proved.

∃??Buildhouse(H, Ramji,2003)⋀Liveinhouse(H,Ramji,2010)

←∀??1∀??2∀??3∃??Buildhouse(H,                               Ramji,2003)⋀Buildhouse(H,                              Ramji

,T1)⋀¬ Changedhouse(Ramji,H,T2) ⋀ Between(2010,T1,T2)                                      // 7, T3 = 2010

←∀??2Buildhouse(H1, Ramji,2003)⋀Buildhouse(H1, Ramji ,2003)⋀¬ Changedhouse(Ramji,H1,T2) ⋀

Between(2010,2003,T2)          // T1=2003 ∃??(H) / H1

In above case we have removed existential quantifier by replacing the value of the variable by a constant H1. H1 is also known as skolem constant. The process is known as skolamization which makes more sense when we use another method to prove called resolution.Another important point before we proceed further.

We have two predicates, both with predicate name Buildhouse and with 3 argument. We can eliminate them by a process call unification. This process makes sure that the variable values are assigned in a consistent way.

Thus we will have to unify BuildHouse (H1, Ramji, 2003)and BuildHouse (H1, Ramji, T1). We need to replace T1 by 2003 to make both of them look alike. Once we do that, it is also an important condition for unification that all instances of T1 are also provided with the same value. A variable must be assigned consistent values across the expression. You can see the need of such requirement, we have one fact telling Ramji has built a house in 2003 and another saying he did so in T1, obviously T1 is 2003. In fact it is quite possible for Ramji to build multiple houses at different times, in which case, we will have to unify this predicate with all such instances one after another and see if we get it through. For simplicity, we will also omit that possibility here.

An interesting point is to make sure all instances of T1 must be assigned the value when one of them is assigned. You can also see that it is true for consistency. When we say that for some time T1, this statement is true, and provide a value, it means that for that value T1 the entire statement is true and not a part of it. That means that our between function must have the second argument as 2003.

←Buildhouse(H1, Ramji,2003)⋀¬ Changedhouse(Ramji,H1,T2) ⋀ Between(2010,2003,T2)

← ¬ Changedhouse(Ramji,H1,T2) ⋀ Between(2010,2003,T2)       // 6

← ¬ Changedhouse(Ramji,H1,2015) ⋀ Between(2010,2003,2015) //T2=2015

←Between(2010,2003,2015)                                                               // Between is called here

←<true>

You probably get the idea that using predicate logic for representation of facts and reasoning is harder than it appears at the first sight. This is the fact true for almost all AI problems that we have encountered so far.

Rules that do not work

There are a few problems with predicate logic though. Sometimes, we have rules which are true but create issues. Let us try to understand.

Ex. 25.4

1. Brother (Mohinder, Surinder)

2. Brother (Steve, Mark)

3. Brother (Ram, Laxman)

4. Brother (Krishna, Balram)

This example seems to be quite simple. As long as the query remains as one of the four cases described in above ex 25.4, for example if there is a query Brother (Steve, Mark) we can easily prove it.

This representation is also quite good if we provide an incorrect input, for example Brother (Ram, Ravan). That will not unify with any of the four cases and thus we can at least prove that as per the database, this information is incorrect.

Now if we have a query, prove Surinder is Mohinder’s brother,or Brother (Surinder, Mohinder). Can we? We can prove Brother (Mohinder, Surinder) as it is there in the database but how about other way round?

There are two ways to solve this problem. First, by adding another fact

5.  Brother (Surinder, Mohinder) Or,add another rule

6.  ∀??∀??Brother (X,Y ) →Brother (Y,X)

We  can clearly  say  that the  rule  is  a better  solution  as otherwise we need to  add  four more predicates. The process may become more complicated if we accept the fact that Ram has three brothers. We need to provide total nine predicates to cover all possibilities if we have to provide information about brothers other than Laxman as well. Obviously the problem can be solved in a far simpler manner if we add a rule and no other predicates.

Now when we provide the query, Brother (Surinder, Mohinder)

←Brother (Mohinder, Surinder)                              // X= Surinder, Y=Mohinder, 5

←<true>

Can you see the problem in above representation? In 2.4, when we provided an incorrect fact as a query to prove, as we cannot proceed further, we could conclude that the query is not possible to be satisfied. Can we do the same for the newer representation with the additional rule? Let us see.

We present a query Brother (Ram, Ravan) Brother (Ram, Ravan)

←Brother (Ravan, Ram)               //5 X=Ram, Y=Ravan

←Brother (Ram, Ravan)               //5 X=Ravan, Y=Ram

….

Now we may continue forever without really proving or disproving what we set out to. Based on what we have seen so far we must state two things.

First, whatever we prove or disprove is based on current knowledge we have and thus it is always confined to what we know till date. We assume a fact to be untrue when we cannot prove it using our current database, which might be true looking at overall context.

Second, predicate logic does not guarantee that the backword chaining process might stop if the predicate to be proven is not possible to be either proved or disproved using the existing database.Having said that, we have a little better way to represent the predicates in this particular case. We might not be in a position to do so in all such cases.We will define a new predicate Brotherof now. We will be in a position to avoid the recursion like situation which we encountered in the previous case.

5.       ∀??∀??Brotherof(X, Y) →Brother (X,Y)

6.       ∀??∀??Brotherof(X, Y) →Brother (Y, X)

Now the query form is also changed. Instead of Brother, the query will have Brotherof.

So if we have query Brotherof(Mohinder, Surinder)

←Brother(Mohinder, Surinder)                          // X= Mohinder Y=Surinder and 5

←<true>

Or if we have query Brotherof(Surinder, Mohinder)

←Brother(Mohinder, Surinder)                 // X= Surinder, Y=Mohinder and 6

←<true>

So we can prove both cases. Let us take an incorrect query Brotherof (Ram, Ravan)

←Brother (Ram, Ravan)                   // X= Ram, Y = Ravan and 5

Now we cannot proceed further so take another route

←Brother (Ravan, Ram)                 // X= Ravan, Y= Ram and 6

And again we cannot proceed further. We are saved from recursively calling predicate brother like the previous example.

You can see that proving using predicate logic and backward chaining also involves a depth first search process. If there are multiple ways to prove a predicate, the system tries each one of them systematically in depth first way, picking up the first one defined to last one in turn.

Before we conclude, let us discuss about unification process a bit.

Unification process

When we have two predicates, we need to make sure that they match exactly for removing during our process of backward chaining. We have done that a few times during our process of proving statements. However simple it looks like, it is a complex process. Let us briefly study how unification help in matching.

Let us take the example of two statements

1. Man (Ramji)

2. ∀??Man (X) → person (X)

When we want to prove that Ramji is person, we unify both predicates with replacing X/Ramji.

Sounds straightforward, isn’t it? It is not always so.

1.  Man (Ramji)

2. ∃??Man (X) → singer (X)

Can we unify X with Ramji to  prove that Ramji is a singer? No. Why? We have an existential quantifier here. The statement is not true for all, thus we cannot prove it to be true. Ramji may be a singer or may not be but the information that we have is not enough for us to prove that. In short Man (Ramji) and Man (X) can unify only if we can have X/Ramji and not otherwise.

Can Man (Ramji) be unified with Man (Ramji)? Yes, as both of the predicates are same as well as the arguments. We need to check both, the name of the predicate and set of arguments, which are same in both cases.

Another point. Can two statements, Man (Ramji) and Man (Pratap) be unified? Though the predicates are the same but the arguments aren’t. So No.

Can (Ramji) and Man (Ramji, Principles) be unified? No; as number of arguments of both predicates are different so they are different predicates and thus cannot be unified.

What about argumentswhich are variables and not constant?

We will confine our discussions to all variables which are universally quantified to simplify the discussion. We have already stated that existentially quantified variables cannot be unified with values unless we have the information that the value is indeed true for that variable.

Suppose we have following during our process of backward chaining. Can we unify them? Brother(X1, Y1) Brother (X2, Y2)

This can be possible with substitutions X1/X2 and Y1/Y2. Let us see how that is done using a very simple example.

Ex. 25.5

Suppose we have following facts and two rules and we need to unify 3 and 4

1.  Brother(Prakash, Ramchandra).

2. Parents(Prakash, Dipak, Madhuri).

3. ∀??∀??∀??∀??Brother (X, Y) and Parents(X, P, Q)→ Parents(Y, P, Q)

4. ∀??∀??∀??∀??Brother(X, Y) and GrandParents (X, A, B)→ Grandparents(Y, A, B)

Note: for simplicity we are considering only one grandparents, otherwise we need two grandparents

one for each parent.

The problem is that both predicates use similar variable names.  We will  have to change both statements.

3. ∀??1∀??1∀??∀??Brother (X1, Y1) and Parents(X, P, Q)→ Parents(Y, P, Q)

4. ∀??2∀??2∀??∀??Brother(X2, Y2) and GrandParents (X, A, B)→ Grandparents(Y, A, B)

Above example clearly indicates that substitute X1/X2 and Y1/Y2 can work in above example.

What if somehow we have two statements of following type?

Brother (X1, X2)

Brother (X2, X3)

This is really tricky. This can unify only if X1/X2 and X2/X3, applying both one after another. That means we first replace all instances of X1 by X2 and then all instances of X2 by X3, in a way, replacing all instances of X1 and X2 by X3, in short we yield

Brother(X3, X3).

What if we have one variable bound in one predicate and another is bound in other predicate? Brother (X, Mohinder)

Brother (Steve, Y)

These two predicates can unify if X/Steve and Y/Mohinder is possible.  Above both of above cases, the result is incorrect but unification is possible.

(Why above wrong results are produced? This is a common problem when an existential quantifier is incorrectly represented as universally quantified variable. In Brother (X,Mohinder) or Brother (Steve,Y) it means that everybody ‘s brother is Mohinder and Steve is everybody’s brother as the universally quantified variables represents a fact true for everybody who belong to that domain. We cannot say the same thing about Brother(X3,X3) (which is similar to Brother(X,X)) but most likely case is misrepresentation of an existentially qualified variable)

Let us take one more case.

Brother (X, Mohinder)

Brother (Steve, Mark)

Above two predicates cannot be unified because though we can have X/Steve, we cannot have Mark/Mohinder or vice versa.

Summary

In this module, we have seen how predicate logic is used to represent little more complex cases than what we have seen in the previous module. We have seen that a universally quantified variable can assume any value and thus a predicate with a universally quantified variable can match with any other predicate with constant arguments. We have also seen that many a times we have incomplete and seemingly obvious information which are omitted from description. Only when we start proving something we realize that it is missing and we need to add them. There are possibilities of having functions as part of the predicate which can help reduce number of predicates. Many times rules will force the backward chaining process to go in endless loop. Sometimes it is possible to refine the situation by writing rules in more clever way. The process which decides the variable binding during matching of predicates is called unification algorithm. The algorithm eventually decides the type of mapping from one variable to another variable or a constant to make sure it remains consistent and true.