From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Mon Feb 25 08:36:37 2008
Date:         Mon, 25 Feb 2008 08:36:14 -0500
From: "William J. Rapaport" <rapaport@cse.Buffalo.EDU>
Subject: 191:  Application of Predicate Logic to AI
To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU

------------------------------------------------------------------------
Subject: 191:  Application of Predicate Logic to AI
------------------------------------------------------------------------

Several of you have asked for examples of applications of discrete math
to computer science.  Here's an application of predicate logic to
artificial intelligence (AI).

In the late 1950s, one of the founders of AI, John McCarthy, proposed a
computer program to be called "the advice taker", as part of a project
that he called "programs with common sense".  (This is a project that he
is still working on, by the way!)

(McCarthy is famous for at least the following things:  He came up with
the name "artificial intelligence", he invented the programming language
Lisp, and he invented time sharing.  For more information on him, link
to our "Logic" webpage at:

	http://www.cse.buffalo.edu/~rapaport/191/S08/logic.html

Then scroll down to "John McCarthy's research on knowledge
representation using FOL:" and click on his name.)

The idea behind the advice taker was that problems to be solved would be
expressed in a predicate-logic language (only a little bit more
expressive than FOPL), a set of premises or assumptions describing
required background information would be given, and then the problem
would be solved by logically deducing it from the assumptions.

He gave an example:  getting from his desk at home to the airport.  
It begins with premises like

	at(I,desk)

meaning "I am at my desk", and rules like 

	AxAyAz[at(x,y) ^ at(y,z) -> at(x,z)]

which expresses the transitivity of the "at" predicate, and slightly more
complicated rules (which go slightly beyond the expressive power of
FOPL) like:

	AxAyAz[walkable(x) ^ at(y,x) ^ at(z,x) ^ at(I,y) ->
		can(I, go(y,z,walking))]

i.e., if x is walkable, and y and z are at x, and I am at y,
      then I can go from y to z by walking.

The proposition to be proved from these (plus lots of others) is:

	want(at(I,airport))

To see it all worked out, take a look at his article:

McCarthy, John (1959),  "Programs with Common Sense", in D.V. Blake &
A.M. Uttley (eds.), Proceedings of the ["Teddington"] Symposium on
Mechanisation of Thought Processes  (London: HM Stationary Office).

There's a link to an online version at our Logic webpage:
http://www.cse.buffalo.edu/~rapaport/191/S08/logic.html