Help with Boolean logic!

[Nihilist]

I though it might be goof to us Boolean algebra to try to prove the existence of God. But instead, I seemed to have proved the non-existence of the physical universe.

Let God’s existence be G, and the existence of the physical universe be U. G’ means ‘Not G’, and U’ means ‘Not U’. Now totality (1) contains four OR’ed possibilities: Both G and U (both God and the physical universe exist), G’ and U (not God, but the physical universe exists), GU’ (God exists, but not the physical universe) and G’U’ (neither God nor the physical universe exist).

Thus it is given:
1= GU + G’U + GU’ + G’U’

Taking common factor G from first two terms of the equation:
1= G (U + U’) + G’U’ + G’U

Using the Boolean rule X + X’=1, to eliminate the expression (U + U’):
1= G + G’U’ + G’U

Applying deMorgan’s law (X’Y’= X’ + Y’) to G’U’:
1= G + G’+ U’ + G’U

Taking common factor G’ out of expressions G’ and G’U:
1= G + G’ (1 + U) + U’

Applying the Boolean rule that 1 + X= 1, to the (1+U) factor in the second term:
1= G + G’ +U

Applying the rule X + X’= 1 to the first two terms of the equation:
1= 1 + U

Subtracting 1 from both sides:
0= U

Therefore, the physical universe does not exist!
HELP!!

 

[rossum]

Applying the rule X + X’= 1 to the first two terms of the equation:
1= 1 + U

You are correct up to this point.

Subtracting 1 from both sides:
0= U

This is your error. In Boolean algebra, the symbol “+” means “OR”, it does not mean addition. There is no operation of “subtraction” in Boolean algebra. You are equivocating between the Boolean “+” and the arithmetic “+”.

In Boolean logic, 1 + X means “TRUE OR X”. 1 + X = 1 for all X.

Hence, your correct 1 = 1 + U results in: 1 = 1, or TRUE = TRUE

Which is true, a tautology and not particularly useful: everything which is true is true.

rossum

 

[Nihilist]

You are correct up to this point.

This is your error. In Boolean algebra, the symbol “+” means “OR”, it does not mean addition. There is no operation of “subtraction” in Boolean algebra. You are equivocating between the Boolean “+” and the arithmetic “+”.

In Boolean logic, 1 + X means “TRUE OR X”. 1 + X = 1 for all X.

Hence, your correct 1 = 1 + U results in: 1 = 1, or TRUE = TRUE

Which is true, a tautology and not particularly useful: everything which is true is true.

rossum

Thanks. I am just learning with Boolean algebra.

A question, if you would be kind enough to help:

Would it be wrong to say?
a+b= c+ b
Therefore, a=c
In other words, would it be wrong to say:
“A group comprising everthing that is a or b, is identical with the group comprising everything that is c or b. Therefore the group comprising a is identical to the group comprising c.”

My brain can’t quite grasp it…

 

[inocente]

You might find the syntax used in C++, C# and Java better for learning.

& = AND
| = OR
~ = NOT

Also true and false are used instead of 1 and 0, which avoids the temptation to do counting on them, and parentheses are used copiously to give the order of evaluation, so it’s a little more long-winded.

So:

(G & U) | (G & ~U) | (~G & U) | (~G & ~U) = true

Taking common factor G from first two terms of the equation:
(G & (U | ~U)) | (~G & U) | (~G & ~U) = true

You can also take common factor ~G out, giving:
(G & (U | ~U)) | (~G & (U | ~U)) = true

Using the X | ~X = true rule to eliminate the expression (U | ~U):
G | ~G = true

And again on G | ~G:
true = true

In this syntax, De Morgan’s laws are ~(X & Y) = ~X | ~Y and ~(X | Y) = ~X & ~Y

 

[Nihilist]

You might find the syntax used in C++, C# and Java better for learning.

& = AND
| = OR
~ = NOT

Also true and false are used instead of 1 and 0, which avoids the temptation to do counting on them, and parentheses are used copiously to give the order of evaluation, so it’s a little more long-winded.

So:

(G & U) | (G & ~U) | (~G & U) | (~G & ~U) = true

Taking common factor G from first two terms of the equation:
(G & (U | ~U)) | (~G & U) | (~G & ~U) = true

You can also take common factor ~G out, giving:
(G & (U | ~U)) | (~G & (U | ~U)) = true

Using the X | ~X = true rule to eliminate the expression (U | ~U):
G | ~G = true

And again on G | ~G:
true = true

In this syntax, De Morgan’s laws are ~(X & Y) = ~X | ~Y and ~(X | Y) = ~X & ~Y

Thanks. I’ll have a look into those other notational systems.

So, if something is true, it’s true…I guess no one can argue with that.

 

[inocente]

So, if something is true, it’s true…I guess no one can argue with that.

It’s a good test of a theorem to make sure the sides match.

 

[rossum]

Would it be wrong to say?
a+b= c+ b
Therefore, a=c

Yes, it would be wrong.

Consider a = true, b = true, c = false.

a + b = a OR b = true, since a is true. b is also true, but that is not needed.

c + b = c OR b = true, since b is true.

In this case we have a + b = c + b (i.e. true = true) and a =/= c; a is true and c is false.

You can only remove the b’s if you independently have b = 0, i.e. you know that b is false. X + 0 = X for all X.

In other words, would it be wrong to say:
“A group comprising everthing that is a or b, is identical with the group comprising everything that is c or b. Therefore the group comprising a is identical to the group comprising c.”

You are not talking groups, but logic. Each statement will evaluate to true or false (1 or 0).

You appear to be having some confusion between arithmetic, boolean logic and set algebra. In mathematics, there are a lot of different definitions of different things and it is important to bear in mind which of the many definitions currently apply.

My brain can’t quite grasp it…

Understandable. It isn’t easy, at least not until you have grasped it. Once you have, then you will wonder why you found it so difficult.

rossum

 

[Nihilist]

Yes, it would be wrong.

Consider a = true, b = true, c = false.

a + b = a OR b = true, since a is true. b is also true, but that is not needed.

c + b = c OR b = true, since b is true.

In this case we have a + b = c + b (i.e. true = true) and a =/= c; a is true and c is false.

You can only remove the b’s if you independently have b = 0, i.e. you know that b is false. X + 0 = X for all X.

You are not talking groups, but logic. Each statement will evaluate to true or false (1 or 0).

You appear to be having some confusion between arithmetic, boolean logic and set algebra. In mathematics, there are a lot of different definitions of different things and it is important to bear in mind which of the many definitions currently apply.

Understandable. It isn’t easy, at least not until you have grasped it. Once you have, then you will wonder why you found it so difficult.

rossum

Many thanks.

I have been using Boole’s “The Mathematical Analysis of Logic”, which initially defines variables in terms of sets containing particular features- in which he defines xy as the set of all things containing the features of x and y, or all X’s from the set of Y’s. Hence my attempt to imagine in terms of set of things with particular characteristics, rather than as propositions which are either true or not.

 

[Oreoracle]

As Rossum said, the problem is the assumption that addition has a cancellation property in this system. Fortunately, if you take addition to be exclusive disjunction (a+b means a is true or b is true but not both) and multiplication to be conjunction, then this forms a mathematical structure called a ring, wherein addition has a cancellation property. Wikipedia has an article over the Boolean ring.

Just to be clear on what a ring is and what’s allowed, here’s the definition broken into parts: A ring is a set containing elements (in this case, propositions) that can be combined with two binary operations called addition and multiplication. Rings satisfy the following axioms:

1. Addition is associative and commutative; that is, a+b=b+a and (a+b)+c=a+(b+c)
2. Multiplication is associative, though not necessarily commutative; that is, (ab)c=a(bc). Note that since conjunctions are commutative, multiplication is commutative in this particular ring. (This is an example of a “commutative ring”.)
3. Addition and multiplication satisfy the distributive property; that is, a(b+c)=ab+ac
4. There exists an element x in the ring such that y+x=y for any y in the ring. This element can be proven to be unique, so we call the only element with this property 0.
5. There exists an element x in the ring such that yx=y for any y in the ring. This element can be proven to be unique, so we call the only element with this property 1.
6. Every element in the ring has an additive inverse; that is, for any x, there exists called -x such that x+(-x)=0. Multiplicative inverses may or may not exist.
7. The ring is closed under addition and multiplication; that is, any sum or product of ring elements is also in the ring.

Using properties of equality, you can show that it’s permissible to add the same term to both sides of an equation, so we can prove the cancellation property “a+c=b+c implies a=b”. Proof: Suppose a+c=b+c. The existence of -c is guaranteed by (6), so add -c to both sides, giving a+c+(-c)=b+c+(-c). We don’t have to write parentheses to group these terms together since addition is associative. By (6), c and -c cancel, giving us a+0=b+0. By (4), the 0’s can be eliminated, giving us a=b.

We also have a cancellation property for multiplication: ac=bc where c=/=0 implies a=b. We cannot use division since the existence of multiplicative inverses isn’t guaranteed. Instead we subtract bc from both sides and factor out c by using the distributive property from (3), yielding (a-b)c=0. (Of course, a-b means “a+(-b)”.) This says that the conjunction of a-b and c is false. Thus at least one of those propositions must be false. Our hypothesis is c=/=0, which means that c isn’t false. Thus a-b must be false, so a-b=0, or a=b. (Not all rings allow you to say that if a product is zero, one of its factors is 0. But this ring does, and such a ring is called an integral domain.)

A good example of a commutative ring that you can keep in mind is the set of integers with the operations of addition and multiplication. Additive inverses exist for each element, but only 1 has a multiplicative inverse, itself. I hope this helps.

 

[phil_at_dayboro]

I’m always impressed with the intelligence of humanity, just wish it could have been spread around a bit more,

 

[Someone2841]

A few notes that I did not see in the previous replies (though Oreoracle did a good job explaining how Boolean Logic uses a communicative ring!).

In Boolean Logic, a + b represents a xor b, not a or b. E.g., 1 + 1 = 0 ~ True xor True = False. a or b would be represented by a + b + ab.

DeMorgan never came up with such a law as X’Y’= X’ + Y’. Let X = 1 and Y = 0. and see that 01 = 0 + 1 is just False. I think you meant (XY)’ = X’ + Y’, but this is still false. Let X = 1 and Y= 1 and see that (00)’ = 0 + 0 is also False. DeMorgan’s law states that (XY)’ = X’ + Y’ + X’Y’.

1 + X= 1 does not hold either. If X = 1 then 1 + 1 = 1, but that is False.

Therefore, you do not validly arrive at 1 = 1 + U (contrary to rossum thinking so). You are correct in noting that this is a contradiction, though, since 1 = 1 + U is true only if U = 0 (False). You /can/ validly subtract 1 in Boolean algebra (again, rossum is incorrect here); it is the same as added 1, and results in the negation of both sides. The whole point of Boolean algebra is to use +, -, and * (but not division!) instead of operators like & and ^, etc.!

---

If a + b = c + b then of course a = c. Again, this does not mean ((a OR b) <-> (c OR b)) <-> (a <-> c), because that is False. It means ((a XOR b) <-> (c XOR b)) <-> (a <-> c), and this is true.