# Optimizing a boolean expression to (NAND,AND,NOT) system

I'm trying to simplify the expression given by the following Karnaugh map to an expression that is using only NANDs, NOTs and ANDs- the less gates (of any kind), the better.

I know how to optimize it to an (OR,AND,NOT) system, but that doesn't seem to help.

I also know how to create an OR gate using only NANDs and NOTs, but that creates a really complicated expression and I've been hinted there's a simple one.

I tried using Wolfram Alpha, but no (AND,NAND,NOT) system exist. The closest one is a (NAND, NOT) system and that expression still looks complicated.

I'm allowed 4 inputs per NAND and 2 inputs per AND.

• How many inputs are you allowed per gate? Unspecified?
– user16324
Commented Jun 15, 2015 at 21:37
• Start with getting the POS expression. In your case you will get from the K-map 4 3-var sums, while each of them can be transformed to a 3-input-NAND representation using the DeMorgan rule. So without any further manual simplifications, I am getting here 4 NOT gates, 4 3-input NANDS and one 4-input AND - total of 9 gates. Commented Jun 15, 2015 at 21:42
• @BrianDrummond Sorry, I haven't specified that. I'm allowed 2 inputs per AND and 4 inputs per NAND. Commented Jun 15, 2015 at 21:56
• @EugeneSh. Thanks! As I've now added I'm only allowed 2 inputs per AND, so although I could part the AND in your solution to 2 ANDs maybe there's a better solution under these conditions. Commented Jun 15, 2015 at 21:58

Complement Law says $\overline{\overline{X}} = X$.
$$\overline A\ \overline B\ \overline C + \overline A\ B\ C + A\ B\ D + A\ \overline B\ \overline D$$
Take Double Complement. $$\overline{\overline{\overline A\ \overline B\ \overline C + \overline A\ B\ C + A\ B\ D + A\ \overline B\ \overline D}}$$
Use DeMorgan's to remove lower complement. $$\overline{\overline{\overline A\ \overline B\ \overline C} ∙ \overline{\overline A\ B\ C} ∙ \overline{A\ B\ D} ∙ \overline{A\ \overline B\ \overline D}}$$