MACM 101 Lecture 9: Lecture 9 Part 2_ Logic Equivalence

• School: Simon Fraser University
• Department: Math & Comp Sci
• Course: MACM 101
• Professor: Andrei Bulatov

Document Summary

X (p(x) q(x)) ( x p(x)) ( x q(x)) X (p(x) q(x)) is not equivalent to ( x p(x)) ( x q(x)) X p(x) is false if and only if there is a such that p(a) is false. This means that ( x p(x)) x p(x) Not all lions are fierce" there is a peaceful lion" . Not all people like coffee some people don"t like coffee . There is no number such that a2 = -1 for all numbers a2 1 . Logic equivalences for statements with multiple quantifiers are similar to those with one quantifier. X y (p(x) (q(y) r(x,y))) x y ((p(x) q(y)) (p(x) r(x,y))) X y (p(x,y) q(y,x)) x y ( p(x,y) q(y,x)) X y z (p(x) (q(y) r(z)) x y z ((p(x) q(y)) r(z)) ( x y p(x,y)) x y p(x,y) ( x y z p(x,y,z)) x y x p(x,y,z) X y p(x,y) y x p(x,y)