Convert a boolean expression to just NOR operatons

134 Views Asked by At

How do we convert this expression to just $\text{NOR}$ operation?

$$A \cdot B + B \cdot C + C \cdot D$$

My attempt:

$A \cdot B + B \cdot C + C \cdot D = \overline{\overline{A \cdot B + B \cdot C + C \cdot D}} $

Using De Morgan's law

$ \to \overline{\overline{(A \cdot B)} \cdot \overline{(B \cdot C)} \cdot \overline{(C \cdot D)}} $

Using $X \text { NOR } Y = \overline{X} \cdot \overline{Y}$

$\to \overline{{(A \cdot B)} \text{ NOR } {(B \cdot C)} \text{ NOR } {(C \cdot D)}}$

Using $X \text { NOR } Y = \overline{X} \cdot \overline{Y}$

$\to \overline{{(\overline{A} \text{ NOR } \overline{B})} \text{ NOR } {(\overline{B} \text{ NOR } \overline{C})} \text{ NOR } {(\overline{C} \text{ NOR } \overline{D})}}$

Using $X \text { NOR } X = \overline{X} $

$\to \overline{((A \text{ NOR } A) \text{ NOR } (B \text{ NOR } B)) \text{ NOR } ((B \text{ NOR } B) \text{ NOR } (C \text{ NOR } C)) \text{ NOR } ((C \text{ NOR } C) \text{ NOR } (D \text{ NOR } D))}$

Using $X \text { NOR } X = \overline{X} $

$\to (((A \text{ NOR } A) \text{ NOR } (B \text{ NOR } B)) \text{ NOR } ((B \text{ NOR } B) \text{ NOR } (C \text{ NOR } C)) \text{ NOR } ((C \text{ NOR } C) \text{ NOR } (D \text{ NOR } D))) \text{ NOR } (((A \text{ NOR } A) \text{ NOR } (B \text{ NOR } B)) \text{ NOR } ((B \text{ NOR } B) \text{ NOR } (C \text{ NOR } C)) \text{ NOR } ((C \text{ NOR } C) \text{ NOR } (D \text{ NOR } D)))$

I am wondering if is there a better solution that return something simpler.

2

There are 2 best solutions below

1
On

WolframAlpha returns

(a NOR c) NOR (b NOR c) NOR (b NOR d)

You can derive it by using the steps here.

4
On

Let us use the Peirce's arrow notation for $\mathrm{NOR}$, that is, denote $A \,\mathrm{NOR}\, B$ by $A \downarrow B$.
Given that you can define $A \downarrow B$ as $(A+B)'$, and also recapture the Boolean operations from Peirce's arrow, it's certainly possible to start from your expression $$AB+BC+CD,$$ and obtain $$(A\downarrow C) \downarrow (B\downarrow C) \downarrow (B\downarrow D).$$ Here, one must observe that $\downarrow$ is not associative (as it can easily be observed), and so the ternary version as to be explicitly defined (like the binary one), as $$U \downarrow V \downarrow W = (U+V+W)'.$$ Then it is possible to arrive at the ternary operator in terms of the binary one using \begin{align} (U+V+W)' &= U'V'W'\\ &= (U+V)'W'\\ &= (U \downarrow V)(W \downarrow W)\\ &= ((U \downarrow V)\downarrow(U \downarrow V)) \downarrow((W \downarrow W)\downarrow(W \downarrow W)). \end{align} This way, we can use the ternary $\downarrow$ as a shortcut.

Here I won't go from the start expression to the final one but take the opposite path.
Going from the starting one to the final would be the real answer.
Yet, you also have that here, by going backwards, but without the insight that lead to the final expression (I don't have that insight and I suppose the comment of Graviton in the question suggests that it's very difficult).
So backwards, \begin{align} (A\downarrow C) \downarrow (B\downarrow C) \downarrow (B\downarrow D) &= ((A\downarrow C) + (B\downarrow C) + (B\downarrow D))'\\ &= ((A+C)' + (B+C)' + (B+D)')'\\ &= (A+C)(B+C)(B+D)\\ &= (AB+C)(B+D)\\ &= AB+ABD+BC+CD\\ &=AB+BC+CD. \end{align} It should be noted that replacing the ternary operator with the real binary one, will again give a huge expression whose meaning is difficult to capture.
Sometimes, that's the price of doing it with less operations.