# 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.

## What is a predicate? What isn't?

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.

## Which variable needs to be quantified? Which one doesn't?

- 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)

## Rewriting Rules for Implication

- 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.

## Notation Confusion

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

## Different ways of denoting divisibility

All these things say the same thing:

3 divides a

- a is divisible by 3
3|a

\exists k \in \mathbb Z, a=3k

a\bmod 3=0

All these, too:

\exists q\in \mathbb Z,a/3 = q R 1

\exists k \in \mathbb Z, a=3k+1

a\bmod 3=1

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