4.4 Laws of Logical Equivalence

Logical equivalence laws are powerful tools for manipulating and simplifying complex propositions. These rules allow us to reorder, regroup, and transform logical statements while preserving their truth values.

From commutative and associative laws to De Morgan's and absorption, these principles form the foundation for logical reasoning. They enable us to break down complex arguments, prove equivalences, and streamline logical proofs in various fields of study.

Fundamental Laws

Reordering and Grouping Propositions

• Commutative laws allow reordering of conjunctions $(p \land q \equiv q \land p)$ and disjunctions $(p \lor q \equiv q \lor p)$ without changing the truth value of the compound proposition
• Associative laws allow regrouping of conjunctions $((p \land q) \land r \equiv p \land (q \land r))$ and disjunctions $((p \lor q) \lor r \equiv p \lor (q \lor r))$ without altering the truth value
• Distributive laws allow distribution of conjunction over disjunction $(p \land (q \lor r) \equiv (p \land q) \lor (p \land r))$ and disjunction over conjunction $(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r))$

Identity and Negation Properties

• Identity laws state that a proposition conjoined with a tautology $(p \land \top \equiv p)$ or disjoined with a contradiction $(p \lor \bot \equiv p)$ is logically equivalent to the original proposition
• Negation laws describe the relationship between a proposition and its negation:
  • $p \land \lnot p \equiv \bot$ (a proposition and its negation conjoined is a contradiction)
  • $p \lor \lnot p \equiv \top$ (a proposition or its negation disjoined is a tautology)

Advanced Laws

Double Negation and Idempotence

• Double negation law states that the negation of the negation of a proposition is logically equivalent to the original proposition $(\lnot (\lnot p) \equiv p)$
  • Negating a proposition twice cancels out the negations
• Idempotent laws indicate that a proposition conjoined with itself $(p \land p \equiv p)$ or disjoined with itself $(p \lor p \equiv p)$ is logically equivalent to the original proposition
  • Repeating a proposition in a conjunction or disjunction does not change the truth value

De Morgan's Laws and Absorption

• De Morgan's laws allow the negation of a conjunction to be rewritten as a disjunction of negations $(\lnot (p \land q) \equiv \lnot p \lor \lnot q)$ and the negation of a disjunction to be rewritten as a conjunction of negations $(\lnot (p \lor q) \equiv \lnot p \land \lnot q)$
  • Negating a compound proposition involves negating each component and swapping the logical connectives
• Absorption laws state that a proposition conjoined with a disjunction containing itself $(p \land (p \lor q) \equiv p)$ or disjoined with a conjunction containing itself $(p \lor (p \land q) \equiv p)$ is logically equivalent to the original proposition
  • The truth value of the compound proposition is determined by the truth value of the repeated proposition

Exporting Implications

• Exportation law allows a conditional statement with a conjunction in the antecedent to be rewritten as a conjunction of conditional statements $(p \to (q \to r) \equiv (p \land q) \to r)$
  • The consequent of the original conditional becomes the consequent of the second conditional in the exported form