Samuel Yang
on June 15, 2018 at 09:54 amDefinition 1 A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called tautology. A compound proposition that is always false is called a contradiction. A compound proposition that is neither a tautology nor a contradiction is called a contingency.
Examples of a tautology and a contradiction
| \(p\) | \(\neg p\) | \(p \lor \neg p\) | \(p \land \neg p\) |
|---|---|---|---|
| T | F | T | F |
| F | T | T | F |
Definition 2 The compound propositions \(p\) and \(q\) are called logically equivalent if \(p \implies q\) is a tautology. The notation \(p \equiv q\) denotes that \(p\) and \(q\) are logically equivalent.
Example 1
Show that \(\neg (p \lor q)\) and \(\neg p \land \neg q\) are logically equivalent.
Solution
As you can see the truth table for these compound propositions displayed below, it follows that \(\neg (p \lor q) \implies (\neg p \land \neg q)\) is a tautology and these compound propositions are logically equivalent.
Truth table for \(\neg (p \lor q)\) and \(\neg p \land \neg q\)
| \(p\) | \(q\) | \(p \lor q\) | \(\neg (p \lor q)\) | \(\neg p\) | \(\neg q\) | \(\neg p \land \neg q\) |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
Example 2
Show that \(p \implies q\) and \(\neg p \lor q\) are logically equivalent.
Solution
As shown below, the truth values of \(p \implies q\) and \(\neg p \lor q\) agree, these compound propositions are logically equivalent.
The truth table for \(p \implies q\) and \(\neg p \lor q\)
| \(p\) | \(q\) | \(p \lor q\) | \(\neg (p \lor q)\) | \(\neg p\) | \(\neg q\) | \(\neg p \land \neg q\) |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
Example 3
Show that \(p \lor (q \land r)\) and \((p \lor q) \land (p \lor q)\) are logically equivalent. This is the distributive law of disjunction over conjunction.
Solution
As shown below, the truth values of \(p \implies q\) and \(\neg p \lor q\) agree, so these compound propositions are logically equivalent.
The truth table for \(p \lor (q \land r)\) and \((p \lor q) \land (p \lor q)\)
| \(p\) | \(q\) | \(r\) | \(q \land r\) | \(p \lor (q \land r)\) | \(p \lor q\) | \(p \lor r\) | \((p \lor q) \land (p \lor r)\) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | F | T | T | T | T |
| T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | T | T | T | T | T |
| F | T | F | F | F | T | F | F |
| F | F | T | F | F | F | T | F |
| F | F | F | F | F | F | F | F |
Table of Important Logical Equivalences
| Equivalence | Name |
|---|---|
|
\(p \land \mathbf T \equiv p\) \(p \lor \mathbf F \equiv p\) |
Identity Laws |
|
\(p \lor \mathbf T \equiv \mathbf T\) \(p \land \mathbf F \equiv \mathbf F\) |
Domination Laws |
|
\(p \lor p \equiv p\) \(p \land p \equiv p\) |
Idempotent Laws |
| \(\neg (\neg p) \equiv p\) | Double Negation Law |
|
\(p \lor q \equiv q \lor p\) \(p \land q \equiv q \land p\) |
Commutative Laws |
|
\((p \lor q) \lor r \equiv p \lor (q \lor r)\) \((p \land q) \land r \equiv p \land (q \land r)\) |
Associative Laws |
|
\(p \lor (q \land r) \equiv (p \lor q) \land (p \land r)\) \(p \land (q \lor r) \equiv (p \land q) \lor ([ \land r)\) |
Distributive Laws |
|
\(\neg (p \land q) \equiv \neg p \lor \neg q\) \(\neg (p \lor q) \equiv \neg p \land \neg q\) |
De Morgan's Laws |
|
\(p \lor (p \land q) \equiv p\) \(p \land (p \lor q) \equiv p\) |
Absorption Laws |
|
\(p \lor \neg p \equiv \mathbf T\) \(p \land \neg p \equiv \mathbf F\) |
Negation Laws |
|
\(p \implies q \equiv \neg p \lor q\) \(p \implies q \equiv \neg q \implies \neg p\) \(p \lor q \equiv \neg p \implies q\) \(p \land q \equiv \neg (p \implies \neg q)\) \(\neg (p \implies q) \equiv p \land \neg q\) \((p \implies q) \land (p \implies r) \equiv p \implies (q \land r)\) \((p \implies r) \land (q \implies r) \equiv (p \lor q) \implies r\) \((p \implies q) \lor (p \implies r) \equiv p \implies (q \lor r)\) \((p \implies r) \lor (q \implies r) \equiv (p \land q) \implies r\) |
|
|
\(p \iff q \equiv (p \implies q) \land (q \implies p)\) \(p \iff q \equiv \neg p \iff \neg q\) \(p \iff q \equiv (p \land q) \lor (\neg p \land \neg q)\) \(\neg (p \iff q) \equiv p \iff \neg q\) |
Example 4
Show that \(\neg (p \implies q)\) and \(p \land \neg q\) are logically equivalent.
Solution
It's a lot easier if we use logical identities as shown in the table above to show that these compound propositions are logically equivalent.
\begin{align} \neg (p \implies q) & \equiv \neg (\neg p \lor q)\\ & \equiv \neg (\neg p) \land \neg q && \text{by the second De Morgan law}\\ & \equiv p \land \neg q && \text{by the double negation law} \end{align}
Example 5
Show that \(\neg (p \lor (\neg p \land q))\) and \(\neg p \land \neg q\) are logically equivalent.
Solution
\begin{align} \neg (p \lor (\neg p \land q)) & \equiv \neg p \land \neg (\neg p \land q) && \text{by the second De Morgan law}\\ & \equiv \neg p \land [\neg (\neg p) \lor \neg q] && \text{be the first De Morgan law}\\ & \equiv \neg p \land (p \lor \neg q) && \text{by the double negation law}\\ & \equiv (\neg p \land p) \lor (\neg p \land \neg q) && \text{by the second distributive law}\\ & \equiv \mathbf F \lor (\neg p \land \neg q) && \text{because \(\neg p \land p \equiv \mathbf F\)}\\ & \equiv (\neg p \land \neg q) \lor \mathbf F && \text{by the communitative law for disjunction}\\ & \equiv (\neg p \land \neg q) && \text{by the identity law for \(\mathbf F\)} \end{align}
Example 6
Show that \((p \land q) \implies (p \lor q)\) is a tautology.
Solution
we will use logical equivalences to show that it is logically equivalent to \(\mathbf T\).
\begin{align} (p \land q) \implies (p \lor q) & \equiv \neg (p \land q) \lor (p \lor q) && \text{because \(p \implies q \equiv \neg p \lor q\)}\\ & \equiv (\neg p \lor \neg q) \lor (p \lor q) && \text{by the first De Morgan law}\\ & \equiv (\neg p \lor p) \lor (\neg q \lor q) && \text{by the associative and communitative laws for disjunction}\\ & \equiv \mathbf T \lor \mathbf T\\ & \equiv \mathbf T \end{align}
Definition 3 A compound is satisfiable if there is an assignment of truth values to its variables that makes it true. When the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable
Example 7
Determine whether the compound proposition \((p \lor \neg q) \land (q \lor \neg r) \land (r \lor \neg p)\) is satisfiable.
Solution
Instead of using truth table to solve this problem, we will reason about truth values. Note that \((p \lor \neg q) \land (q \lor \neg r) \land (r \lor \neg p)\) is true when the three variables \(p\), \(q\), and \(r\) have the same truth value. Hence, it is satisfiable.
-
Article Tags:
- Mathematical Logic