cs2102
Discrete Mathematics

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:

Next week:

See PDF Version for Notes and Questions.


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

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)

Before Friday, 6:29pm:


Video (requires Collab authentication)

See PDF Version for Notes and Questions.

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

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.