1/27/2026

Summary
 Predicate Logic (First-Order Logic (FOL), Predicate
Calculus)
 The Language of Quantifiers
Chapter 1, Part II: Predicate Logic  Logical Equivalences
 Nested Quantifiers
 Translation from Predicate Logic to English
With Question/Answer Animations  Translation from English to Predicate Logic

Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.

Section Summary
 Predicates
 Variables
 Quantifiers
Section 1.4  Universal Quantifier
 Existential Quantifier
 Negating Quantifiers
 De Morgan’s Laws for Quantifiers
 Translating English to Logic
 Logic Programming (optional)

Propositional Logic Not Enough Introducing Predicate Logic

 If we have:  Predicate logic uses the following new features:
“All men are mortal.”  Variables: x, y, z
“Socrates is a man.”  Predicates: P(x), M(x)
 Does it follow that “Socrates is mortal?”  Quantifiers (to be covered in a few slides):
 Can’t be represented in propositional logic. Need a  Propositional functions are a generalization of
language that talks about objects, their properties, and propositions.
their relations.  They contain variables and a predicate, e.g., P(x)
 Later we’ll see how to draw inferences.  Variables can be replaced by elements from their
domain.

1
 1/27/2026

Examples of Propositional
Propositional Functions Functions
 Propositional functions become propositions (and have  Let “x + y = z” be denoted by R(x, y, z) and U (for all three variables) be
truth values) when their variables are each replaced by a the integers. Find these truth values:
value from the domain (or bound by a quantifier, as we will R(2,-1,5)
Solution: F
see later).
R(3,4,7)
 The statement P(x) is said to be the value of the Solution: T
propositional function P at x. R(x, 3, z)
 For example, let P(x) denote “x > 0” and the domain be the Solution: Not a Proposition
integers. Then:  Now let “x - y = z” be denoted by Q(x, y, z), with U as the integers.
Find these truth values:
P(-3) is false. Q(2,-1,3)
P(0) is false. Solution: T
P(3) is true. Q(3,4,7)
Solution: F
 Often the domain is denoted by U. So in this example U is
Q(x, 3, z)
the integers. Solution: Not a Proposition

Compound Expressions Quantifiers Charles Peirce (1839-1914)

 Connectives from propositional logic carry over to predicate  We need quantifiers to express the meaning of English
logic. words including all and some:
 If P(x) denotes “x > 0,” find these truth values:  “All men are Mortal.”
P(3) ∨ P(-1) Solution: T  “Some cats do not have fur.”
P(3) ∧ P(-1) Solution: F  The two most important quantifiers are:
P(3) → P(-1) Solution: F
P(3) → ¬P(-1) Solution: T  Universal Quantifier, “For all,” symbol: 
 Expressions with variables are not propositions and therefore do  Existential Quantifier, “There exists,” symbol: 
not have truth values. For example,  We write as in x P(x) and x P(x).
P(3) ∧ P(y)
 x P(x) asserts P(x) is true for every x in the domain.
P(x) → P(y)
 When used with quantifiers (to be introduced next), these
 x P(x) asserts P(x) is true for some x in the domain.
expressions (propositional functions) become propositions.  The quantifiers are said to bind the variable x in these
expressions.

Universal Quantifier Existential Quantifier

 x P(x) is read as “For all x, P(x)” or “For every x, P(x)”  x P(x) is read as “For some x, P(x)”, or as “There is an
Examples: x such that P(x),” or “For at least one x, P(x).”
1) If P(x) denotes “x > 0” and U is the integers, then x P(x) is Examples:
false. 1. If P(x) denotes “x > 0” and U is the integers, then x P(x) is
2) If P(x) denotes “x > 0” and U is the positive integers, then true. It is also true if U is the positive integers.
x P(x) is true. 2. If P(x) denotes “x < 0” and U is the positive integers, then
3) If P(x) denotes “x is even” and U is the integers, then  x x P(x) is false.
P(x) is false. 3. If P(x) denotes “x is even” and U is the integers, then x
P(x) is true.

2
 1/27/2026

Uniqueness Quantifier (optional) Thinking about Quantifiers

 !x P(x) means that P(x) is true for one and only one x in the  When the domain of discourse is finite, we can think of
universe of discourse. quantification as looping through the elements of the domain.
 This is commonly expressed in English in the following  To evaluate x P(x) loop through all x in the domain.
equivalent ways:  If at every step P(x) is true, then x P(x) is true.
 If at a step P(x) is false, then x P(x) is false and the loop
 “There is a unique x such that P(x).”
terminates.
 “There is one and only one x such that P(x)”
 To evaluate x P(x) loop through all x in the domain.
 Examples:  If at some step, P(x) is true, then x P(x) is true and the loop
1. If P(x) denotes “x + 1 = 0” and U is the integers, then !x P(x) is terminates.
true.  If the loop ends without finding an x for which P(x) is true, then x
2. But if P(x) denotes “x > 0,” then !x P(x) is false. P(x) is false.
 The uniqueness quantifier is not really needed as the restriction  Even if the domains are infinite, we can still think of the
quantifiers this fashion, but the loops will not terminate in some
that there is a unique x such that P(x) can be expressed as: cases.
x (P(x) ∧y (P(y) → y =x))

Properties of Quantifiers Precedence of Quantifiers

 The truth value of x P(x) and  x P(x) depend on both  The quantifiers  and  have higher precedence than
the propositional function P(x) and on the domain U. all the logical operators.
 Examples:  For example, x P(x) ∨ Q(x) means (x P(x))∨ Q(x)
1. If U is the positive integers and P(x) is the statement
 x (P(x) ∨ Q(x)) means something different.
“x < 2”, then x P(x) is true, but  x P(x) is false.
2. If U is the negative integers and P(x) is the statement  Unfortunately, often people write x P(x) ∨ Q(x) when
“x < 2”, then both x P(x) and  x P(x) are true. they mean  x (P(x) ∨ Q(x)).
3. If U consists of 3, 4, and 5, and P(x) is the statement
“x > 2”, then both x P(x) and  x P(x) are true. But if
P(x) is the statement “x < 2”, then both x P(x) and
 x P(x) are false.

Translating from English to Logic Translating from English to Logic

Example 1: Translate the following sentence into predicate Example 2: Translate the following sentence into
logic: “Every student in this class has taken a course in predicate logic: “Some student in this class has taken a
Java.”
course in Java.”
Solution:
First decide on the domain U. Solution:
Solution 1: If U is all students in this class, define a First decide on the domain U.
propositional function J(x) denoting “x has taken a course in Solution 1: If U is all students in this class, translate as
Java” and translate as x J(x).
Solution 2: But if U is all people, also define a propositional x J(x)
function S(x) denoting “x is a student in this class” and Solution 2: But if U is all people, then translate as
translate as x (S(x)→ J(x)). x (S(x) ∧ J(x))
x (S(x) ∧ J(x)) is not correct. What does it mean?
x (S(x)→ J(x)) is not correct. What does it mean?

3
 1/27/2026

Returning to the Socrates Example Equivalences in Predicate Logic

 Introduce the propositional functions Man(x)  Statements involving predicates and quantifiers are
denoting “x is a man” and Mortal(x) denoting “x is logically equivalent if and only if they have the same
mortal.” Specify the domain as all people. truth value
 The two premises are:  for every predicate substituted into these statements
and
 for every domain of discourse used for the variables in
 The conclusion is:
the expressions.
 The notation S ≡T indicates that S and T are logically
 Later we will show how to prove that the conclusion equivalent.
follows from the premises.
 Example: x ¬¬S(x) ≡ x S(x)

Thinking about Quantifiers as

Conjunctions and Disjunctions Negating Quantified Expressions
 If the domain is finite, a universally quantified proposition is  Consider x J(x)
equivalent to a conjunction of propositions without quantifiers
and an existentially quantified proposition is equivalent to a “Every student in your class has taken a course in Java.”
disjunction of propositions without quantifiers.
 If U consists of the integers 1,2, and 3:
Here J(x) is “x has taken a course in Java” and
the domain is students in your class.
 Negating the original statement gives “It is not the case
that every student in your class has taken Java.” This
implies that “There is a student in your class who has
 Even if the domains are infinite, you can still think of the not taken Java.”
quantifiers in this fashion, but the equivalent expressions
without quantifiers will be infinitely long. Symbolically ¬x J(x) and x ¬J(x) are equivalent

Negating Quantified Expressions

(continued) De Morgan’s Laws for Quantifiers
 Now Consider  x J(x)  The rules for negating quantifiers are:
“There is a student in this class who has taken a course in
Java.”
Where J(x) is “x has taken a course in Java.”
 Negating the original statement gives “It is not the case
 The reasoning in the table shows that:
that there is a student in this class who has taken Java.”
This implies that “Every student in this class has not
taken Java”
Symbolically ¬ x J(x) and  x ¬J(x) are equivalent
 These are important. You will use these.

4
 1/27/2026

Some Fun with Translating from

Translation from English to Logic English into Logical Expressions
Examples:  U = {fleegles, snurds, thingamabobs}
1. “Some student in this class has visited Mexico.” F(x): x is a fleegle
Solution: Let M(x) denote “x has visited Mexico” and S(x): x is a snurd
S(x) denote “x is a student in this class,” and U be all T(x): x is a thingamabob
people. Translate “Everything is a fleegle”
x (S(x) ∧ M(x))
2. “Every student in this class has visited Canada or
Solution: x F(x)
Mexico.”
Solution: Add C(x) denoting “x has visited Canada.”
x (S(x)→ (M(x)∨C(x)))

Translation (cont) Translation (cont)

 U = {fleegles, snurds, thingamabobs}  U = {fleegles, snurds, thingamabobs}
F(x): x is a fleegle F(x): x is a fleegle
S(x): x is a snurd S(x): x is a snurd
T(x): x is a thingamabob T(x): x is a thingamabob
“Nothing is a snurd.” “All fleegles are snurds.”

Solution: ¬x S(x) What is this equivalent to? Solution: x (F(x)→ S(x))
Solution: x ¬ S(x)

Translation (cont) Translation (cont)

 U = {fleegles, snurds, thingamabobs}  U = {fleegles, snurds, thingamabobs}
F(x): x is a fleegle F(x): x is a fleegle
S(x): x is a snurd S(x): x is a snurd
T(x): x is a thingamabob T(x): x is a thingamabob
“Some fleegles are thingamabobs.” “No snurd is a thingamabob.”

Solution: x (F(x) ∧ T(x)) Solution: ¬x (S(x) ∧ T(x)) What is this equivalent
to?
Solution: x (¬S(x) ∨ ¬T(x))

5
 1/27/2026

Translation (cont) System Specification Example

 Predicate logic is used for specifying properties that systems must
 U = {fleegles, snurds, thingamabobs} satisfy.
F(x): x is a fleegle  For example, translate into predicate logic:
 “Every mail message larger than one megabyte will be compressed.”
S(x): x is a snurd
 “If a user is active, at least one network link will be available.”
T(x): x is a thingamabob  Decide on predicates and domains (left implicit here) for the variables:
“If any fleegle is a snurd then it is also a thingamabob.”  Let L(m, y) be “Mail message m is larger than y megabytes.”
 Let C(m) denote “Mail message m will be compressed.”
 Let A(u) represent “User u is active.”

Solution: x ((F(x) ∧ S(x))→ T(x))  Let S(n, x) represent “Network link n is state x.
 Now we have:

Some Predicate Calculus

Lewis Carroll Example
Charles Lutwidge Dodgson
(AKA Lewis Caroll)
(1832-1898)
Definitions (optional)
 The first two are called premises and the third is called the  An assertion involving predicates and quantifiers is valid if
conclusion. it is true
1. “All lions are fierce.”  for all domains
2. “Some lions do not drink coffee.”  every propositional function substituted for the predicates in the
assertion.
3. “Some fierce creatures do not drink coffee.” Example:
 Here is one way to translate these statements to predicate logic.  An assertion involving predicates is satisfiable if it is true
Let P(x), Q(x), and R(x) be the propositional functions “x is a  for some domains
lion,” “x is fierce,” and “x drinks coffee,” respectively.  some propositional functions that can be substituted for the
1. x (P(x)→ Q(x)) predicates in the assertion.
2. x (P(x) ∧ ¬R(x)) Otherwise it is unsatisfiable.
3. x (Q(x) ∧ ¬R(x)) Example: not valid but satisfiable
 Later we will see how to prove that the conclusion follows from Example: unsatisfiable
the premises.

MorePredicate Calculus Definitions

(optional) Logic Programming (optional)
 The scope of a quantifier is the part of an assertion in  Prolog (from Programming in Logic) is a programming
language developed in the 1970s by researchers in artificial
which variables are bound by the quantifier. intelligence (AI).
Example: x has wide scope  Prolog programs include Prolog facts and Prolog rules.
 As an example of a set of Prolog facts consider the
following:
Example: x has narrow scope instructor(chan, math273).
instructor(patel, ee222).
instructor(grossman, cs301).
enrolled(kevin, math273).
enrolled(juana, ee222).
enrolled(juana, cs301).
enrolled(kiko, math273).
enrolled(kiko, cs301).

 Here the predicates instructor(p,c) and enrolled(s,c)

represent that professor p is the instructor of course c and
that student s is enrolled in course c.

6
 1/27/2026

Logic Programming (cont) Logic Programming (cont)

 In Prolog, names beginning with an uppercase letter  Prolog programs are loaded into a Prolog interpreter. The
are variables. interpreter receives queries and returns answers using the
Prolog program.
 If we have apredicate teaches(p,s) representing
“professor p teaches student s,” we can write the rule:  For example, using our program, the following query may
be given:
teaches(P,S) :- instructor(P,C), enrolled(S,C).
?enrolled(kevin,math273).
 This Prolog rule can be viewed as equivalent to the
 Prolog produces the response:
following statement in logic (using our conventions for
yes
logical statements).
 Note that the ? is the prompt given by the Prolog
p c s(I(p,c) ∧ E(s,c)) → T(p,s))
interpreter indicating that it is ready to receive a query.

Logic Programming (cont) Logic Programming (cont)

 The query:
?enrolled(X,math273).
 The query:
?teaches(chan,X).
produces the response: The Prolog interpreter tries to produces the response:
X = kevin; find an instantiation for X. It does
X = kevin;
X = kiko; so and returns X = kevin.
X = kiko;
no Then the user types the ;
no
 The query: indicating a request for another
answer. When Prolog is unable to
?teaches(X,juana).
find another answer it returns no.  A number of very good Prolog texts are available. Learn
produces the response: Prolog Now! is one such text with a free online version at
X = patel; [Link]
X = grossman;  There is much more to Prolog and to the entire field of
no
logic programming.

Section Summary
 Nested Quantifiers
 Order of Quantifiers
 Translating from Nested Quantifiers into English
Section 1.4  Translating Mathematical Statements into Statements
involving Nested Quantifiers.
 Translated English Sentences into Logical Expressions.
 Negating Nested Quantifiers.

7
 1/27/2026

Nested Quantifiers Thinking of Nested Quantification

 Nested Loops
 Nested quantifiers are often necessary to express the
 To see if xyP (x,y) is true, loop through the values of x :
meaning of sentences in English as well as important  At each step, loop through the values for y.
If for some pair of x andy, P(x,y) is false, then x yP(x,y) is false and both the
concepts in computer science and mathematics. 
outer and inner loop terminate.
x y P(x,y) is true if the outer loop ends after stepping through each x.
Example: “Every real number has an inverse” is  To see if x yP(x,y) is true, loop through the values of x:
x y(x + y = 0)  At each step, loop through the values for y.
 The inner loop ends when a pair x and y is found such that P(x, y) is true.

where the domains of x and y are the real numbers.  If no y is found such that P(x, y) is true the outer loop terminates as x yP(x,y)
has been shown to be false.
 We can also think of nested propositional functions: x y P(x,y) is true if the outer loop ends after stepping through each x.
 If the domains of the variables are infinite, then this process can not
x y(x + y = 0) can be viewed as x Q(x) where Q(x) is actually be carried out.
y P(x, y) where P(x, y) is (x + y = 0)

Order of Quantifiers Questions on Order of Quantifiers

Examples: Example 1: Let U be the real numbers,
1. Let P(x,y) be the statement “x + y = y + x.” Assume Define P(x,y) : x ∙ y = 0
that U is the real numbers. Then x yP(x,y) and What is the truth value of the following:
y xP(x,y) have the same truth value. 1. xyP(x,y)
Answer: False
2. Let Q(x,y) be the statement “x + y = 0.” Assume that
U is the real numbers. Then x yQ(x,y) is true, but 2. xyP(x,y)
Answer: True
y xQ(x,y) is false.
3. xy P(x,y)
Answer: True
4. x  y P(x,y)
Answer: True

Questions on Order of Quantifiers Quantifications of Two Variables

Example 2: Let U be the real numbers,
Define P(x,y) : x / y = 1 Statement When True? When False
What is the truth value of the following: P(x,y) is true for every There is a pair x, y for
1. xyP(x,y) pair x,y. which P(x,y) is false.

Answer: False
For every x there is a y for There is an x such that
2. xyP(x,y) which P(x,y) is true. P(x,y) is false for every y.
Answer: False There is an x for which For every x there is a y for
3. xy P(x,y) P(x,y) is true for every y. which P(x,y) is false.
Answer: False There is a pair x, y for P(x,y) is false for every
which P(x,y) is true. pair x,y
4. x  y P(x,y)
Answer: True

8
 1/27/2026

Translating Nested Quantifiers into Translating Mathematical

English Statements into Predicate Logic
Example 1: Translate the statement Example : Translate “The sum of two positive integers is
x (C(x )∨ y (C(y ) ∧ F(x, y))) always positive” into a logical expression.
Solution:
where C(x) is “x has a computer,” and F(x,y) is “x and y are
1. Rewrite the statement to make the implied quantifiers and
friends,” and the domain for both x and y consists of all domains explicit:
students in your school. “For every two integers, if these integers are both positive, then the
Solution: Every student in your school has a computer or sum of these integers is positive.”
has a friend who has a computer. 2. Introduce the variables x and y, and specify the domain, to
obtain:
Example 2: Translate the statement “For all positive integers x and y, x + y is positive.”
xy z ((F(x, y)∧ F(x,z) ∧ (y ≠z))→¬F(y,z)) 3. The result is:
x  y ((x > 0)∧ (y > 0)→ (x + y > 0))
Solution: There is a student none of whose friends are where the domain of both variables consists of all integers
also friends with each other.

Translating English into Logical

Expressions Example Calculus in Logic (optional)
Example: Use quantifiers to express the statement Example: Use quantifiers to express the definition of the limit of a
real-valued function f(x) of a real variable x at a point a in its
“There is a woman who has taken a flight on every domain.
airline in the world.” Solution: Recall the definition of the statement
Solution:
is “For every real number ε > 0, there exists a real number δ > 0
1. Let P(w,f) be “w has taken f ” and Q(f,a) be “f is a such that |f(x) – L| < ε whenever 0 < |x –a| < δ.”
flight on a .” Using quantifiers:
2. The domain of w is all women, the domain of f is all
flights, and the domain of a is all airlines.
Where the domain for the variables ε and δ consists of all
3. Then the statement can be expressed as: positive real numbers and the domain for x consists of all real
numbers.
w a f (P(w,f ) ∧ Q(f,a))

Questions on Translation from

English Negating Nested Quantifiers
Choose the obvious predicates and express in predicate logic. Example 1: Recall the logical expression developed three slides back:
w a f (P(w,f ) ∧ Q(f,a))
Example 1: “Brothers are siblings.” Part 1: Use quantifiers to express the statement that “There does not exist a woman who
Solution: x y (B(x,y) → S(x,y)) has taken a flight on every airline in the world.”
Solution: ¬w a f (P(w,f ) ∧ Q(f,a))
Example 2: “Siblinghood is symmetric.” Part 2: Now use De Morgan’s Laws to move the negation as far inwards as possible.
Solution: x y (S(x,y) → S(y,x)) Solution:
Example 3: “Everybody loves somebody.” 1. ¬w a f (P(w,f ) ∧ Q(f,a))
2. w ¬ a f (P(w,f ) ∧ Q(f,a)) by De Morgan’s for 
Solution: x y L(x,y) 3. w  a ¬ f (P(w,f ) ∧ Q(f,a)) by De Morgan’s for 
Example 4: “There is someone who is loved by everyone.” 4. w  a f ¬ (P(w,f ) ∧ Q(f,a)) by De Morgan’s for 
Solution: y x L(x,y) 5. w  a f (¬ P(w,f ) ∨ ¬ Q(f,a)) by De Morgan’s for ∧.
Part 3: Can you translate the result back into English?
Example 5: “There is someone who loves someone.” Solution:
Solution: x y L(x,y) “For every woman there is an airline such that for all flights, this woman has not taken
that flight or that flight is not on this airline”
Example 6: “Everyone loves himself”
Solution: x L(x,x)

9
 1/27/2026

Calculus in Predicate Logic

Return to Calculus and Logic (Opt) (optional)
Example : Recall the logical expression developed in the calculus example three slides back.
Use quantifiers and predicates to express that does not exist. 4. Therefore, to say that does not exist means
1. We need to say that for all real numbers L, that for all real numbers L, can be
2. The result from the previous example can be negated to yield:
expressed as:

3. Now we can repeatedly apply the rules for negating quantified expressions:
Remember that ε and δ range over all positive real
numbers and x over all real numbers.
5. Translating back into English we have, for every real
number L, there is a real number ε > 0, such that for
every real number δ > 0, there exists a real number
The last step uses the equivalence ¬(p→q) ≡ p∧¬q
x such that 0 < | x – a | < δ and |f(x) – L | ≥ ε .

Some Questions about Quantifiers

(optional)
 Can you switch the order of quantifiers?
 Is this a valid equivalence?
Solution: Yes! The left and the right side will always have the same truth
value. The order in which x and y are picked does not matter.
 Is this a valid equivalence?
Solution: No! The left and the right side may have different truth values for
some propositional functions for P. Try “x + y = 0” for P(x,y) with U being the
integers. The order in which the values of x and y are picked does matter.
 Can you distribute quantifiers over logical connectives?
 Is this a valid equivalence?
Solution: Yes! The left and the right side will always have the same truth
value no matter what propositional functions are denoted by P(x) and Q(x).
 Is this a valid equivalence?
Solution: No! The left and the right side may have different truth values.
Pick “x is a fish” for P(x) and “x has scales” for Q(x) with the domain of
discourse being all animals. Then the left side is false, because there are some
fish that do not have scales. But the right side is true since not all animals are
fish.

10