CSE 311 Foundations of Computing I

Publish in

Documents

5 views

View again

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
• 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

Previous Document

News Best Books Arco GRE/GMAT Math Review (Peterson s GRE/GMAT Math Review) Unlimited by David Frieder

Next Document

PDF Online Sweet Talk For Kindle

Related Documents Mar 17, 2018

EGR 105 Foundations of Engineering I Section 8

View more...
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
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x