CSE 20: Discrete Mathematics for Computer Science Prof. Shachar Lovett 2 Todays Topics: 1. 2. 3. Predicate Quantifiers Domain Paradoxes
3 1. Predicate Quantification Sometimes and all the time. 4 Im going to assume you know this from the reading: 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 6 Which picture represents the predicate? (Predicate Love(x,y) means x loves y, denoted by arrow from x to y) A. ssss B.
D. None/more/other C. 7 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. 8 Proof strategies overview (more coming later in the quarter) For a universally quantified (for all) statement: To prove it:
To disprove it: Mathematical induction, direct proof, generalization from the generic particular (construction) 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
9 How could we disprove the predicate? (Predicate Love(x,y) means x loves y) A. B. C. D. E. By counterexample: loves everyone By counterexample: loves no one
By counterexample: nobody loves By counterexample: everyone loves Other/more/none show there is a person who Show there is a person who Show there is a person who Show there is a person who 10 What is the correct negation of the predicate?
(Predicate Love(x,y) means x loves y) A. Other/more/none 11 2. Domain Know thy universe In which domain is the following true?
xy.xy A. B. C. D. All All All All 5. real numbers. integers. real numbers less than or equal to 5.
real numbers greater than or equal to In which domain is the following true? xy.x=y2 A. B. C. D. E. Integers Fruits {0,1} {1,2}
None/other/more than one In which domain is the following true? xyz.x=yz A. B. C. D. E. Integers Fruits {0,1} {1,2}
None/other/more than one Common number systems we will encounter in this class Integers = ,-3,-2,-1,0,1,2,3, Even, Odd Naturals = 1,2,3 Rationals
= numbers which can be written as p/q, where p,q are integers (1/2, -2/3, 4/13,) Non-rationals = Numbers which are not rationals (e,,) In which domain is the following true? All A. B. C. D.
E. cows are white USA England France This room None/other/more than one 17 3. Contradiction and Paradox Q: Do you like CSE 20?
A: Yes and no. 18 Is this sentence true? This sentence is false. a) b) TRUE FALSE 19 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? 20
Is this sentence true? This sentence is true. a) b) TRUE FALSE 21 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: 22 Pinocchios Paradox
23 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: a) b) c) d)
Does the barber shave himself? YES NO Not enough information Other 24 List Organization Question (aka Russells 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