The Structure of a Natural Deduction Proof

Subsection 3.5.2 The Structure of a Natural Deduction Proof

In the last section, we experimented with our reasoning rules and produced what we can call “one-step proofs”. Now we want to see how to construct multiple-step proofs that may exploit many premises, as well as several identities and inference rules.

Our proofs will be composed of a sequence of lines. Each line consists of four elements:

[line-number] statement Rule/Premise [referenced line number(s)]

The sequence of lines obeys the following rules:

The line numbers start at 1 and proceed sequentially.
Each statement is something that we know (at that point in the proof) to be true. So it must be either a premise (including possibly a conditional one) or something that we have just shown to follow from preceding lines of the proof.
The third entry in each line justifies the statement on that line. It can simply say, “Premise”. Or it can be any of the identities or inference rules we have presented. Or it can be a theorem that we’ve previously proved.
Whenever we use an identity, inference rule or theorem, we must specify the statement(s) to which that identity/rule/theorem applied. So, on any line that doesn’t correspond to a premise, we list those earlier line numbers.

Here’s a simple example that illustrates the format of a proof that relies on two premises:

[1] A  T Premise

[2] A Premise

[3] T Modus Ponens [1], [2]

Of course, what we want to learn how to do is to construct less trivial proofs (we hope of interesting things).

So, to review: To prove a conclusion C , we must:

Choose an appropriate set of premises.
Apply our identities and inference rules, starting with one or more of the premises to derive C .

By the way, sometimes when people write proofs, they like to make it clear that they’ve really done it. The conclusion has been proved. So they may add one last line to their proof:

Q. E. D.

Q.E.D. is an abbreviation for the Latin expression quod erat demonstrandum , which means, “that which was to be proved.” You can use it if you like.

English Aside

Q.E.D. is now sometimes used in regular English to mean something like, “And so there. End of discussion. I’ve proved it. I’m right.” And it’s been translated into a lot of other languages.