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:
  • AND introduction, AND elimination (BORING!)
  • OR introduction, OR elimination (MORE BORING!)
  • BOTTOM elimination (from absurdity, we can get anything, also known as the principal of EXPLOSION)



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:
  • You are wearing a cravat.
  • You are not wearing a cravat.


If we say that both of these statements are true or provable in our world, obviously, we have a contradiction. We can derive absurdity.

Clearly, from AND elimination, we know you are wearing a cravat.


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.
  • Negation Elimination: (Super easy! If you get P and NOT P, you've got absurdity!)
  • Negation Introduction: If you start with P, and get to BOTTOM, you've shown NOT P.

A quick note about this: it shouldn't be super surprising! It's really just an application of the implication introduction rule! (Why?)
  • Proof by contradiction: Assuming not P, show absurdity, thus we have P.


Alright. So, we've talked about the classical Natural deduction system. If you get rid of proof by contradiction, you're in the intuitionistic system. If you get rid of BOTTOM elimination AND proof by contradiction, it's minimal logic.

Honestly, this is not super important. Going forward, you're going to be using classical natural deduction. It's really only going to be for this homework (and maybe the tests...) that the difference is important.



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)

Allons-y! Back to CIS160 Page