As we saw in the introductory lesson, the essence of logical reasoning is symbolic manipulation. We start with premises, apply rules of inference to derive conclusions, stringing together such derivations to form logical proofs. The idea is simple. Getting the details right requires a little care. Let's start by defining schemas and rules of inference.
A schema is an expression satisfying the grammatical rules of our language except for the occurrence of metavariables (written here as Greek letters) in place of various subparts of the expression. For example, the following expression is a schema with metavariables φ and ψ.
φ ⇒ ψ
A rule of inference is a pattern of reasoning consisting of some schemas, called premises, and one or more additional schemas, called conclusions. Rules of inference are often written as shown below. The schemas above the line are the premises, and the schemas below the line are the conclusions.
φ ⇒ ψ
The rule in this case is called Implication Elimination (or IE), because it eliminates the implication from the first premise.
Implication Creation (IC), shown below, is another example. This rule tells us that, if a sentence ψ is true, we can infer (φ ⇒ ψ) for any φ whatsoever.
φ ⇒ ψ
Implication Distribution (ID) tells us that implication can be distributed over other implications. If (φ ⇒ (ψ ⇒ χ)) is true, then we can infer ((φ ⇒ ψ) ⇒ (φ ⇒ χ)).
φ ⇒ (ψ ⇒ χ)
(φ ⇒ ψ) ⇒ (φ ⇒ χ)
An instance of a rule of inference is the rule obtained by consistently substituting sentences for the metavariables in the rule. For example, the following is an instance of Implication Elimination.
p ⇒ q
If a metavariable occurs more than once, the same expression must be used for every occurrence. For example, in the case of Implication Elimination, it would not be acceptable to replace one occurrence of φ with one expression and the other occurrence of φ with a different expression.
Note that the replacement can be an arbitrary expression so long as the result is a legal expression. For example, in the following instance of Implication Elimination, we have replaced the variables by compound sentences.
(p ⇒ q) ⇒ (q ⇒ r)
(p ⇒ q)
(q ⇒ r)
Remember that there are infinitely many sentences in our language. Even though we start with finitely many propositional constants (in a propositional vocabulary) and finitely many operators, we can combine them in arbitrarily many ways. The upshot is that there are infinitely many instances of any rule of inference involving metavariables.
A rule applies to a set of sentences if and only if there is an instance of the rule in which all of the premises are in the set. In this case, the conclusions of the instance are the results of the rule application.
For example, if we had a set of sentences containing the sentence p and the sentence (p ⇒ q), then we could apply Implication Elimination to derive q as a result. If we had a set of sentences containing the sentence (p ⇒ q) and the sentence (p ⇒ q) ⇒ (q ⇒ r), then we could apply Implication Elimination to derive (q ⇒ r) as a result.
In using rules of inference, it is important to remember that they apply only to top-level sentences, not to components of sentences. While applying to components sometimes works, it can also lead to incorrect results.
As an example of such a problem, consider the incorrect application of Implication Elimination shown below. Suppose we believe (p ⇒ q) and (p ⇒ r). We might try to apply Implication Elimination here, taking the first premise as the implication and taking the occurrence of p in the second premise as the matching condition, leading us to conclude (q ⇒ r).
p ⇒ q
p ⇒ r
q ⇒ r
Unfortunately, this is not a proper logical conclusion from the premises, as we all know from experience and as we can quickly determine by looking at the associated truth table. It is important to remember that rules of inference apply only to top-level sentences.
By writing down premises, writing instances of axiom schemas, and applying rules of inference, it is possible to derive conclusions that cannot be derived in a single step. This idea of stringing things together in this way leads to the notion of a linear proof.
A linear proof of a conclusion from a set of premises is a sequence of sentences terminating in the conclusion in which each item is either (1) a premise, (2) an instance of an axiom schema, or (3) the result of applying a rule of inference to earlier items in sequence.
Here is an example. Suppose we have the set of sentences we saw earlier. We start our proof by writing out our premises. We believe p; we believe (p ⇒ q); and we believe that (p ⇒ q) ⇒ (q ⇒ r). Using Implication Elimination on the first premise and the second premise, we derive q. Applying Implication Elimination to the second premise and the third premise, we derive (q ⇒ r). Finally, we use the derived premises on lines 4 and 5 to arrive at our desired conclusion.
p ⇒ q
(p ⇒ q) ⇒ (q ⇒ r)
Implication Elimination: 2, 1
q ⇒ r
Implication Elimination: 3, 2
Implication Elimination: 5, 4
Here is another example. Whenever p is true, q is true. Whenever q is true, r is true. With these as premises, we can prove that, whenever p is true, r is true. On line 3, we use Implication Creation to derive (p ⇒ (q ⇒ r)). On line 4, we use Implication Distribution to distribute the implication in line 3. Finally, on line 5, we use Implication Elimination to produce the desired result.
p ⇒ q
q ⇒ r
p ⇒ (q ⇒ r)
Implication Creation: 2
(p ⇒ q) ⇒ (p ⇒ r)
Implication Distribution: 3
p ⇒ r
Implication Elimination: 4, 1
Let R be a set of rules of inference. If there exists a proof of a sentence φ from a set Δ of premises using the rules of inference in R, we say that φ is provable from Δ using R. We usually write this as Δ |-R φ, using the provability operator |- (which is sometimes called single turnstile). If the set of rules is clear from context, we usually drop the subscript, writing just Δ |- φ.
Note that the set of rules presented here is not powerful enough to prove everything that is entailed by a set of premises in Propositional Logic. There is no support for using or deducing negations or conjunctions or disjunctions or biconditionals. Even if we restrict ourselves to implications, we need more rules. While such rules of inference exist, they are a little complicated. For many people, it is easier to reason about implications using hypothetical reasoning.