CSE115/ENGR160 Discrete Mathematics 01/25/11Logical equivalencesSlide 3Slide 4Negating quantified expressionsExampleTranslating English into logical expressionsUsing quantifiers in system specificationsSlide 91.4 Nested quantifiersQuantification as loopSlide 12Order of quantificationQuantification of two variablesQuantification with more variablesTranslating mathematical statementsSlide 17Express limit using quantifiersTranslating statements into EnglishNegating nested quantifiersCSE115/ENGR160 Discrete Mathematics01/25/11Ming-Hsuan YangUC Merced1Logical equivalences•S≡T: Two statements S and T involving predicates and quantifiers are logically equivalent–If and only if they have the same truth value no matter which predicates are substituted into these statements and which domain is used for the variables.–Example: i.e., we can distribute a universal quantifier over a conjunction2)()())()(( xxqxxpxqxpx •Both statements must take the same truth value no matter the predicates p and q, and non matter which domain is used• Show–If p is true, then q is true (p → q)–If q is true, then p is true (q → p)3)()())()(( xxqxxpxqxpx )()())()(()()())()((xxqxxpxqxpxxxqxxpxqxpx•(→) If a is in the domain, then p(a)˄q(a) is true. Hence, p(a) is true and q(a) is true. Because p(a) is true and q(a) is true for every element in the domain, so is true•(←) It follows that are true. Hence, for a in the domain, p(a) is true and q(a) is true, hence p(a)˄q(a) is true. If follows is true 4)()())()(( xxqxxpxqxpx )()( xxqxxp )( and )( xxqxxp ))()(( xqxpx )()())()(( xxqxxpxqxpx Negating quantified expressions5Negations of the following statements“There is an honest politician”“Every politician is dishonest”(Note “All politicians are not honest” is ambiguous)“All Americans eat cheeseburgers”Example6))()(()))()((()))()((()()((xqxpxxqxpxxqxpxxqxpx))()(())()(( Show xqxpxxqxpx )()()(222xxxxxxxxx)2()2()2(222xxxxxx?)2( and )( of negations theareWhat 22 xxxxxTranslating English into logical expressions•“Every student in this class has studied calculus” Let c(x) be the statement that “x has studied calculus”. Let s(x) be the statement “x is in this class”7people all of consistsdomain theif ?)()(people all of consistsdomain theif )()(class thisof students of consistsdomain theif )(xcxsxxcxsxxcxUsing quantifiers in system specifications•“Every mail message larger than one megabyte will be compressed” Let s(m,y) be “mail message m is larger than y megabytes” where m has the domain of all mail messages and y is a positive real number. Let c(m) denote “message m will be compressed” 8))()1,(( mcmsm Example•“If a user is active, at least one network link will be available” Let a(u) represent “user u is active” where u has the domain of all users, and let s(n, x) denote “network link n is in state x” where n has the domain of all network links, and x has the domain of all possible states, {available, unavailable}.9)available,()( nsnuau 1.4 Nested quantifiers100 is ),( and ),( is )( where)( as same0)(yxyxpyxypxqxxqyxyx))0()0()0(())()(()(xyyxyxzyxzyxzyxxyyxyxLet the variable domain be real numberswhere the domain for these variables consists of real numbersQuantification as loop•For every x, for every y –Loop through x and for each x loop through y–If we find p(x,y) is true for all x and y, then the statement is true–If we ever hit a value x for which we hit a value for which p(x,y) is false, the whole statement is false•For every x, there exists y –Loop through x until we find a y that p(x,y) is true–If for every x, we find such a y, then the statement is true11),( yxypx),( yxypxQuantification as loop• : loop through the values for x until we find an x for which p(x,y) is always true when we loop through all values for y–Once found such one x, then it is true• : loop though the values for x where for each x loop through the values of y until we find an x for which we find a y such that p(x,y) is true–False only if we never hit an x for which we never find y such that p(x,y) is true12),( yxypx),( yxypxOrder of quantification13?),(),(),(number real isdomain theand ,statement thebe ),(Let yxxpyyxypxyxypxxyyxyxp?),(),(it true? Is mean?it doesWhat :),(it true? Is mean?it does What :),(number real isdomain theand,0statement thebe ),(Let yxypxyxxpyyxyqxyxxqyyxyxqQuantification of two variables14Quantification with more variables15it true? Is mean?it doesWhat :),,(it true? Is mean?it doesWhat :),,(number real isdomain theand ,statement thebe ),,(Let zyxyqxzzyxzqyxzyxzyxqTranslating mathematical statements•“The sum of two positive integers is always positive”16integers all of consists blesboth variafor domain thewhere))0()0()0((  yxyxyxintegers positive all of consists blesboth variafor domain thewhere)0(  yxyxExample•“Every real number except zero has a multiplicative inverse”17numbers real of consists blesboth variafor domain thewhere))1()0((  xyyxxExpress limit using quantifiers is for every real number ε>0, there exists a real number δ>0, such that |f(x)-L|<ε whenever 0<|x-a|<δ18Lxfax)(lim Recallnumber real isfor x domain theandnumber, real positive is and for domain thewhere)|)(|||0( Lxfaxxnumber real is , and,,for domain thewhere)|)(|||0(00xLxfaxxTranslating statements into English• where c(x) is “x has a computer”, f(x,y) is “x and y are friends”, and the domain for both x and y consists of all students in our school• where f(x,y) means x and y are friends, and the domain consists of all students in our school19))),()(()(( yxfycyxcx )),())(),(),((( zyfzyzxfyxfzyx Negating nested