What is the most unambiguous digraph representation of NAND/NOR?

62 Views Asked by At

Is there an official or standardized way to represent the basic boolean operations with directed graphs? (I don't mean like in circuit diagrams.)

If so, what is it? And if not, I would also accept an alternative graph representation that improves on or makes more fundamental sense and is less open to misinterpretation than my own.

For background, my take on the question is given below.


It is my experience that one can represent a basic operation with an unlabeled small directed graph such that the representation is almost unambiguous, regardless of interpretation.

simple cycle

For example, this represents anything cycling between two states. For my purposes, I imagine it as a logical NOT, but someone looking at this and guessing it generates an endless boolean string of $0101010\dots$ is in the same ballpark.

I was trying to come up with the same thing for a NAND/NOR operation and came up with the following two graphs. One is minimalist (labels are provided only for exposition here):

nand_graph_1

The idea being that there are only two vertices, one true, one false. An edge is formed from each of the two nodes that can possibly be an input, back to one or both of the nodes where valid.

e.g. In this case (NOR), the only thing that can't happen is T being an input yielding T (since only $(F,F)\to T$). The three other edges do appear; note by swapping F/T, you swap NAND/NOR. The same general 2-vertex approach can be used with AND/OR (again allowing F/T label switch to change between AND/OR), XOR/XNOR, and NOT as shown up top.

My more explicit attempt was the following, and again the labels are only present to clarify.

5-node_nand

This one shows the three possible ways two inputs can combine, and the resulting output. As before, if you swap all the T/F labels, you swap between NAND and NOR.

1

There are 1 best solutions below

0
On

What you are trying to construct for the NAND/NOR operators is a state diagram, specifically one for a Moore machine. However, for all but the simplest machines, it is impossible to avoid specifying states or inputs. It was made possible for the NOT operator because its a unary operator, and thus the state and input coincide. Your first graph is ideal enough.