Chapter 9


9.1 Formal Proof of Validity

Consider the following argument:



~ C

A v D

\ D

To establish the validity of this argument with a truth table would require a table of 16 rows. But we can establish its validity more efficiently by a sequence of elementary arguments, each of which is known to be valid. Such a step-by-step procedure is called a formal proof.

In general, we can define a formal proof, that a given argument is valid as a sequence of statements each of which is either a premiss of that argument or follows from preceding statements of the sequence by an elementary valid argument, such that the last statement in the sequence is the conclusion of the argument whose validity is being proved.

An elementary valid argument is any argument that is a substitution instance of an elementary valid argument form. It is important to understand that any substitution instance of an elementary valid argument form is an elementary valid argument.





A formal proof of the argument above would look like this:

    1. A B

2. B C

    1. ~ C
    2. A v D
    3. \ D

    4. A C1,2, H.S.

6. ~ A 5,3,M.T.

7. D 4,6, D.S.

The first four numbered propositions are the premisses of the original argument, followed by its conclusion. Note that the statement of the conclusion here is not a part of the formal proof itself but an informal reminder of the goal of the proof. It also serves to separate the premisses from the rest of the proof. Each of the following numbered steps is a valid conclusion that follows from one or more of the preceding numbered premisses and steps by an elementary valid argument. The notation on the right constitutes the justification for the step. Thus step 5, "A C," is a valid conclusion from premisses 1 and 2 by an elementary valid argument that is a substitution instance of the form called the hypothetical syllogism (abbreviated H.S.). Step 6, "~A," is a valid conclusion from premiss 5 and step 3 by an elementary valid argument that is a substitution instance of the form called modus ponens (M.P.). And finally, step 7, "D," which is the conclusion of the original argument, is a valid conclusion from premiss 4 and step 6 by an elementary valid argument that is a substitution instance of the form called the disjunctive syllogism. Step 7, in other words, shows that "D" follows from the original premisses, and that the argument is valid.

Click here for a step-by-step explanation of this proof. [[Blackboard Demo 9.1.1]]

Click here for a demonstration of a formal proof of an argument that involves substituting compound propositions for statement variables. [[Blackboard Demo 9.1.2]]

Elementary valid argument forms like modus ponens (M.P.), the hypothetical syllogism (H.S.), and the disjunctive syllogism (D.S.) constitute rules of inference in accordance with which conclusions are validly inferred or deduced from premisses. There are nine such rules—summarized in the following table—corresponding to elementary argument forms whose validity is easily established by truth tables. With their aid, formal proofs of validity can be constructed for a wide range of more complicated arguments.

Summary Table

Rules of Inference: Elementary Valid Argument Forms

Name Abbreviation Form
Modus Ponens M.P. p q


\ q

Modus Tollens M.T. p q


\ ~p

Hypothetical Syllogism H.S. p q

q r

\ p r

Disjunctive Syllogism D.S. p v q


\ q

Constructive Dilemma C.D. (p q) · (r s)

p v r

\ q v s

Absorption Abs. p q

\ p (p · q)

Simplification Simp. p · q

\ p

Conjunction Conj. p


\ p · q

Addition Add. p

\ p v q

[[Try It 9.1]]

9.2 The Rule of Replacement

There are many valid truth-functional arguments whose validity cannot be proved using only the nine rules of inference given thus far. We may accept, therefore, as an additional principle of inference the rule of replacement, which permits us to infer from any statement the result of replacing any component of that statement by any other statement logically equivalent to the component replaced.

For example, the principle of double negation (D.N.) asserts that p is logically equivalent to ~ ~ p. This principle allows us to infer from the statement ~ ~ (A v B) that the statement A v B has the same truth value. And from A v B we can deduce A v ~ ~ B.




[[Example 9.2.1]]

Thus to our arsenal of rules of inference we can add ten rules of replacement, all of which, like double negation, are tautologous, or logically true biconditionals.

Summary Table

Rules of Inference: Logically Equivalent Expressions



Name Abbreviation Form
De Morgan’s Theorems De M. ~(p · q) [T] (~p v ~q)

~(p v q) [T] (~p · ~q)

Commutation Com. (p v q) [T] (q v p)

(p · q) [T] (q · p)

Association Assoc. [p v (q v r)] [T] [(p v q) v r]

[p · (q · r)] [T] [(p · q) · r]

Distribution Dist. [p · (q v r)] [T] [(p · q) v (p · r)]

[p v (q · r)] [T] [(p v q) · (p v r)]

Double negation D.N. p [T] ~ ~p
Transposition Trans. (p q) [T] (~q ~p)
Material implication Impl. (p q) [T] (~p v q)
Material equivalence Equiv. (p q) [T] (p q) · (q p)

(p q) [T] [(p · q) v (~p · ~q)]

Exportation Exp. [(p · q) r] [T] [(p (q r)]
Tautology Taut. p [T] (p v p)

p [T] (p · p)

Keep in mind that the replacement of statements by logically equivalent alternatives is different from the substitution of statements for statement variables. In moving from a statement form to a substitution instance of it or from an argument form to a substitution instance of it, we can substitute any statement for any statement variable, provided that if a statement is substituted for one occurrence of a statement variable it must be substituted for every other occurrence of that statement variable. But we can replace a statement with a logically equivalent alternative without having to replace any other occurrence of it. We do not change the truth value of a larger expression if we replace a part of it with a logically equivalent alternative.

In addition, the nine rules of inference by the substitution of arguments for valid argument forms apply only to whole lines of a proof. The statement A can be inferred from A · B by simplification only if A · B constitutes a whole line, not if it is part of a larger expression. In contrast, an expression can be replaced by a logically equivalent alternative—P for ~ ~P, for example—wherever it occurs.

Our system of deduction now encompasses 19 rules. These 19 rules are partially redundant in the sense that they do not constitute a bare minimum of rules that would suffice for the construction of formal proofs of validity. Some rules could be dropped from the system without reducing the deductive strength of our formal system. The present list of 19 rules of inference, however, constitutes a complete system of truth-functional logic in the sense that it permits the construction of a formal proof of validity for any valid truth-functional argument.

The notion of a formal proof is an effective notion, which means that it can be decided mechanically, in a finite number of steps, whether or not a given sequence of statements constitutes a formal proof or not. Only two things are required: First, there must be the ability to see that a statement occurring in one place is precisely the same as a statement occurring in another. Second, there must be the ability to see whether a given statement has a certain pattern or not; that is, to see if it is a substitution instance of a given statement form.

Although a formal proof of validity is effective in the sense that it can be mechanically decided of any given sequence whether it is a proof, constructing a formal proof is not an effective procedure. In this respect formal proofs differ from truth tables. The making of truth tables is completely mechanical: Given any truth functional argument we can always construct a truth table to test its validity by following simple rules of procedure. But we have no effective or mechanical rules for the construction of formal proofs. Here we must think or "figure out" where to begin and how to proceed.

There are, however, some rough and ready rules of thumb that can help. First, simply begin deducing conclusions from the given premisses even if you do not clearly see where the proof is going. As you generate more and more subconclusions the chances increase that you will see how to reach the conclusion. A second is to introduce by the rule of addition any statement that occurs in the conclusion but in none of the premisses, and similarly to eliminate (by any of a variety of methods) any statement that occurs in the premisses but not in the conclusion. A third method, often very productive, is to work backward from the conclusion by looking for some statement or statements from which it can be deduced. Then one can work further backwards by trying to deduce those intermediate statements from the premisses. There is, however, no substitute for practice as a method of acquiring facility in the construction of formal proofs.



9.3 Proof of Invalidity

For an invalid argument there is, of course, no formal proof of validity. But if we fail to discover a formal proof of validity for an argument, this failure does not prove the argument to be invalid or that no such proof can be constructed. It may only mean that we have not tried hard enough.

A truth table can conclusively prove an argument invalid if it has at least one row with Ts under all the premisses and an F under the conclusion. But as already noted, a truth table for an argument form with many variables will be cumbersomely large.

We can, however, prove an argument invalid without constructing a complete truth table if we can assign values to its component propositions that make the conclusion false and the premisses true. This is equivalent to constructing one row of the argument’s truth table. And because an argument is proved invalid by displaying at least one row of its truth table in which all its premisses are true and its conclusion false, it suffices as a proof of invalidity.


There is no mechanical method of producing the right assignments of truth values to show that the conclusion can be false and all premisses true. A certain amount of trial and error is often inevitable. Even so, this method of proving invalidity is almost always shorter and easier than writing out a complete truth table.

Click here for a demonstration of how to construct a proof of invalidity.


9.4 Inconsistency

Consider the following argument:

I will pass the class and I will not pass the class.

Therefore I am the greatest student who has ever lived.

This argument is certainly silly, but when we consider its formal structure we find that it is, in fact, valid. The argument can be symbolized as follows:

P ~P

\ G

The premiss is inconsistent. Because P can only be true or false, the conjunction P · ~P is self-contradictory and must be false. This means that it is impossible to find a truth value assignment that makes the premiss of this argument true and the conclusion false at the same time. The argument is therefore valid, which a formal proof confirms.

Note that although this argument, and any argument with inconsistent premisses, is valid, it cannot possibly be sound because its premisses must always be false. No conclusion can be established to be true by an argument with inconsistent premisses, because its premisses cannot possibly all be true themselves.

The consequence of inconsistency is closely related to the so-called paradoxes of material implication—that if a statement is false then it materially implies any statement whatever. Similarly any argument with inconsistent premisses is valid regardless of its conclusion. In other words, any statement whatever can be validly inferred from an inconsistent set of propositions. This result helps explain why consistency is so highly prized.