CMSC 27100 — Lecture 1

Welcome to CMSC 27100! Basic course information can be found on the home page of the course website.

What is this course about?

This course is about discrete mathematics, as opposed to, say, "continuous" mathematics, like calculus/analysis, or "discreet" mathematics, which you do very quietly and carefully. More specifically, discrete mathematics is the study of mathematics on discrete structures like integers, as opposed to continuous structures, like the real numbers.

Why should you take this course?

Because you have to in order to major in computer science.

I once had a department chair who argued that calculus shouldn't be a requirement for computer science majors. After confirming that he was actually quite serious about this, he explained that discrete mathematics is much more relevant to computer science and he felt that calculus was a significant deterrent to prospective computer scientists. Of course, not many of us agreed that calculus was really that bad, but it is true that computer science at its core is really a subfield of discrete mathematics. Historically speaking, we can think of computer science as an offshoot of mathematical logic that sort of spiralled out of control into what it is today.

Practially speaking, this course will give you the basic mathematical tools necessary for studying computer science. Not only will the content be useful, but the proof techniques that we study will show up in theoretical computer science courses later on.

Intellectually speaking, this course will introduce you to some ideas of mathematical proof that you may not have seen before, depending on your mathematical background. Typically, in North America, many students do not see the topics that we cover in discrete math until, well, they take a course like this.

What will we be covering in this course?

This course is a grab bag of fun discrete mathematical treats.

1. Logic and set theory. While we won't go into these topics in any real depth, they form the basis for the ideas and proof strategies that we'll use throughout the course.
2. Number theory. Number theory is the study of the properties of numbers and in particular, the prime numbers.
3. Combinatorics. Combinatorics is the study of how to count things. This sounds trivial until you have to start trying to figure out how many unique ways to there are.
4. Probability theory. Probability is the study of quantifying the likelihood that events will occur. We focus on discrete probability, where events occur with countably many possible outcomes.
5. Graph theory. Graph theory is the study of graphs. These are not graphs in the calculus or stats sense, but graphs as a set of vertices connected by edges. Graphs can represent relations among a set of objects.

Keep in mind that while this is an explicit list of content that we expect to cover, there is a lot more that we'll be covering implicitly, in the course of studying these topics. As already mentioned, a big part of this course is to develop your skills in mathematical proof.

Logic

Everybody who has worked in formal logic will confirm that it is one of the technically most refractory parts of mathematics. The reason for this is that it deals with rigid, all-or-none concepts, and has very little contact with the continuous concept of the real or of the complex number, that is, with mathematical analysis. Yet analysis is the technically most successful and best-elaborated part of mathematics. Thus formal logic is, by the nature of its approach, cut off from the best cultivated portions of mathematics, and forced onto the most difficult part of the mathematical terrain, into combinatorics.

Mathematical logic is the study of reasoning from the point of view of mathematics. On its own it's a rich and deep field of study. In the context of computer science, the development of mathematical logic in the early 20th century leads directly to the notions of computability. For the purposes of this course, the basics of mathematical logic allow us to develop a language to express mathematical ideas and a framework in which to prove their validity.

In the strictest sense, the language is really just a collection of symbols and some rules about how to arrange them. So, you're allowed to write something that looks like this, but not this and so on and so forth. The magic comes when we define meaning for these symbols.

Propositional logic

We will begin with propositional logic and expand from there later on. The basic element of propositional logic is the proposition.

Definition 1.1. A proposition is a statement that is either true or false.

We can classify propositions into two broad types.

Definition 1.2. An atomic proposition is one that cannot be broken down into smaller propositions. A compound proposition is not atomic.

In mathematical logic, we represent propositions symbolically by formulas. Formulas are made up of propositional variables, parentheses, and connectives. Propositional variables, usually lowercase roman letters like $p,q,r,\dots$, represent atomic propositions and connectives allow us to build compound propositions by joining one or more propositions together. Parentheses are used to denote the ordering that we should interpret the connectives in. We represent propositional formulas by lowercase Greek letters, $\alpha, \beta, \dots$. Hypothetically, we would be able to express every proposition that shows up in this course symbolically, but we won't go that far.

There are four basic logical connectives, called Boolean connectives, after George Boole who defined them in 1854. We will define and consider each one.

Definition 1.3. $\neg p$ is called negation and is pronounced "not $p$". $\neg p$ is true if and only if $p$ is false.

For instance, $\neg q$ is the proposition "I cannot take two weeks off". Note that negation is a unary connective, in that it only applies to one formula, while all the other connectives are binary. Observe that because of this, we tend to express atomic propositions positively.

The unary connective $\neg$ is defined for a propositional formula $\varphi$ by

Definition 1.4. $p \wedge q$ is called conjunction, and is pronounced "$p$ and $q$". $p \wedge q$ is true if and only if both $p$ and $q$ are true.

This connective expresses the idea that both $p$ and $q$ are true. For instance, $q \wedge r$ is the proposition "I can take two weeks off and I can fly to Tokyo".

$p \vee q$ is called disjunction and is pronounced "$p$ or $q$". $p \vee q$ is true if and only if $p$ is true or $q$ is true or both.

For example, $q \vee r$ is the proposition "I can take two weeks off or I can fly to Tokyo". One tricky thing to note with English is that many times we use "or" to mean "exclusive or". For instance, when you are asked whether you prefer beef or chicken, the expectation is that you may only choose one and not both. This logical connective allows for both $p$ and $q$ to be true, which corresponds to something like "and/or" in English.

The binary connectives $\wedge$ and $\vee$ are defined for propositional formulas $\varphi$ and $\psi$ by

Definition 1.5. $p \rightarrow q$ is called implication and is pronounced "if $p$, then $q$". $p \rightarrow q$ is true if and only if $q$ is true or $p$ is false.

For example, $p \rightarrow r$ would be the proposition "If flights to Tokyo are under 900 CAD, then I can fly to Tokyo". The direction in which you read this connective is very important. For instance, it may be the case that flights to Tokyo may not be under 900 CAD but I may still be able to fly. Here, $p$ is called the hypothesis and $q$ is called the conclusion.

$\rightarrow$ is defined for propositional formulas $\varphi$ and $\psi$ by

Implication is probably less familiar than conjunction or disjunction but it's particularly important since it's heavily used in expressing mathematical statements. Again, unlike conjunction and disjunction, implication is not commutative, which means that $p \rightarrow q$ and $q \rightarrow p$ are not necessarily logically equivalent.

One way to think about implications is as a claim, as we do in mathematics. Is the claim true? This depends on whether the hypothesis is true. If the hypothesis isn't true, then the claim can be considered vacuously true. This is sort of like when you begin a claim about all positive numbers that are less than 0: you can say anything about these numbers because they don't exist!

However, if the hypothesis is true, then the truth of our claim depends on whether the conclusion is also true. If it is, then all is right with the world. But if our hypothesis is true while our promised conclusion is false, then we have to conclude that we didn't know what we were talking about and that our claim was false after all.

Proof

A proof is a proof. What kind of a proof? It's a proof. A proof is a proof, and when you have a good proof, it's because it's proven.

Implication leads us naturally to the notion of proof. By constructing truth tables, we can determine the truth values for any given formula based on the connectives in that formula. The big problem with this is that truth tables can get very large: if you have $n$ different propositional variables, you're looking at a truth table of size $2^n$. However, there is another presentation of the logical rules we've defined that avoids the use truth tables. Instead, we use inference rules to allow us to deduce propositions from other propositions.

Definition 1.6. We write $\varphi_1, \dots, \varphi_k \vdash \psi$ if we can deduce $\psi$ from $\varphi_1 \wedge \cdots \wedge \varphi_k$.

Here, we overload the $\vdash$. In one sense, we may infer $\psi$ if we know $\varphi_1, \dots, \varphi_n$ because there is a proof of this fact. On the other hand, once we have proven this fact, we can consider it to be valid and use it as a rule in some other proof. Inference rules define a proof system, which formalizes our intuitive notion of proof. We begin by defining a basic set of inference rules that hopefully cover everything we need to express.

Definition 1.7. Here are some basic inference rules, grouped by the connectives they concern.

• Implication:
  • Modus ponens. Modus ponens is Latin for "mode that affirms", but was very funny to us back in the mid-2000s when people still liked to say "pwn" out loud a lot. In classical deduction, this is the only rule that is used. $$\varphi, \varphi \rightarrow \psi \vdash \psi$$
  • Deduction. This says that if by assuming $\varphi$, we can prove $\psi$, then we can deduce $\varphi \rightarrow \psi$. Using this rule in the middle of a proof requires that we break out into a subproof, kind of like when ordinary math texts decide to prove a lemma in the middle of a proof of a theorem. $$(\varphi \vdash \psi) \vdash \varphi \rightarrow \psi$$
• Disjunction:
  • Addition. \begin{align*} \varphi &\vdash \varphi \vee \psi \\ \psi &\vdash \varphi \vee \psi \end{align*}
  • Disjunctive syllogism. \begin{align*} \varphi \vee \psi, \neg \psi &\vdash \varphi \\ \varphi \vee \psi, \neg \varphi &\vdash \psi \end{align*}
  • Proof by cases. This mirrors our understanding of proof by cases in mathematics. We have one of several cases which may be true but we don't necessarily know which hold, so in order to deduce $\eta$ from $\varphi \vee \psi$, we must be able to arrive at $\eta$ from each of them. $$\varphi \vee \psi, \varphi \rightarrow \eta, \psi \rightarrow \eta \vdash \eta$$
• Conjunction:
  • Simplification. \begin{align*} \varphi \wedge \psi &\vdash \varphi \\ \varphi \wedge \psi &\vdash \psi \end{align*}
  • Conjunction. $$\varphi, \psi \vdash \varphi \wedge \psi$$
• Negation:
  • Negation. $$\varphi \rightarrow F \vdash \neg \varphi \quad \text{or} \quad (\varphi \vdash F) \vdash \neg \varphi.$$
  • Double negation. $$\neg \neg \alpha \iff \alpha$$
  • Excluded middle. As popularized by Yoda, from the blockbuster film Star Wars Episode V: The Empire Strikes Back (1980). $$\alpha \vee \neg \alpha \iff T$$
  • Contradiction. $$\alpha \wedge \neg \alpha \iff F$$
  • Contradiciton elimination. This rule says that if we arrive at false anywhere in our proof, we can deduce anything. Why can we do this? If we arrive at false, it must mean our initial premises were contradictory. And so if we start off with faulty premises, we can prove anything we want. This is similar to our discussion about what happens when the hypothesis of an implication is false; anything can happen. $$F \vdash \varphi$$

From a less mathematical point of view, these rules can be considered forms of argumentation. These rules, together with a base set of rules define a proof system for us to work with. In this sense, argumentation and proof are really the same thing. We begin with a set of premises and try to use the rules to arrive at a conclusion. If we can do this, then we've formed a valid argument or proof.

One thing to notice that the content of the argument has no bearing on whether it's valid or not. This is not unlike how many people try to argue on the internet.

Definition 1.8. Here is a list of additional useful inference rules. I've used $\varphi \iff \psi$ as shorthand for $\varphi \vdash \psi$ and $\psi \vdash \varphi$. Note that these can be derived from the basic rules we've already defined (this could be a useful exercise).

• Commutativity. Commutativity is the property of a binary operation that says that it doesn't matter which order you put the operands in. Most basic arithmetic operations are commutative. Some examples of non-commutative operations include multiplication for matrices and string concatenation. Crucially, for us, the implication connective is not commutative. \begin{align*} \alpha \wedge \beta &\iff \beta \wedge \alpha \\ \alpha \vee \beta &\iff \beta \vee \alpha \end{align*}
• Associativity. Associativity is the property that we can choose the order in which we evaluate a binary operation. \begin{align*} \alpha \wedge (\beta \wedge \gamma) &\iff (\alpha \wedge \beta) \wedge \gamma \\ \alpha \vee (\beta \vee \gamma) &\iff (\alpha \vee \beta) \vee \gamma \end{align*}
• Distributivity. Distributivity is the property that we can distribute an operation within parentheses. \begin{align*} \alpha \wedge (\beta \vee \gamma) &\iff (\alpha \wedge \beta) \vee (\alpha \wedge \gamma) \\ \alpha \vee (\beta \wedge \gamma) &\iff (\alpha \vee \beta) \wedge (\alpha \vee \gamma) \end{align*}
• Idempotence. Idempotence is the property that when an operation is applied to itself, it results in itself. \begin{align*} \alpha \vee \alpha &\iff \alpha \\ \alpha \wedge \alpha &\iff \alpha \end{align*}
• De Morgan's laws. De Morgan was an early formal logician along with George Boole back in during the 19th century. \begin{align*} \neg(\alpha \wedge \beta) &\iff (\neg \alpha) \vee (\neg \beta) \\ \neg(\alpha \vee \beta) &\iff (\neg \alpha) \wedge (\neg \beta) \end{align*}
• Absorption. \begin{align*} \alpha \wedge T &\iff \alpha \\ \alpha \vee T &\iff T \\ \alpha \wedge F &\iff F \\ \alpha \vee F &\iff \alpha \end{align*}
• Simplification. \begin{align*} \alpha \vee (\alpha \wedge \beta) &\iff \alpha \\ \alpha \wedge (\alpha \vee \beta) &\iff \alpha \end{align*}
• Implication. $$\alpha \rightarrow \beta \iff \neg \alpha \vee \beta$$
• Contrapositive. $$\alpha \rightarrow \beta \iff \neg \beta \rightarrow \neg \alpha$$

Looking at Definitions 1.7 and 1.8, it seems like a lot of different rules, so an interesting question is how many of these rules we actually need. For instance, all the rules in Definition 1.8 can be derived from the basic rules of Definition 1.7. However, we can do even better than this. It turns out, we really only need the following rules:

1. $\vdash \varphi \rightarrow (\psi \rightarrow \varphi)$
2. $\vdash (\varphi \rightarrow (\psi \rightarrow \eta)) \rightarrow ((\varphi \rightarrow \psi) \rightarrow (\varphi \rightarrow \eta))$
3. $\vdash (\neg \varphi \rightarrow \neg \psi) \rightarrow (\psi \rightarrow \varphi)$
4. $\varphi, \varphi \rightarrow \psi \vdash \psi$ (this is modus ponens)

This is pretty incredible if you think about it; we don't even need $\wedge$ and $\vee$! Of course, those other connectives and all of the other rules make our lives much easier. But reducing the number of rules we work with helps with proving things about proof systems themselves.

Example 1.9. We can show $p \wedge q \vdash q \wedge p$ (commutativity) fairly easily.

Example 1.10. We can make use of inference rules to change propositional formulas into a form that may be more enlightening. For instance, we will show $p \wedge q \rightarrow r \vdash p \rightarrow (q \rightarrow r)$.

Now, one of the big questions of mathematical logic back in the early 20th century is whether the two presentations we've seen are the same. With truth tables, we are concerned with semantics and what it means if we know something is true or false. With inference rules, we are concerned with syntax and what we may conclude, given a particular formula and how formulas are constructed.

This means that when we're considering logical statements, we can talk about truth or proof. This leads us to the following questions. If I can prove something, does that mean it is true? And if something is true, does that mean there has to be a proof for it?

Luckily for us, it turns out that the answer is yes (mostly)! This is a good thing. For propositional logic, this was shown to be true by Emil Post in 1920. Post turns out to be a fairly important logician with several important contributions to computability theory later on, along with people like Turing, Gödel, and Church.

It's not surprising then that this line of questioning turns out to lead us directly to the notion of computability. Since proof rules are really mechanical, the idea is that if we're able to express mathematical theorems formally, we should be able to build a machine that just crunches a bunch of rules to produce a proof for us. Since proof = truth, this means we can figure out whether a given theorem is true or not by sticking it in the machine.

This sounds suspiciously like a computer and we can think of logicians of this era as basically the earliest computer scientists (like modern computer scientists, they appear keen on disrupting the mathematics industry and putting mathematicians out of jobs by replacing them with machines). But the fact that we now have both extremely powerful computers in our pockets and open problems in mathematics is a sign that this original dream may have run into some complications.