DISCRETE
STRUCTURES
Lecture 11
Quantifiers
Dr. Irfana Bibi
Assistant Professor,
Department of Computer Science,
FCIT, Punjab University, Lahore
Irfana.bibi@pucit.edu.pk
Applications of Logic
2
Basic Logic Gates
x
• Not x where x = ¬x
x xy
• And y where xy = x y
x x+y
• Or y where x+y = x y
x xy
• Nand y where ¬(xy)= xy
x x+y
• Nor y
xÅy
• Xor x
y
Constructing Circuits
Here is the circuit of the statement
(p q) (~p q) (p ~q)
Cont...
Following is the circuit output of the following
statement
(x + y) ¬ y
x
y
Constructing Circuits
Here is the circuit of the following statement:
(P Q ~R) (~ P Q R)
Predicates and Quantified statements
Predicates
A predicate is a sentence which contains finite number of
variables and becomes a statement when specific values
are substituted for the variables.
The domain of a predicate variable is the set of all values that
may be substituted in place of the variable
Truth Set
If P(x) is a predicate and x has domain D, the truth set of
P(x) is the set of all elements of D that make P(x) true
when substituted for x. The truth set of P(x) is denoted by
{x D | P( x)}
read as “the set of all x in D such that P(x)”.
Notation
For any two predicates P(x) and Q(x), the notation
P( x) Q( x) means that every element in the truth set of
P(x) is in the truth set of Q(x).
The notation P( x) Q( x) means that P and Q have
identical truth sets.
Consider the predicate: x 0, xR
The truth set of the above predicate is x R + x 0
Cont…
Example
Let P(x) = x is a factor of 8, Q(x)= x is a factor of 4
and R(x)= x < 5 and x 3 . The domain of x is
assumed to be Z .+ Use symbols , to indicate
true relationships among P(x), Q(x) and R(x).
a. The truth set of P(x) is {1,2,4,8}, Q(x) is {1,2,4}.
Since every element in the truth set of Q(x) is in the
truth set of P(x), So Q( x) P( x)
b. The truth Set of R(x) is {1,2,4}, which is identical to
the truth set of Q(x). Hence Q( x) R( x) .
Universal and Existential Statements
Let Q(x) be a predicate and D the domain of x.
A universal statement is of the form “ x D, Q( x) ”.
It is true if and only if Q(x) is true for all x in D
and it is false if and only if Q(x) is false for at least one
x in D.
A value for x for which Q(x) is false is called a counter
example to the universal statement.
Universal and Existential Statements
Example: Let D={1,2,3,4,5} and consider the
statement x D, x x. Show that this statement is true.
2
Solution: Check that " x 2 x ". is true for each individual
x in D.
12 1 32 3
52 5
22 2 42 4
Hence x D, x x. is true.
2
The technique used in above example while showing
the truthness of the universal statement is called
method of exhaustion.
Cont…..
Consider the statement x R, x 2
x.
Find the counter example to show that this statement is
not true.
Counter example . Take x=1/2, then x is in R and
2
1 1
2 2
0.25 0.50
Hence x R, x 2 x. is false.
Existential Quantifier
Let Q(x) be a predicate and D the domain of
x. An existential statement is of the form.
x D such that Q(x)
It is true if and only if Q(x) is true for at least
one x in D.
It is false if and only if Q(x) is false for all x in
D.
The symbol denotes “there exist” and is
called the existential quantifier.
Truth and falsity of Existential statements
Suppose P(x) is the predicate “x < |x|.” Determine the
truth value of ∃ x s.t. P(x) where the domain 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 because in each
case x = |x|. Therefore, ∃ x such that P(x) is false for
this domain.
(b) If we begin checking the six values of x, we find
P(−2) is true. It states that −2 < |−2|.
We need to check no further; having one case that
makes the predicate true is enough to guarantee that
∃ x s.t. P(x) is true.
Truth and falsity of Existential statements
Ex.1: Consider the statement ∃𝑚 ∈ 𝑍 𝑠. 𝑡. 𝑚2 = 𝑚 .
Show that this statement is true.
Sol: observe that 12
= 1 . Thus m 2
= m is true for at
least one integer m.
Hence m Z s.t. m2 = m is true.
Ex.2:
Let G={5,6,7,8,9,10} and consider the
statement ∃𝑚 ∈ 𝐺 𝑠. 𝑡. 𝑚2 = 𝑚
Show that this statement is false.
Sol: the statement is not true for every value of
the G. Thus ∃𝑚 ∈ 𝐺 𝑠. 𝑡. 𝑚2 = 𝑚 is false.
Translating from formal to informal language
Rewrite the following statements in a variety of
equivalent but more informal ways. Do not use the
symbol ,
a) x R, x2 0.
b) x R, x 2 −1.
c) m Z s.t. m = m
2
Solution: a) we can write the statement in many ways
like “ All real numbers have non negative squares”,
“No real number has a negative square”,
“ x has a non negative square, for each value of x”.
Cont….
b). Similarly we can translate the second statement in
these ways.
“ All real numbers have squares not equal to -1”,
“No real number have square equal to -1”.
c). “There is an integer whose square is equal to itself”,
“we can find at least one integer equal to its own
square”
Book Reading: Pg 43-47 (includes Example 1-16)
Homework:
“Exercise 1.4 on page 56 of Text Book”
Q 1-8,11,12,13,37,38.
Discrete Structures 19
