Class 2: Proof Methods

# Notes and Questions **Contrapositive Inference Rule** $$ \infer{NOT(Q) \implies NOT(P)}{P \implies Q} \qquad \infer{P \implies Q}{NOT(Q) \implies NOT(P)} $$ **Theorem to Prove:** If the product of $x$ and $y$ is even, at least one of $x$ or $y$ must be even. # An integer, $z$, is **even** if there exists an integer $k$ such that $z = 2k$. Is this a _definition_, _axiom_, or _proposition_? ## An integer, $z$, is **odd** if there exists an integer $k$ such that $z = 2k + 1$. (Note that there is no connection between the variables used here, and to define even above.) To prove an implication, $P \implies Q$: 1. assume $P$. 2. Show chain of logical deductions that leads to $Q$. _Thinking implies disagreement; and disagreement implies nonconformity; and nonconformity implies heresy; and heresy implies disloyalty—so, obviously, thinking must be stopped._ Adlai Stevenson, A Call to Greatness (1954) **Odd-Even Lemma:** If an integer is not even, it is odd. Note: A _lemma_ is just a name for a theorem, typically used for proving another theorem.

How should one decide what can be accepted as an axiom, and what must be proven?

What is the purpose of a proof? (in cs2102? in software development? in algorithm design?)

Why do meaningful digital signatures require discrete mathematics?

In physics, your solution should convince a reasonable person. In math, you have to convince a person who’s trying to make trouble. Frank Wilczek