Understanding Logical Equivalence in Propositional Logic

Logical equivalence is a fundamental concept in propositional logic. Two propositional formulas are said to be logically equivalent if they have the same truth value under all possible assignments of truth values to their propositional variables. This means they represent the same logical meaning. We can check for logical equivalence using truth tables or by applying a sequence of known logical equivalences.

Let's examine each pair of expressions given in the question to determine if they are logically equivalent.

Analyzing Pair A: $\neg p \rightarrow (q \rightarrow r)$ and $q \rightarrow (p \lor r)$

We can analyze this pair by converting the implications into disjunctions using the equivalence $A \rightarrow B \equiv \neg A \lor B$.

• First expression: $\neg p \rightarrow (q \rightarrow r)$
  • Apply $A \rightarrow B \equiv \neg A \lor B$ to the outer implication: $\neg(\neg p) \lor (q \rightarrow r)$
  • Apply double negation $\neg(\neg p) \equiv p$: $p \lor (q \rightarrow r)$
  • Apply $A \rightarrow B \equiv \neg A \lor B$ to the inner implication: $p \lor (\neg q \lor r)$
  • Using associative property of disjunction: $p \lor \neg q \lor r$
• Second expression: $q \rightarrow (p \lor r)$
  • Apply $A \rightarrow B \equiv \neg A \lor B$: $\neg q \lor (p \lor r)$
  • Using associative property of disjunction: $\neg q \lor p \lor r$
  • Using commutative property of disjunction: $p \lor \neg q \lor r$

Comparing the simplified forms, $p \lor \neg q \lor r$ is the same as $p \lor \neg q \lor r$. Therefore, the two expressions in Pair A are logically equivalent.

Analyzing Pair B: $(p \rightarrow q) \rightarrow r$ and $p \rightarrow (q \rightarrow r)$

Let's simplify these expressions using the equivalence $A \rightarrow B \equiv \neg A \lor B$.

• First expression: $(p \rightarrow q) \rightarrow r$
  • Apply $A \rightarrow B \equiv \neg A \lor B$ to the outer implication: $\neg(p \rightarrow q) \lor r$
  • Apply $p \rightarrow q \equiv \neg p \lor q$: $\neg(\neg p \lor q) \lor r$
  • Apply De Morgan's Law $\neg(A \lor B) \equiv \neg A \land \neg B$: $(\neg(\neg p) \land \neg q) \lor r$
  • Apply double negation $\neg(\neg p) \equiv p$: $(p \land \neg q) \lor r$
• Second expression: $p \rightarrow (q \rightarrow r)$
  • Apply $A \rightarrow B \equiv \neg A \lor B$ to the inner implication: $p \rightarrow (\neg q \lor r)$
  • Apply $A \rightarrow B \equiv \neg A \lor B$ to the outer implication: $\neg p \lor (\neg q \lor r)$
  • Using associative property of disjunction: $\neg p \lor \neg q \lor r$

Comparing the simplified forms, $(p \land \neg q) \lor r$ is not the same as $\neg p \lor \neg q \lor r$. Implication is not associative. For example, consider the case where $p$ is False, $q$ is False, and $r$ is False:

• $(p \rightarrow q) \rightarrow r \equiv (F \rightarrow F) \rightarrow F \equiv T \rightarrow F \equiv F$
• $p \rightarrow (q \rightarrow r) \equiv F \rightarrow (F \rightarrow F) \equiv F \rightarrow T \equiv T$

Since the truth values differ for this assignment (F vs T), the two expressions in Pair B are not logically equivalent.

Analyzing Pair C: $(p \rightarrow q) \rightarrow (r \rightarrow s)$ and $(p \rightarrow r) \rightarrow (q \rightarrow s)$

Let's simplify these expressions using the equivalence $A \rightarrow B \equiv \neg A \lor B$.

• First expression: $(p \rightarrow q) \rightarrow (r \rightarrow s)$
  • Apply $A \rightarrow B \equiv \neg A \lor B$: $\neg(p \rightarrow q) \lor (r \rightarrow s)$
  • Apply $A \rightarrow B \equiv \neg A \lor B$: $\neg(\neg p \lor q) \lor (\neg r \lor s)$
  • Apply De Morgan's Law: $(p \land \neg q) \lor (\neg r \lor s)$
  • Using associative property of disjunction: $(p \land \neg q) \lor \neg r \lor s$
• Second expression: $(p \rightarrow r) \rightarrow (q \rightarrow s)$
  • Apply $A \rightarrow B \equiv \neg A \lor B$: $\neg(p \rightarrow r) \lor (q \rightarrow s)$
  • Apply $A \rightarrow B \equiv \neg A \lor B$: $\neg(\neg p \lor r) \lor (\neg q \lor s)$
  • Apply De Morgan's Law: $(p \land \neg r) \lor (\neg q \lor s)$
  • Using associative property of disjunction: $(p \land \neg r) \lor \neg q \lor s$

Comparing the simplified forms, $(p \land \neg q) \lor \neg r \lor s$ is not the same as $(p \land \neg r) \lor \neg q \lor s$. For example, consider the case where $p$ is False, $q$ is True, $r$ is False, and $s$ is False:

• $(p \rightarrow q) \rightarrow (r \rightarrow s) \equiv (F \rightarrow T) \rightarrow (F \rightarrow F) \equiv T \rightarrow T \equiv T$
• $(p \rightarrow r) \rightarrow (q \rightarrow s) \equiv (F \rightarrow F) \rightarrow (T \rightarrow F) \equiv T \rightarrow F \equiv F$

Since the truth values differ for this assignment (T vs F), the two expressions in Pair C are not logically equivalent.

Conclusion on Logical Equivalence

Based on the analysis:

• Pair A is logically equivalent.
• Pair B is not logically equivalent.
• Pair C is not logically equivalent.

Therefore, only Pair A is logically equivalent.

Revision Table: Key Logical Equivalences

Additional Information on Propositional Logic Concepts

Propositional logic is a branch of logic that studies ways of joining and/or modifying entire propositions, statements, or sentences to form more complicated propositions, statements, or sentences, as well as the logical relationships and properties that are derived from these methods of combining or altering statements. Key components include:

• Propositions: Declarative sentences that are either true or false, but not both.
• Propositional Variables: Letters (like $p, q, r$) representing propositions.
• Logical Connectives: Symbols used to combine propositions:
  • Negation ($\neg$, NOT)
  • Conjunction ($\land$, AND)
  • Disjunction ($\lor$, OR)
  • Implication ($\rightarrow$, IF...THEN)
  • Biconditional ($\leftrightarrow$, IF AND ONLY IF)
• Truth Values: True (T) and False (F).
• Truth Tables: Tables that show the truth value of a compound proposition for all possible truth assignments to its variables.
• Tautology: A compound proposition that is always true, regardless of the truth values of its variables.
• Contradiction: A compound proposition that is always false, regardless of the truth values of its variables.
• Contingency: A compound proposition that is neither a tautology nor a contradiction.

Understanding logical equivalence is crucial for simplifying logical expressions, proving theorems, and designing logic circuits.