Logical Equivalences

Logical Equivalences

In propositional logic, logical equivalences refer to relationships between two logical statements that always have the same truth value in every possible situation. In other words, two expressions are logically equivalent if, no matter what truth values are assigned to their components, the truth values of the expressions are identical.

Logical equivalences are fundamental in simplifying complex logical expressions, proving theorems, and reasoning about logical statements.

Here are some of the most important logical equivalences and their applications.

1. Double Negation Law

• Statement: $\neg (\neg p) \equiv p$
• Explanation: The negation of the negation of a proposition is logically equivalent to the original proposition. If a statement is false, negating it twice will bring it back to true.
• Example: If $p$ is "It is raining," then $\neg (\neg p)$ is "It is not true that it is not raining," which simplifies to "It is raining."

2. De Morgan's Laws

De Morgan's laws provide equivalences for negations of conjunctions and disjunctions.

First Law: $\neg (p \land q) \equiv \neg p \lor \neg q$

• Explanation: The negation of a conjunction is equivalent to the disjunction of the negations. In other words, "not (both $p$ and $q$)" is the same as saying "either not $p$, or not $q$."
• Example:
  • $p$: "It is raining."
  • $q$: "It is cold."
  • $\neg (p \land q)$: "It is not true that it is both raining and cold."
  • $\neg p \lor \neg q$: "Either it is not raining, or it is not cold."

Second Law: $\neg (p \lor q) \equiv \neg p \land \neg q$

• Explanation: The negation of a disjunction is equivalent to the conjunction of the negations. In other words, "not (either $p$ or $q$)" is the same as saying "neither $p$ nor $q$."
• Example:
  • $p$: "It is raining."
  • $q$: "It is cold."
  • $\neg (p \lor q)$: "It is not true that it is either raining or cold."
  • $\neg p \land \neg q$: "It is neither raining nor cold."

3. Commutative Laws

These laws describe how the order of the propositions in conjunctions and disjunctions does not affect the truth value.

For Conjunction: $p \land q \equiv q \land p$

• Explanation: The order in which you combine two propositions with AND does not change the result. If $p$ and $q$ are both true, so is $q \land p$.

For Disjunction: $p \lor q \equiv q \lor p$

• Explanation: Similarly, the order in which you combine two propositions with OR does not change the result. If at least one of $p$ or $q$ is true, then both $p \lor q$ and $q \lor p$ are true.

4. Associative Laws

These laws describe how the grouping of propositions in conjunctions and disjunctions does not affect the truth value.

For Conjunction: $(p \land q) \land r \equiv p \land (q \land r)$

• Explanation: The grouping of propositions in a conjunction does not matter. If all propositions are true, then the result will be true, no matter how you group them.

For Disjunction: $(p \lor q) \lor r \equiv p \lor (q \lor r)$

• Explanation: The grouping of propositions in a disjunction does not matter. If at least one of the propositions is true, the result will be true, regardless of the grouping.

5. Identity Laws

These laws show how a proposition combined with itself or with a neutral element affects the result.

For Conjunction: $p \land \text{True} \equiv p$

• Explanation: Conjunction with True leaves the original proposition unchanged. If $p$ is true, then $p \land \text{True}$ is just $p$.

For Disjunction: $p \lor \text{False} \equiv p$

• Explanation: Disjunction with False leaves the original proposition unchanged. If $p$ is true, then $p \lor \text{False}$ is just $p$.

6. Domination Laws

These laws describe how combining propositions with true or false can dominate the result.

For Conjunction: $p \land \text{False} \equiv \text{False}$

• Explanation: Conjunction with False always results in False, regardless of the truth value of $p$.

For Disjunction: $p \lor \text{True} \equiv \text{True}$

• Explanation: Disjunction with True always results in True, regardless of the truth value of $p$.

7. Idempotent Laws

These laws describe how repeating the same proposition in conjunctions or disjunctions does not change the result.

For Conjunction: $p \land p \equiv p$

• Explanation: Repeating the same proposition in a conjunction does not change its value. If $p$ is true, $p \land p$ is just $p$.

For Disjunction: $p \lor p \equiv p$

• Explanation: Repeating the same proposition in a disjunction does not change its value. If $p$ is true, $p \lor p$ is just $p$.

8. Absorption Laws

These laws describe how combining a proposition with a conjunction or disjunction involving a part of that proposition can be simplified.

For Conjunction: $p \land (p \lor q) \equiv p$

• Explanation: The conjunction of $p$ and $(p \lor q)$ simplifies to just $p$, because if $p$ is true, the whole expression is true regardless of $q$.

For Disjunction: $p \lor (p \land q) \equiv p$

• Explanation: The disjunction of $p$ and $(p \land q)$ simplifies to just $p$, because if $p$ is true, the whole expression is true regardless of $q$.

9. Contradiction and Tautology

Contradiction: $p \land \neg p \equiv \text{False}$

• Explanation: A proposition $p$ and its negation $\neg p$ cannot both be true at the same time, so their conjunction is always false.

Tautology: $p \lor \neg p \equiv \text{True}$

• Explanation: A proposition $p$ or its negation $\neg p$ must be true, so their disjunction is always true.

10. Implication and Disjunction

An implication can be rewritten as a disjunction.

Implication: $p \to q \equiv \neg p \lor q$

• Explanation: An implication $p \to q$ is logically equivalent to $\neg p \lor q$. If $p$ is false, $p \to q$ is true, which is equivalent to $\neg p \lor q$ being true.

Conclusion

Understanding logical equivalences is essential for simplifying logical expressions, solving logical puzzles, and proving logical statements. By applying these equivalences, you can transform complex logical formulas into simpler or more useful forms, making it easier to reason about their truth values and relationships.