• 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.