Formal Logic/Sentential Logic/Derived Inference Rules

← Theorems

↑ Sentential Logic

Disjunctions in Derivations →

Derived Inference Rules

This page introduces the notion of a derived inference rule and provides a few such rules.

Deriving inference rules

The basics

Now we can carry the abbreviation a step further. A derived inference rule is an inference rule not given to us as part of the derivation system but which constitutes an abbreviation using a previously proved theorem. In particular, suppose we have proved a particular theorem. In this theorem, uniformly replace each sentence letter with a distinct Greek letter. Suppose the result has the following form.

$\varphi _{1}\land \varphi _{2}\land \ ...\,\land \ \varphi _{n}\rightarrow \psi \,\!$.

[Comment: This and what follows seems to me to be potentially confusing to students. The intention stated in earlier sections to avoid metatheory creates a problem here as one needs to know about the Deduction Theorem for this to make more sense.]

We may then introduce a derived inference rule having the form

$\varphi _{1}\,\!$

$\varphi _{2}\,\!$

$\ \vdots$

${\underline {\varphi _{n}}}\,\!$

$\psi \,\!$

An application of the derived rule can be eliminated by replacing it with

1. the previously proved theorem,
2. repeated applications of Conjunction Introduction (KI) to build up the theorem's antecedent, and
3. an application of Conditional Elimination (CE) to obtain the theorem's consequent.

The previously proved theorem can then be eliminated as described above. That would leave you with an unabbreviated derivation.

Removing abbreviations from a derivation is not desirable, of course, because it makes the derivation more complicated and harder to read, but the fact that a derivation could be unabbreviated justifies the use of abbreviations, so that we can employ abbreviations in the first place.

Repetition

Our first derived inference rule will be based on T1, which is

$\mathrm {P} \rightarrow \mathrm {P} \,\!$

Replace the sentence letters with Greek letters, and we get:

$\varphi \rightarrow \varphi \,\!$

We now generate the derived inference rule:

Repetition (R)

${\underline {\varphi }}\,\!$

$\varphi \,\!$

Now we can show how this rule could have simplified our proof of T2.

1.     $\mathrm {Q} \,\!$   Assumption    $[\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )]\,\!$     2.       $\mathrm {P} \,\!$   Assumption    $[\mathrm {P} \rightarrow \mathrm {Q} ]\,\!$ 3.       $\mathrm {Q} \,\!$   1 R     4.     $\mathrm {P} \rightarrow \mathrm {Q} \,\!$   2–3 CI   5.   $\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )\,\!$   1–4 CI

While this is only one line shorter than our original proof of T2, it is less obnoxious. We can use an inference rule instead of a silly trick. As a result, the derivation is easier to read and understand (not to mention easier to produce).

Double negation rules

The next two theorems—and the derived rules based on them—exploit the equivalence between a doubly negated formula and the unnegated formula.

Double Negation Introduction

$\mathbf {T3.} \quad \mathrm {P} \rightarrow \lnot \lnot \mathrm {P} \,\!$

1.     $\mathrm {P} \,\!$   Assumption    $[\mathrm {P} \rightarrow \lnot \lnot \mathrm {P} ]\,\!$     2.       $\lnot \mathrm {P} \,\!$   Assumption    $[\lnot \lnot \mathrm {P} ]\,\!$ 3.       $\mathrm {P} \,\!$   1 R     4.     $\lnot \lnot \mathrm {P} \,\!$   2–3 NI   5.   $\mathrm {P} \rightarrow \lnot \lnot \mathrm {P} \,\!$   1–4 CI

T3 justifies the following rule.

Double Negation Introduction (DNI)

${\underline {\varphi \quad }}\,\!$

$\lnot \lnot \varphi \,\!$

Double Negation Elimination

$\mathbf {T4.} \quad \lnot \lnot \mathrm {P} \rightarrow \mathrm {P} \,\!$

1.     $\lnot \lnot \mathrm {P} \,\!$   Assumption    $[\lnot \lnot \mathrm {P} \rightarrow \mathrm {P} ]\,\!$     2.       $\lnot \mathrm {P} \,\!$   Assumption    $[\mathrm {P} ]\,\!$ 3.       $\lnot \lnot \mathrm {P} \,\!$   1 R     4.     $\mathrm {P} \,\!$   2–3 NE   5.   $\lnot \lnot \mathrm {P} \rightarrow \mathrm {P} \,\!$   1–4 CI

T4 justifies the following rule.

Double Negation Elimination (DNE)

${\underline {\lnot \lnot \varphi }}\,\!$

$\varphi \,\!$

Additional derived rules

Contradiction

$\mathbf {T5.} \quad \mathrm {P} \land \lnot \mathrm {P} \rightarrow \mathrm {Q} \,\!$

1.     $\mathrm {P} \land \lnot \mathrm {P} \,\!$   Assumption    $[\mathrm {P} \land \lnot \mathrm {P} \rightarrow \mathrm {Q} ]\,\!$     2.       $\lnot \mathrm {Q} \,\!$   Assumption    $[\mathrm {Q} ]\,\!$ 3.       $\mathrm {P} \,\!$   1 S 4.       $\lnot \mathrm {P} \,\!$   1 S     5.     $\mathrm {Q} \,\!$   2–4 NE   7.   $\mathrm {P} \land \lnot \mathrm {P} \rightarrow \mathrm {Q} \,\!$   1–5 CI

Our next rule is based on T5.

Contradiction (Contradiction)

$\varphi \,\!$

${\underline {\lnot \varphi }}\,\!$

$\psi \,\!$

This rule is occasionally useful when you have derived a contradiction but the discharge rule you want is not NI or NE. This then avoids a completely trivial subderivation. The rule of Contradiction will be used in the proof of the next theorem.

Conditional Addition

$\mathbf {T6.} \quad \lnot \mathrm {P} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )\,\!$

1.     $\lnot \mathrm {P} \,\!$   Assumption    $[\lnot \mathrm {P} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )]\,\!$     2.       $\mathrm {P} \,\!$   Assumption    $[\mathrm {P} \rightarrow \mathrm {Q} ]\,\!$ 3.       $\mathrm {Q} \,\!$   1, 2 Contradiction     4.     $\mathrm {P} \rightarrow \mathrm {Q} \,\!$   2–3 CI   5.   $\lnot \mathrm {P} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )\,\!$   1–4 CI

On the basis of T2 and T6, we introduce the following derived rule.

Conditional Addition, Form I (CAdd)

${\underline {\psi \quad \quad \quad }}\,\!$

$(\varphi \rightarrow \psi )\,\!$

Conditional Addition, Form II (CAdd)

${\underline {\lnot \psi \quad \quad \ }}\,\!$

$(\psi \rightarrow \varphi )\,\!$

The name 'Conditional Addition' is not in common use. It is based on the traditional name for Disjunction Introduction, namely 'Addition'. This rule does not provide a general means of introducing a conditional. This is because the antecedent line you would need is not always derivable. However, when the antecedent line just happens to be easily available, then applying this rule is simpler than producing the subderivation needed for a Conditional Introduction.

Modus Tollens

$\mathbf {T7.} \quad (\mathrm {P} \rightarrow \mathrm {Q} )\land \lnot \mathrm {Q} \rightarrow \lnot \mathrm {P} \,\!$

1.     $(\mathrm {P} \rightarrow \mathrm {Q} )\land \lnot \mathrm {Q} \,\!$   Assumption    $[(\mathrm {P} \rightarrow \mathrm {Q} )\land \lnot \mathrm {Q} \rightarrow \lnot \mathrm {P} ]\,\!$     2.       $\mathrm {P} \,\!$   Assumption    $[\lnot \mathrm {P} ]\,\!$ 3.       $\mathrm {P} \rightarrow \mathrm {Q} \,\!$   1 KE 4.       $\mathrm {Q} \,\!$   2, 3 CE 5.       $\lnot \mathrm {Q} \,\!$   1 KE     6.     $\lnot \mathrm {P} \,\!$   2–5 NI   7.   $(\mathrm {P} \rightarrow \mathrm {Q} )\land \lnot \mathrm {Q} \rightarrow \lnot \mathrm {P} \,\!$   1–6 CI

Now we use T7 to justify the following rule.

Modus Tollens (MT)

$(\varphi \rightarrow \psi )\,\!$

${\underline {\lnot \psi \quad \quad \ }}\,\!$

$\lnot \varphi \,\!$

Modus Tollens is also sometimes known as 'Denying the Consequent'. Note that the following is not an instance of Modus Tollens, at least as defined above.

$\lnot \mathrm {P} \rightarrow \lnot \mathrm {Q} \,\!$

${\underline {\mathrm {Q} \quad \quad \quad \quad }}\,\!$

$\mathrm {P} \,\!$

The premise lines of Modus Tollens are a conditional and the negation of its consequent. The premise lines of this inference are a conditional and the opposite of its consequent, but not the negation of its consequent. The desired inference here needs to be derived as below.

1.   $\lnot \mathrm {P} \rightarrow \lnot \mathrm {Q} \,\!$   Premise 2.   $\mathrm {Q} \,\!$   Premise 3.   $\lnot \lnot \mathrm {Q} \,\!$   2 DNI 4.   $\lnot \lnot \mathrm {P} \,\!$   1, 3 CE 5.   $\mathrm {P} \,\!$   4 DNE

Of course, it is possible to prove as a theorem:

$(\lnot \mathrm {P} \rightarrow \lnot \mathrm {Q} )\land \mathrm {Q} \rightarrow \mathrm {P} \ .\,\!$

Then you can add a new inference rule—or, more likely, a new form of Modus Tollens—on the basis of this theorem. However, we won't do that here.

Additional theorems

The derived rules given so far are quite useful for eliminating frequently used bits of obnoxiousness in our derivations. They will help to make your derivations easier to generate and also more readable. However, because they are indeed derived rules, they are not strictly required but rather are theoretically dispensable.

A number of other theorems and derived rules could usefully be added. We list here some useful theorems but leave their proofs and the definition of their associated derived inference rules to the reader. If you construct many derivations, you may want to maintain your own personal list that you find useful.

Theorems with biconditionals

$\mathbf {T8.} \quad (\mathrm {P} \leftrightarrow \mathrm {Q} )\land \lnot \mathrm {P} \rightarrow \lnot \mathrm {Q} \,\!$

$\mathbf {T9.} \quad (\mathrm {P} \leftrightarrow \mathrm {Q} )\land \lnot \mathrm {Q} \rightarrow \lnot \mathrm {P} \,\!$

$\mathbf {T10.} \quad \mathrm {P} \land \mathrm {Q} \rightarrow (\mathrm {P} \leftrightarrow \mathrm {Q} )\,\!$

$\mathbf {T11.} \quad \lnot \mathrm {P} \land \lnot \mathrm {Q} \rightarrow (\mathrm {P} \leftrightarrow \mathrm {Q} )\,\!$

Theorems with negations

$\mathbf {T12.} \quad \lnot (\mathrm {P} \rightarrow \mathrm {Q} )\rightarrow \mathrm {P} \land \lnot \mathrm {Q} \,\!$

$\mathbf {T13.} \quad \lnot (\mathrm {P} \leftrightarrow \mathrm {Q} )\rightarrow (\mathrm {P} \leftrightarrow \lnot \mathrm {Q} )\,\!$

$\mathbf {T14.} \quad \lnot (\mathrm {P} \lor \mathrm {Q} )\rightarrow \lnot \mathrm {P} \land \lnot \mathrm {Q} \,\!$

$\mathbf {T15.} \quad \lnot (\mathrm {P} \land \mathrm {Q} )\rightarrow \lnot \mathrm {P} \lor \lnot \mathrm {Q} \,\!$