PREDICATES AND QUANTIFIERS

MATH-2305 Discrete Mathematics

1
Truth Verification of those Statements
that are not Propositions
There are no rules in propositional logic that
allow to conduct the truth value of the
following statements:
There is at least one student in this
classroom who took three Calculus classes
x+7=10
Each computer in this classroom is connected
to the network
y is a student
2
Predicates
Statements like
x+7=10
y is a student
x 3
have two parts.
The first part, a variable, is the subject of the
statement
The second part is the predicate. It refers to a
property that the subject of the statement may
have
3
4
Predicates
Predicate is a dual-purpose term
On the one hand, a predicate is a property or
description of subjects. The following predicates
are all shown in red and bold:
James is tall.
The bridge is long.
19 is a prime number.
On the other hand, a predicate is also used as a
synonym of a propositional function, where the
description is related not to a certain subject, but
to a variable.

Predicates and
Propositional Functions
If a statement depends on a variable, this
statement is called a propositional function (often
a propositional function itself is called a
predicate)
We can denote such a statement by .
Once a value has been assigned to the variable x,
the statement becomes a proposition,
which has a truth value.
is also referred to as 1-place predicate or
simply a predicate
5
( )
P x
( )
P x
( )
P x
6
Multivariable Propositional Functions
Multivariable propositional functions depend on
more than one variable. For example,
x is taller than y
a is greater than one of b, c
x is at least n inches taller than y
x+y=z
x and y are students
n-ary Predicates
A multivariable propositional function depends
on more than one variable. For example, the
propositional function x+y=z depends on 3
variables.
Once some values have been assigned to the
variable x, y, z, the statement x+y=z
becomes a proposition, which has a truth value.
A statement of the form is called a
n-place predicate or n-ary predicate.

7
( )
1 2
, ,...,
n
P x x x
Propositional Functions and
Programming
Propositional functions are widely used in
computer programming and algorithm design for
branching programs and algorithms
If <propositional function(x, y, z)>
then <statement>
else <statement>
If (((x>0) and (x<y)) or (y>z))
then <statement>
else <statement>
8
Precondition and Postcondition
Precondition is a statement that describes a valid
input of some algorithm or program segment
Postcondition is a statement that the output of
some algorithm or program segment should
satisfy when the algorithm (the program
segment) has run
Preconditions and Postconditions are widely used
to verify the correctness of algorithms and
programs
9
Precondition and Postcondition
Example. Let we need to swap the values of
two variables x and y.
Algorithm: temp := x ; x := y; y := temp
Precondition: (x=a) & (y=b)
Postcondition: (x=b) & (y=a)

:= means set to x := y means set x equal to y
10
11
Semantics
If logical propositions are to have meaning, they need
to describe something. Up to now, propositions such
as Johnny is tall, Debbie is 5 years old, and
x
2
=-1 had no intrinsic meaning. Either they are true
or false, but no more.
In order to make such propositions and propositional
functions meaningful, we need to have a domain
(or universe) of discourse, (or simply domain
(or universe)) i.e. a collection of subjects about which
the propositions relate.
Question: What are the domains for the three
propositions above?

12
Semantics
Question: What are the domains for the following
propositions and propositional functions?
Johnny is tall, Debbie is 5 years old
Possible answers: {Johnny, Debbie}; {People in the
world}; {People leaving in Texarkana}, etc.
x
2
=-1
Possible answers: C the set of complex numbers;
R the set of real numbers, Z the set of integer
numbers
Depending on the particular domain, a proposition
may be true or false

Semantics
Semantics is very important in computer
programming
Each data structure and even each single variable
that are used in a computer program always have
their domain of discourse (type).
For example, a variable x can be declared as real
or integer or byte or char.
Depending on this declaration, such expressions
as x=3.5, x=5, x=Class, x=-1 can be meaningful
and acceptable or not.
13
Quantifiers
There are statements, which assert that some
property is true for all values of a variable in a
particular domain (Each student in this
classroom takes the Discrete Math course in Fall
semester 2012).
There are also statements, which assert that
there is an element in a particular domain with a
certain property (There is at least one person in
this classroom who is not a student).
Such statements can be formulated using
quantifiers
14
15
Quantifiers
There are two quantifiers
Universal Quantifier
reads for all or Each or Every
Existential Quantifier
- reads there exists or there is at least
one
A quantifier is placed in front of a
propositional function and binds it to obtain a
proposition with semantic value.
Quantifiers
A statement (propositional function) P(x) is quantified
if there is a quantifier in a front of it, which is applied
to it:

x P(x) is TRUE if P(x) is true for every single x.
x P(x) is FALSE if there is an x for which P(x) is false.

-x P(x) is TRUE if there is an x for which P(x) is true.
-x P(x) is FALSE if P(x) is false for every single x.
16
( ) ( )
x P X x P X -
Quantifiers
The truth table for quantifiers

17
The Truth Table for Quantifiers
Statement When True? When False?

P(x) is true
for every x

There is an x for
which P(x) is false


There is an x for
which P(x) is true

P(x) is false
for every x

( )
x P X -
( )
x P X
18
The Universal Quantifier
x P (x) is true when every instance of x makes
P (x) true when plugged in
Like conjunctioning over entire domain of P (x)
x P (x ) P (x
1
) .P (x
2
) . P (x
3
) .

Example: Each non-negative real number has a
square root
19
Existential Quantifier
-x P (x) is true when an instance can be found
which when plugged in for x makes P (x) true
Like disjunctioning over entire domain of P (x)
-x P (x ) P (x
1
) vP (x
2
) vP (x
3
) v

Example: There exist a complex number whose
square is a negative real number
(i
2
=-1, i is an imaginary unity)

20
Multivariate Quantification
Quantification involving only one variable is
fairly straightforward. Just a bunch of ORs or
a bunch of ANDs.
When two or more variables are involved each
of which is bound by a quantifier, the order of
the binding is important and the meaning
often requires some thought.
23
Parsing Example
Question: If the domain for x, y, and z is the natural
numbers {0,1,2,3,4,5,6,7,} whats the truth
value of -xy -z P (x,y,z ); P (x,y,z ) = y - x z ?

Answer: True.
For any exists we need to find a positive
instance.
Since x is the first variable in the expression and
is existential, we need a number that works for
all other y, z. Set x = 0 (want to ensure that y -x
is not too small).
Now for each y we need to find a positive
instance z such that y - x z holds. Plugging in
x = 0 we need to satisfy y z so set z = y.

24
Parsing Example
Question: If the domain for x, y, and z is the natural
numbers {0,1,2,3,4,5,6,7,} , did we have to set z
= y to ensure that -xy -z P (x,y,z );
P (x,y,z ) = y - x z is true?
Answer: No. Could also have used the constant
z = 0. There are other valid solutions.



25
Parsing Example
Question: Isnt it simpler to satisfy -x y -z (y - x z )
by setting x = y and z= 0 ?

Answer: No, this is illegal ! The existence of x comes
before we know about y. I.e., the scope of x is
higher than the scope of y . So we have to find first
such x that does not depend on y. Thus, it is illegal
to choose x depending on y.


26
Order matters
Set the domain of discourse to be all real
numbers .
Let P (x,y ) = x < y.
Question: What does x -y P (x,y ) mean?
Answer: x -y P (x,y ):
All numbers x admit a larger number y
Question: Whats the truth value of this
expression?
Answer: True. For any real number there is a
larger real number



27
Order matters
P (x,y ) = x < y
Question: What does -y x P (x,y ) mean?
Answer: -y x P (x,y ):
Some number y is larger than all x
Question: Whats the truth value of this
expression?
Answer: False. There is no the largest real
number. Additionally the number cannot be
larger than itself.
28
Order matters but not always
If we have two quantifiers of the same kind,
order does not matter.
x y is the same as y x because these
are both interpreted as for every
combination of x and y
-x -y is the same as -y -x because these are
both interpreted as there is a pair x , y

Predicates - the meaning of multiple quantifiers
xy P(x,y)
-x-y P(x,y)
x-y P(x,y)
-xy P(x,y)

P(x,y) true for all (x, y) pairs.
For every value of x we can find a (possibly different)
y so that P(x,y) is true.
P(x,y) true for at least one (x, y) pair.
There is at least one x for which P(x,y)
is always true.
Quantification order is not
commutative in
general !
Suppose P(x,y) = xs favorite class is y.
Negation of Logical Expressions
with Quantifiers
What about and

Since the quantifiers are the same as taking a bunch of
ANDs () or ORs (-) we obtain applying De Morgans
laws:
30
( )
x P x
( )
? x P x -
( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
1 2
1 2
...
.. ;

.
n
n
P x P x P x
P
x P x
x P x x P x P x
. . .
v v v -

( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
1 2
1 2


...
...
n
n
P x P x P x
P x P x
x P x
x P x P x
v v v
. . .
-
Negation of Logical Expressions
with Quantifiers


Negation of the expression containing the universal
quantifier like for every x belonging to some certain
domain P(x) holds means there exist at least one x in
the certain domain such that P(x) does not hold
Negation of the expression containing the existential
quantifier like there exist such x in the certain domain
that P(x) holds means for every x from the certain
domain P(x) does not hold
31
( ) ( )
x P x x P x -
( ) ( )
x P x x P x -
Negation of Logical Expressions
with Quantifiers
General rule: to negate a logical expression
containing quantifier (quantifiers), move
negation to the expression under quantifier
(quantifiers) and flip all quantifiers from to
- and vice versa.
32
33
Negation Example
Compute:
In English, we are trying to find the opposite of
every x admits a y greater or equal to x squared.
The opposite is that some x does not admit y
greater or equal to x squared
Algebraically, one just flips all quantifiers from
to - and vice versa, and negates the interior
propositional function. In our case we get:
( )
2
x y x y - s
( ) ( ) ( )
2 2 2
x y x y x y y x x y x y - s - - s >
Logical Equivalences
Involving Predicates and Quantifiers
Statements involving predicates and
quantifiers are logically equivalent if and only
if they have the same truth value no matter
which predicates are substituted into these
statements and which domain is used for the
variables in these propositional functions.
34