CSE 150 Lecture Notes, January 29, 2004

CSE 150 LECTURE NOTES

Janury 29, 2004

ANNOUNCEMENTS

Today and next week we'll be talking about first-order logic. This subject may seem dry and pedantic, but it is important and fascinating once you understand it.

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 KBSs never perform as flexibly as a human expert, but they 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." The system uses reasoning algorithms to make deductions from its knowledge to solve a particular problem like "Which courses should Martha take this quarter?"

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.
Numerical and mathematicak knowledge.
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 numerical, meta-level and commonsense knowledge, and no perceptual or procedural knowledge.

We shall talk about reasoning algorithms, and 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.

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.

LOGICS FOR KNOWLEDGE REPRESENTATION

Our topic is how to state knowledge explicitly, and soon, how to draw conclusions from knowledge. In AI this field of research is called knowledge representation and reasoning (KRR).

Definition: A logic is a formal notation for stating knowledge. A logic can also be called a formal language, or a calculus. Formal essentially means mechanizable, i.e. computational. Logics exist in contrast to so-called natural languages such as English and Swahili, which can be manipulated by humans but not by any known algorithms in their full generality.

THE PREDICATE CALCULUS

We shall study first one particular logic, called the predicate calculus and also called first-order logic, which you may 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 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, FUNCTION-SYMBOLS, AND EQUALITY

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.

There is a special predicate-symbol written = in first-order logic. Saying that two terms are equal means that they designate the same object, e.g. =(father(Harry),father(William)) which is usually written father(Harry) = father(William)