Subsection 3.4.2 Inference Rules Preserve Truth
As in the case of the identities in the last section, what we’re claiming, in our statement of each of these inference rules, is that they are true for all propositions ( p , q , r , or even compound expressions containing Boolean operators).
Also, as in the case of the identities, we prove the correctness of each of these rules using truth tables. What we mean by correctness (generally called soundness in this context) is:
If a rule is applied to a set of premises P and it generates a new statement q , then q is guaranteed to be true whenever all the elements of P are.
Recall that we have other synonyms for this:
q follows from P .
P logically implies q .
P entails q .
Whatever we call it, we must preserve truth. We can describe how to do that by using the same structure that we used when we first introduced the idea of proof. We must show that, if one of our rules allows us to generate q from a set of premises P , then this is true:
\(( ∧ ∧ ∧ … ∧ ) →\)
We already know how to prove claims of this sort. Truth tables to the rescue. We will prove the correctness of each of our new inference rules with a truth table.
But first, we’ll introduce one more notation that is common when describing inference rules. We’ll write:
input 1
input 2
…
input n
∴ conclusion
This means that the rule we’re defining applies to one or more input statements and allows us to infer the conclusion.
Important note: Each of the expressions that matches a pattern above the inference line must be an entire statement. While it is allowed to apply identities to subexpressions, inference rules can apply only to entire statements.