proof of demorgans law

mikau · 2008-01-25 16:35:41

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 AA = 0 and A+A = 1. This value is the logical complement (or NOT) of A.
P6 and + are both associative. That is, (AB)C = A(BC) 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.

John E. Franklin · 2008-01-25 18:48:20

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?

mikau · 2008-01-25 19:51:14

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.

John E. Franklin · 2008-01-26 03:22:20

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)

mikau · 2008-01-26 07:07:24

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?

John E. Franklin · 2008-01-26 08:41:08

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.
I just don't want to jump to conclusions since this is
what I normally do...

Melanie1988 · 2009-11-05 13:12:12

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 · 2010-05-18 17:34:17

please help mi , proof of de morgans low: (xy)'=x'+y'

Dharmendra Kumar Verma · 2011-12-07 17:44:36

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

Math Is Fun Forum

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

proof of demorgans law

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

Re: proof of demorgans law

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

Re: proof of demorgans law

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

Re: proof of demorgans law

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

Re: proof of demorgans law

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

Re: proof of demorgans law

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

Re: proof of demorgans law

#8 2010-05-18 17:34:17

Re: proof of demorgans law

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

Re: proof of demorgans law

Board footer