Boolean Algebra - Proving Demorgan's Law

Question

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.

Answer 1

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!

Answer 2

1. (X Y) + (X' + Y') = 1;
2. (X + X' + Y) (Y + X' + Y') = 1; DISTRIBUTIVITY AB+C = (A+C)(B+C);
3. ( 1 + Y) ( 1 + X') = 1; SINCE Z + Z' = 1;
4. (1) (1) = 1; SINCE 1 + Z = 1;
5. 1 = 1; IDENTITY; QED

Answer 3

Trying to do what now? prove that 2 + 2 = 4 without counting?

"true and true is not, not true or, not true."

⊤ ∧ ⊤ ↔ ¬(¬⊤ ∨ ¬⊤)

"false and false is not, not false or, not false."

⊥ ∧ ⊥ ↔ ¬(¬⊥ ∨ ¬⊥)

"true and false is not, not true or, not false."

⊤ ∧ ⊥ ↔ ¬(¬⊤ ∨ ¬⊥)

"The truth is that: true and true is not, not true or, not true and; false and false is not, not false or, not false and; true and false is not, not true or, not false." My punctuation is probably a little screwy on that one but the formula below checks out.

⊤ ↔ (⊤ ∧ ⊤ ↔ ¬(¬⊤ ∨ ¬⊤)) ∧ (⊥ ∧ ⊥ ↔ ¬(¬⊥ ∨ ¬⊥)) ∧ (⊤ ∧ ⊥ ↔ ¬(¬⊤ ∨ ¬⊥))

Answer 4

i bet this is a good method
we got to prove,
xy + x' + y' =1
take LHS
x'+xy+y'
add xx' and x'y to it (notice that it does not change anything prove using simple boolean laws)

so now
LHS becomes,
x'+xx'+xy+x'y+y'
=> x'(1+x)+y(x+x')+y'
=> x'+y+y'
=> x'+1
=> 1

hence xy+x'+y'=1
similarly do it for the other one  

Answer 5

"(x.y)' + x.y = x' + y' + x.y)"

let x.y=A

then look at following statement

A+A'=1