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.
Best Answer
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.