CSE 150 Lecture Notes, February 3, 2003

CSE150 LECTURE NOTES

February 3, 2003

CONSTANT-SYMBOLS, FUNCTION-SYMBOLS, AND EQUALITY

Definition: 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 what the meaning of each sentence is.

An object is something semantic. The name of an object is something syntactic. For example, "Mary" is a name that designates a semantic object. Names are also called constant-symbols.

Definition: A term is any syntactic expression that designates an object.

Names are primitive terms, 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.

THE EQUALITY PREDICATE

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)

We can use the = predicate-symbol to assert that there exists a unique object with a certain property. For example:

exists x { isa-dog(x) & loves(Mary,x) & forall y [ isa-dog(y) & loves(Mary,y) ] -> y=x }

The sentence above can be abbreviated exists! x isa-dog(x) & loves(Mary,x)

THE DIFFERENCE BETWEEN FUNCTIONS AND PREDICATES

A function maps a fixed number of objects to another object. Let f be a k-ary function, and let a1 through ak be arguments.

f(a1,...,ak) always exists: the function is total. This means that if we have the constant 13 and the function father, then father(13) is a well-formed term that designates some object.
f(a1,...,ak) is always unique: the function is single-valued. This means that if we have the function daughter then daughter(Mary) must designate the only daughter of Mary.

To specify anything about the meaning of a function, we must use additional explicit axioms, which often involve equality. For example:

daughter(Mary) = Beth not(Beth = Mary)

A predicate maps a fixed number of objects to a truth value (true or false). We must use a predicate to represent any multi-valued function, e.g. has-daughter(Mary,Joan) has-daughter(Mary,Beth)

To represent a multi-valued function precisely, we must use a complex sentence such as

forall x has-daughter(Mary,x) <-> [ x=Joan \/ x=Beth ]

Be sure to understand the exact effect of the bidirectional implication <->.

SEMANTICS OF FIRST-ORDER LOGIC

Definition: The semantics of a logic is a description of 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
the meaning function M[ ]
the meaning of the universal and existential quantifiers

In first-order logic, every part of a sentence that is syntactically well-formed has a well-defined meaning iitself. We use the notation M[ ] to talk about the meaning of a sentence, or of a part of a sentence.

Unlike for natural languages, essentially all the logics used in AI have a compositional semantics.

Definition: A semantics is compositional (synonym: denotational) if the meaning of each composite part of a sentence is a function of the meaning of its component parts.

If a semantics is compositional, and two sentence fragments have the same meaning, then they can be interchanged everywhere even if they are syntactically distinct.

AXIOMATIZING KNOWLEDGE

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).

When you write down knowledge formally, the real knowledge is in the interrelationships between predicates and functions, not in the names of the predicates and functions, because constant-symbols, function-symbols, and predicate-symbols are uninterpreted.

It is very important for you to understand what the following statement means: Constant, function, and predicate symbols are uninterpreted. It means that, for example, daughter(Mary) designates a semantic entity that, as far as we know, can be the same as or different from every other semantic entity.

Typically, you have an intended interpretation in mind. You write down as many axioms as possible that are useful. An axiom is useful if it is true but not redundant, that is true in the intended interpretation but false in some unintended interpretation, so that it excludes this undesired model of the other axioms.