1
$\begingroup$

I was reading this question which links to this list of propositional equivalences.

One of the equivalences shown (T5a) is:

$$ A \wedge B \vee A \wedge \neg B \equiv A $$

I have used this rule by intuition in the past, but never put a name to it. I was wondering if it has a formal name?

Further I wonder (and perhaps this should be a separate question), if I were to close a DNF formula under this rule (inefficient as this may be), would I find the prime implicants? Does any paper/book describe such a process?

Thanks

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

T5 is nothing more than summarizing the following string of equivalences:

$$(A\land B) \lor (A \land \lnot B) \equiv A\land (B \lor \lnot B) \equiv A \land 1 \equiv A$$

That is, it's justified (can be proven to hold) by an application of the distributive law, and the facts that $B\lor\lnot B = 1\;$ (by T10), and $\;A\land 1 = A\;$ (by T8)

$\endgroup$
3
  • $\begingroup$ I follow. So it doesn't have a name per se? Any thoughts on the second part of the question? $\endgroup$
    – Edd Barrett
    Feb 13, 2014 at 21:20
  • $\begingroup$ I'm not really clear about what you're asking in the second part. The proposition posted is already in DNF. $\endgroup$
    – amWhy
    Feb 13, 2014 at 21:26
  • $\begingroup$ Suppose we have an arbitrary DNF. If we simplify the formula exhaustively using the above simplification rule, do we derive the prime implicants? I'm starting to think no, since we might have to apply absorption too. Basically I am interested in syntax directed ways of deriving the prime implicants from DNF. $\endgroup$
    – Edd Barrett
    Feb 13, 2014 at 22:45

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.