CSE 311 Foundations of Computing I

Publish in

Documents

4 views

Please download to get full document.

View again

of 16
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
CSE 311 Foundations of Computing I. Lecture 6 Predicate Calculus Autumn 2012. Announcements. Reading assignments Predicates and Quantifiers 1.4, 1.5 7 th Edition 1.3, 1.4 5 th and 6 th Edition. Predicate Calculus. Predicate or Propositional Function
Transcript
CSE 311 Foundations of Computing ILecture 6Predicate CalculusAutumn 2012CSE 311Announcements
  • Reading assignments
  • Predicates and Quantifiers
  • 1.4, 1.5 7th Edition
  • 1.3, 1.4 5th and 6th Edition
  • CSE 311Predicate Calculus
  • Predicate or Propositional Function
  • A function that returns a truth value
  • “x is a cat”
  • “x is prime”
  • “student x has taken course y”
  • “x > y”
  • “x + y = z” or Sum(x, y, z)
  • NOTE: We will only use predicates with variables or constants as arguments.Prime(65353)CSE 311Quantifiers
  • x P(x) : P(x) is true for every x in the domain
  • x P(x) : There is an x in the domain for which P(x) is true
  • Relate  and  to  and CSE 311Statements with quantifiersDomain:Positive Integers
  • x Even(x)
  • x Odd(x)
  • x (Even(x)  Odd(x))
  • x (Even(x)  Odd(x))
  • x Greater(x+1, x)
  • x (Even(x)  Prime(x))
  • Even(x)Odd(x)Prime(x)Greater(x,y)Equal(x,y)CSE 311Statements with quantifiersDomain:Positive Integers
  • xy Greater (y, x)
  • xy Greater (x, y)
  • xy (Greater(y, x)  Prime(y))
  • x (Prime(x)  (Equal(x, 2)  Odd(x))
  • xy(Sum(x, 2, y)  Prime(x)  Prime(y))
  • Even(x)Odd(x)Prime(x)Greater(x,y)Equal(x,y)Sum(x,y,z)CSE 311Statements with quantifiersDomain:Positive IntegersEven(x)Odd(x)Prime(x)Greater(x,y)Sum(x,y,z)
  • “There is an odd prime”
  • “If x is greater than two, x is not an even prime”
  • xyz((Sum(x, y, z)  Odd(x)  Odd(y)) Even(z))
  • “There exists an odd integer that is the sum of two primes”
  • CSE 311English to Predicate Calculus
  • “Red cats like tofu”
  • Cat(x)Red(x)LikesTofu(x)CSE 311Goldbach’s Conjecture
  • Every even integer greater than two can be expressed as the sum of two primes
  • Even(x)Odd(x)Prime(x)Greater(x,y)Equal(x,y)
  • xyz ((Greater(x, 2)  Even(x))  (Equal(x, y+z)  Prime(y)  Prime(z))
  • Domain:Positive IntegersCSE 311Scope of Quantifiers
  • Notlargest(x) y Greater (y, x) z Greater (z, x)
  • Value doesn’t depend on y or z “bound variables”
  • Value does depend on x “free variable”
  • Quantifiers only act on free variables of the formula they quantify
  •  x ( y (P(x,y)  x Q(y, x)))
  • CSE 311Scope of Quantifiers
  • x (P(x)  Q(x)) vsx P(x) x Q(x)
  • CSE 311Nested Quantifiers
  • Bound variable name doesn’t matter
  •  x  y P(x, y)  a  b P(a, b)
  • Positions of quantifiers can change
  •  x (Q(x)  y P(x, y))  x  y (Q(x)  P(x, y))
  • BUT: Order is important...
  • CSE 311Quantification with two variablesCSE 311Negations of Quantifiers
  • Not every positive integer is prime
  • Some positive integer is not prime
  • Prime numbers do not exist
  • Every positive integer is not prime
  • CSE 311De Morgan’s Laws for Quantifiersx P(x) x P(x) x P(x) x P(x)CSE 311De Morgan’s Laws for Quantifiersx P(x) x P(x) x P(x) x P(x)“There is no largest integer”
  •   x  y ( x ≥ y)
  • x  y ( x ≥ y)
  • x  y  ( x ≥ y)
  • x  y (y > x)
  • “For every integer there is a larger integer”CSE 311
    Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks