Discrete Structures
Nested Quantifiers
Nested Quantified Expressions
Predicates can have more than one variables
P(x, y) : x teaches course y in CUI-ATK
Q(x, y, z) : x is an instructor of course y in university z
S(x, y, z) : x + y = z
Each variable needs to be given value or quantified to make the
predicate a proposition
Nested Quantified Expressions
Nested Quantified Expressions
Nested Quantified Expressions
Nested Quantified Expressions
Nested Quantified Expressions
Nested Quantified Expressions
Order of quantifier is extremely important
∀x∃y P(x, y) is not the same as ∃y∀x P(x, y)
Q(x, y, z) : x is an instructor of course y in university z
∀z ∀y ∃x Q(x, y, z): In every uni. for every course there is an instructor
∀z ∃x ∀y Q(x, y, z): In every uni. there is an instructor for all courses
∃x ∀y ∀z Q(x, y, z): There is an instructor for every course in every uni.
Nested Quantified Expressions
Nested Quantified Expressions
Nested Quantified Expressions
Nested Quantified Expressions
Translate these statements expressing some mathematical fact into English Let the Universe
of discourse for all variables be real
∀x∃y (x + y = 0) True
Every real number has an additive inverse
∃x∀y (x + y = y) True
There exists an additive identity of all real numbers
∀x∃y (x ̸= 0) → (xy = 1) true
Every non-zero real number has a multiplicative inverse
∃x∀y (xy = y) true
There exists a multiplicative identity of all real numbers
Proof: ∀x∃y (x + y = 0) true
For x=1 (1+(-3)=-2 V 1-2=-1 V 1-1 = 0 V 1+0 = 1 …… ) true
^
For x=2 (2-3=-1 V 2-2=0 V 2-1 = 1 V 2+0=2 …….. ) true
^
For x=3 (3-3=0 V 3-2=1 V 3-1 = 2 V 3+0=3 ^…….. ) true
….
True ^ true ^ true … = true
Proof: ∃x∀y (x + y = y) True
For x=0 (0+1=1 ^ 0+2=2 ^ 0+3 = 3 ^ 0+4 = 4 ^ …… ) true
V
For x=1 (1+1=2 ^ 1+2=3 ^ 1+3 = 4 ^ 1+4=5 ^…….. ) false
V
For x=2 (2+1=3^ 2+2=4 ^ 2+3 = 5 ^ 2+4=6 ^…….. ) false
….
True V false V false V … = true (proved)
Proof: ∀x∃y (x ≠ 0) → (xy = 1) true
For x=1 (1*1=1 V 1*2=2 V 1*3 = 3 V 1*4 = 4 V …… ) true
^
For x=2 (2*1/2=1 V 2*1=2 V 2*2 = 4 V 2*3=6 V…….. ) true
^
….
True V true … = true
Proof: ∃x∀y (xy = y) true
For x=1 (1*1=1 ^ 1*2=2 ^ 1*3 = 3 ^ 1*4 = 4 ^ …… ) true
V
For x=2 (2*1=2^ 2*2=4 ^ 2*3 = 6 ^ 2*4=8 ^…….. ) false
V
For x=3 (3*1=3^ 3*2=6 ^ 3*3 = 9 ^ 3*4=12 ^…….. ) false
….
True V false V false V … = true
Nested Quantified Expressions
Nested Quantified Expressions
Assignment Q1 Prove all of these statements with suitable examples. Please
check slide 8 of lecture 6 and follow its approach to answer this question.
Nested Quantified Expressions
Let the universe of discourse for both variables be the set of integers. Determine whether the
following universally quantified statements are true or false. If false give one counter-example for
each part.
FALSE
False
FALSE
FALSE
FALSE
TRUE
TRUE
FALSE
FALSE
ASSIGNMENT
QUESTION # 2
Rewrite all the false predicates mentioned on the previous slide to
make them true. You can change the expression or quantifier.
Nested Quantified Expressions
Assignment question 3. Rewrite each of these statements so that negations appear only
within predicates (that is, so that no negation is outside a quantifier or an expression
involving logical connectives
Hint: Focus on the de-Morgans laws OR take help
from the following example
Relevant Exercise Questions
Exercise 1.1; 1,2, 6, 11, 13, 16-18, 27-39
Exercise 1.3; 1-6, 9-10
Exercise 1.4; 1,2, 5-7, 9, 11-18
Exercise 1.5; 1-4, 24-30, 39-40, 45,46
