cs2102: Discrete Math

Office Hours Posted (Sat, 26 Aug 2017)

The office hours schedule is now posted on the course site (Office Hours) and Calendar. The schedule will likely be adjusted as the semester progresses. Office hours start on Monday (3pm), and will follow the schedule here after that.

Class 2: Proof Methods (Thu, 24 Aug 2017)

### 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)

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

Class 1: What makes it go? (Tue, 22 Aug 2017)

### 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

Scanning Advice (Tue, 22 Aug 2017)

For many of the assignments in this class, you will need to submit your assignment as a PDF file. For the Course Pledge, you need to print out a page, sign it, and submit a scan of the page. For the Problem Sets, you will need to submit your responses as a single PDF file (this could be generated using a typesetting tool, but it is also find to handwrite your solutions, and produce a scan to submit).

If you have access to a scanner and can use that to generate a PDF, that should produce good results. There are public scanners to use in some of the UVA libraries including in Clemons Library.

If you are careful though, it is also possible to generate a readable
PDF using a mobile phone camera. One tool that works for this is
CamScanner (available as a
free app for limited use, for Android, iPhone, and Windows Phone).
There are lots of other scanning apps that should work - see *The
best scanning apps for Android and
iPhone*.

Please look at the file you have generated before submitting it. If it does not look readable to you, please do not submit it, but figure out how to generate a more readable PDF. Submitting the Course Pledge is a good opportunity to make sure you have figured out a way to generate readable PDFs, since you will need to do this for the problem sets also.

Fall 2017 Course (Fri, 17 Mar 2017)

cs2102 will be offered in Fall 2017, co-taught by Mohammad Mahmoody and David Evans.

For an idea what the course will be like, see last year’s course site. Some things will change, though. Course materials for Fall 2017 will appear hear when they are available.