I looked all over Google for a boolean algebra (not set theory) proof of DeMorgan's Law, and couldn't find one. Stack Overflow was also lacking in DeMorgan's Law questions.
As part of a homework assignment for my CIS 251 class, we were asked to prove part of DeMorgan's Law, given the following expressions:
[z + z' = 1 and zz' = 0]
to prove (xy)' = x' + y' by showing that (simplifying)
(x y) + (x' + y') = 1 and (x y)(x' + y') = 0
My attempt (with a friend) at the first expression was (steps numbered for reference):
1. (x y) + (x' + y') = 1
2. (xy + x’)(xy + y’) = (Distributive Prop)
3. (x + x’)(y + x’)(x + y’)(y + y’) = (Distributive Prop) // This is probably not correct
4. (1)(y + x’)(x + y’)(1) = (Compliment Prop)
5. (y + x’)(x + y’) = (0 & 1 Identity Prop)
6. (x + x’)(y + y’) = (Commutative Prop) // I know for a fact this is not how the commutative property works
7. (1)(1) = (Compliment Prop)
8. 1 = (0 & 1 Identity Prop)
So I know I got it wrong - I cheated somewhere and exaggerated the reality of how some of these postulates actually work. But my friend and I tried for about an hour, and went through every postulate (excluding DeMorgan's Law) and could not for the life of us get it to simplify.
Can anyone show me where we went wrong, or what we missed? We didn't bother with the second one because we knew had the first one wrong, and that the second would be very similar.
PS - I know that this can be proved using truth tables - and for obvious reasons that is applicable in the real world. However, I would like to understand the derivation that allows us to use the simplified expressions.
I do not know the best method of doing this. This is what I have done:
(x.y)' = x' + y'
↔
(x.y)' + x.y = x' + y' + x.y ............ (assuming x.y != 1)
↔
1 = x' + y' + x.y
↔
1 = x' + (y' + x).(y' + y)............... (Distributive property)
↔
1 = x' + (y' + x)
↔
1 = 1
Now, in the first step we assumed that x.y != 1. If it was so, then the statement is obviously true.
P.S.: I am myself not fully satisfied with this proof as we still deal with it in cases. It's not one-blow-for-all!