3.2 Rules of Inference and Replacement

Rules of inference and replacement are essential tools in propositional logic. They allow us to draw valid conclusions from given premises and transform logical expressions into equivalent forms. These rules form the foundation for constructing and analyzing arguments in formal reasoning.

Understanding these rules enables us to navigate complex logical statements and build sound arguments. By applying rules like modus ponens, modus tollens, and De Morgan's laws, we can simplify, transform, and derive new information from existing propositions, enhancing our ability to reason logically.

Rules of Inference

Rules of inference in propositional logic

• Modus ponens (MP) states that if a conditional statement $P \to Q$ is true and the antecedent $P$ is true, then the consequent $Q$ must be true
  • Example: If it is raining ($P$) and if it is raining, then the ground is wet ($P \to Q$), then it can be inferred that the ground is wet ($Q$)
• Modus tollens (MT) asserts that if a conditional statement $P \to Q$ is true and the consequent $Q$ is false, then the antecedent $P$ must be false
  • Example: If the ground is not wet ($\neg Q$) and if it is raining, then the ground is wet ($P \to Q$), then it can be deduced that it is not raining ($\neg P$)
• Hypothetical syllogism (HS) allows the chaining of conditional statements, stating that if $P \to Q$ is true and $Q \to R$ is true, then $P \to R$ is also true
  • Example: If it is raining, then the ground is wet ($P \to Q$), and if the ground is wet, then it is slippery ($Q \to R$), then it follows that if it is raining, it is slippery ($P \to R$)
• Disjunctive syllogism (DS) states that if a disjunction $P \lor Q$ is true and one of the disjuncts, say $P$, is false, then the other disjunct $Q$ must be true
  • Example: If it is either raining or sunny ($P \lor Q$) and it is not raining ($\neg P$), then it must be sunny ($Q$)

Construction of valid propositional arguments

• Combine multiple rules of inference to create a valid argument
  • Example: Given $P \to Q$, $Q \to R$, and $P$, apply HS to obtain $P \to R$, then use MP with $P$ to conclude $R$
• Simplify statements within an argument using rules of replacement
  • Example: If $\neg(P \land Q)$ is known, apply De Morgan's law to obtain $\neg P \lor \neg Q$, which can then be used in a DS with additional information

Rules of Replacement

Rules of replacement for propositions

• Double negation (DN) states that two negations cancel each other out: $\neg(\neg P) \equiv P$
  • Example: The statement $\neg(\neg(it\ is\ raining))$ is logically equivalent to $it\ is\ raining$
• De Morgan's laws allow the negation of a conjunction to be distributed to the individual propositions and the connective to be flipped:
  1. $\neg(P \land Q) \equiv \neg P \lor \neg Q$
  2. $\neg(P \lor Q) \equiv \neg P \land \neg Q$
  • Example: $\neg(it\ is\ raining \land it\ is\ sunny)$ is equivalent to $it\ is\ not\ raining \lor it\ is\ not\ sunny$
• Conditional equivalences provide alternative ways to express conditional statements:
  1. $P \to Q \equiv \neg P \lor Q$
  2. $P \to Q \equiv \neg Q \to \neg P$ (contraposition)
  • Example: The statement $it\ is\ raining \to the\ ground\ is\ wet$ is equivalent to $it\ is\ not\ raining \lor the\ ground\ is\ wet$

Simplification of propositional statements

• Apply DN to remove double negatives
  • Example: Simplify $\neg(\neg(P \land Q))$ to $P \land Q$
• Use De Morgan's laws to simplify negated conjunctions or disjunctions
  • Example: Rewrite $\neg(P \lor (\neg Q \land R))$ as $\neg P \land (Q \lor \neg R)$
• Utilize conditional equivalences to rewrite conditional statements
  • Example: Transform $(P \land Q) \to R$ into $\neg(P \land Q) \lor R$, which can be further simplified to $\neg P \lor \neg Q \lor R$