A proof lets us demonstrate the reasoning between two statements in a rigorous manner.
The \(\equiv\) symbol means that two statements are equivalent. This is the same as saying that they are both true, or both false.
Let’s prove that \((P \lor Q) \lor (R \lor Q) \equiv (P \lor Q) \lor R\) .
| Statement | Reason |
|---|---|
| \((P \lor Q) \lor (R \lor Q)\) | Given |
| \((P \lor Q) \lor (Q \lor R)\) | Commutativity |
| \(((P \lor Q) \lor Q) \lor R\) | Associativity |
| \((P \lor (Q \lor Q)) \lor R\) | Associativity |
| \((P \lor Q) \lor R\) | Simplification |
Some basic rules:
- \(\lnot\lnot P \equiv P\) (double negation)
- \(\lnot \top \equiv \bot\)
- \(P \land \bot \equiv \bot\)
- \(P \land \top \equiv P\)
- \(P \lor \bot \equiv P\)
- \(P \lor \top \equiv \top\)
Some more helpful equivalences:
- Definition of implication: \(P \rightarrow Q \equiv \lnot P \lor Q\)
- Associative property
- With \(\lor\) : \((A \lor B) \lor C \equiv A \lor (B \lor C)\)
- With \(\land\) : \((A \land B) \land C \equiv A \land (B \land C)\)
- With \(\oplus\) : \((A \oplus B) \oplus C \equiv A \oplus (B \oplus C)\)
- With \(\leftrightarrow\) : \((A \leftrightarrow B) \leftrightarrow C \equiv A \leftrightarrow (B \leftrightarrow C)\)
- Commutative property
- With \(\lor\) : \(A \lor B \equiv B \lor A\)
- With \(\land\) : \(A \land B \equiv B \land A\)
- With \(\oplus\) : \(A \oplus B \equiv B \oplus A\)
- With \(\leftrightarrow\) : \(A \leftrightarrow B \equiv B \leftrightarrow A\)
- Distributive property
- With \(\lor\) : \(A \lor (B \lor C) \equiv A\)