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$

1 Answer 1

Reset to default
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$ Commented Sep 23, 2013 at 7:35
  • $\begingroup$ @Michael This property sometimes gets called "absorption." $\endgroup$ Commented Sep 23, 2013 at 14:29

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.