Sample Proofs in QL

  Let's begin by proving a syllogism that we know to be valid, the AAA-1 syllogism:

All M are P
All S are M
All S are P


  which we translate into QL as:

(x)(Mx Px)
(x)(Sx Mx)
(x)(Sx Px)

Our proof begins with the premises of this argument.  Our conclusion is a universally quantified wff. So we know that we will need to use Universal Generalization, and that means we will need a flagged subproof. Let's look at the proof:

1. (x)(Mx Px) premise  
2. (x)(Sx Mx) premise  
3. flag a flagging assumption, UG SP1
4. Ma Pa UI, 1 SP1
5. Sa Ma UI, 2 SP1
6. Sa Pa H.S., 4, 5 SP1
7. (x)(Sx Px) UG, 3-6  

Notice that we began with the subproof for UI. If we had instantiated our premises without introducing our flagging assumption, we would not have been able to use any of the derived lines in our quest to universally generalize. Once we made the assumption, however, we could instantiate the universally generalized premises without any restrictions, and then it was a simple matter of using H.S. in order to get our instantiated wff in the formed needed for universal generalization.

If you think you could use H.S. directly from lines 1 and 2, you'd be mistaken. To use H.S., you need two conditionals, where the consequent of one is the antecedent of the other. But you don't have conditionals on lines 1 and 2. You have universally quantified wffs.

Now let's look at a proof of a QL argument which is not a syllogism:

 

(x)(Fx Gx)
(x)Fx
(x)Gx

Notice that one premise is universally quantified, and one is existentially quantified. Our conclusion is an existential generalization. If we can infer "Ga", we can use existential generalization to infer the conclusion. The key question is this: Which premise should we instantiate first? If we instantiate line 1 first, then our flagging restriction for E.I. says that we have to instantiate the second premise with a new constant. So it's better to instantiate the second premise first, and that way we have only one constant to deal with.

1. (x)(Fx Gx) premise  
2. (x)Fx premise  
3. Fa E.I., 2, flag "a"  
4. Fa Ga U.I., 1  
5. Ga M.P., 3,4  
6. (∃x)Gx E.G., 5  

Remember that there is no "flagged subproof" when we use E.I. Using E.I. does involve flagging the constant we use for the instantiation, but it isn't a subproof. We simply make sure we use a constant that is new to the proof. 

You should begin to notice a pattern in the proof structure. When our proofs involve quantified propositions, we generally start our proofs by using instantiation rules, and when our conclusions are universally quantified, we end with generalization rules.

Here's another example:

~(x)(Rx & ~Tx)
(x)(Lx ~Tx)
(x)(Lx  ~Rx)

And our proof:

1. ~(x)(Rx & ~Tx) premise  
2. (x)(Lx ~Tx) premise  
3. flag a flagging assump. UG SP1
4. (x)(Rx Tx) C.Q.N.R., 1 SP1
5. La assump., CP SP1, SP2
6. La ~Ta U.I., 2 SP1, SP2
7. ~Ta M.P. 5, 6 SP1, SP2
8. Ra Ta U.I., 4 SP1, SP2
9. ~Ra M.T., 7, 8 SP1, SP2
10. La ~Ra CP, 5-9 SP1
11. (x)(Lx ~Rx) U.G. 3-10  

To reach our universally quantified conclusion, we needed a flagged subproof. But we also have a few new features in this proof, not in our first examples. Our first premise is the negation of a categorical proposition, so we used our negation rule to turn it into a categorical proposition. Then we used Conditional Proof and assumed the antecendent of the instantatied conditional we wanted to infer. We derived the consequent, and then used universal generalization. This involved nesting the conditional proof subproof within the flagged subproof. This isn't difficult, but it does require accurate justifications. Make sure you write down your justifications and your subproof notations carefully!

One more, and then you'll be off on your own proofs:

(x)(Lx (Gx v Rx))
(x)(Lx & Tx)
(x)(Tx ~Gx)
(x)Rx

Our conclusion is a simple existentially quantified wff. So we need to infer "Ra" and then use existential generalization. Here again we must take care with the order of our instantiations of the premises. Since our second premise is an existential generalization, it will have to be flagged. So we want to instantiate it first. And the proof:

1. (x)(Lx (Gx v Rx)) premise  
2. (x)(Lx & Tx) premise  
3. (x)(Tx ~Gx) premise  
4. La & Ta E.I., 2, flag "a"  
5. La (Ga v Ra) U.I., 1  
6. Ta ~Ga U.I. 3  
7. ((La (Ga v Ra)) & (Ga v Ra) La) B.E.,5  
8. ((La (Ga v Ra)) Simp., 7  
9. La Simp. 4  
10. (Ga v Ra) M.P., 8,9  
11. Ta Simp., 4  
12. ~Ga M.P., 6, 11  
13. Ra D.S., 10,12  
14. (x)Rx E.G., 13  

There are no new innovations in this proof, just the straightforward application of many of our rules.

Exercises: Easy Proofs in QL and  Harder proofs in QL and Proving Theorems in QL.

back forward
table of contents   List of Exercises