KEMBAR78
Nested Quantifiers in Discrete Math | PDF | Deductive Reasoning | Theoretical Computer Science
Scribd
Upload
161 views2 pages

Nested Quantifiers in Discrete Math

This document discusses nested quantifiers and provides examples of expressing statements using quantifiers with predicates over various domains. Some key points: - Nested quantifiers are quantifiers within the scope of other quantifiers, like ∀x∃yP(x,y). Order matters between quantifiers. - Examples show translating English statements to quantifier expressions, like "Everybody loves somebody" to ∀x∃yL(x,y) - Problems ask to express additional statements over student websites visited or email/calls between classmates. - One section asks to rewrite quantifier statements so that negations only appear in predicates using De Morgan's laws.

Uploaded by

QuangHuyĐoàn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
161 views2 pages

Nested Quantifiers in Discrete Math

This document discusses nested quantifiers and provides examples of expressing statements using quantifiers with predicates over various domains. Some key points: - Nested quantifiers are quantifiers within the scope of other quantifiers, like ∀x∃yP(x,y). Order matters between quantifiers. - Examples show translating English statements to quantifier expressions, like "Everybody loves somebody" to ∀x∃yL(x,y) - Problems ask to express additional statements over student websites visited or email/calls between classmates. - One section asks to rewrite quantifier statements so that negations only appear in predicates using De Morgan's laws.

Uploaded by

QuangHuyĐoàn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

ICS 141: Discrete Mathematics I (Fall 2014)

1.5 Nested Quantifiers


Nested quantifiers are quantifiers that occur within the scope of other quantifiers.
Example: ∀x∃yP (x, y)

Quantifier order matters!


∀x∃yP (x, y) 6= ∃y∀xP (x, y)

1.5 pg. 65 # 9
Let L(x, y) be the statement “x loves y,” where the domain for both x and y consists of all people
in the world. Use quantifiers to express each of these statements.

a) Everybody loves Jerry.


∀xL(x, Jerry)

b) Everybody loves somebody.


∀x∃yL(x, y)

c) There is somebody whom everybody loves.


∃y∀xL(x, y)

d) Nobody loves everybody.


∀x∃y¬L(x, y) or ¬∃x∀yL(x, y)

i Everyone loves himself or herself


∀xL(x, x)

1.5 pg. 64 # 5
Let W (x, y) mean that student x has visited website y, where the domain for x consists of all
students in your school and the domain for y consists of all websites. Express each of these
statements by a simple English sentence.

d ∃y(W (Ashok Puri,y) ∧ W (Cindy Yoon, y))


There is a website that both Ashok and Cindy have visited.

e ∃y∀z(y 6= (David Belcher) ∧ (W (David Belcher, z) → W (y, z)))


There is a person besides David who has visited all the websites that David has visited.

f ∃x∃y∀z(((x 6= y) ∧ (W (x, z) ↔ W (y, z))))


There are two distinct people who have visited exactly the same sites.

1
ICS 141: Discrete Mathematics I (Fall 2014)

1.5 pg. 66 # 13
Let M (x, y) be “x has sent y an e-mail message” and T (x, y) be “x has telephoned y,” where the
domain consists for all students in your class. Use quantifiers to express each of these statements.

k There is a student in your class who has not received an e-mail message from anyone else in
the class and who has not been called by any other student in the class.
∃x∀y((x 6= y) → (¬M (y, x) ∧ ¬T (y, x)))

l Every student in the class has either received an e-mail message or received a telephone call
from another student in the class.
∀x∃y((x 6= y) ∧ (M (y, x) ∨ T (y, x)))

m There are at least two students in your class such that one student has sent the other e-mail
and the second student has telephoned the first student
∃x∃y((x 6= y) ∧ (M (x, y) ∧ T (y, x)))

1.5 pg. 67 # 33
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).

a) ¬∀x∀yP (x, y)
¬∀x∀yP (x, y)
≡ ∃x¬∀yP (x, y) De Morgan’s laws for quantifiers
≡ ∃x∃y¬P (x, y) De Morgan’s laws for quantifiers

d ¬(∃x∃y¬P (x, y) ∧ ∀x∀y(Q(x, y))


¬(∃x∃y¬P (x, y) ∧ ∀x∀y(Q(x, y))
≡ (¬∃x∃y¬P (x, y)) ∨ (¬∀x∀yQ(x, y)) De Morgan’s Law
≡ (∀x¬∃y¬P (x, y)) ∨ (¬∀x∀yQ(x, y)) De Morgan’s laws for quantifiers
≡ (∀x∀y¬¬P (x, y)) ∨ (¬∀x∀yQ(x, y)) De Morgan’s laws for quantifiers
≡ (∀x∀yP (x, y)) ∨ (¬∀x∀yQ(x, y)) Double Negation
≡ (∀x∀yP (x, y)) ∨ (∃x¬∀yQ(x, y)) De Morgan’s laws for quantifiers
≡ (∀x∀yP (x, y)) ∨ (∃x∃y¬Q(x, y)) De Morgan’s laws for quantifiers

You might also like