🧠

Rules of Replacement and Propositional Logic

Jun 16, 2024

Rules of Replacement and Propositional Logic

Introduction

  • Rules of Replacement: Allow for the exchange of logical expressions.
  • Rules of Implication: Create something new through multistep processes.
  • Focus today: Rules of Replacement.

Key Concepts and Rules

De Morgan's Law

  • Form 1:
    • $ eg(P \lor Q) \leftrightarrow (\neg P \land \neg Q)$
  • Form 2:
    • $ eg(P \land Q) \leftrightarrow (\neg P \lor \neg Q)$
  • Example:
    • If a store has neither turkey nor stuffing ($\neg(P \lor Q)$), it means they don't have turkey and don't have stuffing ($\neg P \land \neg Q$).
    • If a store doesn't have both turkey and stuffing ($\neg(P \land Q)$), it means they don't have turkey or they don't have stuffing ($\neg P \lor \neg Q$).

Commutativity

  • Or (wedge): $P \lor Q \leftrightarrow Q \lor P$
  • And (dot): $P \land Q \leftrightarrow Q \land P$

Associativity

  • Or: $(P \lor Q) \lor R \leftrightarrow P \lor (Q \lor R)$
  • And: $(P \land Q) \land R \leftrightarrow P \land (Q \land R)$
  • Parentheses become irrelevant.

Distribution

  • Or: $P \lor (Q \land R) \leftrightarrow (P \lor Q) \land (P \lor R)$
  • And: $P \land (Q \lor R) \leftrightarrow (P \land Q) \lor (P \land R)$

Double Negation

  • Removing or adding two negation symbols does not change the meaning.
  • Example: $\neg(\neg P) \leftrightarrow P$

Application of Rules

Example Problems

  1. Example 1:

    • Given: $Q \lor (L \lor C), \neg C$
    • Conclusion: $L \lor Q$
    • Steps:
      1. Apply Commutativity: $L \lor C \lor Q$ (conversion)
      2. Apply Associativity: $(L \lor (C \lor Q))$ (shift parenthesis)
      3. Apply Disjunctive Syllogism: $Q \lor L$
      4. Apply Commutativity: $L \lor Q$ (to get conclusion)

  2. Example 2:

    • Given: $(H \land (C \land T)), \neg C$
    • Conclusion: $\neg R \lor \neg Q$
    • Steps:
      1. Simplify using Simplification Rule.
      2. Apply Distribution: $(S \lor I) \land \neg J$
      3. Apply Constructive Dilemma.
      4. Use Double Negation as necessary.

Tips for Problem Solving

  • Follow Steps: Always follow allowed logical steps.
  • Rewrite Conclusions: Sometimes useful to rewrite the conclusion for clarity.
  • Be flexible: If initial steps are faulty, be willing to reassess and take a different path.

Closing

  • Practice using the rules.
  • Memorize the key principles for efficient problem solving.
  • Keep working on exercises to internalize these logical operations.

Note: Always ensure logical steps align with the correct rules for validity.

Full transcript