Transcript slides - UCSD CSE

CSE 20
DISCRETE MATH
Prof. Shachar Lovett
http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Clicker
frequency:
CA
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
We’re 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.
D. None/more/other
C.
Which picture represents the predicate?
(Predicate Love(x,y) means “x loves y”, denoted by arrow from x to y)

A.
B.
D. None/more/other
C.
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
B.
C.
D.
E.
loves everyone
By counterexample: Show there is a person who
loves no one
By counterexample: Show there is a person who
nobody loves
By counterexample: Show there is a person who
everyone loves
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
Liar’s 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:
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)
b)
c)
d)
YES
NO
Not enough information
Other
Next class
• Simplification rules
• Implications and common mistakes using them
• Read sections 3.2-3.4 in Jenkyns, Stephenson