Discrete Mathematics
College of Computer Science & Engineering
Computer Science & AI Department
All slides' contents are adapted from the book Discrete Mathematics and its Applications by Rosen, 8th edition.
1
The Foundations:
Logic and Proofs
Chapter 1
2
The Foundations:
Logic and Proofs
Chapter 1 : Section 1.4
Predicates and Quantifiers
3
Outline
Predicates
Quantifiers
Quantifiers over finite domains
Quantifiers with Restricted Domains
Precedence of Quantifiers
Binding Variables
Logical Equivalences Involving Quantifiers
Negating Quantified Expressions
Translating from English into Logical Expressions
Using Quantifiers in System Specifications
4
1 Predicates
5
Predicates (Propositional
Functions)
“x is greater than 3”
This statement is neither true nor false when the value of the
variable is not specified.
This statement has two parts:
The first part (subject of the statement) is the variable x.
The second (predicate) is “is greater than 3”, refers to a
property that the subject of the statement can have.
6
6
Predicates (Propositional
Functions)
We can denote this statement by P(x), where P denotes the
predicate “is greater than 3”, and x is the variable
Once a value has been assigned to x, the statement P(x)
becomes a proposition and has a truth value.
P(x) is called the Propositional function P at x.
7
Predicates (Propositional
Functions)
Propositional functions become propositions (and have truth values)
when their variables are each replaced by a value from the domain.
The statement P(x) is said to be the value of the propositional
function P at x.
For example, let P(x) denote “x > 0” and let the domain be the set of
integers. Then:
P(-3) is false
P(0) is false
P(3) is true
Often the domain is denoted by U. So in this example U is the set of
integers.
8
Examples of Propositional Functions
Let “x + y = z” be denoted by R(x, y, z) and U (for all three variables) be the set of
integers. Find these truth values:
R(2,-1,5)
Solution: F
R(3,4,7)
Solution: T
R(x, 3, z)
Solution: Not a Proposition
Now let “x - y = z” be denoted by Q(x, y, z), with U as the set of integers. Find
these truth values:
Q(2,-1,3)
Solution: T
Q(3,4,7)
Solution: F
Q(x, 3, z)
Solution: Not a Proposition 9
Predicates (Propositional
Functions)
Let P(x) denote “x is greater than 3”. What are the truth values
of P(4) and P(2)?
Let Q(x,y) denote “x = y+3”. What are the truth values of Q(1,2)
and Q(3,0)?
Let A(c,n) denote “computer c is connected to network n”,
suppose that the computer MATH1 is connected to network
CAMPUS2, but not to network CAMPUS1. What are the truth
values of: A(MATH1, CAMPUS1) and A(MATH1, CAMPUS2) ?
More examples and solutions in your book pages 41 and 42
10
Predicates (Propositional
Functions)
Propositional functions (Predicates) occur in
computer programs:
If (x>0) then x:=x+1
P(x) : “x>0”
If P(x) is true the assignment is executed.
If P(x) is false the assignment is not executed.
See example 7 in your book page 43
11
Compound Expressions:
Examples
Connectives from propositional logic carry over to predicate logic.
If P(x) denotes “x > 0,” find these truth values:
P(3) ∨ P(-1) Solution: T
P(3) ∧ P(-1) Solution: F
P(3) → P(-1) Solution: F
P(-1) → P(3) Solution: T
Expressions with variables are not propositions and therefore do not
have truth values. For example,
P(3) ∧ P(y)
P(x) → P(y)
12
Propositional Logic Not
Enough
If we have:
“All men are mortal.”
“Socrates is a man.”
Does it follow that “Socrates is mortal?”
Can’t be represented in propositional logic. Need a language
that talks about objects, their properties, and their relations.
13
Predicate Logic/Calculus
Some people are killers. All killers are evil. Therefore, some people are evil.
Try translating it to Propositional Logic.
Obviously, Propositional Logic can’t capture the subtle structure of this
argument.
A more powerful formalism that will let us capture sentences like the one
above is the Predicate Logic.
14
Introducing Predicate Logic
Predicate logic uses the following new features:
– Variables x, y, z
– Predicates P(x), M(x)
– Quantifiers
Propositional functions are a generalization of
propositions.
– They contain variables and a predicate, e.g., P(x).
– Variables can be replaced by elements from their domain.
15
2
Quantifiers
16
Predicate Logic (Calculus)
\
There are three main features that will distinguish
Predicate Logic from Propositional Logic:
– Variables: range over our particular domain of interest. We will
use lowercase letters starting from x, y, z, . . . etc.
– Predicates: Predicates are special functions that we will use to
state facts about the variables. We will use uppercase letters for
those, like P,Q, R, . . . etc.
– Quantifiers: used to state how many members of our domain of
interest are affected by a particular formula. For these we will
have special symbols.
17
Quantification
We need quantifiers to express the meaning of English
words including all and some:
“All men are Mortal.”
“Some cats have fur.”
The two most important quantifiers are:
Universal Quantifier, “For all,” symbol:
Existential Quantifier, “There exists,” symbol:
We write as in x P(x) and x P(x).
x P(x) asserts P(x) is true for every x in the
domain.
x P(x) asserts P(x) is true for some x in the domain.
18
Universal Quantifier:
Tells
us that a predicate is true for every element under consideration
( Domain / Universe of discourse).
The universal quantification of P(x) is the statement: “P(x) for all values
of x in the domain”
x P(x) read as “for all x P(x)” or “for every x P(x)”
is called universal quantifier .
An element for which P(x) is false is called a counterexample to ∀xP(x).
19
Universal Quantifier: Example
In our example:
If we let, K represents “is a killer ” and E represents “is
evil”, then we can write the sentence “all killers are evil” as:
x (K(x) E(x));
which basically states that, for all people, it is true that if a
person is a killer, then that person is evil.
20
Existential Quantifier
Tells us that: there is one or more elements under consideration for
which the predicate is true.
The Existential Quantification of P(x) is the statement “there exists
an element x in the domain such that P(x)”
x P(x) read as “there is an x such that P(x)” or “there is at least one
x such that P(x)” or “for some x P(x)” .
is called Existential Quantifier.
21
Existential Quantifier:
In our example :
The sentence: “some people are killers” can be written as:
x (K(x));
which basically states that, there is at least one person who
is a killer.
22
Quantifiers
Now, we can translate the whole argument into a predicate logic
formula.
“Some people are killers. All killers are evil. Therefore, some people
are evil.”
It can be stated as:
x (K(x)),
x (K(x) E(x)),
x (E(x))
23
Quantifiers and Truth Values
x P(x)
True when: P(x) is true for every x.
False when: there is an x for which P(x) is false.
x P(x)
True when: There is an x for which P(x) is true
False when: P(x) is false for every x.
24
Domain of discourse/Universe of
discourse/ Domain
Note:
The domain specifies the possible values of the variable x. The
meaning of the quantification of P(x) changes when we change the
domain. The domain must always be specified when a quantifier is
used; without it, quantification of a statement is not defined.
25
Universal Quantifier: Examples
x P(x) is read as “For all x, P(x)” or “For every x, P(x)”
Examples:
If P(x) denotes “x > 0” and U is the integers, then x P(x) is false.
If P(x) denotes “x > 0” and U is the positive integers, then x P(x) is
true.
If P(x) denotes “x is even” and U is the integers, then x P(x) is false.
26
Existential Quantifier: Examples
x P(x) is read as “For some x, P(x)”, or as “There is an x such that P(x),” or “For
at least one x, P(x).”
Examples:
If P(x) denotes “x > 0” and U is the integers, then x P(x) is true. It is also true
if U is the positive integers.
If P(x) denotes “x < 0” and U is the positive integers, then x P(x) is false.
If P(x) denotes “x is even” and U is the integers, then x P(x) is true.
27
More examples for
Universal
quantifier
28
Example 1
Let Q(x) be “x<2” . What is the truth value of x Q(x) when the
domain consists of all real numbers?
Q(x) is not true for every real number x, for example Q(3) is
false.
x =3 is a counterexample for the statement x Q(x). Thus, x
Q(x) is false.
29
Example 2
Example:
What is the truth value of x (x2 x) when the domain consists of:
a) all real numbers?
b) all integers?
Solution:
c) is false because (0.5)2 0.5 , x2 x is false for all real numbers
in the range 0< x <1 .
d) is true because there are no integer x with 0 < x < 1.
30
Example 3
Example:
Let Q(x) be “x2>0”. What is the truth value of ∀ x Q(x) when the
domain consists of all integer numbers?
Q(x) is not true for every integer number x, for example Q(0) is
false.
x =0 is a counterexample for the statement x Q(x). Thus, x Q(x)
is false.
More examples in the book on page 45
31
More examples for
Existential
quantifier
32
Example 1
Example:
Let Q(x) be “x=x+1”. What is the truth value of x Q(x) when the
domain consists of all real numbers?
Q(x) is false for every real number.
Thus, x Q(x) is false.
33
Example 2
Example:
Let Q(x) be “x>3”. What is the truth value of x Q(x) when the
domain consists of all real numbers?
Q(x) is sometimes true , for example Q(4) is true.
Thus, x Q(x) is true.
34
The uniqueness
quantifier
35
The uniqueness quantifier
Uniqueness Quantifier ∃! or ∃1
The notation ∃!x P(x) (or ∃1x P(x)) denotes the
uniqueness quantification of P(x). We read ∃!x P(x) as
“there exists a unique x such that P(x) is true”, or
“there is exactly one ”, or
“there is one and only one”.
36
The uniqueness quantifier
Uniqueness Quantifier ∃! or ∃1
Examples:
1. If P(x) denotes “x - 1 = 0” and U is the
integers, then !x P(x) is true.
2. But if P(x) denotes “x > 0,” then !x P(x) is
false.
37
Quantifiers over
3
finite domains
38
Quantifiers over finite domains
Note that: x Q(x) is false if there is no element in the
domain for which Q(x) is true or the domain is empty.
When all the elements in the domain can be listed (finite
domain):
x1, x2, x3, x4, ……., xn :
– x Q(x) is the same as the conjunction:
Q(x1) Q(x2) …. Q(xn)
– x Q(x) is the same as the disjunction:
Q(x1) Q(x2) …. Q(xn)
39
Quantifiers over finite domains
Example:
Let Q(x) be “x2<10”. What is the truth value of x Q(x)
when the domain consists of the positive integers not exceeding 4?
x Q(x) is the same as the conjunction:
Q(1) Q(2) Q(3) Q(4).
Q(4) is false. Thus, x Q(x) is false.
40
Quantifiers over finite domains
Example:
Let Q(x) be “x2<10”. What is the truth value of x Q(x), when the
domain consists of the positive integers not exceeding 4?
x Q(x) is the same as the disjunction:
Q(1) Q(2) Q(3) Q(4).
Q(1), Q(2), Q(3) are true. Thus, x Q(x) is true.
Also check example 16 page 47
41
Connections between quantifications
and looping
If the domain consists of n (finite) objects and we need to
determine the truth value of:
∀x Q(x)
Loop through all n values of x to see if Q(x) is always true.
If you encounter a value x for which Q(x) is false, exit the loop
with ∀x Q(x) is false.
Otherwise ∀x Q(x) is true.
∃x Q(x)
Loop through all n values of x to see if Q(x) is true.
If you encounter a value x for which Q(x) is true, exit the loop
with ∃x Q(x) is true.
Otherwise ∃x Q(x) is false.
42
The domain
Note:
Generally, an implicit assumption is made that all domains of discourse for
quantifiers are nonempty.
If the domain is empty, then ∀x P(x) is true for any propositional function P(x),
because there are no elements x in the domain for which P(x) is false.
If the domain of discourse is empty, then ∃x Q(x) is false whenever Q(x) is a
propositional function, because when the domain is empty, there can be no element
x in the domain for which Q(x) is true.
43
The domain
Note:
A domain of discourse must always be specified when a statement ∃x
P(x) is used.
Furthermore, the meaning of the statement ∃x P(x) changes when the
domain changes.
Without specifying the domain of discourse, the statement ∃x P(x) has no
meaning.
44
Infinite domains
The truth value of x P(x) and x P(x) depends on both the propositional function
P(x) and on the domain U.
Examples:
If U is the positive integers and P(x) is the statement “x < 2”, then x P(x) is true, but x P(x) is
false.
If U is the negative integers and P(x) is the statement “x < 2”, then both x P(x) and x P(x) are
true.
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.
45
Quantifiers with
4
restricted domain
46
Quantifiers with restricted
domain
What do these statements mean (domain real)
∀x<0 (x2>0) same as ∀x (x<0 x2>0)
“the square of a negative real number is positive”
∀y0 (y3 0) same as ∀y(y0 y3 0)
“the cube of every nonzero real number is nonzero”
∃z >0 (z2=2) same as ∃z(z>0 z2=2)
“there is a positive square root of 2”
47
5 Precedence of Quantifiers
48
Precedence of Quantifiers
The quantifiers and have higher precedence than all the logical
operators .
x P(x) ∨ Q(x) means (x P(x)) ∨ Q(x) .
x (P(x) ∨ Q(x)) means something different.
49
6 Binding Variables
50
Binding Variables
When a quantifier is used on the variable x, we say that this occurrence of the
variable is bound.
All variables that occur in a propositional function must be bound or equal to a
particular value to turn it into a proposition.
x (x + y =1)
The variable x is bounded by the existential quantification x and the variable
y is free.
51
Binding Variables
x (P(x) Q(x)) x R(x)
All variables are bounded.
The scope of:
the first quantifier x is the expression P(x)Q(x),
the second quantifier x is the expression R(x).
Existential quantifier binds the x in P(x)Q(x)
Universal quantifier binds the x in R(x).
52
Again…
x ( x y 1)
Bound free
variable variable
x( P ( x) Q( x)) xR ( x)
Scope of the existential quantifier Scope of the universal
quantifier
53
Logical Equivalences
7
Involving Quantifiers
54
Logical Equivalence involving
Quantifiers
Statements involving predicates and quantifiers are logically
equivalent iff they have the same truth value.
Show that ∀x (P(x) Q(x)) ∀x P(x) ∀x Q(x)
_______________________________________________________
Suppose that ∀x (P(x) Q(x)) is true, this means that if a is in the
domain; then (P(a) Q(a)) is true.
Hence, both P(a) and Q(a) are true for every element in the domain.
So, ∀x P(x) and ∀x Q(x) are both true.
This means that ∀x P(x) ∀x Q(x) is true.
55
Next
suppose that ∀x P(x) ∀x Q(x) is true, it follows that both
∀x P(x) and ∀x Q(x) are true hence, if a is in the domain then
P(a) is true and Q(a) is true
This means that ∀x (P(x) Q(x)) is true.
Now we can conclude that
∀x (P(x) Q(x)) ∀x P(x) ∀x Q(x)
56
Logical Equivalences with
Quantifiers
x ( P( x) Q( x)) xP( x) xQ( x)
x ( P ( x) Q( x)) xP ( x) xQ( x)
But, what about these:
x ( P ( x) Q( x)) xP ( x) xQ ( x) ? False
x ( P ( x) Q( x)) xP ( x) xQ ( x) ? False
57
Negating Quantified
8
Expressions
58
Negating Quantified Expressions
“Every student in this class has taken a calculus course”
x P(x)
Where:
P(x) is “x has taken a calculus course”
Domain = “Students in class”
Negation is:
“It is not the case that every student in your class has taken a calculus course.”
This implies that:
“There is a student in your class who has not taken calculus.”
x P(x)
i.e.,
x P(x) x P(x)
59
Negating Quantified Expressions
Now Consider x J(x):
“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 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.
60
De Morgan’s laws for quantifiers
When the domain of a predicate Q(x) consists of n elements
x1, x2 ,x3, x4, ……., xn
∀x Q(x) is the same as the conjunction
Q(x1) Q(x2) …. Q(xn)
∀x Q(x) is the same as the disjunction
Q(x1) Q(x2) …. Q(xn) x P(x)
∃x Q(x) is the same as the disjunction
Q(x1) Q(x2) …. Q(xn)
∃x Q(x) is the same as the conjunction
Q(x1) Q(x2) …. Q(xn) x P(x)
De Morgan’s Laws for Quantifiers:
x P(x) x P(x)
x P(x) x P(x)
61
Negating Quantified Expressions
The rules for negating quantifiers are:
62
Negating Quantified Expressions
What are the negations of:
∀x (x2>x)
∃x (x2=x)
Solutions:
∀x (x2>x)
∀x (x2>x) ∃x (x2>x) ∃x (x2 x)
∃x (x2=x)
∃x (x2=x) ∀x (x2=x) ∀x (x2 x)
63
Negating Quantified Expressions
Show that: ∀x [P(x) Q(x)] ∃x [P(x) Q(x)]
Solution:
∀x [P(x) Q(x)] ∃x [P(x) Q(x)] Negating
Quantifiers
∃x [P(x) Q(x)] Implication rule
∃x [ P(x) Q(x)] DeMorgan’s law
∃x [P(x) Q(x)] Double Negation
law
Recall that:
( p q) p q
64
Translating from English
9
into Logical Expressions
65
Translating from English into Logical
Expressions
Express the statement “Every student in the class has studied
calculus” using predicates and quantifiers.
First: Rewrite the statement: “For every student in the class, that
student has studied calculus”.
Next: Introduce the variable x, “For every student x in the class, x
has studied calculus”.
Then: Introduce C(x): “x has studied calculus”.
If the domain for x consists of the students in the class,
We can translate our statement as x C(x).
66
Translating from English into Logical
Expressions
If we change the domain to consist of all people;
We need to express our statement as:
“For every person x, if person x is a student in this class, then
x has studied calculus”
C(x): “x has studied calculus”
S(x): “person x is a student in the class”
x (S(x) C(x))
Caution:
our statement cannot be expressed as:
x (S(x) C(x));
Which means: “All people are students in this class and have
studied calculus”. 67
Translating from English into Logical
Expressions
Finally, when we are interested in the background of people in
subjects besides calculus, we may prefer to use the two - variable
quantifier Q(x , y).
For the statement:
“ Student x has studied subject y”
Then, we would replace C(x) by Q(x , calculus) in both approaches
to obtain:
x Q(x , calculus) Domain: students
in this class
or
x (S(x) Q(x , calculus)) Domain: All
people 68
Translating from English into Logical
Expressions
Express the statement “Some student in this class has visited
Bahrain” using predicates and quantifiers.
First: Rewrite the statement “There is a student in this class with
the property, that student visited Bahrain”.
Next: Introduce the variable x, “There is a student x in this class
having the property that x has visited Bahrain”.
Then: Introduce M(x): “x has visited Bahrain”.
If the domain for x consists of the students in the class,
We can translate our statement as: x M(x)
69
Translating from English into Logical
Expressions
If we are interested in people other than in this class, we look the
statement as:
“There is a person x having the properties that x is
a student in this class and x has visited Bahrain”;
In this case, the domain for the variable x consists of all people.
Let S(x): “x is a student in this class”
x (S(x) B(x)).
Caution:
This statement cannot be expressed as: x (S(x) B(x))
Which is true when there is someone not, in the class, because in this
class for such a person x,
S(x) B(x), becomes either FT or FF,
both of which are true !
Check the third case in page 53 (exercise 24)
70
Translating from English into Logical
Expressions
P ( x) x is a humming bird
Q( x) x is large bird Universe of
discourse is all birds.
R ( x) x lives on honey
S ( x) x is richly colored
“All humming birds are richly colored” x ( P( x) S ( x))
“No large birds live on honey” x (Q( x) R( x))
“Birds that do not live on honey
are dull in color” x ( R( x) S ( x))
“Humming birds are small” x ( P( x) Q( x))
71
Using quantifiers in
10
systems specifications
72
Using Quantifiers in System
Specifications
Express the statement “Every mail message larger than one
megabyte will be compressed” using predicates and quantifiers.
Let S(m,y): “Mail message m is larger than y megabytes”, where m
has the domain of all mail messages and y is a positive real number.
Let C(m): “Mail message m will be compressed”
m (S(m,1) C(m))
73
Using Quantifiers in System
Specifications
Express the statement “If a user is active, at least one network link
will be available” using predicates and quantifiers.
Let A(u): “user u is active” , where u has the domain of all users.
Let S(n,x): “network link n is in state x” , where n has the domain of
all network links and x has the domain of all possible states for a
network link.
u A(u) n S(n, available)
74
Summary
Predicates
Quantifiers
Quantifiers over finite domains
Quantifiers with Restricted Domains
Precedence of Quantifiers
Binding Variables
Logical Equivalences Involving
Quantifiers
Negating Quantified Expressions
Translating from English into
Logical Expressions
Using Quantifiers in System
Specifications
75
Reference
• Textbook: “Discrete Mathematics and Its
Applications”, by Kenneth Rosen, 8th ed.
Chapter 1.4: Predicates and quantifiers
76
