Mail


Shortcuts For Experts

Intro
RDBMS/XML
FOL
Frames
Description Logics
A.I.
RDF
UMLS
Google
Conclusion



Automated Reasoning with First Order Logic

A legitimate question that might be asked at this point in the tutorial is "Why is it that we are so concerned with reasoning and logic when all we really want to do is represent information?" Clearly, if we wanted to create some kind Artificially Intelligent computer program, it is clear that the ability to reason with first order logic would be a useful ability to possess. But to simply describe things to our computer, does the computer really have to be able to think in the same way? Sadly, the answer appears to be yes: Creating a useful description of knowledge requires us to slice and dice the knowledge in many different ways and to shuffle objects into different sets based on required and sufficient facts that define these sets.



So how do we go about doing such reasoning in First Order Logic?

The process we'll follow to reason with First Order Logic is simple: First, we'll build a database of facts- Then, we'll want to know whether a new fact has to be true based on the database. However, instead of using the term true we're going to use the word entails. When a fact is entailed by a database, it means that no matter what our interpretation was the new fact has to be true if all the other facts are true. The process of determinig whether a new fact is entailed by a database is called resolution

To get a feel for how a computer could go about performing resolution in an automated way, let's limit ourselves to only and, or, and not and unary predicates (predicate functions that only have one parameter). In this limited subset of first order logic, resolution can be performed in a few simple steps:
  1. Take the statement we want to test against the database and add the opposite to the database (i.e. add the statement to the database with a not in front of it). If our statement was initially true, we should now be able to show that the resulting database is impossible with this new negative statement.

  2. Move all nots inward as far as you can using the following rules: 
    (not (or A B))  --> (and (not A) (not B))
(not (and A B)) --> (or (not A) (not B))
    (cancel out any double negatives that crop up in the process, too)

  3. Move all ors in as far as you can using the following rules: 
    (or A (and B C)) --> 
(and (A or B) (A or C))
(or (and B C) A) --> 
(and (A or B) (A or C))
  4. All ands should now be the outermost connectives- Get rid of them by just making separate statements: 
    (and A B) --> A, B
  5. Add new facts to the database with the following rule: 
    (or A X ...) (or (not A) Y ...)
 --> (or X ... Y ...)
    What we are saying here is that if there are two different statements in the database which or together items and share a common element that is flipped in one of the two statements, then we can take out the shared parts and combine the two statements to create a new statement.

  6. If no new statements were possible in step 4, then we're stuck and this means we are unable to show that our database is impossible, hence the original statement (before negation) cannot be proven true and the resolution process is complete.

  7. Once we have two statements, A and (not A) that both are supposed to be true, it is impossible to have a consistent database, no matter what interpretation we are using. This means that the database is impossible to satisfy... meaning that the original statement (before it was negated) must have been true and the resolution process is complete.

  8. If neither of the last two steps applied, loop back to step 5.

OK, now let's look at an example we can solve:

The Henderson's neighbor keeps complaining about Jim's loud guitar playing. If Jim has a loud guitar then it is impossible for the neighbor to be happy, so having both a happy neighbor and a loud guitar is impossible:

(not (and (loud guitar) (happy neighbor)))
However, we want Jim to be able to play his guitar- If he has either headphones or a guitar amp he can do that: (Note how we can phrase an if-then using only and/or/not)
(or (and (or (owned_by_jim headphones) (owned_by_jim guitar_amp)) (can_play_guitar jim)) (not (can_play_guitar jim)))
If Jim has an amplifier, he will play his guitar loud:
(or (loud guitar) (not (owned_by_jim guitar_amp)))
The Hendersons know that having a happy neighbor and having jim play guitar are a must, so we'll just state this as a fact in our hypothetical database:
(and (happy neighbor) (can_play_guitar jim))
OK, our database of knowledge is done. Now we might be wondering... does our database also imply the following fact:
(and (owned_by_jim headphones) (not (owned_by_jim guitar_amp)))
In other words, we want to know that in a universe where the neighbor is happy and jim can still play his guitar this is only possible if jim has a pair of headphones and we take away his guitar amp. Let's run through the automated steps of resolution to find out the answer.




For step 1, we need to negate our statement to be tested and add it to the database. Our database is now: 

(not (and (loud guitar) (happy neighbor)))
(or (and (or (owned_by_jim headphones) (owned_by_jim guitar_amp)) (can_play_guitar jim)) (not (can_play_guitar jim)))
(or (loud guitar) (not (owned_by_jim guitar_amp)))
(and (happy neighbor) (can_play_guitar jim))
(not (and (owned_by_jim headphones) (not (owned_by_jim guitar_amp))))
For step 2, we need to move our nots inward: 

(or (not (loud guitar)) (not (happy neighbor)))
(or (and (or (owned_by_jim headphones) (owned_by_jim guitar_amp)) (can_play_guitar jim)) (not (can_play_guitar jim)))
(or (loud guitar) (not (owned_by_jim guitar_amp)))
(and (happy neighbor) (can_play_guitar jim))
(or (not (owned_by_jim headphones)) (owned_by_jim guitar_amp))
For step 3, we need to move in our ors: (note that we removed (or (can_play_guitar jim) (not (can_play_guitar jim))) for obvious reasons) 

(or (not (loud guitar)) (not (happy neighbor)))
(or (owned_by_jim headphones) (owned_by_jim guitar_amp) (not (can_play_guitar jim)))
(or (loud guitar) (not (owned_by_jim guitar_amp)))
(and (happy neighbor) (can_play_guitar jim))
(or (not (owned_by_jim headphones)) (owned_by_jim guitar_amp))
For step 4, we can get rid of ands: 

(or (not (loud guitar)) (not (happy neighbor)))
(or (owned_by_jim headphones) (owned_by_jim guitar_amp) (not (can_play_guitar jim)))
(or (loud guitar) (not (owned_by_jim guitar_amp)))
(happy neighbor)
(can_play_guitar jim)
(or (not (owned_by_jim headphones)) (owned_by_jim guitar_amp))
For step 5, we can add the following new facts to our database 

Combining statement 1 and 3: (or (not (happy neighbor)) (not (owned_by_jim guitar_amp)))
Combining statement 1 and 4 - the or on #4 is implied: (removed superfluous or): (not (loud guitar))
Combining statement 2 and 3: (or (owned_by_jim headphones) (not (can_play_guitar jim)) (loud guitar))
Combining statement 2 and 5: (or (owned_by_jim headphones) (owned_by_jim guitar_amp))
Combining statement 2 and 6: (or (owned_by_jim guitar_amp) (not (can_play_guitar jim)))
Combining statement 3 and 6: (or (loud guitar) (not (owned_by_jim headphones)))
Step 6 doesn't apply, since we're not stuck yet

Step 7 doesn't apply, since there's no contradiction yet

For Step 8, we'll loop back to to step 2. Our current database looks as follows:


(or (not (loud guitar)) (not (happy neighbor)))
(or (owned_by_jim headphones) (owned_by_jim guitar_amp) (not (can_play_guitar jim)))
(or (loud guitar) (not (owned_by_jim guitar_amp)))
(happy neighbor)
(can_play_guitar jim)
(or (not (owned_by_jim headphones)) (owned_by_jim guitar_amp))
(or (not (happy neighbor)) (not (owned_by_jim guitar_amp)))
(not (loud guitar))
(or (owned_by_jim headphones) (not (can_play_guitar jim)) (loud guitar))
(or (owned_by_jim headphones) (owned_by_jim guitar_amp))
(or (owned_by_jim guitar_amp) (not (can_play_guitar jim)))
(or (loud guitar) (not (owned_by_jim headphones)))
For Step 5, we can add the following new facts to our database: 

Combining statement 2 and 3: (or (owned_by_jim headphones) (not (can_play_guitar jim)) (loud guitar))
Combining statement 2 and 7: (or (owned_by_jim headphones) (not (can_play_guitar jim)) (not (happy neighbor)))
Combining statement 3 and 8: (not (owned_by_jim guitar_amp))
Combining statement 3 and 10: (or (loud guitar) (owned_by_jim headphones))
Combining statement 3 and 11: (or (loud guitar) (not (can_play_guitar jim)))
Combining statement 5 and 9: (or (owned_by_jim headphones) (loud guitar))
Combining statement 5 and 11: (owned_by_jim guitar_amp)
Combining statement 6 and 7: (or (not (owned_by_jim headphones)) (not (happy neighbor)))
Combining statement 6 and 8: (or (owned_by_jim guitar_amp) (not (can_play_guitar jim)) (loud guitar))
Combining statement 7 and 11: (or (not (happy neighbor)) (not (can_play_guitar jim)))
Combining statement 8 and 12: (not (owned_by_jim headphones))
Combining statement 9 and 12: (or (not (can_play_guitar jim)) (loud guitar))
Combining statement 10 and 12: (or (owned_by_jim guitar_amp) (loud guitar))
Now, for step 6, we want to check if there are any opposing statements like A and (not A). Let's look at our database so far: 

(or (not (loud guitar)) (not (happy neighbor)))
(or (owned_by_jim headphones) (owned_by_jim guitar_amp) (not (can_play_guitar jim)))
(or (loud guitar) (not (owned_by_jim guitar_amp)))
(happy neighbor)
(can_play_guitar jim)
(or (not (owned_by_jim headphones)) (owned_by_jim guitar_amp))
(or (not (happy neighbor)) (not (owned_by_jim guitar_amp)))
(not (loud guitar))
(or (owned_by_jim headphones) (not (can_play_guitar jim)) (loud guitar))
(or (owned_by_jim headphones) (owned_by_jim guitar_amp))
(or (owned_by_jim guitar_amp) (not (can_play_guitar jim)))
(or (loud guitar) (not (owned_by_jim headphones)))
(or (owned_by_jim headphones) (not (can_play_guitar jim)) (loud guitar))
(or (owned_by_jim headphones) (not (can_play_guitar jim)) (not (happy neighbor)))
(not (owned_by_jim guitar_amp))
(or (loud guitar) (owned_by_jim headphones))
(or (loud guitar) (not (can_play_guitar jim)))
(or (owned_by_jim headphones) (loud guitar))
(owned_by_jim guitar_amp)
(or (not (owned_by_jim headphones)) (not (happy neighbor)))
(or (owned_by_jim guitar_amp) (not (can_play_guitar jim)) (loud guitar))
(or (not (happy neighbor)) (not (can_play_guitar jim)))
(not (owned_by_jim headphones))
(or (not (can_play_guitar jim)) (loud guitar))
(or (owned_by_jim guitar_amp) (loud guitar))
And, indeed, there are contradictory statements: 

(owned_by_jim guitar_amp)
(not (owned_by_jim guitar_amp))
What can we deduce from this? We can state that our database is not satisfiable, meaning that no mater what our interpretation is, we will never be able to satisfy all the statements in our database. This happened because we added the statement (not (and (owned_by_jim headphones) (not (owned_by_jim guitar_amp)))), which made the database inconsistent (we could have used the same algorithm to show that the database was consistent before this additional statement). That means that the opposite of the statement, (and (owned_by_jim headphones) (not (owned_by_jim guitar_amp))), is a piece of knowledge that has to be true, given the remainder of the database.

Conclusions About First Order Logic

From this little exercise we can conclude a few different things:
  1. It is relatively straight-forward to create a resolution algorithm for a limited form of first order logic. It is known that algorithm will always give a yes or no result in a finite amount of time.
  2. The size of the database quickly balloons out of control- Notice how the database roughly doubled in size every time we went through the loop. In fact, in the worst case, it is known to grow exponentially, which is very bad for resolution in larger databases.

In fact, it is not too difficult to expand the algorithm to work with the rest of the first order logic vocabulary (all, exists, higher order predicates, etc.). Unfortunately, a more complex algorithm can get caught in infinite loops that are known to be impossible to guard against completely. (to be more precise, it is NP complete) However, with some clever tricks, it is possible to create a resolution algorithm that works well enough for most cases and allows first order logic to be a practical tool for representing knowledge.

Clearly, first order logic is a very powerful and fundamentally simple system for representing knowledge- But we can use other approaches that have some advantages over first order logic and are particularly well suited for representing knowledge- We will be discussing these in the section "Making Knowledge Representation Easier". However, first we're going to make a short detour and look at how knowledge is represented in common computer software in order to learn about the limitations of knowledge in those types of systems...


Making Knowledge Representation Easier >>