Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 3.7.1 Introduction

The proofs that we’ve done so far are syntactic objects. We write down a set of premises. Then we do symbol manipulation. We’ve seen two ways to do that:

Getting at Truth – An Inference System that is Sound and Complete

The big deal though is that we want proofs to tell us something about truth . They can do that if we design our inference rules appropriately. To see how to do that, we need two definitions:

• We’ll say that an inference rule is sound if and only if, whenever it is applied to a set P of premises, any conclusion that it produces is entailed by P (i.e., it must be true whenever P is).

• A set of inference rules R is complete if and only if, given any set P of premises, all statements that are entailed by P can be proved by applying the rules in R .

If we can define a set of inference rules that is both sound and complete then the set of theorems that can be proved from P will exactly correspond to the set of statements that must be true whenever all the premises in P are true.

So do we have a set of sound and complete inference rules for Boolean logic? The answer is yes. Proof by truth table (all by itself) is both sound and complete (even if not convenient). Moving on to natural deduction: All our rules are sound. We know this because we’ve shown the truth tables that prove them to be so. (Thus it’s never possible to use one of them to derive a conclusion that doesn’t follow from the premises.) And, taken together, they are complete. (So it’s always possible, given a statement S that does in fact follow from our premises, to construct a proof of S using our rules.)

Big Idea

The Boolean logic inference engine that we have just studied is both sound and complete.

Completeness is important if we don’t want to be stuck, staring at something we know to be true, but unable to construct a proof.

Soundness is even more fundamental. If we admitted even a single unsound inference rule, proof would no longer tell us anything about truth (our ultimate goal in this whole endeavor). To see why that’s so, suppose that we added, say, this new rule:

Flimflam: p

∴ p ∧ q

Thus, from premise p conclude p and anything we want.

Recall that the Addition rule tells us that, from p , we can infer p ∨ q for any statement q . This new rule, Flimflam, lets us do a similar thing except that we can introduce and instead of just or .

Let’s see what we can do with it:

[1] Q Premise

[2] Q ∧ ¬ Q Flimflam [1]*

[3] F Computation [2]

* Note that Flimflam lets us conjoin Q with absolutely any statement. We happen to have picked the statement ¬ Q in order to get a very simple example of the damage that Flimflam has wrought.

So we see: Flimflam lets us derive False.

And we can keep going:

[4] The moon is made of green cheese. Contradictory Premises [2]

This is precisely the kind of flawed reasoning that sound rules will not let us do.

That we have a set of sound and complete inference rules is great news. Given any problem that we can represent in Boolean logic, we can, in principle, prove all and only the conclusions that follow from the premises that we choose.