# Substitution not clear in 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
• Excluded Middle
• Distributivity
• De Morgan
• Implication
• Contraposition
• Bi-implication
• Self-equivalence

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

-
I think it would be of help if you tell where the exercise come from. Also could you point out which are the standard equivalences you're referring to? –  Giorgio Mossa Sep 21 '13 at 11:14
I think you've printed the first part of the message twice here. –  Doug Spoonwood Sep 22 '13 at 1:24

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.

-
I've drawn my own conclusions and also submitted an answer, could you maybe take a look at it and check it if it's any good? –  CrypticMetaphor Sep 21 '13 at 17:33

I've thought about it and have thought answers to the questions. I will give my answers by means of demonstration. By calculating with the all the propositions stated in the original question.

The first explanation will be a bit more verbose than the others:

(a) $\neg P \wedge \neg P = \neg P$

Our goal is to prove that $\neg P \wedge \neg P$ is equal to $\neg P$. Our tools are the standard equivalences, substitution, and Leibniz.

First we make the following statement:

• $\neg P \wedge \neg P = \neg P \wedge \neg P$
• Idempotence: $P \wedge P = P$
• $P \wedge P = P$
• Substitute: $P$ with $\neg P$
• $\neg P \wedge \neg P = \neg P$
• Leibniz: $\neg P \wedge \neg P$ with $\neg P$
• $\neg P \wedge \neg P = \neg P$

1. Equivalences used:
• Idempotence, used once
2. Substitute, used once
3. Leibniz, used once

(b) $P = \neg P \Rightarrow \text{False}$

• $P=P$
• Negation: $\neg P = P \Rightarrow \text{False}$
• $\neg P = P \Rightarrow \text{False}$
• Substitute: $P$ with $\neg P$
• $\neg \neg P = \neg P \Rightarrow \text{False}$
• Double Negation: $\neg \neg P = P$
• $\neg \neg P = P$
• Leibniz: $\neg \neg P$ with $P$
• $P = \neg P \Rightarrow \text{False}$
• Leibniz: $P$ with $\neg P \Rightarrow \text{False}$
• $P = \neg P \Rightarrow \text{False}$

1. Equivalences used:
• Negation, used once
• Double Negation, used once
2. Substitute, used once
3. Leibniz, used once

(c) $(P \Rightarrow Q) \vee \neg(P \Rightarrow Q) = \text{True}$

• $(P \Rightarrow Q) \vee \neg(P \Rightarrow Q) = (P \Rightarrow Q) \vee \neg(P \Rightarrow Q)$
• Alias: $\varphi = P \Rightarrow Q$
• $\varphi \vee \neg \varphi = \varphi \vee \neg \varphi$
• Excluded Middle: $\varphi \vee \neg \varphi = \text{True}$
• $\varphi \vee \neg \varphi = \text{True}$
• Leibniz: $(P \Rightarrow Q) \vee \neg(P \Rightarrow Q)$ with $\text{True}$
• $(P \Rightarrow Q) \vee \neg(P \Rightarrow Q) = \text{True}$

1. Equivalences used:
• Excluded Middle, used once
2. Substitute, used once
3. Leibniz, used once

(d) $P \wedge (Q \vee Q) = P \wedge Q$

• $P \wedge (Q \vee Q) = P \wedge (Q \vee Q)$
• Idempotence: $Q \vee Q = Q$
• $Q \vee Q = Q$
• Leibniz: $(Q \vee Q$) with $Q$
• $P \wedge (Q \vee Q) = P \wedge Q$

1. Equivalences used:
• Idempotence, used once
2. Substitute, not used
3. Leibniz, used once

(e) $P \vee (\neg P \wedge Q) = P \vee Q$

• $P \vee (\neg P \wedge Q) = P \vee (\neg P \wedge Q)$
• Distributivity: $P \vee (\neg P \wedge Q) = (P \vee \neg P) \wedge (P \vee Q)$
• $P \vee (\neg P \wedge Q) = (P \vee \neg P) \wedge (P \vee Q)$
• Leibniz: $P \vee (\neg P \wedge Q)$ with $(P \vee \neg P) \wedge (P \vee Q)$
• $P \vee (\neg P \wedge Q) = (P \vee \neg P) \wedge (P \vee Q)$
• Excluded Middle: $P \vee \neg P = \text{True}$
• $P \vee \neg P = \text{True}$
• Leibniz: $(P \vee \neg P)$ with $\text{True}$
• $P \vee (\neg P \wedge Q) = \text{True} \wedge (P \vee Q)$
• Alias: $\varphi = P \vee Q$
• $P \vee (\neg P \wedge Q) = \text{True} \wedge \varphi$
• True/False-elimination: $\text{True} \wedge \varphi = \varphi$
• $\text{True} \wedge \varphi = \varphi$
• Leibniz $\text{True} \wedge \varphi$ with $\varphi$
• $P \vee (\neg P \wedge Q) = \varphi$
• $P \vee (\neg P \wedge Q) = P \vee Q$

1. Equivalences used:
• Distributivity, used once
• Excluded Middle, used once
• True/False-elimination, used once
2. Substitute, not used
3. Leibniz, used thrice

I think I've demonstrated my understanding of Leibniz and Substitution by writing this answer.

-
Actually there's an error in c) : you cannot substitute $P \Rightarrow Q$ with $A$ because you can just applies substitutions to letters (i.e. variables) not the expressions. Also there are many times you use Leibnitz but I personally don't get where do you use it. –  Giorgio Mossa Sep 21 '13 at 18:28
I see. I will fix that problem later. Well about leibnitz, the basic idea I had is that, every time I indent, I show an equivalence. because I know that equivalences are correct. I can replace the a part of the formula shown before the equivalence with an identical one. Can you give tell me one which you don't get? –  CrypticMetaphor Sep 21 '13 at 18:40
No, ok I get it some times you use Leibnitz in a trival form (i.e. when one of the two expression in the equation doesn't depend on a variable) now I get it. –  Giorgio Mossa Sep 21 '13 at 18:45