Chapter 1 Predicate Sand Quanti Fier

PREDICATES AND
QUANTIFIERS
PREDICATES, QUANTIFIER, UNIVERSAL

QUANTIFIER, COMMON DOMAIN,
EXAMPLE & COUNTEREXAMPLE,
EXISTENTIAL QUANTIFIER, UNIVERSAL
CONDITIONAL PROPOSITION,
REVISION!
Let p: Today is cold,

q: Today is hot,
r: Today is windy.
Write the following propositions using p, q, and r.
a) Today is hot if and only if not windy.
b) Either today is cold or not cold, but not both.
c) If today is not windy then it is not hot.
d) Today is neither cold nor windy.
e) If today is windy then either it is hot or cold.
Draw the truth table for each of the following
propositions.
ANSWERS.
PREDICATES.
A predicate or propositional function is a statement

containing variables.
For instance “x+2 = 7”, “X is American”,
“x < y”, “p is a prime number” are predicates.
The truth value of the predicate depends on the value
assigned to its variables.
For instance if we replace x with 1 in the predicate
“x+2 = 7” we obtain “1+2 = 7”, which is false,
but if we replace it with 5 we get “5 + 2 = 7”, which is
true.
We represent a predicate by a letter followed by the
variables enclosed between parenthesis:
P(x), Q(x, y), etc.
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. So, 5 is an example for “x + 2 = 7”,
while 1 is a counterexample.
•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.
•In “X is American”, we may assume that X is a

human being,
•so in this case the universe of discourse is the set of
all human beings.
PROPOSITIONS AND QUANTIFIERS
For instance, P(n) : n is prime is a predicate on

the natural numbers.
Observe that P(1) is false, P(2) is true.
In the expression P(x), x is called a free variable.
As x varies the truth value of P(x) varies as well.
The set of true values of a predicate P(x) is
called the truth set and will be denoted by TP .
Example 3.1
Let Q(x, y) : x = y+3 with domain the collection of

natural numbers (i.e. the numbers 0, 1, 2, · · · ).
What are the truth values of the propositions Q(1, 2)
and Q(3, 0)?
Solution:
By substitution in the expression of Q we find: Q(1, 2)

is false since 1 = x ≠ y + 3 = 5. On the contrary, Q(3, 0)
is true since x = 3 = 0 + 3 = y + 3 #
If P(x) and Q(x) are two predicates with a common
domain D
then the notation P(x) ⇒ Q(x) means that every element

in the truth set of P(x) is also an element in the truth set of
Q(x).
Example 3.2
Consider the two predicates P(x) : x is a factor of 4 and

Q(x) : x is a factor of 8.
Show that P(x) ⇒ Q(x).
Solution.
Finding the truth set of each predicate we have:
TP = {1, 2, 4} and TQ = {1, 2, 4, 8}.
Since every number appearing in TP also appears in TQ
then P(x) ⇒ Q(x)
Universal Quantifier
Another way to generate proposition is by means of

quantifiers
Definition:
The universal quantifier of P(x) is the proposition P(x) is
true for all values of x in the domain D, and is denoted by
∀ x ∈ D, P(x)
where the symbol ∀ is called the universal quantifier.

Universal Quantifier
The proposition ∀ x ∈ D, P(x) can also be expressed in any of

the following ways.
For all x, P(x)

For any x, P(x)
For every x, P(x)
For each x, P(x)
P(x), for all x
The proposition ∀ x∈D,

P(x) is false if P(x) is false for at least one value of x.
In this case x is called a counterexample.
Example 3.4
Show that the proposition ∀x ∈R, x > 1/2x is false.
Solution.
A counterexample is x =1/2. Clearly, 1/2< 2 . Why? ½ > 1?
Nope! It is smaller , here. Right?
Example 3.5
Write in the form x∈ D, P(x) the proposition :” every real
number is either positive, negative or 0.”
Solution.
∀ x ∈ R, x > 0, x < 0, or x = 0
Existential Quantifier
The existential quantifier of P(x) is the proposition

P(x) is true if there exists an x in the domain D,
and is denoted by ∃ x ∈ D, P(x)
where the symbol is called the existential quantifier.

∃ = (there is / there exists / there is at least one)
= (there is some x such that p(x))
In other words, the ∃ x ∈D, P(x) is a proposition that is true
if there is at least one value of x ∈D where P(x) is true;
otherwise it is false.
example
For instance if x and y represent human beings

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 that there

is someone such that everybody is his or her friend.
exercise
Let L(x, y) be the predicate "x likes y," and let the
universe of discourse be the set of all people. Use
quantifiers to express each of the following
statements.
a) Everyone likes everyone.

b) Everyone likes someone.
c) Everyone likes George.
d) There is no one whom everyone likes.
e) Everyone does not like someone.
Example 3.6
Let P(x) be the statement ”x > 3”.

What is the truth value of the proposition ∃ x ∈ R,
P(x).
Solution.
Since 4 ∈R and 4 > 3, the given proposition is true.
The proposition ∀ x ∈ D,
P(x) → Q(x) is called
the universal conditional proposition.
For example, the proposition ∀x ∈R,

if x > 2 then x2 > 4 is a universal conditional
proposition.
Example 3.7
Rewrite the proposition ”if a real number is an

integer then it is a rational number” as a universal
conditional proposition.
Solution.
∀ x ∈ R, if x is an integer then x is a rational number.
Example 3.8
a. What is the negation of the proposition

∀ x ∈ D, P(x) ?
b. What is the negation of the proposition

∃ x ∈ D, P(x) ?
c. What is the negation of the proposition

∀ x∈ D, P(x) → Q(x) ?
∃
Solution.
a. ∃ x∈ D, ~ P(x).
b. ∀ x ∈ D, ~ P(x).
c. Since P(x)→ Q(x) = (~ P(x)) ∨ Q(x)
then ~ ( ∀ x ∈D, P(x) → Q(x))
c. ∃ x∈D, ~ P(x) and ~ Q(x)

Example 3.9
Consider the universal conditional proposition

∀ x ∈ D, if P(x) then Q(x).
a. Find the contrapositive.

b. Find the converse.
c. Find the inverse.
Next, we discuss predicates that contain multiple
quantifiers
Example 3.11
a. Let P(x, y) denote the statement ”x+y = y+x.”
What is the truth value of the proposition
( ∀ x∈R)( ∀ y ∈ R), P(x, y) ?
Solution.
a. The given proposition is always true.
Next, we discuss predicates that contain multiple
quantifiers
Example 3.11
b. Let Q(x, y) denote the statement ”x + y = 0.”
What is the truth value of the proposition
( ∃ y ∈ R)( ∀ x ∈R), Q(x, y)?
Solution.
b. The proposition is false.
For otherwise, one can choose x ≠ −y to obtain 0
≠ x + y = 0, which is impossible.
Example 3.12
Find the negation of the following propositions:
a. ∀ x ∃y, P(x, y).

b. ∃ x∀ y, P(x, y).
Solution.
a. ∃ x ∀y, ~ P(x, y).
b. ∀ x ∃ y, ~ P(x, y)
Quantifier Negation Rules:
a) ~( ∀x, P(x)) is equivalent to ∃ x, ~p(x)

b) ~( ∃ x, p(x)) is equivalent to ∀x, ~P(x)
As a conclusion:
We can said that when dealing with quantified statement,

it is useful to write out the statements in words.
In most of the problem, it is easy to express exactly

what :
∀ x , ∃ y, P(x,y).
For every x there exists y such that p(x,y) is true.
Thank you

Chapter 1 Predicate Sand Quanti Fier

Uploaded by

Copyright:

Available Formats

Chapter 1 Predicate Sand Quanti Fier

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

Chapter 1 Predicate Sand Quanti Fier

Uploaded by

Copyright:

Available Formats

PREDICATES AND

PREDICATES, QUANTIFIER, UNIVERSAL

Let p: Today is cold,

A predicate or propositional function is a statement

•In “X is American”, we may assume that X is a

For instance, P(n) : n is prime is a predicate on

Let Q(x, y) : x = y+3 with domain the collection of

By substitution in the expression of Q we find: Q(1, 2)

then the notation P(x) ⇒ Q(x) means that every element

Consider the two predicates P(x) : x is a factor of 4 and

Show that P(x) ⇒ Q(x).

Another way to generate proposition is by means of

where the symbol ∀ is called the universal quantifier.

The proposition ∀ x ∈ D, P(x) can also be expressed in any of

For all x, P(x)

The proposition ∀ x∈D,

The existential quantifier of P(x) is the proposition

where the symbol is called the existential quantifier.

For instance if x and y represent human beings

but ∃ y ∀ x P(x, y) means that there

a) Everyone likes everyone.

Let P(x) be the statement ”x > 3”.

For example, the proposition ∀x ∈R,

Rewrite the proposition ”if a real number is an

a. What is the negation of the proposition

b. What is the negation of the proposition

c. What is the negation of the proposition

c. ∃ x∈D, ~ P(x) and ~ Q(x)

Consider the universal conditional proposition

a. Find the contrapositive.

a. ∀ x ∃y, P(x, y).

a) ~( ∀x, P(x)) is equivalent to ∃ x, ~p(x)

We can said that when dealing with quantified statement,

In most of the problem, it is easy to express exactly

For every x there exists y such that p(x,y) is true.

You might also like