Loading ...
Sorry, an error occurred while loading the content.

Logic and Sets.

Expand Messages
  • paulmillscv@yahoo.co.uk
    Hello Chris, Thank you for your considerate comment. Your comment about the set not being the first or last word in mathematics is interesting. The set is
    Message 1 of 5 , Oct 31, 2001
    • 0 Attachment
      Hello Chris,
      Thank you for your considerate comment. Your comment about the set
      not being the first or last word in mathematics is interesting. The
      set is fruitful of course because it has the same algebra as a
      subset of logic, Boolean algebra. As maths is supposed to analyse
      the laws of human thought then a set will be a good starting point.
      However to reward the industry of the list in dwelling on the
      mysteries of the universe (only briefly I hope) I shall throw said
      cat amongst pigeons once more by sharing with you a secret and one of
      the best links on the web if you haven't seen it already.
      Did you know that De Morgan's laws cannot be proved using
      Boolean algebra? Incredible but true. De Morgan's laws have their
      origin in… human thought. J. To prove this, use the wonderful
      automatic deduction software `Son of Birdbrain' at this link.

      http://www-unix.mcs.anl.gov/AR/sobb/

      Set up a Boolean algebra as axioms and then click on the De Morgan's
      laws hypothesis. The computer cannot prove them with the Boolean
      algebra axioms, even though De Morgan's laws are usually described
      by Boolean algebra notation!

      Regards,
      Paul Mills
      England.
    • Juan Pedro Hecht
      ... Sorry, I disagree. Let: C[ ] be the complement of a set u the union n the intersection E belongs to Lets proof the first one: C[X u Y] C[ X] n
      Message 2 of 5 , Oct 31, 2001
      • 0 Attachment
        Paul wrote:

        >Did you know that De Morgan's laws cannot be proved using
        >Boolean algebra? Incredible but true.


        Sorry, I disagree.

        Let:
        C[ ] be the complement of a set
        u the union
        n the intersection
        E belongs to

        Lets proof the first one: C[X u Y] <---> C[ X] n C[Y] (the second law 's proof is similar)

        1. Supose that x E C[ X u Y] , then x [not E] (X u Y)
        2. Then x [not E] X and x [not E] Y
        3. Then x E C[X] and x E C[Y]
        4. Then x E (C[X] n C[Y]) (left to right part of the proof)
        5. Now supose that y E (C[X] n C[Y]) , then ( y E C[ X]) and (y E C[ Y])
        6. Then ( y [not E] X) and ( y [not E] Y)
        7. Then y [not E] ( X u Y)
        8. Then y E C[ X u Y] (right to left part od the proof) Q.E.D.

        Regards,

        Peter


        [Non-text portions of this message have been removed]
      • Phil Carmody
        ... Propositional calculus is complete. Every tautology has a proof. DeMorgan s laws are true by truth-table, therefore they re provable. ... You mean come up
        Message 3 of 5 , Oct 31, 2001
        • 0 Attachment
          On Wed, 31 October 2001, paulmillscv@... wrote:
          > Did you know that De Morgan's laws cannot be proved using
          > Boolean algebra? Incredible but true. De Morgan's laws have

          Propositional calculus is complete. Every tautology has a proof. DeMorgan's laws are true by truth-table, therefore they're provable.

          > their
          > origin in� human thought. J. To prove this, use the wonderful
          > automatic deduction software `Son of Birdbrain' at this link.
          >
          > http://www-unix.mcs.anl.gov/AR/sobb/
          >
          > Set up a Boolean algebra as axioms and then click on the De
          You mean come up with our own definition of the + and * operators? Well in that case of course Morgan's laws aren't necessarily going to hold.

          > Morgan's
          > laws hypothesis. The computer cannot prove them with the Boolean
          > algebra axioms, even though De Morgan's laws are usually described
          > by Boolean algebra notation!

          You didn't try hard enough. I can prove both of DeMorgan's laws with only 6 hypotheses. Hypotheses which are pretty fundamental to how one would define the operations of 'and' and 'or' from first principles. Unsurprisingly - if you set up the two operators to have just what's needed to look like 'and' and 'or', then you do end up with DeMorgan's laws holding for them. I'm actually surprised that they can be proved with as few as 6 simply hypotheses, it looked like 8 would be required until I tried to just through out ones and see what happened.

          Phil

          Mathematics should not have to involve martyrdom;
          Support Eric Weisstein, see http://mathworld.wolfram.com
          Find the best deals on the web at AltaVista Shopping!
          http://www.shopping.altavista.com
        • paulmillscv@yahoo.co.uk
          Hello Juan, Phil, Yes you are right. De Morgan s laws can be proved from the 8 axioms of Boolean Algebra (as in `Son of Birdbrain or Bell). As Phil notes,
          Message 4 of 5 , Oct 31, 2001
          • 0 Attachment
            Hello Juan, Phil,
            Yes you are right. De Morgan's laws can be proved from the 8
            axioms of Boolean Algebra (as in `Son of Birdbrain' or Bell). As
            Phil notes, they can even be proved without commutativity (the first
            two radio buttons on the web page) and so only require 6 axioms.
            However in my defence all I can say is that when I tried the software
            about 6 months ago, it really did not prove it. Of course it is
            likely I did not press the right buttons. So one lives and learns!
            Thanks for that (major) learning experience.

            But your comments Juan are interesting. Note that you use a new
            operation `belongs to' which does not belong to the Boolean axioms,
            this means that your proof is really a `transformation.' But it may
            well be the case that `belongs to' can be expressed in terms of the 8
            (or 6) axioms. You see, I can be a strict algebraist when I try!

            Phil, your comments are even more interesting. You claim every
            tautology (i.e. every proposition with all Ts in the truth table) is
            provable. I am inclined to agree with you. So therefore as the
            truth table is isomorphic to Boolean algebra then every tautology
            should have a corresponding proof using the Boolean axioms.
            Therefore it is only necessary to look at its truth table in order to
            prove a proposition with Boolean logic. Super stuff.

            Regards,
            Paul Mills
          • Juan Pedro Hecht
            Hello Paul, Thanks, you are right with the comment about the Boolean operator (E) belongs to , but it is not hard to obtain it from the primitive Boolean
            Message 5 of 5 , Nov 1, 2001
            • 0 Attachment
              Hello Paul,

              Thanks, you are right with the comment about the Boolean operator (E)
              'belongs to', but it is not hard to obtain it from the primitive Boolean
              operators:

              Let a, b, c, 0, 1 be objects 'belonging to' the K Boolean Set. All the
              properties for 'belongs to' are:

              (a E a)
              if (a E b) and (b E a) then a=b
              if (a E b) and (b E c) then (a E c)
              (a E 1) and (0 E a)
              (a E (a+b)) and ((a.b) E a)
              if (a E b) then ((not b) E (not a))

              but Boolean Algebra don't need that operator, and of course Morgan's Law's
              are easy to derive from the original Huntington set (1904).

              Thanks again for your comments!

              Juan
              >
              >
              >
            Your message has been successfully submitted and would be delivered to recipients shortly.