PREDICATES AND QUANTIFIERS

1
 TERMINOLOGY REVIEW
Proposition:
- A statement that is either true or false
- Must always be one or the other!

Example:
“The sky is red”
Not a proposition: x + 3 > 4

Boolean variable:
- A variable (usually p, q, r, etc.) that represents a
proposition.

2
 Consider the following statements:
x > 3, x = y +3, x + y = z

We can make propositions out of such statements

“ x is greater then 3”

subject predicate

3
 To write in a predicate logic:
“ x is greater then 3”

subject predicate
We introduce a (functional) symbol for the predicate,
and put the subject as an argument (to the functional
symbol): P(x) . The statement P(x) is also said to be
propositional function.
Examples:
• Father(x): unary predicate
• Brother(x, y): binary predicate
• Sum(x, y, z): ternary predicate
• P(x, y, z, …t): n-ary predicate
4
 PROPOSITIONAL FUNCTIONS
Consider P(x) = x < 5
P(x) has no truth values (x is not given a value)

P(1) is true
The proposition 1 < 5 is true
P(10) is false
The proposition 10 < 5 is false

Thus, P(x) will create a proposition when given a value.

5
 EXAMPLE
Let P(x) denote the statement “x > 3”. What are truth
values of P(4) and P(2)?
SOLUTION:
P(x) = x > 3
P(4) = 4 > 3
P(4) = True

P(x) = x > 3
P(2) = 2 > 3
P(2) = False

6
 EXAMPLES
Let P(x) = “x is a multiple of 5”
For what values of x is P(x) true?

Let P(x) = x+1 > x

For what values of x is P(x) true?

Let P(x) = x + 3
For what values of x is P(x) true?

7
 ANATOMY OF A PROPOSITIONAL
FUNCTION

P(x) = x + 5 > x

variable predicate

8
 PROPOSITIONAL FUNCTIONS
INVOLVING MULTIPLE VARIABLES
Functions with multiple variables:

P(x,y) = x + y == 0
P(1,2) is false, P(1,-1) is true

P(x,y,z) = x + y == z
P(3,4,5) is false, P(1,2,3) is true

P(x1,x2,x3 … xn) = …

9
 PREDICATE DEFINITION
Definition:
A predicate is a sentence that contains a finite number of
variables and becomes a statement when specific values
are substituted for the variables.

Domain:
The domain of a predicate variable is the set of all values
that may be substituted in place of the variable.

10
 UNIVERSE OF DISCOURSE
Consider the statement ‘x > 3’, does it make sense to
assign to x the value ‘blue’?

Intuitively, the universe of discourse is the set of all

things we wish to talk about; that is the set of all objects
that we can sensibly assign to a variable in a propositional
function. Referred to as Domain.

What would be the universe of discourse for the

propositional function below be:

EnrolledCSE235(x)=‘x is enrolled in CSE235’

11
 QUANTIFIERS
When the variables in a propositional function are
assigned values, the resulting statement becomes a
proposition with a certain truth values.

However, there is another important way, called

quantification, to create a proposition from a
propositional function.

Quantification expresses the extent to which a

predicate is true over a range of elements.

12
 In English, the words all, some, many, none and few
are used in quantification.

We will focus on two types of quantification here

Universal Quantification ∀
Existential Quantification ∃

13
 The statement ‘x > 3’ is not a proposition

It becomes a proposition
When we assign values to the argument: ‘4>3’ is false, ‘2<3’ is true, or
When we quantify the statement

Two quantifiers
Universal quantifier ∀ \for
all
the proposition is true for all possible values in the universe of discourse

Existential quantifier ∃
\exists
14
the proposition is true for some value(s) in the universe of discourse
 UNIVERSAL QUANTIFIER
Definition: The universal quantification of a predicate P(x) is
the proposition ‘P(x) is true for all values of x in the universe
of discourse.’

Notation:
We use the notation: ∀ x P(x), which is read ‘for all x’.

If the universe of discourse is finite, say {n1,n2,…,nk}, then the

universal quantifier is simply the conjunction of the
propositions over all the elements
∀ x P(x) ⇔ P(n1) ∧ P(n2) ∧ … ∧ P(nk)

15
 UNIVERSAL QUANTIFIER
Represented by an upside-down A: ∀
It means “for all”
Let P(x) = x+1 > x

We can state the following:

∀x P(x)
English translation: “for all values of x, P(x) is true”
English translation: “for all values of x, x+1>x is true”

16
 EXAMPLE
Let the universe of discourse be the real numbers.
Then, ∀x P(x) is true

Let P(x) = x/2 < x

Not true for the negative numbers!
Thus, ∀x P(x) is false
When the domain is all the real numbers

In order to prove that a universal quantification is true, it

must be shown for ALL cases.

In order to prove that a universal quantification is false, it

must be shown to be false for only ONE case

17
 LOOP
Think of ∀ as a for loop:

∀x P(x), where 1 ≤ x ≤ 10

… can be translated as …

for ( x = 1; x <= 10; x++ )

is P(x) true?

If P(x) is true for all parts of the for loop, then ∀x P(x)
Consequently, if P(x) is false for any one value of the for loop, then
∀x P(x) is false

18
 REMEMBER
The truth value of ∀ x P(x) depends on the
domain/universe of discourse!

A statement ∀ x P(x) is false. If and only If P(x) is not

always true when x is in the domain.

One way to show that P(x) is not always true when x is

in the domain is to find a counterexample.

A single counter example is all we need to establish

that ∀ x P(x) is false.
19
 EXAMPLE
Let Q(x) be the statement “x < 2”. What is the truth
value of the quantification ∀ x Q(x), where the domain
consists of all real numbers?

Solution:
Q(x) is not true for every real number x
Counter Example:
Let x = 3
Q(3) is false
Thus,
∀ x Q(x) is false.

20
 EXAMPLE
What is the truth value of ∀ x P(x), where P(x) is the statement
“x2 < 10” and the domain consists of the positive integers not
exceeding 4?

Solution:
The statement ∀ x P(x) is the same as the conjunction
P(1) ∧ P(2) ∧ P(3) ∧ P(4)
P(1) is true
P(2) is true
P(3) is true
P(4) is false
P(4), which is the statement “42 < 10” is false,
Thus,
∀ x P(x) is false.
21
 EXAMPLE
a) What is the truth value of ∀ x (x2 ≥ x), if the domain
consists of all real numbers?
b) What is the truth value of ∀ x (x2 ≥ x), if the domain
consists of all integers?

a) Solution:
The universal quantification (x2 ≥ x) is not true for
every real number x
Counter Example:
Let x = ½
(1/2)2 ≥ (1/2) is false

22
 b) Solution:
The universal quantification (x2 ≥ x) is true for
all integers.

23
 EXISTENTIAL QUANTIFICATION
Definition: The existential quantification of a predicate P(x)
is the proposition ‘There exists a value x in the universe of
discourse such that P(x) is true.’

Notation:
We use the notation: ∃ x P(x), which is read ‘there exists x’.

If the universe of discourse is finite, say {n1,n2,…,nk}, then the

existential quantifier is simply the disjunction of the
propositions over all the elements
∃ x P(x) ⇔ P(n1) ∨ P(n2) ∨ … ∨ P(nk)

24
 Represented by an backwards E: ∃
It means “there exists”
Let P(x) = x+1 > x

We can state the following:

∃x P(x)
English translation: “there exists (a value of) x such that P(x) is
true”
English translation: “for at least one value of x, x+1>x is true”

25
 EXAMPLE
Let P(x) = x+1 > x universe of discourse is integars
There is a numerical value for which x+1>x
In fact, it’s true for all of the values of x!
Thus, ∃x P(x) is true

In order to show an existential quantification is true, you

only have to find ONE value

In order to show an existential quantification is false, you

have to show it’s false for ALL values

26
 EXAMPLE
Let P(x) be the statement “x > 3.” What is the truth
value of the quantification ∃ x P(x), where the domain
consists of all real numbers?

Solution:
P(x) is true for some values in domain
Counter Example:
Let x = 4
P(4) is true
Thus,
∃ x P(x) is true.

27
 EXAMPLE
Let Q(x) be the statement “x = x + 1.” What is the truth
value of the quantification ∃ x Q(x), where the domain
consists of all real numbers?

Solution:
Q(x) is false for every real number x.
Counter Example:
Let x = 6
Q(6) = 6 = 6 + 1 is false
Thus,
∃ x Q(x) is false.

28
 EXAMPLE
What is the truth value of ∃ x P(x), where P(x) is the statement
“x2 > 10” and the universe of discourse consists of the positive
integers not exceeding 4?

Solution:
The statement ∃ x P(x) is the same as the disjunction
P(1) ∨ P(2) ∨ P(3) ∨ P(4)
P(1) is false
P(2) is false
P(3) is false
P(4) is true
P(4), which is the statement “42 < 10” is true
Thus,
∃ x P(x) is true

29
 NOTE
Recall that P(x) is a propositional function
Let P(x) be “x == 0”
Recall that a proposition is a statement that is either true
or false
P(x) is not a proposition
There are two ways to make a propositional function into
a proposition:
Supply it with a value
For example, P(5) is false, P(0) is true
Provide a quantification
For example, ∀x P(x) is false and ∃x P(x) is true
◻ Let the universe of discourse be the real numbers

30
 QUANTIFIERS: Truth values
In general, when are quantified statements true or false?

Statement True when… False when...

There is an x for which
∀x P(x) P(x) is true for every x
P(x) is false
There is an x for which
∃x P(x) P(x) is false for every x
P(x) is true
 UNIQUENESS QUANTIFIER
The Uniqueness quantifier, denoted by ∃! or ∃1.

Notation:
∃! x P(x) [or ∃1 x P(x)] states “there exist a unique x such
that P(x) is true”

Other phrases for uniqueness quantification include “there is

exactly one” and “there is one and only one.”

32
 EXAMPLE
∃! x (x - 1 = 0), where the domain is the set of real
numbers.

Solution:
(x - 1 = 0) is true for a unique real number.
Counter Example:
Let x = 1
(x - 1 = 0) is true
Note:
Generally, uniqueness quantifier is avoided.
It is best to stick with existential and universal quantifier.

33
 QUANTIFIERS WITH RESTRICTED
DOMAINS
EXAMPLE:
What do statements ∀ x < 0 (x2 > 0),
∀ y ≠ 0 (y3 ≠ 0) and ∃z
> 0 (z2 =2)
SOLUTION:
The statement ∀ x < 0 (x2 > 0) states that for every real
number x with x < 0, x2 > 0.
That is, “the square of negative real number is positive.”
The statement is the same as:
∀ x (x < 0 → x2 > 0).

34
 The statement ∀ y ≠ 0 (y3 ≠ 0) states for every real
number y with y ≠ 0, we have (y3 ≠ 0).

That is, “the cube of every nonzero real number is

nonzero.”

This statement is equivalent to:

∀y(y ≠ 0 → y3 ≠ 0)

35
 The statement ∃ z > 0 (z2 =2) states that there exist a
real number z with z > 0 such that z2 =2.

That is, “There is a positive square root of 2.”

This statement is equivalent to:

∃ z (z > 0 ∧ z2 =2).

36
 NOTE:
The restriction of a universal quantification is the same as
the universal quantification of a conditional statement.
Example:
∀ x < 0 (x2 > 0) is another way of expressing
∀x (x < 0 → x2 > 0)
The restriction of existential quantification is the same as
the existential quantification of a conjunction.
Example:
∃ z > 0 (z2 =2) is another way of expressing
∃ z (z > 0 ∧ z2 =2)

37
 PRECEDENCE OF QUANTIFICATION
The quantifiers ∀ and ∃ have higher precedence than all
logical operators from propositional calculus.

Example:
∀ x P(x) ∨ Q(x) is the disjunction of ∀ x P(x) and
Q(x).

In other words,
It means
(∀ x P(x)) ∨ Q(x) rather than ∀ x (P(x) ∨ Q(x)).

38
 BINDING VARIABLES
When a quantifier is used on the variable x, we say that
the occurrence of the variable is bound.

An occurrence of a variable that is not bound by a

quantifier is said to be free.

The part of a logical expression to which a quantifier is

applied is called the scope of this quantifier.

39
 EXAMPLE
In the statement ∃ x (x + y =1),

The variable x is bound to by the existential quantification

∃ x.

The variable y is free because it is not bound by a quantifier.

∃ x (x + y =1), x is bound, but y is free.

40
 EXAMPLE
In the statement ∃x (P(x) ∧ Q(x)) ∨ ∀x R(x), all
variables are bound.

The scope of the first quantifier, ∃x, is the expression

(P(x) ∧ Q(x))
The scope of the second quantifier, ∀x is the expression
R(x)
That is, the existential quantifier binds the variable x in
P(x) ∧ Q(x)
Universal quantifier binds the variable x in R(x).

41
 EXAMPLES
(∃x P(x)) ∨ Q(x)
The x in Q(x) is not bound; thus not a proposition

(∃x P(x)) ∨ (∀x Q(x))

Both x values are bound; thus it is a proposition

∃x (P(x) ∧ Q(x)) ∨ (∀y R(y))

All variables are bound; thus it is a proposition

(∃x P(x) ∧ Q(y) ∨ (∀y R(y))

The y in Q(y) is not bound; this not a proposition
42
 BINDING VARIABLES
Let P(x, y) be x > y

Consider: ∀x P(x, y)
This is not a proposition!
What is y?
If it’s 5, then ∀x P(x, y) is false
If it’s x-1, then ∀x P(x, y) is true

Note that y is not “bound” by a quantifier

43
LOGICAL EQUIVALENCES INVOLVING
QUANTIFIERS
Two statements S and T involving predicates and
quantifiers are logically equivalent if and only if they have
the same truth value regardless of the interpretation,
i.e. regardless of
The meaning that is attributed to each propositional function.
The domain of discourse.

Notation:
We use the notation S ≡ T to indicate that two
statements S and T involving predicates and quantifiers
are logically equivalent.

44
 EXAMPLE
Is ∀x (P(x) ∧ Q(x)) logically equivalent to ∀x P(x) ∧ ∀x
Q(x)?
where the same domain is used throughout.

Solution:
Use two steps
If ∀x (P(x) ∧ Q(x)) is true, then ∀x P(x) ∧ ∀x Q(x) is true
Proof: Suppose ∀x (P(x) ∧ Q(x)) is true.
Then if a is in the domain, P(a) ∧ Q(a) is true,
So P(a) is true and Q(a) is true.
So, if a is in the domain P(a) is true, which is the same as ∀x P(x) is true;
and similarly, we get that ∀x P(x) is true
45
 TRANSLATING FROM ENGLISH INTO
LOGICAL EXPRESSIONS
Example: Express the statement using predicates and
quantifiers.
“Every student in this class has studied calculus”

Solution:
Step 1: First we rephrase the statement so that we can
clearly identify the appropriate quantifiers to use.
“For every student in this class, that student has studied
calculus.”

Step 2: Introduce a variable x

“For every student x in this class, x has studied calculus”
46
 Step 3: Introduce C(x)
C(x) = x has studied calculus.
Domain = Students in the class.

Step 4:
∀x C(x)

47
 EXAMPLE
Express the statement using predicates and quantifiers.

“For every person x, If person x is a student in this class then x

has studied calculus.”

Solution:
Step 1:
Step 2:
Step 3: Introduce S(x) and C(x)
S(x) = Person x is in the class.
C(x) = x has studied Calculus.
Domain = Students in the class.
Step 4:
∀x (S(x) → C(x))
48
 EXAMPLE
Express the statement using predicates and quantifiers.
“Some student in this class has visited Mexico”

Solution:
Step 1: First we rephrase the statement so that we can
clearly identify the appropriate quantifiers to use.
“There is a student in this class with the property that the
student has visited Mexico”

Step 2: Introduce a variable x

“There is a student x in this class having the property that
x has visited Mexico”
49
 Step 3: Introduce M(x)
M(x) = x has visited Mexico.
Domain = Students in the class.

Step 4:
∃ x M(x)

50
 EXAMPLE
Express the statement using predicates and quantifiers.

“There is a person x having the properties that x is a student

in this class and x has visited Mexico.”

Solution:
Step 1:
Step 2:
Step 3: Introduce S(x) and M(x)
S(x) = x is a student in this class.
M(x) = x has visited Mexico.
Domain = All person.
Step 4:
∃ x (S(x) ∧ M(x))
51
 EXAMPLE
Express the statement using predicates and quantifiers.

“For every x in this class, x has the property that x has visited
Mexico or x has visited Canada.”

Solution:
Step 1:
Step 2:
Step 3: Introduce C(x) and M(x)
C(x) = x has visited Canada.
M(x) = x has visited Mexico.
Domain = All people.
Step 4:
∀ x (C(x) ∨ M(x))
52
 EXAMPLE
Express the statement using predicates and quantifiers.

“For every person x, if x is a student in this class, then x has visited

Mexico or x has visited Canada.”

Solution:
Step 1:
Step 2:
Step 3: Introduce S(x) and M(x)
S(x) = x is a student in this class.
C(x) = x has visited Canada.
M(x) = x has visited Mexico.
Domain = student in the class.
Step 4:
∀ x (S(x) → (C(x) ∨ M(x))).
53
 EXAMPLES FROM LEWIS CARROL
Consider these statements. The first two are called
premises and the third is called the conclusion. The entire
set is called an argument.

“All lions are fierce.”

“Some lions do not drink coffee.”
Therefore,
“Some fierce creatures do not drink coffee.”

54
 SOLUTION
Let
P(x) = “x is a lion.”
Q(x) = “x is fierce.”
R(x) = “x drinks coffee.”
Domain = Assume all creatures.

We can express these statements as:

“All lions are fierce.”
∀x (P(x) → Q(x)).

55
 “Some lions do not drink coffee.”
∃x (P(x) ∧ ¬R(x)).

“Some fierce creatures do not drink coffee.”

∃x (Q(x) ∧ ¬R(x)).

56
 MORE EXAMPLES
Translate the statements:
“All hummingbirds are richly colored”
“No large birds live on honey”
“Birds that do not live on honey are dull in color”
“Hummingbirds are small”

Solution:
Assign propositional functions

Let
P(x) = “x is a hummingbird”
Q(x) = “x is large”
R(x) = “x lives on honey”
S(x) = “x is richly colored”

Let our universe of discourse be all birds

57
 Translate the statements:
Assume that “small” is the same as “not large” and that
“dull in color” is the same as “not richly colored”

“All hummingbirds are richly colored”

∀x (P(x)→S(x))

“No large birds live on honey”

¬∃x (Q(x) ∧ R(x))
Alternatively: ∀x (¬Q(x) ∨ ¬R(x))

“Birds that do not live on honey are dull in color”

∀x (¬R(x) → ¬S(x))

“Hummingbirds are small”

∀x (P(x) → ¬Q(x))

58
NEGATING QUANTIFIED EXPRESSIONS
Consider the statement:
“Every student in your class has taken a course in
calculus.”

P(x) = x has taken a course in calculus.

Domain = Students in your class.
∀x P(x)

59
 The negation of this statement is
“It is not the case that every student in your class has
taken a course in calculus.”

This is equivalent to
“There is a student in your class who has not taken a
course in calculus.”
∃x ¬P(x)

60
 This example illustrate the following logical equivalence:
¬∀x P(x) ≡ ∃x ¬P(x)

61
 NOTE
First note that ¬∀x P(x) is true if and only if ∀x P(x) is
false.

Note that ∀x P(x) is false if and only if there is an

element x in domain for which P(x) is false.

Finally, note that there is an element x in the domain for

which ¬ P(x) is true if and only if ∃x ¬P(x) is true.

Putting these steps together, we can conclude that:

¬∀x P(x) is true if and only if ∃x ¬P(x) is true.

62
 It follows that ¬∀x P(x) and ∃x ¬P(x) are logically
equivalent.

63
 Another example illustrate that following logical
equivalence:
¬∃x Q(x) ≡ ∀x ¬Q(x)

64
 EXAMPLE
What are the negations of the statements:
“There is an honest politician”

Solution:
H(x) = x is a honest.
Domain = all politician
∃x H(x)
The negation of this statement is
¬∃x H(x) = ∀x ¬H(x)
“Every politician is dishonest.”

65
 EXAMPLE
What are the negations of the statements:
“All Americans eat cheeseburgers”

Solution:
C(x) = x eats cheeseburgers.
Domain = all Americans
∀x C(x)
The negation of this statement is
¬∀x C(x) = ∃x ¬C(x)
“Some Americans does not eat cheeseburgers.”

66
 EXAMPLE
What are negations of the statement:
∀x (x2 > x)

Solution:
The negation of ∀x (x2 > x) is the statement ¬∀x (x2 >
x)
¬∀x (x2 > x) = ∃x ¬(x2 > x)
This can be re-written as:
∃x (x2 ≤ x)

67
 EXAMPLE
What are negations of the statement:
∃x (x2 = 2)

Solution:
The negation of ∃x (x2 = 2) is the statement ¬∃x (x2 =
2)
¬∃x (x2 = 2) = ∀x ¬(x2 = 2)
This can be re-written as:
∀x (x2 ≠ 2)

68
 EXMPLE
Show that ¬∀x (P(x)→Q(x)) and ∃x (P(x) ∧ ¬Q(x)) are
logically equivalent.

Solution:
≡ ¬∀x (P(x)→Q(x)) Given
≡ ∃x ¬(P(x)→Q(x)) De Morgan’s law for universal
quantifiers
≡ ∃x ¬(¬P(x) ∨ Q(x)) As we know that p → q = ¬p
∨q
≡ ∃x (¬(¬P(x)) ∧ ¬Q(x)) De-Morgan’s law
≡ ∃x (P(x) ∧ ¬Q(x)) Double Negation law
≡ R.H.S
69
 EXMPLE
Express the negation of ∀x∃yP(x,y) ∨ ∀x∃yQ(x,y).

Solution:

≡ ¬(∀x∃yP(x,y) ∨ ∀x∃yQ(x,y)) Given

≡ ¬(∀x∃yP(x,y) ∧ ¬∀x∃yQ(x,y) De Morgan’s law
≡ ∃x¬∃yP(x,y) ∧ ∃x¬∃yQ(x,y) De Morgan’s law
≡ ∃x∀y ¬P(x,y) ∧ ∃x∀y ¬Q(x,y) De-Morgan’s law

70
 LOGIC PROGRAMMING
An important type of programming language is designed
to reason using the rules of predicate logic.

Prolog (Programming in Logic)

Developed in 1970s by computer scientists working in

the area of artificial intelligence.

71