Like all popular and attractive people, I am interested in logic circuits. A logic circuit is an arrangement of interconnected logic gates, which are simple models of boolean operations. They essentially work like redstone from Minecraft. They can be thought of as an idealized electrical circuit where there are only two possible states for any given input, output, or wire: True or False (or equivalently 1 or 0, or On and Off). Different components can output various combinations of signals depending on their input signals. They are an important concept in computer science since this model is essentially how computers work on a very basic level. Logic gates are also directly implemented in most modern programming languages in the form of boolean operators like "AND" (&&), "OR" (||), and "NOT" (!), which are needed to control conditional statements.
One problem of interest with regard to logic circuits is the circuit satisfiability problem (CSAT), where we are given a logic circuit with multiple inputs and a single output, and the problem is to choose a set of True/False inputs that will cause the output to evaluate as True. The decision version of the problem is simply to determine whether or not this is possible. It is closely related to the boolean satisfiability problem (SAT), and both SAT and CSAT are NP-complete (in fact, SAT was the first problem ever proven to be NP-complete).
If your goal is to figure out a set of inputs that cause a logic circuit to output True, a very dumb but straightforward method would be just to try every possible combination of inputs and check the output value for each of them. This kind of exhaustive search is not really tractable for large problems since the number of combinations to check grows exponentially with the number of inputs, but for a small circuit it is easy for a computer to do. The results of this process can be used to generate a truth table for the circuit, where each row displays an input combination and its resulting output.
For example, consider the logic circuit below, which contains three inputs (IN1, IN2, and IN3), one output (OUT), and four logic gates, including: NOT (which outputs the negation of its input), AND (which outputs True if and only if both inputs are True), and OR (which outputs True if and only if at least one input is True). Wires carrying True signals are shown in red.
Some combinations of input, like "IN1 = True, IN2 = False, IN3 = True" (shown in the middle above) produce a False output. It happens that only one possible input, "IN1 = True, IN2 = True, IN3 = True", results in a True output. The logic table below shows every possible input combination and its resulting output. The table could be expanded to also include intermediate values, like the outputs of the individual gates, but here we are displaying only the final results.
| IN1 | IN2 | IN3 | OUT |
|---|---|---|---|
| F | F | F | F |
| F | F | T | F |
| F | T | F | F |
| F | T | T | F |
| T | F | F | F |
| T | F | T | F |
| T | T | F | F |
| T | T | T | T |
In order to facilitate this process, and as a personal exercise, I wrote a Python module for automatically generating logic circuit truth tables. This is an ongoing project that I would like to add more to over time, but in the meantime the current version is available on GitHub:
This is a Python module that defines a variety of logic gate classes (including common gates like NOT, AND, OR, XOR, NAND, NOR, and XNOR, as well as technical gates like splitters and switches), as well as a few classes and methods for loading logic circuits from an external file and for generating truth tables. A logic circuit can be defined by instantiating each gate one-by-one and defining which gate outputs should feed into which gate inputs. Arbitrary signals can be fed to the system's input gates and the entire circuit can be automatically updated to determine the states of all output gates. There is also a truth table class which allows a set of input and output gates to be specified, and its main method cycles through every possible combination of input settings to produce a truth table for the circuit.
This project is a work in progress. I would eventually like to implement a mouse-driven GUI that allows the user to place and connect logic gates by hand, as well as drawing the status of the circuit similar to the above pictures. In the meantime, though, you will just have to find satisfaction in knowing all of the calculations that your computer is silently performing.
