# Optimally convert (small) boolean expressions into NOR form by hand

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.

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