[Math] Substitution not clear in logic

logic

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:

  1. Which standard equivalence(s) you use,
  2. whether you apply Substitution or Leibniz, or both,
  3. 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:

  • Commutativity
  • Associativity
  • Idempotence
  • Double Negation
  • Inversion
  • True/False-elimination
  • Negation
  • Contradiction
  • Excluded Middle
  • Distributivity
  • De Morgan
  • Implication
  • Contraposition
  • Bi-implication
  • Self-equivalence

The exercises come from the book Logical reasoning: A first course Amazon Link

Best Answer

You are working in the algebra of propositions, whose objects are the propositional expressions (i.e. formulas obtained by applications of connectives to propositional variables and truth-values) and operations are the connectives themselves.

In such algebra there are some expression that are equivalent, meaning that they represent the same logical proposition.

Leibnitz lemma states that propositional expressions depend functionally from their subexpression: if you replace/substitute inside a formula a subformula with another equivalent formula the obtained formula is equivalent to the starting one. This statement is similar to the one that says if you have a functional expression $f(x)$ depending by a variable $x$ then if $a=b$ you have that $f(a)=f(b)$, i.e. the expression obtained by substitution of $x$ in $f$ with $a$ and $b$ are equivalent.

Substitution lemmas instead says something different: it tells that if you have two equivalent formulas (that may contain some variables) and substitute in both formulas a variable with a formula then you get two formulas that are equivalent. This statement is similar to the following functional one: for any pair of functional expressions $f(x)$ and $g(x)$, both depending on $x$, if $f(x)=g(x)$ then for every other functional expression $h(y)$ the equality $f(h(y))=g(h(y))$ holds (where $f(h(y))$ is the obvious expression you get if you substitute every occurrence of the $x$ in $f(x)$ with the expression $h(y)$).

As for understanding how to use such principles I guess an example is of help. So let's prove the equivalence $\neg P \land P = P$. We start by idempotence $$P \land P = P$$ by substitution lemma we can substitute in both expression $P$ with $\neg P$ and get the an equivalence $$\neg P \land \neg P = \neg P$$

To see an application of Leibnitz lemma let's prove the second equivalence namely $\neg P \Rightarrow \text{False} = P$. To prove this we start from the equivalence $$P \Rightarrow Q = \neg P \lor Q$$ by substitution lemma we get the equivalence $$P \Rightarrow \text{False} = \neg P \lor \text{False}$$ again by substitution of $P$ with $\neg P$ we get the equivalence $$\neg P \Rightarrow \text{False} = \neg (\neg P )\lor \text{False}$$ Now since the equivalence $\neg (\neg P) = P$ holds we can get the equivalence $$\neg (\neg P) \lor \text{False} = P \lor \text{False}$$ and so by transitivity of equivalence $$\neg P \Rightarrow \text{False} = P \lor \text{False}$$ In the end the true-elimination equivalence $P \lor \text{False} = P$ allows to deduce that $$\neg P \Rightarrow \text{False} = P$$

Hope this helps.

Related Question