Null 2

Predicate Calculus
Topics
• Predicates
• Quantifiers
• Universal Quantifier
• Existential Quantifier
• Translate to Logical expression
Predicate Logic
Propositional logic cannot adequately
express the meaning of all statements in
mathematics and in natural language.
Predicate logic can be used to express the

meaning of a wide range of statements in
mathematics and computer science in ways that
permit us to reason and explore relationships
between objects.
Predicates
“x is greater than 10.”
Variable x is the subject of the statement.
“is greater than 10” is the predicate. It refers to
a property that the subject of the statement can
have.
Predicates
“x is greater than 10.”
can be denoted by P(x), where P denotes the

predicate“is greater than 10” and x is the
variable.
The statement P(x) is also said to be the

value of the propositional function P at x.
Example
Let P(x) denote the statement “x > 3.”
What are the truth values of P(4) and P(2)?
Solution
What are the truth values of P(4) and P(2)?
We obtain the statement P(4) by setting x = 4 in
the statement
Hence, P(4), which is the statement “4 > 3,” is
true.
However, P(2), which is the statement “2 > 3,” is
false. “x > 3.”
Example
Let A(x) denote the statement “Computer
x is under attack by an intruder.”
Solution
Let A(x) denote the statement “Computer x is under
attack by an intruder.”
Suppose that of the computers on campus, only

CS2 and MATH1 are currently under attack by intruders.
What are truth values of A(CS1), A(CS2), and A(MATH1)?
Ans: A(CS1) is false.

A(CS2) is true.
A(MATH1) is true.
Example
Let Q(x,y) denote the statement
“x = y + 3.” What are the truth values of the
propositions Q(1,2) and Q(3,0)?
Solution
Let Q(x,y) denote the statement “x = y + 3.”
What are the truth values of the propositions
Q(1,2) and Q(3,0)?
Ans:
Q(1,2) is the statement “1 = 2 + 3,” which is
false.
Q(3,0) is the proposition “3 = 0 + 3,” which is
true.
Quantifiers
Quantification
- Create a proposition from a propositional
function
- Expresses the extent to which a predicate is
true over a range of elements
- In English we use the terms all, some, many,
none, and few.
Predicate Calculus
- area of logic that deals with predicates
and quantifiers
Two Types of Quantification
1. Universal Quantification
- tells us that a predicate is true for every
element under consideration.
2. Existential Quantification
- tells us that there is one or more element
under consideration for which the predicate is
true.
The Universal Quantifier
Definition
The universal quantification of P(x) is the
statement
“P(x) for all values of x in the domain.”
The notation ∀xP(x) denotes the universal
quantification of P(x).Here ∀ is called the universal
quantifier.
We read ∀xP(x) as “for all xP(x)” or “for every
xP(x).” An element for which P(x) is false is called a
counterexample of ∀xP(x).
Domain
• also called the domain of discourse (or the
universe of discourse)
• specifies the possible values of the variable x
in P(x)
• the truth value of ∀xP(x) depends on the
domain
Example
Let P(x) be the statement “x + 1 > x.”
What is the truth value of the
quantification ∀xP(x),where the domain consists
of all real numbers?
Solution
Let P(x) be the statement “x + 1 > x.”
∀xP(x) is true.
Example
Let Q(x) be the statement “x < 2.”
quantification ∀xQ(x),where the domain
consists of all real numbers?
Solution
Q(x) is the statement “x < 2”.
Q(x) is not true for every real number x,

because, for instance, Q(3) is false.
That is, x = 3 is a counterexample for the

statement∀xQ(x). Thus ∀xQ(x) is false.
Example
Suppose that P(x) is “𝒙𝟐 > 0.”
of all integers?
Solution
Suppose that P(x) is “𝒙𝟐 > 𝟎“.∀xP(x) is
false.
Counterexample: 𝒙𝟐 = 0 when x = 0
Example
What is the truth value of ∀xP(x), where
P(x) is the statement “𝒙𝟐 < 10” and the domain
consists of the positive integers not exceeding
4?
Solution
P(x) is the statement “𝒙𝟐 < 10” and the domain consists
of the positive integers not exceeding 4:
The statement ∀xP(x) is the same as the conjunction
P(1) ∧ P(2) ∧ P(3) ∧ P(4)
P(1) = 12 < 10 = 1 < 10
P(2) = 22 < 10 = 4 < 10
P(3) = 32 < 10 = 9 < 10
P(4) = 42 < 10 = 16 < 10
Because P(4) is false, it follows that ∀xP(x) is false.
The Existential Quantifier
Definition
The existential quantification of P(x) is the
statement
“There exists an element x in the domain such
that P(x).”
We use the notation ∃xP(x) for the
existential quantification of P(x). Here ∃ is called
the existential quantifier.
Example
quantification ∃xP(x),where the domain consists
Solution
P(4) = 4 > 3
Because “x > 3” is sometimes true, the

existential quantification of P(x), which is ∃xP(x),
is true.
Example
quantification ∃xP(x),where P(x) is the
statement “𝒙𝟐 > 10” and the universe of
discourse consists of positive integers not
exceeding 4?
Solution
P(x) is the statement “𝒙𝟐 > 10” and the domain consists
of positive integers not exceeding 4?
The statement ∃xP(x) is the same as the disjunction

P(1) ∨ P(2) ∨ P(3) ∨ P(4)
P(1) = 12 > 10 = 1 > 10
P(2) = 22 > 10 = 4 > 10
P(3) = 32 > 10 = 9 > 10
P(4) = 42 > 10 = 16 > 10
Because P(4) is true, it
follows that ∃ xP(x) is true.
Truth values of Quantifiers
Quantifiers.
Statement When True? When False?
∀xP(x) P(x) is true for every x. There is an x for

which P(x) is false.
∃xP(x) There is an x for which P(x) is false for

P(x) is true every x.
Precedence of Quantifiers
The quantifiers ∀ and ∃ have higher
precedence than all logical operators from
propositional calculus.
For example,
∀xP(x) ∨ Q(x) = (∀xP(x)) ∨ Q(x) rather than
∀x(P(x) ∨ Q(x)).
Quantifiers with restricted
domains
What do the following statements mean for
the domain of real numbers?
Translating from English into
Logical Expressions
Example
Express the statement using predicates and
quantifiers:
“Every student in class has studied calculus.”

Solution
“Every student in class has studied calculus.”
What if we change the domain to consist of all people?
“For every person x, if person x is a student in this class

then x has studied calculus.”
If S(x) represents the statement that person x is in this

class: ∀x(S(x) → C(x))
[Note: not ∀x(S(x) ∧ C(x)) because this statement says

that all people are students in this class and have studied
calculus!]
Translate the statements:
– “All hummingbirds are richly colored”
– “No large birds live on honey”
– “Birds that do not live on honey are dull in
color”
– “Hummingbirds are small”
Our propositional functions
– Let P(x) be “x is a hummingbird”
– Let Q(x) be “x is large”
– Let R(x) be “x lives on honey”
– Let S(x) be “x is richly colored”
• Translate the statements:

– “All hummingbirds are richly colored” "x (P(x)→S(x))
– “No large birds live on honey” ￢$x (Q(x) Ù R(x))
• Alternatively: "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))

Null 2

Uploaded by

Copyright:

Available Formats

Null 2

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

Null 2

Uploaded by

Copyright:

Available Formats

Predicate Calculus

Predicate logic can be used to express the

can be denoted by P(x), where P denotes the

The statement P(x) is also said to be the

Suppose that of the computers on campus, only

Ans: A(CS1) is false.

Q(x) is not true for every real number x,

That is, x = 3 is a counterexample for the

Because “x > 3” is sometimes true, the

The statement ∃xP(x) is the same as the disjunction

∀xP(x) P(x) is true for every x. There is an x for

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

“Every student in class has studied calculus.”

“For every person x, if person x is a student in this class

If S(x) represents the statement that person x is in this

[Note: not ∀x(S(x) ∧ C(x)) because this statement says

• Translate the statements:

You might also like