In the last video, we proved a couple logical equivalences:
\(p \rightarrow q \equiv q \vee (\neg p) \) or \(p \rightarrow q \equiv (\neg p) \vee q \)
\(\neg(p \wedge q) \equiv (\neg p) \vee (\neg q)\) (De Morgan's Law)
Let's work out a few more equivalences that are especially helpful and worth memorizing. Let's start with the obvious one:
\(\neg \neg p \equiv p\)
To keep everything simple, I'm assuming we're all comfortable with the idea that two negations cancel and both "and" and "or" are commutative. So we'll frequently make these transformations without an explicit step. In a formal logic course, we might be more careful.
There's a second De Morgan's law where we swap the roles of AND and OR, which can be proved with a truth table just like the first one.
\(\neg(p \vee q) \equiv (\neg p) \wedge (\neg q)\)
Finally we can use the above equivalences to derive another useful one.
\( \neg (p \rightarrow q) \equiv \neg (q \vee (\neg p) ) \equiv (\neg q) \wedge p \)
You can relate \( \neg (p \rightarrow q) \equiv (\neg q) \wedge p\) back to the truth table for if/then (implies). An if/then statement is false exactly when the hypothesis (p) is true and the conclusion (q) is false.
| p | q | \(p \rightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
There's three ways to figure out logical equivalences:
As we've seen, truth tables work best with only 1-3 input variables and expressions that aren't too complex. However, the number of rows is \(2^k\) where k is the number of input variables. And it's very easy to make mistakes. So truth tables don't scale well.
Applying a sequence of logical equivalences can be very slick. However, if you don't have a clear plan, it's easy to go around in circles.
Thinking deeply doesn't always work and it may only produce an informal argument that must be verified by one of the other methods. But it sometimes works extremely well.
Consider this problem:
When is \(a \rightarrow (b \rightarrow c)\) true/false?
Let's apply the "deep thought" method. When is this expression false? Well, (using the truth table for implies) it's false when a is true and \((b \rightarrow c)\) is false. When is \((b \rightarrow c)\) false? Well, when b is true and c is false. So the whole expression is false exactly when a and b are true and c is false.
Now, let's apply equivalences. A heuristic that is often useful is to eliminate all instances of \(\rightarrow\) using the identity. \(p \rightarrow q \equiv (\neg p) \vee p \). So we have
\(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 answer checks out against our deep thought answer for when the expression is false: they are related by De Morgan's law.
Now, let's do the upgrade to propositional logic. That is, we're going to add variables and "quantifiers". The two common quantifiers in mathematics are "for all" (shorthand \(\forall\)) and "there exists" (shorthand \(\exists\)).
Consider this example
For every integer x, \(x^2 \ge x\)
Variables bound by quantifiers are very similar to the "dummy" variables used in summations and integrals. They are defined only locally, just inside our quantified expression.
The replacement set is important to the meaning of quantified statements. If we change the domain to the reals, the statement above is no longer true. We can show this with a concrete counter-example: set x to be 0.5.
Scope of definitions isn't as clearly defined in mathematical writing as it is in programming languages, because math is written for a human audience. However, here's an example where we've clearly tried to use a variable after its scope has ended:
Theorem: There is an integer x, such that \(x^2 = 0\).
...
So \(3x^2 + 7 = 3\cdot 0 + 7 = 7\).
This is wrong because the statement of a theorem is usually seen as self-contained. So x is only defined while we are stating the theorem. A bit later, when the author tries to use x, it's not defined anymore. Good mathematical style requires re-introducing the variable x, e.g.
Theorem: There is an integer x, such that \( x^2 = 0\).
...
Let x be such an integer.
Then \(3x^2 + 7 = 3\cdot 0 + 7 = 7\).
Here's an example that's technically correct but bad style. Is this statement true or false?
There is an integer x such that \(x^2 = 1\) and there is an integer x such that \(x^2 = 0\).
This is, in fact, true. The scope of the first x ends before "and." We can be sure it ends there, because a (new) variable x is introduced right after "and". So the two x's are different variables. We can set the first equal to 1 and the second equal to 0, to show that the whole statement is true. This is confusing. It would have been much better style to use different names for the two variables.
Now look at this statement. It has only one quantifier, introducing a single variable x whose scope is the whole sentence. So this statement is false, because \(x^2\) can't have two unequal values.
There is an integer x such that \(x^2 = 1\) and \(x^2 = 0\).