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} $$
##
Martin Luther King, Jr., Where Do We Go From Here?, address to SCLC 16 August 1967