Removing redundancy in a propositional formula

Question

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.

score 3 · Accepted Answer · answered Sep 23 '13 at 07:26

3

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

answered Sep 23 '13 at 07:26

user91500

5,606

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

Removing redundancy in a propositional formula

1 Answers1