Dis - Struc - ITEC 205 - L9

COLLEGE OF COMPUTER
STUDIES
PREPARED BY: P. FERNANDEZ
Discrete Structures
LESSON 7 – PREDICATE LOGIC ( C O N T I N U ATI O N )
Quantifier
 A quantifier turns a propositional function into a proposition without
assigning specific values for the variable. There are primarily two
quantifiers:
universal quantifier
and the
existential quantifier.
Quantifier – Universal
The universal quantification of P (x) is the proposition:
“P (x) is true for all values x in the universe of discourse.”
Notation: “For all x P (x)” or “For every x P (x)” is written
∀xP (x).
Quantifier – Existential
The existential quantification of P (x) is the proposition:
“There exists an element x in the universe of discourse such that P (x) is
true.”
Notation: “There exists x such that P (x)” or “There is at least one x such
that P (x)” is written
∃xP (x).
Quantifier – Example
Example:
F (x): x is a fox. S (x): x is sly. T (x): x is trustworthy.
and the universe of discourse for all three functions is the set of all animals.
• Everything is a fox: ∀xF (x)
• All foxes are sly: ∀x[F (x) → S (x)]
• If any fox is sly, then it is not
trustworthy:
∀x[(F (x) ∧ S (x) → ¬T (x)] ⇔ ¬∃x[F (x) ∧ S (x) ∧ T (x)
Example:
Express the following sentences using predicates and quantifiers.
• “All lions are fierce.”
• “Some lions do not drink coffee.”
Assume
 P(x): x is a lion. “All lions are fierce.” ∀ x (P(x) →
Q(x))
 Q(x): x is fierce. “Some lions do not drink coffee.” ∃x (P(x) /\
¬R(x))
 R(x): x drinks coffee.
Example:
 If a brick is on another brick, it is not on the table.

 Every brick is on the table or on another brick.
 No brick is on a brick which is also on a brick.
To simplify matters, we'll let the domain of our universe consist of bricks.

• Let T(x)T(x) denote "x is on the table".
• Let O(x,y)O(x,y) denote "x is on top of y".
Example:
First sentence: “If a brick is on another brick, it is not on the table”.

∀x(∃y(O(x,y))→¬T(x))
Then, we have “Every brick is on the table or on another brick”:

∀x(T(x)∨∃y(O(x,y)))
Example:
“No brick is on a brick which is also on a brick”.
In loglish: "For all bricks x, if there exists a brick y such that O(x, y),
then there does not exist any z such that O(y,z)."
Now, the full translation:
x(∃y(O(x,y)→¬∃z(O(y,z)))
Example:
Let P(x) be the statement x2<x where the universe for x is all real
numbers. Determine the truth value of:
(a) P(0), b) P(1/3), (c) P(2)
Solution:
(a) The proposition P(0) states that 02<0, which is false.

(b) The proposition P(1/3) states that (1/3)2 < 1/3 which is true.
(c) The proposition P(2) states that 4<2, which is false.
Example:
Let Q(x,y) be the statement x+y=x-y where the universe for x and y is all
real numbers. Determine the truth value of:
(a) Q(5,-2), (b) Q(4.7,0)

Solution:
(a) Q(5,-2) says that 5-2=5-(-2), or, 3=7, which is false.

(b) Q(4.7,0) says that 4.7-0=4.7+0, which is true.
Example:
Suppose P(x) is the predicate x<|x|. Determine the truth value of ∀x
P(x), where the universe for x is:
(a) the three numbers -3,-2,-1.

(b) (b) all real numbers.
Solution:
(a) P(-3), P(-2), and P(-1) are all true since the numbers -3,-2,-1 are
negative but their absolute values are positive. Therefore, ∀ x P(x) is
true.
(b) The predicate x<|x| is false for every non-negative number. For
example, P(1) is false since 1=|1|. having just one value of x that makes
the predicate false is enough to guarantee that ∀ x P(x) is false.
Example:
Suppose P(x) is the predicate x<|x|. Determine the truth value of ∃x P(x)
where the universe for x is:
(a) the three numbers 1,2,3

(b) the six numbers -2,-1,0,1,2,3.
Solution:
(a) P(1), P(2), and P(3) are all false since in each case x=|x|.
Therefore, ∃x P(x) is false for this universe.
(b) If we begin checking the six values of x, we find P(-2) is true since it
states that -2<|-2|, or -2<2. We need check no further; having one case
that makes the predicate true is enough to guarantee that ∃x P(x) is
true.
Solution:
(a) P(1), P(2), and P(3) are all false since in each case x=|x|.
Therefore, ∃x P(x) is false for this universe.
(b) If we begin checking the six values of x, we find P(-2) is true since it
states that -2<|-2|, or -2<2. We need check no further; having one case
that makes the predicate true is enough to guarantee that ∃x P(x) is
true.
Example:
Determine whether ∃t (t2+12=7t) is true, where the universe for t
consists of all real numbers.
Solution:
The equation t2+12=7t can be rewritten as t2-7t+12=0, which factors as

(t-3)(t-4)=0.
This is true for the numbers 3 and 4.
Hence the given proposition is true.
Example:
Negate: ”There is a person who walked on the moon”.
We can always obtain the negation of a statement by placing the phrase it is not the case that in front
of the statement. Thus, the negation is It is not the case that there is a person who walked on the
moon. That is, No person walked on the moon.
We can also work with symbols. Let W(x) be the statement x walked on the moon where the universe
for x consists of all people. The statement claims that there is an x such that x walked on the moon;
that is, ∃x W(x). The negation is ¬∃x W(x), which is equivalent to ∀x ¬ W(x). Therefore, the negative
states that for every x that can be chosen, x did not walk on the moon. That is, No person walked on
the moon.
Example:
Negate: ” Everyone in the class has a laptop computer.”.
If we take L(x) to be x has a laptop computer where the universe for x
consists of all people in this class, then the given statement is ∀x L(x).
The negation is ¬ ∀x L(x), which is equivalent to ∃x ¬ L(x).
In words, There is someone in this class who does not have a laptop
computer.

Dis - Struc - ITEC 205 - L9

Uploaded by

Copyright:

Available Formats

Dis - Struc - ITEC 205 - L9

Uploaded by

Document Information

Original Title

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

Dis - Struc - ITEC 205 - L9

Uploaded by

Copyright:

Available Formats

COLLEGE OF COMPUTER

 If a brick is on another brick, it is not on the table.

To simplify matters, we'll let the domain of our universe consist of bricks.

First sentence: “If a brick is on another brick, it is not on the table”.

Then, we have “Every brick is on the table or on another brick”:

(a) The proposition P(0) states that 02<0, which is false.

(a) Q(5,-2), (b) Q(4.7,0)

(a) Q(5,-2) says that 5-2=5-(-2), or, 3=7, which is false.

(a) the three numbers -3,-2,-1.

(a) the three numbers 1,2,3

The equation t2+12=7t can be rewritten as t2-7t+12=0, which factors as

You might also like