2/14/2022

The predicate calculus

Predicate Calculus Extends propositional logic in two ways:

1. Propositions are no longer atomic. They assert that an entity has a
aka First-Order Logic property or that a relation holds between entities
2. Universal quantifier: Every entity has some particular property.
Existential quantifier: There exists an entity with some particular
property.
All (or nearly all) mathematical statements can be expressed in the
predicate calculus, and (nearly) all proofs can be justified in the
predicate calculus.
Many other forms of reasoning as well.

1 2

Syntax Syntax
Logical symbols: Term ::= Constant | Variable | Function(Term … Term)
Boolean operators: ¬, ⋀, ∨, ⇒, ⇔, AtomicFormula ::= Predicate(Term … Term)
Quantifiers: ∀, ∃. Formula ::= AtomicFormula |¬ Formula | (Formula Boolean Formula) |
Variables: x, y, z
Quantifier Variable Formula
(Often useful also to have equals sign =, but we will not be using it.)
A sentence is a formula in which every occurrence of a variable is
bound by a quantifier.
Non-logical symbols:
Constant symbols: 2, EiffelTower, Year1709AD Same precedence on Boolean operators.
Function symbols: Plus(x,y). Quantifiers have scope to the end of the sentence.
Predicate symbols: Parent(x,y). Greater(x,y). PegInHole(h,t). Combine variables with same quantifier e.g. write ∀x ∀y as ∀x,y

3 4

The syntax of a sentence is a tree Semantics

F
F There is a universe Ω of entities.
F What kind of entities? Whatever you want: People, physical objects,
organizations, numbers, units of time, regions of space …
F F
But you decide at the start on your entities, and you stick to that.
A A
∀xα(x) means that all entities x have property α.
T
∃xα(x) means that some entity x has property α.
T T T T T
Q VQ V P V V B P F V C V
∀ x ∀ y Gt( x , y) ⇒ Gt (Plus( x, One), y)

5 6

1
 2/14/2022

Denotation of non-logical symbols Tarskian semantics for predicate calculus

A constant symbol denotes an entity in Ω. Given a first-order language L, the domain Ω, and the denotation of
E.g. D(“Two”) = 2. every non-logical symbol in L: the semantics for predicate calculus
An n-place predicate symbol denotes a n-place relation over Ω; that is, defines whether a given sentence is true or false.
a set of n-tuples of entities. However I’m not going to go into it.
E.g. D(“Gt”) = {<x,y> | x > y} = { <2,1>, <5,3>, <4,1> … } Instead, I’ve going to give you some advice about correctly writing
An n-place function symbol denotes a n-place mapping over Ω; that is, sentences in predicate calculus.
a set of (n+1)-tuples of entities where the last term depends
functionally on the first n.
E.g. D(“Plus”) = { <x,y,z> | x+y=z} = {<1,1,2>, <2,3,5>, <8,1,9> …}

7 8

How to express facts in predicate calculus Examples: People and songs

Preliminary comments about translating from English to Pred. Calc.
If I specify a domain Ω and a language L (that is, a set of non-logical
symbols and their meaning) and then ask you how an English sentence
can be expressed in L, that can be a reasonable question. I will be
asking you questions of this kind on problem sets and exams.
If I give you a subject matter and describe what kinds of facts I want to
express and what kinds of reasoning I want to support, and ask you to
design a language that expresses those facts and a theory that justifies
the reasoning, that can be a reasonable question, but it is a large and
difficult one. I won’t be asking you problems of that kind. That would
be a term project in a course in knowledge representation.

9 10

Example: People, articles, journals

11 12

2
 2/14/2022

There are no fixed rules for Observe the rule of syntax

translating natural language to logic. Constants, functions, and variables are inside predicates.
You have to think about the meaning of what the sentence says, and Boolean operators and quantifiers are outside predicates.
express that meaning in logic. Predicates are not inside one another.
“Sam has a male child”
But there are certainly things to keep in mind and errors to avoid. WRONG!!! Male(∃x Child(x,Sam))
WRONG!!! ∃x Child(Male(x),Sam)
RIGHT: ∃x Male(x) ⋀ Child(x,Sam)
“Mary and Ed are children of Anne.”
WRONG!!! Child(Mary ⋀ Ed, Anne)
RIGHT: Child(Mary,Anne) ⋀ Child(Ed,Anne)

13 14

Restricted universal quantification Restricted universal quantification

“All crows are black” WRONG: ∀x Crow(x) ⋀ Black(x).
RIGHT: ∀x Crow(x) ⇒ Black(x). This means, “Everything is both a crow and black” “Everything is a black
As stated before, α⇒β means “not α or β“. crow.”
So this means “Everything Is either not a crow or it is black”. So if some In general, ∀x α(x)⋀β(x) is equivalent to [∀x α(x)] ⋀ [∀x β(x).]
particular object is a crow, it must be black. If everything is both α and β, then everything is α and everything is β.
If you’ve written a formula of the form ∀x α(x)⋀β(x) where a
conjunction is directly in the scope of a universal formula, there is a
95% chance you’ve written it wrong. To check, rewrite as
[∀x α(x)] ⋀ [∀x β(x)], and see whether it still looks plausible.

15 16

Restricted existential quantification Restricted existential quantification

“Some ducks are white.” “Some ducks are white.”
RIGHT: ∃x Duck(x) ⋀ White(x) WRONG: ∃x Duck(x) ⇒ White(x)
(except that the plural is lost).
This means “There is something that is both a duck and is white.”
“Some white things are ducks” would be represented the same way,
but that’s OK.

17 18

3
 2/14/2022

Restricted existential quantification Restricted existential quantification

“Some ducks are white.” “Some ducks are white.”
WRONG: ∃x Duck(x) ⇒ White(x) WRONG: ∃x Duck(x) ⇒ White(x)

WRONG! WRONG!

WRONG!!!!

19 20

Restricted existential quantification Added during class

“Some ducks are white.” A student asked, “Does the formula mean, ‘There are no non-white ducks.’”
WRONG: ∃x Duck(x) ⇒ White(x) No. You can express “There are no non-white ducks” as
Translate into an equivalent form where the wrongness is more ¬[∃x Duck(x) ^ ¬White(x)]. Or one can write, equivalently
apparent.
Step 1: ∃x ¬Duck(x) ∨ White(x). ∀x Duck(x) => White(x).
Step 2: ∃x α(x) ∨ β(x) is always equivalent to [∃x α(x)] ∨ [∃x β(x)]. Proof that they are equivalent: ¬[∃x α(x)] is always equivalent to
If there is something that is either α or β , then either there is ∀x ¬α(x). If there does not exist anything that is α, then everything is not α.
something that is α or there is something that is β; and conversely.
So Step 1 is equivalent to [∃x ¬Duck(x)] ∨ [∃x White(x)] “Either there is So ¬[∃x Duck(x) ^ ¬White(x)] is equivalent to
something in the world that is not a duck or there is something that is ∀x ¬(Duck(x) ^ ¬White(x)) which is equivalent to
white.” So the formula is true unless everything in the world is a non- ∀x ¬Duck(x) ∨¬¬White(x) which is ∀x Duck(x) => White(x).
white duck. So it isn’t saying much
But ∃x Duck(x) ⇒ White(x) is not the same thing.

21 22

Restricted existential quantification Don’t trust the English! Quantifiers

General rule: If you’ve written a formula of the form ∃x α(x) ⇒ β(x) “Some”, “Somebody” “Something”, “a”, “the” often mean an existential
where an implication (or a two-way implication) is directly in the scope quantifier:
of an existential quantifier, then it is 99% certain that it’s wrong.
Essentially the only exceptions are when α actually doesn’t contain x. In “George sees a robin.” ∃x Sees(George,x) ⋀ Robin(x).
that case, you should rewrite this, for clarity, α ⇒ ∃x β(x).
For instance ∀x ∃y Even(x) ⇒ Times(y,2,x) is right, but it’s better to “Someone’s knocking at the door”
write it ∀x Even(x) ⇒ ∃y Times(y,2,x). ∃x,y Door(y) ⋀ KnockingAt(x,y).
If you’ve written it and you really feel certain that it’s right, then
rewrite it in the logically equivalent form [∃x ¬ α(x)] ∨ [∃x β(x)], and see
if it still seems right.

23 24

4
 2/14/2022

Don’t trust the English! Quantifiers Don’t trust the English! Quantifiers
But not always. “A squirrel is a mammal”.
“If someone is 18 years old, they are allowed to vote.” ∀x Squirrel(x) ⇒ Mammal(x)
∀x Geq(AgeOf(x),Times(18,Year)) ⇒ Legal(Do(x,Vote))
NOT: ∃x Geq(AgeOf(x),Times(18,Year)) ⋀ Legal(Do(x,Vote))
“A person is allowed to drive only if they have a license.”
(“There is someone over 18 who is allowed to vote”)
∀x Legal(x,Drive) ⇒ ∃y License(y) ⋀ Owns(x,y).
DEFINITELY NOT: ∃x Geq(AgeOf(x),Times(18,Year)) ⇒ Legal(Do(x,Vote))
(Discussed earlier: This means “Either there is someone not yet 18, or there
is someone who may legally vote”) “Lucy owns a parrot that is larger than a cat.”
NOT ANY BETTER: [∃x Geq(AgeOf(x),Times(18,Year))] ⇒ Legal(Do(x,Vote)) ∃x Parrot(x) ⋀ Owns(Lucy,x) ⋀ ∀y Cat(y) ⇒ Larger(x,y)
(This means: If anyone is at least 18, then x may vote.

25 26

Alternative correct representations Alternative correct representations

Logically equivalent representation: Logically equivalent given some background knowledge:
“Pamela has a long nose.”
“A vegetarian is someone who eats no meat.” Is this
∀x Vegetarian(x) ⇔ ¬[∃y Meat(y) ⋀ Eats(x,y)]. ∀y NoseOf(y,Pamela) ⇒ Long(y).
∀x Vegetarian(x) ⇔ [∀y Meat(y) ⇒ ¬Eats(x,y)]. or
∀x [∃y Meat(y) ⋀ Eats(x,y)] ⇔ ¬Vegetarian(x). ∃x NoseOf(y,Pamela) ⋀ Long(y).
Given that a person has one nose, these are equivalent.

27 28

In designing a language,
Alternative correct representation
do not shortchange the representation!
“Alabama borders Mississippi”. Especially: If you need to represent things that change over time, you
Is this will have to incorporate an explicit representation of time.
Borders(Alabama,Mississippi) or ∀x Light(x) ⋀ Off(x) ⋀ Flip(SwitchOf(x)) ⇒ On(x). WRONG.
Borders(Mississippi,Alabama) or
Borders(Alabama,Mississippi) ⋀ Borders(Mississippi,Alabama) ∀x,t,t2 Light(x) ⋀ Off(x,t) ⋀ Occurs(t,t2,Flip(SwitchOf(x)) ⇒ On(x,t2).
Given the background knowledge that “Borders” is symmetric, these Or some such.
are equivalent. It’s also the case that you don’t want to introduce more distinctions
than you need. But of course, it’s hard to judge what you may need in
the future.

29 30

5
 2/14/2022

Largely outside the scope

of the predicate calculus
• Generic statements: “Birds can fly. “
• Vagueness: “Sarah is tall.”
• Uncertainty. “It will probably take less than an hour to get to the
airport.”
• Modal operators: “John knows that Salem or Portland is the capital of
Oregon.”
• Meta-reasoning: “Hint: To solve problem 2.1, use the fundamental
theorem of the calculus.”

31