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.