Noah (angelbob) wrote,

Beware: Proof Ahead

A thought-provoking post by internet_addict got me onto a different topic. I was taking a Boolean logic class back in college. We had a little logical solver, and we'd tell it what transformations to apply in what order to get from the givens to the result. It was nifty. One of the ones I had trouble with was to prove that given inconsistent premises, you can prove anything. In other words, if your given propositions contradict, there is *nothing* you can't prove. To put it in formal terms:

Given: P && ^P (that means: P and not P)
Prove: Q (any unrelated assumption)

And you can do that, knowing nothing about Q. Here's how:

Q || ^Q (Tautology -- every proposition must be either true or false)
^Q => P (Tautology -- if P is true then anything implies P, by definition of logical "implies")
^P => ^^Q (Contrapositive of the previous -- if ^Q implies P then ^P implies ^^Q)
^P => Q (not not Q is the same as Q)

You know that ^P is true from the given: (P && ^P).
So, from only (P && ^P) you have proven the unrelated proposition Q.

It's easier if you do a proof by negation, of course. But we were explicitly not allowed to do that on this problem, since it'd make it trivial.
  • Post a new comment


    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.