I'm studying for my discrete math exam and I'm looking over the professors' examples. I have a question about one of them and I was hoping someone could help me out. Here is the example:
6. Use equivalence laws to show that the following two formulas are equivalent.
f = ((x and y) = x)
g = x -> y
Sol:
f
= {first formula}
(x and y) = x
= {Equality}
((x and y) and x) or (not (x and y) and not x)
= {Symmetry, Associativity, x and x = x}
(x and y) or (not (x and y) and not x)
= {De-Morgan's, Absorption}
(x and y) or not x
= {Distribution}
(x or not x) and (y or not x)
= {x or not x = T}
T and (y or not x)
= {T and h(x,y) = h(x,y)}
y or not x
= {Implication}
x -> y
= {second formula}
g
My question comes at the De-Morgan's and Absorption step:
(x and y) or (not (x and y) and not x)
I assume the De-Morgan's step renders the following:
(x and y) or not(x and y) and x)
Apparently the right hand side is then absorbed into x:
(x and y) or not x
But I was under the impression from my notes that absorption only worked when there was both an 'and' and an 'or', for example (from my notes):
f(x) and [f(x) or g(x)] = f(x)
f(x) or [f(x) and g(x) = f(x)
However it appears from this example that absorption works with only 'and's (and I assume only 'or's):
(x and y) and x = x
Would someone please verify my interpretation? I assume my professor is not making a typo but I want to be sure, thanks.
Your mistake is in the missing DeMorgan step.
$$(\lnot(x\land y)\land\lnot x)\iff\lnot((x\land y)\lor x)$$
And now you can absorb that into $x$.