cs2102: Discrete Math

Class 4: Logical Operators and Formulas (Thu, 31 Aug 2017)

### Schedule

**Problem Set 1** is due **Friday at 6:29pm**.

Next week, we will cover the rest of Chapter 3 (Satisfiability and Quantifiers).

## Links

Scott Brown, *The Life and Work of Augustus De Morgan*. Applied Probability 2006.

Ada’s Correspondence with De Morgan (Clay Mathematics Institute)

# Notes and Questions

## Well-Ordering Principle Proof

**Odd Summation.** (Problem 2.12) Prove that for all $n > 0$, the sum of the first $n$ odd numbers is $n^2$.

Class 3: Well-Ordering Principle (Tue, 29 Aug 2017)

### Schedule

This week, you should read MCS Chapter 2 and MCS Chapter 3 (at least through the end of Section 3.4).

**Problem Set 1** is due **Friday at 6:29pm**.

Office hours started Monday afternoon. See the course calendar for the full office hours schedule.

## Links

*The Well-Ordering Theorem: one of the Greatest Mathematical Controversies of All Time*, Kathryn Mann.

# Notes and Questions

What properties must a sensible ordering function have?

**Definition.** A set is *ordered* with respect to an ordering relation (e.g., $<$), if two things hold. First: every pair of inequal elements $a,b$ in $A$
either satisfy $a<b$ or $b<a$. Second $a<b$ and $b<a$ should always imply that $a<b$ (this is called the transitivity).

**Definition.** An ordered set,with respect to an ordering
relation (e.g., $<$), is *well-ordered* if all of its non-empty subsets has a minimum
element.

Which of these are well-ordered?

- The set of non-negative integers, comparator $<$.
- The set of integers, comparator $<$.
- The set of integers, comparator $|a| < |b|$.
- The set of integers, comparator if |a| = |b|: $a < b$, else: $|a| < |b|$.
- The set of national soccer teams, comparator winning games.

Prove the set of positive rationals is *not* well-ordered under $<$.

#

Provide a comparison function that can be used to well-order the positive rationals.

### Template for Well-Ordering Proofs (Section 2.2)

To prove that $P(n)$ is true for all $n \in \mathbb{N}$:

- Define the set of counterexamples, $C ::= { n \in \mathbb{N} | NOT(P(n)) }$.
- Assume for contradiction that $C$ is ______________.
- By the well-ordering principle, there must be __________________ , $m \in C$.
- Reach a contradiction (this is the creative part!). One way to reach a contradiction would be to show $P(m)$. Another way is to show there must be an element $m’ \in C$ where $m’ < m$.
- Conclude that $C$ must be empty, hence there are no counter-examples and $P(n)$ always holds.

**Example: Betable Numbers.** A number is *betable* if it can be
produced using some combination of \$2 and \$5 chips. Prove that all
integer values greater than \$3 are betable.

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.