Question: Can the absorption property be used to simplify p \lor (\neg p \land q)?

Here's the absorption property again: p\lor ( p \land q)\equiv p (and the analog for \land/\lor holds, too)

As an aside, here's a proof of that property by truth table:

p

q

p\land q

p\lor ( p \land q)

F

F

F

F

F

T

F

F

T

F

F

T

T

T

T

T

Now on to our actual problem: Does the absorption property in any way apply to p \lor (\neg p \land q), possibly using double negation (but nothing else)?

It turns out that it does not. I think that the 'clever way' I had initially seen in class was this:

p \lor (\neg p \land q) \equiv (\neg \neg p) \lor (\neg p \land q) \text{ is not equivalent to (!) } \neg (\neg p \lor (\neg p \land q)) \dots

As you can see above (by the 'not equivalent to'), that is wrong! Observe how the parentheses after the initial negation suddenly contain the whole expression. Good thing I caught myself.

In summary, double negation always only modifies the 'innnermost' symbols, and adding two negations at a time, one stands no chance of turing p into \neg p. As a result, the two p subexpressions of the absorption property as applied here are never going to match up, because the absorption property cannot apply if there are stray '\neg' symbols. In summary, sorry for the confusion.

Teaching/DiscreteMathSpring2011/Supplements/AbsorptionProperty (last edited 2011-02-01 04:00:17 by AndreasKloeckner)