Class 1: What makes it go?

### Schedule

Before **Thursday’s class**: (visit https://uvacs2102.github.io/class1 for the web version of these notes with links)

Join the cs2102 slack group and set up your profile with a pronouncable name (not your UVA email id) (setting up your profile photo is encouraged, but not required).

Read the Course Syllabus and post any questions or comments you have on it on the course slack group (#general).

Read the

*Introduction*and*Chapter 1: What is a Proof?*from the Mathematics for Computer Science Book by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer (henceforth, “MCS”). The book is freely available on-line under a Creative Commons License. Students are**strongly encrouaged**to print out the readings to read them more effectively on paper.

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 single 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).

**Video**(requires Collab authentication)

Why is most of the math you have used in school previously *continuous*?

What are the differences between how scientists, lawyers, and
mathematicians establish ``*truth*”?

A *proposition* is a statement that is either ________ or _________.

A *predicate* is a proposition whose truth may depend on the value of
variables.

### Proof

A *theorem* is a ____________ that has been proven true.

An *axiom* is a proposition that is *accepted to be true*. Axioms are
not proven; they are *assumed* to be true.

**Definition.** A *mathematical proof* of a proposition is a chain of
*logical deductions* starting from a set of accepted *axioms* that
leads to the proposition.

### Rules of Inference

The possible steps that can be used in a proof are logical deductions based on inference rules.

Inference rules are written as: $$ \infer{\textrm{\emph{conclusion}}}{\textrm{\emph{antecedents}}} $$ This means if everything on top of the rule is established to be true, then you can conclude what is on the bottom.

*Modus Ponens*: To prove *Q*, (1) prove *P* and (2) prove that *P* implies *Q*. ($P \implies Q$ is a notation for $P$ implies $Q$).

$$ \infer{Q}{P,\quad P \implies Q} $$

An inference rule is *sound* if can never lead to a **false** conclusion.

Which of these inference rules are sound?

$$ \infer{Q}{P} \qquad \infer{false}{P, P \implies Q} \qquad \infer{true}{P, NOT(P)} \qquad \infer{P \implies NOT(P)}{P, NOT(P)} \qquad \infer{NOT(Q) \implies P}{NOT(P) \implies Q} $$

##

*Through violence you may murder a liar but you can’t establish truth. Through violence you may murder a hater, but you can’t murder hate. Darkness cannot put out darkness. Only light can do that.*

Martin Luther King, Jr.,

*Where Do We Go From Here?*, address to SCLC 16 August 1967