Discrete

Math:
Predicate
Logic
The propositional logic is not powerful enough to represent all types
of assertions that are used in computer science and mathematics, or
to express certain types of relationship between propositions such as
equivalence.

For example, the assertion "x is greater than 1", where x is a variable,
is not a proposition because you can not tell whether it is true or false
unless you know the value of x. Thus the propositional logic can not
deal with such sentences. However, such assertions appear quite
often in mathematics and we want to do inferencing on those
assertions.
Also the pattern involved in the following logical equivalences can
not be captured by the propositional logic:

"Not all birds fly" is equivalent to "Some birds don't fly".

"Not all integers are even" is equivalent to "Some integers are not
even".
"Not all cars are expensive" is equivalent to "Some cars are not
expensive",
... .
To cope with deficiencies of propositional logic we introduce two
new features: predicates and quantifiers.

Consider the statements

y>9
r + s = 12.
They are assertions but are not considered propositions
because their truth value depends upon the value we’ll give
for the variables r, s or y.
• A predicate is a verb phrase template that describes a
property of objects, or a relationship among objects
represented by the variables.

• “predicate,” or “first-order,” logic

Example 1. The sentences "The car Tom is driving is blue",
"The sky is blue", and "The cover of this book is blue" come
from the template "is blue" by placing an appropriate
noun/noun phrase in front of it. The phrase "is blue" is a
predicate and it describes the property of being blue.
Predicates are often given a name. For example any of
"is_blue", "Blue" or "B" can be used to represent the
predicate "is blue" among others. If we adopt B as the name
for the predicate "is_blue", sentences that assert an object is
blue can be represented as "B(x)", where x represents an
arbitrary object. B(x) reads as "x is blue".
 Atomic Formulas
• An atomic formula is a predicate with zero or more
arguments. For example, u(X) is an atomic formula with
predicate u and one argument, here occupied by the variable
X. In general, an argument is either a variable or a constant.
• *Variables are symbols capable of taking on any constant as
value.
• An atomic formula all of whose arguments are constants is
called a ground atomic formula. Nonground atomic
formulas can have constants or variables as formula
arguments, but at least one argument must be a variable.
Example 2. Similarly the sentences "Alf gives the book to Gem",
"Sophie gives a guitar to Lei", and "Mico gives a lecture to Eia" are
obtained by substituting an appropriate object for variables x, y, and z
in the sentence "x gives y to z". The template "... gives ... to ..." is a
predicate and it describes a relationship among three objects. This
predicate can be represented by Give( x, y, z ) or G( x, y, z ), for
example.

John gives a book to Gen : G(Alf, book, Gem)

Sophie gives a guitar to Lei: G(Sophie, guitar, Lei)
*x, y and z are considered as predicate variables while Alf, book, Gem
are examples of predicate constants
• Example 3. P(x, y, z) is a predicate for x studied in
school y for z years.

Cristina studied in UB for 4 years.: P(Cristina, UB,

4)
Gemma studied in PUP for 5 years.: P(Gemma, PUP, 5)
Example 4. S(x,y,z) is a predicate for x + y = z.
4 + 6 = 10: S(4,6,10)
Depending on the number of variables in a predicate, it
could be unary, binary and n-ary or n-place predicate.
P(x) - unary predicate
Q(x,y) - binary predicate
R(x1, x2, …,xn) - n-ary predicate
 Universe of Discourse

The universe of discourse, also called universe, is the set

of objects of interest. The propositions in the predicate
logic are statements on objects of a universe. The
universe is thus the domain of the (individual) variables.
It can be the set of real numbers, the set of integers, the
set of all cars on a parking lot, the set of all students in a
classroom etc. The universe is often left implicit in
practice. But it should be obvious from the context.
When predicate variables are replaced with predicate
constants, the predicate becomes a proposition.
• Consider the predicate in example 4. S(x,y,z) is a predicate, yet
when the variables x, y and z are replaced with the numbers 4,6
and 10, it becomes a proposition because its truth value can now
be determined.
• If P(x1, …,xn) is true for all values c1, c2, …,cn from the
universe U, then we say that P(x1, x2, …,xn) is valid in U.
• If P(x1, …,xn) is true for some values c1, c2, …,cn from the universe
U, then we say that P(x1, …,xn) is satisfiable in U.
• If P(x1, x2, …,xn) is not true for any set of values c 1, c2, …,cn
from the universe U, then we say that P(x 1, x2, …,xn) is
unsatisfiable in U.
• 1. Let P(x) denote the statement "x  4." What are the truth
values?
a) P(O)
b) P(4)
c) P(6)
2. Let P(x) be the statement "the word x contains the letter a."
What are the truth values?
a) P(orange)
b) P(lemon)
c) P(true) d) P(false)
Quantification – Forming Propositions from
Quantifications

• A predicate with variables is not a proposition. For

example, the statement x > 1 with variable x over the
universe of real numbers is neither true nor false since we
don't know what x is. It can be true or false depending on
the value of x.
For x > 1 to be a proposition either we substitute a
specific number for x or change it to something like
"There is a number x for which x > 1 holds", or "For every
number x, x > 1 holds".
Predicate with variables (called an atomic formula) can be
made a proposition by applying one of the following two
operations to each of its variables:
1. assign a value to the variable
2. quantify the variable using a quantifier
 The Universal Quantifier

The expression: x P(x), denotes the universal

quantification of the atomic formula P(x). Translated into
the English language, the expression is understood as:
"For all x, P(x) holds", "for each x, P(x) holds" , “for any x,
P(x) holds", “for arbitrary x, P(x) holds" or "for every x,
P(x) holds". is called the universal quantifier, and x
means all the objects x in the universe. If this is followed
by P(x) then the meaning is that P(x) is true for every
object x in the universe.
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 ∀x
P(x) as "for all x P(x)" or "for every x P(x )." An element
for which P(x) is false is called a counterexample of ∀x
P(x).
Universal Quantifier and Connective AND

• If all the elements in the universe of discourse can be

listed then the universal quantification x P(x) is equivalent
to the conjunction: P(x1)) Ʌ P(x2) Ʌ P(x3) ... P(xn) .

For example, in the above example of x P(x), if we knew

that there were only 4 cars in our universe of discourse
(c1, c2, c3 and c4) then we could also translate the
statement as: P(c1) Ʌ P(c2) Ʌ P(c3) Ʌ P(c4)
• To express the AND of a collection of expressions formed
by substituting every possible value for some variable X,
we need an additional way to create expressions “For all”
of predicate logic. The operator is ∀, read “for all.”
For example, "All cars have wheels" could be transformed
into the propositional form,

x P(x), where:

P(x) is the predicate denoting: x has wheels, and

the universe of discourse is only populated by cars.
Existential Quantifier and Connective OR

If all the elements in the universe of discourse can be listed,

then the existential quantification  xP(x) is equivalent to
the disjunction: P(x1)  P(x2)  P(x3)  ... P(xn).

For example, in the above example of x P(x), if we knew

that there were only 5 living creatures in our universe of
discourse (say: Sai, Mico, Lei, Eia and Dad), then we
could also write the statement as: P(Sai) P(Mico) 
P(Lei)  P(Eia)  P(Dad)
 The Existential Quantifier

The expression: xP(x), denotes the existential

quantification of P(x). Translated into the English
language, the expression could also be understood as:
"There exists an x such that P(x)" or "There is at least one
x such that P(x)" is called the existential quantifier, and
x means at least one object x in the universe. If this is
followed by P(x) then the meaning is that P(x) is true for
at least one object x of the universe
• To express the OR of a collection of expressions formed
by substituting every possible value for some variable X,
we need an additional way to create expressions “There
exists” of predicate logic. The operator is ∃, read “there
exists.”
For example, "Someone loves you" could be transformed
into the propositional form, x P(x), where:

P(x) is the predicate meaning: x loves you,

The universe of discourse contains (but is not limited to) all

living creatures.
• For example, let the universe be the set of airplanes and let F(x, y) denote "x flies
faster than y". Then
x  y F(x, y) can be translated initially as "For every airplane x the following holds:
 x is faster than every (any) airplane y". In simpler English it means "Every
airplane is faster than every airplane (including itself !)".
x  y F(x, y) can be read initially as "For every airplane x the following holds: for
some airplane y, x is faster than y". In simpler English it means "Every airplane is
faster than some airplane".
 x  y F(x, y) represents "There exist an airplane x which satisfies the following:
(or such that) for every airplane y, x is faster than y". In simpler English it says
"There is an airplane which is faster than every airplane" or "Some airplane is faster
than every airplane".
 x  y F(x, y) reads "For some airplane x there exists an airplane y such that x is
faster than y", which means "Some airplane is faster than some airplane".
 Order of Quantifiers

• A common logical mistake is to confuse the order of

quantifiers — for example, to think that (∀X)(∃Y ) means
the same as (∃Y )(∀X), which it does not. For example, if
we informally interpret loves(X, Y ) as “X loves Y ,” then
(∀X)(∃Y )loves(X, Y ) means “Everybody loves somebody,”
that is, for every individual X there is at least one individual
Y that X loves. On the other hand, (∃Y )(∀X)loves(X, Y )
means that there is some individual Y who is loved by
everyone
 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, because, for
instance, Q(3) is false. That is, x = 3 is a counterexample
for the statement ∀xQ(x). Thus ∀x Q(x) is false.
 Example

What is the truth value of ∀ P(x), where P(x) is the

statement "x2 < 10" and the domain consists of the positive
integers not exceeding 4?
Solution:
The statement ∀ P(x) is the same as the conjunction
P(l) Ʌ P(2) Ʌ P(3) Ʌ P(4), because the domain consists of
the integers 1, 2, 3, and 4. Because P(4), which is the
statement
"42 < 10," is false, it follows that ∀ P(x) is false.
 Example
What is the truth value of ∃xP(x), where P(x) is the statement
"x2 > 1 0" and the universe of discourse consists of the positive
integers not exceeding 4?
Solution:
Because the domain is { l , 2, 3, 4}, the proposition ∃xP (x) is
the same as the disjunction P(1) v P(2) v P(3) v P(4).
Because P(4), which is the statement "42 > 10," is true, it
follows that ∃xP(x) is true.
 Remember:

• Expressions of predicate logic can be built from

predicates using the operators of propositional logic .
• “Quantifiers” are operators of predicate logic that have no
counterpart in propositional logic. We can use quantifiers
to state that an expression is true for all values of some
argument or that there exists at least one value of the
argument that makes the expression true.
• “Interpretations” for expressions of predicate logic are
possible meanings for the predicates and variables They
are analogous to truth assignments in propositional logic.
• Tautologies of predicate logic are expressions that are
true for all interpretations. Some tautologies of predicate
logic are analogs of tautologies for propositional logic
while others are not.
• Proofs in predicate logic can be carried out in a manner
similar to proofs in propositional logic.
 Exercise
• . Let P(x) be the statement "x can speak Russian" and let Q(x)
be the statement "x knows the computer language C++."
Express each of these sentences in terms of P (x), Q(x),
quantifiers, and logical connectives. The domain for quantifiers
consists of all students at your school.
a) There is a student at your school who can speak Russian and
who knows C++. b) There is a student at your school who can
speak Russian but who doesn't know C++. c) Every student at
your school either can speak Russian or knows C++. d) No
student at your school can speak Russian or knows C++.
Logical Equivalences Involving 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 of discourse is used for the
variables in these propositional functions.
We use the notation S ≡ T to indicate that two statements S
and T involving predicates and quantifiers are logically
equivalent.
∀x(P(x) Ʌ Q(x)) ≡ ∀xP(x) Ʌ ∀x Q(x).
Negating Quantified Expressions

Consider the statement

Everyone in this class has been vaccinated.
∀x P(x)
It’s negation ~∀x(P(x) is the same as Ǝx~P(x)

~∀x(P(x) ≡ Ǝx~P(x)
Consider the statement
There is a student in this class who has been
vaccinated.
Ǝx Q(x)
It’s negation ~Ǝx Q(x) is the same as ∀x~Q(x)

~Ǝx Q(x) ≡ ∀x~Q(x)

De Morgan’s Law for Quantifiers

~∀x(P(x) ≡ Ǝx~P(x)
~Ǝx P(x) ≡ ∀x~P(x)
 Example
What are the negations of the statements ∀x(x2 > x) and Ǝx(x2 = 2)?

Solution:
The negation of ∀x(x2 > x)is the statement ~∀x(x2 > x), which is
equivalent to Ǝx~(x2 > x). This can be rewritten as Ǝx(x2 ≤ 2).
The negation of Ǝx(x2 = 2) is the statement ~Ǝx(x2 = 2) , which is
equivalent to ∀x~(x2 = 2). This can be rewritten as ∀x(x2 ≠ 2).

*The truth values of these statements depend on the domain.