CSE 250A Lecture Notes, February 12, 2001

CSE 250A LECTURE NOTES

February 12, 2001

ANNOUNCEMENTS

Remember that the second project report is due on Friday. I'm available to discuss draft reports.

Today's handout is the description of the third project, on reviewing research papers. The assignment has three stages, with two deadlines, Mondays February 19 and February 26.

Next Monday there will be nolecture because of yet another university holiday.

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)

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

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
the meaning function M[ ]
truth tables for the meaning of connectives

It is very important for you to understand what thhe following statement means: Constant, function, and predicate symbols are uninterpreted. Intuitively, 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.

First-order logic has a compositional semantics, also known as a denotational semantics. Each part of a sentence that is syntactically well-formed has a well-defined meaning in isolation, and the meaning of each composite part of a sentence is a function of the meaning of its component parts.