1
$\begingroup$

I have the following propositional formula:

$$\lnot A \land (\lnot A \lor \lnot B) \land (\lnot A \lor C) \land (\lnot B \lor C)$$

I can see and "explain" that the middle two terms in brackets are redundant, so the formula simplifies to:

$$\lnot A \land (\lnot B \lor C)$$

I can't, however, figure out how to get there formally using the associativity laws of $\land$ and $\lor$, de Morgan's laws, etc.

Can anyone please give some help with those formal steps? Thanks in advance.

$\endgroup$
3
$\begingroup$

Note that $P\land(P\lor Q)\equiv P$, so $$\lnot A \land (\lnot A \lor \lnot B) \land (\lnot A \lor C) \land (\lnot B \lor C)\equiv\lnot A \land(\lnot A\lor(\lnot B\land C))\land (\lnot B \lor C)$$$$\equiv\lnot A\land(\lnot B \lor C).$$

$\endgroup$
2
  • $\begingroup$ That's exactly the sort of property I was looking for, thanks very much. $\endgroup$ – Michael Sep 23 '13 at 7:35
  • $\begingroup$ @Michael This property sometimes gets called "absorption." $\endgroup$ – Doug Spoonwood Sep 23 '13 at 14:29

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.