Logic Chapter Fourteen
Next Chapter

Tautologies and Theorems

Tautologies (Or "Duh" sentences.)

A tautology is a sentence that can't be false, (which is good, I suppose) and which also can't tell you anything you couldn't have thought of for yourself, (which is kind of disappointing, when you think about it). For instance, "All bachelors are unmarried" is a tautology because, duh, if you know what "bachelor" means, you know, without ever having to look at a single one of them, that they're all unmarried. (Imagine you're at a party, and you find yourself sitting next to someone who says nothing but tautologies. Wouldn't that drive you insane?)

In this text, and in symbolic logic generally, the word "tautology" refers to symbolic sentence that can't be false. For instance and are both tautologies. (Think about it.)

So tautologies are sentences that can't be false. Think about it. Can you draw a picture that makes BaBa false? Or one which makes Fe(WoFe) false? Now think about making one of them the the conclusion of an argument. Could you draw a picture in which the premises were true and the conclusion was false? You can't, simply because you can't ever make that concluion false. So any argument that has a tautology as it's conclusion is automatically valid!



General Tautologies

Remember that we use "P" and "Q" to refer to any specific formula, so and also both tautologies and they say that any formula that has the same form will also be a tautology. That's why I call them "general tautologies." ("General Tautology! The enemy is attacking!" "Hmm, that means they are trying to harm us in some way." "Well, duh. Can't you think of anything useful?" "No, I'm General Tautology, remember? I can only tell you things you could figure out for yourself." "Oh $&*#!, did I join the wrong army!")

Contingency

Just in case you're interested, any statement that's not a tautology is called a "contingency." I could explain why, but I don't feel like it.

Theorems, Again (Sigh.)

Okay now, since general tautologies are always true, we can keep track of them as we prove them. We can give them numbers also. Once we've proved a general tautology, and given it a number we call it a "theorem." (Why do we do this? I'll, um, explain later.)


Proving Theorems

When we prove a theorem, we do it exactly the way we prove a one-line, no-premises argument, except that we use the sentence letters "P," "Q" and so on instead of meaningful terms.

I claim that PP and Q(PQ) are both tautologies, and can be made into theorems. Let's prove them.



Whoa! That was easy!



Okay, that was trickier. (Didn't I tell you rule R would come in handy?)

So now we have two theorems.


Now, here's that labor saving rule I mentioned.

Rule 16: Theorem (Thm <number of theorem>) 
If T is a theorem, containing sentence letters such as "P," "Q," "R" and so on, an "instance" of that theorem may be written in as a new line in which every "P" has been replaced by exactly the same sentence, every "Q" has been replaced by exactly the same sentence (which can be different from the sentence written in for every "P"), and so on.

Did you get the bit about an "instance?" An instance of a theorem is a sentence that's just like the theorem except that the P's and Q's have been replaced by what I'm calling "meaningful" sentences and terms. A meaningful sentence is any well-formed logical formula, like Ba, or Rs, or Hi ^ Gu, or Mu v No, or Iu Ge, or HeNi, or (Ja v Te) ^ (Wf [Ul Tm]).

So the following are all instances of Theorem 1, which is P P

BaBa
RsRs
(Hi ^ Gu)(Hi ^ Gu)
(Mu v No)(Mu v No)
(Iu Ge)(Iu Ge)
(HeNi)(HeNi)
{(Ja v Te) ^ (Wf [Ul Tm])}{(Ja v Te) ^ (Wf [Ul Tm])}

I hope you appreciate the way I used different types of brackets in the last one!

And these are all instances of Q (P Q)

Rs(BaRs)
(Mu v No)((Hi ^ Gu) (Mu v No)
(Iu Ge)((Mu v No)(Iu Ge))
Ba ({(Ja v Te) ^ (Wf [Ul Tm])}Ba )
{(Ja v Te) ^ (Wf [Ul Tm])}([HeNi]{(Ja v Te) ^ (Wf [Ul Tm])})

Confused? Try marking the main operator, and every other operator that appears in the theorem. Then highlight the formula that substitutes for P whenever it appears. Then highlight Q's substitute in a different color.

Here is Rs(BaRs) with the theorem's operators marked:


Rs ( Ba Rs )

Now, let's highlight all the Q's (remember, "Rs" is substituted for "Q" here).

Rs ( Ba Rs )

And we'll do all the P's in a different color

Rs ( Ba Rs )

Now, before you look at what I did with the other formulas, you should definitely go back and try it for yourself.

Seriously, go back and write out your own instances of each theorem.

Okay, here's what I came up with for the other instances of theorem 2, which is Q (P Q).

(Mu v No) ( (Hi ^ Gu) (Mu v No) )

(Iu Ge) ( (Mu v No) (Iu Ge) )

Ba ( {(Ja v Te) ^ (Wf [Ul Tm])} Ba )

{(Ja v Te) ^ (Wf [Ul Tm])} ( [HeNi] {(Ja v Te) ^ (Wf [Ul Tm])} )

Okay, now pick out the instances of theorem 1 (P P) from the things that are not instances of theorem 1.
1.
(Hi Gu)(Hi ^ Gu)
Instance Not Instance
2.
(Hi Gu)(Hi Gu)
Instance Not Instance
3.
(Mu ^ No)(Mu v No)
Instance Not Instance
4.
[Rs(BaRs)][Rs(BaRs)]
Instance Not Instance
5.
{(Mu v No)[(Hi ^ Gu) (Mu v No)]}{(Mu v No)[(Hi ^ Gu) (Mu v No)]}
Instance Not Instance
6.
BaRs
Instance Not Instance

How did you do? Does this theorem business make sense to you? (If it doesn't, can you at least tell instances from non-instances?)

Here are some more theorems.

Theorems 3 & 4 (Exportation Laws) 
3. [(P ^ Q) R] [P (QR)]
4. [(P ^ Q) R] [Q (PR)]

Notice that although these two theorems say almost the same thing, they are different theorems. An instance of theorem 3 is not an instance of theorem 4, and an instance of theorem 4 is not an instance of theorem 3.

And, just to be as clear as possible, while this sentence [P (QR)] [(P ^ Q) R] says almost exactly the same thing as theorem 3, it is not theorem 3 and no instance of this particular formula will ever be an instance of theorem 3.

What do theorems 3 and 4 mean? Well, remember that "" stands for "is logically equivalent to." Which is just another way of saying "is true in each and every circumstance that the following sentence is true." So theorem 3 says that "[(P ^ Q) R]" is logically equivalent to "[(P (QR)]," which just means that whenever "[(P ^ Q) R]" is true, "[(P (QR)]" will also be true, and vice versa, which, of course implies that whenever "[(P ^ Q) R]" is false, "[(P (QR)]" will also be false, and vice versa.

To put it another way, both sides of theorem 3 have the same truth table.



Hey, that's pretty cool! Did you notice that there's only one world-line where the two sides are false! That's the one where both P and Q are true, and R is false. (Well, I think that's cool.)

As a special treat I'm going to let you derive these theorems as part of your homework! (Just kidding.)

The key to deriving these theorems lies in using Conditional Proof over and over again to generate assumptions that can then be used to produce the necessary consequents. I suggest you try to prove the theorems on your own. They just might turn up on a test. If you get stuck, try looking through your notes for some arguments with a similar logical structure that can give you hints.

What the heck, give theorem 3 a go, and then check your answer below. Don't look down until you've tried it for youself.



So, how close were you? You were right on the money! That's great!

Notice that this proof says nothing at all about Theorem 4. Although these theorems 3 and 4 say almost the same thing, they are still different theorems. So a proof of theorem 3 is not a proof of theorem 4, and a proof of theorem 4 is not a proof of theorem 3.

For practice, derive theorem 4. [(P ^ Q) R] [Q (PR)].

This should be pretty easy, since the basic strategy I used for theorem 3 should work for theorem 4.

It is vitally important that you be able to tell things that are instances of theorems from formulas that are not instances of formulas, so go through the following formulas, circling instances of theorems, and crossing out formulas that are not instances of any theorem we've discussed so far. (Theorems we haven't discussed don't count.)

When you find something that is an instance of a theorem, mark it with the number of the theorem it is an instance of.



If you have time after distinguishing theorems from non-theorems and identifying specific theorem instances, try to derive some of the valid arguments mixed in among the following arguments, using THEOREMS whenever you can.

1. 2. 3. 4. 5.
6. 7. 8. 9. 10.
11. 12. 13. 14. 15.
16. 17. 18. 19. 20.

1. 2. 3. 4.
5. 6. 7. 8.
Copyright 2007 by Martin C. Young

Next Chapter

This Site is Proudly Hosted By:
WEBster Computing Services