Discrete Mathematics

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:

Video (requires Collab authentication)

### Notes and Questions Why is most of the math used in computer science _discrete_?

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