Predicates and Quantifiers

o Consider this proposition:
“x is an integer” - this statement is neither true nor false

when the value of the variable is not specified
o No rules of propositional logic allow us to conclude the truth
of the statement.- thus we are introducing a more powerful
type of logic called Predicate Logic.
o Predicate logic is a logical system for reasoning about
properties of objects.
o It augments the logical connectives from propositional logic
with
 predicates that describe properties of objects,
 quantifiers that allow us to reason about multiple

objects.
o A predicate/ propositional function is a statement containing
variables.
o We can be denoted the predicate by a letter followed by
variable enclosed between parenthesis: P(x), Q(x, y), etc.
o Once a value has been assigned to the variable x, the statement
P(x) becomes a proposition and has a truth value.
o Each variable in a predicate is assumed to belong to a universe
(or domain) of discourse, for instance in the predicate “n is
an odd integer” ’n’ represents an integer, so the universe of
discourse of n is the set of all integers.
o An example for P(x) is a value of x for which P(x) is true. A
counterexample is a value of x for which P(x) is false.
Example:
5 is an example for “x + 2 = 7”, while 1 is a counterexample.
o Quantification expresses the extent to which a predicate is
true over a range of elements.
o Types of quantification:
 universal quantification-which tells us that a predicate is
true for every element under consideration
 existential quantification-which tells us that there is one
or more element under consideration for which the predicate
is true.
Universal Quantification of P(x)
o Universal quantification of P(x) is denoted ∀xP(x) is read as
“for all x, P(x)” or “for every x, P(x)”
o The universal quantification of P(x) for a particular domain is
the proposition that asserts that P(x)is true for all values of
x in this domain.
o The domain specifies the possible values of the variable x.
o The meaning of the universal quantification of P(x)changes when
we change the domain.
o The domain must always be specified when a universal quantifier
is used; without it, the universal quantification of a
statement is not defined
o An element for which P(x) is false is called a counterexample of
∀xP(x).
Example
Let Q(x) be the statement “x > 2”. What is the truth value of
the quantification ∀xQ(x) where the domain consists of all
real numbers?
Solution: Q(x) is not true for every real number x ∀xQ(x) is
false.
One way to show that Q(x) is not always true when x is in the
domain is to find a counterexample to the statement ∀xQ(x) . Note
that a single counterexample is all we need to establish that
∀xQ(x) is false.
Quiz:
Let P(x) be the statement “x 2 > 0”. What is the truth value of the
quantification ∀xP(x)where the domain consists of all integers?
Existential Quantification of P(x)
o Existential quantification of P(x) is the proposition “There
exists an element x in the domain such that P(x)”
o Its denoted by ∃xP(x) and is 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)”
o With existential quantification, we form a proposition that is
true if and only if P(𝑥) is true for at least one value of 𝑥 in
the domain.
o A domain must always be specified when a statement ∃xP(x) is
used.
o Furthermore, the meaning of ∃xP(x) changes when the domain
changes.
Example
Let P(x) denote the statement “x > 𝟑”
What is the truth value of the quantification ∃xP(x) where the
domain consists of all real numbers?
Solution: ∃xP(x) is true.
The statement ∃xP(x) is false if and only if there is no
element x in the domain for which P(x) is true.
Summary of the quantifiers
Statement When True? When False?

∀xQ(x) Q(x)is true, for There is an x for
every x which Q(x) is false
∃xP(x) There is an x for P(x)is false for every
which P(x)is true x
o In predicates with more than one variable it is possible to use

several quantifiers at the same time, for instance ∀x∀y∃z P(x,
y, z), meaning “for all x and all y there is some z such that
P(x, y, z)”.
o Note that in general the existential and universal quantifiers
cannot be swapped, i.e., in general ∀x∃y P(x, y) means
something different from ∃y∀x P(x, y). For instance if x and y
represent human beings and P(x, y) represents “x is a friend of
y”, then ∀x∃y P(x, y) means that everybody is a friend of
someone, but ∃y∀x P(x, y) means there is someone such that
everybody is his or her friend.
Precedence of Quantifiers
The quantifiers ∀ and ∃ have higher precedence than all logical
operators from propositional logic.
Example
∃xP(x)^ Q(x)^ R(x)
is parsed like this:
(∃xP(x))^(Q(x)^ R(x))
To ensure that x is properly quantified, explicitly put
parentheses around the region you want to quantify:
Negating Quantified Expressions
o Consider the statement “Every politician in Zimbabwe is
corrupt.”
o This statement is a universal quantification, namely, ∀xQ(x),
where Q(x) is the statement “A politician being corrupt” and
the domain consists of the politician in Zimbabwe.
o The negation of this statement is “It is not the case that
every politician in Zimbabwe is corrupt.”
o This is equivalent to “There is a politician in Zimbabwe who
is not corrupt.” And this is simply the existential
quantification of the negation of the original propositional
function, namely, ∃x~Q(x).
o This example illustrates the following logical equivalence:
~∀xQ(x) ≡ ∃x~Q(x)
o Suppose we wish to negate an existential quantification.
Consider the proposition “There is a student in this class who
is married.”
o This is the existential quantification ∃x Q(x), where Q(x)is the
statement “a student being married.” The negation of this
statement is the proposition “It is not the case that there is
a student in this class who is married.”
o This is equivalent to “Every student in this class is not
married” which is just the universal quantification of the
negation of the original propositional function, or, phrased in
the language of quantifiers, ∀x~Q(x).
o This example illustrates the equivalence:~∃x Q(x), ≡ ∀𝑥 ~Q(𝑥)
De Morgan’s Laws for Quantifiers
Negation Equivalent When Is Negation
Statement True?
~∃𝑥P(𝑥) ∀𝑥~P(𝑥) For every 𝑥, P(𝑥) is
false
~∀𝑥P(𝑥) ∃𝑥~P(𝑥) There is an 𝑥 for
which P(𝑥) is false

Predicates and Quantifiers

Uploaded by

Copyright:

Available Formats

Predicates and Quantifiers

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Predicates and Quantifiers

Uploaded by

Copyright:

Available Formats

o Consider this proposition:

“x is an integer” - this statement is neither true nor false

 quantifiers that allow us to reason about multiple

Statement When True? When False?

o In predicates with more than one variable it is possible to use

You might also like