Noah (angelbob) wrote,
Noah
angelbob

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.
Subscribe

  • Welp, that's it.

    The last person I knew on here is moving over to DreamWidth. When I load my friends list (without her) I literally get one private post from me and…

  • Moved all my RSS feeds over...

    It looks like DreamWidth also supports creating unlimited RSS feeds for various stuff... I've moved all mine over. Okay, *now* my friends list looks…

  • Setting up DreamWidth...

    I now have noahgibbs.dreamwidth.org. This same userid already belongs to somebody else who has no posts and doesn't otherwise resemble me. Still…

  • Post a new comment

    Error

    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.
  • 17 comments

  • Welp, that's it.

    The last person I knew on here is moving over to DreamWidth. When I load my friends list (without her) I literally get one private post from me and…

  • Moved all my RSS feeds over...

    It looks like DreamWidth also supports creating unlimited RSS feeds for various stuff... I've moved all mine over. Okay, *now* my friends list looks…

  • Setting up DreamWidth...

    I now have noahgibbs.dreamwidth.org. This same userid already belongs to somebody else who has no posts and doesn't otherwise resemble me. Still…