1
$\begingroup$
  • 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?

$\endgroup$

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.