Logic and Sets.
- 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.
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!
- Paul wrote:
>Did you know that De Morgan's laws cannot be proved usingSorry, I disagree.
>Boolean algebra? Incredible but true.
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.
[Non-text portions of this message have been removed]
- On Wed, 31 October 2001, paulmillscv@... wrote:
> Did you know that De Morgan's laws cannot be proved usingPropositional calculus is complete. Every tautology has a proof. DeMorgan's laws are true by truth-table, therefore they're provable.
> Boolean algebra? Incredible but true. De Morgan's laws have
> theirYou 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.
> origin in� human thought. J. To prove this, use the wonderful
> automatic deduction software `Son of Birdbrain' at this link.
> Set up a Boolean algebra as axioms and then click on the De
> Morgan'sYou 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.
> 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!
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!
- 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.
- 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
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!