2

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.

Node.JS
  • 1,119
  • AFAIK, in general, finding simplest equivalent expression only in terms of $\text{NOR}$ is NP-hard. There are certainly some tricks, but most software, even, is essentially brute-force assessments of truth-tables. – Graviton Jan 15 '23 at 22:14

2 Answers2

2

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.

amrsa
  • 12,917
  • I don't understand how you converted $(A+C)(B+C)(B+D)$ to $(AB+C)(B+D)$ – Node.JS Jan 20 '23 at 19:13
  • @Node.JS Distributivity: $(A+C)(B+C)=AB+C$. You see, in Boolean algebras, distributivity works both ways, that is, each of the binary operations distributes over the other. – amrsa Jan 20 '23 at 19:16
  • 1
    You can also use the other distributivity and absorption to reach the same conclusion: $$(A+C)(B+C)=AB+AC+BC+C=AB+C,$$ since $BC+C=C$, by absorption and then $AC+C=C$. – amrsa Jan 20 '23 at 19:19
  • The last comment was very helpful. Thank you so much. Really appreciate it – Node.JS Jan 20 '23 at 19:27
1

WolframAlpha returns

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

You can derive it by using the steps here.

RobPratt
  • 45,619