CSE 250A Lecture Notes, February 9, 2001

CSE 250A LECTURE NOTES

February 9, 2001

ANNOUNCEMENTS

Remember that the second project report is due in a week. Be sure to learn from the first one. I'm available to discuss draft papers.

Sad news: Herb Simon, the most important founder of artificial intelligence, died today. He won the Turing award in 1975 and the Nobel prize in economics in 1978. He was born in 1916 and an active professor in many departments at Carnegie Mellon University from 1949 until today.

Today and next week we'll be talking about first-order logic. For a more formal presentation of this topic, the book Logic and Structure by Dirk Van Dalen, published by Springer, is especially recommended.

For an online reference, see the slides based on Chapter 4 of Logic for Mathematics and Computer Science by Stanley Burris, Prentice Hall, 1998, available here.

For the history of first-order logic and an overview of what research in mathematical logic is about, see the article on Formal Logic in the Encyclopedia Britannica.

KNOWLEDGE-BASED SYSTEMS

Many practical engineering successes of AI have come from knowledge-based systems (KBSs), which are also called expert systems. The latter name is less accurate because many KBSs do not perform at the level of a human expert, but are nonetheless useful.

A KBS is a software system that contains a great quantity of knowledge, e.g. facts like "CSE100 is a prerequisite for CSE151."

Nowadays, many KBSs are not identified as such to the user. As with other technologies inside and outside AI, the technology of KBSs has lost its magic and become routine. For an example of a very simple web-based expert system that is not identified as such, see the E-Loan mortgage recommender.

Typically KBSs do not contain all the knowledge that a human who is an expert in the same domain would possess. The varieties of knowledge that a human expert possesses can be classified as follows:

Explicit facts and rules stated declaratively.
Meta-level knowledge, including

Knowledge about missing knowledge, such as "The time and place of CSE100 is not known for 2000/2001."
Control knowledge, such as "Electives should be scheduled first, then required courses."

Commonsense knowledge, such as "A student cannot take two different courses in the same time slot."
Perceptual knowledge, such as what a faculty adviser's signature looks like.
Procedural knowledge, like how to make the strokes with a pen that constitute a signature.

A typical KBS contains a lot of declarative knowledge, very limited meta-level and commonsense knowledge, and no perceptual or procedural knowledge.

We shall talk about the practicalities of KBSs later. Our topic now will be the mathematical foundation of many KBSs, namely first-order logic, and how to use it to express factual knowledge explicitly.

A KBS uses reasoning algorithms to make deductions from its knowledge to solve a particular problem like "Which courses should Martha take this quarter?" We shall also study these algorithms.

The leading advocate of knowledge-based systems is Edward A. Feigenbaum, a professor at Stanford and Chief Scientist of the U.S. Air Force from 1994 to 1997. Feigenbaum was the 1994 winner of the Turing award.

THE PREDICATE CALCULUS

We shall study first one particular logic, called the predicate calculus and also first-order logic, which you should have seen in previous courses. This is a generalization of propositional calculus, which is occasionally called zero-order logic.

Remember that a proposition is a primitive sentence, i.e. a fact. In the predicate calculus propositions are "decomposed" into predicates and arguments.

A predicate is a relationship such as loves. An argument is an object such as a person. Objects are a primitive notion, in the same way that propositions are primitive in propositional logic. A constant is a name for an object, e.g. John.

So in predicate calculus a proposition might be loves(Mary,John) and a compound sentence might be loves(Mary,John) & loves(John,Mary)

Predicates allow us to talk about properties of single objects and relationships between two or more objects. A predicate applied to argument objects yields a truth value.

First-order logic does not allow us to state knowledge that is perceptual or procedural. It also cannot represent knowledge that is declarative but numerical, probabilistic, or tentative. We shall look at formalisms for these types of knowledge later.

VARIABLES AND QUANTIFIERS

A variable is a special identifier that stands for an arbitrary object. Variables are conventionally named x, y, z, etc.

Every variable is "universal" or "existential", meaning that it refers to all objects or at least one.

A quantifier is a symbol that introduces a variable and says whether it is universal or existential. The universal quantifier is an upside-down A, written "forall" in ascii. The existential quantifier is a backwards E, written "exists" in ascii.

Every variable in a sentence must be introduced by a quantifier. For example: forall x loves(Mary,x) says "for every semantic object, call it x, Mary loves x"

A more plausible sentence is forall x isacat(x) -> loves(Mary,x) which says "for every semantic object, call it x, if x is a cat then Mary loves x." The majority of universally quantified sentences that are true are implications.

CONSTANT-SYMBOLS AND FUNCTION-SYMBOLS

An object is a semantic entity. The name of an object is a syntactic entity. Technically, "Mary" is a name that designates an object.

A "term" is any syntactic expression that designates an object. As a name, we say that "Mary" is a primitive term, i.e. a constant-symbol. Compound terms are made up of function-symbols applied to constant-symbols, e.g. "father(Mary)".

The function-symbol "father" is the name of a function that maps semantic objects to semantic objects.

A function maps a fixed number of objects to another object. For example, + is a binary function: it maps two objects to one object.

A predicate maps a fixed number of objects to a truth value (true or false).

SEMANTICS OF FIRST-ORDER LOGIC

The syntax of a logic specifies what the correct "well-formed" sentences are in the logic. Syntax can be given by a grammar. The semantics of a logic specifies how the "meaning" of a sentence is built up from the meanings of its parts.

We covered the following notions:

universe: any non-empty set, typically named U
meaning of a constant-symbol: an element of the universe
meaning of a unary predicate-symbol: a subset of the universe
meaning of a k-ary predicate-symbol: a subset of the Cartesian product U^k = U x ... x U
meaning of a function-symbol: a mapping from U^k to U