(Some) logical equivalences
Can replace \(p\) and \(q\) with any compound proposition
| \(\lnot ( \lnot p) \equiv p\) | Double negation | |
| \(p \lor q \equiv q \lor p\) | \(p \land q \equiv q \land p\) | Commutativity Ordering of terms |
| \((p \lor q) \lor r \equiv p \lor (q \lor r)\) | \((p \land q) \land r \equiv p \land (q \land r)\) | Associativity Grouping of terms |
| \(p \land F \equiv F\) \(p \lor T \equiv T\) | \(p \land T \equiv p\) \(p \lor F \equiv p\) | Domination aka short circuit evaluation |
| \(\lnot (p \land q) \equiv \lnot p \lor \lnot q\) | \(\lnot (p \lor q) \equiv \lnot p \land\lnot q\) | DeMorgan’s Laws |
| \(p \to q \equiv \lnot p \lor q\) | ||
| \(p \to q \equiv \lnot q \to \lnot p\) | Contrapositive | |
| \(\lnot (p \to q) \equiv p\land \lnot q\) | ||
| \(\lnot( p \leftrightarrow q) \equiv p \oplus q\) | ||
| \(p \leftrightarrow q \equiv q \leftrightarrow p\) | ||
Extra examples:
\(p \leftrightarrow q\) is not logically equivalent to \(p \land q\) because
\(p \to q\) is not logically equivalent to \(q \to p\) because
| Input | Output | ||||
| \(p\) | \(q\) | \(r\) | \((p \land q) \oplus (~ ( p \oplus q) \land r~)\) | \((p \land q) \vee (~ ( p \oplus q) \land r~)\) | |
| \(T\) | \(T\) | \(T\) | |||
| \(T\) | \(T\) | \(F\) | |||
| \(T\) | \(F\) | \(T\) | |||
| \(T\) | \(F\) | \(F\) | |||
| \(F\) | \(T\) | \(T\) | |||
| \(F\) | \(T\) | \(F\) | |||
| \(F\) | \(F\) | \(T\) | |||
| \(F\) | \(F\) | \(F\) | |||
Logical equivalence : Two compound propositions are logically equivalent means that they have the same truth values for all settings of truth values to their propositional variables.
Tautology: A compound proposition that evaluates to true for all settings of truth values to its propositional variables; it is abbreviated \(T\).
Contradiction: A compound proposition that evaluates to false for all settings of truth values to its propositional variables; it is abbreviated \(F\).
Contingency: A compound proposition that is neither a tautology nor a contradiction.
Extra Example: Which of the compound propositions in the table below are logically equivalent?
| Input | Output | |||||
| \(p\) | \(q\) | \(\lnot (p \land \lnot q)\) | \(\lnot (\lnot p \lor \lnot q)\) | \((\lnot p \lor q)\) | \((\lnot q \lor \lnot p)\) | \((p \land q)\) |
| \(T\) | \(T\) | |||||
| \(T\) | \(F\) | |||||
| \(F\) | \(T\) | |||||
| \(F\) | \(F\) | |||||