CSE 20 - Discrete Mathematics

CSE 20 - Discrete Mathematics

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

Recently Viewed Presentations

  • OxyFuel Equipment Introduction  Oxyfuel welding is a welding

    OxyFuel Equipment Introduction Oxyfuel welding is a welding

    Primary uses today are heating, brazing and cutting. * OxyFuel Safety The hazards of oxyfuel welding are primarily compressed gas cylinders, flammable gases and open flame. Common concerns are (pg 294) PPE (shade 4 face shield/goggles, gloves). Store and handle...
  • Fluency Clinic - COE

    Fluency Clinic - COE

    The Camperdown Program (O'Brien, Packman, & Onslow 2008) The Fluency Plus Program (Kroll & Scott-Sulsky) The SpeechEasy Device. Pharmacologic Interventions. Demands for Technology. Copy of prolonged speech recording and means of playing it (either audio or audiovisual) and an individual...
  • 26.3 Birds TEKS 7A, 7B, 10A The student

    26.3 Birds TEKS 7A, 7B, 10A The student

    Times MS Pゴシック Arial Calibri Blank Presentation 1_Blank Presentation The student is expected to: 7A analyze and evaluate how evidence of common ancestry among groups is provided by the fossil record, biogeography, and homologies, including anatomical, molecular, and developmental; 7B...
  • HISTORIA #1 - Oregon

    HISTORIA #1 - Oregon

    "American Dreams" 2. This is a new method that we're using, where forest workers tell their own stories. This story that you are about to watch is the story of a forest worker who was constantly abused and humiliated by...
  • Unit 3: cells - JENSEN BIOLOGY

    Unit 3: cells - JENSEN BIOLOGY

    Fine adjustment knob: this is the smaller of the two adjustment knobs and it is used to move the stage slightly to sharpen the image. Light source: projects light upwards through the slide/specimen, diaphragm, and lenses. Usually a light, though...
  • Livestock Grazing for Fishable Waters: A Catchment Approach

    Livestock Grazing for Fishable Waters: A Catchment Approach

    This collapse results in a change in the active channel's width/depth ratio, gradient, and sinuosity, which reduces a riparian-wetland area's ability to dissipate energy. The intent of item 9 is to document that the streambanks have the right plants or...
  • Presidential Policy Directive PPD/8 National Preparedness ...

    Presidential Policy Directive PPD/8 National Preparedness ...

    How Can Grant Funding Be Utilized. ... Performance threshold(s) for each core capability that will guide our allocation of resources to support national preparedness. ... Presidential Policy Directive PPD/8 National Preparedness - Requirements and Approach to Implementation ...
  • Photography Composition using the Elements and Principles of Art

    Photography Composition using the Elements and Principles of Art

    Photography Content using the Elements and Principles of Art ELEMENTS are the basic building blocks Art Line Shape/Form Space Value Texture Color Emphasis Balance Unity Contrast Movement/ Rhythm Pattern/Repetition PRINCPLES of Art Elements The basic building blocks Line Shape/Form Space...