Send via SMS

⊙ AntiQuark

Truth, Beauty, Charm, Strange


Probability & DeMorgan's

In my previous post, a reformed cow orker dared me to prove DeMorgans for ternary (three-valued) logic. Well, I'll one-up that, MacKenzie (if that's your real name)... how 'bout I prove DM for a form of logic that has an infinite number of shades of truth?

I'm referring to the logic of probability theory.

Remember that the probabilities of events in combination can be explained by the following three equations:

First, the probability of observing a AND b happen simultaneously is given by

P(a ^ b) = P(a)P(b).

Second, the probability of observing either a OR b, is

P(a v b) = P(a) + P(b) - P(a)P(b).

Third, the probability of NOT observing a happen is

P(~a) = 1 - P(a).

An interesting fact is that if you restrict your probability values to 0 (certainty that an event is impossible) and 1 (certainty that an event will happen) then the rules above become identical to the AND, OR and NOT operations of propositional logic. And, like propositional logic, the laws of probability have their own DeMorgan's laws:

P(~(a ^ b)) = P(~a v ~b)

P(~(a v b)) = P(~a ^ ~b).

Proving these laws is simple, you just plug in the equations. (For clarity, let A = P(a) and B = P(b).)

First, evaluate the probability P(~(a ^ b)):

= 1 - P(a ^ b)
= 1 - AB

Next, determine the probability P(~a v ~b):

= P((1 - A) v (1 - B))
= (1 - A) + (1 - B) - (1 - A)(1 - B)
= 1 - A + 1 - B - (1 - A - B + AB)
= 1 - A + 1 - B - 1 + A + B - AB
= 1 - AB

See, they're equal! Therefore P(~(a ^ b)) = P(~a v ~b). (The dual statement, P(~(a v b)) = P(~a ^ ~b) can proven similarly.)

QED, etc. Oh yeah, I almost forgot... TAKE THAT, MacKENZIE!


  • At 2/04/2006 2:15 AM, burton mackenzie said…

    Well played, Sir. :-)

  • At 2/15/2006 3:49 AM, Anonymous said…

    Nice, but you could do even better. Why not try it in an ortholattice?

  • At 2/15/2006 9:35 AM, Derek said…

    Piece of cake! Now I just have to figure out what the hell an ortholattice is...

  • At 2/16/2006 11:47 AM, Derek said…

    Hmmm, is that a trick question? It seems that most references define an ortholattice with DeMorgan's as one of the laws, not a theorem.

  • At 2/24/2006 2:20 PM, Tobe said…

    Hmm. I guess it's not fun to prove it if it's part of your axiomatization. Let me try again (and say more).

    In the link I gave above, if you click on "Ortholattices" in the table of contents, there is an axiomatization that doesn't include De Morgan's laws, and an unproven theorem stating that the fourth axiom is equivalent to De Morgan's laws in the presence of the other axioms. The suggestion was supposed to be to try proving that theorem (if it seems interesting).

    There's an intriguing quote at the top of that page which made me think you could be interested in this:

    "Quantum theory is simply the replacement in standard probability theory of event-as-subset-of-a-set (abelian, distributive) by event-as-subspace-of-a-Hilbert-space (non-abelian, non-distributive)"

    Logics of ortholattices and similar beasties are supposed to have a relation to quantum mechanics analogous to that of the logic of probability to probability. So having De Morgan's laws for ortholattices means that they turn up (in a sense) in quantum mechanics, even though probabilities there don't behave classically.

    P.S. The beginning all this quantum logic stuff was Von Neumann and Birkhoff's 1936 paper "The Logic of Quantum Mechanics".

  • At 2/26/2006 1:38 PM, Derek said…

    I looked at it, thought I might give it a try, but I was unsure how to handle the "<<" and ">>" operators.

    Can those operators be replaced with a combination of "^", "v" and "~" operations?

    There are a few explanations of "<<" and ">>" in the same page, but I'm not sure which one applies.

  • At 3/01/2006 1:54 AM, Tobe said…

    Syntactically, they work the same as in boolean logic.

    A << B if and only if A v B = B.

    The poset and lattice definitions are the same as the one above, once you figure out how to interpret "v" in these settings.

    In case it helps, one concrete example of an ortholattice is this:

    Fix a finite dimensional vector space. Call it "the universal vector space". Suppose it has an inner product (so we can say what it means for vectors to be orthogonal to one another).

    Variables stand for vector subspaces of the universal vector space.
    ^ means intersection
    v means span of union
    ~ means orthogonal complement.
    A << B means "A is a vector subspace of B".

  • At 3/09/2006 9:13 PM, Derek said…

    I gave it a quick try, bit I didn't get anywhere. The equalities are giving my problems.


Post a Comment

<< Home