So I'm trying to simplify the Boolean expression (1) $A + \bar{A}\bar{B}$.

I noticed that by Karnaugh maps this is equivalent to $A+\bar{B}$, and I also noticed that if I take the complement of (1), I get ~(1)= $\bar{A}(A + B) = \bar{A}A + \bar{A}B = \bar{A}B$, so then taking complements again yields (1) = $A + \bar{B}$.

But this feels very ad hoc to me, and makes me feel like I'm missing some key point about how to simplify this expression more systematically.

Any thoughts appreciated.



There is a Law of Distributivity of Boolean operation $\lor$ (disjunction, which is sometimes denoted by $+$) over Boolean operation $\land$ (conjunction, which is sometimes simply omitted): $$x \lor (y \land z)= (x \lor y)\land(x \lor z)$$ So, in your case: $$A \lor (\lnot A \land \lnot B) = (A \lor \lnot A) \land (A \lor \lnot B) = A \lor \lnot B$$ For more information please see: Boolean Algebra.


To simplify small expressions, you will use ad hoc methods (in larger expressions, this often lets you achieve _some _ simplification).

For larger cases, you could write or use existing software, which tries to find the “simplest” expression equivalent to a given one, according to your definition of “simplest”. The runtime will grow fast. Actually the question whether an expression can be simplified to “false” is NP-complete (that is practically unsolvable for hard cases), and that is just one very special case of simplifying an expression.


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.