笔记

CS70

Takeaways of a Discrete Mathematics and Probability Theory class

Takeaways of CS70

Note 1

1. Propositional Logic

  1. Conjunction: $P \wedge Q$ (“P and Q”). True only when both P and Q are true.
  2. Disjunction: $P \vee Q$ (“P or Q”). True when at least one of P and Q is true.
  3. Negation: $\neg P$ (“not P”). True when P is false.
$P$ $Q$ $P \wedge Q$
$T$ $T$ $T$
$T$ $F$ $F$
$F$ $T$ $F$
$F$ $F$ $F$
  1. Implication: $P \Rightarrow Q$ (“P implies Q”). This is the same as “If P, then Q.”
P Q $P \Rightarrow Q$ $\neg P \lor Q$
$T$ $T$ $T$ $T$
$T$ $F$ $F$ $F$
$F$ $T$ $T$ $T$
$F$ $F$ $T$ $T$
$$ P\Rightarrow Q \equiv \neg P\vee Q $$

$P \Rightarrow Q$ is the most common form mathematical theorems take. Here are some of the different ways of saying it:

  1. P, then Q;
  2. Q if P;
  3. P only if Q;
  4. P is sufficient for Q;
  5. Q is necessary for P;
  6. Q unless not P.

If both $P \Rightarrow Q$ and $Q \Rightarrow P$ are true, then we say “P if and only if Q” (abbreviated “P iff Q”) or $P \Leftrightarrow Q$

Given an implication $P \Rightarrow Q$, we can also define its

  • Contrapositive: $¬Q \Rightarrow ¬P $
  • Converse: $Q \Rightarrow P$
$P$ $Q$ $\neg P$ $\neg Q$ $P \Rightarrow Q$ $Q \Rightarrow P$ $\neg Q \Rightarrow \neg P$ $P \Leftrightarrow Q$
$T$ $T$ $F$ $F$ $T$ $T$ $T$ $T$
$T$ $F$ $F$ $T$ $F$ $T$ $F$ $F$
$F$ $T$ $T$ $F$ $T$ $F$ $T$ $F$
$F$ $F$ $T$ $T$ $T$ $T$ $T$ $T$
$$ (P \Rightarrow Q) \equiv (¬Q \Rightarrow ¬P) $$

2. Quantifiers and Negation

Quantifier:

  1. $(∀x ∈ Z)(∃y ∈ Z)(x < y)$
  2. $(∃y ∈ Z)(∀x ∈ Z)(x < y)$

Negation:

  1. $¬(P∧Q) ≡ (¬P∨ ¬Q)$
  2. $¬(P∨Q) ≡ (¬P∧ ¬Q)$
  3. $¬(∃xP(x)) ≡ ∀x¬P(x)$
  4. $¬(∀xP(x)) ≡ ∃x¬P(x)$
  5. $¬(∀x∃yP(x, y)) ≡ ∃x¬(∃yP(x, y)) ≡ ∃x∀y¬P(x, y).$

Note 2

1. Direct Proof

$$ \begin{array}{|l|} \hline \textbf{Direct Proof} \\ \quad \textit{Goal}: \text{ To prove } P \Rightarrow Q. \\ \quad\textit{Approach}: \text{ Assume } P \\ \hspace{4cm}\vdots \\ \hspace{3cm}\text{Therefore } Q \\ \hline \end{array} $$

2. Proof by Contraposition

$$ \begin{array}{|l|} \hline \textbf{Proof by Contraposition} \\ \quad\textit{Goal}: \text{ To prove } P \Rightarrow Q. \\ \quad\textit{Approach}: \text{ Assume } \neg Q \\ \hspace{4cm}\vdots \\ \hspace{3cm}\text{Therefore } \neg P \\ \quad\textit{Conclusion}: \neg Q \Rightarrow \neg P, \text{ which is equivalent to } P \Rightarrow Q. \\ \hline \end{array} $$

Recall from our discussion on propositional logic that any implication $P \Rightarrow Q$ is equivalent to its contrapositive $¬Q \Rightarrow ¬P$. Yet, sometimes $¬Q \Rightarrow ¬P$ can be much simpler to prove than $P \Rightarrow Q$. Thus, a proof by contraposition proceeds by proving $¬Q \Rightarrow ¬P$ instead of $P \Rightarrow Q$.

3. Proof by Contradiction

$$ \begin{array}{|l|} \hline \textbf{Proof by Contradiction} \\ \quad\textit{Goal}: \text{ To prove } P. \\ \quad\textit{Approach}: \text{ Assume } \neg P \\ \hspace{4cm}\vdots \\ \hspace{3.85cm}R \\ \hspace{4cm}\vdots \\ \hspace{3.7cm}\neg R \\ \quad\textit{Conclusion}: \neg P \Rightarrow (\neg R \land R), \text{ which is a contradiction. Thus, } P. \\ \hline \end{array} $$

4. Proof by Cases

$\textit{Skip}$

Note 3

1. Mathematical Induction

  1. Base Case: Prove that P(0) is true.
  2. Induction Hypothesis: For arbitrary k ≥ 0, assume that P(k) is true.
  3. Inductive Step: With the assumption of the Induction Hypothesis in hand, show that P(k+1) is true

2. Simple Induction vs. Strong Induction

There is another notion of induction, which we now discuss, called strong induction.

The latter is similar to simple induction, except we have a slightly different induction hypothesis: Instead of just assuming $P(k)$ is true (as was the case with simple induction), we assume the stronger statement that $P(0), P(1), . . . , \text{and} P(k)$ are all true (i.e., that $\wedge^k_{i=0} P(i)$ is true).

strong induction does have an appealing advantage — it can make proofs easier, since we get to assume a stronger hypothesis