Quantifiers in Discrete Mathematics
CSE 20
DISCRETE MATH
Prof. Shachar Lovett
C
l
i
c
k
e
r
f
r
e
q
u
e
n
c
y
:
C
A
Todays topics
•
Boolean logic: quantifiers
•
Paradoxes
•
S
e
c
t
i
o
n
s
3
.
2
-
3
.
4
i
n
J
e
n
k
y
n
s
,
S
t
e
p
h
e
n
s
o
n
Quantifiers
•
Universal:
•
Existential:
•
Example:
x,y
z, x-y=z
•
The
universe
where inputs live is important
•
Our example is:
•
True
if x,y,z are integers
•
False
if x,y,z are positive integers
Some examples
We’re going to focus on:
•
“Nested” quantifiers/more than one quantifier
•
General strategy for proving (or disproving) quantified
statements
A
.
D
.
N
o
n
e
/
m
o
r
e
/
o
t
h
e
r
B
.
C
.
Which picture represents the predicate?
(Predicate Love(x,y) means “x loves y”, denoted by arrow from x to y)
A
.
D
.
N
o
n
e
/
m
o
r
e
/
o
t
h
e
r
B
.
C
.
Which picture represents the predicate?
(Predicate Love(x,y) means “x loves y”, denoted by arrow from x to y)
Proof strategies overview
(more coming later)
•
F
o
r
a
u
n
i
v
e
r
s
a
l
l
y
q
u
a
n
t
i
f
i
e
d
(
“
f
o
r
a
l
l
”
)
s
t
a
t
e
m
e
n
t
:
•
T
o
p
r
o
v
e
i
t
:
•
direct proof, generalization from the generic particular
(construction), mathematical induction
•
T
o
d
i
s
p
r
o
v
e
i
t
:
•
Provide a single counterexample
•
F
o
r
a
n
e
x
i
s
t
e
n
t
i
a
l
l
y
q
u
a
n
t
i
f
i
e
d
(
“
t
h
e
r
e
e
x
i
s
t
s
”
)
s
t
a
t
e
m
e
n
t
:
•
T
o
p
r
o
v
e
i
t
:
•
Provide a single example
•
T
o
d
i
s
p
r
o
v
e
i
t
:
•
State the correct version as a universally quantified statement (“For
all x,
not
P(x)”) then prove it using above methods
What is the correct negation of the predicate?
(Predicate Love(x,y) means “x loves y”)
What is the correct negation of the predicate?
(Predicate Love(x,y) means “x loves y”)
Black swans
“All swans are white”
I lived 100 years. All the swans I saw in my lifetime are
white. Is this enough for the predicate to be true?
A.
Yes
B.
No
Black swans
“All swans are white”
I lived 101 years. I saw one black swan in all this time. Is
this enough for the predicate to be false?
A.
Yes
B.
No
Paradoxes
•
Lets have some fun with paradoxes
•
They actually have deep mathematical meaning
•
They came up when mathematicians and philosophers
tried to understand some “corner cases” in math and logic
Is this sentence true?
“This sentence is true”
A.
True
B.
False
Is this sentence true?
“This sentence is false”
A.
True
B.
False
Liar’s Paradox
“This sentence is false”
•
This has been perplexing people since at least the Greeks in 4
th
century BCE (2300 years!)
•
What are some key features of this that make it a paradox?
Grandparent Paradox
(Time Travel Paradox)
•
You travel back in time and prevent one pair of your
biological grandparents from ever meeting each other
(assume this prevents your birth).
•
Now who will go back in time to prevent your grandparents from
meeting?
•
Pop culture version:
Pinocchio’s Paradox
The Barber
•
A certain town has only one barber (a man). Every man
in the town is clean-shaven. For each man
m
in the
town, the barber shaves
m
if and only if
m
does not
shave himself.
•
Question: Does the barber shave himself?
a)
YES
b)
NO
c)
Not enough information
d)
Other
List Organization Question
(aka Russell’s paradox)
•
Suppose you have many lists and some of your lists are
lists of lists
(to help you organize your lists), and some
lists even include themselves.
•
You make a list of all lists that do
not
include themselves,
called
NON-DANGER-LIST
.
•
Question:
•
Should
NON-DANGER-LIST
include itself?
a)
YES
b)
NO
c)
Not enough information
d)
Other
Next class
•
Simplification rules
•
Implications and common mistakes using them
•
R
e
a
d
s
e
c
t
i
o
n
s
3
.
2
-
3
.
4
i
n
J
e
n
k
y
n
s
,
S
t
e
p
h
e
n
s
o
n
Delve into the world of discrete mathematics with a focus on quantifiers, including universal and existential examples. Learn about proving and disproving quantified statements, along with strategies like direct proof, counterexamples, and mathematical induction. Explore the concept of predicates and negations in mathematical logic.
Uploaded on Oct 10, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics Boolean logic: quantifiers Paradoxes Sections 3.2-3.4 in Jenkyns, Stephenson
Quantifiers Universal: Existential: Example: x,y z, x-y=z The universe where inputs live is important Our example is: True if x,y,z are integers False if x,y,z are positive integers
Some examples For all even numbers x and y, the sum of x and y is also even. ?,? ?, ? + ? ? There exists an integer g such that g is greater than 5. ? ? ?.?. ? > 5
Were going to focus on: Nested quantifiers/more than one quantifier General strategy for proving (or disproving) quantified statements
Which picture represents the predicate? (Predicate Love(x,y) means x loves y , denoted by arrow from x to y) A. B. C. D. None/more/other
Which picture represents the predicate? (Predicate Love(x,y) means x loves y , denoted by arrow from x to y) A. B. C. D. None/more/other
Proof strategies overview (more coming later) For a universally quantified ( for all ) statement: To prove it: direct proof, generalization from the generic particular (construction), mathematical induction To disprove it: Provide a single counterexample For an existentially quantified ( there exists ) statement: To prove it: Provide a single example To disprove it: State the correct version as a universally quantified statement ( For all x, not P(x) ) then prove it using above methods
What is the correct negation of the predicate? (Predicate Love(x,y) means x loves y ) ? ?.????(?,?) A. By counterexample: show there is a person who loves everyone B. By counterexample: Show there is a person who loves no one C. By counterexample: Show there is a person who nobody loves D. By counterexample: Show there is a person who everyone loves E. Other/more/none
What is the correct negation of the predicate? (Predicate Love(x,y) means x loves y ) ? ?.????(?,?) A. ? ?.~???? ?,? B. ? ?.~????(?,?) C. ? ?.~???? ?,? D. ? ?.~????(?,?) E. Other/more/none
Black swans All swans are white I lived 100 years. All the swans I saw in my lifetime are white. Is this enough for the predicate to be true? A. Yes B. No
Black swans All swans are white I lived 101 years. I saw one black swan in all this time. Is this enough for the predicate to be false? A. Yes B. No
Paradoxes Lets have some fun with paradoxes They actually have deep mathematical meaning They came up when mathematicians and philosophers tried to understand some corner cases in math and logic
Is this sentence true? This sentence is true A. True B. False
Is this sentence true? This sentence is false A. True B. False
Liars Paradox This sentence is false This has been perplexing people since at least the Greeks in 4th century BCE (2300 years!) What are some key features of this that make it a paradox?
Grandparent Paradox (Time Travel Paradox) You travel back in time and prevent one pair of your biological grandparents from ever meeting each other (assume this prevents your birth). Now who will go back in time to prevent your grandparents from meeting? Pop culture version:
The Barber A certain town has only one barber (a man). Every man in the town is clean-shaven. For each man m in the town, the barber shaves m if and only if m does not shave himself. Question: Does the barber shave himself? a) YES b) NO c) Not enough information d) Other
List Organization Question (aka Russell s paradox) Suppose you have many lists and some of your lists are lists of lists (to help you organize your lists), and some lists even include themselves. You make a list of all lists that do not include themselves, called NON-DANGER-LIST. Question: Should NON-DANGER-LIST include itself? a) YES b) NO c) Not enough information d) Other
Next class Simplification rules Implications and common mistakes using them Read sections 3.2-3.4 in Jenkyns, Stephenson
