Discrete Mathematics

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

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

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

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 (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: • 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) # 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) • 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

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.