Class 2: Proof Methods

### Schedule

Before **Friday, 6:29pm**:

Read, print, and sign the Course Pledge. You should print the PDF version for signing, and submit a scan of your signed pledge as a PDF file using Collab.

Read Jeremy Kun’s

*Habits of Highly Mathematical People*.Submit a Course Registration Survey (which includes some questions based on Kun’s essay).

Next week:

- Before Tuesday’s class: Read MCS Chapter 2
- Before Thursday’s class: Read MCS Chapter 3
- Due Friday at 6:29pm:
**Problem Set 1**(now posted)

**Video**(requires collab authentication)

# 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