Discrete Mathematics Guide
Formula Sheet
| Use | Formula / rule | Meaning |
|---|---|---|
| Logic symbols | \(\neg p,\ p\land q,\ p\lor q,\ p\oplus q,\ p\to q,\ p\leftrightarrow q\) | not; and; inclusive or; exclusive or; if-then; iff |
| NAND / NOR | \(p\uparrow q=\neg(p\land q)\), \(p\downarrow q=\neg(p\lor q)\) | NAND means not both; NOR means neither |
| Implication | \(p\to q\equiv \neg p\lor q\) | false only when \(p\) is true and \(q\) is false |
| Contrapositive | \(p\to q\equiv \neg q\to \neg p\) | same truth value |
| De Morgan | \(\neg(p\land q)\equiv \neg p\lor\neg q\) \(\neg(p\lor q)\equiv \neg p\land\neg q\) | switch AND/OR when negating |
| Quantifiers | \(\neg\forall xP(x)\equiv\exists x\neg P(x)\) \(\neg\exists xP(x)\equiv\forall x\neg P(x)\) | flip the quantifier and negate the inside statement |
| Even / odd | \(n=2k\); \(n=2k+1\), \(k\in\mathbb Z\) | definitions |
| Rational | \(x=a/b\), \(a,b\in\mathbb Z\), \(b\ne0\) | definition |
| Divisible by \(d\) | \(d\mid n\) means \(n=dk\) for some \(k\in\mathbb Z\) | definition |
| Induction | base case; assume \(P(k)\); prove \(P(k+1)\) | prove statements for integers |
| Factorial | \(n!=n(n-1)\cdots2\cdot1\), \(0!=1\) | arrange all \(n\) objects |
| Permutation | \(P(n,r)=\dfrac{n!}{(n-r)!}\) | choose and arrange \(r\) from \(n\) |
| Combination | \(\binom nr=\dfrac{n!}{r!(n-r)!}\) | choose \(r\) from \(n\); order ignored |
| Pigeonhole | \(k(m-1)+1\) | force \(m\) objects into one of \(k\) boxes |
| Probability | \(P(E)=\dfrac{|E|}{|S|}\) | equally likely outcomes |
| Conditional probability | \(P(A\mid B)=\dfrac{P(A\cap B)}{P(B)}\) | probability of \(A\) after \(B\) is known |
| Bayes | \(P(A\mid B)=\dfrac{P(B\mid A)P(A)}{P(B)}\) | reverse a conditional probability |
| Independence | \(P(A\cap B)=P(A)P(B)\) | also \(P(A\mid B)=P(A)\), if \(P(B)>0\) |
| Expected value | \(E(X)=\sum_{s\in S}X(s)p(s)\) | weighted average of the values of \(X\) |
| Variance | \(\operatorname{Var}(X)=E(X^2)-[E(X)]^2\) | spread of a random variable |
Chapter 1 - Logic and Proofs
| Symbol | Read it as | Example |
|---|---|---|
| \(\neg p\) | not \(p\) | not raining |
| \(p\land q\) | \(p\) and \(q\) | both true |
| \(p\lor q\) | \(p\) or \(q\), or both | inclusive or |
| \(p\oplus q\) | \(p\) or \(q\), but not both | exclusive or |
| \(p\to q\) | if \(p\), then \(q\) | hypothesis \(p\), conclusion \(q\) |
| \(p\leftrightarrow q\) | \(p\) iff \(q\) | same truth value |
| \(p\uparrow q\) | not both \(p\) and \(q\) | \(\neg(p\land q)\) |
| \(p\downarrow q\) | neither \(p\) nor \(q\) | \(\neg(p\lor q)\) |
Check whether \(p\to q\) and \(\neg q\to\neg p\) are equivalent.
Answer steps
| \(p\) | \(q\) | \(p\to q\) | \(\neg q\to\neg p\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
The final columns match, so they are equivalent.
Negate \(\forall x\exists y\,(x=y^2)\) so that the negation symbol is gone.
Answer steps
What is the difference between \(\forall x\exists yP(x,y)\) and \(\exists y\forall xP(x,y)\)?
Answer steps
\(\forall x\exists yP(x,y)\): every \(x\) gets at least one \(y\). The \(y\) may change.
\(\exists y\forall xP(x,y)\): one special \(y\) works for every \(x\).
Example: if \(P(x,y)\) means "\(y\) is the parent of \(x\)," then "every person has a parent" is \(\forall x\exists yP(x,y)\). "One person is everyone's parent" is \(\exists y\forall xP(x,y)\).
Let \(F(x,y)\) mean "\(x\) can fool \(y\)." Write: there is exactly one person whom everybody can fool.
Answer steps
The first part says everybody can fool \(y\). The second part says any person with that property must be \(y\).
Prove: if \(x\) and \(y\) are even integers, then \(3x-4y\) is even.
Answer steps
An integer \(n\) is even if \(n=2k\) for some \(k\in\mathbb Z\).
Since \(x\) and \(y\) are even, let \(x=2a\) and \(y=2b\), where \(a,b\in\mathbb Z\).
\[3x-4y=3(2a)-4(2b)=6a-8b=2(3a-4b).\]Since \(3a-4b\in\mathbb Z\), the expression is even.
Disprove: the product of two irrational numbers is always irrational.
Answer steps
One counterexample is enough.
\[\sqrt2\cdot\sqrt2=2.\]Both factors are irrational, but the product is rational.
Chapter 5 - Induction, Recursion, Algorithms
- Base case: prove the first case.
- Inductive hypothesis: assume \(P(k)\) is true.
- Inductive step: use \(P(k)\) to prove \(P(k+1)\).
Let \(f(0)=0\) and \(f(n)=f(n-1)+2n-1\). Find \(f(1),f(2),f(3),f(4)\), guess a formula, and prove it.
Answer steps
The formula is \(f(n)=n^2\).
Base case: \(f(0)=0=0^2\).
Assume \(f(k)=k^2\). Then
\[f(k+1)=f(k)+2(k+1)-1=k^2+2k+1=(k+1)^2.\]Write a recursive algorithm that computes \(nx\) using only addition, where \(n\) is a nonnegative integer.
Answer steps
multiply(n, x):
if n = 0 return 0
else return x + multiply(n - 1, x)
The recursion uses \(nx=x+(n-1)x\). The base case is \(0x=0\).
Write an iterative algorithm that computes \(x^n\) using multiplication.
Answer steps
power(n, x):
answer := 1
for i := 1 to n
answer := answer * x
return answer
After one loop, \(answer=x\). After two loops, \(answer=x^2\). After \(n\) loops, \(answer=x^n\).
Trace \(f(4)\) for the algorithm \(f(n)=n^2+f(n-1)\), with \(f(0)=0\).
Answer steps
For the loop below, determine the possible final values of \(y\).
while y < 0
y := y + 1
Answer steps
If \(y\) starts negative, the loop adds 1 until \(y=0\). If \(y\) starts nonnegative, the loop does not run.
So the final value is either \(0\), or the original nonnegative value. In all cases, the final value satisfies \(y\ge0\).
Prove: \(3\mid n^3+2n\) for natural numbers \(n\).
Answer steps
Base case: \(1^3+2(1)=3\), so the statement is true for \(n=1\).
Assume \(3\mid k^3+2k\). This means \(k^3+2k=3a\) for some integer \(a\).
\[(k+1)^3+2(k+1)=k^3+3k^2+3k+1+2k+2\] \[=(k^3+2k)+3k^2+3k+3\] \[=(k^3+2k)+3(k^2+k+1).\]The first part is divisible by 3 by the hypothesis. The second part has a visible factor of 3. So the sum is divisible by 3.
Chapter 6 - Counting
| Object | Meaning | Example |
|---|---|---|
| \(n!\) | arrange all \(n\) objects | \(5!=5\cdot4\cdot3\cdot2\cdot1\) |
| \(P(n,r)\) | choose \(r\) objects and arrange them | president, VP, secretary |
| \(\binom nr\) | choose \(r\) objects; order ignored | committee of \(r\) people |
How many passwords of length 15 use digits, uppercase letters, and lowercase letters and contain at least one uppercase and at least one lowercase?
Answer steps
Total characters: \(10+26+26=62\), so total passwords are \(62^{15}\).
Subtract passwords with no uppercase: \(36^{15}\). Subtract passwords with no lowercase: \(36^{15}\).
Passwords with only digits got subtracted twice, so add them back: \(10^{15}\).
\[62^{15}-36^{15}-36^{15}+10^{15}.\]There are 10 AOCs and 20 teams. How many students guarantee at least 3 students in the same AOC and same team?
Answer steps
The boxes are AOC/team pairs:
\[10\cdot20=200.\]To avoid 3 in one box, each box can have at most 2 students:
\[200\cdot2=400.\]One more forces a box with 3 students:
\[401.\]A group has 7 men and 3 women. How many ways can they line up so that no two women are adjacent?
Answer steps
Arrange the 7 men first: \(7!\).
The men create 8 gaps:
_ M _ M _ M _ M _ M _ M _ M _
Choose 3 of those gaps for the women: \(\binom83\). Arrange the women: \(3!\).
\[7!\binom83 3!.\]Find the next three larger permutations after \(4173652\).
Answer steps
For the first next permutation, scan from the right:
\(6>5>2\), but \(3<6\). So \(3\) is the pivot.
To the right of 3, the smallest larger value is 5. Swap 3 and 5:
\[4173652\to4175632.\]Sort the suffix after 5 in increasing order:
\[4175236.\]Repeat the same rule:
\[4175236,\quad 4175263,\quad 4175326.\]How many paths go from \((0,0)\) to \((m,n)\) using only right and up moves?
Answer steps
Every path must have exactly \(m\) right moves and \(n\) up moves.
So each path is just an ordering of \(m\) R's and \(n\) U's. There are \(m+n\) total move-slots.
Choose which \(m\) of those slots are R moves. Once those slots are chosen, the other \(n\) slots must be U moves:
\[\binom{m+n}{m}.\]Choosing the U slots instead gives the same answer:
\[\binom{m+n}{m}=\binom{m+n}{n}.\]Chapter 7 - Probability
| Notation | Meaning |
|---|---|
| \(S\) | sample space: all possible outcomes |
| \(P(A)\) | probability that event \(A\) happens |
| \(P(A\mid B)\) | probability that \(A\) happens after \(B\) is known to have happened |
| \(X\) | random variable: a function that assigns a number to each outcome |
| \(E(X)\) | expected value: weighted average of the values of \(X\) |
| \(\operatorname{Var}(X)\) | variance: how spread out \(X\)'s values are |
| Use | Formula |
|---|---|
| Equally likely outcomes | \(P(E)=|E|/|S|\) |
| Conditional probability | \(P(A\mid B)=P(A\cap B)/P(B)\) |
| Bayes | \(P(A\mid B)=P(B\mid A)P(A)/P(B)\) |
| Independence | \(P(A\cap B)=P(A)P(B)\), or \(P(A\mid B)=P(A)\) |
| Expected value | \(E(X)=\sum_{s\in S}X(s)p(s)\) |
| Variance | \(E(X^2)-[E(X)]^2\) |
A fair die is rolled twice. Let \(A\) be the event that the sum is 5. Let \(B\) be the event that the first roll is even. Find \(P(A)\), \(P(A\mid B)\), and decide whether \(A\) and \(B\) are independent.
Answer steps
There are 36 total outcomes. Sum 5 happens for:
\[(1,4),(2,3),(3,2),(4,1).\] \[P(A)=4/36=1/9.\]If \(B\) has happened, the first roll is one of \(2,4,6\). That gives \(3\cdot6=18\) possible outcomes.
Among those, the sum is 5 for:
\[(2,3),(4,1).\] \[P(A\mid B)=2/18=1/9.\]Since \(P(A\mid B)=P(A)\), the events are independent.
A biased coin has heads twice as likely as tails. It is flipped three times. Find the probability of at least one tail.
Answer steps
Let \(P(T)=x\). Then \(P(H)=2x\). Since probabilities add to 1:
\[x+2x=1,\quad x=1/3.\]So \(P(T)=1/3\) and \(P(H)=2/3\).
Use the complement. "At least one tail" is the opposite of "all heads."
\[P(\text{at least one tail})=1-P(HHH)=1-\left(\frac23\right)^3=\frac{19}{27}.\]Suppose 5% of players use steroids. Users test positive 98% of the time. Non-users test positive 12% of the time. Find \(P(\text{user}\mid +)\).
Answer steps
Let \(D\) mean the player uses steroids.
The numerator is the probability of being a user and testing positive:
\[P(+\mid D)P(D)=0.98(0.05)=0.049.\]The denominator is the total probability of testing positive:
\[P(+)=P(+\mid D)P(D)+P(+\mid\neg D)P(\neg D).\] \[P(+)=0.98(0.05)+0.12(0.95)=0.049+0.114=0.163.\]Therefore:
\[P(D\mid +)=\frac{0.049}{0.163}\approx0.301.\]A fair coin is flipped three times. Let \(X\) be the number of heads. Find \(E(X)\) and \(\operatorname{Var}(X)\).
Answer steps
The sample space is:
\[S=\{HHH,HHT,HTH,THH,HTT,THT,TTH,TTT\}.\]Each outcome has probability \(1/8\). The values of \(X\) are:
\[3,2,2,2,1,1,1,0.\] \[E(X)=\frac{3+2+2+2+1+1+1+0}{8}=\frac32.\]For variance, first compute \(E(X^2)\):
\[E(X^2)=\frac{9+4+4+4+1+1+1+0}{8}=3.\] \[\operatorname{Var}(X)=E(X^2)-[E(X)]^2=3-\left(\frac32\right)^2=\frac34.\]Practice Problems
Truth table equivalence. Compare the final columns for \(p\to q\) and \(\neg p\lor q\). Are they equivalent?
Quantifier negation. Negate \(\forall x\exists y(P(x,y)\land Q(x,y))\) so that the negation is only on predicates.
Quantifier translation. Let \(F(x,y)\) mean "\(x\) can fool \(y\)." Write: everyone can be fooled by somebody.
Knights and knaves. A says, "B is a knight." B says, "A and I are different types." Determine A and B.
Even proof. State the definition of even. Then prove: if \(n\) is even, then \(7n+10\) is even.
Counterexample. Disprove: the sum of two irrational numbers is always irrational.
Contradiction proof. Prove: if \(x\) is rational and \(y\) is irrational, then \(x+y\) is irrational.
Recursive formula. Let \(f(0)=1\) and \(f(n)=f(n-1)+3\). Find \(f(1),f(2),f(3)\), guess a formula, and prove it by induction.
Recursive algorithm. Write a recursive algorithm that computes \(x^n\) using multiplication, where \(n\) is a nonnegative integer.
Recursive trace. Trace \(f(3)\) for \(f(0)=1\) and \(f(n)=n+2f(n-1)\).
Loop final values. Suppose \(y\) is an integer. What are the possible final values after this loop?
while y < 3
y := y + 1
Password counting. Passwords have length 8 and use digits and lowercase letters. How many contain at least one digit?
Pigeonhole. Students are classified by 4 graduation years and 21 majors. How many students guarantee two share both year and major?
Committee. From 8 men and 5 women, how many committees have exactly 3 men and 2 women?
Gap method. How many ways can 8 men and 5 women stand in a line if no two women stand next to each other?
Next permutation. Find the next larger permutation after \(3651742\).
Conditional probability. Two fair dice are rolled. Let \(A\) be "the sum is 7" and \(B\) be "the first roll is 3." Find \(P(A)\), \(P(A\mid B)\), and decide whether \(A\) and \(B\) are independent.
Biased coin. Heads is three times as likely as tails. The coin is flipped twice. Find the probability of at least one head.
Bayes. In a clinic, 8% of patients are infected. Infected patients test positive 98% of the time. Non-infected patients test positive 3% of the time. Find \(P(\text{infected}\mid +)\).
Expected value and variance. A box has tickets labeled \(1,2,2,3,4\). One ticket is chosen uniformly. Let \(X\) be the number on the ticket. Find \(E(X)\) and \(\operatorname{Var}(X)\).
Practice Problem Answers
Truth table equivalence
| \(p\) | \(q\) | \(p\to q\) | \(\neg p\lor q\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | T |
| F | F | T | T |
The final columns match, so the propositions are equivalent.
Quantifier negation
Flip each quantifier as the negation moves inward. Then use De Morgan's law on the AND statement.
Quantifier translation
Read it as: for every person \(y\), there is some person \(x\) who can fool \(y\).
Knights and knaves
If A were a knight, then A's statement would make B a knight. But then B's statement would say they are different types, which would be false. So A is not a knight.
Therefore A is a knave. A's statement "B is a knight" is false, so B is also a knave. B's statement that they are different types is false, as required.
Answer: A and B are both knaves.
Even proof
An integer \(n\) is even if \(n=2k\) for some integer \(k\).
Assume \(n\) is even. Then \(n=2k\) for some \(k\in\mathbb Z\).
\[7n+10=7(2k)+10=14k+10=2(7k+5).\]Since \(7k+5\) is an integer, \(7n+10\) is even.
Counterexample
Use one example where the hypothesis is true but the conclusion is false.
\[\sqrt2+(-\sqrt2)=0.\]Both \(\sqrt2\) and \(-\sqrt2\) are irrational, but their sum is rational. So the statement is false.
Contradiction proof
Assume \(x\) is rational and \(y\) is irrational. Suppose, for contradiction, that \(x+y\) is rational.
Then \(y=(x+y)-x\). A rational number minus a rational number is rational, so this would make \(y\) rational.
That contradicts the assumption that \(y\) is irrational. Therefore \(x+y\) is irrational.
Recursive formula
The pattern adds 3 each time, starting at 1, so the formula is:
\[f(n)=3n+1.\]Base case: \(f(0)=1=3(0)+1\).
Inductive step: assume \(f(k)=3k+1\). Then
\[f(k+1)=f(k)+3=(3k+1)+3=3(k+1)+1.\]So the formula holds for all nonnegative integers \(n\).
Recursive algorithm
power(n, x):
if n = 0 return 1
else return x * power(n - 1, x)
The base case is \(x^0=1\). The recursive step uses \(x^n=x\cdot x^{n-1}\).
Recursive trace
So \(f(3)=19\).
Loop final values
If \(y<3\), the loop keeps adding 1 until \(y=3\). If \(y\ge3\), the loop does not run.
So the final value is either \(3\), or the original value if it was already at least \(3\). In every case, the final value satisfies \(y\ge3\).
Password counting
There are 36 possible characters total: 10 digits and 26 lowercase letters. So total passwords:
\[36^8.\]Passwords with no digit use only lowercase letters:
\[26^8.\]Subtract the no-digit cases:
\[36^8-26^8.\]Pigeonhole
The boxes are year-major pairs:
\[4\cdot21=84.\]With 84 students, it is possible to put one in each box. One more forces a repeated box.
\[84+1=85.\]Committee
Choose the men and women separately. Order does not matter in a committee.
\[\binom83\binom52.\]Gap method
Arrange the 8 men first:
\[8!.\]They create 9 gaps around them:
_ M _ M _ M _ M _ M _ M _ M _ M _
Choose 5 of those gaps for the women, then arrange the 5 women:
\[8!\binom95 5!.\]Next permutation
Start with \(3651742\). Scan from the right. The first place where a number is smaller than the number after it is \(1<7\), so \(1\) is the pivot.
To the right of 1, the smallest number bigger than 1 is 2. Swap 1 and 2:
\[3652741.\]Then put the suffix after 2 in increasing order:
\[3652147.\]So the next permutation is \(3652147\).
Conditional probability
There are 36 total dice outcomes. The sum is 7 for 6 outcomes:
\[(1,6),(2,5),(3,4),(4,3),(5,2),(6,1).\] \[P(A)=6/36=1/6.\]Given \(B\), the first roll is already 3, so only the second die varies. To get sum 7, the second die must be 4.
\[P(A\mid B)=1/6.\]Since \(P(A\mid B)=P(A)\), the events are independent.
Biased coin
Let \(P(T)=x\). Since heads is three times as likely as tails, \(P(H)=3x\).
\[x+3x=1,\qquad x=1/4.\]So \(P(T)=1/4\) and \(P(H)=3/4\).
Use the complement: at least one head is the opposite of both flips being tails.
\[P(\text{at least one head})=1-P(TT)=1-\left(\frac14\right)^2=\frac{15}{16}.\]Bayes
Let \(D\) mean infected. The numerator is infected and positive:
\[P(+\mid D)P(D)=0.98(0.08)=0.0784.\]The denominator is total positive tests:
\[P(+)=0.98(0.08)+0.03(0.92)=0.0784+0.0276=0.106.\]Therefore:
\[P(D\mid +)=\frac{0.0784}{0.106}\approx0.740.\]Expected value and variance
The five equally likely ticket values are \(1,2,2,3,4\).
\[E(X)=\frac{1+2+2+3+4}{5}=\frac{12}{5}.\]For variance, first compute \(E(X^2)\):
\[E(X^2)=\frac{1^2+2^2+2^2+3^2+4^2}{5}=\frac{34}{5}.\] \[\operatorname{Var}(X)=E(X^2)-[E(X)]^2=\frac{34}{5}-\left(\frac{12}{5}\right)^2=\frac{26}{25}.\]