Quiz 2 Greatest Hits

Logic Equivalences

The distributive laws read a\land (b\lor c)\equiv a\land b \lor a\land c and a\lor (b\land c)\equiv (a\lor b) \land (a\lor c). A bunch of other things do not obey distributive laws:
- There's no distributive law for implication. (see also below)
- You should definitely not distribute negations over \land and \lor. That's what DeMorgan's law is for.

a|b is a predicate, i.e. results in a value of true or false. Thus you cannot write things like a|b\in \mathbb N.

You need to quantify a variable which isn't either given or already quantified.
- I.e. if you're defining the predicate P(n) as P(n)\equiv \dots, then within the dots, the meaning of n is clear (it's the argument of the predicate).
- If you're stating an implication, then generally all variables need to be quantified.
- In general, if you write more than one quantifier for the same variable within one statement, what you are writing is wrong.
Each quantifier gives a meaning to the variable within its 'reach' or 'quantified area'. The variable cannot be meaningfully used outside that area. In particular:
- WRONG: 3| x \land \forall x\in \mathbb N, x \bmod 2. (x outside (in front of) quantified area)

We know exactly two rewriting rules for the implication:
- a\rightarrow b \equiv \neg b \rightarrow \neg a (contrapositive)
- a\rightarrow b \equiv \neg a\lor b
Therefore, if the contrapositive doesn't help in a given situation, you need to use the second rule. Once you have the statement in terms of only \land, \lor and \not, all the rewriting rules we learned in Section 1.3 are available, and you'll have a much easier time.

a|b means: a divides b, i.e. b is divisible by a. So in problem 3, it's always 3|\text{stuff}.

All these things say the same thing:

All these, too:

You should be comfortable moving between these different ways of stating divsibility.