Section 03: Rules of replacement

Last updated
Save as PDF

Page ID: 1066

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Consider how you would prove this argument: \(F\) → (\(G\)&\(H\)), .˙. \(F\) → \(G\)

Perhaps it is tempting to write down the premise and apply the &E rule to the conjunction (\(G\)&\(H\)). This is impermissible, however, because the basic rules of proof can only be applied to whole sentences. We need to get (\(G\)&\(H\)) on a line by itself. We can prove the argument in this way:

We will now introduce some derived rules that may be applied to part of a sentence. These are called rules of replacement, because they can be used to replace part of a sentence with a logically equivalent expression. One simple rule of replacement is commutivity (abbreviated Comm), which says that we can swap the order of conjuncts in a conjunction or the order of disjuncts in a disjunction. We define the rule this way:

(\(\mathcal{A}\) & \(\mathcal{B}\)) ⇐⇒ (\(\mathcal{B}\) & \(\mathcal{A}\))

(\(\mathcal{A}\)∨\(\mathcal{B}\)) ⇐⇒ (\(\mathcal{B}\)∨\(\mathcal{A}\))

(\(\mathcal{A}\)↔\(\mathcal{B}\)) ⇐⇒ (\(\mathcal{B}\)↔\(\mathcal{A}\)) Comm

The bold arrow means that you can take a subformula on one side of the arrow and replace it with the subformula on the other side. The arrow is doubleheaded because rules of replacement work in both directions.

Consider this argument: (\(M\)∨\(P\)) → (\(P\)&\(M\)), .˙. (\(P\)∨\(M\)) → (\(M\)&\(P\))

It is possible to give a proof of this using only the basic rules, but it will be long and inconvenient. With the Comm rule, we can provide a proof easily:

Another rule of replacement is double negation (DN). With the DN rule, you can remove or insert a pair of negations anywhere in a sentence. This is the rule:

¬¬\(\mathcal{A}\)⇐⇒\(\mathcal{A}\) DN

Two more replacement rules are called De Morgan’s Laws, named for the 19thcentury British logician August De Morgan. (Although De Morgan did discover these laws, he was not the first to do so.) The rules capture useful relations between negation, conjunction, and disjunction. Here are the rules, which we abbreviate DeM:

¬(\(\mathcal{A}\)∨\(\mathcal{B}\)) ⇐⇒ (¬\(\mathcal{A}\)&¬\(\mathcal{B}\))

¬(\(\mathcal{A}\)&\(\mathcal{B}\)) ⇐⇒ (¬\(\mathcal{A}\)∨¬\(\mathcal{B}\)) DeM

Because \(\mathcal{A}\)→\(\mathcal{B}\) is a material conditional, it is equivalent to ¬\(\mathcal{A}\)∨\(\mathcal{B}\). A further replacement rule captures this equivalence. We abbreviate the rule MC, for ‘material conditional.’ It takes two forms:

(\(\mathcal{A}\)→\(\mathcal{B}\)) ⇐⇒ (¬\(\mathcal{A}\)∨\(\mathcal{B}\))

(\(\mathcal{A}\)∨\(\mathcal{B}\)) ⇐⇒ (¬\(\mathcal{A}\)→\(\mathcal{B}\)) MC

Now consider this argument: ¬(\(P\) →\(Q\)), .˙. \(P\)&¬\(Q\)

As always, we could prove this argument using only the basic rules. With rules of replacement, though, the proof is much simpler:

A final replacement rule captures the relation between conditionals and biconditionals. We will call this rule biconditional exchange and abbreviate it ↔ex.

[(\(\mathcal{A}\)→\(\mathcal{B}\))&(\(\mathcal{B}\)→\(\mathcal{A}\))] ⇐⇒ (\(\mathcal{A}\)↔\(\mathcal{B}\)) ↔ex