Week One Lecture Notes

Logarithm simplification

Simplify the following expression: $$ \log_2(13) \cdot \log_{13}(2048)$$

Recall the change of base formula: $\log_b x = \frac{\log_a(x)}{\log_a(b)}$. We can rewrite this as $\log_a (x) = \log_b(x) \cdot \log_a(b)$

Now apply this formula to convert the mysterious base-13 log into a base-2 log that lets us simplify the formula. That is, set $a = 2, b=13,$ and $x = 2048$. $$\log_{13}(2048) \cdot \log_2(13) = \log_2(2048) = \log_2(2^{11}) =11 $$

Mystery Logic Formula

Question: When is $a \rightarrow (b \rightarrow c)$ true/false?

Method 1: when is this expression false? Let's use the truth table for implies.

$a \rightarrow (b \rightarrow c)$ is false when a is true but $(b \rightarrow c)$ is false.
$(b \rightarrow c)$ is false when b is true and c is false.
So the whole statement is false when a and b are true and c is false.

Method 2: logical equivalences.

Useful heuristic: eliminate $\rightarrow$ using the identity $p \rightarrow q \equiv (\neg p) \vee q$.

Applying this to our mystery formula:

$a \rightarrow (b \rightarrow c) \equiv (\neg a) \vee (b \rightarrow c) \equiv (\neg a) \vee (\neg b) \vee c $

So $a \rightarrow (b \rightarrow c)$ is true exactly when a is false, or b is false, or c is true.

The "when is it true" and "when is it false" answers are related by De Morgan's Law.

Mechanical negation

"Ripped from the midterms"

State the negation of "For any cookie c, if c is not small and c is tasty, then c is not healthy."

Recall the rules for negating individual logic operations

$\neg \neg p \equiv p$
$ \neg (p \rightarrow q) \equiv p \wedge (\neg q)$
$\neg(p \wedge q) \equiv (\neg p) \vee (\neg q)$
$\neg(p \vee q) \equiv (\neg p) \wedge (\neg q)$ $\neg \forall x, P(x) \equiv \exists x, \neg P(x) $
$\neg \exists x, P(x) \equiv \forall x, \neg P(x) $

First, let's make shorthand for the individual predicates:

S(x) is "x is small"
T(x) is "x is tasty"
H(x) is "x is healthy".

And then translate the statement into shorthand:

$\forall c \in \text{cookies}, (\neg S(c) \wedge T(c)) \rightarrow \neg H(c) $

Wrap a negation around the statement:

$\neg \forall c \in \text{cookies}, (\neg S(c) \wedge T(c)) \rightarrow \neg H(c) $

The outermost operator is the $\forall$. So move the negation across it:

$\exists c \in \text{cookies}, \neg ((\neg S(c) \wedge T(c)) \rightarrow \neg H(c)) $

Now use the rule for negating an if/then statement:

$\exists c \in \text{cookies}, (\neg S(c) \wedge T(c)) \wedge H(c) $

Since we have two "and" operators (not a combination of "and" and "or), we can drop the parentheses to make this more readable.

$\exists c \in \text{cookies}, \neg S(c) \wedge T(c) \wedge H(c) $

And then translate the sentence back into words:

Negation: There is a cookie c, such that c is not small and c is tasty but c is healthy.

Contrapositive

A useful fact in logic is that an implication $p \rightarrow q$ is equivalent to its contrapositive $\neg q \rightarrow \neg p$. (E.g. build the two truth tables.) In practice, this is almost always seen with a universal quantifier: $\forall x, p(x) \rightarrow q(x) $ is equivalent to $\forall x, \neg q(x) \rightarrow \neg p(x)$.

Let's start with our cookie claim again:

For any cookie c, if c is not small and c is tasty, then c is not healthy.
$\forall c \in \text{cookies}, (\neg S(c) \wedge T(c)) \rightarrow \neg H(c) $

The contrapositive is:

$\forall c \in \text{cookies}, H(c) \rightarrow \neg (\neg S(c) \wedge T(c)) $

Simplifying this using De Morgan's Law:

$\forall c \in \text{cookies}, H(c) \rightarrow S(c) \vee \neg T(c) $

Translating back into words:

For any cookie c, if c is healthy, then c is small or c is not tasty.

Claim involving irrational numbers

Another question ripped from the midterms: is the following claim true or false?

Claim: $\forall x,y \in \mathbb{R}$, if x is irrational and y is irrational, then x+y is irrational.

The negation is

$\neg (\forall x,y \in \mathbb{R}$, if x is irrational and y is irrational, then x+y is irrational).

Moving the negation gradually into the middle of the statement, we get

$\exists x,y \in \mathbb{R}, \neg $(if x is irrational and y is irrational, then x+y is irrational).

And then, remembering that an if/then statement is false exactly when the hypothesis is true but the conclusion is false ....

$\exists x,y \in \mathbb{R}, $ x is irrational and y is irrational and x+y is rational.

So now we know what would make the claim false: a pair of irrational numbers that add up to a rational number. Suppose we set $x = \pi $ and $y = - \pi $. Then $x + y = 0$, which is rational.