1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.