I'm learning logical reasoning and I'm a bit stuck at understanding substitution. Here are the lemmas of substitution and Leibniz:
Lemma substitution: Suppose that a formula is equivalent to another, and that, for example, the letter P occurs many times in both formulas. Then it holds that: If in both formulas, we substitute one (and the same) thing for P, then the resulting formulas are also equivalent. This holds for single, sequential and simultaneous substitutions.
Lemma Leibniz: If an abstract proposition $\phi$, sub-formula $\psi1$ is replaced by an equivalent formula $\psi2$, the old and the new $\phi$ are equivalent.
Now I understand what both mean. But when I get to the following exercise I get confused:
Show the equivalences by calculating with propositions. Always state precisely:
- Which standard equivalence(s) you use,
- whether you apply Substitution or Leibniz, or both,
- and how you do this.
(a) $\neg P \wedge \neg P = \neg P$
(b) $P = \neg P \Rightarrow False$
(c) $(P \Rightarrow Q) \vee \neg(P \Rightarrow Q) = True$
(b) $P \wedge (P \wedge Q) = P$
(d) $P \vee (\neg P \wedge Q) = P \vee Q$
I understand standard equivalences, and I understand leibniz, but how does substitution come into play? Don't you need two equivalent formulas for substitution in which you replace a variable in both formulas? I don't understand where substituion comes into play here, all I see is Leibniz. Just replace a formula by an equivalent one.
Could someone explain how substituion applies to these excercises?I'm learning logical reasoning and I'm a bit stuck at understanding substitution. Here are the lemmas of substitution and Leibniz:
Here is the list of standard equivalences I got from the book:
- Double Negation
- Excluded Middle
- De Morgan
The exercises come from the book Logical reasoning: A first course Amazon Link