Transcript 1/22 - courses.psu.edu

Function Symbols & Arithmetic
PHIL012 January 22, 2001
Outline
•
•
•
•
•
Announcements
function symbols, terms, complex terms
The first order language of arithmetic
Sample problems
Assignment
Terms
• A “Term” is another name for the arguments
that predicates take.
• Examples
Terms
Predicate
Cube(a)
a
Cube
Between(a,b,c)
a, b, c
Between
Likes(Mary, Tom)
Mary, Tom
Likes
Tall(Father(Max)
Father(Max)
Tall
Function Symbols
• A Function Symbol looks like a predicate
(since it takes arguments):
• Predicate: Cube(a)
• Function Symbol: Father(Max)
• However, a Predicate with its arguments
form a sentence.
• Whereas, a Function Symbol with its
argument is simply a term.
Function Symbols vs. Predicates
• Cube(a) is a sentence because it makes a
claim. It says “a is a cube”
• Father(Max) does not make a claim. It
simply picks out a person, “Max’s Father.”
• Father(Max) is a term because it doesn’t say
anything about Max’s father.
• Cube(a) has a truth value. Father(Max)
does not.
Terms and Function Symbols
• In the two expressions, Cube(a) and
Tall(Father(Max)),
• “a” is like “Father(Max)”
• “Tall” is like “Cube”
• “a” and “Father(Max)” behave like names
in picking out objects
• “Tall” and “Cube” are predicates,
specifying properties of objects.
Complex Terms
• Father(Max) is an example of a Complex
Term.
• A Complex Term is formed by putting a
function symbol in front of either a name or
another complex term.
• Complex Terms are used just like names
(simple terms) in forming atomic sentences.
Sample Problem
• Suppose we have 2 languages for talking
about employment.
• Language 1 is functional, since it contains
the function symbol, “Employer”.
Employer(Claire) means “Claire’s
Employer”
• Language 2 is relational. It uses the
predicate Employs(Tony,Claire) to say that
Tony is Claire’s employer.
Language 1
• Names: Tony, Claire, Max
• Function Symbol: Employer
• Predicates: EarnsMoreThan, =
Language 2
• Names: Tony, Claire, Max
• Predictates: EarnsMoreThan, =, Employs
Translate these Language 2
sentences into Language 1
Lanuage 2
Language 2
Employs(Claire,Max)
Employer(Max) = Claire
Employs(Max,Tony)
Employer(Tony) = Max
EarnsMoreThan(Claire,
Tony)
EarnsMoreThan(Claire,Tony)
Language 1 into Language 2
Language 1
Employer(Max) = Claire
Language 2
Employs(Claire,Max)
Employer(Max) = Employer(Tony)
untranslatable
EarnsMoreThan(Employer(Max),
untranslatable
Employer(Tony))
Summary
• Terms are simple or complex.
• A Simple Term is a Name
• A Complex Term is a Function Symbol
followed by some number of Simple Terms
or Complex Terms.
• Terms pick out objects.
• Predicates specify properties of objects.
Function Symbols & Arithmetic
• We can specify all of the numbers and
operations of arithmetic using a simplified
set of symbols:
• Names: The numbers 0, 1
• Predicates: =, <
• Function Symbols: +, *
Inductive Definition of Terms
• The language includes an infinite number of
complex terms:
• 0, 1, (1+1), (1+1)+1, ((1+1)+1)+1, …
• We need to have a routine way of
determining whether an expression is a term
in the language or not.
• We do this by inductive definition.
Inductive Definition
• To form an inductive definition,
• We set up initial set of terms,
• Definition 1: 0 and 1 are terms
Inductive Definition Continued
• We specify a set of rules that must be
followed to get additional terms. In this
case, these are:
• Definition 2: If t1 and t2 are terms, then
(t1 + t2) and (t1 * t2) are also terms.
• Definition 3: An expression is a term IFF it
was derived by repeating definitions 1 and
2.
Sample Problems
• Show that the following are expressions in
our language:
1. ((1 + 1) * ((1+1) +1))
Sample Problems
2. ((0 * (1 + 0)) + 1)
Assignment
• For Wednesday:
– Read 2.7
– Try to work through problems 14-17.
• By Midnight Thursday:
– Turn in problems 14-17 (Homework 3)
• For Friday:
– Read 2.8
• Our first test (Chapter 2) will be on Feb 5
• We will have a review on Feb 2.