Math Is Fun Forum

Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

#1 2008-01-25 16:35:41

mikau
Member
Registered: 2005-08-22
Posts: 1,504

proof of demorgans law

does anyone know a way to prove demorgans law without breaking the possibilities into separate cases?

(note i'm using  for AND, + for OR and ' for NOT)

suppose these are the postulates you may use:

P1 Boolean algebra is closed under the AND, OR, and NOT operations.
P2 The identity element with respect to  is one and + is zero. There is no identity element with respect to logical NOT.
P3 The  and + operators are commutative.
P4  and + are distributive with respect to one another. That is, A  (B + C) = (A  B) + (A  C) and A + (B  C) = (A + B)  (A + C).
P5 For every value A there exists a value A such that AA = 0 and A+A = 1. This value is the logical complement (or NOT) of A.
P6  and + are both associative. That is, (AB)C = A(BC) and (A+B)+C = A+(B+C)

and you may use the following thoerems:

Th1: A + A = A
Th2: A  A = A
Th3: A + 0 = A
Th4: A  1 = A
Th5: A  0 = 0
Th6: A + 1 = 1

use all of the above to prove (a + b) = a  b

i begin by proving the following lemma:

lemma 1: if A * B' = 0 and A + B' = 1, then A=B

proof by contrapositive: suppose A ≠ B, then A = B' therefore
A*B' = A*A = 0 and by theorem 2,
A = 0,  but likewise
A + B' = A+A = 1 and by theorem 2
A+A = A = 1, thus we have A = 1 and A = 0, a contradiction. Thus the lemma is proved.

Now we use this to prove (a + b) = a  b

we use the lemma, if A * B' = 0 and A + B' = 1, then A=B

let A = a' * b' and let B = (a + b)'

first we show A * B' = 0

A*B' =  (a' * b')*(a + b), using the distributive and commutative postulates,
=  a'*a * b' + a'*b'*b  now using postulate 5
= 0 * b' + a'* 0, now by theorem 5
= 0 * 0 = 0

now we show A + B' = 1

A + B' = a' * b' + a + b

suppose a = b (this is what i don't like doing )
then
a' * 'b + a + b = a' * a' + a + a.  by theorems 1 and 2,
= a' + a. by postulate 5
= 1

suppose now that a ≠ b, then (and so a = b' and b = a')
then

a' * b' + a + b = a' * a + a + a'. by postulate 5
= 0 + 1 = 1

therefore the lemma applies so A = B,  or more specifically,  (a + b) = a  b qed.

I guess this works but is there any way to avoid breaking it up into cases? If i'm going to use that, i might as well use a truth table to prove it.

A logarithm is just a misspelled algorithm.

Offline

#2 2008-01-25 18:48:20

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

Re: proof of demorgans law

When you say A ≠ B, do you mean some of the time or all of time?
Since A is 1 or 0 and B is 1 or 0, just because A is not equal to B,
doesn't necessarily mean that A is equal to negative B, or does it?
It all depends on how independent your variables are?

igloo myrtilles fourmis

Offline

#3 2008-01-25 19:51:14

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: proof of demorgans law

agreed, john. In fact i'm wondering if its okay to say A ≠ B ⇒ A = Not B at this point, or if we need to establish it using other postulates.

A logarithm is just a misspelled algorithm.

Offline

#4 2008-01-26 03:22:20

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

Re: proof of demorgans law

I'm no mathmatician, so I'm not sure if there are different kinds of "not equal" signs; one that means unequal no matter what, and one that means not equal at least in one case.
If it means always unequals, then you are right that they are opposites since it is a two-state {0, 1} arena.

Let me just fiddle around here, this
stuff below can be ignored if it
doesn't help.

I'm gonna just use variables beside one another to mean AND'ing to make this faster typing.
a = a
a = a ( 1 + b`)
a = a + ab`
...
a = a
a = a (1 + 0)
a = a (b + b`) = a(b`+ b)
a = ab + ab`
...
Likewise use b instead of a.
b = b
b = b (1 + 0)
b = b (a + a`) = b(a` + a)
b = ba + ba`
b = ab + a`b
...
I think "P5" is the key to solving this.
Can you use these rules? 1` = 0     0`=1

I'd like to add a comment on this
particular boolean algebra described above.
There is no mention that the values of
A and B can be only 0 and 1, and that
A and B are variables that can each be
independent or related to one another
in some circumstances or something.
Is this all just assumed???
If we don't lay down a strong foundation,
then loop-holes can be found, and you
can get funny weird results, that are an
algebra that is less fully constrained than
the one you wanted in the first place.

I'll edit this and add more...

Last edited by John E. Franklin (2008-01-26 05:19:23)

igloo myrtilles fourmis

Offline

#5 2008-01-26 07:07:24

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: proof of demorgans law

I'm no mathmatician, so I'm not sure if there are different kinds of "not equal" signs; one that means unequal no matter what, and one that means not equal at least in one case.
If it means always unequals, then you are right that they are opposites since it is a two-state {0, 1} arena.

first i'm using 1 and 0 to represent the boolean values true and false respectively, thats just notation

the above are all postulates, I think there are probably some axioms that i'm allowed to use. For instance, a boolean value is either true or false. If it isn't false, its true, and vice versa.

when working with variables, the actual values are not given, however you can be sure that either A = B or A ≠ B no matter what values for A and B are being dealt with. If you can show that it works in both cases, then you have proved it in the general case.

But yeah, the question remains, is it okay to say A ≠ B ⇒ A = B'

I think if we are working with boolean values, we have to be able to assume that much, right?

A logarithm is just a misspelled algorithm.

Offline

#6 2008-01-26 08:41:08

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

Re: proof of demorgans law

Well, the thing is, there are so many ways folks have
used symbols, that almost anything is true and false
at the same time, depending on the exact meaning
of your symbols.  Like the ⇒ symbol is unfamiliar to me,
but I also use ---> in my own posts.  But since you
are trying to do a "proof", this is where I have to
drop out and say I'm not formal enough or legit yet.
The operators and equality statement and implication
symbols can all get confused, because there are
similarities between them.  Like the non-equal symbol
is similar to the XOR operator, but one is an operator,
and the other separates two sides of an equation.
The ⇒ symbol also reminds me of the imply logic symbol,
and parallels can probably be stated along these lines.
The other thing is that, Venn diagrams are a useful tool,
and one can visualize DeMorgans Law with Venn diagrams
quite easily, if you know how to shade it in and take
the negative image, but I hesitated to even bring up this
because you are trying to stick to certain rules; and
perhaps the boolean algebra mentioned here is not
exactly the same as Venn diagrams anyway, because the
entire set of rules and original structure may be allowing
for things to be stated that are not true for Venn diagrams.
what I normally do...

igloo myrtilles fourmis

Offline

#7 2009-11-05 13:12:12

Melanie1988
Guest

Re: proof of demorgans law

I need help proving the DeMorgan's Law with Boolean Algebra. No "and" nor "or".

( a + b )' = a' * b'

For example, Proof of Absorption Law:
a ( a + b ) = a
( a * a ) + ( a * b ) => distributive property
a + a * b => idempotent law
a ( 1 + b ) => distributive property
a ( 1 ) => boundedness law
a => identity property

sima
Guest

#9 2011-12-07 17:44:36

Dharmendra Kumar Verma
Guest

Re: proof of demorgans law

for every x in a Boolean
algebra there is a unique x' such that
x + x' = 1   and   x  x' = 0
So it is sufficient to show that x'y' is the complement of x + y.  We'll do this by showing that
(x + y) + (x'y') = 1   and    (x + y)  (x'y') = 0
(x + y) + (x'y') = [(x + y) + x'] [(x + y) + y'] OR distributes over AND
= [(y + x) + x'] [(x + y) + y'] OR is commutative
= [y + (x + x')] [x + (y + y')] OR is associative
= (y + 1)(x + 1) Complement, x + x' = 1
= 1  1 x + 1 = 1
= 1 Idempotent,
x  x = x
Also,
(x + y)(x'y') = (x'y')(x + y) AND is commutative
= [(x'y')x] + [(x'y')y] AND distributes over OR
= [(y'x')x] + [(x'y')y] AND is commutative
= [y'(x'x)] + [x'(y'y)] AND is associative
= [y'(xx')] + [x'(yy')] AND is commutative
= [y'  0] + [x'  0] Complement, x  x' = 0
= 0 + 0 x  0 = 0
= 0 Idempotent, x + x = x