MACM 101 Lecture 11: Lecture 11 Part 1_ Theorems and Proofs II

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

Document Summary

Lecture 11 part 1: theorems and proofs ii. Direct proofs are used when we need to proof statements like. Example: if 2x 6 = 0 then x = 3. Notation: p(x) - 2x 6 = 0 , q(x) - 2x = 6 , r(x) - x = 3 . Previous knowledge: x (p(x) q(x)), x (q(x) r(x)) Reason assumption: x (p(x) q(x)), x (q(x) r(x)) premises, p(c) q(c), q(c) r(c), r(c, x (p(x) r(x)) rule of univ. specification. Premises: x (s(x) m(x)), x (m(x) f(x)), x (f(x) l(x)) Reason assumption: x (s(x) m(x)), x (m(x) f(x)), x (f(x) l(x)) premises, s(c) m(c), m(c) f(c), f(c) l(c, l(c, x (s(x) l(x)) rule of univ. spec. Definition: n is even if and only if there is k such that n = 2k, e(n). Prove that if 3n + 2 is even, then n is also even. That is x (e(3x + 2) e(x)).