# Logic minimization via 2 inputs NOR gates: Is it monotone w.r.t to adding a minterm?

• notation: $$x+y:=\mbox{OR}(x,y)$$, $$\bar x:=\mbox{NOT}(x)$$, $$xy:=\mbox{AND}(x,y)$$, 1:=TRUE, 0:=FALSE.

• Let $$f$$ be a Boolean function of $$n$$-variables, i.e. $$f: \{0,1\}^n \to \{0,1\}$$.

• minterm:= any product (AND) of $$n$$ literals (complemented or uncomplemented). e.g, $$x_1 \bar x_2 x_3$$ is a minterm in 3 variables

• $$\mbox{NOR2}(f)$$ is the minimum number of 2-input NOR gates required to represent a given function $$f$$. For instance, $$\mbox{NOR2}(x_1 x_2)=3$$.

Let $$f_1= m_1, f_2=m_2$$, where $$m_1, m_2$$ are minterms that are co-prime (i.e, $$f_1+f_2$$ can't be minimized further. In other words, $$m_1,m_2$$ are prime implicants of $$f_1+f_2$$). For instance, $$x_1 \bar x_2 x_3$$ and $$x_1 x_2 \bar x_3$$ are co-prime

Then, is the following true? $$\mbox{NOR2}(f_1+f_2)\ge \mbox{max}\{ \mbox{NOR2}(f_1), \mbox{NOR2}(f_2) \}$$

[i.e, adding two coprime minterms can't yield a 2-input NOR circuit with fewer gates]

I think it is true but I can't think of a proof. Any ideas on how to start proving it?