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\$
6
  • \$\begingroup\$ google.com/… \$\endgroup\$
    – Andy aka
    Commented Mar 16, 2016 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
    Commented Mar 16, 2016 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
    Commented Mar 16, 2016 at 19:36
  • \$\begingroup\$ Yes, so what didn't you see on the linked page (hint 1st picture)? \$\endgroup\$
    – Andy aka
    Commented Mar 16, 2016 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
    Commented Mar 17, 2016 at 10:57

1 Answer 1

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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.