Laws of Logic
1). DeMorgan's law:
\(\neg (P \land Q) = \neg P \lor \neg Q\)
\(\neg (P \lor Q) = \neg P \land \neg Q\\\)
2). Commutative law:
\(P \land Q = Q \land P\)
\(P \lor Q = Q \lor P\\\)
3). Associative law:
\(P \land (Q \land R) = (P \land Q) \land R\)
\(P \lor (Q \lor R) = (P \lor Q) \lor R\\\)
4). Idempotent law:
\(P \land P = P\)
$ P ∨ P = P\\$
5). Distributive law:
\(P \land (Q \lor R) = (P \land Q) \lor (P \land R)\)
\(P \lor (Q \land R) = (P \lor Q) \land (P \lor R)\\\)
6). Absorption law:
\(P \land (Q \lor R) = P\)
\(P \lor (Q \land R) = P\\\)
7). Double negation:
\(\neg \neg P = P\\\)
8). Modus Ponens: \(\\\)
if \(P \to Q\):
If you know tha both \(P\) and the implication \(P \to Q\) are true, you can conclude tha \(Q\) must also be true.
9). Modus Tollens: \(\\\)
if \(P \to Q\):
if you know that the implication \(P \to Q\) is true, and \(Q\) is false, you can conclude that \(P\) must must also be false.
The validity of both arguments can be checked with truth tables.
Truth table
| \(P\) | \(Q\) | \(P \lor (Q \lor \neg P)\) | \(P \land (Q \lor \neg Q)\) | \(P \lor \neg (Q \lor \neg Q)\) | ||||
|---|---|---|---|---|---|---|---|---|
| F | F | T | F | F | ||||
| F | T | T | F | F | ||||
| T | F | T | F | T | ||||
| T | T | T | F | T | ||||
| Tautology | Contradiction | Neither |
Tautology laws:
\(P \land (\text{a tautology}) = P\)
\(P \lor (\text{a tautology}) = \text{a tautology}\)
\(\neg (\text{a tautology}) = \text{a contradiction}\)
Contradiction laws:
\(P \land (\text{a contradiction}) = \text{a contradiction}\)
\(P \lor (\text{a contradiction}) = P\)
\(\neg (\text{a contradiction}) = \text{a tautology}\)
Proof solving strategies the big picture
1). Writing a proof drawing inference from hypothesis
- To prove a goal of the form \(P \to Q\)
- Assume Q is false then prove \(P\) is false \(\}\) contrapositive of the goal
2). Writing a proof drawing inference from conclusion
- To prove a conclusion of the form \(P \to Q\)
- Assume \(P\) is true then prove \(Q\)
3). Writing a proof drawing inference from contradiction
To prove a goal of the form \(\neg P\):
a). Reexpress teh goal in some other form and then use one of the proof strategies above
b). Assume \(P\) is true and try to reach a contradiction. Once you've reached it you can conclude that \(P\) must be false