Logic – Applying Rules of Replacement in Proofs

logicproof-writing

I'm a beginner in proof-based math, and I'm trying to flesh out my understanding of the reasoning behind proofs of logical equivalence ($a \iff b$) and implication ($a \implies b$).

  • When proving that some compound proposition, which is made up of various atomic propositional variables (say $p, q, r$), is equivalent to another compound proposition, it seems that at each step in a proof to iteratively show logical equivalence we can replace any proposition with an equivalent one. For example, using a known premise that $p \iff q$ in a broader proof of logical equivalence:
    $$
    \begin{align}
    & \dots p \dots \newline
    \iff & \dots q \dots
    \end{align}
    $$

    • Is this indeed true? Is there a specific rule of logic that this technique is appealing to?

  • Moreover, when proving that some compound proposition, which is made up of various atomic propositional variables (say $p, q, r$), implies some other compound proposition, I've been assuming that we can do the analogous replacement: i.e., that in a proof to iteratively show logical implication we can replace any proposition with one that it implies. For example, using a known premise that $p \implies q$ in a broader proof of logical implication:
    $$
    \begin{align}
    & \dots p \dots \newline
    \implies & \dots q \dots
    \end{align}
    $$

    • Is this valid reasoning? If so, is there a specific rule of logic/inference that this technique is appealing to? (If not, why not? Is there some simple counterexample to help understanding why?)

I've referred to various "intro to proofs" math texts and also looked around the internet, and I can't find any resource stating either of these facts clearly in this context. So any insights or clarification including a pointer to useful references would be very helpful.

Best Answer

  • When proving that some compound proposition, which is made up of various atomic propositional variables (say $p, q, r$), is equivalent to another compound proposition, it seems that at each step in a proof to iteratively show logical equivalence we can replace any proposition with an equivalent one. For example, using a known premise that $p \iff q$ in a broader proof of logical equivalence: $$ \begin{align} & \dots p \dots \newline \iff & \dots q \dots \end{align} $$ Is this indeed true? Is there a specific rule of logic that this technique is appealing to?

Yes, it is true you can make those substitutions/replacements. It is not so much an equivalence principle like DeMorgan or Distribution, but rather a meta-logical principle. It is called the Replacement Theorem ... but it being a meta-logical principle, you don't really need to refer to it. Thus, going from something like:

$$A \lor \neg \neg B$$

to

$$A \lor B$$

can be justified by Double Negation (even though you implicitly do use the Law of Replacement as well)

  • Moreover, when proving that some compound proposition, which is made up of various atomic propositional variables (say $p, q, r$), implies some other compound proposition, I've been assuming that we can do the analogous replacement: i.e., that in a proof to iteratively show logical implication we can replace any proposition with one that it implies. For example, using a known premise that $p \implies q$ in a broader proof of logical implication: $$ \begin{align} & \dots p \dots \newline \implies & \dots q \dots \end{align} $$ Is this valid reasoning? If so, is there a specific rule of logic/inference that this technique is appealing to? (If not, why not? Is there some simple counterexample to help understanding why?)

No! This is not valid (or rather, not always .. which is why, for safety sake, we never allow it)

Consider:

We know that we have a rule (often called Simplification or $\land$ Elimination) that allows you to go from:

$$P \land Q$$

to:

$$P$$

But note, if you would be allowed to apply this to:

$$(P \land Q) \to R$$

you would get:

$$P \to R$$

and that is not a valid inference! (set P to true and $Q$ and $R$ to False, and $(P \land Q) \to R$ wil be True, but $(P \land Q) \to R$ will be false.

So no, there is no such analogous replacement principle for logical implication like there is for logical equivalence.

Related Question