Constructing Direct Proofs of Validity in Sentence Logic

In a proof of validity, one is to attempt to derive the conclusion through the premises. Putting it a little more simply, one is to attempt to determine how the conclusion comes "out of" the premises. In a deductively valid argument, the conclusion is contained in the premises, and the truth of this claim is seen clearly in the fact that the conclusion is DERIVED from the premises either through a combination of the use of the rules of inference and replacement, or the use of one set or another. The simple problems at the beginning of Chapter 4 in both the study guide and the text contain problems that deal with only the first 8 rules of inference (10, if you consider Destructive Dilemma and Absorption). The remaining problems, however, deal with all of the valid implicational and equivalence forms. Thus, the best way to proceed is to begin with the justifications (whether using 8 or all 18 rules) and determine not only WHAT has been done in the course of the proof, but also WHY the proof was constructed in that way. Approaching the "justification" problems in this way not only helps in being able to use the rules more efficiently, it also makes clear (in most cases) why someone would want to use a specific rule in some specific part of the proof.

Once the justification problems have been completed, then move to the first 5 or 6 proofs at the beginning of each section in which the proof must be constructed from the premises. The first 5 or 6 problems are normally much simpler than those remaining. Once one becomes reasonably proficient in the workings of the simpler proofs, then move to the more complicated ones (e.g., 6-10 in any section). (Below are some general guidelines for the construction of proofs).

General Guidelines for Constructing a Formal Proof of Validity

Remember that no one can teach you how to do any specific proof. You can be shown how they work. But it is not possible, I think, to teach anyone how any individual proof is to be done. First, there is the matter of knowing the rules of inference. Second, there is the matter of gaining a working knowledge of the relationship of the rules of inference to the arguments to which they are applied. Someone who teaches logic can teach you, then, how to approach proofs, how to develop strategies for working them out, and how to do all proofs generally. But the ability to do every and any proof will come from within yourself. It is rare that such an ability develops, however, without a little help in some form or other. And that "help" is what I am now providing to you.

1. Keep in mind the content of the conclusion. Remember that the idea is to derive the conclusion from the premises. Some of the ways in which to do this are to consider what type of statement the conclusion is. If the conclusion is a conjunction, it may be possible to complete the proof by determining if deriving only one half of the conclusion (one conjunct) is possible. Then, the rest of the proof can be done by attempting to determine the other conjunct - which finally leads to the use of conjunction at the end of the proof. If the conclusion is a disjunction, it may be possible to derive only one disjunct, and then add the remaining disjunct through the use of the rule addition - which very literally allows the addition of anything at all. If the conclusion is an equivalence, consider the various ways in which equivalences are stated (using the corresponding rule of replacement by that name). If the conclusion is an implication, in many cases, the rule that will be used will be either hypothetical syllogism or material implication. Remember also that in a conclusion that is a disjunction, do not rule out the possibility of using constructive dilemma. (These, again, are only general ideas to keep in mind - they DO NOT always work, nor can you count on them on a regular basis). Finally, if the conclusion is a single term (either negated or non-negated), in many cases, the solution to the proof will come through MP, MT, DS, Taut, or Simp (generally in that order of common occurrence).

2. If you do not "see" the solution to the proof through a consideration of the way in which the conclusion appears, then attempt simply to apply one line to another (i.e., try to apply one premise or a newly constructed line to one that already exists using the rules of inference). It will, in many cases, be the case that the line constructed last will be the next one used in the derivation of the conclusion.

3. If it is not possible to apply one line to another using the rules of inference, then try to alter an existing line so that one of the rules of inference CAN be applied in the use of one or more lines of the proof. The alteration of a line is normally achieved through one of the rules of equivalence, simplification, addition, or absorption.

The ability to construct a proof of validity depends, largely, on your ability to be creative and to see similarities between premises and newly constructed lines in a proof. But this 'creative ability' normally does not come through a revelation, so to speak, but through almost incessant practice. REMEMBER THAT YOU CANNOT HOPE TO DO WELL WITH PROOFS UNTIL YOU ARE ABLE TO RECOGNIZE EVERY ONE OF THE RULES OF INFERENCE AND REPLACEMENT. THE WAY TO DO THIS IS GENERALLY NOT THROUGH ROTE MEMORIZATION, BUT THROUGH USING THE RULES ON "JUSTIFICATION" PROBLEMS APPEARING AT THE BEGINNING OF EACH NEW SECTION INTRODUCED IN THE TEXT.

Below is a completed proof of validity using only the equivalence rules. A discussion of the procedure of the proof follows its presentation:

Consider this proof of validity:

1. -C ---> (D v -W)/ W ---> (D v C)

2. C v (D v -W) 1, impl.

3. (C v D) v -W 2, assoc

4. (D v C) v -W 3, com

5. -(D v C) ---> -W 4, impl

6. W ---> (D v C) 5, contrap.

One should attempt to try to 'figure out' how and why the proof is done in the way in which it is done. First, the order of atomic sentences in the conclusion is WDC, but the order of them in the premise is CDW. Thus, one ought to try to get them all in the same order within the lines of the proof that will be constructed based on that single premise. But one should also note that DC 'go together' in the conclusion, i.e., they are together in a set of parentheses. So, try to put them together in a set of parentheses in a line you will construct using ASSOCIATION. But association cannot be used until all the connectives that are in the statement are all the same -- i.e., they need all to be either conjunctions or disjunctions. Since there is already a disjunction in the first line of the proof (the premise), change the implication in line 1 (using MATERIAL IMPLICATION) to a disjunction. Once it is changed to a disjunction, then, on line 3, ASSOCIATION can be used in order to put the D and the C together within the parentheses. But in the conclusion, DC are in the order D v C, but in line 3, they are in the order 'CD'. Thus, the rule of equivalence that allows one to change the order of atomic sentences within a compound statement is COMMUTATION, and it should be used here. Line 4 then becomes (D v C) v -W. The conclusion is almost derived. When you look at the conclusion, the order of presentation of atomic sentences is WDC. Line four has DC-W. But it can also be seen that the conclusion is a conditional sentence (major connective). Of course, CONTRAPOSITION allows any implication to be reversed, with the corresponding antecedent and consequent obtaining negations. But since the line is not an implication, but MATERIAL IMPLICATION allows the transformation of a disjunction into a conditional, use material implication on the line to derive -(D v C) ---> -W. Then, line 6 becomes W --> (D v C) through the use of CONTRAPOSITION. The last line of the proof is now identical with the statement of the conclusion. Assuming that every rule of replacement was used properly, this proves that the argument is valid.

One further consideration:

Remember that the rules of replacement (equivalence) are used either on entire lines of a proof, or only on part of a line (as in clear in line 4 above). This is not the case for the rules of inference, however, which apply to entire lines of proofs. To make this clear, it is possible in (D v C) v -W to alter the appearance of (D v C) without 'bothering' the -W. But if, using the same statement, one wanted to use DISJUNCTIVE SYLLOGISM, the entire line must be considered. Thus, from the statement, one cannot derive C from -D when (D v C) is connected to -W as a disjunction. But it is possible to derive (D v C) itself when one already has an existing W on some other line of the proof (or can derive one from other lines). At that point, it would then be possible to derive C (assuming that -D already exists or can be derived from some other line or lines of the proof).

An Extra Proof Explanation:

When constructing a formal proof, it may occur that by simply glancing at the premises, the procedures to follow in justifying lines is clear. But, it is not always the case that it is this simple. Sometimes it will not be apparent just exactly what should be done. When this happens, it might be helpful to consider the different ways in which the conclusion, in its present formulation, may be stated. For example, the argument:

R v (S . -T)

(R v S) --> (U v -T)/ T --> U

may not appear, at first glance, in such a way as to indicate what operations should be performed on the premises to obtain the exact statement of the conclusion.

To make the procedure more apparent, consider the possible ways in which the conclusion may be alternately stated:

T --> (T . U), by absorption

-T v U, by material implication

-U v -T by transposition (contraposition)

If you can see that, in premise 2, the consequent of the conditional contains a statement very similar to -T v U, the possible formulation of T --> U, then you can see that by using commutation on U v -T, you would obtain -T v U, which would then yield T --> U. But there is still more to do. It is necessary to obtain U v -T alone. The most readily noticeable procedure by which to do this is Modus Ponens. But now your problem is to get R v S alone in order to apply it to the second premise. You can do this by using distribution on premise 1, thus obtaining (R v S) . (R v -T). Now, you can take R v S out by simplification, apply it to premise 2, and obtain U v -T. Now all you have to do is commute U v -T and make it -T v U, then apply material implication, thus obtaining the conclusion, T --> U. You ought to follow each of these steps to see how the proof is constructed.

The main thing to remember when working out these problems is to try to think ahead (if you can). Try to decide how the premises are related to the conclusion and how various transformations may be done on specific lines to yield the conclusion, and how one line may be applied to another to obtain a needed line.

There is no straightforward rule for constructing formal proofs. Most of the time it is simply by trial and error until you become skilled at noticing the various applications of the rules of inference immediately .. and sometimes even then trial and error is the only way to start. Once a proof is started, and once you obtain at least a vague idea of what you may do to the various lines in the proof, you are well on the way to finding the solution.

Based on the examples and explanations above, I think it might be fair to say that there are several general rules that you can follow in attempting to construct a formal proof of validity (direct proofs only).

1. Restate the conclusion if it is an implication. That is, write it out somewhere off to the side of the argument as an implication and as a contrapositive. If the conclusion is a conjunction, remember that you may be able to derive it by deriving both of the conjuncts singly. If the conclusion is a disjunction, you can write it out as an implication, then as a contrapositive, etc. If the conclusion is an equivalence, think of the two ways in which equivalences are stated. Write them off to the side of the proof and see if there is anything in the premises that can be altered or derived to formulate the re-written conclusion. If the conclusion is a single, atomic sentence, it won't do you any good to re-write it, since there are very few ways to do so. Just try to find the sentence in the premises.

2. After you have taken the time to rewrite the conclusion, think ahead (or back, from the rules of inference) to the type of rule that might derive that conclusion. If the conclusion is a single atomic sentence, it might be good to think first of MP and MT, though this is not always the case. If the conclusion is an implication, you might want to see if there are at least a few hypothetical propositions in the premises. If there are, it will probably come through hypothetical syllogism. If the conclusion is a disjunction, you might think of deriving one disjunct, and then consider adding the other one to it at the end of the proof. Or, you might want to see if there are enough premises in the argument that would warrant using constructive dilemma. If the conclusion is an equivalence, it will almost always be the case that the conclusion will be derived from the use of the rule, material equivalence, but it is by no means always the case.

3. When all else fails (and sometimes it is simply better to start a proof this way, anyway), look at the premises and find out if there are any lines that apply directly to each other. If there are, determine the rule of inference to use and DO IT. This will usually lead you somewhere that you want to go (to the answer). And it will usually be the case that the last line you constructed will be the next one you will use.

4. If you can't find a line to apply to some other, then consider altering a line. That is, if you have a premise that is a conjunction, simplify it. If you have a premise that has a negation on the outside of a set of parentheses, figure out a way to use DeM on it. That will usually give you something useful. And if you have a premise that is an implication, use material implication on it. It will probably alter it enough to show you a rule like MP or MT. In other words, it may be the case (and it often is the case) that altering a line will allow you to use step 3 above.

5. Don't forget to stop when you have derived the conclusion. Sometimes people get 'carried away' and keep on going even after they are actually done with the proof!

Again, NO ONE CAN TEACH YOU HOW TO DO EVERY PROOF, BUT YOU CAN BE TAUGHT HOW TO DO PROOFS IN GENERAL, THE GENERAL RULES INVOLVED IN THE CONSTRUCTION OF A PROOF, HOW TO START (THAT IS THE MOST DIFFICULT STEP); AND IF YOU KNOW THE RULES OF INFERENCE AND REPLACEMENT, you will probably be pretty good at proofs. You will probably not be "good" at them in a day, or maybe even in a week. But sooner or later (with a little luck and some work) all of it falls together and you WILL be able to do them. Be patient.