Objectives
To learn about applications of logic in AI, and some of its limitations.
Module Description
This module describes several applications of logic in
AI.
Part 1 deals with Modal Logic, an extension of propositional logic in which two extra connectives are introduced. The extra connectives can have several meanings (according to the particular modal logic at hand), including necessity and possibility; knowledge; belief; obligation and permission.
We look at applications to knowledge in multi-agent environments. An agent in a group must take into account not only facts true in the world, but also the knowledge held by other agents in the group. For example, in a bargaining situation, the seller of a car must consider what a buyer knows about the car's value. The buyer must also consider what the seller knows about what the buyer knows about the value, and so on. The logic of knowledge allows us to express these sentences.
Example: There are three wise men. It's common knowledge among them that there are three red hats and two white hats. The king puts a hat on each of the wise men. Each man can see the other two hats, but not his own. The king asks them sequentially if they know the colour of their own hat. The first man says he does not know; the second says he does not know. When the third man is asked, he announces that he does know. What colour is the third man's hat?Part 2 of the module deals with how default information can be handled in logic. This is information which is generally true, but known to have exceptions; for example, "Generally, birds can fly". (Here, exceptions include penguins, sick birds, etc.) The technique for handling defaults in predicate logic is known as circumscription. An example of the sort of inference we would like to be able to make is:
Premises:If you try coding this in predicate logic, you'll find that the premises are contradictory, so any conclusion can be deduced. Circumscription avoids this problem.
Generally, birds can fly.
Generally, penguins cannot fly.
All penguins are birds.
R is a bird.
S is a penguin.Conclusions:
R can fly.
S cannot fly
Key Texts
R. Fagin, J. Halpern, Y. Moses and M. Vardi, Reasoning about
knowledge, MIT Press, 1995.
S. Russell and P. Norvig, Artificial Intelligence: a Modern
Approach, Prentice Hall, 1995