Discrete Mathematics
This is a preserved file from cs2102 Fall 2016. An updated version may exist at https://uvacs2102.github.io/

cs2102: Discrete Math (Fall 2016)

Problem Set 2 (Fri, 2 Sep 2016)

Problem Set 2 is now posted, and is due on Friday, 9 September at 6:29pm.

Class 4: Logical Formulas (Thu, 1 Sep 2016)

Schedule

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

I will not be able to hold my normal office hours on Monday.

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

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$.

# # ## Notations Mathematics and other domains often use many symbols to mean the same thing. Section 3.2 of the book gives some common notations, but there are others in common use. \begin{center} \begin{tabular}{cccc} English & Logic & C, Java, Rust & Python \\ \hline $P$ \smallcaps{implies} $Q$ & $P \implies Q$ {\em or} $P \longrightarrow Q$ & - & - \\ \smallcaps{not}$(P)$ & $\neg P$ {\em or} $\overline{P}$ & \verb+!p+ & \verb+not p+ \\ $P$ \smallcaps{and} $Q$ & $P \wedge Q$ & \verb+p && q+ & \verb+p and q+ \\ $P$ \smallcaps{or} $Q$ & $P \vee Q$ & \verb+P || Q+ & \verb+p or q+ \\ $P$ \smallcaps{xor} $Q$ & $P \oplus Q$ & \verb+p ^ q+ (bitwise) or \verb+p != q+ & \verb+p ^ q+ \\ \end{tabular} \end{center} For what values in Java or C are \verb+p ^ q+ and \verb+p != q+ both valid, but have different meanings? ## Logical Formulas \begin{center} \begin{tabular}{c|c|c} $P$ & \smallcaps{not}$(P)$ & \_\_\_\_\_\_\_\_ \\ \hline \T & \F & \\ \F & \T & \\ \end{tabular} \end{center} How many one-input Boolean operators are there? How many do we need to produce them all? # \begin{center} \begin{tabular}{cc|c|c|c|c|c} $P$ & $Q$ & $P \wedge Q$ & $P \vee Q$ & $P \implies Q$ & \_\_\_\_\_\_\_\_ & $P \oplus Q$ \\ \hline \T & \T & \T & \T & & \T & \F \\ \T & \F & & \T & & \F & \T \\ \F & \T & & \T & & \F & \T \\ \F & \F & & \F & & \T & \F \\ \end{tabular} \end{center} How many two-input Boolean operators are there? # **De Morgan's Laws:** $$\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q) \qquad \neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$$ How can these be written without the $\neg$ in front? ## Prove that it is possible to make all two-input Boolean operators using just \smallcaps{not} and any _odd_ two-input operator. (An operator is _odd_, if the number of outputs that are **True** are odd.) ## **Definition: valid.** A logical formula is _valid_ if there is no way to make it **false**. That is, no matter what truth values its variables have, it is always **true**. (Another name for this is a _tautology_.) **Definition: satisfiable.** A logical formula is _satisfiable_ if there is _some_ way to make it **true**. That is, there is at least one assignment of truth value to its variables that makes the forumla true. For each of the formulas below, determine if it is _valid_ and if it is _satisfiable_. 1. $(P \vee \neg P)$ 2. $(P \vee Q) \wedge (\neg P \vee Q)$ 3. $((P \implies Q) \wedge (Q \implies P)) \vee (P \xor Q)$

Class 3: Well-Ordering Principle (Tue, 30 Aug 2016)

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. There are upcoming office hours: today (Tuesday) 3:30-5pm and 7:30-9:30pm; Wednesday 10am-1pm, 2:30-4pm, 6:30-9:30pm (all of these are in Rice 436), and Dave has office hours Wednesday 1-2pm (in Rice 507). See the course calendar for the full office hours schedule.

Challenge Problem Opportunity. It is trivial to show that numbers in Java or C are not we-ordered, but quite challenging to show this for Python. Write a Python program that demonstrates the fact that numbers in Python are not well-ordered.

The Well-Ordering Theorem: one of the Greatest Mathematical Controversies of All Time, Kathryn Mann.
US aviation authority: Boeing 787 bug could cause ‘loss of control’ (Nigel Jones’ explanation)
Basic Integer Overflows, blexim, Phrak (Volume 0x0b, Issue 0x3c).
Never need an excuse to watch Gangnam Style.

Notes and Questions

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

What properties must a sensible ordering function have?

Trichotomy. A relation, $\prec$, satisfies the axiom of trichotomy if exactly one of these is true for all elements $a$ and $b$: $a \prec b$, $b \prec a$ or $a = b$.

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}$:

  1. Define the set of counterexamples, $C ::= { n \in \mathbb{N} | NOT(P(n)) }$.
  2. Assume for contradiction that $C$ is ______________.
  3. By the well-ordering principle, there must be __________________ , $m \in C$.
  4. 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$.
  5. 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.

# # # **Example: Division Property.** Given integer $a$ and positive integer $b$, there exist integers $q$ and $r$ such that: $a = qb + r$ and $0 \le r < b$.
# # _The whole problem with the world is that fools and fanatics are always so certain of themselves, and wiser people so full of doubts._ Bertrand Russell

Office Hours Posted (Sun, 28 Aug 2016)

The schedule here is subject to change. Please check the current Office Hours Schedule for the current schedule.

The Office Hours Schedule is now posted on the Course Calendar. Office hours start this week Monday (August 29). Except for Dave’s, all office hours are in Rice 436. Dave’s office hours are in his office, Rice 507.

Mondays
9:30-10:30am Dave (Rice 507)
10:30-2pm Yong Jae, Adam R., Brooke
4-6:30pm Adam G., Sarah

Tuesdays
noon-1:30pm Riya
3:30-5pm Luke
7:30-9:30pm Subhan

Wednesdays
10am-1pm Yong Jae, Brooke, Harrison
1-2pm Dave (Rice 507)
2:30-5pm Adam G., Gloria
6:30-9:30pm Sarah, Han Jin, Subhan

Thursdays
10am-1:30pm Harrison, Luke, Han
3:30-10pm Gloria, Riya, Adam R., Christopher, Subhan, Yaser

Fridays
9-11:30am Sarah, Yong Jae
1:30-4pm Luke, Yaser
5-6pm Hussain

Sundays
noon-3:30pm Hussain, Yong Jae
4-5:30pm Christopher

Survey Questions (Sat, 27 Aug 2016)

Here are my (in progress) responses to selected questions submitted in the registration surveys. I’ll add more responses here as I go through the rest of your questions. If you have other questions after reading this, feel free to ask them on slack (if you want it to be anonymous, send it as a direct message and I’ll answer it here).

I really hope that you (I’m assuming I’m talking to the Prof. Evans) regularly take a step back from the math we are doing and make an effort to explain how the things we are doing relate back to computing. In my opinion, this is what will really make the class interesting.
Yes, I’ll definitely try and do this as much as I can. Some of the things we cover in this class have direct and immediate relevance to computing, and I’ll aim to point out in classes. For deeper understanding of the connections, especially when they are a bit less direct as is the case for many topics, I think it is probably necessary to do longer assignments that connect the abstract math concepts to computing. I’m thinking about doing this some later in the course, but also want to keep the assignments a reasonable length.

How does the in class participation work? As in: how do you keep track of who participates?
I’m looking for “class contribution”, not just “participation”. Class contribution means you have done things to make the class better for your classmates (as well as for me!). This could be by answering or asking questions in class, as well as on slack. It could also be by bringing up interesting ideas or sharing relevant materials or news items. I’m not keeping track of “points” for whenever someone does something, and wouldn’t want people to be contributing with “getting a point” as the main motivation. You should be contributing because you want to get more out of the class yourself, and because you want to do things to make the class experience better for everyone. Even for a largish class like this, over the course of the semester it is usually clear which students have made the biggest contributions to the class, and it will impact their grades favorably. If you don’t stand out as a class contributor, it won’t count against you (the common weighting for class contribution in the final grade is 0%), but people who contribute enough to stand out will be rewarded.

Are there any good external resources/references that would aid me in this course?
Yes, there are lots of resources that could be useful.

The most useful will be the MIT OpenCourseWare sites for the “6.042: Mathematics for Computer Science” course:

You’ll find lots of examples and problems on these sites.

Another great (free) resource, but less directly matching what we do in this course, is Richard Hammack’s Book of Proof.

When AI does everything for us and there are few jobs will you become a Communist?
This is a really good question, and something I’ve occasionally talked about (see Invent the Future! from my OS class). I don’t think communism is the answer, but hope we’ll get to some kind of socialist utopia where everyone can have a high quality of life (well above just subsistance) based on the abundant value that can be created with automation, but there are opportunities for highly creative or hard-working individuals to obtain excessive wealth (and some privileges that go with this) by creating things that have great benefit to millions or billions of people.

How did you get so interested in discrete math? It seems like a difficult subject to get in to.
Most of my interest in the area stems from interest in cryptography and its applications. Cryptography is interesting and fun because its about making and breaking puzzles; its important because it enables private and secure transactions on open networks, and it changes power relationships between individuals, organizations, and governments. Nearly everything in cryptography today builds on concepts from discrete mathematics.

I’m teaching this course mostly because I like teaching foundational courses and especially courses early in the curriculum, both for a first chance to expose students to exciting new ideas and empowering students more dramatically than can be done in later courses. The other reasons I wanted to teach cs2102 are becuase I’ve already taught most of the courses in our curriculum (cs200/cs150/cs1120; cs101 (Udacity); cs2220; cs2150; cs3102; and cs4414) and like to teach new things since I learn more by doing that, and this course seemed more likely to be a good source of ideas for Cville Math Circle than the other core courses I haven’t taught yet.

Enjoyed your discussion of using “hard math problems” in todays encryption of for example the Bitcoin. Would love future discussions on the subject as it very much interests me.
Thanks! I will try, but worry sometimes students find trangressions like this confusing (or get worried about whether or not it is something they need to know for an exam (which hopefully it will be clear when it isn’t). If you’re interested in learning more about bitcoin, check out my CryptoCurrency Cabal course from last year.

As I said above, I’m very interested in cyber-security. Please do continue to frame lessons in applicable contexts. After all, I’d love to inspired toward another summer project.
I’d like to know more about data security.
Great! I will keep trying to do this, but also need to limit how much time I spend on things too far outside the main course topics. If you’re interested in the work my research group does in security and applied cryptography, see https://www.jeffersonswheel.org. I am happy to have excellent students join my research group, and anyone who does well in this class will be well-positioned for a summer position.

What inspired you to join the field of Computer Science in the first place, and how important do you feel this course is to the overall field?
I had the good fortune to encounter computers when I was in second grade. My school had a teletype machine with an acoustic coupler modem (you would dial a phone to connect to the district’s headquaters computer and stick the phon into the coupler). There was no display, but it would print out interactions line-by-line. The good news was everything was just a BASIC program. We started by playing the games, but you could type LIST and see all the source code and read it to learn how to “cheat” to win the game, and to start changing the code. The next year, the school got Apple II’s, which were fantastic machines with color graphics (that could display on a TV or monitor) and even a disk drive that you could use to store programs! It was so much fun to be able to play around with BASIC programs to draw on the screen, and eventually figure out how to handle key-presses to make games.

When I was in middle school, I sold my first program, which was a program to keep track of team information for the wrestling coach. Unfortunately, I didn’t test it with more than 10 teammates, so when he tried entering the team in it the program crashed when he got to the 11th person.

I knew programming computers was a lot of fun, but didn’t know anything about computer science (or that I wanted to do it for a career), until taking Gerry Sussman’s 6.001 Structure and Interpretation of Computer Programs course (at MIT in 1989). That opened me to the power and beauty of computer science, beyond just writing programs, and I’ve only had a few digressions since.

As to why cs2102 (and the other theoretical and foundational courses you take) is important, courses like these are the ones that should empower you to envision and execute creative computing beyond standard practice. There are tons of 3-month boot camps that can train most smart people to become adequate web and mobile developers or data scientist programmers, and people who complete these programs are able to find good six-figure jobs. The best of them will stay active in learning new APIs and tools, and develop the experience needed to build increasingly complex projects. If you want to do that you don’t need to do a four-year degree at an expensive University like UVa — there are much easier, faster, and cheaper career paths to being a professional programmer.

On the other hand, people without fundamental understanding of the underlying mathematics and theory of computing (which you should get from cs2102, cs3102, and cs4102), and deep understanding of how computing systems work (which you should get from cs2150, cs3330, and cs4414), are unlikely to do things that really advance the state of computing. Most programmers do things that are unsurprising and mundane; you should aspire to do things that are surprising and indistinguishable from magic.

Although I hope cs2102 will be valuable and exciting on its own, its real importance in the curriculum and your overall computing development, is to prepare you well for cs3102 and cs4102. As a whole, though, the foundational understanding you should get from those courses should enable you to design, build, and analyze computing systems that do things people previously thought were not possible (or didn’t even think about at all!)

Problem Set 1 (Fri, 26 Aug 2016)

Problem Set 1 is now posted, and is due on Friday, 2 September at 6:29pm.

Class 2: Proof Methods (Thu, 25 Aug 2016)

Schedule

Before Friday (tomorrow), 6:29pm:

Next week:

Sorry the proof in class got so messed up! Although part of my goal for class today was to illustrated the subjectiveness of human-written and read proofs, I apologize for making things so confusing and broken. I’d updated the notes to include the full proof (hopefully correct now!) at the level of detail intended in class. Its good to see students are being skeptical proof-readers and noticing mistakes like this.

We didn’t get to the “if and only if” proof in the notes in class today, but you are encouraged to try this on your own. We’ll look at this the Well Ordering Principle (Chapter 2) in Tuesday’s class.

Challenge Problem Opportunity. I wasn’t very satisfied with my proof of the “Odd-Even Lemma” in class. I hope a student will come up with a better proof. Come up with a proof that passes the “skeptical reader” test and would convince someone with no prior knowledge of odd and even numbers.

Dan Ariely, Honor Codes

The Coq Proof Assistant tool I mentioned in class today is available from https://coq.inria.fr/. (You are not expected to use this for cs2102, or generate proofs at this level of rigor or details, but are certainly welcome to if you want!)

Anatomy of a Miracle, Vanity Fair, June 2009.

Intel’s FDIV bug (there’s even a web page for jokes about Intel’s FDIV bug).

# Notes and Questions 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$. **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?)

Proof from Class

Proposition: If the product of $x$ and $y$ is even, at least one of $x$ or $y$ must be even.

Our goal is to prove the implication, $P \implies Q$, where:

  • $P$ is “the product of $x$ and $y$ is even”
  • $Q$ is “at least one of $x$ and $y$ must be even”

We will prove the contrapositive. The inference rule,

$$ \infer{P \implies Q}{NOT(Q) \implies NOT(P)} $$ will be the last step in our proof. To be able to use this rule, we need to make the antecedent true. So, our goal is to prove $NOT(Q) \implies NOT(P)$.

To prove an implication, we assume the left side and short the right side. So, our proof begins:

  1. We prove the contrapositive.
  2. Assume NOT(at least one of $x$ and $y$ must be even).
  3. By the meaning of negation, this means both $x$ and $y$ are not even.
  4. By the “Odd-Even Lemma”, both $x$ and $y$ are odd.
  5. By the definition of odd, there exist integers $k$ and $m$ such that $x = 2k + 1$ and $y = 2m + 1$.
  6. Substituting, $xy = (2k + 1)(2m + 1) = 4mk + 2m + 2k + 1 = 2(2mk + m + k) + 1$.
  7. By the closure of addition and multiplication over the integers, there is some integer $r = 2mk + m + k$, so $xy = 2r + 1$.
  8. By the definition of odd, $xy$ is odd.
  9. By the (not proven) “Even-Odd Lemma”, this means $xy$ is not even.
  10. So, we have shown NOT(the product of $x$ and $y$ is even).
  11. Since we concluded this starting from the assumption (step 2), this proves the implication: NOT(at least one of $x$ and $y$ must be even) $\implies$ NOT(the product of $x$ and $y$ is even).
  12. Using the contrapositive inference rule, we can conclude: the product of $x$ and $y$ is even $\implies$ at least one of $x$ and $y$ must be even. \QEDA

\dbox{ {\bf Challenge Problem Opportunity.} I wasn’t very satisfied with my proof of the “Odd-Even Lemma” in class. I hope a student will come up with a better proof. A proof that passes the “skeptical reader” test and would convince someone with no prior knowledge of odd and even numbers is worth up to 10 bonus points. }

Proving “If and Only If”

Strategy: To prove $P$ if and only if $Q$:

  1. Prove $P \implies Q$.
  2. Prove $Q \implies P$.

Definition. The standard deviation of a sequence of values $x_1, x_2, \ldots, x_n$ is $$ \sqrt{\frac{(x_1 - \mu)^2 + (x_2 - \mu)^2 + \ldots + (x_n - \mu)^2}{n}} $$ where $\mu$ is the mean of the values: $$ \mu ::= \frac{x_1 + x_2 + \ldots + x_n}{n} $$.

Theorem 1.6.1. The standard deviation of a sequence of values, $x_1, x_2, \ldots, x_n$ is $0$ if and only if all of the $x_i$ values are equal to the mean of $x_1, x_2, \ldots, x_n$.

The book proves this using a chain of iff implications; prove it using the two-implications strategy.

#

#

#

#

#

#

#

#

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, 23 Aug 2016)

Schedule

Before Thursday’s class: (visit https://uvacs2102.github.io for the web version of these notes with links)

Before Friday, 6:29pm:

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

##

Contrapositive:

$$ \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.