# Logic in terms of 'gates' and 'circuits'

So, I think I have a reasonably good grasp of the mechanics of boolean algebra, truth tables, etc. But I start to get confused when I see boolean functions introduced in the context of 'gates' and 'circuits,' or we have a problem to the effect of stringing together multiple gates to generate some other gate, where the entirety of such a diagram is a 'circuit.' As I look into this more, it seems as though the issue of 'gates' and 'circuits' is just a different way to represent these boolean functions (AND, OR, NAND, etc. -- I think there are some others I don't know by name, but could recognize).

If I understand it correctly, a 'gate' is essentially a function that takes inputs in propositions (or, apparently, truth values themselves can be inputs, i.e., T for some arbitrary true proposition). It could take one input, in the form of negation, in which case it produces the negation of the proposition, while an 'and' gate takes two inputs--two propositions/truth values--and produces a truth value, either T or F, depending on whether we would write 'T' for that particular row of the truth table. If we apply multiple gates--or functions, if this is correct, as I think this is an easier way to think of this--we get a 'circuit.'

I could have perhaps answered my own question here, but could someone tell me whether I'm correct in these above explanations? If not, what am I missing? Any other insights on this topic would be greatly appreciated.

• Looks like the correct interpretation. Then you go to draw the circuit, or go from a drawing back to the Boolean. – coffeemath Jan 24 '18 at 4:16
• You've nicely described everything there. You should be confident about what you've written, it's correct. – Gaurang Tandon Jan 24 '18 at 4:16
• bingo, you got it – XRBtoTheMOON Jan 24 '18 at 4:18
• Excellent--thank you! And, as a quick follow-up question: when you say going from the drawing back to the boolean, do you mean going from the diagram back to the truth table (or, I suppose specifically, a particular line of the truth table)? – user465188 Jan 24 '18 at 4:18

While you do seem to have the general idea, there is some terminological confusion in what you've written. Frankly, this confusion is probably not your fault.

A proposition is a formula that can be assigned a truth value. That is, it is a piece of syntax (perhaps represented by an abstract syntax tree). You might have something like $P\land \neg Q$.

In the context of classical propositional logic, we interpret propositions into some two element set. We typically refer to them as "true" and "false" or use symbols like "T" and "F" or $0$ and $1$, but any two element set would do. It could be "cat" and "dog" for all it matters. I'll use $0$ and $1$. As part of the definition of this interpretation, we require the interpretation to interpret the logical connectives, like $\land$ and $\neg$, into particular functions. For example, $\neg$ is required to be interpreted into the function that sends $0$ to $1$ and $1$ to $0$. A function whose inputs and output come from two element sets are referred to as Boolean functions.

A gate corresponds to a Boolean function. Its inputs are conceptually elements of a given two element set. There is no a priori meaning to the elements of that set. In particular, they don't need to correspond to the truth values of some proposition. We often talk about the inputs of a gate being $0$/$1$ or "low"/"high" or "on"/"off". Simplifying a bit, a (combinational) circuit is then just a composition of Boolean functions. There's actually a bit of subtlety here as normal algebraic notation doesn't have a good way of representing sharing. Sharing corresponds to an output of a gate that is used as an input to multiple other gates. For the purpose of the functional behavior, you can simply duplicate the algebraic expressions in that case, though that could lead to very large expressions for relatively small circuits. If every output is used once, then this won't be an issue.

So gates don't "take inputs in propositions" nor "produce propositions". They take inputs in some given two element set and produce outputs in the same set. The soundness and completeness theorems of classical propositional logic link Boolean functions to formulas in classical propositional logic. This means we can leverage logical techniques to help understand and simplify Boolean functions. But this is a bridge between two separate worlds: syntax and semantics. Just because it's possible to interpret a formula as a Boolean function, doesn't make them the same thing.

In practice, there is more that goes on with gates and circuits as used in e.g. computer hardware. As I alluded to earlier, a single expression built from Boolean functions can potentially be realized by multiple distinct circuits depending on how the gates are wired together in the circuit. These distinctions are definitely not immaterial to circuit design. There are often gates that have multiple outputs as well as multiple inputs. While, again, this doesn't really matter for the functional description, it presents more ways an algebraic representation is inadequate. Things get really different when you allow feedback, i.e. outputs of later gates being inputs of earlier gates. When this is allowed, we talk about sequential circuits, and we can no longer represent the functional behavior of the circuit as a Boolean function. In this case, we need timing information about the gates beyond just their functional behavior. In this context, circuits correspond more to something like temporal logic.

• I appreciate this very detailed reply. I find myself somewhat confused, however, on one point. You wrote: "They take inputs in some given two element set and produce outputs in the same set." The two-element set, as I understand it, could be {T, F} (usually the case, in my experience), {1,2}, etc. While I understand that we could enter a constant into a gate by, for example, entering a proposition p and True, the result of which is p since $p \wedge T \equiv p$, what you wrote seems to imply--please correct me if I'm wrong--that any proposition couldn't be entered into the gate. – user465188 Jan 24 '18 at 6:45
• There is the logical connective $\land$ which takes two well-formed formulas and builds a larger well-formed formula. Then there is the Boolean function which I'll call $\mathsf{and}$ and which might be defined as $\mathbf{and}(x,y)=\begin{cases}1,&\text{if }x=1\text{ and }y=1\\0,&\text{otherwise}\end{cases}$, and this latter thing is what corresponds to a gate. $p\land T$ is not $0$ or $1$, so it is not an input of $\mathsf{and}$. To come at it from the other side, $p\land T\neq p$. $p\land T$ and $p$ are logically equivalent but they are not equal. The set of formulas is infinite. – Derek Elkins left SE Jan 24 '18 at 7:16
• If you have experience with programming, the distinction between syntax and semantics is the difference between a program's source code and its behavior. The program print(3+5) is a different program than print(8), the source code files don't even have the same length, but they behave the same when interpreted. Similarly, formulas correspond to source code and $p\land T$ and $p$ correspond to distinct programs that when interpreted as Boolean functions produce the same Boolean function. Saying a gate produces a proposition is like saying you have a program whose output is source code. – Derek Elkins left SE Jan 24 '18 at 7:16