First thing: if you're reading through the notes, you probably want to skip the
stuff about Gentzen proof systems (40-48) unless you're already comfortable with the way we're
doing stuff! The Gentzen system is essentially just a different way of writing the
rules and proof trees that we've been talking about, and it's not worth getting
confused over. If you're super comfortable with the material, though, go ahead and read it,
it's interesting and maybe you like it better!
Alright. So in class this week (and a little bit at the end of last week) we've
been talking about adding the rules for AND, OR, and NOT. Hopefully these rules do not seem too spooky!
Remember, we're still doing proofs and things just like we were before: at each step, apply
one of the rules you know about to get to the previous step, and then make sure you discharge
all your assumptions at the steps where it's allowed to discharge!
So, the rules that we've added to our tool box are:
This should be the first one that maybe has you scratching your head. "Why, Alex," you might ask, "does deriving a contradiction from your assumptions allow you to derive absolutely anything?" I would respond, "Why, Mr. Darcy, it is quite simple!" Consider the set of inconsistent statements:
|Now, assume for a moment that the Great Pumpkin does NOT exist. Using the negation elimination rule, we can say The Great Pumpkin does NOT exist IMPLIES BOTTOM This is the same as NOT(The Great pumpkin does NOT exist). Using double negation elimination, The Great Pumpkin Exists, And discharging our initial assumption, If you are Wearing a cravat AND you are not wearing a cravat, Then the Great Pumpkin exists. Which is, of course, absurd. (Sorry, Linus.)|
Alright, back to rules.
Now skip a bunch more pages (60-62) and get to the next important idea: logical equivalence. Two statements are equivalent P = Q, means you can show (P ⇒ Q) AND (Q ⇒ P)