2
\$\begingroup\$

Is there a way to easily convert a boolean expression with only few variables into a NOR form?

Let's take the half-adder as an example:

a b | sum
---------
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

The sum of products is: $$sum = \overline{a} b + a \overline{b}$$

If I convert that to a form which only involves NAND gates with 2 inputs, I get:

$$sum = \overline{a}b + a\overline{b} = \overline{\overline{\overline{a}b + a\overline{b}}} = \overline{\overline{\overline{a}b + a\overline{b}} + 0} = \overline{\overline{\overline{a + \overline{b + 0}} + \overline{\overline{a+0} + b}} + 0}$$

I count 6 NOR gates.

However, if I first write the boolean expression as a product of sums: $$sum = (a + b) \cdot (\overline{a} + \overline{b}) = \overline{\overline{a+b} + \overline{\overline{a} + \overline{b}}} = \overline{\overline{a+b} + \overline{\overline{a + 0} + \overline{b + 0}}}$$

Now, there are only 5 NOR gates.

As I guess this is a heavy optimization problem (as suggested by this paper, I'd like to ask whether there is a way to 'optimize' it in small boolean expressions (e.g. < 3 variables).

Furthermore, I'd be interested in an answer regarding the same question with NANDs as well as the same problem appears there, too.

\$\endgroup\$
  • \$\begingroup\$ google.com/… \$\endgroup\$ – Andy aka Mar 16 '16 at 17:39
  • \$\begingroup\$ @Andyaka The goal is to convert the expression into a NOR form, so that it only consists of NOR gates with two inputs. \$\endgroup\$ – CMOS Mar 16 '16 at 18:04
  • \$\begingroup\$ You can evaluate it using Wolfram Alpha with the input: NOR ((not a) and b) or (a and (not b)) \$\endgroup\$ – tcrosley Mar 16 '16 at 19:36
  • \$\begingroup\$ Yes, so what didn't you see on the linked page (hint 1st picture)? \$\endgroup\$ – Andy aka Mar 16 '16 at 20:43
  • \$\begingroup\$ @Andyaka Do you mean Wikipedia's XOR gate built from NOR gates? Well, I am searching for a general algorithm/tips for small functions. \$\endgroup\$ – CMOS Mar 17 '16 at 10:57
1
\$\begingroup\$

I question the real value of your question, since noone ever has only simple NOR gates to work with in practice. There are algorithms for finding near-optimal minimised solutions to less trivial expressions. https://en.m.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer

Brute force is the best approach for a small problem, I fear.

\$\endgroup\$

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.