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 311AnnouncementsReading assignments Predicates and Quantifiers 1.4, 1.5 7th Edition 1.3, 1.4 5th and 6th Edition CSE 311Predicate CalculusPredicate 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 311Quantifiersx 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 Integersx 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 Integersxy Greater (y, x) xy Greater (x, y) xy (Greater(y, x) Prime(y)) x (Prime(x) (Equal(x, 2) Odd(x)) xy(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” xyz((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)xyz ((Greater(x, 2) Even(x)) (Equal(x, y+z) Prime(y) Prime(z)) Domain:Positive IntegersCSE 311Scope of QuantifiersNotlargest(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 Quantifiersx (P(x) Q(x)) vsx P(x) x Q(x) CSE 311Nested QuantifiersBound 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 QuantifiersNot 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 Quantifiersx P(x) x P(x) x P(x) x P(x)CSE 311De Morgan’s Laws for Quantifiersx 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

Related Documents

Oct 7, 2017

Feb 28, 2018

Mar 13, 2018

Mar 13, 2018

Mar 13, 2018

Mar 17, 2018

Mar 17, 2018

Mar 17, 2018

Mar 18, 2018

Mar 19, 2018

Mar 23, 2018

Mar 24, 2018

Mar 29, 2018

Apr 2, 2018

Apr 16, 2018

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